[InstCombine] Fold trunc nuw i1 to false when dominated by icmp. #151961

andjo403 · 2025-08-04T13:30:27Z

Proof: https://alive2.llvm.org/ce/z/4BOiFF

llvmbot · 2025-08-04T13:30:58Z

@llvm/pr-subscribers-llvm-transforms

Author: Andreas Jonson (andjo403)

Changes

Proof: https://alive2.llvm.org/ce/z/4BOiFF

Full diff: https://github.com/llvm/llvm-project/pull/151961.diff

2 Files Affected:

(modified) llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp (+32)
(modified) llvm/test/Transforms/InstCombine/trunc.ll (+140)

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp
index a43a6ee1f58b0..8529d7b30b56d 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp
@@ -951,6 +951,38 @@ Instruction *InstCombinerImpl::visitTrunc(TruncInst &Trunc) {
     }
   }
 
+  // Fold Trunc nuw i1 With Dominating ICmp
+  if (DestWidth == 1 && Trunc.hasNoUnsignedWrap()) {
+    auto HandleDomCond = [&](ICmpInst::Predicate DomPred,
+                             const APInt *DomC) -> Instruction * {
+      ConstantRange DominatingCR =
+          ConstantRange::makeExactICmpRegion(DomPred, *DomC);
+      if (!DominatingCR.contains(APInt(SrcWidth, 1)))
+        return replaceInstUsesWith(Trunc, Builder.getFalse());
+      return nullptr;
+    };
+
+    for (BranchInst *BI : DC.conditionsFor(Src)) {
+      CmpPredicate DomPred;
+      const APInt *DomC;
+      if (!match(BI->getCondition(),
+                 m_ICmp(DomPred, m_Specific(Src), m_APInt(DomC))))
+        continue;
+
+      BasicBlockEdge Edge0(BI->getParent(), BI->getSuccessor(0));
+      if (DT.dominates(Edge0, Trunc.getParent())) {
+        if (auto *V = HandleDomCond(DomPred, DomC))
+          return V;
+      } else {
+        BasicBlockEdge Edge1(BI->getParent(), BI->getSuccessor(1));
+        if (DT.dominates(Edge1, Trunc.getParent()))
+          if (auto *V =
+                  HandleDomCond(CmpInst::getInversePredicate(DomPred), DomC))
+            return V;
+      }
+    }
+  }
+
   if (DestWidth == 1 &&
       (Trunc.hasNoUnsignedWrap() || Trunc.hasNoSignedWrap()) &&
       isKnownNonZero(Src, SQ.getWithInstruction(&Trunc)))
diff --git a/llvm/test/Transforms/InstCombine/trunc.ll b/llvm/test/Transforms/InstCombine/trunc.ll
index dfe9d941f840c..a03aa88063247 100644
--- a/llvm/test/Transforms/InstCombine/trunc.ll
+++ b/llvm/test/Transforms/InstCombine/trunc.ll
@@ -1218,3 +1218,143 @@ define i2 @neg_trunc_nsw_i2_non_zero(i8 %1) {
   %ret = trunc nsw i8 %1 to i2
   ret i2 %ret
 }
