[SimplifyIndVar] Constant fold IV users

[etherzhhb]

Summary

This patch tries to transform cases like:

for (unsigned i = 0; i < N; i += 2) {
  bool c0 = (i & 0x1) == 0;
  bool c1 = ((i + 1) & 0x1) == 1;
}

To

for (unsigned i = 0; i < N; i += 2) {
  bool c0 = true;
  bool c1 = true;
}

[etherzhhb]

Fix typo

[sanjoy]

Nice!

lib/Transforms/Utils/SimplifyIndVar.cpp

547 ↗

(On Diff #116642)

s/ParentLoop/L

ParentLoop would can be confused with the parent loop of the loop containing I

test/Transforms/IndVarSimplify/replace-srem-by-urem.ll

74 ↗

(On Diff #116642)

Did you change this to prevent constant folding? If so, please mention that in the commit message.

[etherzhhb]

test/Transforms/IndVarSimplify/replace-srem-by-urem.ll

74 ↗

(On Diff #116642)

Ok, I am thinking to copy this case over to constant-fold.ll

llvm/trunk/lib/Transforms/Utils/SimplifyIndVar.cpp

 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "indvars"
 
 STATISTIC(NumElimIdentity, "Number of IV identities eliminated");
 STATISTIC(NumElimOperand,  "Number of IV operands folded into a use");
+STATISTIC(NumFoldedUser, "Number of IV users folded into a constant");
 STATISTIC(NumElimRem     , "Number of IV remainder operations eliminated");
 STATISTIC(
     NumSimplifiedSDiv,
     "Number of IV signed division operations converted to unsigned division");
 STATISTIC(
     NumSimplifiedSRem,
     "Number of IV signed remainder operations converted to unsigned remainder");
 STATISTIC(NumElimCmp     , "Number of IV comparisons eliminated");
public:
     /// Iteratively perform simplification on a worklist of users of the
     /// specified induction variable. This is the top-level driver that applies
     /// all simplifications to users of an IV.
     void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);
 
     Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
 
     bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);
+    bool foldConstantSCEV(Instruction *UseInst);
 
     bool eliminateOverflowIntrinsic(CallInst *CI);
     bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
     void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
     void simplifyIVRemainder(BinaryOperator *Rem, Value *IVOperand,
                              bool IsSigned);
     void replaceRemWithNumerator(BinaryOperator *Rem);
     void replaceRemWithNumeratorOrZero(BinaryOperator *Rem);
if (eliminateOverflowIntrinsic(CI))
       return true;
 
   if (eliminateIdentitySCEV(UseInst, IVOperand))
     return true;
 
   return false;
 }
 
+/// Replace the UseInst with a constant if possible
+bool SimplifyIndvar::foldConstantSCEV(Instruction *I) {
+  if (!SE->isSCEVable(I->getType()))
+    return false;
+
+  // Get the symbolic expression for this instruction.
+  const SCEV *S = SE->getSCEV(I);
+
+  const Loop *L = LI->getLoopFor(I->getParent());
+  S = SE->getSCEVAtScope(S, L);
+
+  if (auto *C = dyn_cast<SCEVConstant>(S)) {
+    I->replaceAllUsesWith(C->getValue());
+    DEBUG(dbgs() << "INDVARS: Replace IV user: " << *I
+                 << " with constant: " << *C << '\n');
+    ++NumFoldedUser;
+    Changed = true;
+    DeadInsts.emplace_back(I);
+    return true;
+  }
+
+  return false;
+}
+
 /// Eliminate any operation that SCEV can prove is an identity function.
 bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
                                            Instruction *IVOperand) {
   if (!SE->isSCEVable(UseInst->getType()) ||
       (UseInst->getType() != IVOperand->getType()) ||
       (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
     return false;
 
void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
   while (!SimpleIVUsers.empty()) {
     std::pair<Instruction*, Instruction*> UseOper =
       SimpleIVUsers.pop_back_val();
     Instruction *UseInst = UseOper.first;
 
     // Bypass back edges to avoid extra work.
     if (UseInst == CurrIV) continue;
 
+    // Try to replace UseInst with a constant before any other simplifications
+    if (foldConstantSCEV(UseInst))
+      continue;
+
     Instruction *IVOperand = UseOper.second;
     for (unsigned N = 0; IVOperand; ++N) {
       assert(N <= Simplified.size() && "runaway iteration");
 
       Value *NewOper = foldIVUser(UseOper.first, IVOperand);
       if (!NewOper)
         break; // done folding
       IVOperand = dyn_cast<Instruction>(NewOper);

llvm/trunk/test/Transforms/IndVarSimplify/constant-fold.ll

+; RUN: opt -indvars -S < %s | FileCheck %s
+
+define void @test0(i32* %x) {
+entry:
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.inc, %entry
+  %i.01 = phi i32 [ 0, %entry ], [ %add, %for.inc ]
+  %and = and i32 %i.01, 3
+  %cmp1 = icmp eq i32 %and, 0
+  %cond = select i1 %cmp1, i32 0, i32 1
+  store i32 %cond, i32* %x, align 4
+  %add = add i32 %i.01, 4
+  %cmp = icmp ult i32 %add, 8
+  br i1 %cmp, label %for.inc, label %for.end
+
+for.end:                                          ; preds = %for.inc
+  ret void
+}
+
+; Should fold the condition of the select into constant
+; CHECK-LABEL: void @test
+; CHECK:         icmp eq i32 0, 0
+
+define void @test1(i32* %a) {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %i.01 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %mul = mul nsw i32 %i.01, 64
+  %rem = srem i32 %mul, 8
+  %idxprom = sext i32 %rem to i64
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom
+  store i32 %i.01, i32* %arrayidx, align 4
+  %inc = add nsw i32 %i.01, 1
+  %cmp = icmp slt i32 %inc, 64
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
+; Should fold the rem since %mul is multiple of 8
+; CHECK-LABEL: @test1(
+; CHECK-NOT:     rem
+; CHECK:         sext i32 0 to i64

llvm/trunk/test/Transforms/IndVarSimplify/replace-srem-by-urem.ll

 define void @test4(i32* %a) {
 ; CHECK-LABEL: @test4(
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %entry, %for.body
   %i.01 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   %mul = mul nsw i32 %i.01, 64
-  %rem = srem i32 %mul, 8
+  %rem = srem i32 %mul, 7
 ; CHECK:     urem
 ; CHECK-NOT: srem
   %idxprom = sext i32 %rem to i64
   %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom
   store i32 %i.01, i32* %arrayidx, align 4
   %inc = add nsw i32 %i.01, 1
   %cmp = icmp slt i32 %inc, 64
   br i1 %cmp, label %for.body, label %for.end