[Polly] Consolidate invariant loads

[jdoerfert]

Summary

                                                                                                                                               
If a (assumed) invariant location is loaded multiple times we
generated a parameter for each location. However, this caused compile
time problems for several benchmarks (e.g., 445_gobmk in SPEC2006 and
BT in the NAS benchmarks). Additionally, the code we generate is
suboptimal as we preload the same location multiple times and perform
the same checks on all the parameters that refere to the same value.

With this patch we consolidate the invariant loads in three steps:
  1) During SCoP initialization required invariant loads are put in
     equivalence classes based on their pointer operand. One
     representing load is used to generate a parameter for the whole
     class, thus we never generate multiple parameters for the same
     location.
  2) During the SCoP simplification we remove invariant memory
     accesses that are in the same equivalence class. While doing so
     we build the union of all execution domains as it is only
     important that the location is at least accessed once.
  3) During code generation we only preload one element of each
     equivalence class with the unified execution domain. All others
     are mapped to that preloaded value.
     equivalence classes based on their pointer operand. One
     representing load is used to generate a parameter for the whole
     class, thus we never generate multiple parameters for the same
     location.

[jdoerfert]

Diff against D13195 to highlight the changes

[Meinersbur]

Could you please describe what the code is doing not only in the commit message, but also as source code comment?

Why is ScopDetection involved at all? Shouldn't it be ScopInfo alone which decides what that Scop's parameters are?

[jdoerfert]

In D13338#257504, @Meinersbur wrote:

Could you please describe what the code is doing not only in the commit message, but also as source code comment?

I think the source is well documented. If you disagree please inline a comment so I know what part you refer too.

Why is ScopDetection involved at all?

Because in ScopInfo we cannot build the equivalence classes until the SCoP is completed and to build the SCoP in resonable time we need equivalence classes.
For example in the SCEVAffinator (that is used throughout the SCoP creation) we need to normalize required invariant load parameters otherwise we would introduce different parameters for each invariant load.
To normalize these parameters we already need equivalence classes but in the expression that is translated at that point there might only be a reference to one of the invariant loads (most certainly not to all that are equivalent).
Thus, to determine the representing element for an equivalence class we need to know all elements of it before we use the SCEVAffinator for the first time.
The only way to build the equivalence classses before we use the SCEVAffinator is to do it in the ScopDetection where we actually see all required invariant loads.

Shouldn't it be ScopInfo alone which decides what that Scop's parameters are?

ScopInfo actually never "really" decides what the parameters are, it only normalizes them to a certain degree (and now even more). The parameters are collected and given to the SCoP by the SCEVAffinator and the SCEVValidator.

[Meinersbur]

In D13338#257549, @jdoerfert wrote:

In D13338#257504, @Meinersbur wrote:

Could you please describe what the code is doing not only in the commit message, but also as source code comment?

I think the source is well documented. If you disagree please inline a comment so I know what part you refer too.

The commit message describes 3 phases, but there are just 1.5 notable new comments. What about the other phases?

I added some inline comments where I think you could write a bit more. (These are not questions you need to answer to me, I got them from either some other comment or the commit log).

Mmh, I mixed them with my other remarks that I found.

Why is ScopDetection involved at all?

Because in ScopInfo we cannot build the equivalence classes until the SCoP is completed and to build the SCoP in resonable time we need equivalence classes.
For example in the SCEVAffinator (that is used throughout the SCoP creation) we need to normalize required invariant load parameters otherwise we would introduce different parameters for each invariant load.
To normalize these parameters we already need equivalence classes but in the expression that is translated at that point there might only be a reference to one of the invariant loads (most certainly not to all that are equivalent).
Thus, to determine the representing element for an equivalence class we need to know all elements of it before we use the SCEVAffinator for the first time.
The only way to build the equivalence classses before we use the SCEVAffinator is to do it in the ScopDetection where we actually see all required invariant loads.

Correct me if I am wrong, SCEVAffinator is only used by the ScopInfo pass. ScopInfo also get the list of invariant using getRequiredInvariantLoads(). It can by itself create the equivalence classes by going through the map.

This might be additional work because ScopDetection in the patch does the equivalence classes already on the fly. However, it would be better for layering as ScopDetection shouldn't care about hoisting; it just determines the size of scop regions.

Shouldn't it be ScopInfo alone which decides what that Scop's parameters are?

ScopInfo actually never "really" decides what the parameters are, it only normalizes them to a certain degree (and now even more). The parameters are collected and given to the SCoP by the SCEVAffinator and the SCEVValidator.

Isn't it ScopInfo::addParams() which collect the parameters?

include/polly/ScopDetection.h

148–152

What are they remembered for?

186–190

What are the equivalence classes? Why are there equivalence classes?

253–266

What is the condition for that?

401–406

Why are they required?

include/polly/ScopInfo.h

936

Why the rename?

1219

If those are two actions, why not put them into different functions?
I can't find the changes for simplifySCoP().

1241

I prefer the longer name from ScopDetection

include/polly/Support/SCEVAffinator.h

57

What is it used for?

include/polly/Support/SCEVValidator.h

49–51

@param missing

include/polly/Support/ScopHelper.h

45–53

What is the order?

46

What is the key?

141

When is it applicable? What is the special property of the representive SCEV?

lib/Analysis/ScopDetection.cpp

301–332

Describe under which condition the invariant valid load is required

301–332

return onlyValidRequiredInvariantLoads(AccessILC, Context)

702

This is 1)?

1147–1149

Is it dummy (could you pass NULL instead)? Or does it serve as scratch storage?

lib/Analysis/ScopInfo.cpp

1368

Why the rename?

1406

Ideas how to improve this?

1419

Is this 2)? Can you describe why it is the union of the two?

1476

Why is one parameter correct but not the other?

lib/CodeGen/IslNodeBuilder.cpp

908–909

Why the rename? Doesn't "auto" know by itself that it's a const reference?

930

This is 3) ?

lib/Support/ScopHelper.cpp

372

Describe the conditions

[jdoerfert]

Updated according to Michaels idea. The SCoP will now hide most of the equivalence class magic.

[Meinersbur]

Cool! Looks less impactful now!

[grosser]

Hi Johannes,

the patch looks conceptually good and it has a very useful commit message. I do not have any code changes, but would suggest a couple of additional comments. Some of the information that I miss as source code comments can probably just been taken from your commit message.

Some minor comments:

• There is an incomplete sentence in part 3) of the commit message

Cool! Looks less impactful now!

@Michael: Thanks for reviewing! One point: in this message it seems you finished your review, but it is unclear if the patch is good to go, if you would prefer Johannes to still address some of your open comments or if you prefer me to have another look. It would help if you could state this explicitly.

Best,
Tobias

include/polly/ScopInfo.h

702

ordered

936

As Michael mentioned, the rename seems unrelated. If it is I would prefer to commit it separately before this commit to reduce the actual diff.

lib/Analysis/ScopInfo.cpp

1425

As Michael mentioned, adding the information of part 2) of your commit message as a comment here would make the code more understandable. IAs this function is getting large, it might indeed make sense to split it into two subfunctions, each with its own comment.

1472

You mention the term equivalence classes here and in one header, but do not explain which equivalence classes exist. It would be helpful to explicitly state at one of these locations what are the elements that are sorted into equivalence classes, how do they differ and which properties are used to sort them into equivalence classes.

1476

Michael commented: "Why is one parameter correct but not the other?"

This does not yet seem to be addressed and is not clear to me either,

lib/CodeGen/IslNodeBuilder.cpp

908–910

As Michael commented, this rename seems unrelated. (I like the rename, but please just commit it separately ahead of time)

@Michael: auto can derive 'const' and '*' but in some cases we still add them to make clear that something is a ptr or a const. Not sure if this information adds additional value here though.

930

As Michael mentioned, this seems to be 3) from your commit message. Adding the information from your commit message in the source code would be useful.

include/polly/CodeGen/IslNodeBuilder.h

protected:
   /// For mark nodes with an unknown name, we just forward the code generation
   /// to its child. This is currently the only behavior implemented, as there is
   /// currently not special handling for marker nodes implemented.
   ///
   /// @param Mark The node we generate code for.
   virtual void createMark(__isl_take isl_ast_node *Marker);
   virtual void createFor(__isl_take isl_ast_node *For);
 
+  /// @brief Preload the memory access at @p AccessRange with @p Build.
+  Value *preloadUnconditionally(__isl_take isl_set *AccessRange,
+                                isl_ast_build *Build);
+
   /// @brief Preload the memory load access @p MA.
   ///
   /// If @p MA is not always executed it will be conditionally loaded and
   /// merged with undef from the same type. Hence, if @p MA is executed only
   /// under condition C then the preload code will look like this:
   ///
   /// MA_preload = undef;
   /// if (C)

include/polly/ScopDetection.h

 // creating a larger non canonical region.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_SCOP_DETECTION_H
 #define POLLY_SCOP_DETECTION_H
 
 #include "polly/ScopDetectionDiagnostic.h"
+#include "polly/Support/ScopHelper.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AliasSetTracker.h"
 #include "llvm/Pass.h"
 #include <map>
 #include <memory>
 #include <set>
 
private:
   using NonAffineSubRegionSetTy = RegionSet;
   using NonAffineSubRegionMapTy =
       DenseMap<const Region *, NonAffineSubRegionSetTy>;
   NonAffineSubRegionMapTy NonAffineSubRegionMap;
 
   /// @brief Map to remeber loops in non-affine regions.
   using BoxedLoopsMapTy = DenseMap<const Region *, BoxedLoopsSetTy>;
   BoxedLoopsMapTy BoxedLoopsMap;
 
+  /// @brief Map to remember loads that are required to be invariant.
+  DenseMap<const Region *, InvariantLoadsClassesTy> RequiredInvariantLoadsMap;
+
   /// @brief Context variables for SCoP detection.
   struct DetectionContext {
     Region &CurRegion;   // The region to check.
     AliasSetTracker AST; // The AliasSetTracker to hold the alias information.
     bool Verifying;      // If we are in the verification phase?
     RejectLog Log;
 
     /// @brief Map a base pointer to all access functions accessing it.
     ///
struct DetectionContext {
     /// @brief The region has at least one loop that is not overapproximated.
     bool hasAffineLoops;
 
     /// @brief The set of non-affine subregions in the region we analyze.
     NonAffineSubRegionSetTy &NonAffineSubRegionSet;
 
     /// @brief The set of loops contained in non-affine regions.
     BoxedLoopsSetTy &BoxedLoopsSet;
 
+    /// @brief Loads that need to be invariant during execution.
+    InvariantLoadsClassesTy &RequiredILC;
+
     DetectionContext(Region &R, AliasAnalysis &AA,
                      NonAffineSubRegionSetTy &NASRS, BoxedLoopsSetTy &BLS,
-                     bool Verify)
+                     InvariantLoadsClassesTy &RequiredILC, bool Verify)
         : CurRegion(R), AST(AA), Verifying(Verify), Log(&R), hasLoads(false),
           hasStores(false), hasAffineLoops(false), NonAffineSubRegionSet(NASRS),
-          BoxedLoopsSet(BLS) {}
+          BoxedLoopsSet(BLS), RequiredILC(RequiredILC) {}
   };
 
   // Remember the valid regions
   RegionSet ValidRegions;
 
   // Remember a list of errors for every region.
   mutable RejectLogsContainer RejectLogs;
 
private:
   /// @return True if R is a Scop, false otherwise.
   bool isValidRegion(DetectionContext &Context) const;
 
   /// @brief Check if a call instruction can be part of a Scop.
   ///
   /// @param CI The call instruction to check.
   /// @return True if the call instruction is valid, false otherwise.
   static bool isValidCallInst(CallInst &CI);
 
+  /// @brief Check if the required invariant loads can be hoisted.
+  ///
+  /// If true is returned the loads are added to the required invariant loads
+  /// contained in the @p Context.
+  ///
+  /// @param RequiredILC The loads to check.
+  /// @param Context     The current detection context.
+  ///
+  /// @return True if all loads can be assumed invariant.
+  bool onlyValidRequiredInvariantLoads(InvariantLoadsClassesTy &RequiredILC,
+                                       DetectionContext &Context) const;
+
   /// @brief Check if a value is invariant in the region Reg.
   ///
   /// @param Val Value to check for invariance.
   /// @param Reg The region to consider for the invariance of Val.
   ///
   /// @return True if the value represented by Val is invariant in the region
   ///         identified by Reg.
   bool isInvariant(const Value &Val, const Region &Reg) const;
 
private:
   /// @param BI        The branch to check.
   /// @param Condition The branch condition.
   /// @param Context   The context of scop detection.
   ///
   /// @return True if the branch @p BI is valid.
   bool isValidBranch(BasicBlock &BB, BranchInst *BI, Value *Condition,
                      DetectionContext &Context) const;
 
+  /// @brief Check if the SCEV @p S is affine in the current @p Context.
+  ///
+  /// This will also use a heuristic to decide if we want to require loads to be
+  /// invariant to make the expression affine or if we want to treat is as
+  /// non-affine.
+  ///
+  /// @param S           The expression to be checked.
+  /// @param Context     The context of scop detection.
+  /// @param BaseAddress The base address of the expression @p S (if any).
+  bool isAffine(const SCEV *S, DetectionContext &Context,
+                Value *BaseAddress = nullptr) const;
+
   /// @brief Check if the control flow in a basic block is valid.
   ///
   /// @param BB The BB to check the control flow.
   /// @param Context The context of scop detection.
   ///
   /// @return True if the BB contains only valid control flow.
   bool isValidCFG(BasicBlock &BB, DetectionContext &Context) const;
 
public:
   /// @param Verify Rerun the scop detection to verify SCoP was not invalidated
   ///               meanwhile.
   ///
   /// @return Return true if R is the maximum Region in a Scop, false otherwise.
   bool isMaxRegionInScop(const Region &R, bool Verify = true) const;
 
   /// @brief Return the set of loops in non-affine subregions for @p R.
   const BoxedLoopsSetTy *getBoxedLoops(const Region *R) const;
 
+  /// @brief Return the set of required invariant loads for @p R.
+  const InvariantLoadsClassesTy *
+  getRequiredInvariantLoads(const Region *R) const;
+
   /// @brief Return true if @p SubR is a non-affine subregion in @p ScopR.
   bool isNonAffineSubRegion(const Region *SubR, const Region *ScopR) const;
 
   /// @brief Get a message why a region is invalid
   ///
   /// @param R The region for which we get the error message
   ///
   /// @return The error or "" if no error appeared.
   std::string regionIsInvalidBecause(const Region *R) const;

include/polly/ScopInfo.h

llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
                               MemoryAccess::ReductionType RT);
 
 /// @brief Ordered list type to hold accesses.
 using MemoryAccessList = std::forward_list<MemoryAccess *>;
 
 /// @brief Type for invariant memory accesses and their domain context.
 using InvariantAccessTy = std::pair<MemoryAccess *, isl_set *>;
 
+/// @brief Type for multiple equivalent invariant memory accesses.
+using InvariantAccessListTy = std::forward_list<InvariantAccessTy>;
+
 /// @brief Type for multiple invariant memory accesses and their domain context.
-using InvariantAccessesTy = SmallVector<InvariantAccessTy, 8>;
+using InvariantAccessesTy = SmallVector<InvariantAccessListTy, 8>;
 
 ///===----------------------------------------------------------------------===//
 /// @brief Statement of the Scop
 ///
 /// A Scop statement represents an instruction in the Scop.
 ///
 /// It is further described by its iteration domain, its schedule and its data
 /// accesses.
public:
 
   void setBasicBlock(BasicBlock *Block) {
     // TODO: Handle the case where the statement is a region statement, thus
     //       the entry block was split and needs to be changed in the region R.
     assert(BB && "Cannot set a block for a region statement");
     BB = Block;
   }
 
-  /// @brief Move the memory access in @p InvMAs to @p TargetList.
+  /// @brief Move the memory access in @p InvMAs to @p InvariantAccesses.
   ///
   /// Note that scalar accesses that are caused by any access in @p InvMAs will
   /// be eliminated too.
   void hoistMemoryAccesses(MemoryAccessList &InvMAs,
-                           InvariantAccessesTy &TargetList);
+                           InvariantAccessesTy &InvariantAccesses);
 
   typedef MemoryAccessVec::iterator iterator;
   typedef MemoryAccessVec::const_iterator const_iterator;
 
   iterator begin() { return MemAccs.begin(); }
   iterator end() { return MemAccs.end(); }
   const_iterator begin() const { return MemAccs.begin(); }
   const_iterator end() const { return MemAccs.end(); }

 
 private:
   Scop(const Scop &) = delete;
   const Scop &operator=(const Scop &) = delete;
 
   DominatorTree &DT;
   ScalarEvolution *SE;
 
+  /// @brief The ScopDetection to access the required invariant loads.
+  ScopDetection &SD;
+
   /// The underlying Region.
   Region &R;
 
   // Access function of bbs.
   AccFuncMapType &AccFuncMap;
 
   /// Flag to indicate that the scheduler actually optimized the SCoP.
   bool IsOptimized;
private:
   /// During code generation we will create a runtime alias check for each alias
   /// group to ensure the SCoP is executed in an alias free environment.
   MinMaxVectorPairVectorTy MinMaxAliasGroups;
 
   /// @brief List of invariant accesses.
   InvariantAccessesTy InvariantAccesses;
 
   /// @brief Scop constructor; invoked from ScopInfo::buildScop.
-  Scop(Region &R, AccFuncMapType &AccFuncMap, ScalarEvolution &SE,
-       DominatorTree &DT, isl_ctx *ctx, unsigned MaxLoopDepth);
+  Scop(Region &R, AccFuncMapType &AccFuncMap, ScopDetection &SD,
+       ScalarEvolution &SE, DominatorTree &DT, isl_ctx *ctx,
+       unsigned MaxLoopDepth);
 
   /// @brief Initialize this ScopInfo .
   void init(LoopInfo &LI, ScopDetection &SD, AliasAnalysis &AA);
 
   /// @brief Add loop carried constraints to the header block of the loop @p L.
   ///
   /// @param L  The loop to process.
   /// @param LI The LoopInfo analysis.