+
+define i1 @trunc_nuw_i1_dominating_icmp_ne_1(i8 %x) {
+; CHECK-LABEL: @trunc_nuw_i1_dominating_icmp_ne_1(
+; CHECK-NEXT:    [[ICMP_NOT:%.*]] = icmp eq i8 [[X:%.*]], 1
+; CHECK-NEXT:    br i1 [[ICMP_NOT]], label [[BB2:%.*]], label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    ret i1 false
+; CHECK:       bb2:
+; CHECK-NEXT:    ret i1 true
+;
+  %icmp = icmp ne i8 %x, 1
+  br i1 %icmp, label %bb1, label %bb2
+bb1:
+  %ret1 = trunc nuw i8 %x to i1
+  ret i1 %ret1
+bb2:
+  %ret2 = trunc nuw i8 %x to i1
+  ret i1 %ret2
+}
+
+define i1 @trunc_nuw_i1_dominating_icmp_eq_1(i8 %x) {
+; CHECK-LABEL: @trunc_nuw_i1_dominating_icmp_eq_1(
+; CHECK-NEXT:    [[ICMP:%.*]] = icmp eq i8 [[X:%.*]], 1
+; CHECK-NEXT:    br i1 [[ICMP]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    ret i1 true
+; CHECK:       bb2:
+; CHECK-NEXT:    ret i1 false
+;
+  %icmp = icmp eq i8 %x, 1
+  br i1 %icmp, label %bb1, label %bb2
+bb1:
+  %ret1 = trunc nuw i8 %x to i1
+  ret i1 %ret1
+bb2:
+  %ret2 = trunc nuw i8 %x to i1
+  ret i1 %ret2
+}
+
+define i1 @trunc_nuw_i1_dominating_icmp_ne_0(i8 %x) {
+; CHECK-LABEL: @trunc_nuw_i1_dominating_icmp_ne_0(
+; CHECK-NEXT:    [[ICMP_NOT:%.*]] = icmp eq i8 [[X:%.*]], 0
+; CHECK-NEXT:    br i1 [[ICMP_NOT]], label [[BB2:%.*]], label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    ret i1 true
+; CHECK:       bb2:
+; CHECK-NEXT:    ret i1 false
+;
+  %icmp = icmp ne i8 %x, 0
+  br i1 %icmp, label %bb1, label %bb2
+bb1:
+  %ret1 = trunc nuw i8 %x to i1
+  ret i1 %ret1
+bb2:
+  %ret2 = trunc nuw i8 %x to i1
+  ret i1 %ret2
+}
+
+define i1 @trunc_nuw_i1_dominating_icmp_eq_0(i8 %x) {
+; CHECK-LABEL: @trunc_nuw_i1_dominating_icmp_eq_0(
+; CHECK-NEXT:    [[ICMP:%.*]] = icmp eq i8 [[X:%.*]], 0
+; CHECK-NEXT:    br i1 [[ICMP]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    ret i1 false
+; CHECK:       bb2:
+; CHECK-NEXT:    ret i1 true
+;
+  %icmp = icmp eq i8 %x, 0
+  br i1 %icmp, label %bb1, label %bb2
+bb1:
+  %ret1 = trunc nuw i8 %x to i1
+  ret i1 %ret1
+bb2:
+  %ret2 = trunc nuw i8 %x to i1
+  ret i1 %ret2
+}
+
+define i1 @neg_trunc_i1_dominating_icmp_ne_1(i8 %x) {
+; CHECK-LABEL: @neg_trunc_i1_dominating_icmp_ne_1(
+; CHECK-NEXT:    [[ICMP_NOT:%.*]] = icmp eq i8 [[X:%.*]], 1
+; CHECK-NEXT:    br i1 [[ICMP_NOT]], label [[BB2:%.*]], label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[RET1:%.*]] = trunc i8 [[X]] to i1
+; CHECK-NEXT:    ret i1 [[RET1]]
+; CHECK:       bb2:
+; CHECK-NEXT:    ret i1 true
+;
+  %icmp = icmp ne i8 %x, 1
+  br i1 %icmp, label %bb1, label %bb2
+bb1:
+  %ret1 = trunc i8 %x to i1
+  ret i1 %ret1
+bb2:
+  %ret2 = trunc i8 %x to i1
+  ret i1 %ret2
+}
+
+define i2 @neg_trunc_nuw_i2_dominating_icmp_ne_1(i8 %x) {
+; CHECK-LABEL: @neg_trunc_nuw_i2_dominating_icmp_ne_1(
+; CHECK-NEXT:    [[ICMP_NOT:%.*]] = icmp eq i8 [[X:%.*]], 1
+; CHECK-NEXT:    br i1 [[ICMP_NOT]], label [[BB2:%.*]], label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[RET1:%.*]] = trunc nuw i8 [[X]] to i2
+; CHECK-NEXT:    ret i2 [[RET1]]
+; CHECK:       bb2:
+; CHECK-NEXT:    ret i2 1
+;
+  %icmp = icmp ne i8 %x, 1
+  br i1 %icmp, label %bb1, label %bb2
+bb1:
+  %ret1 = trunc nuw i8 %x to i2
+  ret i2 %ret1
+bb2:
+  %ret2 = trunc nuw i8 %x to i2
+  ret i2 %ret2
+}
+
+define i1 @neg_trunc_nuw_i1_not_dominating_icmp_ne_1(i8 %x, i1 %y) {
+; CHECK-LABEL: @neg_trunc_nuw_i1_not_dominating_icmp_ne_1(
+; CHECK-NEXT:    br i1 [[Y:%.*]], label [[BB1:%.*]], label [[BB0:%.*]]
+; CHECK:       bb0:
+; CHECK-NEXT:    [[ICMP_NOT:%.*]] = icmp eq i8 [[X:%.*]], 1
+; CHECK-NEXT:    br i1 [[ICMP_NOT]], label [[BB2:%.*]], label [[BB1]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[RET1:%.*]] = trunc nuw i8 [[X]] to i1
+; CHECK-NEXT:    ret i1 [[RET1]]
+; CHECK:       bb2:
+; CHECK-NEXT:    ret i1 true
+;
+  br i1 %y, label %bb1, label %bb0
+bb0:
+  %icmp = icmp ne i8 %x, 1
+  br i1 %icmp, label %bb1, label %bb2
+bb1:
+  %ret1 = trunc nuw i8 %x to i1
+  ret i1 %ret1
+bb2:
+  %ret2 = trunc nuw i8 %x to i1
+  ret i1 %ret2
+}

andjo403 · 2025-08-04T13:31:25Z

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

+
  if (DestWidth == 1 &&
      (Trunc.hasNoUnsignedWrap() || Trunc.hasNoSignedWrap()) &&
      isKnownNonZero(Src, SQ.getWithInstruction(&Trunc)))


only added fold to false as the fold to true is handled here

dtcxzyw

LG.

dtcxzyw · 2025-08-05T02:40:02Z

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

    }
  }

+  // Fold Trunc nuw i1 With Dominating ICmp


Suggested change

// Fold Trunc nuw i1 With Dominating ICmp

// Fold trunc nuw i1 with dominating icmp.

nikic

This does not look like a great fit for InstCombine. Would (IP)SCCP be able to handle this if we teach ConstantRange::truncate() to make use of the nuw flag?

dtcxzyw · 2025-08-05T12:20:08Z

This does not look like a great fit for InstCombine. Would (IP)SCCP be able to handle this if we teach ConstantRange::truncate() to make use of the nuw flag?

It is also required by #110511 (comment).

nikic · 2025-08-17T14:37:00Z

Can this be closed now that the SCCP support has landed?

andjo403 · 2025-08-17T19:01:08Z

this PR still gives changes in the llvm-opt-benchmark when I run it locally after the SCCP PR was merged.
eg bench/zed-rs/optimized/f2m41hcwghjno5p8tkrposn1f.ll and bench/ruff-rs/optimized/8dg5gv1ul0w7vccunqd3ii3jp.ll from the first run https://github.com/dtcxzyw/llvm-opt-benchmark/pull/2643/files.
but it is only 15 files now from 71 before and some of the files changed was not part of the first run.

I can try to look at why SCCP is not enough.

background for why I added this here was that I fund this fold for icmp and was thinking of adding trunc nuw support there and was not able to find something similar for trunc.

llvm-project/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

Lines 1407 to 1480 in 0561ff6

    
           Instruction *InstCombinerImpl::foldICmpWithDominatingICmp(ICmpInst &Cmp) { 
        
             // We already checked simple implication in InstSimplify, only handle complex 
        
             // cases here. 
        
             Value *X = Cmp.getOperand(0), *Y = Cmp.getOperand(1); 
        
             const APInt *C; 
        
             if (!match(Y, m_APInt(C))) 
        
               return nullptr; 
        
             CmpInst::Predicate Pred = Cmp.getPredicate(); 
        
             ConstantRange CR = ConstantRange::makeExactICmpRegion(Pred, *C); 
        
             auto handleDomCond = [&](ICmpInst::Predicate DomPred, 
        
                                      const APInt *DomC) -> Instruction * { 
        
               // We have 2 compares of a variable with constants. Calculate the constant 
        
               // ranges of those compares to see if we can transform the 2nd compare: 
        
               // DomBB: 
        
               //   DomCond = icmp DomPred X, DomC 
        
               //   br DomCond, CmpBB, FalseBB 
        
               // CmpBB: 
        
               //   Cmp = icmp Pred X, C 
        
               ConstantRange DominatingCR = 
        
                   ConstantRange::makeExactICmpRegion(DomPred, *DomC); 
        
               ConstantRange Intersection = DominatingCR.intersectWith(CR); 
        
               ConstantRange Difference = DominatingCR.difference(CR); 
        
               if (Intersection.isEmptySet()) 
        
                 return replaceInstUsesWith(Cmp, Builder.getFalse()); 
        
               if (Difference.isEmptySet()) 
        
                 return replaceInstUsesWith(Cmp, Builder.getTrue()); 
        
               // Canonicalizing a sign bit comparison that gets used in a branch, 
        
               // pessimizes codegen by generating branch on zero instruction instead 
        
               // of a test and branch. So we avoid canonicalizing in such situations 
        
               // because test and branch instruction has better branch displacement 
        
               // than compare and branch instruction. 
        
               bool UnusedBit; 
        
               bool IsSignBit = isSignBitCheck(Pred, *C, UnusedBit); 
        
               if (Cmp.isEquality() || (IsSignBit && hasBranchUse(Cmp))) 
        
                 return nullptr; 
        
               // Avoid an infinite loop with min/max canonicalization. 
        
               // TODO: This will be unnecessary if we canonicalize to min/max intrinsics. 
        
               if (Cmp.hasOneUse() && 
        
                   match(Cmp.user_back(), m_MaxOrMin(m_Value(), m_Value()))) 
        
                 return nullptr; 
        
               if (const APInt *EqC = Intersection.getSingleElement()) 
        
                 return new ICmpInst(ICmpInst::ICMP_EQ, X, Builder.getInt(*EqC)); 
        
               if (const APInt *NeC = Difference.getSingleElement()) 
        
                 return new ICmpInst(ICmpInst::ICMP_NE, X, Builder.getInt(*NeC)); 
        
               return nullptr; 
        
             }; 
        
             for (BranchInst *BI : DC.conditionsFor(X)) { 
        
               CmpPredicate DomPred; 
        
               const APInt *DomC; 
        
               if (!match(BI->getCondition(), 
        
                          m_ICmp(DomPred, m_Specific(X), m_APInt(DomC)))) 
        
                 continue; 
        
               BasicBlockEdge Edge0(BI->getParent(), BI->getSuccessor(0)); 
        
               if (DT.dominates(Edge0, Cmp.getParent())) { 
        
                 if (auto *V = handleDomCond(DomPred, DomC)) 
        
                   return V; 
        
               } else { 
        
                 BasicBlockEdge Edge1(BI->getParent(), BI->getSuccessor(1)); 
        
                 if (DT.dominates(Edge1, Cmp.getParent())) 
        
                   if (auto *V = 
        
                           handleDomCond(CmpInst::getInversePredicate(DomPred), DomC)) 
        
                     return V; 
        
               } 
        
             } 
        
             return nullptr; 
        
           }

nikic · 2025-08-17T19:28:10Z

@andjo403 It's possible that #153003 may help for the remaining cases.

andjo403 · 2025-08-17T19:32:01Z

forgot to mention that I tried to run with #153003 applied also but there still was 15 files changed have not looked if it was the same changes

andjo403 · 2025-08-17T21:00:09Z

hmm maybe it was git that tricked me, it was not happy with more then 10k changed files, when I checked bench/ruff-rs/optimized/8dg5gv1ul0w7vccunqd3ii3jp.ll with this PR vs #153003 there was only changes of names on variables so that PR helps a least.

andjo403 · 2025-08-20T15:42:43Z

seems like most was solved by #153003

andjo403 added 2 commits August 4, 2025 15:19

[InstCombine] Add test for trunc with dominating icmp.

f13dc12

[InstCombine] Fold trunc nuw i1 to false when dominated by icmp.

424fe1e

andjo403 requested review from dtcxzyw and nikic August 4, 2025 13:30

llvmbot added llvm:instcombine Covers the InstCombine, InstSimplify and AggressiveInstCombine passes llvm:transforms labels Aug 4, 2025

andjo403 commented Aug 4, 2025

View reviewed changes

andjo403 mentioned this pull request Aug 4, 2025

Task submission dtcxzyw/llvm-opt-benchmark#1312

Open

zyw-bot mentioned this pull request Aug 4, 2025

pre-commit: PR151961 dtcxzyw/llvm-opt-benchmark#2643

Closed

dtcxzyw approved these changes Aug 5, 2025

View reviewed changes

nikic reviewed Aug 5, 2025

View reviewed changes

This was referenced Aug 11, 2025

[PredicateInfo] Handle trunc nuw i1 condition. #152988

Merged

[SCCP] Add support for trunc nuw range. #152990

Merged

andjo403 closed this Aug 20, 2025

andjo403 deleted the truncNuwDominatingIcmp branch August 22, 2025 19:41

	// Fold Trunc nuw i1 With Dominating ICmp
	// Fold trunc nuw i1 with dominating icmp.

[InstCombine] Fold trunc nuw i1 to false when dominated by icmp. #151961

[InstCombine] Fold trunc nuw i1 to false when dominated by icmp. #151961

Uh oh!

Conversation

andjo403 commented Aug 4, 2025

Uh oh!

llvmbot commented Aug 4, 2025

Uh oh!

andjo403 Aug 4, 2025

Choose a reason for hiding this comment

Uh oh!

dtcxzyw left a comment

Choose a reason for hiding this comment

Uh oh!

dtcxzyw Aug 5, 2025

Choose a reason for hiding this comment

Uh oh!

nikic left a comment

Choose a reason for hiding this comment

Uh oh!

dtcxzyw commented Aug 5, 2025

Uh oh!

nikic commented Aug 17, 2025

Uh oh!

andjo403 commented Aug 17, 2025

Uh oh!

nikic commented Aug 17, 2025

Uh oh!

andjo403 commented Aug 17, 2025

Uh oh!

andjo403 commented Aug 17, 2025

Uh oh!

andjo403 commented Aug 20, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants