[LoopUnrollAnalyzer] Check that we're using SCEV for the same loop we're simulating.

[mzolotukhin]

Summary

Check that we're using SCEV for the same loop we're simulating. Otherwise, we might try to use the iteration number of the current loop in SCEV expressions for inner/outer loops IVs, which is clearly incorrect.

[sanjoy]

Minor drop by comments inline

lib/Analysis/LoopUnrollAnalyzer.cpp

40

Nit: why not change this to if (!AR || AR->getLoop() != L)?

unittests/Analysis/UnrollAnalyzer.cpp

132

Do we actually need the trailing newlines? I don't think the parser actually cares, and they're somewhat distracting.

[mzolotukhin]

• Remove trailing newlines.
• Combine two conditions in simplifyInstWithSCEV.

[mzolotukhin]

Thanks, Sanjoy! I updated the patch accordingly.

Michael

[sanjoy]

lgtm

I don't know this area of code well, but this change looks fairly simple and obvious

[mzolotukhin]

Thanks! It looks like the newlines are actually necessary, so I returned them in the committed patch.

Michael

include/llvm/Analysis/LoopUnrollAnalyzer.h

class UnrolledInstAnalyzer : private InstVisitor<UnrolledInstAnalyzer, bool> {
   struct SimplifiedAddress {
     Value *Base = nullptr;
     ConstantInt *Offset = nullptr;
   };
 
 public:
   UnrolledInstAnalyzer(unsigned Iteration,
                        DenseMap<Value *, Constant *> &SimplifiedValues,
-                       ScalarEvolution &SE)
-      : SimplifiedValues(SimplifiedValues), SE(SE) {
+                       ScalarEvolution &SE, const Loop *L)
+      : SimplifiedValues(SimplifiedValues), SE(SE), L(L) {
       IterationNumber = SE.getConstant(APInt(64, Iteration));
   }
 
   // Allow access to the initial visit method.
   using Base::visit;
 
 private:
   /// \brief A cache of pointer bases and constant-folded offsets corresponding
private:
   /// While we walk the loop instructions, we build up and maintain a mapping
   /// of simplified values specific to this iteration.  The idea is to propagate
   /// any special information we have about loads that can be replaced with
   /// constants after complete unrolling, and account for likely simplifications
   /// post-unrolling.
   DenseMap<Value *, Constant *> &SimplifiedValues;
 
   ScalarEvolution &SE;
+  const Loop *L;
 
   bool simplifyInstWithSCEV(Instruction *I);
 
   bool visitInstruction(Instruction &I) { return simplifyInstWithSCEV(&I); }
   bool visitBinaryOperator(BinaryOperator &I);
   bool visitLoad(LoadInst &I);
   bool visitCastInst(CastInst &I);
   bool visitCmpInst(CmpInst &I);
 };
 }
 #endif

lib/Analysis/LoopUnrollAnalyzer.cpp

bool UnrolledInstAnalyzer::simplifyInstWithSCEV(Instruction *I) {
 
   const SCEV *S = SE.getSCEV(I);
   if (auto *SC = dyn_cast<SCEVConstant>(S)) {
     SimplifiedValues[I] = SC->getValue();
     return true;
   }
 
   auto *AR = dyn_cast<SCEVAddRecExpr>(S);
-  if (!AR)
+  if (!AR || AR->getLoop() != L)
     return false;
 
   const SCEV *ValueAtIteration = AR->evaluateAtIteration(IterationNumber, SE);
   // Check if the AddRec expression becomes a constant.
   if (auto *SC = dyn_cast<SCEVConstant>(ValueAtIteration)) {
     SimplifiedValues[I] = SC->getValue();
     return true;
   }

lib/Transforms/Scalar/LoopUnrollPass.cpp

for (Instruction &I : *L->getHeader()) {
         SimplifiedInputValues.push_back({PHI, C});
     }
 
     // Now clear and re-populate the map for the next iteration.
     SimplifiedValues.clear();
     while (!SimplifiedInputValues.empty())
       SimplifiedValues.insert(SimplifiedInputValues.pop_back_val());
 
-    UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, SE);
+    UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, SE, L);
 
     BBWorklist.clear();
     BBWorklist.insert(L->getHeader());
     // Note that we *must not* cache the size, this loop grows the worklist.
     for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
       BasicBlock *BB = BBWorklist[Idx];
 
       // Visit all instructions in the given basic block and try to simplify

