Allow invariant loads in the SCoP description

  This patch allows invariant loads to be used in the SCoP description,
  e.g., as loop bounds, conditions or in memory access functions.

  First we collect "required invariant loads" during SCoP detection that
  would otherwise make an expression we care about non-affine. To this
  end a new level of abstraction was introduced before
  SCEVValidator::isAffineExpr() namely ScopDetection::isAffine() and
  ScopDetection::onlyValidRequiredInvariantLoads(). Here we can decide
  if we want a load inside the region to be optimistically assumed
  invariant or not. If we do, it will be marked as required and in the
  SCoP generation we bail if it is actually not invariant. If we don't
  it will be a non-affine expression as before. At the moment we
  optimistically assume all "hoistable" (namely non-loop-carried) loads
  to be invariant. This causes us to expand some SCoPs and dismiss them
  later but it also allows us to detect a lot we would dismiss directly
  if we would ask e.g., AliasAnalysis::canBasicBlockModify(). We also
  allow potential aliases between optimistically assumed invariant loads
  and other pointers as our runtime alias checks are sound in case the
  loads are actually invariant. Together with the invariant checks this
  combination allows to handle a lot more than LICM can.

  The code generation of the invariant loads had to be extended as we
  can now have dependences between parameters and invariant (hoisted)
  loads as well as the other way around, e.g.,
    test/Isl/CodeGen/invariant_load_parameters_cyclic_dependence.ll
  First, it is important to note that we cannot have real cycles but
  only dependences from a hoisted load to a parameter and from another
  parameter to that hoisted load (and so on). To handle such cases we
  materialize llvm::Values for parameters that are referred by a hoisted
  load on demand and then materialize the remaining parameters. Second,
  there are new kinds of dependences between hoisted loads caused by the
  constraints on their execution. If a hoisted load is conditionally
  executed it might depend on the value of another hoisted load. To deal
  with such situations we sort them already in the ScopInfo such that
  they can be generated in the order they are listed in the
  Scop::InvariantAccesses list (see compareInvariantAccesses). The
  dependences between hoisted loads caused by indirect accesses are
  handled the same way as before.

llvm-svn: 249607

1 files changed, 16 insertions, 7 deletions

diff --git a/polly/lib/Support/ScopHelper.cpp b/polly/lib/Support/ScopHelper.cpp
index cc41d4812f7..d2123bd69eb 100644
--- a/polly/lib/Support/ScopHelper.cpp
+++ b/polly/lib/Support/ScopHelper.cpp
@@ -14,7 +14,6 @@
 #include "polly/Support/ScopHelper.h"
 #include "polly/Options.h"
 #include "polly/ScopInfo.h"
-#include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/ScalarEvolution.h"
@@ -240,8 +239,6 @@ void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
 struct ScopExpander : SCEVVisitor<ScopExpander, const SCEV *> {
   friend struct SCEVVisitor<ScopExpander, const SCEV *>;
 
-  typedef llvm::DenseMap<const llvm::Value *, llvm::Value *> ValueMapT;
-
   explicit ScopExpander(const Region &R, ScalarEvolution &SE,
                         const DataLayout &DL, const char *Name, ValueMapT *VMap)
       : Expander(SCEVExpander(SE, DL, Name)), SE(SE), Name(Name), R(R),
@@ -342,10 +339,9 @@ private:
   ///}
 };
 
-Value *
-polly::expandCodeFor(Scop &S, ScalarEvolution &SE, const DataLayout &DL,
-                     const char *Name, const SCEV *E, Type *Ty, Instruction *IP,
-                     llvm::DenseMap<const llvm::Value *, llvm::Value *> *VMap) {
+Value *polly::expandCodeFor(Scop &S, ScalarEvolution &SE, const DataLayout &DL,
+                            const char *Name, const SCEV *E, Type *Ty,
+                            Instruction *IP, ValueMapT *VMap) {
   ScopExpander Expander(S.getRegion(), SE, DL, Name, VMap);
   return Expander.expandCodeFor(E, Ty, IP);
 }
@@ -383,3 +379,16 @@ Value *polly::getConditionFromTerminator(TerminatorInst *TI) {
 
   return nullptr;
 }
+
+bool polly::isHoistableLoad(LoadInst *LInst, Region &R, LoopInfo &LI,
+                            ScalarEvolution &SE) {
+  Loop *L = LI.getLoopFor(LInst->getParent());
+  const SCEV *PtrSCEV = SE.getSCEVAtScope(LInst->getPointerOperand(), L);
+  while (L && R.contains(L)) {
+    if (!SE.isLoopInvariant(PtrSCEV, L))
+      return false;
+    L = L->getParentLoop();
+  }
+
+  return true;
+}