private:
 
   /// @brief Add parameter constraints to @p C that imply a non-empty domain.
   __isl_give isl_set *addNonEmptyDomainConstraints(__isl_take isl_set *C) const;
 
   /// @brief Simplify the SCoP representation
   ///
   /// At the moment we perform the following simplifications:
   ///   - removal of empty statements (due to invariant load hoisting)
+  ///   - consolidation of invariant loads of the same address.
   void simplifySCoP();
 
-  /// @brief Hoist all invariant memory loads.
+  /// @brief Hoist invariant memory loads and check for required ones.
   void hoistInvariantLoads();
 
   /// @brief Build the Context of the Scop.
   void buildContext();
 
   /// @brief Build the BoundaryContext based on the wrapping of expressions.
   void buildBoundaryContext();
 
   /// @brief Add user provided parameter constraints to context.
   void addUserContext();
 
   /// @brief Add the bounds of the parameters to the context.
   void addParameterBounds();
 
   /// @brief Simplify the assumed and boundary context.
   void simplifyContexts();
 
+  /// @brief Return the required invariant load equivalence classes.
+  const InvariantLoadsClassesTy &getRIL() const;
+
   /// @brief Create a new SCoP statement for either @p BB or @p R.
   ///
   /// Either @p BB or @p R should be non-null. A new statement for the non-null
   /// argument will be created and added to the statement vector and map.
   ///
   /// @param BB         The basic block we build the statement for (or null)
   /// @param R          The region we build the statement for (or null).
   ScopStmt *addScopStmt(BasicBlock *BB, Region *R);
public:
   ///
   AccFuncSetType *getAccessFunctions(const BasicBlock *BB) {
     AccFuncMapType::iterator at = AccFuncMap.find(BB);
     return at != AccFuncMap.end() ? &(at->second) : 0;
   }
   //@}
 
   ScalarEvolution *getSE() const;
+  ScopDetection &getSD() const { return SD; }
 
   /// @brief Get the count of parameters used in this Scop.
   ///
   /// @return The count of parameters used in this Scop.
   inline ParamVecType::size_type getNumParams() const {
     return Parameters.size();
   }
 
class ScopInfo : public RegionPass {
   void buildScop(Region &R, DominatorTree &DT);
 
   /// @brief Build an instance of MemoryAccess from the Load/Store instruction.
   ///
   /// @param Inst       The Load/Store instruction that access the memory
   /// @param L          The parent loop of the instruction
   /// @param R          The region on which to build the data access dictionary.
   /// @param BoxedLoops The set of loops that are overapproximated in @p R.
+  /// @param ScopRIL    The required invariant loads equivalence classes.
   void buildMemoryAccess(Instruction *Inst, Loop *L, Region *R,
-                         const ScopDetection::BoxedLoopsSetTy *BoxedLoops);
+                         const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
+                         const InvariantLoadsClassesTy &ScopRIL);
 
   /// @brief Analyze and extract the cross-BB scalar dependences (or,
   ///        dataflow dependencies) of an instruction.
   ///
   /// @param Inst               The instruction to be analyzed
   /// @param R                  The SCoP region
   /// @param NonAffineSubRegion The non affine sub-region @p Inst is in.
   ///

include/polly/Support/SCEVAffinator.h

 //===------ polly/SCEVAffinator.h - Create isl expressions from SCEVs -----===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Create a polyhedral description for a SCEV value.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_SCEV_AFFINATOR_H
 #define POLLY_SCEV_AFFINATOR_H
 
+#include "polly/Support/ScopHelper.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 
 #include "isl/ctx.h"
 
 struct isl_ctx;
 struct isl_map;
 struct isl_basic_map;

 /// Translate a SCEV to an isl_pw_aff.
 struct SCEVAffinator : public llvm::SCEVVisitor<SCEVAffinator, isl_pw_aff *> {
 public:
   SCEVAffinator(Scop *S);
   ~SCEVAffinator();
 
   /// @brief Translate a SCEV to an isl_pw_aff.
   ///
-  /// @param E  he expression that is translated.
-  /// @param BB The block in which @p E is executed.
+  /// @param E   The expression that is translated.
+  /// @param BB  The block in which @p E is executed.
+  /// @param ILC The invariant loads equivalence classes of the SCoP.
   ///
   /// @returns The isl representation of the SCEV @p E in @p Domain.
   __isl_give isl_pw_aff *getPwAff(const llvm::SCEV *E,
+                                  const InvariantLoadsClassesTy &ILC,
                                   llvm::BasicBlock *BB = nullptr);
 
   /// @brief Compute the context in which integer wrapping is happending.
   ///
   /// This context contains all parameter configurations for which we
   /// know that the wrapping and non-wrapping expressions are different.
   ///
   /// @returns The context in which integer wrapping is happening.

include/polly/Support/SCEVValidator.h

 //===--- SCEVValidator.h - Detect Scops -------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 // Checks if a SCEV expression represents a valid affine expression.
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_SCEV_VALIDATOR_H
 #define POLLY_SCEV_VALIDATOR_H
 
+#include "polly/Support/ScopHelper.h"
 #include "llvm/ADT/SetVector.h"
 #include <vector>
 
 namespace llvm {
 class Region;
 class SCEV;
 class ScalarEvolution;
 class Value;
 class Loop;
+class LoadInst;
 }
 
 namespace polly {
 /// @brief Find the loops referenced from a SCEV expression.
 ///
 /// @param Expr The SCEV expression to scan for loops.
 /// @param Loops A vector into which the found loops are inserted.
 void findLoops(const llvm::SCEV *Expr,
                llvm::SetVector<const llvm::Loop *> &Loops);
 
 /// @brief Find the values referenced by SCEVUnknowns in a given SCEV
 /// expression.
 ///
 /// @param Expr The SCEV expression to scan for SCEVUnknowns.
 /// @param Expr A vector into which the found values are inserted.
 void findValues(const llvm::SCEV *Expr, llvm::SetVector<llvm::Value *> &Values);
 
 /// Returns true when the SCEV contains references to instructions within the
 /// region.
 ///
 /// @param S The SCEV to analyze.
 /// @param R The region in which we look for dependences.
 bool hasScalarDepsInsideRegion(const llvm::SCEV *S, const llvm::Region *R);
 bool isAffineExpr(const llvm::Region *R, const llvm::SCEV *Expression,
-                  llvm::ScalarEvolution &SE,
-                  const llvm::Value *BaseAddress = 0);
+                  llvm::ScalarEvolution &SE, const llvm::Value *BaseAddress = 0,
+                  InvariantLoadsClassesTy *ILC = nullptr);
 std::vector<const llvm::SCEV *>
 getParamsInAffineExpr(const llvm::Region *R, const llvm::SCEV *Expression,
                       llvm::ScalarEvolution &SE,
+                      const InvariantLoadsClassesTy &ILC,
                       const llvm::Value *BaseAddress = 0);
 
 /// @brief Extract the constant factors from the multiplication @p M.
 ///
 /// @param M  A potential SCEV multiplication.
 /// @param SE The ScalarEvolution analysis to create new SCEVs.
 ///
 /// @returns The constant factor in @p M and the rest of @p M.
 std::pair<const llvm::SCEV *, const llvm::SCEV *>
 extractConstantFactor(const llvm::SCEV *M, llvm::ScalarEvolution &SE);
 }
 
 #endif

include/polly/Support/ScopHelper.h

 // Small functions that help with LLVM-IR.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_SUPPORT_IRHELPER_H
 #define POLLY_SUPPORT_IRHELPER_H
 
 #include "llvm/ADT/DenseMap.h"
-#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/ADT/SetVector.h"
 
 namespace llvm {
 class Type;
 class Instruction;
+class LoadInst;
 class LoopInfo;
 class Loop;
 class ScalarEvolution;
 class SCEV;
 class Value;
 class PHINode;
 class Region;
 class Pass;
 class BasicBlock;
 class StringRef;
 class DataLayout;
 class DominatorTree;
 class RegionInfo;
 class TerminatorInst;
 class ScalarEvolution;
 }
 
 namespace polly {
 class Scop;
 typedef llvm::DenseMap<const llvm::Value *, llvm::Value *> ValueMapT;
 typedef llvm::SmallVector<ValueMapT, 8> VectorValueMapT;
 
+/// @brief Type for a __ordered__ set of invariant loads.
+using InvariantLoadsSetTy = llvm::SetVector<llvm::LoadInst *>;
+
+/// @brief Type for equivalence classes of invariant loads.
+using InvariantLoadsClassesTy =
+    llvm::DenseMap<const llvm::SCEV *, InvariantLoadsSetTy>;
+
 /// Temporary Hack for extended regiontree.
 ///
 /// @brief Cast the region to loop.
 ///
 /// @param R  The Region to be casted.
 /// @param LI The LoopInfo to help the casting.
 ///
 /// @return If there is a a loop that has the same entry and exit as the region,
 ///         return the loop, otherwise, return null.

 /// @brief Return the condition for the terminator @p TI.
 ///
 /// For unconditional branches the "i1 true" condition will be returned.
 ///
 /// @param TI The terminator to get the condition from.
 ///
 /// @return The condition of @p TI and nullptr if none could be extracted.
 llvm::Value *getConditionFromTerminator(llvm::TerminatorInst *TI);
+
+/// @brief Check if @p LInst can be hoisted in @p R.
+///
+/// @param LInst The load to check.
+/// @param R     The analyzed region.
+/// @param LI    The loop info.
+/// @param SE    The scalar evolution analysis.
+///
+/// @return True if @p LInst can be hoisted in @p R.
+bool isHoistableLoad(llvm::LoadInst *LInst, llvm::Region &R, llvm::LoopInfo &LI,
+                     llvm::ScalarEvolution &SE);
+
+/// @brief Get the representing SCEV for invariant loads if applicable.
+///
+/// @param S   The SCEV to normalize.
+/// @param SE  The ScalarEvolution analysis.
+/// @param ILC The invariant loads equivalence classes.
+///
+/// @return The representing SCEV for invariant loads or @p S if none.
+const llvm::SCEV *
+normalizeInvariantLoadSCEV(const llvm::SCEV *S, llvm::ScalarEvolution &SE,
+                           const InvariantLoadsClassesTy &ILC);
 }
 #endif

lib/Analysis/ScopDetection.cpp

 
 #include "polly/CodeGen/BlockGenerators.h"
 #include "polly/CodeGen/CodeGeneration.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/Options.h"
 #include "polly/ScopDetection.h"
 #include "polly/ScopDetectionDiagnostic.h"
 #include "polly/Support/SCEVValidator.h"