unittests/Analysis/UnrollAnalyzer.cpp

bool runOnFunction(Function &F) override {
     BasicBlock *Header = &*FI++;
     Loop *L = LI->getLoopFor(Header);
     BasicBlock *Exiting = L->getExitingBlock();
 
     SimplifiedValuesVector.clear();
     TripCount = SE->getSmallConstantTripCount(L, Exiting);
     for (unsigned Iteration = 0; Iteration < TripCount; Iteration++) {
       DenseMap<Value *, Constant *> SimplifiedValues;
-      UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, *SE);
+      UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, *SE, L);
       for (auto *BB : L->getBlocks())
         for (Instruction &I : *BB)
           Analyzer.visit(I);
       SimplifiedValuesVector.push_back(SimplifiedValues);
     }
     return false;
   }
   void getAnalysisUsage(AnalysisUsage &AU) const override {
TEST(UnrollAnalyzerTest, BasicSimplifications) {
   EXPECT_TRUE(I1 != SimplifiedValuesVector[TripCount - 1].end());
   EXPECT_EQ(dyn_cast<ConstantInt>((*I1).second)->getZExtValue(), TripCount);
 
   // Check that "%cond = icmp sge i64 %inc, 10" is simplified to false
   I2 = SimplifiedValuesVector[TripCount - 1].find(Y2);
   EXPECT_TRUE(I2 != SimplifiedValuesVector[TripCount - 1].end());
   EXPECT_TRUE(dyn_cast<ConstantInt>((*I2).second)->getZExtValue());
 }
+
+TEST(UnrollAnalyzerTest, OuterLoopSimplification) {
+  const char *ModuleStr =
+      "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\" "
+      "define void @foo() {"
+      "entry:"
+      "  br label %outer.loop"
+      "outer.loop:"
+      "  %iv.outer = phi i64 [ 0, %entry ], [ %iv.outer.next, %outer.loop.latch ]"
+      "  br label %inner.loop"
+      "inner.loop:"
+      "  %iv.inner = phi i64 [ 0, %outer.loop ], [ %iv.inner.next, %inner.loop ]"
+      "  %iv.inner.next = add nuw nsw i64 %iv.inner, 1"
+      "  %exitcond.inner = icmp eq i64 %iv.inner.next, 1000"
+      "  br i1 %exitcond.inner, label %outer.loop.latch, label %inner.loop"
+      "outer.loop.latch:"
+      "  %iv.outer.next = add nuw nsw i64 %iv.outer, 1"
+      "  %exitcond.outer = icmp eq i64 %iv.outer.next, 40"
+      "  br i1 %exitcond.outer, label %exit, label %outer.loop"
+      "exit:"
+      "  ret void"
+      "}";
+
+  UnrollAnalyzerTest *P = new UnrollAnalyzerTest();
+  std::unique_ptr<Module> M = makeLLVMModule(P, ModuleStr);
+  legacy::PassManager Passes;
+  Passes.add(P);
+  Passes.run(*M);
+
+  Module::iterator MI = M->begin();
+  Function *F = &*MI++;
+  Function::iterator FI = F->begin();
+  FI++;
+  BasicBlock *Header = &*FI++;
+  BasicBlock *InnerBody = &*FI++;
+
+  BasicBlock::iterator BBI = Header->begin();
+  Instruction *Y1 = &*BBI++;
+  BBI = InnerBody->begin();
+  Instruction *Y2 = &*BBI++;
+  // Check that we can simplify IV of the outer loop, but can't simplify the IV
+  // of the inner loop if we only know the iteration number of the outer loop.
+  auto I1 = SimplifiedValuesVector[0].find(Y1);
+  EXPECT_TRUE(I1 != SimplifiedValuesVector[0].end());
+  auto I2 = SimplifiedValuesVector[0].find(Y2);
+  EXPECT_TRUE(I2 == SimplifiedValuesVector[0].end());
+}
 } // end namespace llvm
 
 INITIALIZE_PASS_BEGIN(UnrollAnalyzerTest, "unrollanalyzertestpass",
                       "unrollanalyzertestpass", false, false)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 INITIALIZE_PASS_END(UnrollAnalyzerTest, "unrollanalyzertestpass",
                     "unrollanalyzertestpass", false, false)