[SCEV][LAA] Add tests for SCEV expression transformations performed during LAA

[sbaranga]

Summary

Add a print method to Predicated Scalar Evolution which prints all interesting
transformations done by PSE.

Loop Access Analysis will now print this as part of the analysis output.
We now use this to check the exact expression transformations that were done
by PSE in LAA.

The additional checking also acts as white-box testing for the getAsAddRec method.

[sanjoy]

lgtm with minor stylistic comments

lib/Analysis/ScalarEvolution.cpp

10227

Can you use a range for here?

10230

Same here: why not use a range for loop here?

[sbaranga]

Change both loops to be range-based.

include/llvm/Analysis/ScalarEvolution.h

public:
     void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags);
     /// \brief Returns true if we've proved that V doesn't wrap by means of a
     /// SCEV predicate.
     bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags);
     /// \brief Returns the ScalarEvolution analysis used.
     ScalarEvolution *getSE() const { return &SE; }
     /// We need to explicitly define the copy constructor because of FlagsMap.
     PredicatedScalarEvolution(const PredicatedScalarEvolution&);
+    /// Print the SCEV mappings done by the Predicated Scalar Evolution.
+    /// The printed text is indented by \p Depth.
+    void print(raw_ostream &OS, unsigned Depth) const;
   private:
     /// \brief Increments the version number of the predicate.
     /// This needs to be called every time the SCEV predicate changes.
     void updateGeneration();
     /// Holds a SCEV and the version number of the SCEV predicate used to
     /// perform the rewrite of the expression.
     typedef std::pair<unsigned, const SCEV *> RewriteEntry;
     /// Maps a SCEV to the rewrite result of that SCEV at a certain version

lib/Analysis/LoopAccessAnalysis.cpp

void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
   OS << "\n";
 
   OS.indent(Depth) << "Store to invariant address was "
                    << (StoreToLoopInvariantAddress ? "" : "not ")
                    << "found in loop.\n";
 
   OS.indent(Depth) << "SCEV assumptions:\n";
   PSE.getUnionPredicate().print(OS, Depth);