-#include "polly/Support/ScopHelper.h"
 #include "polly/Support/ScopLocation.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/RegionIterator.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"

 
 bool ScopDetection::isMaxRegionInScop(const Region &R, bool Verify) const {
   if (!ValidRegions.count(&R))
     return false;
 
   if (Verify) {
     BoxedLoopsSetTy DummyBoxedLoopsSet;
     NonAffineSubRegionSetTy DummyNonAffineSubRegionSet;
+    InvariantLoadsClassesTy DummyILC;
     DetectionContext Context(const_cast<Region &>(R), *AA,
                              DummyNonAffineSubRegionSet, DummyBoxedLoopsSet,
-                             false /*verifying*/);
+                             DummyILC, false /*verifying*/);
     return isValidRegion(Context);
   }
 
   return true;
 }
 
 std::string ScopDetection::regionIsInvalidBecause(const Region *R) const {
   if (!RejectLogs.count(R))
bool ScopDetection::addOverApproximatedRegion(Region *AR,
   for (BasicBlock *BB : AR->blocks()) {
     Loop *L = LI->getLoopFor(BB);
     if (AR->contains(L))
       Context.BoxedLoopsSet.insert(L);
   }
 
   return (AllowNonAffineSubLoops || Context.BoxedLoopsSet.empty());
 }
 
+bool ScopDetection::onlyValidRequiredInvariantLoads(
+    InvariantLoadsClassesTy &RequiredILC, DetectionContext &Context) const {
+
+  for (const auto &RILEquivClass : RequiredILC)
+    for (LoadInst *LInst : RILEquivClass.second)
+      if (!isHoistableLoad(LInst, Context.CurRegion, *LI, *SE))
+        return false;
+
+  for (auto &EquivClass : RequiredILC) {
+    auto &ContextEquivClass = Context.RequiredILC[EquivClass.first];
+    ContextEquivClass.insert(EquivClass.second.begin(),
+                             EquivClass.second.end());
+  }
+
+  return true;
+}
+
+bool ScopDetection::isAffine(const SCEV *S, DetectionContext &Context,
+                             Value *BaseAddress) const {
+
+  InvariantLoadsClassesTy AccessILC;
+  if (!isAffineExpr(&Context.CurRegion, S, *SE, BaseAddress, &AccessILC))
+    return false;
+
+  if (!onlyValidRequiredInvariantLoads(AccessILC, Context))
+    return false;
+
+  return true;
+}
+
 bool ScopDetection::isValidSwitch(BasicBlock &BB, SwitchInst *SI,
                                   Value *Condition,
                                   DetectionContext &Context) const {
-  Region &CurRegion = Context.CurRegion;
-
   Loop *L = LI->getLoopFor(&BB);
   const SCEV *ConditionSCEV = SE->getSCEVAtScope(Condition, L);
 
-  if (!isAffineExpr(&CurRegion, ConditionSCEV, *SE))
+  if (!isAffine(ConditionSCEV, Context))
     if (!AllowNonAffineSubRegions ||
         !addOverApproximatedRegion(RI->getRegionFor(&BB), Context))
       return invalid<ReportNonAffBranch>(Context, /*Assert=*/true, &BB,
                                          ConditionSCEV, ConditionSCEV, SI);
 
   return true;
 }
 
 bool ScopDetection::isValidBranch(BasicBlock &BB, BranchInst *BI,
                                   Value *Condition,
                                   DetectionContext &Context) const {
-  Region &CurRegion = Context.CurRegion;
-
   // Non constant conditions of branches need to be ICmpInst.
   if (!isa<ICmpInst>(Condition)) {
     if (!AllowNonAffineSubRegions ||
         !addOverApproximatedRegion(RI->getRegionFor(&BB), Context))
       return invalid<ReportInvalidCond>(Context, /*Assert=*/true, BI, &BB);
   }
 
   if (ICmpInst *ICmp = dyn_cast<ICmpInst>(Condition)) {
if (ICmpInst *ICmp = dyn_cast<ICmpInst>(Condition)) {
     //              this is fixed we disallow pointer expressions completely.
     if (ICmp->getOperand(0)->getType()->isPointerTy())
       return false;
 
     Loop *L = LI->getLoopFor(ICmp->getParent());
     const SCEV *LHS = SE->getSCEVAtScope(ICmp->getOperand(0), L);
     const SCEV *RHS = SE->getSCEVAtScope(ICmp->getOperand(1), L);
 
-    if (!isAffineExpr(&CurRegion, LHS, *SE) ||
-        !isAffineExpr(&CurRegion, RHS, *SE)) {
+    if (!isAffine(LHS, Context) || !isAffine(RHS, Context)) {
       if (!AllowNonAffineSubRegions ||
           !addOverApproximatedRegion(RI->getRegionFor(&BB), Context))
         return invalid<ReportNonAffBranch>(Context, /*Assert=*/true, &BB, LHS,
                                            RHS, ICmp);
     }
   }
 
   return true;
bool ScopDetection::isInvariant(const Value &Val, const Region &Reg) const {
   // infinite recursion.
   if (isa<PHINode>(*I))
     return false;
 
   for (const Use &Operand : I->operands())
     if (!isInvariant(*Operand, Reg))
       return false;
 
-  // When the instruction is a load instruction, check that no write to memory
-  // in the region aliases with the load.
-  if (const LoadInst *LI = dyn_cast<LoadInst>(I)) {
-    auto Loc = MemoryLocation::get(LI);
-
-    // Check if any basic block in the region can modify the location pointed to
-    // by 'Loc'.  If so, 'Val' is (likely) not invariant in the region.
-    for (const BasicBlock *BB : Reg.blocks())
-      if (AA->canBasicBlockModify(*BB, Loc))
-        return false;
-  }
-
   return true;
 }
 
 MapInsnToMemAcc InsnToMemAcc;
 
 bool ScopDetection::hasAffineMemoryAccesses(DetectionContext &Context) const {
   Region &CurRegion = Context.CurRegion;
 
for (const SCEVUnknown *BasePointer : Context.NonAffineAccesses) {
     if (Shape->DelinearizedSizes.empty()) {
       if (AllowNonAffine)
         continue;
 
       for (const auto &Pair : Context.Accesses[BasePointer]) {
         const Instruction *Insn = Pair.first;
         const SCEV *AF = Pair.second;
 
-        if (!isAffineExpr(&CurRegion, AF, *SE, BaseValue)) {
+        if (!isAffine(AF, Context, BaseValue)) {
           invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, AF, Insn,
                                          BaseValue);
           if (!KeepGoing)
             return false;
         }
       }
       continue;
     }
for (const SCEVUnknown *BasePointer : Context.NonAffineAccesses) {
     for (const auto &Pair : Context.Accesses[BasePointer]) {
       const Instruction *Insn = Pair.first;
       auto *AF = Pair.second;
       bool IsNonAffine = false;
       TempMemoryAccesses.insert(std::make_pair(Insn, MemAcc(Insn, Shape)));
       MemAcc *Acc = &TempMemoryAccesses.find(Insn)->second;
 
       if (!AF) {
-        if (isAffineExpr(&CurRegion, Pair.second, *SE, BaseValue))
+        if (isAffine(Pair.second, Context, BaseValue))
           Acc->DelinearizedSubscripts.push_back(Pair.second);
         else
           IsNonAffine = true;
       } else {
         SE->computeAccessFunctions(AF, Acc->DelinearizedSubscripts,
                                    Shape->DelinearizedSizes);
         if (Acc->DelinearizedSubscripts.size() == 0)
           IsNonAffine = true;
         for (const SCEV *S : Acc->DelinearizedSubscripts)
-          if (!isAffineExpr(&CurRegion, S, *SE, BaseValue))
+          if (!isAffine(S, Context, BaseValue))
             IsNonAffine = true;
       }
 
       // (Possibly) report non affine access
       if (IsNonAffine) {
         BasePtrHasNonAffine = true;
         if (!AllowNonAffine)
           invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, Pair.second,
bool ScopDetection::isValidMemoryAccess(Instruction &Inst,
   findLoops(AccessFunction, Loops);
   for (const Loop *L : Loops)
     if (Context.BoxedLoopsSet.count(L))
       isVariantInNonAffineLoop = true;
 
   if (PollyDelinearize && !isVariantInNonAffineLoop) {
     Context.Accesses[BasePointer].push_back({&Inst, AccessFunction});
 
-    if (!isAffineExpr(&CurRegion, AccessFunction, *SE, BaseValue))
+    if (!isAffine(AccessFunction, Context, BaseValue))
       Context.NonAffineAccesses.insert(BasePointer);
   } else if (!AllowNonAffine) {
     if (isVariantInNonAffineLoop ||
-        !isAffineExpr(&CurRegion, AccessFunction, *SE, BaseValue))
+        !isAffine(AccessFunction, Context, BaseValue))
       return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true,
                                             AccessFunction, &Inst, BaseValue);
   }
 
   // FIXME: Alias Analysis thinks IntToPtrInst aliases with alloca instructions
   // created by IndependentBlocks Pass.
   if (IntToPtrInst *Inst = dyn_cast<IntToPtrInst>(BaseValue))
     return invalid<ReportIntToPtr>(Context, /*Assert=*/true, Inst);
bool ScopDetection::isValidMemoryAccess(Instruction &Inst,
   // not cause irrelevant verification failures.
   if (!AS.isMustAlias()) {
     if (PollyUseRuntimeAliasChecks) {
       bool CanBuildRunTimeCheck = true;
       // The run-time alias check places code that involves the base pointer at
       // the beginning of the SCoP. This breaks if the base pointer is defined
       // inside the scop. Hence, we can only create a run-time check if we are
       // sure the base pointer is not an instruction defined inside the scop.
+      // However, if we can ignore loads that will be hoisted.
       for (const auto &Ptr : AS) {
         Instruction *Inst = dyn_cast<Instruction>(Ptr.getValue());
         if (Inst && CurRegion.contains(Inst)) {
+          LoadInst *LInst = dyn_cast<LoadInst>(Inst);
+          if (LInst && isHoistableLoad(LInst, CurRegion, *LI, *SE)) {
+            const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());
+            Context.RequiredILC[PointerSCEV].insert(LInst);
+            continue;
+          }
+
           CanBuildRunTimeCheck = false;
           break;
         }
       }
 
       if (CanBuildRunTimeCheck)
         return true;
     }
Region *ScopDetection::expandRegion(Region &R) {
   std::unique_ptr<Region> LastValidRegion;
   auto ExpandedRegion = std::unique_ptr<Region>(R.getExpandedRegion());
 
   DEBUG(dbgs() << "\tExpanding " << R.getNameStr() << "\n");
 
   while (ExpandedRegion) {
     DetectionContext Context(
         *ExpandedRegion, *AA, NonAffineSubRegionMap[ExpandedRegion.get()],
-        BoxedLoopsMap[ExpandedRegion.get()], false /* verifying */);
+        BoxedLoopsMap[ExpandedRegion.get()],
+        RequiredInvariantLoadsMap[ExpandedRegion.get()], false /* verifying */);
     DEBUG(dbgs() << "\t\tTrying " << ExpandedRegion->getNameStr() << "\n");
     // Only expand when we did not collect errors.
 
     if (!Context.Log.hasErrors()) {
       // If the exit is valid check all blocks
       //  - if true, a valid region was found => store it + keep expanding
       //  - if false, .tbd. => stop  (should this really end the loop?)
       if (!allBlocksValid(Context) || Context.Log.hasErrors()) {

 void ScopDetection::removeCachedResults(const Region &R) {
   ValidRegions.remove(&R);
   BoxedLoopsMap.erase(&R);
   NonAffineSubRegionMap.erase(&R);
 }
 
 void ScopDetection::findScops(Region &R) {
   DetectionContext Context(R, *AA, NonAffineSubRegionMap[&R], BoxedLoopsMap[&R],
-                           false /*verifying*/);
+                           RequiredInvariantLoadsMap[&R], false /*verifying*/);
 
   bool RegionIsValid = false;
   if (!DetectUnprofitable && regionWithoutLoops(R, LI)) {
     removeCachedResults(R);
     invalid<ReportUnprofitable>(Context, /*Assert=*/true, &R);
   } else
     RegionIsValid = isValidRegion(Context);
 

 const ScopDetection::BoxedLoopsSetTy *
 ScopDetection::getBoxedLoops(const Region *R) const {
   auto BLMIt = BoxedLoopsMap.find(R);
   if (BLMIt == BoxedLoopsMap.end())
     return nullptr;
   return &BLMIt->second;
 }
 
+const InvariantLoadsClassesTy *
+ScopDetection::getRequiredInvariantLoads(const Region *R) const {
+  auto RILMIt = RequiredInvariantLoadsMap.find(R);
+  if (RILMIt == RequiredInvariantLoadsMap.end())
+    return nullptr;
+  return &RILMIt->second;
+}
+
 void polly::ScopDetection::verifyRegion(const Region &R) const {
   assert(isMaxRegionInScop(R) && "Expect R is a valid region.");
 
   BoxedLoopsSetTy DummyBoxedLoopsSet;
   NonAffineSubRegionSetTy DummyNonAffineSubRegionSet;
+  InvariantLoadsClassesTy DummyILC;
   DetectionContext Context(const_cast<Region &>(R), *AA,
                            DummyNonAffineSubRegionSet, DummyBoxedLoopsSet,
-                           true /*verifying*/);
+                           DummyILC, true /*verifying*/);
   isValidRegion(Context);
 }
 
 void polly::ScopDetection::verifyAnalysis() const {
   if (!VerifyScops)
     return;
 
   for (const Region *R : ValidRegions)

 }
 
 void ScopDetection::releaseMemory() {
   RejectLogs.clear();
   ValidRegions.clear();
   InsnToMemAcc.clear();
   BoxedLoopsMap.clear();
   NonAffineSubRegionMap.clear();
+  RequiredInvariantLoadsMap.clear();
 
   // Do not clear the invalid function set.
 }
 
 char ScopDetection::ID = 0;
 
 Pass *polly::createScopDetectionPass() { return new ScopDetection(); }
 

lib/Analysis/ScopInfo.cpp

void ScopStmt::buildDomain() {
   Domain = isl_set_set_tuple_id(Domain, Id);
 }
 
 void ScopStmt::deriveAssumptionsFromGEP(GetElementPtrInst *GEP) {
   isl_ctx *Ctx = Parent.getIslCtx();
   isl_local_space *LSpace = isl_local_space_from_space(getDomainSpace());
   Type *Ty = GEP->getPointerOperandType();
   ScalarEvolution &SE = *Parent.getSE();
+  ScopDetection &SD = Parent.getSD();
+
+  // The set of loads that are required to be invariant.
+  auto &ScopRIL = *SD.getRequiredInvariantLoads(&Parent.getRegion());
 
   std::vector<const SCEV *> Subscripts;
   std::vector<int> Sizes;
 
   std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, SE);
 
   if (auto *PtrTy = dyn_cast<PointerType>(Ty)) {
     Ty = PtrTy->getElementType();
   }
 
   int IndexOffset = Subscripts.size() - Sizes.size();
 
   assert(IndexOffset <= 1 && "Unexpected large index offset");
 
   for (size_t i = 0; i < Sizes.size(); i++) {
     auto Expr = Subscripts[i + IndexOffset];
     auto Size = Sizes[i];
 
-    if (!isAffineExpr(&Parent.getRegion(), Expr, SE))
+    InvariantLoadsClassesTy AccessRIL;
+    if (!isAffineExpr(&Parent.getRegion(), Expr, SE, nullptr, &AccessRIL))
+      continue;
+
+    bool NonAffine = false;
+    for (const auto EquivClass : AccessRIL)
+      for (LoadInst *LInst : EquivClass.second)
+        if (!ScopRIL.lookup(EquivClass.first).count(LInst))
+          NonAffine = true;
+
+    if (NonAffine)
       continue;
 
     isl_pw_aff *AccessOffset = getPwAff(Expr);
     AccessOffset =
         isl_pw_aff_set_tuple_id(AccessOffset, isl_dim_in, getDomainId());
 
     isl_pw_aff *DimSize = isl_pw_aff_from_aff(isl_aff_val_on_domain(
         isl_local_space_copy(LSpace), isl_val_int_from_si(Ctx, Size)));
void ScopStmt::print(raw_ostream &OS) const {
 
   for (MemoryAccess *Access : MemAccs)
     Access->print(OS);
 }
 
 void ScopStmt::dump() const { print(dbgs()); }
 
 void ScopStmt::hoistMemoryAccesses(MemoryAccessList &InvMAs,
-                                   InvariantAccessesTy &TargetList) {
+                                   InvariantAccessesTy &InvariantAccesses) {
 
   // Remove all memory accesses in @p InvMAs from this statement together
   // with all scalar accesses that were caused by them. The tricky iteration
   // order uses is needed because the MemAccs is a vector and the order in
   // which the accesses of each memory access list (MAL) are stored in this
   // vector is reversed.
   for (MemoryAccess *MA : InvMAs) {
     auto &MAL = *lookupAccessesFor(MA->getAccessInstruction());
void ScopStmt::hoistMemoryAccesses(MemoryAccessList &InvMAs,
 
   // Get the context under which this statement, hence the memory accesses, are
   // executed.
   isl_set *DomainCtx = isl_set_params(getDomain());
   DomainCtx = isl_set_remove_redundancies(DomainCtx);
   DomainCtx = isl_set_detect_equalities(DomainCtx);
   DomainCtx = isl_set_coalesce(DomainCtx);
 
-  for (MemoryAccess *MA : InvMAs)
-    TargetList.push_back(std::make_pair(MA, isl_set_copy(DomainCtx)));
+  Scop &S = *getParent();
+  ScalarEvolution &SE = *S.getSE();
+
+  // Project out all parameters that relate to loads in this statement that
+  // we will hoist. Otherwise we would have cyclic dependences on the
+  // constraints under which the hoisted loads are executed.
+  for (MemoryAccess *MA : InvMAs) {
+    Instruction *AccInst = MA->getAccessInstruction();
+    if (SE.isSCEVable(AccInst->getType())) {
+      isl_id *ParamId = S.getIdForParam(SE.getSCEV(AccInst));
+      if (ParamId) {
+        int Dim = isl_set_find_dim_by_id(DomainCtx, isl_dim_param, ParamId);
+        DomainCtx = isl_set_eliminate(DomainCtx, isl_dim_param, Dim, 1);
+      }
+      isl_id_free(ParamId);
+    }
+  }
+
+  for (MemoryAccess *MA : InvMAs) {
+
+    // Check for another invariant access that accesses the same location as
+    // MA and if found consolidate them. Otherwise create a new equivalence
+    // class at the end of InvariantAccesses.
+    // TODO: This is quadratic in the number invariant accesses.
+    LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());
+    const SCEV *PointerSCEV = SE.getSCEV(LInst->getPointerOperand());
+    bool Consolidated = false;
+
+    for (auto &IAClass : InvariantAccesses) {
+      InvariantAccessTy &IA = IAClass.front();
+      LoadInst *IALInst = cast<LoadInst>(IA.first->getAccessInstruction());
+      const SCEV *IAPointerSCEV = SE.getSCEV(IALInst->getPointerOperand());
+      if (PointerSCEV != IAPointerSCEV)
+        continue;
+
+      isl_set *IAClassDomainCtx =
+          isl_set_union(IA.second, isl_set_copy(DomainCtx));
+      IAClass.push_front(std::make_pair(MA, IAClassDomainCtx));
+      Consolidated = true;
+      break;
+    }
+
+    if (Consolidated)
+      continue;
+
+    InvariantAccesses.emplace_back(
+        InvariantAccessListTy({std::make_pair(MA, isl_set_copy(DomainCtx))}));
+  }
 
   isl_set_free(DomainCtx);
 }
 
 //===----------------------------------------------------------------------===//
 /// Scop class implement
 
 void Scop::setContext(__isl_take isl_set *NewContext) {
   NewContext = isl_set_align_params(NewContext, isl_set_get_space(Context));
   isl_set_free(Context);
   Context = NewContext;
 }
 
 void Scop::addParams(std::vector<const SCEV *> NewParameters) {
   for (const SCEV *Parameter : NewParameters) {
     Parameter = extractConstantFactor(Parameter, *SE).second;
     if (ParameterIds.find(Parameter) != ParameterIds.end())
       continue;
 
     int dimension = Parameters.size();
 
     Parameters.push_back(Parameter);
     ParameterIds[Parameter] = dimension;
   }
 }
 
 __isl_give isl_id *Scop::getIdForParam(const SCEV *Parameter) const {
+  // Normalize invariant loads first to get the correct parameter SCEV.
+  Parameter = normalizeInvariantLoadSCEV(Parameter, *getSE(), getRIL());
+
   ParamIdType::const_iterator IdIter = ParameterIds.find(Parameter);
 
   if (IdIter == ParameterIds.end())
     return nullptr;
 
   std::string ParameterName;
 
   if (const SCEVUnknown *ValueParameter = dyn_cast<SCEVUnknown>(Parameter)) {
if (MaxLD == 0)
     return 1;
 
   assert(MinLD >= 1 && "Minimal loop depth should be at least one");
   assert(MaxLD >= MinLD &&
          "Maximal loop depth was smaller than mininaml loop depth?");
   return MaxLD - MinLD + 1;
 }
 
-Scop::Scop(Region &R, AccFuncMapType &AccFuncMap,
+Scop::Scop(Region &R, AccFuncMapType &AccFuncMap, ScopDetection &SD,
            ScalarEvolution &ScalarEvolution, DominatorTree &DT,
            isl_ctx *Context, unsigned MaxLoopDepth)
-    : DT(DT), SE(&ScalarEvolution), R(R), AccFuncMap(AccFuncMap),
+    : DT(DT), SE(&ScalarEvolution), SD(SD), R(R), AccFuncMap(AccFuncMap),
       IsOptimized(false), HasSingleExitEdge(R.getExitingBlock()),
       MaxLoopDepth(MaxLoopDepth), IslCtx(Context), Affinator(this),
       BoundaryContext(nullptr) {}
 
 void Scop::init(LoopInfo &LI, ScopDetection &SD, AliasAnalysis &AA) {
   buildContext();
 
   buildDomains(&R, LI, SD, DT);
for (MinMaxAccessTy &MMA : MinMaxAccessPair.first) {
       isl_pw_multi_aff_free(MMA.second);
     }
     for (MinMaxAccessTy &MMA : MinMaxAccessPair.second) {
       isl_pw_multi_aff_free(MMA.first);
       isl_pw_multi_aff_free(MMA.second);
     }
   }
 
-  for (const auto &IA : InvariantAccesses)
-    isl_set_free(IA.second);
+  for (const auto &IAClass : InvariantAccesses)
+    isl_set_free(IAClass.front().second);
 }
 
 void Scop::updateAccessDimensionality() {
   for (auto &Stmt : *this)
     for (auto &Access : Stmt)
       Access->updateDimensionality();
 }
 

 }
 
 void Scop::hoistInvariantLoads() {
   isl_union_map *Writes = getWrites();
   for (ScopStmt &Stmt : *this) {
 
     // TODO: Loads that are not loop carried, hence are in a statement with
     //       zero iterators, are by construction invariant, though we
-    //       currently "hoist" them anyway.
+    //       currently "hoist" them anyway. This is necessary because we allow
+    //       them to be treated as parameters (e.g., in conditions) and our code
+    //       generation would otherwise use the old value.
 
     isl_set *Domain = Stmt.getDomain();
     MemoryAccessList InvMAs;
 
     for (MemoryAccess *MA : Stmt) {
       if (MA->isImplicit() || MA->isWrite() || !MA->isAffine())
         continue;
 
for (ScopStmt &Stmt : *this) {
     Stmt.hoistMemoryAccesses(InvMAs, InvariantAccesses);
 
     isl_set_free(Domain);
   }
   isl_union_map_free(Writes);
 
   if (!InvariantAccesses.empty())
     IsOptimized = true;
+
+  // Check required invariant loads that were tagged during SCoP detection.
+  for (const auto EquivClass : getRIL())
+    for (LoadInst *LI : EquivClass.second) {
+      assert(LI && getRegion().contains(LI));
+      ScopStmt *Stmt = getStmtForBasicBlock(LI->getParent());
+      if (Stmt->lookupAccessesFor(LI) != nullptr) {
+        DEBUG(errs() << "\n\nWARNING: Load (" << *LI
+                     << ") is required to be invariant but was not marked as "
+                        "such. SCoP for "
+                     << getRegion() << " will be dropped\n\n");
+        addAssumption(isl_set_empty(getParamSpace()));
+        return;
+      }
+    }
+
+  // We want invariant accesses to be sorted in a "natural order" because there
+  // might be dependences between invariant loads. These can be caused by
+  // indirect loads but also because an invariant load is only conditionally
+  // executed and the condition is dependent on another invariant load. As we
+  // want to do code generation in a straight forward way, e.g., preload the
+  // accesses in the list one after another, we sort them such that the
+  // preloaded values needed in the conditions will always be in front. Before
+  // we already ordered the accesses such that indirect loads can be resolved,
+  // thus we use a stable sort here.
+
+  auto compareInvariantAccesses = [this](
+      const InvariantAccessListTy &IAClass0,
+      const InvariantAccessListTy &IAClass1) {
+    const InvariantAccessTy &IA0 = IAClass0.front();
+    const InvariantAccessTy &IA1 = IAClass1.front();
+
+    Instruction *AI0 = IA0.first->getAccessInstruction();
+    Instruction *AI1 = IA1.first->getAccessInstruction();
+
+    const SCEV *S0 =
+        SE->isSCEVable(AI0->getType()) ? SE->getSCEV(AI0) : nullptr;
+    const SCEV *S1 =
+        SE->isSCEVable(AI1->getType()) ? SE->getSCEV(AI1) : nullptr;
+
+    isl_id *Id0 = getIdForParam(S0);
+    isl_id *Id1 = getIdForParam(S1);
+
+    if (Id0 && !Id1) {
+      isl_id_free(Id0);
+      isl_id_free(Id1);
+      return true;
+    }
+
+    if (!Id0) {
+      isl_id_free(Id0);
+      isl_id_free(Id1);
+      return false;
+    }
+
+    assert(Id0 && Id1);
+
+    isl_set *Dom0 = IA0.second;
+    isl_set *Dom1 = IA1.second;
+
+    int Dim0 = isl_set_find_dim_by_id(Dom0, isl_dim_param, Id0);
+    int Dim1 = isl_set_find_dim_by_id(Dom0, isl_dim_param, Id1);
+
+    bool Involves0Id1 = isl_set_involves_dims(Dom0, isl_dim_param, Dim1, 1);
+    bool Involves1Id0 = isl_set_involves_dims(Dom1, isl_dim_param, Dim0, 1);
+    assert(!(Involves0Id1 && Involves1Id0));
+
+    isl_id_free(Id0);
+    isl_id_free(Id1);
+
+    return Involves1Id0;
+  };
+
+  std::stable_sort(InvariantAccesses.begin(), InvariantAccesses.end(),
+                   compareInvariantAccesses);
 }
 
 const ScopArrayInfo *
 Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *AccessType,
                                ArrayRef<const SCEV *> Sizes, bool IsPHI) {
   auto &SAI = ScopArrayInfoMap[std::make_pair(BasePtr, IsPHI)];
   if (!SAI) {
     SAI.reset(new ScopArrayInfo(BasePtr, AccessType, getIslCtx(), Sizes, IsPHI,

 }
 
 void Scop::print(raw_ostream &OS) const {
   OS.indent(4) << "Function: " << getRegion().getEntry()->getParent()->getName()
                << "\n";
   OS.indent(4) << "Region: " << getNameStr() << "\n";
   OS.indent(4) << "Max Loop Depth:  " << getMaxLoopDepth() << "\n";
   OS.indent(4) << "Invariant Accesses: {\n";
-  for (const auto &IA : InvariantAccesses) {
-    IA.first->print(OS);
-    OS.indent(12) << "Execution Context: " << IA.second << "\n";
+  for (const auto &IAClass : InvariantAccesses) {
+    IAClass.front().first->print(OS);
+    OS.indent(12) << "Execution Context: " << IAClass.front().second << "\n";
   }
   OS.indent(4) << "}\n";
   printContext(OS.indent(4));
   printArrayInfo(OS.indent(4));
   printAliasAssumptions(OS);
   printStatements(OS.indent(4));
 }
 
 void Scop::dump() const { print(dbgs()); }
 
 isl_ctx *Scop::getIslCtx() const { return IslCtx; }
 
+const InvariantLoadsClassesTy &Scop::getRIL() const {
+  return *SD.getRequiredInvariantLoads(&getRegion());
+}
+
 __isl_give isl_pw_aff *Scop::getPwAff(const SCEV *E, BasicBlock *BB) {
-  return Affinator.getPwAff(E, BB);
+  return Affinator.getPwAff(E, getRIL(), BB);
 }
 
 __isl_give isl_union_set *Scop::getDomains() const {
   isl_union_set *Domain = isl_union_set_empty(getParamSpace());
 
   for (const ScopStmt &Stmt : *this)
     Domain = isl_union_set_add_set(Domain, Stmt.getDomain());
 
bool ScopInfo::buildScalarDependences(Instruction *Inst, Region *R,
 
   return AnyCrossStmtUse;
 }
 
 extern MapInsnToMemAcc InsnToMemAcc;
 
 void ScopInfo::buildMemoryAccess(
     Instruction *Inst, Loop *L, Region *R,
-    const ScopDetection::BoxedLoopsSetTy *BoxedLoops) {
+    const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
+    const InvariantLoadsClassesTy &ScopRIL) {
   unsigned Size;
   Type *SizeType;
   Value *Val;
   enum MemoryAccess::AccessType Type;
 
   if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
     SizeType = Load->getType();
     Size = TD->getTypeStoreSize(SizeType);
if (auto *GEP = dyn_cast<GetElementPtrInst>(NewAddress)) {
       std::vector<const SCEV *> Subscripts;
       std::vector<int> Sizes;
       std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, *SE);
       auto BasePtr = GEP->getOperand(0);
 
       std::vector<const SCEV *> SizesSCEV;
 
       bool AllAffineSubcripts = true;
-      for (auto Subscript : Subscripts)
-        if (!isAffineExpr(R, Subscript, *SE)) {
+      for (auto Subscript : Subscripts) {
+        InvariantLoadsClassesTy AccessRIL;
+        AllAffineSubcripts =
+            isAffineExpr(R, Subscript, *SE, nullptr, &AccessRIL);
+
+        for (const auto EquivClass : AccessRIL)
+          for (LoadInst *LInst : EquivClass.second)
+            if (!ScopRIL.lookup(EquivClass.first).count(LInst))
               AllAffineSubcripts = false;
+
+        if (!AllAffineSubcripts)
           break;
-        }
 
       if (AllAffineSubcripts && Sizes.size() > 0) {
         for (auto V : Sizes)
           SizesSCEV.push_back(SE->getSCEV(ConstantInt::get(
               IntegerType::getInt64Ty(BasePtr->getContext()), V)));
         SizesSCEV.push_back(SE->getSCEV(ConstantInt::get(
             IntegerType::getInt64Ty(BasePtr->getContext()), Size)));
 
void ScopInfo::buildMemoryAccess(
   if (BoxedLoops) {
     SetVector<const Loop *> Loops;
     findLoops(AccessFunction, Loops);
     for (const Loop *L : Loops)
       if (BoxedLoops->count(L))
         isVariantInNonAffineLoop = true;
   }
 
-  bool IsAffine = !isVariantInNonAffineLoop &&
-                  isAffineExpr(R, AccessFunction, *SE, BasePointer->getValue());
+  InvariantLoadsClassesTy AccessRIL;
+  bool IsAffine =
+      !isVariantInNonAffineLoop &&
+      isAffineExpr(R, AccessFunction, *SE, BasePointer->getValue(), &AccessRIL);
+
+  for (const auto EquivClass : AccessRIL)
+    for (LoadInst *LInst : EquivClass.second)
+      if (!ScopRIL.lookup(EquivClass.first).count(LInst))
+        IsAffine = false;
 
   // FIXME: Size of the number of bytes of an array element, not the number of
   // elements as probably intended here.
   const SCEV *SizeSCEV =
       SE->getConstant(TD->getIntPtrType(Inst->getContext()), Size);
 
   if (!IsAffine && Type == MemoryAccess::MUST_WRITE)
     Type = MemoryAccess::MAY_WRITE;

 void ScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB,
                                     Region *NonAffineSubRegion,
                                     bool IsExitBlock) {
   Loop *L = LI->getLoopFor(&BB);
 
   // The set of loops contained in non-affine subregions that are part of R.
   const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD->getBoxedLoops(&R);
 
+  // The set of loads that are required to be invariant.
+  auto &ScopRIL = *SD->getRequiredInvariantLoads(&R);
+
   for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) {
     Instruction *Inst = I;
 
     PHINode *PHI = dyn_cast<PHINode>(Inst);
     if (PHI)
       buildPHIAccesses(PHI, R, NonAffineSubRegion, IsExitBlock);
 
     // For the exit block we stop modeling after the last PHI node.
     if (!PHI && IsExitBlock)
       break;
 
+    // TODO: At this point we only know that elements of ScopRIL have to be
+    //       invariant and will be hoisted for the SCoP to be processed. Though,
+    //       there might be other invariant accesses that will be hoisted and
+    //       that would allow to make a non-affine access affine.
     if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
-      buildMemoryAccess(Inst, L, &R, BoxedLoops);
+      buildMemoryAccess(Inst, L, &R, BoxedLoops, ScopRIL);
 
     if (isIgnoredIntrinsic(Inst))
       continue;
 
+    // Do not build scalar dependences for required invariant loads as we will
+    // hoist them later on anyway or drop the SCoP if we cannot.
+    if (LoadInst *LInst = dyn_cast<LoadInst>(Inst)) {
+      const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());
+      if (ScopRIL.lookup(PointerSCEV).count(LInst))
+        continue;
+    }
+
     if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) {
       if (!isa<StoreInst>(Inst))
         addScalarWriteAccess(Inst);
     }
   }
 }
 
 void ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst,

 void ScopInfo::addPHIReadAccess(PHINode *PHI) {
   addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI,
                   ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
                   MemoryAccess::PHI);
 }
 
 void ScopInfo::buildScop(Region &R, DominatorTree &DT) {
   unsigned MaxLoopDepth = getMaxLoopDepthInRegion(R, *LI, *SD);
-  scop = new Scop(R, AccFuncMap, *SE, DT, ctx, MaxLoopDepth);
+  scop = new Scop(R, AccFuncMap, *SD, *SE, DT, ctx, MaxLoopDepth);
 
   buildAccessFunctions(R, R);
 
   // In case the region does not have an exiting block we will later (during
   // code generation) split the exit block. This will move potential PHI nodes
   // from the current exit block into the new region exiting block. Hence, PHI
   // nodes that are at this point not part of the region will be.
   // To handle these PHI nodes later we will now model their operands as scalar

lib/CodeGen/BlockGenerators.cpp

Value *VectorBlockGenerator::generateStrideZeroLoad(
 
   Value *VectorLoad = Builder.CreateShuffleVector(
       ScalarLoad, ScalarLoad, SplatVector, Load->getName() + "_p_splat");
   return VectorLoad;
 }
 
 Value *VectorBlockGenerator::generateUnknownStrideLoad(
     ScopStmt &Stmt, const LoadInst *Load, VectorValueMapT &ScalarMaps,
-    __isl_keep isl_id_to_ast_expr *NewAccesses
-
-    ) {
+    __isl_keep isl_id_to_ast_expr *NewAccesses) {
   int VectorWidth = getVectorWidth();
   const Value *Pointer = Load->getPointerOperand();
   VectorType *VectorType = VectorType::get(
       dyn_cast<PointerType>(Pointer->getType())->getElementType(), VectorWidth);
 
   Value *Vector = UndefValue::get(VectorType);
 
   for (int i = 0; i < VectorWidth; i++) {

lib/CodeGen/CodeGeneration.cpp

bool runOnScop(Scop &S) override {
     // introduced the conditional branch. This is important as the conditional
     // branch will guard the original scop from new induction variables that
     // the SCEVExpander may introduce while code generating the parameters and
     // which may introduce scalar dependences that prevent us from correctly
     // code generating this scop.
     BasicBlock *StartBlock =
         executeScopConditionally(S, this, Builder.getTrue());
     auto SplitBlock = StartBlock->getSinglePredecessor();
+
+    // First generate code for the hoisted invariant loads and transitively the
+    // parameters they reference. Afterwards, for the remaining parameters that
+    // might reference the hoisted loads. Finally, build the runtime check
+    // that might reference both hoisted loads as well as parameters.
     Builder.SetInsertPoint(SplitBlock->getTerminator());
-    NodeBuilder.addParameters(S.getContext());
     NodeBuilder.preloadInvariantLoads();
+    NodeBuilder.addParameters(S.getContext());
+
     Value *RTC = buildRTC(Builder, NodeBuilder.getExprBuilder());
     Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC);
     Builder.SetInsertPoint(StartBlock->begin());
 
     NodeBuilder.create(AstRoot);
 
     NodeBuilder.finalizeSCoP(S);
     fixRegionInfo(EnteringBB->getParent(), R->getParent());

lib/CodeGen/IslNodeBuilder.cpp

void IslNodeBuilder::materializeParameters(isl_set *Set, bool All) {
   for (unsigned i = 0, e = isl_set_dim(Set, isl_dim_param); i < e; ++i) {
     if (!All && !isl_set_involves_dims(Set, isl_dim_param, i, 1))
       continue;
     isl_id *Id = isl_set_get_dim_id(Set, isl_dim_param, i);
     materializeValue(Id);
   }
 }
 
-/// @brief Create the actual preload memory access for @p MA.
-static inline Value *createPreloadLoad(Scop &S, const MemoryAccess &MA,
-                                       isl_ast_build *Build,
-                                       IslExprBuilder &ExprBuilder) {
-  isl_set *AccessRange = isl_map_range(MA.getAccessRelation());
+Value *IslNodeBuilder::preloadUnconditionally(isl_set *AccessRange,
+                                              isl_ast_build *Build) {
   isl_pw_multi_aff *PWAccRel = isl_pw_multi_aff_from_set(AccessRange);
   PWAccRel = isl_pw_multi_aff_gist_params(PWAccRel, S.getContext());
   isl_ast_expr *Access =
       isl_ast_build_access_from_pw_multi_aff(Build, PWAccRel);
   return ExprBuilder.create(Access);
 }
 
 Value *IslNodeBuilder::preloadInvariantLoad(const MemoryAccess &MA,
                                             isl_set *Domain,
                                             isl_ast_build *Build) {
 
+  isl_set *AccessRange = isl_map_range(MA.getAccessRelation());
+  materializeParameters(AccessRange, false);
+
   isl_set *Universe = isl_set_universe(isl_set_get_space(Domain));
   bool AlwaysExecuted = isl_set_is_equal(Domain, Universe);
   isl_set_free(Universe);
 
   if (AlwaysExecuted) {
     isl_set_free(Domain);
-    return createPreloadLoad(S, MA, Build, ExprBuilder);
+    return preloadUnconditionally(AccessRange, Build);
   } else {
 
+    materializeParameters(Domain, false);
     isl_ast_expr *DomainCond = isl_ast_build_expr_from_set(Build, Domain);
 
     Value *Cond = ExprBuilder.create(DomainCond);
     if (!Cond->getType()->isIntegerTy(1))
       Cond = Builder.CreateIsNotNull(Cond);
 
     BasicBlock *CondBB = SplitBlock(Builder.GetInsertBlock(),
                                     Builder.GetInsertPoint(), &DT, &LI);
if (AlwaysExecuted) {
     CondBBTerminator->eraseFromParent();
 
     Builder.SetInsertPoint(ExecBB);
     Builder.CreateBr(MergeBB);
 
     Builder.SetInsertPoint(ExecBB->getTerminator());
     Instruction *AccInst = MA.getAccessInstruction();
     Type *AccInstTy = AccInst->getType();
-    Value *PreAccInst = createPreloadLoad(S, MA, Build, ExprBuilder);
+    Value *PreAccInst = preloadUnconditionally(AccessRange, Build);
 
     Builder.SetInsertPoint(MergeBB->getTerminator());
     auto *MergePHI = Builder.CreatePHI(
         AccInstTy, 2, "polly.preload." + AccInst->getName() + ".merge");
     MergePHI->addIncoming(PreAccInst, ExecBB);
     MergePHI->addIncoming(Constant::getNullValue(AccInstTy), CondBB);
 
     return MergePHI;
   }
 }
 
 void IslNodeBuilder::preloadInvariantLoads() {
 
-  const auto &InvAccList = S.getInvariantAccesses();
-  if (InvAccList.empty())
+  const auto &InvariantAccesses = S.getInvariantAccesses();
+  if (InvariantAccesses.empty())
     return;
 
   const Region &R = S.getRegion();
   BasicBlock *EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();
 
   BasicBlock *PreLoadBB =
       SplitBlock(Builder.GetInsertBlock(), Builder.GetInsertPoint(), &DT, &LI);
   PreLoadBB->setName("polly.preload.begin");
   Builder.SetInsertPoint(PreLoadBB->begin());
 
   isl_ast_build *Build =
       isl_ast_build_from_context(isl_set_universe(S.getParamSpace()));
 
-  for (const auto &IA : InvAccList) {
-    MemoryAccess *MA = IA.first;
+  for (const auto &IAClass : InvariantAccesses) {
+
+    MemoryAccess *MA = IAClass.front().first;
     assert(!MA->isImplicit());
 
-    isl_set *Domain = isl_set_copy(IA.second);
+    isl_set *Domain = isl_set_copy(IAClass.front().second);
     Instruction *AccInst = MA->getAccessInstruction();
     Value *PreloadVal = preloadInvariantLoad(*MA, Domain, Build);
-    ValueMap[AccInst] = PreloadVal;
+    for (const InvariantAccessTy &IA : IAClass)
+      ValueMap[IA.first->getAccessInstruction()] = PreloadVal;
 
     if (SE.isSCEVable(AccInst->getType())) {
       isl_id *ParamId = S.getIdForParam(SE.getSCEV(AccInst));
       if (ParamId)
         IDToValue[ParamId] = PreloadVal;
       isl_id_free(ParamId);
     }
 
void IslNodeBuilder::addParameters(__isl_take isl_set *Context) {
   }
 
   isl_set_free(Context);
 }
 
 Value *IslNodeBuilder::generateSCEV(const SCEV *Expr) {
   Instruction *InsertLocation = --(Builder.GetInsertBlock()->end());
   return expandCodeFor(S, SE, DL, "polly", Expr, Expr->getType(),
-                       InsertLocation);
+                       InsertLocation, &ValueMap);
 }

lib/Support/SCEVAffinator.cpp

SCEVAffinator::SCEVAffinator(Scop *S)
     : S(S), Ctx(S->getIslCtx()), R(S->getRegion()), SE(*S->getSE()),
       TD(R.getEntry()->getParent()->getParent()->getDataLayout()) {}
 
 SCEVAffinator::~SCEVAffinator() {
   for (const auto &CachedPair : CachedExpressions)
     isl_pw_aff_free(CachedPair.second);
 }
 
-__isl_give isl_pw_aff *SCEVAffinator::getPwAff(const SCEV *Expr,
-                                               BasicBlock *BB) {
+__isl_give isl_pw_aff *
+SCEVAffinator::getPwAff(const SCEV *Expr, const InvariantLoadsClassesTy &ILC,
   this->BB = BB;
 
   if (BB) {
     auto *DC = S->getDomainConditions(BB);
     NumIterators = isl_set_n_dim(DC);
     isl_set_free(DC);
   } else
     NumIterators = 0;
 
-  S->addParams(getParamsInAffineExpr(&R, Expr, SE));
+  S->addParams(getParamsInAffineExpr(&R, Expr, SE, ILC));
 
   return visit(Expr);
 }
 
 __isl_give isl_set *
 SCEVAffinator::getWrappingContext(SCEV::NoWrapFlags Flags, Type *ExprType,
                                   __isl_keep isl_pw_aff *PWA,
                                   __isl_take isl_set *ExprDomain) const {

lib/Support/SCEVValidator.cpp

 
 #include "polly/Support/SCEVValidator.h"
 #include "polly/ScopInfo.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Support/Debug.h"
 #include <vector>
 
 using namespace llvm;
+using namespace polly;
 
 #define DEBUG_TYPE "polly-scev-validator"
 
 namespace SCEVType {
 /// @brief The type of a SCEV
 ///
 /// To check for the validity of a SCEV we assign to each SCEV a type. The
 /// possible types are INT, PARAM, IV and INVALID. The order of the types is

 
 /// Check if a SCEV is valid in a SCoP.
 struct SCEVValidator
     : public SCEVVisitor<SCEVValidator, class ValidatorResult> {
 private:
   const Region *R;
   ScalarEvolution &SE;
   const Value *BaseAddress;
+  InvariantLoadsClassesTy *ILC;
 
 public:
-  SCEVValidator(const Region *R, ScalarEvolution &SE, const Value *BaseAddress)
-      : R(R), SE(SE), BaseAddress(BaseAddress) {}
+  SCEVValidator(const Region *R, ScalarEvolution &SE, const Value *BaseAddress,
+                InvariantLoadsClassesTy *ILC)
+      : R(R), SE(SE), BaseAddress(BaseAddress), ILC(ILC) {}
 
   class ValidatorResult visitConstant(const SCEVConstant *Constant) {
     return ValidatorResult(SCEVType::INT);
   }
 
   class ValidatorResult visitTruncateExpr(const SCEVTruncateExpr *Expr) {
     ValidatorResult Op = visit(Expr->getOperand());
 
if (R->contains(I)) {
       DEBUG(dbgs() << "INVALID: UnknownExpr references an instruction "
                       "within the region\n");
       return ValidatorResult(SCEVType::INVALID);
     }
 
     return ValidatorResult(SCEVType::PARAM, S);
   }
 
+  ValidatorResult visitLoadInstruction(Instruction *I, const SCEV *S) {
+    if (R->contains(I) && ILC) {
+      // Insert I in the equivalence class of the pointer of I and use
+      // the first element of that equivalence class to determine the
+      // parameter that is used for I.
+
+      LoadInst *LInst = cast<LoadInst>(I);
+      const SCEV *PointerSCEV = SE.getSCEV(LInst->getPointerOperand());
+      auto &EquivClass = (*ILC)[PointerSCEV];
+      EquivClass.insert(cast<LoadInst>(I));
+      const SCEV *EquivClassSCEV = SE.getSCEV(EquivClass[0]);
+      return ValidatorResult(SCEVType::PARAM, EquivClassSCEV);
+    }
+
+    return visitGenericInst(I, S);
+  }
+
   ValidatorResult visitSDivInstruction(Instruction *SDiv, const SCEV *S) {
     assert(SDiv->getOpcode() == Instruction::SDiv &&
            "Assumed SDiv instruction!");
 
     auto *Divisor = SDiv->getOperand(1);
     auto *CI = dyn_cast<ConstantInt>(Divisor);
     if (!CI)
       return visitGenericInst(SDiv, S);
ValidatorResult visitUnknown(const SCEVUnknown *Expr) {
 
     if (BaseAddress == V) {
       DEBUG(dbgs() << "INVALID: UnknownExpr references BaseAddress\n");
       return ValidatorResult(SCEVType::INVALID);
     }
 
     if (Instruction *I = dyn_cast<Instruction>(Expr->getValue())) {
       switch (I->getOpcode()) {
+      case Instruction::Load:
+        return visitLoadInstruction(I, Expr);
       case Instruction::SDiv:
         return visitSDivInstruction(I, Expr);
       case Instruction::SRem:
         return visitSRemInstruction(I, Expr);
       default:
         return visitGenericInst(I, Expr);
       }
     }
void findValues(const SCEV *Expr, SetVector<Value *> &Values) {
   ST.visitAll(Expr);
 }
 
 bool hasScalarDepsInsideRegion(const SCEV *Expr, const Region *R) {
   return SCEVInRegionDependences::hasDependences(Expr, R);
 }
 
 bool isAffineExpr(const Region *R, const SCEV *Expr, ScalarEvolution &SE,
-                  const Value *BaseAddress) {
+                  const Value *BaseAddress, InvariantLoadsClassesTy *ILC) {
   if (isa<SCEVCouldNotCompute>(Expr))
     return false;
 
-  SCEVValidator Validator(R, SE, BaseAddress);
+  SCEVValidator Validator(R, SE, BaseAddress, ILC);
   DEBUG({
     dbgs() << "\n";
     dbgs() << "Expr: " << *Expr << "\n";
     dbgs() << "Region: " << R->getNameStr() << "\n";
     dbgs() << " -> ";
   });
 
   ValidatorResult Result = Validator.visit(Expr);
 
   DEBUG({
     if (Result.isValid())
       dbgs() << "VALID\n";
     dbgs() << "\n";
   });
 
   return Result.isValid();
 }
 
-std::vector<const SCEV *> getParamsInAffineExpr(const Region *R,
-                                                const SCEV *Expr,
-                                                ScalarEvolution &SE,
-                                                const Value *BaseAddress) {
+std::vector<const SCEV *>
+getParamsInAffineExpr(const Region *R, const SCEV *Expr, ScalarEvolution &SE,
+                      const InvariantLoadsClassesTy &ILC,
   if (isa<SCEVCouldNotCompute>(Expr))
     return std::vector<const SCEV *>();
 
-  SCEVValidator Validator(R, SE, BaseAddress);
+  // TODO: The const cast is necessary since the Validator is also used to
+  //       create the equivalence classes, however here we just want the
+  //       parameters to be normalized with regards to ILC.
+  SCEVValidator Validator(R, SE, BaseAddress,
+                          const_cast<InvariantLoadsClassesTy *>(&ILC));
   ValidatorResult Result = Validator.visit(Expr);
   assert(Result.isValid() && "Requested parameters for an invalid SCEV!");
 
   return Result.getParameters();
 }
 
 std::pair<const SCEV *, const SCEV *>
 extractConstantFactor(const SCEV *S, ScalarEvolution &SE) {

lib/Support/ScopHelper.cpp

 //===- ScopHelper.cpp - Some Helper Functions for Scop.  ------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Small functions that help with Scop and LLVM-IR.
 //
 //===----------------------------------------------------------------------===//
 
 #include "polly/Support/ScopHelper.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"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
if (BranchInst *BR = dyn_cast<BranchInst>(TI)) {
     return BR->getCondition();
   }
 
   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
     return SI->getCondition();
 
   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;
+}
+
+const SCEV *
+polly::normalizeInvariantLoadSCEV(const SCEV *S, ScalarEvolution &SE,
+                                  const InvariantLoadsClassesTy &ILC) {
+  const SCEVUnknown *SU = dyn_cast_or_null<SCEVUnknown>(S);
+  if (!SU)
+    return S;
+
+  LoadInst *LInst = dyn_cast<LoadInst>(SU->getValue());
+  if (!LInst)
+    return S;
+
+  const auto &EquivClass = ILC.lookup(SE.getSCEV(LInst->getPointerOperand()));
+  if (EquivClass.empty())
+    return S;
+
+  return SE.getSCEV(*EquivClass.begin());
+}

test/Isl/CodeGen/invariant_load_base_pointer.ll

+; RUN: opt %loadPolly -polly-no-early-exit -polly-codegen -polly-ignore-aliasing -polly-detect-unprofitable -S < %s | FileCheck %s
+;
+; CHECK-LABEL: polly.preload.begin:
+; CHECK-NEXT:    %polly.access.BPLoc = getelementptr i32*, i32** %BPLoc, i64 0
+; CHECK-NEXT:    %polly.access.BPLoc.load = load i32*, i32** %polly.access.BPLoc
+;
+; CHECK-LABEL: polly.stmt.bb2:
+; CHECK-NEXT:    %p_tmp3 = getelementptr inbounds i32, i32* %polly.access.BPLoc.load, i64 %polly.indvar
+;
+;    void f(int **BPLoc) {
+;      for (int i = 0; i < 1024; i++)
+;        (*BPLoc)[i] = 0;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32** %BPLoc) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb4, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb4 ], [ 0, %bb ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %bb2, label %bb5
+
+bb2:                                              ; preds = %bb1
+  %tmp = load i32*, i32** %BPLoc, align 8
+  %tmp3 = getelementptr inbounds i32, i32* %tmp, i64 %indvars.iv
+  store i32 0, i32* %tmp3, align 4
+  br label %bb4
+
+bb4:                                              ; preds = %bb2
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb5:                                              ; preds = %bb1
+  ret void
+}

test/Isl/CodeGen/invariant_load_base_pointer_conditional.ll

+; RUN: opt %loadPolly -polly-no-early-exit -polly-codegen -polly-ignore-aliasing -polly-detect-unprofitable -S < %s | FileCheck %s
+;
+; CHECK-LABEL: polly.preload.begin:
+; CHECK-NEXT:    %0 = sext i32 %N to i64
+; CHECK-NEXT:    %1 = icmp sge i64 %0, 514
+; CHECK-NEXT:    br label %polly.preload.cond
+;
+; CHECK-LABEL: polly.preload.cond:
+; CHECK-NEXT:    br i1 %1, label %polly.preload.exec, label %polly.preload.merge
+;
+; CHECK-LABEL: polly.preload.merge:
+; CHECK-NEXT:    %polly.preload.tmp6.merge = phi i32* [ %polly.access.BPLoc.load, %polly.preload.exec ], [ null, %polly.preload.cond ]
+;
+; CHECK-LABEL: polly.stmt.bb5:
+; CHECK-NEXT:    %p_tmp7 = getelementptr inbounds i32, i32* %polly.preload.tmp6.merge, i64 %polly.indvar6
+;
+;    void f(int **BPLoc, int *A, int N) {
+;      for (int i = 0; i < N; i++)
+;        if (i > 512)
+;          (*BPLoc)[i] = 0;
+;        else
+;          A[i] = 0;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32** %BPLoc, i32* %A, i32 %N) {
+bb:
+  %tmp = sext i32 %N to i64
+  br label %bb1
+
+bb1:                                              ; preds = %bb11, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb11 ], [ 0, %bb ]
+  %tmp2 = icmp slt i64 %indvars.iv, %tmp
+  br i1 %tmp2, label %bb3, label %bb12
+
+bb3:                                              ; preds = %bb1
+  %tmp4 = icmp sgt i64 %indvars.iv, 512
+  br i1 %tmp4, label %bb5, label %bb8
+
+bb5:                                              ; preds = %bb3
+  %tmp6 = load i32*, i32** %BPLoc, align 8
+  %tmp7 = getelementptr inbounds i32, i32* %tmp6, i64 %indvars.iv
+  store i32 0, i32* %tmp7, align 4
+  br label %bb10
+
+bb8:                                              ; preds = %bb3
+  %tmp9 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 0, i32* %tmp9, align 4
+  br label %bb10
+
+bb10:                                             ; preds = %bb8, %bb5
+  br label %bb11
+
+bb11:                                             ; preds = %bb10
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb12:                                             ; preds = %bb1
+  ret void
+}

test/Isl/CodeGen/invariant_load_condition.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-codegen -S < %s | FileCheck %s
+;
+; CHECK-LABEL: polly.preload.begin:
+; CHECK-NEXT:     %polly.access.C = getelementptr i32, i32* %C, i64 0
+; CHECK-NEXT:     %polly.access.C.load = load i32, i32* %polly.access.C
+; CHECK-NOT:      %polly.access.C.load = load i32, i32* %polly.access.C
+;
+; CHECK: polly.cond
+; CHECK:   %[[R0:[0-9]*]] = sext i32 %polly.access.C.load to i64
+; CHECK:   %[[R1:[0-9]*]] = icmp sle i64 %[[R0]], -1
+;
+; CHECK: polly.cond
+; CHECK:   %[[R2:[0-9]*]] = sext i32 %polly.access.C.load to i64
+; CHECK:   %[[R3:[0-9]*]] = icmp sge i64 %[[R2]], 1
+;
+; CHECK-NOT:  polly.stmt.bb2
+;
+;    void f(int *A, int *C) {
+;      for (int i = 0; i < 1024; i++)
+;        if (*C)
+;          A[i] = 0;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32* %C) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb7, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb7 ], [ 0, %bb ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %bb2, label %bb8
+
+bb2:                                              ; preds = %bb1
+  %tmp = load i32, i32* %C, align 4
+  %tmp3 = icmp eq i32 %tmp, 0
+  br i1 %tmp3, label %bb6, label %bb4
+
+bb4:                                              ; preds = %bb2
+  %tmp5 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 0, i32* %tmp5, align 4
+  br label %bb6
+
+bb6:                                              ; preds = %bb2, %bb4
+  br label %bb7
+
+bb7:                                              ; preds = %bb6
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb8:                                              ; preds = %bb1
+  ret void
+}

test/Isl/CodeGen/invariant_load_escaping_second_scop.ll

+; RUN: opt %loadPolly -polly-codegen -polly-no-early-exit -polly-detect-unprofitable -S < %s | FileCheck %s
+;
+;    void fence(void);
+;
+;    void f(int *A, int *B) {
+;      int i = 0;
+;      int x = 0;
+;
+;      do {
+;        x = *B;
+; S:     A[i] += x;
+;      } while (i++ < 100);
+;
+;      fence();
+;
+;      do {
+; P:     A[i]++;
+;      } while (i++ < x / 2);
+;    }
+;
+; CHECK:      polly.start:
+; CHECK-NEXT:   sext i32 %tmp.merge to i64
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32* %B) {
+entry:
+  br label %stmt.S
+
+stmt.S:                                          ; preds = %do.cond, %entry
+  %indvars.iv2 = phi i64 [ %indvars.iv.next3, %do.cond ], [ 0, %entry ]
+  %tmp = load i32, i32* %B, align 4
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv2
+  %tmp4 = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp4, %tmp
+  store i32 %add, i32* %arrayidx, align 4
+  br label %do.cond
+
+do.cond:                                          ; preds = %do.body
+  %indvars.iv.next3 = add nuw nsw i64 %indvars.iv2, 1
+  %exitcond = icmp ne i64 %indvars.iv.next3, 101
+  br i1 %exitcond, label %stmt.S, label %do.end
+
+do.end:                                           ; preds = %do.cond
+  %tmp5 = trunc i64 101 to i32
+  call void @fence() #2
+  %tmp6 = sext i32 %tmp5 to i64
+  br label %stmt.P
+
+stmt.P:                                        ; preds = %do.cond.5, %do.end
+  %indvars.iv = phi i64 [ %indvars.iv.next, %do.cond.5 ], [ %tmp6, %do.end ]
+  %arrayidx3 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp7 = load i32, i32* %arrayidx3, align 4
+  %inc4 = add nsw i32 %tmp7, 1
+  store i32 %inc4, i32* %arrayidx3, align 4
+  br label %do.cond.5
+
+do.cond.5:                                        ; preds = %do.body.1
+  %div = sdiv i32 %tmp, 2
+  %tmp8 = sext i32 %div to i64
+  %cmp7 = icmp slt i64 %indvars.iv, %tmp8
+  %indvars.iv.next = add i64 %indvars.iv, 1
+  br i1 %cmp7, label %stmt.P, label %do.end.8
+
+do.end.8:                                         ; preds = %do.cond.5
+  ret void
+}
+
+declare void @fence()

test/Isl/CodeGen/invariant_load_loop_ub.ll

+; RUN: opt %loadPolly -polly-codegen -polly-detect-unprofitable -S < %s | FileCheck %s
+;
+; CHECK: polly.start
+;
+;    void f(int *A, int *UB) {
+;      for (int i = 0; i < *UB; i++)
+;        A[i] = 0;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32* %UB) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb6, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb6 ], [ 0, %bb ]
+  %tmp = load i32, i32* %UB, align 4
+  %tmp2 = sext i32 %tmp to i64
+  %tmp3 = icmp slt i64 %indvars.iv, %tmp2
+  br i1 %tmp3, label %bb4, label %bb7
+
+bb4:                                              ; preds = %bb1
+  %tmp5 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 0, i32* %tmp5, align 4
+  br label %bb6
+
+bb6:                                              ; preds = %bb4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb7:                                              ; preds = %bb1
+  ret void
+}

test/Isl/CodeGen/invariant_load_outermost.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit \
 ; RUN: -polly-codegen -S < %s | FileCheck %s
 
 ; CHECK: polly.start
 
 ;    void f(int *A) {
 ;      if (*A > 42)
 ;        *A = *A + 1;
 ;      else
 ;        *A = *A - 1;
 ;    }
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(i32* %A) {
 entry:
   br label %entry.split
 
 entry.split:
   %tmp = load i32, i32* %A, align 4
   %cmp = icmp sgt i32 %tmp, 42
   br i1 %cmp, label %if.then, label %if.else
 
 if.then:                                          ; preds = %entry
   %tmp1 = load i32, i32* %A, align 4
   %add = add nsw i32 %tmp1, 1
   br label %if.end
 
 if.else:                                          ; preds = %entry
   %tmp2 = load i32, i32* %A, align 4
   %sub = add nsw i32 %tmp2, -1
   br label %if.end
 
 if.end:                                           ; preds = %if.else, %if.then
   %storemerge = phi i32 [ %sub, %if.else ], [ %add, %if.then ]
   store i32 %storemerge, i32* %A, align 4
   ret void
 }

test/Isl/CodeGen/invariant_load_parameters_cyclic_dependence.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s --check-prefix=SCOP
+; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
+;
+; This caused the code generation to emit a broken module as there are two
+; dependences that need to be considered, thus code has to be emitted in a
+; certain order:
+;   1) To preload A[N * M] the expression N * M [p0] is needed (both for the
+;      condition under which A[N * M] is executed as well as to compute the
+;      index).
+;   2) To generate (A[N * M] / 2) [p1] the preloaded value is needed.
+;
+; SCOP: p0: (%N * %M)
+; SCOP: p1: (zext i32 (%tmp4 /u 2) to i64)
+;
+; CHECK: polly.preload.merge:
+; CHECK:   %polly.preload.tmp4.merge = phi i32 [ %polly.access.A.load, %polly.preload.exec ], [ 0, %polly.preload.cond ]
+; CHECK:   %3 = lshr i32 %polly.preload.tmp4.merge, 1
+; CHECK:   %4 = zext i32 %3 to i64
+;
+;    void f(int *restrict A, int *restrict B, int N, int M) {
+;
+;      for (int i = 0; i < N * M; i++)
+;        for (int j = 0; j < A[N * M] / 2; j++)
+;          B[i + j]++;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* noalias %A, i32* noalias %B, i32 %N, i32 %M) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc.8, %entry
+  %indvars.iv2 = phi i64 [ %indvars.iv.next3, %for.inc.8 ], [ 0, %entry ]
+  %mul = mul nsw i32 %N, %M
+  %tmp = sext i32 %mul to i64
+  %cmp = icmp slt i64 %indvars.iv2, %tmp
+  br i1 %cmp, label %for.body, label %for.end.10
+
+for.body:                                         ; preds = %for.cond
+  br label %for.cond.1
+
+for.cond.1:                                       ; preds = %for.inc, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %for.body ]
+  %mul2 = mul nsw i32 %N, %M
+  %idxprom = sext i32 %mul2 to i64
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom
+  %tmp4 = load i32, i32* %arrayidx, align 4
+  %div = udiv i32 %tmp4, 2
+  %tmp5 = sext i32 %div to i64
+  %cmp3 = icmp slt i64 %indvars.iv, %tmp5
+  br i1 %cmp3, label %for.body.4, label %for.end
+
+for.body.4:                                       ; preds = %for.cond.1
+  %tmp6 = add nsw i64 %indvars.iv2, %indvars.iv
+  %arrayidx6 = getelementptr inbounds i32, i32* %B, i64 %tmp6
+  %tmp7 = load i32, i32* %arrayidx6, align 4
+  %inc = add nsw i32 %tmp7, 1
+  store i32 %inc, i32* %arrayidx6, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body.4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond.1
+
+for.end:                                          ; preds = %for.cond.1
+  br label %for.inc.8
+
+for.inc.8:                                        ; preds = %for.end
+  %indvars.iv.next3 = add nuw nsw i64 %indvars.iv2, 1
+  br label %for.cond
+
+for.end.10:                                       ; preds = %for.cond
+  ret void
+}

test/Isl/CodeGen/invariant_load_ptr_ptr_noalias.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-codegen -polly-ignore-aliasing -S -polly-no-early-exit < %s | FileCheck %s
+;
+; CHECK-LABEL: polly.preload.begin:
+; CHECK:   %polly.access.A = getelementptr i32**, i32*** %A, i64 42
+; CHECK:   %polly.access.A.load = load i32**, i32*** %polly.access.A
+; CHECK:   %polly.access.polly.access.A.load = getelementptr i32*, i32** %polly.access.A.load, i64 32
+; CHECK:   %polly.access.polly.access.A.load.load = load i32*, i32** %polly.access.polly.access.A.load
+;
+; CHECK: polly.stmt.bb2:
+; CHECK:   %p_tmp6 = getelementptr inbounds i32, i32* %polly.access.polly.access.A.load.load, i64 %polly.indvar
+; CHECK:   store i32 0, i32* %p_tmp6, align 4
+;
+;    void f(int ***A) {
+;      for (int i = 0; i < 1024; i++)
+;        A[42][32][i] = 0;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32*** %A) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb7, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb7 ], [ 0, %bb ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %bb2, label %bb8
+
+bb2:                                              ; preds = %bb1
+  %tmp = getelementptr inbounds i32**, i32*** %A, i64 42
+  %tmp3 = load i32**, i32*** %tmp, align 8
+  %tmp4 = getelementptr inbounds i32*, i32** %tmp3, i64 32
+  %tmp5 = load i32*, i32** %tmp4, align 8
+  %tmp6 = getelementptr inbounds i32, i32* %tmp5, i64 %indvars.iv
+  store i32 0, i32* %tmp6, align 4
+  br label %bb7
+
+bb7:                                              ; preds = %bb2
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb8:                                              ; preds = %bb1
+  ret void
+}

test/Isl/CodeGen/invariant_load_scalar_dep.ll

+; RUN: opt %loadPolly -polly-no-early-exit -polly-codegen -polly-ignore-aliasing -polly-detect-unprofitable -S < %s | FileCheck %s
+;
+; CHECK-LABEL: polly.preload.begin:
+; CHECK:    %polly.access.B = getelementptr i32, i32* %B, i64 0
+; CHECK:    %polly.access.B.load = load i32, i32* %polly.access.B
+;
+; CHECK-LABEL: polly.stmt.bb2.split:
+; CHECK:    %scevgep = getelementptr i32, i32* %A, i64 %polly.indvar
+; CHECK:    store i32 %polly.access.B.load, i32* %scevgep, align 4
+;
+;    void f(int *restrict A, int *restrict B) {
+;      for (int i = 0; i < 1024; i++)
+;        auto tmp = *B;
+;        // Split BB
+;        A[i] = tmp;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* noalias %A, i32* noalias %B) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb4, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb4 ], [ 0, %bb ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %bb2, label %bb5
+
+bb2:                                              ; preds = %bb1
+  %tmp = load i32, i32* %B, align 4
+  br label %bb2.split
+
+bb2.split:
+  %tmp3 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 %tmp, i32* %tmp3, align 4
+  br label %bb4
+
+bb4:                                              ; preds = %bb2
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb5:                                              ; preds = %bb1
+  ret void
+}

test/Isl/CodeGen/reduction_2.ll

 
 if.end:                                           ; preds = %if.then, %for.end
   %retval.0 = phi i32 [ 1, %if.then ], [ 0, %for.end ] ; <i32> [#uses=1]
   ret i32 %retval.0
 }
 
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind
 
-; CHECK: for (int c0 = 0; c0 <= 1018; c0 += 1)
-; CHECK:   Stmt_for_body(c0);
+; Negative test. At the moment we will optimistically assume RED[0] in the conditional after the
+; loop might be invariant and expand the SCoP from the loop to include the conditional. However,
+; during SCoP generation we will realize that RED[0] is in fact not invariant and bail.
+;
+; Possible solutions could be:
+;   - Do not optimistically assume it to be invariant (as before this commit), however we would loose
+;     a lot of invariant cases due to possible aliasing.
+;   - Reduce the size of the SCoP if an assumed invariant access is in fact not invariant instead of
+;     rejecting the whole region.
+;
+; CHECK-NOT: for (int c0 = 0; c0 <= 1018; c0 += 1)
+; CHECK-NOT:   Stmt_for_body(c0);

test/Isl/CodeGen/whole-scop-non-affine-subregion.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit \
 ; RUN: -polly-codegen -S < %s | FileCheck %s
 
 ; CHECK: polly.start
-
+;    int /* pure */ g()
 ;    void f(int *A) {
-;      if (*A > 42)
+;      if (g())
 ;        *A = *A + 1;
 ;      else
 ;        *A = *A - 1;
 ;    }
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(i32* %A) {
 entry:
   br label %entry.split
 
 entry.split:
-  %tmp = load i32, i32* %A, align 4
-  %cmp = icmp sgt i32 %tmp, 42
+  %call = call i32 @g()
+  %cmp = icmp eq i32 %call, 0
   br i1 %cmp, label %if.then, label %if.else
 
 if.then:                                          ; preds = %entry
   %tmp1 = load i32, i32* %A, align 4
   %add = add nsw i32 %tmp1, 1
+  store i32 %add, i32* %A, align 4
   br label %if.end
 
 if.else:                                          ; preds = %entry
   %tmp2 = load i32, i32* %A, align 4
   %sub = add nsw i32 %tmp2, -1
+  store i32 %sub, i32* %A, align 4
   br label %if.end
 
 if.end:                                           ; preds = %if.else, %if.then
-  %storemerge = phi i32 [ %sub, %if.else ], [ %add, %if.then ]
-  store i32 %storemerge, i32* %A, align 4
   ret void
 }
+
+declare i32 @g() #0
+
+attributes #0 = { nounwind readnone }

test/ScopDetect/base_pointer.ll

then:
   br label %return
 
 return:
   fence seq_cst
   ret void
 }
 
 ; CHECK-LABEL: base_pointer_in_condition
-; CHECK: Valid Region for Scop: for.i => then
+; CHECK: Valid Region for Scop: pre => return
 
 define void @base_pointer_is_argument(float* %A, i64 %n) {
 entry:
   br label %for.i
 
 for.i:
   %indvar.i = phi i64 [ %indvar.i.next, %for.i.inc ], [ 0, %entry ]
   br label %S1
for.i.inc:
   %exitcond.i = icmp ne i64 %indvar.i.next, %n
   br i1 %exitcond.i, label %for.i, label %exit
 
 exit:
   ret void
 }
 
 ; CHECK: base_pointer_is_ptr2ptr
-; CHECK-NOT: Valid Region for Scop
+; CHECK: Valid Region for Scop: for.j => for.i.inc

test/ScopDetectionDiagnostics/ReportLoopBound-01.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-allow-nonaffine-loops=false -polly-detect -analyze < %s 2>&1| FileCheck %s --check-prefix=REJECTNONAFFINELOOPS
 ; RUN: opt %loadPolly -polly-detect-unprofitable -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-allow-nonaffine-loops=true -polly-detect -analyze < %s 2>&1| FileCheck %s --check-prefix=ALLOWNONAFFINELOOPS
 ; RUN: opt %loadPolly -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-allow-nonaffine-loops=true -polly-allow-nonaffine -polly-detect -analyze < %s 2>&1| FileCheck %s --check-prefix=ALLOWNONAFFINEALL
 
 ; void f(int A[], int n) {
-;   for (int i = 0; i < A[n]; i++)
+;   for (int i = 0; i < A[n+i]; i++)
 ;     A[i] = 0;
 ; }
 
 ; If we reject non-affine loops the non-affine loop bound will be reported:
 ;
 ; REJECTNONAFFINELOOPS: remark: ReportLoopBound-01.c:2:8: The following errors keep this region from being a Scop.
 ; REJECTNONAFFINELOOPS: remark: ReportLoopBound-01.c:2:8: Failed to derive an affine function from the loop bounds.
 ; REJECTNONAFFINELOOPS: remark: ReportLoopBound-01.c:3:5: Invalid Scop candidate ends here.

 
 for.body:                                         ; preds = %for.body.lr.ph, %for.body
   %indvar = phi i64 [ 0, %for.body.lr.ph ], [ %indvar.next, %for.body ]
   %arrayidx2 = getelementptr i32, i32* %A, i64 %indvar, !dbg !24
   %1 = add i64 %indvar, 1, !dbg !24
   %inc = trunc i64 %1 to i32, !dbg !21
   store i32 0, i32* %arrayidx2, align 4, !dbg !24
   tail call void @llvm.dbg.value(metadata !{null}, i64 0, metadata !18, metadata !DIExpression()), !dbg !20
-  %2 = load i32, i32* %arrayidx, align 4, !dbg !21
+  %arrayidx3 = getelementptr inbounds i32, i32* %arrayidx, i64 %indvar, !dbg !21
+  %2 = load i32, i32* %arrayidx3, align 4, !dbg !21
   %cmp = icmp slt i32 %inc, %2, !dbg !21
   %indvar.next = add i64 %indvar, 1, !dbg !21
   br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge, !dbg !21
 
 for.cond.for.end_crit_edge:                       ; preds = %for.body
   br label %for.end, !dbg !25
 
 for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry.split

test/ScopDetectionDiagnostics/ReportVariantBasePtr-01.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -analyze < %s 2>&1| FileCheck %s
 
 ; struct b {
 ;   double **b;
 ; };
 ;
 ; void a(struct b *A) {
 ;   for (int i=0; i<32; i++)
-;     A->b[i] = 0;
+;     A[i].b[i] = 0;
 ; }
 
 ; CHECK: remark: ReportVariantBasePtr01.c:6:8: The following errors keep this region from being a Scop.
 ; CHECK: remark: ReportVariantBasePtr01.c:7:5: The base address of this array is not invariant inside the loop
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 %struct.b = type { double** }
 
 define void @a(%struct.b* nocapture readonly %A) #0 {
 entry:
   br label %entry.split
 
 entry.split:                                      ; preds = %entry
   tail call void @llvm.dbg.value(metadata %struct.b* %A, i64 0, metadata !16, metadata !DIExpression()), !dbg !23
   tail call void @llvm.dbg.value(metadata i32 0, i64 0, metadata !17, metadata !DIExpression()), !dbg !25
-  %b = getelementptr inbounds %struct.b, %struct.b* %A, i64 0, i32 0, !dbg !26
   br label %for.body, !dbg !27
 
 for.body:                                         ; preds = %for.body, %entry.split
   %indvar4 = phi i64 [ %indvar.next, %for.body ], [ 0, %entry.split ]
+  %b = getelementptr inbounds %struct.b, %struct.b* %A, i64 %indvar4, i32 0, !dbg !26
   %0 = mul i64 %indvar4, 4, !dbg !26
   %1 = add i64 %0, 3, !dbg !26
   %2 = add i64 %0, 2, !dbg !26
   %3 = add i64 %0, 1, !dbg !26
   %4 = load double**, double*** %b, align 8, !dbg !26, !tbaa !28
   %arrayidx = getelementptr double*, double** %4, i64 %0, !dbg !26
   store double* null, double** %arrayidx, align 8, !dbg !26, !tbaa !33
   %5 = load double**, double*** %b, align 8, !dbg !26, !tbaa !28

test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_1.ll

 ; SCALAR:            MayWriteAccess := [Reduction Type: +] [Scalar: 0]
 ; SCALAR:                { Stmt_bb3__TO__bb11[i0] -> MemRef_A[o0] : o0 <= 2147483645 and o0 >= -2147483648 };
 ; SCALAR:    }
 
 ;
 ;    void f(int * restrict A, int * restrict C) {
 ;      int j;
 ;      for (int i = 0; i < 1024; i++) {
-;        while ((j = C[i]))
+;        while ((j = C[i++])) {
 ;          A[j]++;
+;          if (true) break;
+;        }
 ;      }
 ;    }
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(i32* noalias %A, i32* noalias %C) {
 bb:
   br label %bb1
bb3:                                              ; preds = %bb6, %bb2
   br i1 %tmp5, label %bb11, label %bb6
 
 bb6:                                              ; preds = %bb3
   %tmp7 = sext i32 %tmp4 to i64
   %tmp8 = getelementptr inbounds i32, i32* %A, i64 %tmp7
   %tmp9 = load i32, i32* %tmp8, align 4
   %tmp10 = add nsw i32 %tmp9, 1
   store i32 %tmp10, i32* %tmp8, align 4
-  br label %bb3
+  br i1 true, label %bb11, label %bb3
 
 bb11:                                             ; preds = %bb3
   br label %bb12
 
 bb12:                                             ; preds = %bb11
   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
   br label %bb1
 
 bb13:                                             ; preds = %bb1
   ret void
 }

test/ScopInfo/NonAffine/non_affine_conditional_surrounding_affine_loop.ll

 ; RUN: opt %loadPolly -polly-scops -polly-allow-nonaffine-branches \
 ; RUN:     -polly-allow-nonaffine-loops=true -polly-detect-unprofitable \
 ; RUN:     -analyze < %s | FileCheck %s --check-prefix=INNERMOST
 ; RUN: opt %loadPolly -polly-scops -polly-allow-nonaffine \
 ; RUN:     -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true \
 ; RUN:     -polly-detect-unprofitable -analyze < %s | FileCheck %s \
 ; RUN:     --check-prefix=ALL
 ;
-; INNERMOST:    Function: f
-; INNERMOST:    Region: %bb9---%bb17
-; INNERMOST:    Max Loop Depth:  1
-; INNERMOST:    Context:
-; INNERMOST:    [N] -> {  :
-; INNERMOST-DAG:          N >= -2147483648
-; INNERMOST-DAG:       and
-; INNERMOST-DAG:          N <= 2147483647
-; INNERMOST            }
-; INNERMOST:    Assumed Context:
-; INNERMOST:    [N] -> {  :  }
-; INNERMOST:    p0: %N
-; INNERMOST:    Alias Groups (0):
-; INNERMOST:        n/a
-; INNERMOST:    Statements {
-; INNERMOST:      Stmt_bb11
-; INNERMOST:            Domain :=
-; INNERMOST:                [N] -> { Stmt_bb11[i0] :
-; INNERMOST-DAG:                i0 >= 0
-; INNERMOST-DAG:              and
-; INNERMOST-DAG:                i0 <= -1 + N
-; INNERMOST:                  }
-; INNERMOST:            Schedule :=
-; INNERMOST:                [N] -> { Stmt_bb11[i0] -> [i0] };
-; INNERMOST:            ReadAccess := [Reduction Type: +] [Scalar: 0]
-; INNERMOST:                [N] -> { Stmt_bb11[i0] -> MemRef_A[i0] };
-; INNERMOST:            MustWriteAccess :=  [Reduction Type: +] [Scalar: 0]
-; INNERMOST:                [N] -> { Stmt_bb11[i0] -> MemRef_A[i0] };
-; INNERMOST:    }
+; Negative test for INNERMOST.
+; At the moment we will optimistically assume A[i] in the conditional before the inner
+; loop might be invariant and expand the SCoP from the loop to include the conditional. However,
+; during SCoP generation we will realize that A[i] is in fact not invariant (in this region = the body
+; of the outer loop) and bail.
+;
+; Possible solutions could be:
+;   - Do not optimistically assume it to be invariant (as before this commit), however we would loose
+;     a lot of invariant cases due to possible aliasing.
+;   - Reduce the size of the SCoP if an assumed invariant access is in fact not invariant instead of
+;     rejecting the whole region.
+;
+; INNERMOST-NOT:    Function: f
 ;
 ; ALL:    Function: f
 ; ALL:    Region: %bb3---%bb19
 ; ALL:    Max Loop Depth:  1
 ; ALL:    Context:
 ; ALL:    {  :  }
 ; ALL:    Assumed Context:
 ; ALL:    {  :  }

test/ScopInfo/NonAffine/non_affine_conditional_surrounding_non_affine_loop.ll

 ; RUN: opt %loadPolly -polly-scops -polly-allow-nonaffine-branches \
 ; RUN:     -polly-allow-nonaffine-loops=true -polly-detect-unprofitable \
 ; RUN:     -analyze < %s | FileCheck %s --check-prefix=INNERMOST
 ; RUN: opt %loadPolly -polly-scops -polly-allow-nonaffine \
 ; RUN:     -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true \
 ; RUN:     -analyze < %s | FileCheck %s --check-prefix=ALL
 ;
-; INNERMOST:    Function: f
-; INNERMOST:    Region: %bb9---%bb18
-; INNERMOST:    Max Loop Depth:  1
-; INNERMOST:    Context:
-; INNERMOST:    [p_0] -> {  :
-; INNERMOST-DAG:   p_0 >= -2199023255552
-; INNERMOST-DAG:    and 
-; INNERMOST-DAG:   p_0 <= 2199023254528
-; INNERMOST:             }
-; INNERMOST:    Assumed Context:
-; INNERMOST:    [p_0] -> {  :  }
-; INNERMOST:    p0: {0,+,(sext i32 %N to i64)}<%bb3>
-; INNERMOST:    Alias Groups (0):
-; INNERMOST:        n/a
-; INNERMOST:    Statements {
-; INNERMOST:      Stmt_bb12
-; INNERMOST:            Domain :=
-; INNERMOST:                [p_0] -> { Stmt_bb12[i0] :
-; INNERMOST-DAG:                i0 >= 0
-; INNERMOST-DAG:              and
-; INNERMOST-DAG:                i0 <= -1 + p_0
-; INNERMOST:                  }
-; INNERMOST:            Schedule :=
-; INNERMOST:                [p_0] -> { Stmt_bb12[i0] -> [i0] };
-; INNERMOST:            ReadAccess := [Reduction Type: +] [Scalar: 0]
-; INNERMOST:                [p_0] -> { Stmt_bb12[i0] -> MemRef_A[i0] };
-; INNERMOST:            MustWriteAccess :=  [Reduction Type: +] [Scalar: 0]
-; INNERMOST:                [p_0] -> { Stmt_bb12[i0] -> MemRef_A[i0] };
-; INNERMOST:    }
+; Negative test for INNERMOST.
+; At the moment we will optimistically assume A[i] in the conditional before the inner
+; loop might be invariant and expand the SCoP from the loop to include the conditional. However,
+; during SCoP generation we will realize that A[i] is in fact not invariant (in this region = the body
+; of the outer loop) and bail.
+;
+; Possible solutions could be:
+;   - Do not optimistically assume it to be invariant (as before this commit), however we would loose
+;     a lot of invariant cases due to possible aliasing.
+;   - Reduce the size of the SCoP if an assumed invariant access is in fact not invariant instead of
+;     rejecting the whole region.
+;
+; INNERMOST-NOT:    Function: f
 ;
 ; ALL:    Function: f
 ; ALL:    Region: %bb3---%bb20
 ; ALL:    Max Loop Depth:  1
 ; ALL:    Context:
 ; ALL:    {  :  }
 ; ALL:    Assumed Context:
 ; ALL:    {  :  }

test/ScopInfo/intra_and_inter_bb_scalar_dep.ll

 ;   }
 ; }
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
 
 ; CHECK:       Invariant Accesses: {
 ; CHECK:           ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:              MemRef_init_ptr[0]
-; CHECK:           ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
-; CHECK:              MemRef_init_ptr[0]
+; CHECK-NOT:       ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NOT:          MemRef_init_ptr[0]
 ; CHECK:       }
 define void @f(i64* noalias %A, i64 %N, i64* noalias %init_ptr) #0 {
 entry:
   br label %for.i
 
 for.i:                                            ; preds = %for.i.end, %entry
   %indvar.i = phi i64 [ 0, %entry ], [ %indvar.i.next, %for.i.end ]
   %indvar.i.next = add nsw i64 %indvar.i, 1

test/ScopInfo/invariant_load_base_pointer.ll

+; RUN: opt %loadPolly -polly-scops -polly-ignore-aliasing -polly-detect-unprofitable -analyze < %s | FileCheck %s
+;
+; CHECK: Invariant Accesses:
+; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:   { Stmt_bb2[i0] -> MemRef_BPLoc[0] };
+;
+;    void f(int **BPLoc) {
+;      for (int i = 0; i < 1024; i++)
+;        (*BPLoc)[i] = 0;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32** %BPLoc) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb4, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb4 ], [ 0, %bb ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %bb2, label %bb5
+
+bb2:                                              ; preds = %bb1
+  %tmp = load i32*, i32** %BPLoc, align 8
+  %tmp3 = getelementptr inbounds i32, i32* %tmp, i64 %indvars.iv
+  store i32 0, i32* %tmp3, align 4
+  br label %bb4
+
+bb4:                                              ; preds = %bb2
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb5:                                              ; preds = %bb1
+  ret void
+}

test/ScopInfo/invariant_load_base_pointer_conditional.ll

+; RUN: opt %loadPolly -polly-scops -polly-ignore-aliasing -polly-detect-unprofitable -analyze < %s | FileCheck %s
+;
+; CHECK: Invariant Accesses:
+; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:   [N] -> { Stmt_bb5[i0] -> MemRef_BPLoc[0] };
+;
+;    void f(int **BPLoc, int *A, int N) {
+;      for (int i = 0; i < N; i++)
+;        if (i > 512)
+;          (*BPLoc)[i] = 0;
+;        else
+;          A[i] = 0;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32** %BPLoc, i32* %A, i32 %N) {
+bb:
+  %tmp = sext i32 %N to i64
+  br label %bb1
+
+bb1:                                              ; preds = %bb11, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb11 ], [ 0, %bb ]
+  %tmp2 = icmp slt i64 %indvars.iv, %tmp
+  br i1 %tmp2, label %bb3, label %bb12
+
+bb3:                                              ; preds = %bb1
+  %tmp4 = icmp sgt i64 %indvars.iv, 512
+  br i1 %tmp4, label %bb5, label %bb8
+
+bb5:                                              ; preds = %bb3
+  %tmp6 = load i32*, i32** %BPLoc, align 8
+  %tmp7 = getelementptr inbounds i32, i32* %tmp6, i64 %indvars.iv
+  store i32 0, i32* %tmp7, align 4
+  br label %bb10
+
+bb8:                                              ; preds = %bb3
+  %tmp9 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 0, i32* %tmp9, align 4
+  br label %bb10
+
+bb10:                                             ; preds = %bb8, %bb5
+  br label %bb11
+
+bb11:                                             ; preds = %bb10
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb12:                                             ; preds = %bb1
+  ret void
+}

test/ScopInfo/invariant_load_condition.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s
+;
+; CHECK: Invariant Accesses:
+; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:  { Stmt_bb2[i0] -> MemRef_C[0] };
+;
+;    void f(int *A, int *C) {
+;      for (int i = 0; i < 1024; i++)
+;        if (*C)
+;          A[i] = 0;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32* %C) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb7, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb7 ], [ 0, %bb ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %bb2, label %bb8
+
+bb2:                                              ; preds = %bb1
+  %tmp = load i32, i32* %C, align 4
+  %tmp3 = icmp eq i32 %tmp, 0
+  br i1 %tmp3, label %bb6, label %bb4
+
+bb4:                                              ; preds = %bb2
+  %tmp5 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 0, i32* %tmp5, align 4
+  br label %bb6
+
+bb6:                                              ; preds = %bb2, %bb4
+  br label %bb7
+
+bb7:                                              ; preds = %bb6
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb8:                                              ; preds = %bb1
+  ret void
+}

test/ScopInfo/invariant_load_loop_ub.ll

+; RUN: opt %loadPolly -polly-scops -polly-detect-unprofitable -analyze < %s | FileCheck %s
+;
+; CHECK: Invariant Accesses:
+; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:   { Stmt_bb1[i0] -> MemRef_UB[0] };
+;
+;    void f(int *A, int *UB) {
+;      for (int i = 0; i < *UB; i++)
+;        A[i] = 0;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32* %UB) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb6, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb6 ], [ 0, %bb ]
+  %tmp = load i32, i32* %UB, align 4
+  %tmp2 = sext i32 %tmp to i64
+  %tmp3 = icmp slt i64 %indvars.iv, %tmp2
+  br i1 %tmp3, label %bb4, label %bb7
+
+bb4:                                              ; preds = %bb1
+  %tmp5 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 0, i32* %tmp5, align 4
+  br label %bb6
+
+bb6:                                              ; preds = %bb4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb7:                                              ; preds = %bb1
+  ret void
+}

test/ScopInfo/invariant_load_ptr_ptr_noalias.ll

 ; RUN: opt %loadPolly -tbaa -polly-scops -polly-ignore-aliasing \
 ; RUN:                -polly-detect-unprofitable -analyze < %s | FileCheck %s
 ;
+; Note: The order of the invariant accesses is important!
+;
+; CHECK: Invariant Accesses: {
+; CHECK:    ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:         MemRef_A[42]
+; CHECK:    ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:         MemRef_tmp3[32]
+; CHECK: }
+;
 ; CHECK: Arrays {
 ; CHECK:   i32** MemRef_A[*][8]
 ; CHECK:   i32* MemRef_tmp3[*][8] [BasePtrOrigin: MemRef_A]
 ; CHECK:   i32 MemRef_tmp5[*][4] [BasePtrOrigin: MemRef_tmp3]
 ; CHECK: }
 ;
 ; CHECK: Arrays (Bounds as pw_affs) {
 ; CHECK:   i32** MemRef_A[*][ { [] -> [(8)] } ]

 
 bb1:                                              ; preds = %bb7, %bb
   %indvars.iv = phi i64 [ %indvars.iv.next, %bb7 ], [ 0, %bb ]
   %exitcond = icmp ne i64 %indvars.iv, 1024
   br i1 %exitcond, label %bb2, label %bb8
 
 bb2:                                              ; preds = %bb1
   %tmp = getelementptr inbounds i32**, i32*** %A, i64 42
-  %tmp3 = load i32**, i32*** %tmp, align 8, !tbaa !1
+  %tmp3 = load i32**, i32*** %tmp, align 8
   %tmp4 = getelementptr inbounds i32*, i32** %tmp3, i64 32
-  %tmp5 = load i32*, i32** %tmp4, align 8, !tbaa !1
+  %tmp5 = load i32*, i32** %tmp4, align 8
   %tmp6 = getelementptr inbounds i32, i32* %tmp5, i64 %indvars.iv
-  store i32 0, i32* %tmp6, align 4, !tbaa !5
+  store i32 0, i32* %tmp6, align 4
   br label %bb7
 
 bb7:                                              ; preds = %bb2
   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
   br label %bb1
 
 bb8:                                              ; preds = %bb1
   ret void
 }
-
-!0 = !{!"clang version 3.8.0 (http://llvm.org/git/clang.git 9e282ff441e7a367dc711e41fd19d27ffc0f78d6)"}
-!1 = !{!2, !2, i64 0}
-!2 = !{!"any pointer", !3, i64 0}
-!3 = !{!"omnipotent char", !4, i64 0}
-!4 = !{!"Simple C/C++ TBAA"}
-!5 = !{!6, !6, i64 0}
-!6 = !{!"int", !3, i64 0}

test/ScopInfo/invariant_load_scalar_dep.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s
+;
+; CHECK: Invariant Accesses:
+; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:   { Stmt_bb2[i0] -> MemRef_B[0] };
+; CHECK-NOT:  MustWriteAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NOT:   { Stmt_bb2[i0] -> MemRef_tmp[] };
+;
+;    void f(int *restrict A, int *restrict B) {
+;      for (int i = 0; i < 1024; i++)
+;        auto tmp = *B;
+;        // Split BB
+;        A[i] = tmp;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* noalias %A, i32* noalias %B) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb4, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb4 ], [ 0, %bb ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %bb2, label %bb5
+
+bb2:                                              ; preds = %bb1
+  %tmp = load i32, i32* %B, align 4
+  br label %bb2b
+
+bb2b:
+  %tmp3 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 %tmp, i32* %tmp3, align 4
+  br label %bb4
+
+bb4:                                              ; preds = %bb2
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb1
+
+bb5:                                              ; preds = %bb1
+  ret void
+}

test/ScopInfo/invariant_loads_complicated_dependences.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; CHECK:         Invariant Accesses: {
+; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [tmp, tmp5] -> { Stmt_for_body[i0] -> MemRef_LB[0] };
+; CHECK-NEXT:            Execution Context: [tmp, tmp5] -> {  :  }
+; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [tmp, tmp5] -> { Stmt_do_cond[i0, i1] -> MemRef_UB[0] };
+; CHECK-NEXT:            Execution Context: [tmp, tmp5] -> {  :  }
+; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [tmp, tmp5] -> { Stmt_if_else[i0, i1] -> MemRef_U[0] };
+; CHECK-NEXT:            Execution Context: [tmp, tmp5] -> {  : tmp <= 5 }
+; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [tmp, tmp5] -> { Stmt_if_then[i0, i1] -> MemRef_V[0] };
+; CHECK-NEXT:            Execution Context: [tmp, tmp5] -> {  : (tmp5 >= 1 + tmp and tmp5 >= 6) or tmp >= 6 }
+; CHECK-NEXT:    }
+;
+;    void f(int *restrict A, int *restrict V, int *restrict U, int *restrict UB,
+;           int *restrict LB) {
+;      for (int i = 0; i < 100; i++) {
+;        int j = /* invariant load */ *LB;
+;        do {
+;          if (j > 5)
+;            A[i] += /* invariant load */ *V;
+;          else
+;            A[i] += /* invariant load */ *U;
+;        } while (j++ < /* invariant load */ *UB);
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* noalias %A, i32* noalias %V, i32* noalias %U, i32* noalias %UB, i32* noalias %LB) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 100
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp = load i32, i32* %LB, align 4
+  br label %do.body
+
+do.body:                                          ; preds = %do.cond, %for.body
+  %j.0 = phi i32 [ %tmp, %for.body ], [ %inc, %do.cond ]
+  %cmp1 = icmp sgt i32 %j.0, 5
+  br i1 %cmp1, label %if.then, label %if.else
+
+if.then:                                          ; preds = %do.body
+  %tmp1 = load i32, i32* %V, align 4
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp2 = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp2, %tmp1
+  store i32 %add, i32* %arrayidx, align 4
+  br label %if.end
+
+if.else:                                          ; preds = %do.body
+  %tmp3 = load i32, i32* %U, align 4
+  %arrayidx3 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp4 = load i32, i32* %arrayidx3, align 4
+  %add4 = add nsw i32 %tmp4, %tmp3
+  store i32 %add4, i32* %arrayidx3, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  br label %do.cond
+
+do.cond:                                          ; preds = %if.end
+  %inc = add nsw i32 %j.0, 1
+  %tmp5 = load i32, i32* %UB, align 4
+  %cmp5 = icmp slt i32 %j.0, %tmp5
+  br i1 %cmp5, label %do.body, label %do.end
+
+do.end:                                           ; preds = %do.cond
+  br label %for.inc
+
+for.inc:                                          ; preds = %do.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopInfo/invariant_loads_cyclic_dependences.ll

+; RUN: opt %loadPolly -analyze -polly-scops < %s | FileCheck %s
+;
+; Negative test. If we assume UB[*V] to be invariant we get a cyclic
+; dependence in the invariant loads that needs to be resolved by
+; ignoring the actual accessed address and focusing on the fact
+; that the access happened. However, at the moment we assume UB[*V]
+; not to be loop invariant, thus reject this region.
+;
+; CHECK-NOT: Statements
+;
+;
+;    void f(int *restrict V, int *restrict UB, int *restrict A) {
+;      for (int i = 0; i < 100; i++) {
+;        int j = 0;
+;        int x = 0;
+;        do {
+;          x = /* invariant load dependent on UB[*V] */ *V;
+;          A[j + i]++;
+;        } while (j++ < /* invariant load dependent on *V */ UB[x]);
+;      }
+;    }
+;
+target datalayout = "e-m:e-i32:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* noalias %V, i32* noalias %UB, i32* noalias %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv2 = phi i32 [ %indvars.iv.next3, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i32 %indvars.iv2, 100
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  br label %do.body
+
+do.body:                                          ; preds = %do.cond, %for.body
+  %indvars.iv = phi i32 [ %indvars.iv.next, %do.cond ], [ 0, %for.body ]
+  %tmp = load i32, i32* %V, align 4
+  %tmp4 = add nuw nsw i32 %indvars.iv, %indvars.iv2
+  %arrayidx = getelementptr inbounds i32, i32* %A, i32 %tmp4
+  %tmp5 = load i32, i32* %arrayidx, align 4
+  %inc = add nsw i32 %tmp5, 1
+  store i32 %inc, i32* %arrayidx, align 4
+  br label %do.cond
+
+do.cond:                                          ; preds = %do.body
+  %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
+  %arrayidx3 = getelementptr inbounds i32, i32* %UB, i32 %tmp
+  %tmp6 = load i32, i32* %arrayidx3, align 4
+  %cmp4 = icmp slt i32 %indvars.iv, %tmp6
+  br i1 %cmp4, label %do.body, label %do.end
+
+do.end:                                           ; preds = %do.cond
+  br label %for.inc
+
+for.inc:                                          ; preds = %do.end
+  %indvars.iv.next3 = add nuw nsw i32 %indvars.iv2, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopInfo/invariant_loop_bounds.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; CHECK:      Invariant Accesses: {
+; CHECK-NEXT:         ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             MemRef_bounds[2]
+; CHECK-NEXT: Execution Context: [tmp, tmp8, tmp10] -> {  : }
+; CHECK-NEXT:         ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             MemRef_bounds[1]
+; CHECK-NEXT: Execution Context: [tmp, tmp8, tmp10] -> {  : tmp >= 1 }
+; CHECK-NEXT:         ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             MemRef_bounds[0]
+; CHECK-NEXT: Execution Context: [tmp, tmp8, tmp10] -> {  : tmp8 >= 1 and tmp >= 1 }
+; CHECK-NEXT: }
+;
+; CHECK:    p0: %tmp
+; CHECK:    p1: %tmp8
+; CHECK:    p2: %tmp10
+; CHECK:    Statements {
+; CHECK:      Stmt_for_body_6
+; CHECK:            Domain :=
+; CHECK:                [tmp, tmp8, tmp10] -> { Stmt_for_body_6[i0, i1, i2] : i0 >= 0 and i0 <= -1 + tmp and i1 >= 0 and i1 <= -1 + tmp8 and i2 >= 0 and i2 <= -1 + tmp10 };
+; CHECK:            Schedule :=
+; CHECK:                [tmp, tmp8, tmp10] -> { Stmt_for_body_6[i0, i1, i2] -> [i0, i1, i2] };
+; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                [tmp, tmp8, tmp10] -> { Stmt_for_body_6[i0, i1, i2] -> MemRef_data[i0, i1, i2] };
+; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                [tmp, tmp8, tmp10] -> { Stmt_for_body_6[i0, i1, i2] -> MemRef_data[i0, i1, i2] };
+; CHECK:    }
+;
+;    int bounds[3];
+;    double data[1024][1024][1024];
+;
+;    void foo() {
+;      int i, j, k;
+;      for (k = 0; k < bounds[2]; k++)
+;        for (j = 0; j < bounds[1]; j++)
+;          for (i = 0; i < bounds[0]; i++)
+;            data[k][j][i] += i + j + k;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+@bounds = common global [3 x i32] zeroinitializer, align 4
+@data = common global [1024 x [1024 x [1024 x double]]] zeroinitializer, align 16
+
+define void @foo() {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc.16, %entry
+  %indvars.iv5 = phi i64 [ %indvars.iv.next6, %for.inc.16 ], [ 0, %entry ]
+  %tmp = load i32, i32* getelementptr inbounds ([3 x i32], [3 x i32]* @bounds, i64 0, i64 2), align 4
+  %tmp7 = sext i32 %tmp to i64
+  %cmp = icmp slt i64 %indvars.iv5, %tmp7
+  br i1 %cmp, label %for.body, label %for.end.18
+
+for.body:                                         ; preds = %for.cond
+  br label %for.cond.1
+
+for.cond.1:                                       ; preds = %for.inc.13, %for.body
+  %indvars.iv3 = phi i64 [ %indvars.iv.next4, %for.inc.13 ], [ 0, %for.body ]
+  %tmp8 = load i32, i32* getelementptr inbounds ([3 x i32], [3 x i32]* @bounds, i64 0, i64 1), align 4
+  %tmp9 = sext i32 %tmp8 to i64
+  %cmp2 = icmp slt i64 %indvars.iv3, %tmp9
+  br i1 %cmp2, label %for.body.3, label %for.end.15
+
+for.body.3:                                       ; preds = %for.cond.1
+  br label %for.cond.4
+
+for.cond.4:                                       ; preds = %for.inc, %for.body.3
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %for.body.3 ]
+  %tmp10 = load i32, i32* getelementptr inbounds ([3 x i32], [3 x i32]* @bounds, i64 0, i64 0), align 4
+  %tmp11 = sext i32 %tmp10 to i64
+  %cmp5 = icmp slt i64 %indvars.iv, %tmp11
+  br i1 %cmp5, label %for.body.6, label %for.end
+
+for.body.6:                                       ; preds = %for.cond.4
+  %tmp12 = add nsw i64 %indvars.iv, %indvars.iv3
+  %tmp13 = add nsw i64 %tmp12, %indvars.iv5
+  %tmp14 = trunc i64 %tmp13 to i32
+  %conv = sitofp i32 %tmp14 to double
+  %arrayidx11 = getelementptr inbounds [1024 x [1024 x [1024 x double]]], [1024 x [1024 x [1024 x double]]]* @data, i64 0, i64 %indvars.iv5, i64 %indvars.iv3, i64 %indvars.iv
+  %tmp15 = load double, double* %arrayidx11, align 8
+  %add12 = fadd double %tmp15, %conv
+  store double %add12, double* %arrayidx11, align 8
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body.6
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond.4
+
+for.end:                                          ; preds = %for.cond.4
+  br label %for.inc.13
+
+for.inc.13:                                       ; preds = %for.end
+  %indvars.iv.next4 = add nuw nsw i64 %indvars.iv3, 1
+  br label %for.cond.1
+
+for.end.15:                                       ; preds = %for.cond.1
+  br label %for.inc.16
+
+for.inc.16:                                       ; preds = %for.end.15
+  %indvars.iv.next6 = add nuw nsw i64 %indvars.iv5, 1
+  br label %for.cond
+
+for.end.18:                                       ; preds = %for.cond
+  ret void
+}

test/ScopInfo/invariant_same_loop_bound_multiple_times-1.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; Verify that we only have one parameter and one invariant load for all
+; three loads that occure in the region but actually access the same
+; location. Also check that the execution context is the most generic
+; one, e.g., here the universal set.
+;
+; CHECK:      Invariant Accesses: {
+; CHECK-NEXT:         ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             MemRef_bounds[0]
+; CHECK-NEXT:         Execution Context: [tmp] -> {  :  }
+; CHECK-NEXT: }
+;
+; CHECK:      p0: %tmp
+; CHECK-NOT:  p1
+; CHECK:      Statements {
+; CHECK:        Stmt_for_body_6
+; CHECK:              Domain :=
+; CHECK:                  [tmp] -> { Stmt_for_body_6[i0, i1, i2] : i0 >= 0 and i0 <= -1 + tmp and i1 >= 0 and i1 <= -1 + tmp and i2 >= 0 and i2 <= -1 + tmp };
+; CHECK:              Schedule :=
+; CHECK:                  [tmp] -> { Stmt_for_body_6[i0, i1, i2] -> [i0, i1, i2] };
+; CHECK:              ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                  [tmp] -> { Stmt_for_body_6[i0, i1, i2] -> MemRef_data[i0, i1, i2] };
+; CHECK:              MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                  [tmp] -> { Stmt_for_body_6[i0, i1, i2] -> MemRef_data[i0, i1, i2] };
+; CHECK:      }
+;
+;    int bounds[1];
+;    double data[1024][1024][1024];
+;
+;    void foo() {
+;      int i, j, k;
+;      for (k = 0; k < bounds[0]; k++)
+;        for (j = 0; j < bounds[0]; j++)
+;          for (i = 0; i < bounds[0]; i++)
+;            data[k][j][i] += i + j + k;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+@bounds = common global [1 x i32] zeroinitializer, align 4
+@data = common global [1024 x [1024 x [1024 x double]]] zeroinitializer, align 16
+
+define void @foo() {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc.16, %entry
+  %indvars.iv5 = phi i64 [ %indvars.iv.next6, %for.inc.16 ], [ 0, %entry ]
+  %tmp = load i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @bounds, i64 0, i64 0), align 4
+  %tmp7 = sext i32 %tmp to i64
+  %cmp = icmp slt i64 %indvars.iv5, %tmp7
+  br i1 %cmp, label %for.body, label %for.end.18
+
+for.body:                                         ; preds = %for.cond
+  br label %for.cond.1
+
+for.cond.1:                                       ; preds = %for.inc.13, %for.body
+  %indvars.iv3 = phi i64 [ %indvars.iv.next4, %for.inc.13 ], [ 0, %for.body ]
+  %tmp8 = load i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @bounds, i64 0, i64 0), align 4
+  %tmp9 = sext i32 %tmp8 to i64
+  %cmp2 = icmp slt i64 %indvars.iv3, %tmp9
+  br i1 %cmp2, label %for.body.3, label %for.end.15
+
+for.body.3:                                       ; preds = %for.cond.1
+  br label %for.cond.4
+
+for.cond.4:                                       ; preds = %for.inc, %for.body.3
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %for.body.3 ]
+  %tmp10 = load i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @bounds, i64 0, i64 0), align 4
+  %tmp11 = sext i32 %tmp10 to i64
+  %cmp5 = icmp slt i64 %indvars.iv, %tmp11
+  br i1 %cmp5, label %for.body.6, label %for.end
+
+for.body.6:                                       ; preds = %for.cond.4
+  %tmp12 = add nsw i64 %indvars.iv, %indvars.iv3
+  %tmp13 = add nsw i64 %tmp12, %indvars.iv5
+  %tmp14 = trunc i64 %tmp13 to i32
+  %conv = sitofp i32 %tmp14 to double
+  %arrayidx11 = getelementptr inbounds [1024 x [1024 x [1024 x double]]], [1024 x [1024 x [1024 x double]]]* @data, i64 0, i64 %indvars.iv5, i64 %indvars.iv3, i64 %indvars.iv
+  %tmp15 = load double, double* %arrayidx11, align 8
+  %add12 = fadd double %tmp15, %conv
+  store double %add12, double* %arrayidx11, align 8
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body.6
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond.4
+
+for.end:                                          ; preds = %for.cond.4
+  br label %for.inc.13
+
+for.inc.13:                                       ; preds = %for.end
+  %indvars.iv.next4 = add nuw nsw i64 %indvars.iv3, 1
+  br label %for.cond.1
+
+for.end.15:                                       ; preds = %for.cond.1
+  br label %for.inc.16
+
+for.inc.16:                                       ; preds = %for.end.15
+  %indvars.iv.next6 = add nuw nsw i64 %indvars.iv5, 1
+  br label %for.cond
+
+for.end.18:                                       ; preds = %for.cond
+  ret void
+}

test/ScopInfo/invariant_same_loop_bound_multiple_times-2.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; Verify that we only have one parameter and one invariant load for all
+; three loads that occure in the region but actually access the same
+; location. Also check that the execution context is the most generic
+; one, e.g., here the universal set.
+;
+; CHECK:      Invariant Accesses: {
+; CHECK-NEXT:         ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             MemRef_bounds[0]
+; CHECK-NEXT:         Execution Context: [tmp, p] -> {  :  }
+; CHECK-NEXT: }
+;
+; CHECK:      p0: %tmp
+; CHECK:      p1: %p
+; CHECK-NOT:  p2:
+; CHECK:      Statements {
+; CHECK:        Stmt_for_body_6
+; CHECK:              Domain :=
+; CHECK:                  [tmp, p] -> { Stmt_for_body_6[i0, i1, i2] : p = 0 and i0 >= 0 and i0 <= -1 + tmp and i1 >= 0 and i1 <= -1 + tmp and i2 >= 0 and i2 <= -1 + tmp };
+; CHECK:              Schedule :=
+; CHECK:                  [tmp, p] -> { Stmt_for_body_6[i0, i1, i2] -> [i0, i1, i2] };
+; CHECK:              ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                  [tmp, p] -> { Stmt_for_body_6[i0, i1, i2] -> MemRef_data[i0, i1, i2] };
+; CHECK:              MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:                  [tmp, p] -> { Stmt_for_body_6[i0, i1, i2] -> MemRef_data[i0, i1, i2] };
+; CHECK:      }
+;
+;    int bounds[1];
+;    double data[1024][1024][1024];
+;
+;    void foo(int p) {
+;      int i, j, k;
+;      for (k = 0; k < bounds[0]; k++)
+;        if (p == 0)
+;          for (j = 0; j < bounds[0]; j++)
+;            for (i = 0; i < bounds[0]; i++)
+;              data[k][j][i] += i + j + k;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+@bounds = common global [1 x i32] zeroinitializer, align 4
+@data = common global [1024 x [1024 x [1024 x double]]] zeroinitializer, align 16
+
+define void @foo(i32 %p) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc.16, %entry
+  %indvars.iv5 = phi i64 [ %indvars.iv.next6, %for.inc.16 ], [ 0, %entry ]
+  %tmp = load i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @bounds, i64 0, i64 0), align 4
+  %tmp7 = sext i32 %tmp to i64
+  %cmp = icmp slt i64 %indvars.iv5, %tmp7
+  br i1 %cmp, label %for.body, label %for.end.18
+
+for.body:                                         ; preds = %for.cond
+  %cmpp = icmp eq i32 %p, 0
+  br i1 %cmpp, label %for.cond.1, label %for.inc.16
+
+for.cond.1:                                       ; preds = %for.inc.13, %for.body
+  %indvars.iv3 = phi i64 [ %indvars.iv.next4, %for.inc.13 ], [ 0, %for.body ]
+  %tmp8 = load i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @bounds, i64 0, i64 0), align 4
+  %tmp9 = sext i32 %tmp8 to i64
+  %cmp2 = icmp slt i64 %indvars.iv3, %tmp9
+  br i1 %cmp2, label %for.body.3, label %for.end.15
+
+for.body.3:                                       ; preds = %for.cond.1
+  br label %for.cond.4
+
+for.cond.4:                                       ; preds = %for.inc, %for.body.3
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %for.body.3 ]
+  %tmp10 = load i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @bounds, i64 0, i64 0), align 4
+  %tmp11 = sext i32 %tmp10 to i64
+  %cmp5 = icmp slt i64 %indvars.iv, %tmp11
+  br i1 %cmp5, label %for.body.6, label %for.end
+
+for.body.6:                                       ; preds = %for.cond.4
+  %tmp12 = add nsw i64 %indvars.iv, %indvars.iv3
+  %tmp13 = add nsw i64 %tmp12, %indvars.iv5
+  %tmp14 = trunc i64 %tmp13 to i32
+  %conv = sitofp i32 %tmp14 to double
+  %arrayidx11 = getelementptr inbounds [1024 x [1024 x [1024 x double]]], [1024 x [1024 x [1024 x double]]]* @data, i64 0, i64 %indvars.iv5, i64 %indvars.iv3, i64 %indvars.iv
+  %tmp15 = load double, double* %arrayidx11, align 8
+  %add12 = fadd double %tmp15, %conv
+  store double %add12, double* %arrayidx11, align 8
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body.6
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond.4
+
+for.end:                                          ; preds = %for.cond.4
+  br label %for.inc.13
+
+for.inc.13:                                       ; preds = %for.end
+  %indvars.iv.next4 = add nuw nsw i64 %indvars.iv3, 1
+  br label %for.cond.1
+
+for.end.15:                                       ; preds = %for.cond.1
+  br label %for.inc.16
+
+for.inc.16:                                       ; preds = %for.end.15
+  %indvars.iv.next6 = add nuw nsw i64 %indvars.iv5, 1
+  br label %for.cond
+
+for.end.18:                                       ; preds = %for.cond
+  ret void
+}

test/ScopInfo/required-invariant-loop-bounds.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; CHECK:      Invariant Accesses: {
+; CHECK-NEXT:       ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:         MemRef_bounds[0]
+; CHECK-NEXT: Execution Context: [tmp, tmp1] -> {  :  }
+; CHECK-NEXT:       ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:         MemRef_bounds[1]
+; CHECK-NEXT: Execution Context: [tmp, tmp1] -> {  : tmp >= 0 }
+; CHECK:      }
+
+;    double A[1000][1000];
+;    long bounds[2];
+;
+;    void foo() {
+;
+;      for (long i = 0; i <= bounds[0]; i++)
+;        for (long j = 0; j <= bounds[1]; j++)
+;          A[i][j] += i + j;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+@bounds = common global [2 x i64] zeroinitializer, align 16
+@A = common global [1000 x [1000 x double]] zeroinitializer, align 16
+
+define void @foo() {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc.6, %entry
+  %i.0 = phi i64 [ 0, %entry ], [ %inc7, %for.inc.6 ]
+  %tmp = load i64, i64* getelementptr inbounds ([2 x i64], [2 x i64]* @bounds, i64 0, i64 0), align 16
+  %cmp = icmp sgt i64 %i.0, %tmp
+  br i1 %cmp, label %for.end.8, label %for.body
+
+for.body:                                         ; preds = %for.cond
+  br label %for.cond.1
+
+for.cond.1:                                       ; preds = %for.inc, %for.body
+  %j.0 = phi i64 [ 0, %for.body ], [ %inc, %for.inc ]
+  %tmp1 = load i64, i64* getelementptr inbounds ([2 x i64], [2 x i64]* @bounds, i64 0, i64 1), align 8
+  %cmp2 = icmp sgt i64 %j.0, %tmp1
+  br i1 %cmp2, label %for.end, label %for.body.3
+
+for.body.3:                                       ; preds = %for.cond.1
+  %add = add nsw i64 %i.0, %j.0
+  %conv = sitofp i64 %add to double
+  %arrayidx4 = getelementptr inbounds [1000 x [1000 x double]], [1000 x [1000 x double]]* @A, i64 0, i64 %i.0, i64 %j.0
+  %tmp2 = load double, double* %arrayidx4, align 8
+  %add5 = fadd double %tmp2, %conv
+  store double %add5, double* %arrayidx4, align 8
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body.3
+  %inc = add nuw nsw i64 %j.0, 1
+  br label %for.cond.1
+
+for.end:                                          ; preds = %for.cond.1
+  br label %for.inc.6
+
+for.inc.6:                                        ; preds = %for.end
+  %inc7 = add nuw nsw i64 %i.0, 1
+  br label %for.cond
+
+for.end.8:                                        ; preds = %for.cond
+  ret void
+}