[LLE] Use the PredicatedScalarEvolution interface to query SCEVs for dependences

[sbaranga]

Summary

LAA uses the PredicatedScalarEvolution interface, so it can produce
forward/backward dependences having SCEVs that are AddRecExprs only after being
transformed by PredicatedScalarEvolution.

Use PredicatedScalarEvolution to get the expected expressions.

[anemet]

LGTM.

[sbaranga]

Thanks! Committed in r255241

-Silviu

lib/Transforms/Scalar/LoopLoadElimination.cpp

struct StoreToLoadForwardingCandidate {
   LoadInst *Load;
   StoreInst *Store;
 
   StoreToLoadForwardingCandidate(LoadInst *Load, StoreInst *Store)
       : Load(Load), Store(Store) {}
 
   /// \brief Return true if the dependence from the store to the load has a
   /// distance of one.  E.g. A[i+1] = A[i]
-  bool isDependenceDistanceOfOne(ScalarEvolution *SE) const {
+  bool isDependenceDistanceOfOne(PredicatedScalarEvolution &PSE) const {
     Value *LoadPtr = Load->getPointerOperand();
     Value *StorePtr = Store->getPointerOperand();
     Type *LoadPtrType = LoadPtr->getType();
     Type *LoadType = LoadPtrType->getPointerElementType();
 
     assert(LoadPtrType->getPointerAddressSpace() ==
                StorePtr->getType()->getPointerAddressSpace() &&
            LoadType == StorePtr->getType()->getPointerElementType() &&
            "Should be a known dependence");
 
     auto &DL = Load->getParent()->getModule()->getDataLayout();
     unsigned TypeByteSize = DL.getTypeAllocSize(const_cast<Type *>(LoadType));
 
-    auto *LoadPtrSCEV = cast<SCEVAddRecExpr>(SE->getSCEV(LoadPtr));
-    auto *StorePtrSCEV = cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr));
+    auto *LoadPtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(LoadPtr));
+    auto *StorePtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(StorePtr));
 
     // We don't need to check non-wrapping here because forward/backward
     // dependence wouldn't be valid if these weren't monotonic accesses.
-    auto *Dist =
-        cast<SCEVConstant>(SE->getMinusSCEV(StorePtrSCEV, LoadPtrSCEV));
+    auto *Dist = cast<SCEVConstant>(
+        PSE.getSE()->getMinusSCEV(StorePtrSCEV, LoadPtrSCEV));
     const APInt &Val = Dist->getValue()->getValue();
     return Val.abs() == TypeByteSize;
   }
 
   Value *getLoadPtr() const { return Load->getPointerOperand(); }
 
 #ifndef NDEBUG
   friend raw_ostream &operator<<(raw_ostream &OS,
return std::all_of(Latches.begin(), Latches.end(),
                        return DT->dominates(StoreBlock, Latch);
                      });
 }
 
 /// \brief The per-loop class that does most of the work.
 class LoadEliminationForLoop {
 public:
   LoadEliminationForLoop(Loop *L, LoopInfo *LI, const LoopAccessInfo &LAI,
-                         DominatorTree *DT, ScalarEvolution *SE)
-      : L(L), LI(LI), LAI(LAI), DT(DT), SE(SE) {}
+                         DominatorTree *DT)
+      : L(L), LI(LI), LAI(LAI), DT(DT), PSE(LAI.PSE) {}
 
   /// \brief Look through the loop-carried and loop-independent dependences in
   /// this loop and find store->load dependences.
   ///
   /// Note that no candidate is returned if LAA has failed to analyze the loop
   /// (e.g. if it's not bottom-tested, contains volatile memops, etc.)
   std::forward_list<StoreToLoadForwardingCandidate>
   findStoreToLoadDependences(const LoopAccessInfo &LAI) {
for (const auto &Cand : Candidates) {
         // Already multiple stores forward to this load.
         if (OtherCand == nullptr)
           continue;
 
         // Handle the very basic of case when the two stores are in the same
         // block so deciding which one forwards is easy.  The later one forwards
         // as long as they both have a dependence distance of one to the load.
         if (Cand.Store->getParent() == OtherCand->Store->getParent() &&
-            Cand.isDependenceDistanceOfOne(SE) &&
-            OtherCand->isDependenceDistanceOfOne(SE)) {
+            Cand.isDependenceDistanceOfOne(PSE) &&
+            OtherCand->isDependenceDistanceOfOne(PSE)) {
           // They are in the same block, the later one will forward to the load.
           if (getInstrIndex(OtherCand->Store) < getInstrIndex(Cand.Store))
             OtherCand = &Cand;
         } else
           OtherCand = nullptr;
       }
     }
 