+
+  OS << "\n";
+
+  OS.indent(Depth) << "Expressions re-written:\n";
+  PSE.print(OS, Depth);
 }
 
 const LoopAccessInfo &
 LoopAccessAnalysis::getInfo(Loop *L, const ValueToValueMap &Strides) {
   auto &LAI = LoopAccessInfoMap[L];
 
 #ifndef NDEBUG
   assert((!LAI || LAI->NumSymbolicStrides == Strides.size()) &&

lib/Analysis/ScalarEvolution.cpp

 
 PredicatedScalarEvolution::
 PredicatedScalarEvolution(const PredicatedScalarEvolution &Init) :
   RewriteMap(Init.RewriteMap), SE(Init.SE), L(Init.L), Preds(Init.Preds),
   Generation(Init.Generation) {
   for (auto I = Init.FlagsMap.begin(), E = Init.FlagsMap.end(); I != E; ++I)
     FlagsMap.insert(*I);
 }
+
+void PredicatedScalarEvolution::print(raw_ostream &OS, unsigned Depth) const {
+  // For each block.
+  for (Loop::block_iterator bb = L.block_begin(),
+       be = L.block_end(); bb != be; ++bb)
+
+    for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end();
+         it != e; ++it) {
+      Instruction *I = &*it;
+      if (!SE.isSCEVable(I->getType()))
+        continue;
+
+      auto *Expr = SE.getSCEV(I);
+      auto II = RewriteMap.find(Expr);
+
+      if (II == RewriteMap.end())
+        continue;
+
+      // Don't print things that are not interesting.
+      if (II->second.second == Expr)
+        continue;
+
+      OS.indent(Depth) << "[PSE]" << *I << ":\n";
+      OS.indent(Depth + 2) << *Expr << "\n";
+      OS.indent(Depth + 2) << "--> " << *II->second.second << "\n";
+    }
+}

test/Analysis/LoopAccessAnalysis/wrapping-pointer-versioning.ll

 ; LAA-NEXT: {0,+,2}<%for.body> Added Flags: <nusw>
 ; LAA-NEXT: {%a,+,4}<%for.body> Added Flags: <nusw>
 
 ; The expression for %mul_ext as analyzed by SCEV is
 ;    (zext i32 {0,+,2}<%for.body> to i64)
 ; We have added the nusw flag to turn this expression into the SCEV expression:
 ;    i64 {0,+,2}<%for.body>
 
+; LAA: [PSE]  %arrayidxA = getelementptr i16, i16* %a, i64 %mul_ext:
+; LAA-NEXT: ((2 * (zext i32 {0,+,2}<%for.body> to i64)) + %a)
+; LAA-NEXT: --> {%a,+,4}<%for.body>
+
+
 ; LV-LABEL: f1
 ; LV-LABEL: for.body.lver.check
 ; LV: [[PredCheck0:%[^ ]*]] = icmp ne i128
 ; LV: [[Or0:%[^ ]*]] = or i1 false, [[PredCheck0]]
 ; LV: [[PredCheck1:%[^ ]*]] = icmp ne i128
 ; LV: [[FinalCheck:%[^ ]*]] = or i1 [[Or0]], [[PredCheck1]]
 ; LV: br i1 [[FinalCheck]], label %for.body.ph.lver.orig, label %for.body.ph
 define void @f1(i16* noalias %a,

 ; LAA-NEXT: {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> Added Flags: <nusw>
 ; LAA-NEXT: {((2 * (zext i32 (2 * (trunc i64 %N to i32)) to i64)) + %a),+,-4}<%for.body> Added Flags: <nusw>
 
 ; The expression for %mul_ext as analyzed by SCEV is
 ;     (zext i32 {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> to i64)
 ; We have added the nusw flag to turn this expression into the following SCEV:
 ;     i64 {zext i32 (2 * (trunc i64 %N to i32)) to i64,+,-2}<%for.body>
 
+; LAA: [PSE]  %arrayidxA = getelementptr i16, i16* %a, i64 %mul_ext:
+; LAA-NEXT: ((2 * (zext i32 {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> to i64)) + %a)
+; LAA-NEXT: --> {((2 * (zext i32 (2 * (trunc i64 %N to i32)) to i64)) + %a),+,-4}<%for.body>
+
 ; LV-LABEL: f2
 ; LV-LABEL: for.body.lver.check
 ; LV: [[PredCheck0:%[^ ]*]] = icmp ne i128
 ; LV: [[Or0:%[^ ]*]] = or i1 false, [[PredCheck0]]
 ; LV: [[PredCheck1:%[^ ]*]] = icmp ne i128
 ; LV: [[FinalCheck:%[^ ]*]] = or i1 [[Or0]], [[PredCheck1]]
 ; LV: br i1 [[FinalCheck]], label %for.body.ph.lver.orig, label %for.body.ph
 define void @f2(i16* noalias %a,

 ; LAA-NEXT: {0,+,2}<%for.body> Added Flags: <nssw>
 ; LAA-NEXT: {%a,+,4}<%for.body> Added Flags: <nusw>
 
 ; The expression for %mul_ext as analyzed by SCEV is
 ;     i64 (sext i32 {0,+,2}<%for.body> to i64)
 ; We have added the nssw flag to turn this expression into the following SCEV:
 ;     i64 {0,+,2}<%for.body>
 
+; LAA: [PSE]  %arrayidxA = getelementptr i16, i16* %a, i64 %mul_ext:
+; LAA-NEXT: ((2 * (sext i32 {0,+,2}<%for.body> to i64)) + %a)
+; LAA-NEXT: --> {%a,+,4}<%for.body>
+
 ; LV-LABEL: f3
 ; LV-LABEL: for.body.lver.check
 ; LV: [[PredCheck0:%[^ ]*]] = icmp ne i128
 ; LV: [[Or0:%[^ ]*]] = or i1 false, [[PredCheck0]]
 ; LV: [[PredCheck1:%[^ ]*]] = icmp ne i128
 ; LV: [[FinalCheck:%[^ ]*]] = or i1 [[Or0]], [[PredCheck1]]
 ; LV: br i1 [[FinalCheck]], label %for.body.ph.lver.orig, label %for.body.ph
 define void @f3(i16* noalias %a,

 ; LAA-NEXT: {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> Added Flags: <nssw>
 ; LAA-NEXT: {((2 * (sext i32 (2 * (trunc i64 %N to i32)) to i64)) + %a),+,-4}<%for.body> Added Flags: <nusw>
 
 ; The expression for %mul_ext as analyzed by SCEV is
 ;     i64  (sext i32 {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> to i64)
 ; We have added the nssw flag to turn this expression into the following SCEV:
 ;     i64 {sext i32 (2 * (trunc i64 %N to i32)) to i64,+,-2}<%for.body>
 
+; LAA: [PSE]  %arrayidxA = getelementptr i16, i16* %a, i64 %mul_ext:
+; LAA-NEXT: ((2 * (sext i32 {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> to i64)) + %a)
+; LAA-NEXT: --> {((2 * (sext i32 (2 * (trunc i64 %N to i32)) to i64)) + %a),+,-4}<%for.body>
+
 ; LV-LABEL: f4
 ; LV-LABEL: for.body.lver.check
 ; LV: [[PredCheck0:%[^ ]*]] = icmp ne i128
 ; LV: [[Or0:%[^ ]*]] = or i1 false, [[PredCheck0]]
 ; LV: [[PredCheck1:%[^ ]*]] = icmp ne i128
 ; LV: [[FinalCheck:%[^ ]*]] = or i1 [[Or0]], [[PredCheck1]]
 ; LV: br i1 [[FinalCheck]], label %for.body.ph.lver.orig, label %for.body.ph
 define void @f4(i16* noalias %a,

 ; We can still analyze this by adding the required no wrap SCEV predicates.
 
 ; LAA-LABEL: f5
 ; LAA: Memory dependences are safe{{$}}
 ; LAA: SCEV assumptions:
 ; LAA-NEXT: {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> Added Flags: <nssw>
 ; LAA-NEXT: {((2 * (sext i32 (2 * (trunc i64 %N to i32)) to i64)) + %a),+,-4}<%for.body> Added Flags: <nusw>
 
+; LAA: [PSE]  %arrayidxA = getelementptr inbounds i16, i16* %a, i32 %mul:
+; LAA-NEXT: ((2 * (sext i32 {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> to i64))<nsw> + %a)<nsw>
+; LAA-NEXT: --> {((2 * (sext i32 (2 * (trunc i64 %N to i32)) to i64)) + %a),+,-4}<%for.body>
+
 ; LV-LABEL: f5
 ; LV-LABEL: for.body.lver.check
 define void @f5(i16* noalias %a,
                 i16* noalias %b, i64 %N) {
 entry:
   %TruncN = trunc i64 %N to i32
   br label %for.body