propagateStoredValueToLoadUsers(const StoreToLoadForwardingCandidate &Cand,
     //      %x.initial = load %gep_0
     // loop:
     //      %x.storeforward = phi [%x.initial, %ph] [%y, %loop]
     //      %x = load %gep_i            <---- now dead
     //         = ... %x.storeforward
     //      store %y, %gep_i_plus_1
 
     Value *Ptr = Cand.Load->getPointerOperand();
-    auto *PtrSCEV = cast<SCEVAddRecExpr>(SE->getSCEV(Ptr));
+    auto *PtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(Ptr));
     auto *PH = L->getLoopPreheader();
     Value *InitialPtr = SEE.expandCodeFor(PtrSCEV->getStart(), Ptr->getType(),
                                           PH->getTerminator());
     Value *Initial =
         new LoadInst(InitialPtr, "load_initial", PH->getTerminator());
     PHINode *PHI = PHINode::Create(Initial->getType(), 2, "store_forwarded",
                                    &L->getHeader()->front());
     PHI->addIncoming(Initial, PH);
for (const StoreToLoadForwardingCandidate Cand : StoreToLoadDependences) {
       DEBUG(dbgs() << "Candidate " << Cand);
       // Make sure that the stored values is available everywhere in the loop in
       // the next iteration.
       if (!doesStoreDominatesAllLatches(Cand.Store->getParent(), L, DT))
         continue;
 
       // Check whether the SCEV difference is the same as the induction step,
       // thus we load the value in the next iteration.
-      if (!Cand.isDependenceDistanceOfOne(SE))
+      if (!Cand.isDependenceDistanceOfOne(PSE))
         continue;
 
       ++NumForwarding;
       DEBUG(dbgs()
             << NumForwarding
             << ". Valid store-to-load forwarding across the loop backedge\n");
       Candidates.push_back(Cand);
     }
if (LAI.PSE.getUnionPredicate().getComplexity() >
         LoadElimSCEVCheckThreshold) {
       DEBUG(dbgs() << "Too many SCEV run-time checks needed.\n");
       return false;
     }
 
     // Point of no-return, start the transformation.  First, version the loop if
     // necessary.
     if (!Checks.empty() || !LAI.PSE.getUnionPredicate().isAlwaysTrue()) {
-      LoopVersioning LV(LAI, L, LI, DT, SE, false);
+      LoopVersioning LV(LAI, L, LI, DT, PSE.getSE(), false);
       LV.setAliasChecks(std::move(Checks));
       LV.setSCEVChecks(LAI.PSE.getUnionPredicate());
       LV.versionLoop();
     }
 
     // Next, propagate the value stored by the store to the users of the load.
     // Also for the first iteration, generate the initial value of the load.
-    SCEVExpander SEE(*SE, L->getHeader()->getModule()->getDataLayout(),
+    SCEVExpander SEE(*PSE.getSE(), L->getHeader()->getModule()->getDataLayout(),
                      "storeforward");
     for (const auto &Cand : Candidates)
       propagateStoredValueToLoadUsers(Cand, SEE);
     NumLoopLoadEliminted += NumForwarding;
 
     return true;
   }
 
 private:
   Loop *L;
 
   /// \brief Maps the load/store instructions to their index according to
   /// program order.
   DenseMap<Instruction *, unsigned> InstOrder;
 
   // Analyses used.
   LoopInfo *LI;
   const LoopAccessInfo &LAI;
   DominatorTree *DT;
-  ScalarEvolution *SE;
+  PredicatedScalarEvolution PSE;
 };
 
 /// \brief The pass.  Most of the work is delegated to the per-loop
 /// LoadEliminationForLoop class.
 class LoopLoadElimination : public FunctionPass {
 public:
   LoopLoadElimination() : FunctionPass(ID) {
     initializeLoopLoadEliminationPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnFunction(Function &F) override {
     auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     auto *LAA = &getAnalysis<LoopAccessAnalysis>();
     auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-    auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 
     // Build up a worklist of inner-loops to vectorize. This is necessary as the
     // act of distributing a loop creates new loops and can invalidate iterators
     // across the loops.
     SmallVector<Loop *, 8> Worklist;
 
     for (Loop *TopLevelLoop : *LI)
       for (Loop *L : depth_first(TopLevelLoop))
         // We only handle inner-most loops.
         if (L->empty())
           Worklist.push_back(L);
 
     // Now walk the identified inner loops.
     bool Changed = false;
     for (Loop *L : Worklist) {
       const LoopAccessInfo &LAI = LAA->getInfo(L, ValueToValueMap());
       // The actual work is performed by LoadEliminationForLoop.
-      LoadEliminationForLoop LEL(L, LI, LAI, DT, SE);
+      LoadEliminationForLoop LEL(L, LI, LAI, DT);
       Changed |= LEL.processLoop();
     }
 
     // Process each loop nest in the function.
     return Changed;
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {