[Polly] De-LICM and De-GVN (WIP)

[Meinersbur]

Summary

Undo the effects of LICM on loop dependencies. This is done by mapping the scalars such as those that are created by LICM and GVN-PRE back to the array elements they were promoted from.

Exec time results (with -polly-position=before-vectorizer)

3mm -71.63%
2mm -71.56%
gemm -71.03%
syrk -44.84%
doitgen -43.18%
syr2k -42.73%
mvt -28.57%
gemver -26.32%
gramschmidt -12.71%

bmm 2.03%
CrystalMk 3.14%
FloatMM 4.35%
cholesky 73.39%
trmm 226.78%

Do not try to apply this patch directly. It requires some other patches to make this patch smaller and that I am going to commit/upload independently. Get the latest from my Github branch.

[Meinersbur]

Current status:
Works fine on the licm_reduction.ll test case, but has one redundant MustWriteAccess which already has been there before.
None of the other tests or code generation has been worked on yet.
Currently only code for the case that the value is written back to the array. Hoisting of reads must be handled with additional code.
There are many operations based on DenseSets of edges, but I I don't know how to check lifetime overlaps more efficiently.

[Meinersbur]

WIP update:

Implemented CodeGeneration part and inter alia.

"De-LICM" tries to map emulated scalar to an array element that is not used because it will be overwritten unconditionally (no-use zone). BBs will read and write to this mapped location instead of space from a dedicated Alloca. Array element locations are represented using the StoreInst that writes to this. For this reason De-LICM of LoadInst-only zones are currently unsupported.

BBs are modeled s.t. the array elements are loaded into scalars before its instructions and written back after them if the value is modified. This is to avoid to track live values within basic blocks. Live values are tracked between BBs. Two scalars conflict (cannot be mapped to the same array element) if they would write different scalars at the end of the block. The algorithm is greedy, i.e. values that are first encountered to not conflict with any other previously mapped lifetimes are used.

Afterwards memory accesses are created unless they are identified to be redundant. Reads are created on-the-fly while mapped writes are added at the end. As a result, explicit LoadInst/StoreInst in the BB may have no corresponding MemoryAccess.

Dirty code-disclaimer: auto declarations, unused variables, outcommented or dead code, implementations in header file, incomplete merge with r247928 (Multi-dimensional accesses with bitcasts), ignored options, 64 failed unit tests (of which 3 are crashes), etc to be corrected.

Some changes could be committed separately:

• There is a map that stores whether there is already a MemoryAccess for a given scalar to avoid adding redundant accesses.
• Explicit MemoryAccess types (AccessOrigin in the code): Explicit (from LoadInst/StoreInst), Scalar (.s2a) and PHI (.phiops)
• Dedicated addMemoryAccess-equivalents for each of the types.

Intended but not yet implemented:

• Have separate lists of MemoryAccesses for leading reloads and trailing stores of scalars. Would restore the 1-to-1 relationship of instructions and explicit MemoryAccesses.
• Remove printing of former TempScopInfo's IRAccesses and change the test cases to check of output of scop->dump() instead.

[Meinersbur]

Mostly rebase to D13762

[Meinersbur]

Pass unit tests

[grosser]

Hi Michael,

I wonder what the current status of this patch is. As your patch has probably evolved a lot since this original submission, it would be great if you could push an updated version for people to have a look and to provide feedback on how to merge this code or algorithm best.

Best,
Tobias

[Meinersbur]

Update, based on r251962

[Meinersbur]

Rebase to r254343

[Meinersbur]

Rebase; Fix all LNT tests except llvm.org/PR26718

This is not yet a clean patch.

TODOs:

• Change analysis/transformation to work with exiting MemoryAccesses (instead of modifying their creation) in order to benefit from changes in D13611.
• Per-edge MemoryAccesses required for many tests cases to work properly. D15722 might be useful.
• Add systematic unit tests

[etherzhhb]

Can we put the algorithm to a ScopPass or another cpp file?

include/polly/CodeGen/BlockGenerators.h

134–136

Comments to explain what is going on here? (because the dirty code-disclaimer?)

362

Also talk about @param NewAccesses? (because the dirty code-disclaimer?)

381

Here too

496–499

Comments to explain what is the different between this one and the above one?

isl_id_to_ast_expr *NewAccesses should be an __isl_keep?

826

@param NewAccesses

include/polly/ScopInfo.h

74

The MemAccInst here can only be StoreInst?

110

will the same statement map to multiple values?

2295

It would be good to put explanation for the difference between Inst and AddrAlias.

2348

Stored at the location indicated by @param Addr?

2399

Can we move this to a ScopPass? Or move the algorithm implementation to another cpp file?

lib/Analysis/ScopInfo.cpp

3839

[Unrelated to this patch] Can we put a early return here to reduce the indent levels?

if (!(isa<GetElementPtrInst>(Address) || isa<BitCastInst>(Address)))
  return nullptr;

...

[Meinersbur]

Thanks for your first look.

In D12975#362672, @etherzhhb wrote:

Can we put the algorithm to a ScopPass or another cpp file?

Explained inline.

include/polly/CodeGen/BlockGenerators.h

362

Before the code is stable enough I don't bother to keep docs up-to-date that don't explain anything new.

Generally I think, we should not propagate such values by arguments through a lot of calls. The doxygen comments get very repetitive. Passing using as class member would be better. If the value is only available a limited time (here: during copyStmt), we could create a class that is valid during this period.

include/polly/ScopInfo.h

74

Kind of.

Yes in contexts of mapping targets. Altough it is only the result of the implementation in greedyCollapse that only StoreInsts are chosen.

No in context where we check if a LoadInst would read the same value, either to see that the value is still used, or whether the LoadInst would be redundant.

110

No for OutgoingValueMapTy. There is a OutgoingValueMapTy per mapping location and only one value can be mapped to that location at a Stamt's exit.

2348

Yes.

2399

I already suggested this for invariant load hoisting, but I don't remember what Johannes' answer was.

It does not make sense for the algorithm in this implementation. We'd need to split ScopInfo into two parts: before and MemoryAccess creation. A ScopInfo is not useful for outsiders without its MemoryAccesses.

It may become feasible when I move the implementation that modifies exiting MemoryAccesses. If we want such a split of passes, we should also split: Invariant load hoisting, D13611, and this.

[etherzhhb]

I need to read this again tomorrow

include/polly/CodeGen/BlockGenerators.h

public:
   /// If no alloca was mapped for @p Access a new one is created.
   ///
   /// @param Access    The memory access for which to generate the alloca
   ///
   /// @returns The alloca for @p Access or a replacement value taken from
   ///          GlobalMap.
   Value *getOrCreateAlloca(const MemoryAccess &Access);
 
+  Value *getImplicitAddress(MemoryAccess &Access, Loop *L, LoopToScevMapT &LTS,
+                            ValueMapT &BBMap,
+                            __isl_keep isl_id_to_ast_expr *NewAccesses);
+
   /// @brief Return the alloca for @p Array
   ///
   /// If no alloca was mapped for @p Array a new one is created.
   ///
   /// @param Array The array for which to generate the alloca
   ///
   /// @returns The alloca for @p Array or a replacement value taken from
   ///          GlobalMap.
protected:
   ///
   /// @returns The alloca for @p ScalarBase.
   Value *getOrCreateAlloca(Value *ScalarBase, ScalarAllocaMapTy &Map,
                            const char *NameExt);
 
   /// @brief Generate reload of scalars demoted to memory and needed by @p Stmt.
   ///
   /// @param Stmt  The statement we generate code for.
   /// @param BBMap A mapping from old values to their new values in this block.
-  void generateScalarLoads(ScopStmt &Stmt, ValueMapT &BBMap);
+  void generateScalarLoads(ScopStmt &Stmt, LoopToScevMapT &LTS,
+                           ValueMapT &BBMap,
+                           __isl_keep isl_id_to_ast_expr *NewAccesses);
 
   /// @brief Generate the scalar stores for the given statement.
   ///
   /// After the statement @p Stmt was copied all inner-SCoP scalar dependences
   /// starting in @p Stmt (hence all scalar write accesses in @p Stmt) need to
   /// be demoted to memory.
   ///
   /// @param Stmt  The statement we generate code for.
   /// @param LTS   A mapping from loops virtual canonical induction
   ///              variable to their new values
   ///              (for values recalculated in the new ScoP, but not
   ///               within this basic block)
   /// @param BBMap A mapping from old values to their new values in this block.
   virtual void generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
-                                    ValueMapT &BBMap);
+                                    ValueMapT &BBMap,
+                                    __isl_keep isl_id_to_ast_expr *NewAccesses);
 
   /// @brief Handle users of @p Inst outside the SCoP.
   ///
   /// @param R         The current SCoP region.
   /// @param Inst      The current instruction we check.
   /// @param Address   If given it is used as the escape address for @p Inst.
   void handleOutsideUsers(const Region &R, Instruction *Inst,
                           Value *Address = nullptr);
Value *getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap,
                      LoopToScevMapT &LTS, Loop *L) const;
 
   void copyInstScalar(ScopStmt &Stmt, Instruction *Inst, ValueMapT &BBMap,
                       LoopToScevMapT &LTS);
 
   /// @brief Get the innermost loop that surrounds the statement @p Stmt.
   Loop *getLoopForStmt(const ScopStmt &Stmt) const;
 
+  Loop *getLoopForStmt(ScopStmt &Stmt);
+
   /// @brief Generate the operand address
   /// @param NewAccesses A map from memory access ids to new ast expressions,
   ///                    which may contain new access expressions for certain
   ///                    memory accesses.
   Value *generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst,
                                   ValueMapT &BBMap, LoopToScevMapT &LTS,
                                   isl_id_to_ast_expr *NewAccesses);
 
+  Value *generateLocationAccessed(ScopStmt &Stmt, Loop *L, Value *Pointer,
+                                  ValueMapT &BBMap, LoopToScevMapT &LTS,
+                                  isl_id_to_ast_expr *NewAccesses,
+                                  __isl_take isl_id *Id, Type *ExpectedType);
+
   /// @param NewAccesses A map from memory access ids to new ast expressions,
   ///                    which may contain new access expressions for certain
   ///                    memory accesses.
   Value *generateScalarLoad(ScopStmt &Stmt, LoadInst *load, ValueMapT &BBMap,
                             LoopToScevMapT &LTS,
                             isl_id_to_ast_expr *NewAccesses);
 
   /// @param NewAccesses A map from memory access ids to new ast expressions,
private:
   /// starting in @p Stmt (hence all scalar write accesses in @p Stmt) need to
   /// be demoted to memory.
   ///
   /// @param Stmt  The statement we generate code for.
   /// @param LTS   A mapping from loops virtual canonical induction variable to
   ///              their new values (for values recalculated in the new ScoP,
   ///              but not within this basic block)
   /// @param BBMap A mapping from old values to their new values in this block.
-  virtual void generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
-                                    ValueMapT &BBMAp) override;
+  virtual void
+  generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMAp,
+                       __isl_keep isl_id_to_ast_expr *NewAccesses) override;
 
   /// @brief Copy a single PHI instruction.
   ///
   /// This copies a single PHI instruction and updates references to old values
   /// with references to new values, as defined by GlobalMap and BBMap.
   ///
   /// @param Stmt      The statement to code generate.
   /// @param PHI       The PHI instruction to copy.

include/polly/ScopInfo.h

 
 namespace polly {
 
 class MemoryAccess;
 class Scop;
 class ScopStmt;
 class ScopInfo;
 
+/// @brief Values of this type identify an array element.
+///
+/// To identify an array element at runtime, we need a SCEV that can be expanded
+/// to the desired location an Loop context in which that expanded value is the
+/// same. Eg. in the next loop iteration its value be different.
+///
+/// A MemAccInst gives us both: the SCEV by asking ScalarEvolution on its
+/// PointerArgument, and a Loop using LoopInfo::getLoopFor().
+/// ScopInfo::buildMemoryAccess() can create the MemoryAccess for that specific
+/// element when passing that MemAccInst.
+///
+/// Alternative implementations could use tuples of llvm::Value/Instruction,
+/// SCEV/Loop, or the MemoryAccess members that buildMemoryAccess() computes.
+/// All of these would require more changes.
+///
+/// The DeLICM algorithm always begins at a StoreInst to look for viable
+/// locations, hence an AddrAlias will always be a StoreInst. MemAccInst as
+/// alias types appear when explicit LoadInsts are checked whether they load the
+/// same value.
+///
+/// As an extension we could also allow exiting scalars as mapping targts. This
+/// would reduce the number of scalar MemoryAccesses, but not improve
+/// schedulability because the scalar access would remain scalar.
+typedef StoreInst *AddrAliasTy;
+
+/// @brief Lists of expected values when leaving a statements.
+///
+/// For each ScopStmt*, defines an value that an array element (defined by an
+/// AddrAliasTy) should have when execution of that statements has terminated.
+///
+/// There are 3 possible contents:
+///
+/// Undefined (.count() returns false): We don't know what is stored and it
+/// might used later. Don't try to overwrite or read it.
+///
+/// Free (stmt maps to nullptr): whatever is currently stored, will be
+/// overwritted before it is read. We can store other temporary values at this
+/// location until that write.
+///
+/// Defined (stmt maps to an llvm::Value): Either the value is known (eg.
+/// because it has been written to that element) or the DeLICM algorithm decided
+/// to store that value there temporally there until it is overwritten.
 typedef DenseMap<ScopStmt *, Value *> OutgoingValueMapTy;
 
 //===---------------------------------------------------------------------===//
 
 /// @brief Enumeration of assumptions Polly can take.
 enum AssumptionKind {
   ALIASING,
   INBOUNDS,
   WRAPPING,
private:
   ///
   ///    => { S[i] -> A[i]; S[i] -> A[o] : 4i <= o <= 4i + 3 }
   isl_map *AccessRelation;
 
   /// @brief Updated access relation read from JSCOP file.
   isl_map *NewAccessRelation;
   // @}
 
+  // For Mapped locations
+  // @{
+  // Take the memory access information from here
+  MemAccInst MappedAliasAddr;
+  // @}
+
   bool isAffine() const { return IsAffine; }
 
   __isl_give isl_basic_map *createBasicAccessMap(ScopStmt *Statement);
 
   void assumeNoOutOfBound();
 
   /// @brief Compute bounds on an over approximated  access relation.
   ///
public:
   /// @param Kind       The kind of memory accessed.
   /// @param Subscripts Subscipt expressions
   /// @param Sizes      Dimension lengths of the accessed array.
   /// @param BaseName   Name of the acessed array.
   MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst, AccessType AccType,
                Value *BaseAddress, Type *ElemType, bool Affine,
                ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
                Value *AccessValue, ScopArrayInfo::MemoryKind Kind,
-               StringRef BaseName);
+               StringRef BaseName, MemAccInst MappedAliasAddr);
   ~MemoryAccess();
 
   /// @brief Add a new incoming block/value pairs for this PHI/ExitPHI access.
   ///
   /// @param IncomingBlock The PHI's incoming block.
   /// @param IncomingValue The value when reacing the PHI from the @p
   ///                      IncomingBlock.
   void addIncoming(BasicBlock *IncomingBlock, Value *IncomingValue) {
     assert(!isRead());
-    assert(isAnyPHIKind());
+    assert(isAnyPHIKind() || isMapped());
     Incoming.emplace_back(std::make_pair(IncomingBlock, IncomingValue));
   }
 
   /// @brief Return the list of possible PHI/ExitPHI values.
   ///
   /// After code generation moves some PHIs around during region simplification,
   /// we cannot reliably locate the original PHI node and its incoming values
   /// anymore. For this reason we remember these explicitely for all PHI-kind
   /// accesses.
   ArrayRef<std::pair<BasicBlock *, Value *>> getIncoming() const {
-    assert(isAnyPHIKind());
     return Incoming;
   }
 
   /// @brief Get the type of a memory access.
   enum AccessType getType() { return AccType; }
 
   /// @brief Is this a reduction like access?
   bool isReductionLike() const { return RedType != RT_NONE; }
public:
   bool isStrideOne(__isl_take const isl_map *Schedule) const;
 
   /// Is always the same memory accessed for a given statement instance set?
   /// Schedule is a map from the statement to a schedule where the innermost
   /// dimension is the dimension of the innermost loop containing the
   /// statement.
   bool isStrideZero(__isl_take const isl_map *Schedule) const;
 
+  bool isMapped() const { return MappedAliasAddr; }
+
+  MemAccInst getMappedAliasAddr() const {
+    assert(isMapped());
+    return MappedAliasAddr;
+  }
+
+  Value *getEffectiveAddr() const {
+    return (isMapped() ? getMappedAliasAddr()
+                       : MemAccInst::cast(getAccessInstruction()))
+        .getPointerOperand();
+  }
+
   /// @brief Whether this is an access of an explicit load or store in the IR.
   bool isArrayKind() const { return Kind == ScopArrayInfo::MK_Array; }
 
   /// @brief Whether this access is an array to a scalar memory object.
   ///
   /// Scalar accesses are accesses to MK_Value, MK_PHI or MK_ExitPHI.
   bool isScalarKind() const { return !isArrayKind(); }
 
class ScopInfo : public RegionPass {
   ///        the Load/Store instruction.
   ///
   /// @param Stmt    The statment to add the MemoryAccess into.
   /// @param BB      The block where the access takes place.
   /// @param Inst    Instruction that requires the access.
   /// @param Val     Value being read/written.
   /// @param isLoad  Whether the value is being loaded or stored.
   /// @param Addr    To determine the array element accessed.
-  /// @returns True if the access could be built, False otherwise.
-  bool buildAccessMultiDimFixed(ScopStmt *Stmt, BasicBlock *BB,
-                                Instruction *Inst, Value *Val, bool isLoad,
-                                MemAccInst Addr);
+  /// @returns       The created MemoryAccess, or nullptr if it could not be
+  ///                created.
+  MemoryAccess *buildAccessMultiDimFixed(ScopStmt *Stmt, BasicBlock *BB,
+                                         Instruction *Inst, Value *Val,
+                                         bool isLoad, MemAccInst Addr);
 
   /// @brief Try to build a multi-dimensional parameteric sized MemoryAccess
   ///        from the Load/Store instruction.
   ///
   /// @param Stmt    The statment to add the MemoryAccess into.
   /// @param BB      The block where the access takes place.
   /// @param Inst    Instruction that requires the access.
   /// @param Val     Value being read/written.
   /// @param isLoad  Whether the value is being loaded or stored.
   /// @param Addr    To determine the array element accessed.
-  /// @returns True if the access could be built, False otherwise.
-  /// @returns True if the access could be built, False otherwise.
-  bool buildAccessMultiDimParam(ScopStmt *Stmt, BasicBlock *BB,
+  /// @returns       The created MemoryAccess, or nullptr if it could not be
+  ///                created.
+  MemoryAccess *buildAccessMultiDimParam(ScopStmt *Stmt, BasicBlock *BB,
                                          Instruction *Inst, Value *ValueOperand,
                                          bool isLoad, MemAccInst Addr);
 
   /// @brief Try to build a MemoryAccess for a memory intrinsic.
   ///
   /// @param Stmt       The statment to add the MemoryAccess into.
   /// @param BB         The block where the access takes place.
   /// @param Inst       The instruction that access the memory
   ///
   /// @returns True if the access could be built, False otherwise.
   bool buildAccessMemIntrinsic(ScopStmt *Stmt, BasicBlock *BB, MemAccInst Inst);
 
   /// @brief Build a single-dimensional parameteric sized MemoryAccess
   ///        from the Load/Store instruction.
   ///
   /// @param Stmt    The statment to add the MemoryAccess into.
   /// @param BB      The block where the access takes place.
   /// @param Inst    Instruction that requires the access.
   /// @param Val     Value being read/written.
   /// @param isLoad  Whether the value is being loaded or stored.
   /// @param Addr    To determine the array element accessed.
-  void buildAccessSingleDim(ScopStmt *Stmt, BasicBlock *BB, Instruction *Inst,
-                            Value *Val, bool isLoad, MemAccInst Addr);
+  /// @returns       The created MemoryAccess.
+  MemoryAccess *buildAccessSingleDim(ScopStmt *Stmt, BasicBlock *BB,
+                                     Instruction *Inst, Value *Val, bool isLoad,
+                                     MemAccInst Addr);
 
-  /// @brief Build an instance of MemoryAccess from the Load/Store instruction.
+  /// @brief Build an instance of MemoryAccess that accesses an array (either
+  /// explicitly using a LoadInst/StoreInst or from a mapped scalar)
   ///
   /// @param Stmt       The statment to add the MemoryAccess into.
   /// @param BB         The block where the access takes place.
   /// @param Inst       The Load/Store instruction that accesses the memory.
   void buildMemoryAccess(ScopStmt *Stmt, BasicBlock *BB, MemAccInst Inst);
 
   /// @brief Build a MemoryAccess that accesses the array element specified by
   /// @p Addr.
   ///
   /// @param Stmt    The statment to add the MemoryAccess into.
   /// @param BB      The block where the access takes place.
   /// @param Inst    Instruction that requires the access.
   /// @param Val     Value being read/written.
   /// @param isLoad  Whether the value is being loaded or stored.
   /// @param Addr    To determine the array element accessed.
-  void buildMemoryAccessWithAlias(ScopStmt *Stmt, BasicBlock *BB,
-                                  Instruction *Inst, Value *Val, bool isLoad,
-                                  MemAccInst Addr);
+  /// @returns       The created MemoryAccess, or nullptr if it could not be
+  ///                created.
+  MemoryAccess *buildMemoryAccessWithAlias(ScopStmt *Stmt, BasicBlock *BB,
+                                           Instruction *Inst, Value *Val,
+                                           bool isLoad, MemAccInst Addr);
+
+  Value *extractBasePointer(Value *Addr, Loop *L);
+
+  const ScopArrayInfo *getOrCreateSAI(MemAccInst SI);
 
   /// @brief Analyze and extract the cross-BB scalar dependences (or,
   ///        dataflow dependencies) of an instruction.
   ///
   /// @param Inst    The instruction to be analyzed.
   void buildScalarDependences(Instruction *Inst);
 
   /// @brief Search for uses of the llvm::Value defined by @p Inst that are not
class ScopInfo : public RegionPass {
   ///
   /// @return The created MemoryAccess, or nullptr if the access is not within
   ///         the SCoP.
   MemoryAccess *
   addMemoryAccess(ScopStmt *Stmt, BasicBlock *BB, Instruction *Inst,
                   MemoryAccess::AccessType Type, Value *BaseAddress,
                   llvm::Type *ElemType, bool Affine, Value *AccessValue,
                   ArrayRef<const SCEV *> Subscripts,
-                  ArrayRef<const SCEV *> Sizes, ScopArrayInfo::MemoryKind Kind);
+                  ArrayRef<const SCEV *> Sizes, ScopArrayInfo::MemoryKind Kind,
+                  MemAccInst AddrAlias);
 
   /// @brief Create a MemoryAccess for writing an llvm::Instruction.
   ///
   /// The access will be created at the position of @p Inst.
   ///
   /// @param Inst The instruction to be written.
   ///
   /// @see ensureValueRead()
class ScopInfo : public RegionPass {
   ///
   /// @param PHI PHINode under consideration; the READ access will be added
   /// here.
   ///
   /// @see ensurePHIWrite()
   /// @see ScopArrayInfo::MemoryKind
   void addPHIReadAccess(PHINode *PHI);
 
+  // isRedundantXYZ determine whether we do not need to execute
+  // a load because its value is not used in the current statement -or-
+  // a store because the value is already stored at the location.
+
+  bool isRedundantScalarRead(AddrAliasTy Addr, Instruction *Val, ScopStmt *Stmt,
+                             bool isExplicit = false);
+  bool isRedundantScalarWrite(AddrAliasTy Addr, Value *Val, ScopStmt *Stmt,
+                              bool isExplicit = false);
+  bool isRedundantScalarWriteOfAlias(AddrAliasTy Addr, Instruction *ValInst,
+                                     ScopStmt *Stmt, bool isExplicit,
+                                     MemAccInst Alias);
+
+  bool isRedundantMemAcc(MemAccInst AccInst);
+  bool isRedundantLoad(LoadInst *LI);
+  bool isRedundantStore(StoreInst *SI);
+
+  DenseMap<Instruction *, AddrAliasTy> CollapseValue;
+  DenseMap<PHINode *, AddrAliasTy> CollapsePHI;
+  DenseMap<AddrAliasTy, OutgoingValueMapTy> OutgoingCollapsedValue;
+
+  /// @brief Return the temporary storage location of an Instruction.
+  ///
+  /// Returning nullptr means it will be stored in its dedicated .s2a or .phiops
+  /// alloca.
+  ///
+  /// The Stmt is required to get the context. Inside the stmt a value can be
+  /// directly accesses without alloca or temporary storage. In case of PHIInst
+  /// this means to read from there the PHI is mapped to. After that statment,
+  /// we find the value where the Value is mapped to to cross statements (One
+  /// cannot always reuse the same location, it could conflict).
+  StoreInst *getMappedAlias(Instruction *Inst, ScopStmt *Stmt);
+
+  /// @brief Mapping target for llvm::Value (.s2a) demotions.
+  StoreInst *getValueMappedAddr(Instruction *Inst) {
+    auto Iter = CollapseValue.find(Inst);
+    if (Iter == CollapseValue.end())
+      return nullptr;
+    return Iter->getSecond();
+  }
+
+  /// @bried Mapping target for PHI (.phiops) demotions.
+  StoreInst *getPHIMappedAddr(PHINode *PHI) {
+    auto Iter = CollapsePHI.find(PHI);
+    if (Iter == CollapsePHI.end())
+      return nullptr;
+    return Iter->getSecond();
+  }
+
+  /// The pointer to an array element may not be computable everywhere in the
+  /// scop. For instance, it cannot be computed before the loop that defines the
+  /// induction variable used to compute the index.
+  bool isComputableAtEndingOf(Value *Val, BasicBlock *BB);
+
+  /// @brief DeLICM main algorithm.
+  ///
+  /// Tries to map scalars to array elements when those are known to be
+  /// overwritten.
+  void greedyCollapse();
+
+  /// Determine the locations before the store that won't be used before
+  /// overwritten and map scalars onto these free locations.
+  void greedyCollapseStore(AddrAliasTy Store);
+
+  /// Tag all the paths from the definition to the use in Edges with the
+  /// definition.
+  bool addDefUseEdges(OutgoingValueMapTy &Edges, Use &Use);
+
+  /// Return the set of locations that @p Val would occupy if it is mapped.
+  OutgoingValueMapTy &getLiveEdges(Instruction *Val);
+  DenseMap<Instruction *, OutgoingValueMapTy> AliveValuesCache;
+
+  /// Return the set of locations the @p PHI would occupy if it is mapped. These
+  /// are only the edges from all incoming blocks to the block containing the
+  /// PHINode.
+  DenseMap<PHINode *, OutgoingValueMapTy> PHIEdgesCache;
+  OutgoingValueMapTy &getPHIEdges(PHINode *PHI);
+
+  /// Do @p SI and @p LI describe the same location?
+  bool mustConflict(MemAccInst SI, MemAccInst LI);
+
+  /// Is it possible that the locations described by @p SI and @p LI alias?
+  bool mayConflict(MemAccInst SI, MemAccInst LI);
+
+  bool mayOverwrite(MemAccInst SI, BasicBlock *BB) {
+    return mayOverwrite(SI, BB, BB->begin(), BB->end());
+  }
+  bool mayOverwrite(MemAccInst SI, BasicBlock *BB, BasicBlock::iterator Start) {
+    return mayOverwrite(SI, BB, Start, BB->end());
+  }
+  bool mayOverwrite(MemAccInst SI, BasicBlock *BB, BasicBlock::iterator Start,
+                    BasicBlock::iterator End);
+
+  /// Determine the edges where writing a value to the array doesn't matter,
+  /// because it will be overwritten anyway.
+  /// Also add the edges where we know what value is stored in the location
+  /// described by @p SI.
+  OutgoingValueMapTy computeNoUseZones(AddrAliasTy SI);
+
 public:
   static char ID;
   explicit ScopInfo();
   ~ScopInfo();
 
   /// @brief Try to build the Polly IR of static control part on the current
   ///        SESE-Region.
   ///

lib/Analysis/ScopInfo.cpp

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopIterator.h"
+#include "llvm/Analysis/PostDominators.h" //FIXME: We currently do not preserve PostDom, i.e. do not use it
 #include "llvm/Analysis/RegionIterator.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/Support/Debug.h"
 #include "isl/aff.h"
 #include "isl/constraint.h"
 #include "isl/local_space.h"
 #include "isl/map.h"
static cl::opt<int> MaxDisjunctsAssumed(
     cl::Hidden, cl::ZeroOrMore, cl::init(150), cl::cat(PollyCategory));
 
 static cl::opt<bool> IgnoreIntegerWrapping(
     "polly-ignore-integer-wrapping",
     cl::desc("Do not build run-time checks to proof absence of integer "
              "wrapping"),
     cl::Hidden, cl::ZeroOrMore, cl::init(false), cl::cat(PollyCategory));
 
+static cl::opt<bool> ScalarCollapse(
+    "polly-scalar-collapse", cl::desc("Try mapping scalars to array elements"),
+    cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory));
+
 //===----------------------------------------------------------------------===//
 
 // Create a sequence of two schedules. Either argument may be null and is
 // interpreted as the empty schedule. Can also return null if both schedules are
 // empty.
 static __isl_give isl_schedule *
 combineInSequence(__isl_take isl_schedule *Prev,
                   __isl_take isl_schedule *Succ) {

 
 void MemoryAccess::computeBoundsOnAccessRelation(unsigned ElementSize) {
   ScalarEvolution *SE = Statement->getParent()->getSE();
 
   auto MAI = MemAccInst(getAccessInstruction());
   if (MAI.isMemIntrinsic())
     return;
 
-  Value *Ptr = MAI.getPointerOperand();
+  Value *Ptr = getEffectiveAddr();
+
   if (!Ptr || !SE->isSCEVable(Ptr->getType()))
     return;
 
   auto *PtrSCEV = SE->getSCEV(Ptr);
   if (isa<SCEVCouldNotCompute>(PtrSCEV))
     return;
 
   auto *BasePtrSCEV = SE->getPointerBase(PtrSCEV);
void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) {
   isl_space_free(Space);
 }
 
 MemoryAccess::MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst,
                            AccessType AccType, Value *BaseAddress,
                            Type *ElementType, bool Affine,
                            ArrayRef<const SCEV *> Subscripts,
                            ArrayRef<const SCEV *> Sizes, Value *AccessValue,
-                           ScopArrayInfo::MemoryKind Kind, StringRef BaseName)
+                           ScopArrayInfo::MemoryKind Kind, StringRef BaseName,
+                           MemAccInst AddrAlias)
     : Kind(Kind), AccType(AccType), RedType(RT_NONE), Statement(Stmt),
       BaseAddr(BaseAddress), BaseName(BaseName), ElementType(ElementType),
       Sizes(Sizes.begin(), Sizes.end()), AccessInstruction(AccessInst),
       AccessValue(AccessValue), IsAffine(Affine),
       Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(nullptr),
-      NewAccessRelation(nullptr) {
+      NewAccessRelation(nullptr), MappedAliasAddr(AddrAlias) {
   static const std::string TypeStrings[] = {"", "_Read", "_Write", "_MayWrite"};
   const std::string Access = TypeStrings[AccType] + utostr(Stmt->size()) + "_";
 
   std::string IdName =
       getIslCompatibleName(Stmt->getBaseName(), Access, BaseName);
   Id = isl_id_alloc(Stmt->getParent()->getIslCtx(), IdName.c_str(), this);
 }
 
void MemoryAccess::print(raw_ostream &OS) const {
   case MUST_WRITE:
     OS.indent(12) << "MustWriteAccess :=\t";
     break;
   case MAY_WRITE:
     OS.indent(12) << "MayWriteAccess :=\t";
     break;
   }
   OS << "[Reduction Type: " << getReductionType() << "] ";
-  OS << "[Scalar: " << isScalarKind() << "]\n";
+  OS << "[Scalar: " << isScalarKind() << "]";
+  if (isMapped())
+    OS << " [MAPPED]";
+  OS << "\n";
   OS.indent(16) << getOriginalAccessRelationStr() << ";\n";
   if (hasNewAccessRelation())
     OS.indent(11) << "new: " << getNewAccessRelationStr() << ";\n";
 }
 
 void MemoryAccess::dump() const { print(errs()); }
 
 // Create a map in the size of the provided set domain, that maps from the

 /// used only once (by @p StoreMA) and its load operands are also used only
 /// once, we have found a possible reduction chain. It starts at an operand
 /// load and includes the binary operator and @p StoreMA.
 ///
 /// Note: We allow only one use to ensure the load and binary operator cannot
 ///       escape this block or into any other store except @p StoreMA.
 void ScopStmt::collectCandiateReductionLoads(
     MemoryAccess *StoreMA, SmallVectorImpl<MemoryAccess *> &Loads) {
-  auto *Store = dyn_cast<StoreInst>(StoreMA->getAccessInstruction());
+  auto *Store = dyn_cast_or_null<StoreInst>(StoreMA->getAccessInstruction());
   if (!Store)
     return;
 
   // Skip if there is not one binary operator between the load and the store
   auto *BinOp = dyn_cast<BinaryOperator>(Store->getValueOperand());
   if (!BinOp)
     return;
 
for (ScopStmt &Stmt : *this) {
     // Skip statements with an empty domain as they will never be executed.
     isl_set *StmtDomain = Stmt.getDomain();
     bool StmtDomainEmpty = isl_set_is_empty(StmtDomain);
     isl_set_free(StmtDomain);
     if (StmtDomainEmpty)
       continue;
 
     for (MemoryAccess *MA : Stmt) {
-      if (MA->isScalarKind())
+      if (MA->isScalarKind() || MA->isMapped())
         continue;
       if (!MA->isRead())
         HasWriteAccess.insert(MA->getBaseAddr());
       MemAccInst Acc(MA->getAccessInstruction());
       if (MA->isRead() && Acc.isMemTransferInst())
         PtrToAcc[Acc.asMemTransferInst()->getSource()] = MA;
       else
         PtrToAcc[Acc.getPointerOperand()] = MA;
InvariantEquivClasses.emplace_back(PointerSCEV, MemoryAccessList{MA},
                                        isl_set_copy(DomainCtx), Ty);
   }
 
   isl_set_free(DomainCtx);
 }
 
 bool Scop::isHoistableAccess(MemoryAccess *Access,
                              __isl_keep isl_union_map *Writes) {
+  if (Access->isMapped())
+    return false;
+
   // 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. 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.
 
   auto &Stmt = *Access->getStatement();
   BasicBlock *BB = Stmt.getEntryBlock();
if (!R->contains(UseParent) ||
          R->getExitingBlock())) {
       // At least one escaping use found.
       ensureValueWrite(Inst);
       break;
     }
   }
 }
 
-bool ScopInfo::buildAccessMultiDimFixed(ScopStmt *Stmt, BasicBlock *BB,
+MemoryAccess *ScopInfo::buildAccessMultiDimFixed(ScopStmt *Stmt, BasicBlock *BB,
                                                  Instruction *Inst, Value *Val,
-                                        bool isLoad, MemAccInst AddrAlias) {
+                                                 bool isLoad,
+                                                 MemAccInst AddrAlias) {
   Type *ElementType = Val->getType();
   Value *Address = AddrAlias.getPointerOperand();
   Loop *L = LI->getLoopFor(BB);
   const SCEV *AccessFunction = SE->getSCEVAtScope(Address, L);
   const SCEVUnknown *BasePointer =
       dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
   enum MemoryAccess::AccessType Type =
       isLoad ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
 
   if (isa<GetElementPtrInst>(Address) || isa<BitCastInst>(Address)) {
     auto *NewAddress = Address;
     if (auto *BitCast = dyn_cast<BitCastInst>(Address)) {
       auto *Src = BitCast->getOperand(0);
       auto *SrcTy = Src->getType();
       auto *DstTy = BitCast->getType();
       if (SrcTy->getPrimitiveSizeInBits() == DstTy->getPrimitiveSizeInBits())
         NewAddress = Src;
     }
 
     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;
       Region *R = &scop->getRegion();
       const InvariantLoadsSetTy &ScopRIL = *SD->getRequiredInvariantLoads(R);
 
       for (auto *Subscript : Subscripts) {
         InvariantLoadsSetTy AccessILS;
         if (!isAffineExpr(R, Subscript, *SE, nullptr, &AccessILS))
-          return false;
+          return nullptr;
 
         for (LoadInst *LInst : AccessILS)
           if (!ScopRIL.count(LInst))
-            return false;
+            return nullptr;
       }
 
       if (Sizes.size() > 0) {
         for (auto V : Sizes)
           SizesSCEV.push_back(SE->getSCEV(ConstantInt::get(
               IntegerType::getInt64Ty(BasePtr->getContext()), V)));
 
-        addMemoryAccess(Stmt, BB, Inst, Type, BasePointer->getValue(),
+        return addMemoryAccess(Stmt, BB, Inst, Type, BasePointer->getValue(),
                                ElementType, true, Val, Subscripts, SizesSCEV,
-                        ScopArrayInfo::MK_Array);
-        return true;
+                               ScopArrayInfo::MK_Array,
+                               (Inst == AddrAlias) ? MemAccInst() : AddrAlias);
       }
     }
   }
-  return false;
+  return nullptr;
 }
 
-bool ScopInfo::buildAccessMultiDimParam(ScopStmt *Stmt, BasicBlock *BB,
+MemoryAccess *ScopInfo::buildAccessMultiDimParam(ScopStmt *Stmt, BasicBlock *BB,
                                                  Instruction *Inst, Value *Val,
-                                        bool isLoad, MemAccInst AddrAlias) {
+                                                 bool isLoad,
+                                                 MemAccInst AddrAlias) {
   Value *Address = AddrAlias.getPointerOperand();
   Type *ElementType = Val->getType();
   unsigned ElementSize = DL->getTypeAllocSize(ElementType);
   enum MemoryAccess::AccessType Type =
       isLoad ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
   Loop *L = LI->getLoopFor(BB);
   Region &R = scop->getRegion();
 
if (PollyDelinearize && AccItr != InsnToMemAcc.end()) {
     // element size used for delinearization differs the delinearization is
     // incorrect. Hence, we invalidate the scop.
     //
     // TODO: Handle delinearization with differing element sizes.
     auto DelinearizedSize =
         cast<SCEVConstant>(Sizes.back())->getAPInt().getSExtValue();
     Sizes.pop_back();
     if (ElementSize != DelinearizedSize)
-      scop->invalidate(DELINEARIZATION, Inst->getDebugLoc());
+      scop->invalidate(DELINEARIZATION,
+                       Inst ? Inst->getDebugLoc() : DebugLoc());
 
-    addMemoryAccess(Stmt, BB, Inst, Type, BasePointer->getValue(), ElementType,
-                    true, Val, AccItr->second.DelinearizedSubscripts, Sizes,
-                    ScopArrayInfo::MK_Array);
-    return true;
+    return addMemoryAccess(
+        Stmt, BB, Inst, Type, BasePointer->getValue(), ElementType, true, Val,
+        AccItr->second.DelinearizedSubscripts, Sizes, ScopArrayInfo::MK_Array,
+        (Inst == AddrAlias) ? MemAccInst() : AddrAlias);
   }
-  return false;
+  return nullptr;
 }
 
 bool ScopInfo::buildAccessMemIntrinsic(ScopStmt *Stmt, BasicBlock *BB,
                                        MemAccInst Inst) {
   if (!Inst.isMemIntrinsic())
     return false;
 
   Loop *L = LI->getLoopFor(Inst.getParent());
 
   auto *LengthVal = SE->getSCEVAtScope(Inst.asMemIntrinsic()->getLength(), L);
   assert(LengthVal);
 
   auto *DestPtrVal = Inst.asMemIntrinsic()->getDest();
   assert(DestPtrVal);
   auto *DestAccFunc = SE->getSCEVAtScope(DestPtrVal, L);
   assert(DestAccFunc);
   auto *DestPtrSCEV = dyn_cast<SCEVUnknown>(SE->getPointerBase(DestAccFunc));
   assert(DestPtrSCEV);
   DestAccFunc = SE->getMinusSCEV(DestAccFunc, DestPtrSCEV);
   addMemoryAccess(Stmt, BB, Inst, MemoryAccess::MUST_WRITE,
                   DestPtrSCEV->getValue(),
                   IntegerType::getInt8Ty(DestPtrVal->getContext()), false,
                   Inst.getValueOperand(), {DestAccFunc, LengthVal}, {},
-                  ScopArrayInfo::MK_Array);
+                  ScopArrayInfo::MK_Array, MemAccInst());
 
   if (!Inst.isMemTransferInst())
     return true;
 
   auto *SrcPtrVal = Inst.asMemTransferInst()->getSource();
   assert(SrcPtrVal);
   auto *SrcAccFunc = SE->getSCEVAtScope(SrcPtrVal, L);
   assert(SrcAccFunc);
   auto *SrcPtrSCEV = dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccFunc));
   assert(SrcPtrSCEV);
   SrcAccFunc = SE->getMinusSCEV(SrcAccFunc, SrcPtrSCEV);
   addMemoryAccess(Stmt, BB, Inst, MemoryAccess::READ, SrcPtrSCEV->getValue(),
                   IntegerType::getInt8Ty(SrcPtrVal->getContext()), false,
                   Inst.getValueOperand(), {SrcAccFunc, LengthVal}, {},
-                  ScopArrayInfo::MK_Array);
+                  ScopArrayInfo::MK_Array, MemAccInst());
 
   return true;
 }
 
-void ScopInfo::buildAccessSingleDim(ScopStmt *Stmt, BasicBlock *BB,
-                                    Instruction *Inst, Value *Val, bool isLoad,
+MemoryAccess *ScopInfo::buildAccessSingleDim(ScopStmt *Stmt, BasicBlock *BB,
+                                             Instruction *Inst, Value *Val,
+                                             bool isLoad,
                                              MemAccInst AddrAlias) {
   Value *Address = AddrAlias.getPointerOperand();
   Type *ElementType = Val->getType();
   enum MemoryAccess::AccessType Type =
       isLoad ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
   Loop *L = LI->getLoopFor(BB);
   Region *R = &scop->getRegion();
   const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD->getBoxedLoops(R);
   const InvariantLoadsSetTy &ScopRIL = *SD->getRequiredInvariantLoads(R);
MemoryAccess *ScopInfo::buildAccessSingleDim(ScopStmt *Stmt, BasicBlock *BB,
 
   for (LoadInst *LInst : AccessILS)
     if (!ScopRIL.count(LInst))
       IsAffine = false;
 
   if (!IsAffine && Type == MemoryAccess::MUST_WRITE)
     Type = MemoryAccess::MAY_WRITE;
 
-  addMemoryAccess(Stmt, BB, Inst, Type, BasePointer->getValue(), ElementType,
-                  IsAffine, Val, {AccessFunction}, {}, ScopArrayInfo::MK_Array);
+  return addMemoryAccess(Stmt, BB, Inst, Type, BasePointer->getValue(),
+                         ElementType, IsAffine, Val, {AccessFunction}, {},
+                         ScopArrayInfo::MK_Array,
+                         (Inst == AddrAlias) ? MemAccInst() : AddrAlias);
 }
 
 void ScopInfo::buildMemoryAccess(ScopStmt *Stmt, BasicBlock *BB,
                                  MemAccInst Inst) {
   if (buildAccessMemIntrinsic(Stmt, BB, Inst))
     return;
 
+  if (isRedundantMemAcc(Inst)) {
+    DEBUG(dbgs() << "Instruction" << *Inst.asInstruction()
+                 << " considered redundant\n");
+    return;
+  }
+
   buildMemoryAccessWithAlias(Stmt, BB, Inst, Inst.getValueOperand(),
                              Inst.isLoad(), Inst);
 }
 
-void ScopInfo::buildMemoryAccessWithAlias(ScopStmt *Stmt, BasicBlock *BB,
-                                          Instruction *Inst, Value *Val,
-                                          bool isLoad, MemAccInst AddrAlias) {
+MemoryAccess *ScopInfo::buildMemoryAccessWithAlias(ScopStmt *Stmt,
+                                                   BasicBlock *BB,
+                                                   Instruction *Inst,
+                                                   Value *Val, bool isLoad,
+                                                   MemAccInst AddrAlias) {
 
-  if (buildAccessMultiDimFixed(Stmt, BB, Inst, Val, isLoad, AddrAlias))
-    return;
+  if (auto MA =
+          buildAccessMultiDimFixed(Stmt, BB, Inst, Val, isLoad, AddrAlias))
+    return MA;
+
+  if (auto MA =
+          buildAccessMultiDimParam(Stmt, BB, Inst, Val, isLoad, AddrAlias))
+    return MA;
+
+  return buildAccessSingleDim(Stmt, BB, Inst, Val, isLoad, AddrAlias);
+}
+
+Value *ScopInfo::extractBasePointer(Value *Alias, Loop *L) {
+  const SCEV *AccessFunction = SE->getSCEVAtScope(Alias, L);
+  auto BP = SE->getPointerBase(AccessFunction);
+  assert((isa<SCEVUnknown>(BP) || isa<SCEVConstant>(BP)) &&
+         "Basepointers must be not computable or NULL");
+  const SCEVUnknown *BasePointer = dyn_cast<SCEVUnknown>(BP);
+  if (!BasePointer)
+    return nullptr;
+  return BasePointer->getValue();
+}
 
-  if (buildAccessMultiDimParam(Stmt, BB, Inst, Val, isLoad, AddrAlias))
-    return;
+const ScopArrayInfo *ScopInfo::getOrCreateSAI(MemAccInst SI) {
+  auto Alias = SI.getPointerOperand();
+  auto L = LI->getLoopFor(SI.getParent());
+  auto BasePtr = extractBasePointer(Alias, L);
+  if (!BasePtr)
+    return nullptr;
 
-  buildAccessSingleDim(Stmt, BB, Inst, Val, isLoad, AddrAlias);
+  return scop->getOrCreateScopArrayInfo(
+      BasePtr, Alias->getType()->getPointerElementType(), {},
+      ScopArrayInfo::MemoryKind::MK_Array);
 }
 
 void ScopInfo::buildAccessFunctions(Region &R, Region &SR) {
 
   if (SD->isNonAffineSubRegion(&SR, &R)) {
     for (BasicBlock *BB : SR.blocks())
       buildAccessFunctions(R, *BB, &SR);
     return;
if (!IsExitBlock)
       buildEscapingDependences(&Inst);
   }
 }
 
 MemoryAccess *ScopInfo::addMemoryAccess(
     ScopStmt *Stmt, BasicBlock *BB, Instruction *Inst,
     MemoryAccess::AccessType AccType, Value *BaseAddress, Type *ElementType,
     bool Affine, Value *AccessValue, ArrayRef<const SCEV *> Subscripts,
-    ArrayRef<const SCEV *> Sizes, ScopArrayInfo::MemoryKind Kind) {
+    ArrayRef<const SCEV *> Sizes, ScopArrayInfo::MemoryKind Kind,
+    MemAccInst AddrAlias) {
+
   // Do not create a memory access for anything not in the SCoP. It would be
   // ignored anyway.
   if (!Stmt)
     return nullptr;
 
   AccFuncSetType &AccList = scop->getOrCreateAccessFunctions(BB);
   Value *BaseAddr = BaseAddress;
   std::string BaseName = getIslCompatibleName("MemRef_", BaseAddr, "");
MemoryAccess *ScopInfo::addMemoryAccess(
   // overwrite the old value.
   if (Kind == ScopArrayInfo::MK_PHI || Kind == ScopArrayInfo::MK_ExitPHI)
     isKnownMustAccess = true;
 
   if (!isKnownMustAccess && AccType == MemoryAccess::MUST_WRITE)
     AccType = MemoryAccess::MAY_WRITE;
 
   AccList.emplace_back(Stmt, Inst, AccType, BaseAddress, ElementType, Affine,
-                       Subscripts, Sizes, AccessValue, Kind, BaseName);
+                       Subscripts, Sizes, AccessValue, Kind, BaseName,
+                       AddrAlias);
+
   Stmt->addAccess(&AccList.back());
   return &AccList.back();
 }
 
 void ScopInfo::ensureValueWrite(Instruction *Inst) {
-  ScopStmt *Stmt = scop->getStmtFor(Inst);
+  // Mapped scalar writes are handled separately.
+  auto AddrAlias = getValueMappedAddr(Inst);
+  if (AddrAlias)
+    return;
+
+  ScopStmt *Stmt = scop->getStmtFor(Inst->getParent());
 
   // Inst not defined within this SCoP.
   if (!Stmt)
     return;
 
   // Do not process further if the instruction is already written.
   if (Stmt->lookupValueWriteOf(Inst))
     return;
 
   addMemoryAccess(Stmt, Inst->getParent(), Inst, MemoryAccess::MUST_WRITE, Inst,
                   Inst->getType(), true, Inst, ArrayRef<const SCEV *>(),
-                  ArrayRef<const SCEV *>(), ScopArrayInfo::MK_Value);
+                  ArrayRef<const SCEV *>(), ScopArrayInfo::MK_Value,
+                  MemAccInst());
 }
 
 void ScopInfo::ensureValueRead(Value *V, BasicBlock *UserBB) {
 
   // There cannot be an "access" for literal constants. BasicBlock references
   // (jump destinations) also never change.
   if ((isa<Constant>(V) && !isa<GlobalVariable>(V)) || isa<BasicBlock>(V))
     return;
void ScopInfo::ensureValueRead(Value *V, BasicBlock *UserBB) {
   if (ValueStmt == UserStmt)
     return;
 
   // Do not create another MemoryAccess for reloading the value if one already
   // exists.
   if (UserStmt->lookupValueReadOf(V))
     return;
 
+  AddrAliasTy AddrAlias = nullptr;
+  if (ValueInst)
+    // AddrAlias = getValueMappedAddr(ValueInst);
+    AddrAlias = getMappedAlias(ValueInst, UserStmt);
+  if (AddrAlias) {
+    if (isRedundantScalarRead(AddrAlias, ValueInst, UserStmt)) {
+      DEBUG(dbgs() << "Mapped VALUE read of " << ValueInst->getName() << " to"
+                   << *AddrAlias << " before " << UserStmt->getBaseName()
+                   << " considered redundant\n");
+      return;
+    }
+
+    buildMemoryAccessWithAlias(UserStmt, UserBB, nullptr, V, true, AddrAlias);
+  } else
     addMemoryAccess(UserStmt, UserBB, nullptr, MemoryAccess::READ, V,
                     V->getType(), true, V, ArrayRef<const SCEV *>(),
-                  ArrayRef<const SCEV *>(), ScopArrayInfo::MK_Value);
+                    ArrayRef<const SCEV *>(), ScopArrayInfo::MK_Value,
+                    MemAccInst());
+
   if (ValueInst)
     ensureValueWrite(ValueInst);
 }
 
 void ScopInfo::ensurePHIWrite(PHINode *PHI, BasicBlock *IncomingBlock,
                               Value *IncomingValue, bool IsExitBlock) {
+  // MAPPED writes are added in a postprocessing.
+  auto AddrAlias = getPHIMappedAddr(PHI);
+  if (AddrAlias)
+    return;
+
   ScopStmt *IncomingStmt = scop->getStmtFor(IncomingBlock);
   if (!IncomingStmt)
     return;
 
   // Take care for the incoming value being available in the incoming block.
   // This must be done before the check for multiple PHI writes because multiple
   // exiting edges from subregion each can be the effective written value of the
   // subregion. As such, all of them must be made available in the subregion
   // statement.
   ensureValueRead(IncomingValue, IncomingBlock);
 
   // Do not add more than one MemoryAccess per PHINode and ScopStmt.
   if (MemoryAccess *Acc = IncomingStmt->lookupPHIWriteOf(PHI)) {
     assert(Acc->getAccessInstruction() == PHI);
     Acc->addIncoming(IncomingBlock, IncomingValue);
     return;
   }
 
   MemoryAccess *Acc = addMemoryAccess(
       IncomingStmt, IncomingBlock, PHI, MemoryAccess::MUST_WRITE, PHI,
       PHI->getType(), true, PHI, ArrayRef<const SCEV *>(),
       ArrayRef<const SCEV *>(),
-      IsExitBlock ? ScopArrayInfo::MK_ExitPHI : ScopArrayInfo::MK_PHI);
+      IsExitBlock ? ScopArrayInfo::MK_ExitPHI : ScopArrayInfo::MK_PHI,
+      MemAccInst());
   assert(Acc);
   Acc->addIncoming(IncomingBlock, IncomingValue);
 }
 
 void ScopInfo::addPHIReadAccess(PHINode *PHI) {
   ScopStmt *Stmt = scop->getStmtFor(PHI);
+
+  auto AddrAlias = getPHIMappedAddr(PHI);
+  if (AddrAlias) {
+    if (isRedundantScalarRead(AddrAlias, PHI, Stmt)) {
+      DEBUG(dbgs() << "Mapped PHI read of '" << *PHI << "' to '" << *AddrAlias
+                   << "' before '" << Stmt->getBaseName()
+                   << "' considered redundant\n");
+      return;
+    }
+
+    buildMemoryAccessWithAlias(Stmt, PHI->getParent(), PHI, PHI, true,
+                               AddrAlias);
+    return;
+  }
+
   addMemoryAccess(Stmt, PHI->getParent(), PHI, MemoryAccess::READ, PHI,
                   PHI->getType(), true, PHI, ArrayRef<const SCEV *>(),
-                  ArrayRef<const SCEV *>(), ScopArrayInfo::MK_PHI);
+                  ArrayRef<const SCEV *>(), ScopArrayInfo::MK_PHI,
+                  MemAccInst());
+}
+
+#ifndef NDEBUG
+template <typename T>
+static void dumpCollapsed(DenseMap<T *, AddrAliasTy> &Map) {
+  for (auto &Pair : Map) {
+    auto Value = Pair.first;
+    auto Alias = Pair.second;
+    if (!Alias)
+      continue;
+    dbgs() << *Value << "  ->" << *Alias << "\n";
+  }
+}
+#endif
+
+void ScopInfo::greedyCollapse() {
+  DEBUG(dbgs() << "### DeLICM BEGIN\n");
+  auto &R = scop->getRegion();
+
+  for (auto BB : R.blocks()) {
+    // Currently ignore something in subregions as their execution is not
+    // guarantted and it is more likely that there are other loads/stores in
+    // the region.
+    auto Stmt = scop->getStmtFor(BB);
+    if (Stmt->isRegionStmt())
+      continue;
+
+    for (auto &I : *BB) {
+      auto SI = dyn_cast<StoreInst>(&I);
+      if (!SI)
+        continue;
+
+      greedyCollapseStore(SI);
+    }
+  }
+
+  DEBUG(dbgs() << "Mapped Values:\n");
+  DEBUG(dumpCollapsed(CollapseValue));
+  DEBUG(dbgs() << "Mapped PHIs:\n");
+  DEBUG(dumpCollapsed(CollapsePHI));
+
+  DEBUG(dbgs() << "### DeLICM END\n");
+}
+
+/// Return whether the two maps conflict, that is, define different (or
+/// undefined) values for some location.
+static bool isConflicting(OutgoingValueMapTy &Superset,
+                          OutgoingValueMapTy &Subset) {
+  for (auto &Edge : Subset) {
+    auto BB = Edge.first;
+    auto Val = Edge.second;
+    auto Iter = Superset.find(BB);
+    if (Iter == Superset.end())
+      return true; // Conflicting because Superset content is undefined.
+    if (!Iter->second)
+      continue;
+    if (Iter->second != Val)
+      return true;
+  }
+  return false;
+}
+
+/// Merge the defined values of @p Subset into @p Superset.
+static void fixOutgoingValues(OutgoingValueMapTy &Superset,
+                              OutgoingValueMapTy &Subset) {
+  assert(!isConflicting(Superset, Subset));
+  for (auto &Edge : Subset) {
+    auto BB = Edge.first;
+    auto Val = Edge.second;
+    Superset[BB] = Val;
+  }
+}
+
+#ifndef NDEBUG
+static void printOutgoing(llvm::raw_ostream &OS, OutgoingValueMapTy &Map) {
+  for (auto &Pair : Map) {
+    auto Stmt = Pair.first;
+    auto Val = Pair.second;
+
+    if (Val)
+      OS << "  [" << Stmt->getBaseName() << "]  =" << *Val << "\n";
+    else
+      OS << "  [" << Stmt->getBaseName() << "]\n";
+  }
+}
+#endif
+
+void ScopInfo::greedyCollapseStore(AddrAliasTy Store) {
+  // Core DeLICM implementation details.
+  // We have a potential location to store scalars into. We now determine
+  // whether and which scalars can be mapped into that location. The algorithm
+  // works in 3 phases.
+  //
+  // 1> computeNoUseZones) Determine the non-lifetime of the value stored in the
+  // location (no use Zone), i.e. the value currently stored there will never be
+  // used. There are also the cases where we know what value is currently stored
+  // and we can reuse that.
+  //
+  // 2> greedyCollapseStore) From the store's value operand tree upwards, try to
+  //   map scalars (llvm::Values and PHI junctions) to the AddrAlias. This is a
+  //   greedy algorithm, the first value that fits is enshrined into the no-use
+  //   zone as known value to avoid that other values get mapped to the same
+  //   location. Try this until all values from the operand tree have been
+  //   checked. Values that are only defined and used within the same statement
+  //   do not need to be mapped. A scalar can be mapped to at most one location.
+  //
+  // 3> buildScop) When creating READ MemoryAccesses, change they storage
+  // location of mapped scalars to the AddrAlias. Scalar WRITE MemoryAccesses
+  // are skipped. The writes are added after creating the reads where necessary.
+  // This avoid writing the same value multiple times (eg. once as MK_PHI and
+  // another time fore its MK_Value)
+  //
+  // Possible implementation improvements:
+  // - The algorithm makes heavy use of DenseMaps. Some values might be instead
+  //   computed on-the-fly. Eg. getPHIEdges is simple to compute.
+  // - Numbering BasicBlocks in the SCoP and using vectors instead saves map
+  //   lookups.
+  // - Currently there is just one unique exit value per statment (called an
+  //   edge because of a previous implementation). Defining a value per leaving
+  //   edge would allow more mapping possibilities. Particularly on branches
+  //   that either enter the loop or skip it. Because when skipping it the
+  //   location could be read afterwards, currently nothing can be mapped to
+  //   that branching statement (undefined value). Such edge mapping would
+  //   require a new kind of MemoryAccesses on edges instead of on statemements.
+  // - Map not only on array elements by stores, but also on existing scalars to
+  //   reduce the total number of MemoryAccesses.
+  // - Prefer mapping scalars that lead to LoadInst's of the same location.
+  // - The current assumption is that the algorithm runs before the create of
+  //   MemoryAccesses. For better interaction with other passes that modify
+  //   MemoryAccesses, change the algorithm to take the access information from
+  //   the ScopStmt and then modify the the MemoryAccesses.
+  // - Allow that only parts of a value's lifetime range is mapped instead
+  //   always the whole range. Would be useful for values that are defined
+  //   before the SCoP.
+  // - Better ensure (unit tests) that multiple stores/loads to the same
+  //   location in a BasicBlock does not miscompile. Eg. a store after a load
+  //   might overwrite out temporary value, although the store's value
+  //   overwritten again. Such code should not happen after general
+  //   optimization, but we can't be sure.
+  auto &R = scop->getRegion();
+  auto Alias = Store->getPointerOperand();
+  auto StoredVal = dyn_cast<Instruction>(Store->getValueOperand());
+  if (!StoredVal)
+    return;
+
+  // Check that we did not already map something to the same location.
+  // TODO: Handle stores (mustConflict) to same location as equivalence set and
+  // compute no-use zone together.
+  for (auto &Pair : OutgoingCollapsedValue) {
+    auto OtherStore = Pair.first;
+    if (mayConflict(Store, OtherStore))
+      return;
+  }
+
+  auto &NoUseZone = OutgoingCollapsedValue[Store] = computeNoUseZones(Store);
+  bool MappedSomething = false;
+  // if (NoUseZone.empty()) return; //TODO: Make this an option
+
+  DEBUG(dbgs() << "NoUseZone for:" << *Store << " {\n");
+  DEBUG(printOutgoing(dbgs(), NoUseZone));
+  DEBUG(dbgs() << "}\n");
+
+  SmallVector<Instruction *, 16> Worklist;
+  Worklist.push_back(StoredVal);
+
+  do {
+    auto Val = Worklist.pop_back_val();
+
+    // Map only the same type.
+    if (Val->getType() != StoredVal->getType())
+      continue;
+
+    // Do not map instruction that span from before the scop (we'd need an
+    // explicit write to the mapped location when entering the scop).
+    auto ValStmt = scop->getStmtFor(Val);
+    if (!ValStmt)
+      continue;
+
+    if (CollapseValue.count(Val))
+      continue; // Already collapsed to this or another addr
+
+    // Don't try to demote synthesizable values
+    // TODO: Might allow collapsing to multiple addresses
+    if (canSynthesize(Val, LI, SE, &R))
+      continue;
+
+    // If the address is not available at Val's location, don't collapse it
+    // TODO: It might be available further downstream if we allow partial
+    // collapse
+    if (!isComputableAtEndingOf(Alias, Val->getParent()))
+      continue;
+
+    auto &Edges = getLiveEdges(Val);
+    if (isConflicting(NoUseZone, Edges))
+      continue;
+
+    if (!Edges.empty() && !Edges.count(nullptr)) {
+      MappedSomething = true;
+      CollapseValue[Val] = Store;
+      fixOutgoingValues(NoUseZone, Edges);
+    }
+    if (auto PHI = dyn_cast<PHINode>(Val)) {
+      if (CollapsePHI.count(PHI))
+        continue; // Already collapsed to this or another addr
+
+      // Check addr availability
+      if (std::any_of(PHI->block_begin(), PHI->block_end(),
+                      [=](BasicBlock *PredBB) {
+                        return !isComputableAtEndingOf(Alias, PredBB);
+                      }))
+        continue;
+
+      auto &PHIEdges = getPHIEdges(PHI);
+      if (isConflicting(NoUseZone, PHIEdges))
+        continue;
+      if (!PHIEdges.empty() && !PHIEdges.count(nullptr)) {
+        MappedSomething = true;
+        CollapsePHI[PHI] = Store;
+        fixOutgoingValues(NoUseZone, PHIEdges);
+      }
+    }
+
+    for (auto &Use : Val->operands()) {
+      auto UseVal = dyn_cast<Instruction>(Use.get());
+      if (UseVal)
+        Worklist.push_back(UseVal);
+    }
+
+  } while (!Worklist.empty());
+
+  // Remove mapping again if nothing has been mapped to it.
+  if (!MappedSomething) {
+    DEBUG(dbgs() << "Nothing mapped to" << *Alias << "\n");
+    OutgoingCollapsedValue.erase(Store);
+    return;
+  }
+
+  DEBUG(dbgs() << "Mappings for:" << *Alias << " {\n");
+  DEBUG(printOutgoing(dbgs(), NoUseZone); dbgs() << "}\n");
+}
+
+/// Is BB one of blocks that has an edge that leaves Stmt?
+static bool isExitingBB(ScopStmt *Stmt, BasicBlock *BB) {
+  if (Stmt->isBlockStmt())
+    return true;
+  auto SubRegion = Stmt->getRegion();
+  for (auto Exiting : predecessors(SubRegion->getExit())) {
+    if (!SubRegion->contains(Exiting))
+      continue;
+    if (Exiting == BB)
+      return true;
+  }
+  return false;
+}
+
+/// Remove PHINodes that have just one incoming block. These will have exectly
+/// the same value as that incoming value and we do not want it to seemingly
+/// conflict with it.
+static Value *followLCSSA(Value *Val) {
+  auto PHI = dyn_cast<PHINode>(Val);
+  if (!PHI)
+    return Val;
+
+  if (PHI->getNumIncomingValues() != 1)
+    return Val;
+
+  return PHI->getIncomingValue(0);
+}
+
+bool ScopInfo::addDefUseEdges(OutgoingValueMapTy &Edges, Use &Use) {
+  auto Val = dyn_cast<Instruction>(Use.get());
+  if (!Val)
+    return true;
+  auto DefBB = Val->getParent();
+
+  auto User = Use.getUser();
+  auto EffectiveUser = dyn_cast<Instruction>(User);
+  if (!EffectiveUser)
+    return true;
+
+  // Currently do not support five ranges extending beyond the scop. This
+  // includes exit phi nodes.
+  auto UserStmt = scop->getStmtFor(EffectiveUser);
+  if (!UserStmt) {
+    Edges[nullptr] = nullptr;
+    return false;
+  }
+
+  BasicBlock *EffectiveUserBB = EffectiveUser->getParent();
+  if (auto PHI = dyn_cast<PHINode>(EffectiveUser)) {
+    auto i = Use.getOperandNo();
+    EffectiveUserBB = PHI->getIncomingBlock(i);
+    EffectiveUser = EffectiveUserBB->getTerminator();
+  }
+
+  // All OK if the use follows the definition within the same basic block.
+  // Continuing would assume that that definition comes after the user, i.e.
+  // looping to itself (should be impossible for reachable BBs).
+  if (EffectiveUserBB == Val->getParent()) {
+    auto Next = Val;
+    while ((Next = Next->getNextNode()))
+      if (Next == EffectiveUser)
+        return true;
+  }
+
+  DenseSet<BasicBlock *> Reachable;
+  SmallVector<BasicBlock *, 8> Worklist;
+  Worklist.push_back(EffectiveUserBB);
+
+  while (!Worklist.empty()) {
+    auto BB = Worklist.pop_back_val();
+
+    for (auto Pred : predecessors(BB)) {
+      if (Reachable.count(Pred)) // Already visited
+        continue;
+      if (DefBB != Pred && !DT->dominates(DefBB, Pred))
+        continue;
+
+      Reachable.insert(Pred);
+      auto Node = scop->getStmtFor(Pred);
+      if (!Node) {
+        // Mark as not feasible (lifetime extends scop)
+        // TODO: How to handle this case
+        Edges[nullptr] = nullptr;
+        return false;
+      }
+      if (DefBB != Pred)
+        Worklist.push_back(Pred); // Do not flow back through the DefBB, only
+                                  // the last executed definition is relevant.
+
+      // Definitions that are inside subregions are infeasible for mapping. Must
+      // be a PHI mapping. TODO: Values dominated by all exiting nodes can be
+      // used outside, not only the entry ndoe.
+      if (Val->getParent() != Node->getEntryBlock()) {
+        Edges[nullptr] = nullptr;
+        return false;
+      }
+
+      Edges[Node] = followLCSSA(Val);
+    }
+  }
+  return true;
+}
+
+OutgoingValueMapTy &ScopInfo::getLiveEdges(Instruction *Val) {
+  auto It = AliveValuesCache.find(Val);
+  if (It != AliveValuesCache.end())
+    return It->second;
+
+  auto &Edges = AliveValuesCache[Val];
+
+  // Do not try to map away invariant loads, those are optimized away later.
+  if (auto LI = dyn_cast<LoadInst>(Val)) {
+    auto ScopRIL = SD->getRequiredInvariantLoads(&scop->getRegion());
+    if (ScopRIL->count(LI)) {
+      Edges[nullptr] = nullptr;
+      return Edges;
+    }
+  }
+
+  for (auto &Use : Val->uses())
+    addDefUseEdges(Edges, Use);
+
+  return Edges;
+}
+
+OutgoingValueMapTy &ScopInfo::getPHIEdges(PHINode *PHI) {
+  auto It = PHIEdgesCache.find(PHI);
+  if (It != PHIEdgesCache.end())
+    return It->second;
+
+  auto &ScopRegion = scop->getRegion();
+
+  OutgoingValueMapTy &Result = PHIEdgesCache[PHI];
+  int NumIncoming = PHI->getNumIncomingValues();
+  for (int i = 0; i < NumIncoming; i += 1) {
+    auto IncomingValue = PHI->getIncomingValue(i);
+    auto IncomingBlock = PHI->getIncomingBlock(i);
+    if (!ScopRegion.contains(IncomingBlock))
+      continue;
+
+    auto Node = scop->getStmtFor(IncomingBlock);
+    if (!Node)
+      continue;
+    if (Node->isBlockStmt())
+      Result[Node] = followLCSSA(IncomingValue);
+    else if (isExitingBB(Node, IncomingBlock)) {
+      // A subregion can have multiple outgoing edges, so we use the PHI itself
+      // to represent since we can map at most one outgoing value. The
+      // 'incoming' values themselves may not even be accessible outside the
+      // subregion.
+      assert(!Result.count(Node) || Result[Node] == followLCSSA(PHI));
+      Result[Node] = followLCSSA(PHI);
+    }
+  }
+  return Result;
+}
+
+bool ScopInfo::mustConflict(MemAccInst SI, MemAccInst LI) {
+  if (SI == LI)
+    return true;
+
+#if 0
+  // 1. Check: Ask alias analysis
+  auto AATest = AA->alias(MemoryLocation::get(SI.asInstruction()),
+                          MemoryLocation::get(LI.asInstruction()));
+  if (AATest == MustAlias)
+    return true;
+#endif
+
+  // 2. Check: Is it accessing the same array element?
+  // This might be redundant if the AliasAnalysis does a good job.
+  auto SIExpr = SE->getSCEV(SI.getPointerOperand());
+  auto LIExpr = SE->getSCEV(LI.getPointerOperand());
+
+  // This should ensure that the BaseAddrsess and Subscripts are equal.
+  // SI and LI must occur within the same loop body for which the SCEV have
+  // dependences (ie. the induction variable's value is guarantted the be the
+  // same). This should have been ensured by greedyCollapse, but we may want to
+  // add an assertion here.
+
+  return SIExpr == LIExpr;
+}
+
+bool ScopInfo::mayConflict(MemAccInst SI, MemAccInst LI) {
+#if 0
+  // 1. Check: Ask alias analysis
+  auto AATest = AA->alias(MemoryLocation::get(SI), MemoryLocation::get(LI));
+  if (AATest == NoAlias)
+    return false;
+#endif
+
+  // 2. Check: Polly's requirement that arrays are disjoint
+  auto LoadSAI = getOrCreateSAI(LI);
+  if (LoadSAI->getBasePtrOriginSAI())
+    LoadSAI = LoadSAI->getBasePtrOriginSAI();
+
+  auto WriteSAI = getOrCreateSAI(SI);
+  if (WriteSAI->getBasePtrOriginSAI())
+    WriteSAI = WriteSAI->getBasePtrOriginSAI();
+
+  return LoadSAI == WriteSAI;
+}
+
+bool ScopInfo::mayOverwrite(MemAccInst Loc, BasicBlock *BB,
+                            BasicBlock::iterator Start,
+                            BasicBlock::iterator End) {
+  for (auto It = Start; It != End; ++It) {
+    auto SI = dyn_cast<StoreInst>(&*It);
+    if (!SI)
+      continue;
+
+    if (mayConflict(Loc, SI))
+      return true;
+  }
+  return false;
+}
+
+// TODO: It's possible that on one outgoing edge the data needs to be preserve,
+// but is free to use when going the other branch; to support the, we require
+// per-edge NoUseZone and edge-dependent PHI WRITE MemoryAccesses
+OutgoingValueMapTy ScopInfo::computeNoUseZones(AddrAliasTy SI) {
+  auto StoreBB = SI->getParent();
+  auto &PD = getAnalysis<PostDominatorTree>();
+
+  OutgoingValueMapTy Result;
+  // Get all the locations where a value written to the same address as SI will
+  // be overwritten by SI.
+  SmallVector<BasicBlock *, 8> Postdominated;
+  PD.getDescendants(StoreBB,
+                    Postdominated); // (Postdominated will also contain StoreBB)
+
+  SmallVector<BasicBlock *, 8> Worklist;
+  DenseSet<BasicBlock *> ReachableRead;
+
+  // Search for loads in BBs that are postdominated by the store
+  for (auto Node : Postdominated) {
+    for (auto &Inst : *Node) {
+      if (Node == StoreBB && &Inst == SI)
+        break;
+
+      if (!isa<LoadInst>(Inst))
+        continue;
+      auto &LI = cast<LoadInst>(Inst);
+      if (mayConflict(SI, LI)) {
+        Worklist.push_back(Node);
+        break;
+      }
+    }
+  }
+
+  // Determine the BasicBlocks with a control flow to a read to that value. That
+  // is, the blocks where the value is not dead.
+  // TODO: Add function return to Worklist; unless the array is local the caller
+  // is free to read the memory. We'd not need the postominator.
+  while (!Worklist.empty()) {
+    auto BB = Worklist.pop_back_val();
+    for (auto Pred : predecessors(BB)) {
+      if (ReachableRead.count(Pred))
+        continue;
+      if (!PD.dominates(StoreBB, Pred))
+        continue;
+      ReachableRead.insert(Pred);
+
+      // The exit of the store's BB might be reachable, but everything in front
+      // of it will be overwritten.
+      if (StoreBB == Pred)
+        continue;
+
+      Worklist.push_back(Pred);
+    }
+  }
+
+  // Determine the statmtements where:
+  // - the location will be overwritten
+  // - no path leads to a read that does not cross the write
+  for (auto Node : Postdominated) {
+    if (Node == StoreBB)
+      continue;
+
+    if (ReachableRead.count(Node))
+      continue;
+
+    auto Stmt = scop->getStmtFor(Node);
+    if (Stmt)
+      Result[Stmt] = nullptr;
+  }
+
+  // Also fix when we know what value the element has
+  SmallVector<BasicBlock *, 8> PostWriteWorklist;
+
+  // Value at SI's location at when leaving a BasicBlock
+  // unmapped means don't know
+  // nullptr means no unique value
+  DenseMap<BasicBlock *, Value *> KnownContent;
+
+  auto HomeBB = SI->getParent();
+  if (mayOverwrite(SI, HomeBB, SI->getNextNode()->getIterator()))
+    return Result;
+
+  KnownContent[HomeBB] = SI->getValueOperand();
+  for (auto Succ : successors(HomeBB))
+    PostWriteWorklist.push_back(Succ);
+
+  while (!PostWriteWorklist.empty()) {
+    auto BB = PostWriteWorklist.pop_back_val();
+    auto BeenVisited = KnownContent.count(BB);
+
+    if (!DT->properlyDominates(HomeBB, BB))
+      continue;
+
+    if (mayOverwrite(SI, BB)) {
+      KnownContent[BB] = nullptr;
+      continue;
+    }
+
+    if (BeenVisited && KnownContent.lookup(BB) != SI->getValueOperand()) {
+      KnownContent[BB] = nullptr;
+      continue;
+    }
+
+    KnownContent[BB] = SI->getValueOperand();
+    if (BeenVisited)
+      continue;
+
+    for (auto Succ : successors(BB))
+      PostWriteWorklist.push_back(Succ);
+  }
+  // Translate the per-BB relationship to KnownContent a per-Stmt relationship
+  // in Result
+  for (auto &Stmt : *scop) {
+    if (Result.count(&Stmt))
+      continue;
+
+    if (Stmt.isBlockStmt()) {
+      auto BB = Stmt.getBasicBlock();
+      if (KnownContent.lookup(BB))
+        Result[&Stmt] = KnownContent.lookup(BB);
+      continue;
+    }
+
+    auto R = Stmt.getRegion();
+    bool Contradicting = false;
+    for (auto Exiting : predecessors(R->getExit())) {
+      if (!R->contains(Exiting))
+        continue;
+
+      if (KnownContent.lookup(Exiting) != SI->getValueOperand()) {
+        Contradicting = true;
+        break;
+      }
+    }
+
+    if (!Contradicting)
+      Result[&Stmt] = SI->getValueOperand();
+  }
+
+  return Result;
+}
+
+StoreInst *ScopInfo::getMappedAlias(Instruction *Inst, ScopStmt *Stmt) {
+  // If Inst is a PHI we can directly use it (.phiops) in the same statement.
+  // For use in other statments, it must be temporary stored as a value (.s2a)
+  if (auto PHIVal = dyn_cast<PHINode>(Inst)) {
+    auto PHIStmt = scop->getStmtFor(PHIVal);
+    if (PHIStmt == Stmt)
+      return getPHIMappedAddr(PHIVal);
+  }
+
+  return getValueMappedAddr(Inst);
+}
+
+bool ScopInfo::isRedundantScalarRead(AddrAliasTy AddrAlias, Instruction *Val,
+                                     ScopStmt *Stmt, bool isExplicit) {
+  // Check if there is already a LoadInst for this Scalar. If so, we prioritize
+  // this LoadInst over creating a different one.
+
+  if (!isExplicit) {
+    if (auto LI = dyn_cast<LoadInst>(Val)) {
+      auto LoadStmt = scop->getStmtFor(LI);
+      auto LoadAlias = LI;
+      if (Stmt == LoadStmt && mustConflict(LoadAlias, AddrAlias))
+        return true;
+    }
+  }
+
+  for (auto &Use : Val->uses()) {
+    if (auto User = dyn_cast<PHINode>(Use.getUser())) {
+      auto IncomingBB = User->getIncomingBlock(Use);
+      auto UserStmt = scop->getStmtFor(IncomingBB);
+      if (UserStmt != Stmt)
+        continue;
+
+      auto UserAlias = getPHIMappedAddr(User);
+      if (!UserAlias)
+        return false;
+
+      if (UserAlias != AddrAlias)
+        return false;
+    } else if (auto User = dyn_cast<StoreInst>(Use.getUser())) {
+      auto UserStmt = scop->getStmtFor(User);
+      if (UserStmt != Stmt)
+        continue;
+
+      if (User != AddrAlias)
+        return false;
+    } else if (auto User = dyn_cast<Instruction>(Use.getUser())) {
+      auto UserStmt = scop->getStmtFor(User);
+      if (UserStmt != Stmt) // This includes out-of-scop users
+        continue;
+
+      return false;
+    } else
+      return false;
+  }
+
+  return true;
+}
+
+// Find a reason why the value is already stored in Addr.
+bool ScopInfo::isRedundantScalarWrite(AddrAliasTy Addr, Value *Val,
+                                      ScopStmt *Stmt, bool isExplicit) {
+  if (!Addr)
+    return false;
+
+  auto ValInst = dyn_cast<Instruction>(Val);
+  if (!ValInst)
+    return false;
+
+  // Writing invariant loads is unnecessary; those will be directly forwarded to
+  // they use.
+  if (auto LI = dyn_cast<LoadInst>(Val)) {
+    auto ScopRIL = SD->getRequiredInvariantLoads(&scop->getRegion());
+    if (ScopRIL->count(LI))
+      return true;
+  }
+
+  auto DefStmt = scop->getStmtFor(ValInst);
+
+  // With subregions that have multiple incoming values for the successor
+  // statement, the defining PHI is in the the successor, not Stmt. We correct
+  // that by treating the PHI as if a PHI with the affected incoming values were
+  // split into a separate BB and merges into the subregion as exiting block.
+  if (Stmt->isRegionStmt() && isa<PHINode>(ValInst) &&
+      ValInst->getParent() == Stmt->getRegion()->getExit())
+    DefStmt = Stmt;
+
+  // If defined in another statement, that statment must have already written
+  // that value.
+  // TODO: When supporting partial mapping, must compare what value is currenty
+  // in (when entring Stmt) to what value it should have when leaving the stmt.
+  if (DefStmt != Stmt)
+    return true;
+
+  if (!isExplicit)
+    // Search for a store in the same block st. that an implicit store is
+    // unnecessary.
+    for (auto &U : Val->uses()) {
+      auto SI = dyn_cast<StoreInst>(U.getUser());
+      if (!SI)
+        continue;
+      if (scop->getStmtFor(SI) != Stmt)
+        continue;
+
+      if (mustConflict(Addr, SI))
+        return true;
+    }
+
+  // If the value has jsut been loaded from that location, we don't need to
+  // re-save it.
+  if (auto LI = dyn_cast<LoadInst>(ValInst)) {
+    if (mustConflict(Addr, LI))
+      return true;
+  }
+
+  MemAccInst ValAlias = getMappedAlias(ValInst, Stmt);
+  if (!ValAlias) {
+    // If Val is not mapped itself, maybe it is loaded from a location.
+    // if (auto LI = dyn_cast<LoadInst>(ValInst))
+    //  ValAlias = LI;
+  }
+
+  if (!ValAlias)
+    return false;
+
+  if (!mustConflict(ValAlias, Addr))
+    return false;
+
+  // Value from outside the scop
+  // TODO: must write it when entering the scop or disallow mapping it.
+  if (!DefStmt) {
+    llvm_unreachable(
+        "Mapped definitions from before the SCoP currently not supported.");
+    return false;
+  }
+
+  auto ValPHI = dyn_cast<PHINode>(ValInst);
+  if (ValPHI && (DefStmt == Stmt))
+    return true;
+
+  return false;
+}
+
+bool ScopInfo::isRedundantScalarWriteOfAlias(AddrAliasTy Addr,
+                                             Instruction *ValInst,
+                                             ScopStmt *Stmt, bool isExplicit,
+                                             MemAccInst ValAlias) {
+  if (!mustConflict(ValAlias, Addr))
+    return false;
+
+  auto DefStmt = scop->getStmtFor(ValInst);
+
+  // Value from outside the scop
+  // TODO: must write it when entering the scop or disallow mapping it.
+  if (!DefStmt) {
+    llvm_unreachable(
+        "Mapped definitions from before the SCoP currently not supported.");
+    return false;
+  }
+
+  auto ValPHI = dyn_cast<PHINode>(ValInst);
+  if (ValPHI && (DefStmt == Stmt))
+    return true;
+
+  // If defined in another statement, that statment must have already written
+  // that value.
+  // TODO: When supporting partial mapping, must compare what value is currenty
+  // in (when entring Stmt) to what value it should have when leaving the stmt.
+  if (DefStmt != Stmt)
+    return true;
+
+  // All other cases.
+  return false;
+}
+
+bool ScopInfo::isRedundantMemAcc(MemAccInst AccInst) {
+  if (AccInst.isLoad())
+    return isRedundantLoad(AccInst.asLoad());
+  if (AccInst.isStore())
+    return isRedundantStore(AccInst.asStore());
+  return false;
+}
+
+bool ScopInfo::isRedundantLoad(LoadInst *LI) {
+  // Invariant load hoisting requires the MemoryAccess to be created.
+  const InvariantLoadsSetTy *ScopRIL =
+      SD->getRequiredInvariantLoads(&scop->getRegion());
+  if (ScopRIL->count(LI))
+    return false;
+
+  auto Alias = getValueMappedAddr(LI);
+  if (!Alias)
+    return false;
+  if (!mustConflict(LI, Alias))
+    return false;
+  auto Stmt = scop->getStmtFor(LI);
+  return isRedundantScalarRead(Alias, LI, Stmt, true);
+}
+
+bool ScopInfo::isRedundantStore(StoreInst *SI) {
+  auto Val = dyn_cast<Instruction>(SI->getValueOperand());
+  if (!Val)
+    return false;
+
+  auto Stmt = scop->getStmtFor(SI);
+  auto Addr = getMappedAlias(Val, Stmt);
+  return isRedundantScalarWrite(Addr, Val, Stmt, true);
 }
 
 void ScopInfo::buildScop(Region &R, AssumptionCache &AC) {
   unsigned MaxLoopDepth = getMaxLoopDepthInRegion(R, *LI, *SD);
   scop.reset(new Scop(R, *SE, MaxLoopDepth));
 
   buildStmts(R, R);
+
+  for (auto BB : R.blocks()) {
+    for (auto &I : *BB) {
+      auto AccInst = MemAccInst::dyn_cast(I);
+      if (!AccInst)
+        continue;
+
+// WORKAROUND AHEAD:
+// getOrCreateScopArrayInfo requires that the base SAI of indirect
+// accesses are already created. This relies on requesting those first.
+// This workaround may still fail because there is no guarantee that basic
+// blocks are iterated through in an topological order of the dominance
+// tree (i.e. the base access in a BB before the indirect one, but
+// iterated through in reverse order)
+#if 1
+      getOrCreateSAI(AccInst);
+#endif
+    }
+  }
+
+  if (ScalarCollapse)
+    greedyCollapse();
+
   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
   // accesses. Note that we do not model anything in the exit block if we have
   // an exiting block in the region, as there will not be any splitting later.
   if (!R.getExitingBlock())
     buildAccessFunctions(R, *R.getExit(), nullptr,
                          /* IsExitBlock */ true);
 
+  for (auto &AddrIter : OutgoingCollapsedValue) {
+    auto Alias = AddrIter.first;
+    auto &Map = AddrIter.second;
+
+    for (auto &BBIter : Map) {
+      auto Node = BBIter.first;
+      auto OutVal = BBIter.second;
+
+      // Happens if in no-use zone, but no value/PHI has been mapped to it.
+      if (!OutVal)
+        continue;
+
+      if (isRedundantScalarWrite(Alias, OutVal, Node))
+        continue;
+
+      DEBUG(dbgs() << "Mapped write of '" << *OutVal << "' to '" << *Alias
+                   << "' after '" << Node->getBaseName() << "'\n");
+      // Special treatment for subregions that have multiple outgoing values;
+      // The code generator must know about them.
+      if (auto PHI = dyn_cast<PHINode>(OutVal))
+        if (Node->isRegionStmt() &&
+            Node->getRegion()->getExit() == PHI->getParent()) {
+          auto MA = buildMemoryAccessWithAlias(Node, Node->getEntryBlock(), PHI,
+                                               OutVal, false, Alias);
+          for (auto &Incoming : PHI->operands()) {
+            auto Incomingblock = PHI->getIncomingBlock(Incoming);
+            if (!Node->contains(Incomingblock))
+              continue;
+            MA->addIncoming(Incomingblock, Incoming.get());
+          }
+          continue;
+        }
+
+      buildMemoryAccessWithAlias(Node, Node->getEntryBlock(), nullptr, OutVal,
+                                 false, Alias);
+    }
+  }
+
   scop->init(*AA, AC, *SD, *DT, *LI);
 }
 
 void ScopInfo::print(raw_ostream &OS, const Module *) const {
   if (!scop) {
     OS << "Invalid Scop!\n";
     return;
   }
 
   scop->print(OS);
 }
 
-void ScopInfo::clear() { scop.reset(); }
+void ScopInfo::clear() {
+  scop.reset();
+  CollapseValue.clear();
+  CollapsePHI.clear();
+  OutgoingCollapsedValue.clear();
+  AliveValuesCache.clear();
+  PHIEdgesCache.clear();
+}
 
 //===----------------------------------------------------------------------===//
 ScopInfo::ScopInfo() : RegionPass(ID) {}
 
 ScopInfo::~ScopInfo() { clear(); }
 
 void ScopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<LoopInfoWrapperPass>();
   AU.addRequired<RegionInfoPass>();
   AU.addRequired<DominatorTreeWrapperPass>();
+  AU.addRequired<PostDominatorTree>();
   AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
   AU.addRequiredTransitive<ScopDetection>();
   AU.addRequired<AAResultsWrapperPass>();
   AU.addRequired<AssumptionCacheTracker>();
   AU.setPreservesAll();
 }
 
 bool ScopInfo::runOnRegion(Region *R, RGPassManager &RGM) {
if (scop->getMaxLoopDepth() > 0)
       ++RichScopFound;
   }
 
   emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE, *F, End, Msg);
 
   return false;
 }
 
+namespace {
+struct SCEVExpandibilityChecker {
+private:
+  BasicBlock *LocationBlock;
+  bool IncludeBlock;
+  DominatorTree *DT;
+  bool FoundUnexapandable;
+
+  SCEVExpandibilityChecker(BasicBlock *LocationBlock, bool IncludeBlock,
+                           DominatorTree *DT)
+      : LocationBlock(LocationBlock), IncludeBlock(IncludeBlock), DT(DT),
+        FoundUnexapandable(false) {}
+
+  bool unexpandable() {
+    FoundUnexapandable = true;
+    return false;
+  }
+
+public:
+  bool follow(const SCEV *S) {
+    if (auto AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
+      auto L = AddRec->getLoop();
+      if (!L->contains(LocationBlock))
+        return unexpandable();
+    } else if (auto Unk = dyn_cast<SCEVUnknown>(S)) {
+      auto Val = Unk->getValue();
+      if (isa<Constant>(Val))
+        return true;
+
+      Instruction *Inst = dyn_cast<Instruction>(Val);
+
+      // Strange case
+      if (!Inst)
+        return unexpandable();
+
+      auto InstBB = Inst->getParent();
+      if (InstBB == LocationBlock) {
+        if (!IncludeBlock)
+          return unexpandable();
+        return true;
+      }
+
+      if (!DT->dominates(InstBB, LocationBlock))
+        return unexpandable();
+    }
+
+    return true;
+  }
+
+  bool isDone() { return FoundUnexapandable; }
+
+  static bool isExpandableBefore(const SCEV *S, BasicBlock *LocationBlock,
+                                 bool IncludeBlock, DominatorTree *DT) {
+    SCEVExpandibilityChecker Checker(LocationBlock, IncludeBlock, DT);
+    SCEVTraversal<SCEVExpandibilityChecker> ST(Checker);
+    ST.visitAll(S);
+    return !Checker.isDone();
+  }
+};
+}
+
+bool ScopInfo::isComputableAtEndingOf(Value *Val, BasicBlock *BB) {
+  if (SE->isSCEVable(Val->getType())) {
+    if (const SCEV *Scev = SE->getSCEV(Val))
+      if (!isa<SCEVCouldNotCompute>(Scev)) {
+        if (SCEVExpandibilityChecker::isExpandableBefore(Scev, BB, true, DT))
+          return true;
+      }
+  }
+
+  auto Inst = dyn_cast<Instruction>(Val);
+  if (!Inst)
+    return false;
+  auto InstBB = Inst->getParent();
+
+  if (InstBB == BB)
+    return true;
+  return DT->dominates(InstBB, BB);
+}
+
 char ScopInfo::ID = 0;
 
 Pass *polly::createScopInfoPass() { return new ScopInfo(); }
 
 INITIALIZE_PASS_BEGIN(ScopInfo, "polly-scops",
                       "Polly - Create polyhedral description of Scops", false,
                       false);
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass);

lib/CodeGen/BlockGenerators.cpp

if (!NewInst->getType()->isVoidTy())
     NewInst->setName("p_" + Inst->getName());
 }
 
 Value *
 BlockGenerator::generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst,
                                          ValueMapT &BBMap, LoopToScevMapT &LTS,
                                          isl_id_to_ast_expr *NewAccesses) {
   const MemoryAccess &MA = Stmt.getArrayAccessFor(Inst);
+  return generateLocationAccessed(
+      Stmt, getLoopForStmt(Stmt), Inst.getPointerOperand(), BBMap, LTS,
+      NewAccesses, MA.getId(), MA.getAccessValue()->getType());
+}
 
-  isl_ast_expr *AccessExpr = isl_id_to_ast_expr_get(NewAccesses, MA.getId());
+Value *BlockGenerator::generateLocationAccessed(
+    ScopStmt &Stmt, Loop *L, Value *Pointer, ValueMapT &BBMap,
+    LoopToScevMapT &LTS, isl_id_to_ast_expr *NewAccesses, __isl_take isl_id *Id,
+    Type *ExpectedType) {
+  isl_ast_expr *AccessExpr = isl_id_to_ast_expr_get(NewAccesses, Id);
 
   if (AccessExpr) {
     AccessExpr = isl_ast_expr_address_of(AccessExpr);
     auto Address = ExprBuilder->create(AccessExpr);
 
     // Cast the address of this memory access to a pointer type that has the
     // same element type as the original access, but uses the address space of
     // the newly generated pointer.
-    auto OldPtrTy = MA.getAccessValue()->getType()->getPointerTo();
+    auto OldPtrTy = ExpectedType->getPointerTo();
     auto NewPtrTy = Address->getType();
     OldPtrTy = PointerType::get(OldPtrTy->getElementType(),
                                 NewPtrTy->getPointerAddressSpace());
 
     if (OldPtrTy != NewPtrTy)
       Address = Builder.CreateBitOrPointerCast(Address, OldPtrTy);
     return Address;
   }
 
-  return getNewValue(Stmt, Inst.getPointerOperand(), BBMap, LTS,
-                     getLoopForStmt(Stmt));
+  return getNewValue(Stmt, Pointer, BBMap, LTS, L);
 }
 
-Loop *BlockGenerator::getLoopForStmt(const ScopStmt &Stmt) const {
-  auto *StmtBB =
-      Stmt.isBlockStmt() ? Stmt.getBasicBlock() : Stmt.getRegion()->getEntry();
-  return LI.getLoopFor(StmtBB);
+Loop *BlockGenerator::getLoopForStmt(ScopStmt &Stmt) {
+  return LI.getLoopFor(Stmt.getEntryBlock());
 }
 
 Value *BlockGenerator::generateScalarLoad(ScopStmt &Stmt, LoadInst *Load,
                                           ValueMapT &BBMap, LoopToScevMapT &LTS,
                                           isl_id_to_ast_expr *NewAccesses) {
   if (Value *PreloadLoad = GlobalMap.lookup(Load))
     return PreloadLoad;
 
void BlockGenerator::copyInstruction(ScopStmt &Stmt, Instruction *Inst,
   if (Inst->isTerminator())
     return;
 
   // Synthesizable statements will be generated on-demand.
   if (canSyntheziseInStmt(Stmt, Inst))
     return;
 
   if (auto *Load = dyn_cast<LoadInst>(Inst)) {
+    // If there is no MemoryAccess for this load, the load has been identified
+    // as redundant.
+    if (!Stmt.getArrayAccessOrNULLFor(Load))
+      return;
+
     Value *NewLoad = generateScalarLoad(Stmt, Load, BBMap, LTS, NewAccesses);
     // Compute NewLoad before its insertion in BBMap to make the insertion
     // deterministic.
     BBMap[Load] = NewLoad;
     return;
   }
 
   if (auto *Store = dyn_cast<StoreInst>(Inst)) {
+    // If there is no MemoryAccess for this store, it has been identified as
+    // redundant.
+    if (!Stmt.getArrayAccessOrNULLFor(Store))
+      return;
+
     generateScalarStore(Stmt, Store, BBMap, LTS, NewAccesses);
     return;
   }
 
   if (auto *PHI = dyn_cast<PHINode>(Inst)) {
     copyPHIInstruction(Stmt, PHI, BBMap, LTS);
     return;
   }
BasicBlock *BlockGenerator::splitBB(BasicBlock *BB) {
   return CopyBB;
 }
 
 BasicBlock *BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB,
                                    ValueMapT &BBMap, LoopToScevMapT &LTS,
                                    isl_id_to_ast_expr *NewAccesses) {
   BasicBlock *CopyBB = splitBB(BB);
   Builder.SetInsertPoint(&CopyBB->front());
-  generateScalarLoads(Stmt, BBMap);
+  generateScalarLoads(Stmt, LTS, BBMap, NewAccesses);
 
   copyBB(Stmt, BB, CopyBB, BBMap, LTS, NewAccesses);
 
   // After a basic block was copied store all scalars that escape this block in
   // their alloca.
-  generateScalarStores(Stmt, LTS, BBMap);
+  generateScalarStores(Stmt, LTS, BBMap, NewAccesses);
   return CopyBB;
 }
 
 void BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *CopyBB,
                             ValueMapT &BBMap, LoopToScevMapT &LTS,
                             isl_id_to_ast_expr *NewAccesses) {
   EntryBB = &CopyBB->getParent()->getEntryBlock();
 

 
 Value *BlockGenerator::getOrCreateAlloca(const MemoryAccess &Access) {
   if (Access.isPHIKind())
     return getOrCreatePHIAlloca(Access.getBaseAddr());
   else
     return getOrCreateScalarAlloca(Access.getBaseAddr());
 }
 
+Value *
+BlockGenerator::getImplicitAddress(MemoryAccess &Access, Loop *L,
+                                   LoopToScevMapT &LTS, ValueMapT &BBMap,
+                                   __isl_keep isl_id_to_ast_expr *NewAccesses) {
+  if (Access.isValueKind() || Access.isExitPHIKind())
+    return getOrCreateScalarAlloca(Access.getBaseAddr());
+  else if (Access.isPHIKind())
+    return getOrCreatePHIAlloca(Access.getBaseAddr());
+
+  assert(Access.isMapped());
+  auto MappedAddr = Access.getMappedAliasAddr();
+  return generateLocationAccessed(
+      *Access.getStatement(), L, MappedAddr.getPointerOperand(), BBMap, LTS,
+      NewAccesses, Access.getId(), Access.getAccessValue()->getType());
+}
+
 Value *BlockGenerator::getOrCreateAlloca(const ScopArrayInfo *Array) {
   if (Array->isPHIKind())
     return getOrCreatePHIAlloca(Array->getBasePtr());
   else
     return getOrCreateScalarAlloca(Array->getBasePtr());
 }
 
 Value *BlockGenerator::getOrCreateScalarAlloca(Value *ScalarBase) {
void BlockGenerator::handleOutsideUsers(const Region &R, Instruction *Inst,
 
   // Get or create an escape alloca for this instruction.
   auto *ScalarAddr = Address ? Address : getOrCreateScalarAlloca(Inst);
 
   // Remember that this instruction has escape uses and the escape alloca.
   EscapeMap[Inst] = std::make_pair(ScalarAddr, std::move(EscapeUsers));
 }
 
-void BlockGenerator::generateScalarLoads(ScopStmt &Stmt, ValueMapT &BBMap) {
+void BlockGenerator::generateScalarLoads(
+    ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap,
+    __isl_keep isl_id_to_ast_expr *NewAccesses) {
   for (MemoryAccess *MA : Stmt) {
-    if (MA->isArrayKind() || MA->isWrite())
+    if ((MA->isArrayKind() && !MA->isMapped()) || MA->isWrite())
       continue;
 
-    auto *Address = getOrCreateAlloca(*MA);
+    Value *Address =
+        getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS, BBMap, NewAccesses);
     assert((!isa<Instruction>(Address) ||
             DT.dominates(cast<Instruction>(Address)->getParent(),
                          Builder.GetInsertBlock())) &&
            "Domination violation");
-    BBMap[MA->getBaseAddr()] =
+    BBMap[MA->getAccessValue()] =
         Builder.CreateLoad(Address, Address->getName() + ".reload");
   }
 }
 
-void BlockGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
-                                          ValueMapT &BBMap) {
+void BlockGenerator::generateScalarStores(
+    ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap,
+    __isl_keep isl_id_to_ast_expr *NewAccesses) {
   Loop *L = LI.getLoopFor(Stmt.getBasicBlock());
 
   assert(Stmt.isBlockStmt() && "Region statements need to use the "
                                "generateScalarStores() function in the "
                                "RegionGenerator");
 
   for (MemoryAccess *MA : Stmt) {
-    if (MA->isArrayKind() || MA->isRead())
+    if ((MA->isArrayKind() && !MA->isMapped()) || MA->isRead())
       continue;
 
     Value *Val = MA->getAccessValue();
     if (MA->isAnyPHIKind()) {
       assert(MA->getIncoming().size() >= 1 &&
              "Block statements have exactly one exiting block, or multiple but "
              "with same incoming block and value");
       assert(std::all_of(MA->getIncoming().begin(), MA->getIncoming().end(),
                          [&](std::pair<BasicBlock *, Value *> p) -> bool {
                            return p.first == Stmt.getBasicBlock();
                          }) &&
              "Incoming block must be statement's block");
       Val = MA->getIncoming()[0].second;
     }
-    auto *Address = getOrCreateAlloca(*MA);
+    auto Address =
+        getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS, BBMap, NewAccesses);
 
     Val = getNewValue(Stmt, Val, BBMap, LTS, L);
     assert((!isa<Instruction>(Val) ||
             DT.dominates(cast<Instruction>(Val)->getParent(),
                          Builder.GetInsertBlock())) &&
            "Domination violation");
     assert((!isa<Instruction>(Address) ||
             DT.dominates(cast<Instruction>(Address)->getParent(),
void VectorBlockGenerator::copyInstruction(
   // expressed in the clast and do not need to be copied.
   if (Inst->isTerminator())
     return;
 
   if (canSyntheziseInStmt(Stmt, Inst))
     return;
 
   if (auto *Load = dyn_cast<LoadInst>(Inst)) {
+    if (!Stmt.getArrayAccessOrNULLFor(Load))
+      return;
+
     generateLoad(Stmt, Load, VectorMap, ScalarMaps, NewAccesses);
     return;
   }
 
   if (hasVectorOperands(Inst, VectorMap)) {
     if (auto *Store = dyn_cast<StoreInst>(Inst)) {
+      if (!Stmt.getArrayAccessOrNULLFor(Store))
+        return;
+
       copyStore(Stmt, Store, VectorMap, ScalarMaps, NewAccesses);
       return;
     }
 
     if (auto *Unary = dyn_cast<UnaryInstruction>(Inst)) {
       copyUnaryInst(Stmt, Unary, VectorMap, ScalarMaps);
       return;
     }
void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
   // inputs.
   BasicBlock *EntryBB = R->getEntry();
   BasicBlock *EntryBBCopy = SplitBlock(Builder.GetInsertBlock(),
                                        &*Builder.GetInsertPoint(), &DT, &LI);
   EntryBBCopy->setName("polly.stmt." + EntryBB->getName() + ".entry");
   Builder.SetInsertPoint(&EntryBBCopy->front());
 
   ValueMapT &EntryBBMap = RegionMaps[EntryBBCopy];
-  generateScalarLoads(Stmt, EntryBBMap);
+  generateScalarLoads(Stmt, LTS, EntryBBMap, IdToAstExp);
 
   for (auto PI = pred_begin(EntryBB), PE = pred_end(EntryBB); PI != PE; ++PI)
     if (!R->contains(*PI))
       BlockMap[*PI] = EntryBBCopy;
 
   // Determine the original exit block of this subregion. If it the exit block
   // is also the scop's exit, it it has been changed to polly.merge_new_and_old.
   // We move one block back to find the original block. This only happens if the
for (BasicBlock *BB : SeenBlocks) {
 
     LTS[L] = SE.getUnknown(LoopPHI);
   }
 
   // Continue generating code in the exit block.
   Builder.SetInsertPoint(&*ExitBBCopy->getFirstInsertionPt());
 
   // Write values visible to other statements.
-  generateScalarStores(Stmt, LTS, ValueMap);
+  generateScalarStores(Stmt, LTS, ValueMap, IdToAstExp);
   BlockMap.clear();
   RegionMaps.clear();
   IncompletePHINodeMap.clear();
 }
 
 PHINode *RegionGenerator::buildExitPHI(MemoryAccess *MA, LoopToScevMapT &LTS,
                                        ValueMapT &BBMap, Loop *L) {
   ScopStmt *Stmt = MA->getStatement();
PHINode *RegionGenerator::buildExitPHI(MemoryAccess *MA, LoopToScevMapT &LTS,
   return NewPHI;
 }
 
 Value *RegionGenerator::getExitScalar(MemoryAccess *MA, LoopToScevMapT &LTS,
                                       ValueMapT &BBMap) {
   ScopStmt *Stmt = MA->getStatement();
   Loop *L = LI.getLoopFor(Stmt->getEntryBlock());
 
-  if (MA->isAnyPHIKind()) {
-    auto Incoming = MA->getIncoming();
-    assert(!Incoming.empty() &&
-           "PHI WRITEs must have originate from at least one incoming block");
-
+  if (!Incoming.empty()) {
     // If there is only one incoming value, we do not need to create a PHI.
     if (Incoming.size() == 1) {
       Value *OldVal = Incoming[0].second;
       return getNewValue(*Stmt, OldVal, BBMap, LTS, L);
     }
 
     return buildExitPHI(MA, LTS, BBMap, L);
   }
 
   // MK_Value accesses leaving the subregion must dominate the exit block; just
   // pass the copied value
   Value *OldVal = MA->getAccessValue();
   return getNewValue(*Stmt, OldVal, BBMap, LTS, L);
 }
 
-void RegionGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
-                                           ValueMapT &BBMap) {
+void RegionGenerator::generateScalarStores(
+    ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap,
+    __isl_keep isl_id_to_ast_expr *NewAccesses) {
   assert(Stmt.getRegion() &&
          "Block statements need to use the generateScalarStores() "
          "function in the BlockGenerator");
 
   for (MemoryAccess *MA : Stmt) {
-    if (MA->isArrayKind() || MA->isRead())
+    if ((MA->isArrayKind() && !MA->isMapped()) || MA->isRead())
       continue;
 
     Value *NewVal = getExitScalar(MA, LTS, BBMap);
-    Value *Address = getOrCreateAlloca(*MA);
+    Value *Address =
+        getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS, BBMap, NewAccesses);
     assert((!isa<Instruction>(NewVal) ||
             DT.dominates(cast<Instruction>(NewVal)->getParent(),
                          Builder.GetInsertBlock())) &&
            "Domination violation");
     assert((!isa<Instruction>(Address) ||
             DT.dominates(cast<Instruction>(Address)->getParent(),
                          Builder.GetInsertBlock())) &&
            "Domination violation");

lib/Exchange/JSONExporter.cpp

for (MemoryAccess *MA : Stmt) {
         isl_map_free(currentAccessMap);
         isl_map_free(newAccessMap);
         return false;
       }
 
       isl_id *OutId = isl_map_get_tuple_id(currentAccessMap, isl_dim_out);
       newAccessMap = isl_map_set_tuple_id(newAccessMap, isl_dim_out, OutId);
 
-      if (MA->isArrayKind()) {
+      if (MA->isArrayKind() &&
+          !MA->isMapped() /* MAPPED accesses don't have MA->getAccessInstruction() */) {
         // We keep the old alignment, thus we cannot allow accesses to memory
         // locations that were not accessed before if the alignment of the
         // access is not the default alignment.
         bool SpecialAlignment = true;
         if (LoadInst *LoadI = dyn_cast<LoadInst>(MA->getAccessInstruction())) {
           SpecialAlignment =
               DL.getABITypeAlignment(LoadI->getType()) != LoadI->getAlignment();
         } else if (StoreInst *StoreI =

test/Isl/CodeGen/doubleacc.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -polly-scops -analyze < %s | FileCheck %s -check-prefix=SCOPS
+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -polly-codegen -S < %s | FileCheck %s -check-prefix=CODEGEN
+;
+;    void foo(long n, float A[n]) {
+;      for (long i = 0; i < n; i += 1) {
+;        A[i] += 1;
+;        A[i] += 1;
+;      }
+;    }
+; XFAIL: *
+target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @foo(i32 %n, float* %A) #1 {
+entry:
+  %tmp = sext i32 %n to i64
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %cmp = icmp slt i64 %indvars.iv, %tmp
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %arrayidx = getelementptr inbounds float, float* %A, i64 %indvars.iv
+  %tmp1 = load float, float* %arrayidx, align 4
+  %add = fadd float %tmp1, 1.000000e+00
+  store float %add, float* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds float, float* %A, i64 %indvars.iv
+  %tmp2 = load float, float* %arrayidx2, align 4
+  %add3 = fadd float %tmp2, 1.000000e+00
+  store float %add3, float* %arrayidx2, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+attributes #1 = { nounwind uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+; SCOPS-LABEL: Stmt_for_body
+; SCOPS-NEXT:      Domain :=
+; SCOPS-NEXT:          [n] -> { Stmt_for_body[i0] : i0 >= 0 and i0 <= -1 + n };
+; SCOPS-NEXT:      Schedule :=
+; SCOPS-NEXT:          [n] -> { Stmt_for_body[i0] -> [i0] };
+; SCOPS-NEXT:      ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; SCOPS-NEXT:          [n] -> { Stmt_for_body[i0] -> MemRef_A[i0] };
+; SCOPS-NEXT:      MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; SCOPS-NEXT:          [n] -> { Stmt_for_body[i0] -> MemRef_A[i0] };
+; SCOPS-NEXT:      ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; SCOPS-NEXT:          [n] -> { Stmt_for_body[i0] -> MemRef_A[i0] };
+; SCOPS-NEXT:      MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; SCOPS-NEXT:          [n] -> { Stmt_for_body[i0] -> MemRef_A[i0] };
+; SCOPS-NEXT:      }
+
+; CODEGEN-LABEL: polly.stmt.for.body:
+; CODEGEN:         %tmp1_p_scalar_ = load float, float* %scevgep[[SCEV1:[0-9]*]]
+; CODEGEN:         %p_add[[ADD1:[0-9]*]] = fadd float %tmp1_p_scalar_, 1.000000e+00
+; CODEGEN:         store float %p_add[[ADD1]], float* %scevgep[[SCEV1]]
+; CODEGEN:         %tmp2_p_scalar_ = load float, float* %scevgep[[SCEV2:[0-9]*]]
+; CODEGEN:         %p_add[[ADD2:[0-9]*]] = fadd float %tmp2_p_scalar_, 1.000000e+00
+; CODEGEN:         store float %p_add[[ADD2]], float* %scevgep[[SCEV2]]
+; CODEGEN:         br i1 

test/Isl/CodeGen/invaraint_load_hoist_alignment.ll

 ; RUN: opt %loadPolly -basicaa -polly-codegen -polly-vectorizer=polly -S < %s | FileCheck %s
+
+; Invariant load hoisting removes load, but VectorBlockGenerator still generates it.
+; XFAIL: *
+
 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-n8:16:32:64"
 target triple = "x86_64-unknown-linux-gnu"
 
 @A = common global [1024 x i32] zeroinitializer, align 16
 @B = common global [1024 x i32] zeroinitializer, align 16
 
 declare i32 @foo(i32) readnone
 

test/Isl/CodeGen/simple_vec_call.ll

 ; RUN: opt %loadPolly -basicaa -polly-codegen -polly-vectorizer=polly -S < %s | FileCheck %s
+
+; Invariant load hoisting removes load, but VectorBlockGenerator still generates it.
+; XFAIL: *
+
 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-n8:16:32:64"
 
 @A = common global [1024 x float] zeroinitializer, align 16
 @B = common global [1024 x float] zeroinitializer, align 16
 
 declare float @foo(float) readnone
 
 define void @simple_vec_call() nounwind {

test/Isl/CodeGen/simple_vec_call_2.ll

 ; RUN: opt %loadPolly -basicaa -polly-codegen -polly-vectorizer=polly -dce -S < %s | FileCheck %s
+
+; Invariant load hoisting removes load, but VectorBlockGenerator still generates it.
+; XFAIL: *
+
 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-n8:16:32:64"
 
 @A = common global [1024 x float] zeroinitializer, align 16
 @B = common global [1024 x float**] zeroinitializer, align 16
 
 declare float** @foo(float) readnone
 
 define void @simple_vec_call() nounwind {

test/Isl/CodeGen/simple_vec_cast.ll

 ; RUN: opt %loadPolly -basicaa -polly-codegen -polly-vectorizer=polly -dce -S < %s | FileCheck %s -check-prefix=CHECK
+
+; Invariant load hoisting removes load, but VectorBlockGenerator still generates it.
+; XFAIL: *
+
 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-n8:16:32:64"
 
 @A = common global [1024 x float] zeroinitializer, align 16
 @B = common global [1024 x double] zeroinitializer, align 16
 
 define void @simple_vec_const() nounwind {
 bb:
   br label %bb1

test/Isl/CodeGen/simple_vec_const.ll

 ; RUN: opt %loadPolly -basicaa -polly-codegen -polly-vectorizer=polly -S < %s | FileCheck %s
 
+; Invariant load hoisting removes load, but VectorBlockGenerator still generates it.
+; XFAIL: *
+
 ;#define N 1024
 ;float A[N];
 ;float B[N];
 ;
 ;void simple_vec_const(void) {
 ;  int i;
 ;
 ;  for (i = 0; i < 4; i++)

test/Isl/CodeGen/simple_vec_ptr_ptr_ty.ll

 ; RUN: opt %loadPolly -basicaa -polly-codegen -polly-vectorizer=polly -S < %s | FileCheck %s
+
+; Invariant load hoisting removes load, but VectorBlockGenerator still generates it.
+; XFAIL: *
+
 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-n8:16:32:64"
 
 @A = common global [1024 x float**] zeroinitializer, align 16
 @B = common global [1024 x float**] zeroinitializer, align 16
 
 declare float @foo(float) readnone
 
 define void @simple_vec_call() nounwind {

test/ScopInfo/NonAffine/non_affine_loop_used_later.ll

 ; CHECK-NEXT: Context:
 ; CHECK-NEXT: [N] -> {  : -2147483648 <= N <= 2147483647 }
 ; CHECK-NEXT: Assumed Context:
 ; CHECK-NEXT: [N] -> {  :  }
 ; CHECK-NEXT: Boundary Context:
 ; CHECK-NEXT: [N] -> {  :  }
 ; CHECK-NEXT: p0: %N
 ; CHECK-NEXT: Arrays {
+; CHECK-NEXT:     i32 MemRef_A[*]; // Element size 4
 ; CHECK-NEXT:     i32 MemRef_j_0__phi; // Element size 4
 ; CHECK-NEXT:     i32 MemRef_j_0; // Element size 4
-; CHECK-NEXT:     i32 MemRef_A[*]; // Element size 4
 ; CHECK-NEXT:     i32 MemRef_j_2__phi; // Element size 4
 ; CHECK-NEXT:     i32 MemRef_j_2; // Element size 4
 ; CHECK-NEXT: }
 ; CHECK-NEXT: Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:     i32 MemRef_A[*]; // Element size 4
 ; CHECK-NEXT:     i32 MemRef_j_0__phi; // Element size 4
 ; CHECK-NEXT:     i32 MemRef_j_0; // Element size 4
-; CHECK-NEXT:     i32 MemRef_A[*]; // Element size 4
 ; CHECK-NEXT:     i32 MemRef_j_2__phi; // Element size 4
 ; CHECK-NEXT:     i32 MemRef_j_2; // Element size 4
 ; CHECK-NEXT: }
 ; CHECK-NEXT: Alias Groups (0):
 ; CHECK-NEXT:     n/a
 ; CHECK-NEXT: Statements {
 ; CHECK-NEXT:     Stmt_bb2
 ; CHECK-NEXT:         Domain :=

test/ScopInfo/delicm_GVN.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const n], int m) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        double red = A[j];
+;        for (int i = 0; i < m; i += 1) { /* reduction loop */
+;          red += 4.2;
+;          A[j] = red;
+;       }
+;    }
+
+; Nested reduction standard case
+; After GVN-Pre (LICM cannot because of possible aliasing)
+; Possible difficulties:
+; - Slot %arrayidx is overwritten in loop, indicating that %arraidx is not available for use
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction.for, label %return
+
+reduction.for:
+  %i = phi i32 [0, %parallel.for], [%i.inc, %reduction.inc]
+  %phi = phi double [%ld, %parallel.for], [%add, %reduction.inc]
+  %i.cmp = icmp slt i32 %i, %m
+  br i1 %i.cmp, label %body, label %parallel.inc
+
+body:
+  %add = fadd double %phi, 4.2
+  store double %add, double* %arrayidx
+  br label %reduction.inc
+
+reduction.inc:
+  %i.inc = add nuw nsw i32 %i, 1
+  br label %reduction.for
+
+parallel.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK:      Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'parallel.for => return' in function 'func':
+; CHECK-NEXT:     Function: func
+; CHECK-NEXT:     Region: %parallel.for---%return
+; CHECK-NEXT:     Max Loop Depth:  2
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     [n, m] -> {  : -2147483648 <= n <= 2147483647 and -2147483648 <= m <= 2147483647 }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     Boundary Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     p0: %n
+; CHECK-NEXT:     p1: %m
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         double MemRef_A[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_phi__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_phi; // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         double MemRef_A[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_phi__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_phi; // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:         Stmt_parallel_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] : 0 <= i0 <= n; Stmt_parallel_for[0] : n < 0 };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> [i0, 0, 0, 0] : i0 <= n; Stmt_parallel_for[0] -> [0, 0, 0, 0] : n < 0 };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:         Stmt_reduction_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] : 0 <= i0 < n and 0 <= i1 <= m; Stmt_reduction_for[i0, 0] : m < 0 and 0 <= i0 < n };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> [i0, 1, i1, 0] : i1 <= m; Stmt_reduction_for[i0, 0] -> [i0, 1, 0, 0] : m < 0 };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:         Stmt_body
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] : 0 <= i0 < n and 0 <= i1 < m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> [i0, 1, i1, 1] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:         Stmt_reduction_inc
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] : 0 <= i0 < n and 0 <= i1 < m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] -> [i0, 1, i1, 2] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:     }
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'func':
+; CHECK-NEXT: Invalid Scop!

test/ScopInfo/delicm_LICM_cond.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        double red = A[j];
+;        for (int i = 0; i < m; i += 1) /* reduction loop */
+;          if (i % 2 == 0)
+;            red += 4.2;
+;        A[j] = red;
+;    }
+
+; Body executed conditionally
+; Possible difficulties:
+; - %reduction.inc non-existing, where to put the store?
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m, double* noalias nonnull %B) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction.for, label %return
+
+reduction.for:
+  %i = phi i32 [0, %parallel.for], [%i.inc, %body], [%i.inc, %body.true]
+  %phi = phi double [%ld, %parallel.for], [%phi, %body], [%add, %body.true]
+  %i.cmp = icmp slt i32 %i, %m
+  %i.inc = add nuw nsw i32 %i, 1
+  br i1 %i.cmp, label %body, label %parallel.inc
+
+body:
+  %rem = and i32 %i, 1
+  %cond = icmp eq i32 %rem, 0
+  br i1 %cond, label %body.true, label %reduction.for
+
+body.true:
+  %add = fadd double %phi, 4.2
+  br label %reduction.for
+
+parallel.inc:
+  store double %phi, double* %arrayidx
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK:      Statements {
+; CHECK-NEXT:     Stmt_body
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [p_0] -> { Stmt_body[] };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [p_0] -> { Stmt_body[] -> [0] };
+; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             [p_0] -> { Stmt_body[] -> MemRef_i[] };
+; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             [p_0] -> { Stmt_body[] -> MemRef_phi[] };
+; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             [p_0] -> { Stmt_body[] -> MemRef_phi[] };
+; CHECK-NEXT:     Stmt_body_true
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [p_0] -> { Stmt_body_true[] : p_0 = 0 };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [p_0] -> { Stmt_body_true[] -> [1] };
+; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             [p_0] -> { Stmt_body_true[] -> MemRef_phi[] };
+; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             [p_0] -> { Stmt_body_true[] -> MemRef_i[] };
+; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             [p_0] -> { Stmt_body_true[] -> MemRef_phi[] };
+; CHECK-NEXT: }

test/ScopInfo/delicm_LICM_conditional_reductions.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m, int c) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        double red = A[j];
+;        if (c) {
+;          for (int i = 0; i < m; i += 1) /* reduction loop */
+;            red += 4.2;
+;        else {
+;          for (int i = 0; i < m; i += 1) /* reduction loop */
+;            red *= 1.2;
+;        }
+;        A[j] = red;
+;    }
+
+; Nested reduction standard case
+; After LICM 
+; Possible difficulties:
+; - Two independent loop-carried phis can reuse the same %arrayidx (to be distinguished from the case where it can't)
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m, i32 %c) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %condition, label %return
+
+condition:
+  %ccmp = icmp ne i32 %c, 0
+  br i1 %ccmp, label %reduction1.for, label %reduction2.for
+
+reduction1.for:
+  %i1 = phi i32 [0, %condition], [%i1.inc, %reduction1.inc]
+  %phi1 = phi double [%ld, %condition], [%add, %reduction1.inc]
+  %i1.cmp = icmp slt i32 %i1, %m
+  br i1 %i1.cmp, label %body1, label %parallel.inc
+
+body1:
+  %add = fadd double %phi1, 4.2
+  br label %reduction1.inc
+
+reduction1.inc:
+  %i1.inc = add nuw nsw i32 %i1, 1
+  br label %reduction1.for
+  
+reduction2.for:
+  %i2 = phi i32 [0, %condition], [%i2.inc, %reduction2.inc]
+  %phi2 = phi double [%ld, %condition], [%mul, %reduction2.inc]
+  %i2.cmp = icmp slt i32 %i2, %m
+  br i1 %i2.cmp, label %body2, label %parallel.inc
+
+body2:
+  %mul = fmul double %phi2, 1.2
+  br label %reduction2.inc
+
+reduction2.inc:
+  %i2.inc = add nuw nsw i32 %i2, 1
+  br label %reduction2.for
+
+parallel.inc:
+  %condphi = phi double [%phi1, %reduction1.for], [%phi2, %reduction2.for]
+  store double %condphi, double* %arrayidx
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK:      Statements {
+; CHECK-NEXT:     Stmt_body1
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [n, c, m] -> { Stmt_body1[i0, i1] : 0 <= i0 < n and 0 <= i1 < m and (c < 0 or c > 0) };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [n, c, m] -> { Stmt_body1[i0, i1] -> [i0, 1, i1] : c < 0 or c > 0 };
+; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:             [n, c, m] -> { Stmt_body1[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:             [n, c, m] -> { Stmt_body1[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:     Stmt_body2
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [n, c, m] -> { Stmt_body2[i0, i1] : c = 0 and 0 <= i0 < n and 0 <= i1 < m };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [n, c, m] -> { Stmt_body2[i0, i1] -> [i0, 0, i1] };
+; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:             [n, c, m] -> { Stmt_body2[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:             [n, c, m] -> { Stmt_body2[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT: }

test/ScopInfo/delicm_LICM_consecutive_reductions.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        double red = A[j];
+;        for (int i1 = 0; i1 < m; i1 += 1) /* reduction loop */
+;          red += 4.2;
+;        for (int i2 = 0; i2 < m; i2 += 1) /* reduction loop */
+;          red += 5.3;
+;        A[j] = red;
+;    }
+
+; Two reductions executed sequentially 
+; Possible difficulties:
+; - Two loop-carrying phis that can use the same %arrayidx
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction1.for, label %return
+
+reduction1.for:
+  %i1 = phi i32 [0, %parallel.for], [%i1.inc, %reduction1.inc]
+  %phi1 = phi double [%ld, %parallel.for], [%add1, %reduction1.inc]
+  %i1.cmp = icmp slt i32 %i1, %m
+  br i1 %i1.cmp, label %body1, label %reduction2.for
+
+body1:
+  %add1 = fadd double %phi1, 4.2
+  br label %reduction1.inc
+
+reduction1.inc:
+  %i1.inc = add nuw nsw i32 %i1, 1
+  br label %reduction1.for
+
+reduction2.for:
+  %i2 = phi i32 [0, %reduction1.for], [%i2.inc, %reduction2.inc]
+  %phi2 = phi double [%phi1, %reduction1.for], [%add2, %reduction2.inc]
+  %i2.cmp = icmp slt i32 %i2, %m
+  br i1 %i2.cmp, label %body2, label %parallel.inc
+
+body2:
+  %add2 = fadd double %phi2, 5.3
+  br label %reduction2.inc
+
+reduction2.inc:
+  %i2.inc = add nuw nsw i32 %i2, 1
+  br label %reduction2.for
+
+parallel.inc:
+  store double %phi2, double* %arrayidx
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK:      Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction2.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction1.for => reduction2.for' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'parallel.for => return' in function 'func':
+; CHECK-NEXT:     Function: func
+; CHECK-NEXT:     Region: %parallel.for---%return
+; CHECK-NEXT:     Max Loop Depth:  2
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     [n, m] -> {  : -2147483648 <= n <= 2147483647 and -2147483648 <= m <= 2147483647 }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     Boundary Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     p0: %n
+; CHECK-NEXT:     p1: %m
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         double MemRef_A[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_phi1__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_add1; // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         double MemRef_A[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_phi1__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_add1; // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:         Stmt_parallel_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] : 0 <= i0 <= n; Stmt_parallel_for[0] : n < 0 };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> [i0, 0, 0, 0] : i0 <= n; Stmt_parallel_for[0] -> [0, 0, 0, 0] : n < 0 };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_phi1__phi[] };
+; CHECK-NEXT:         Stmt_reduction1_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction1_for[i0, i1] : 0 <= i0 < n and 0 <= i1 <= m; Stmt_reduction1_for[i0, 0] : m < 0 and 0 <= i0 < n };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction1_for[i0, i1] -> [i0, 1, i1, 0] : i1 <= m; Stmt_reduction1_for[i0, 0] -> [i0, 1, 0, 0] : m < 0 };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction1_for[i0, i1] -> MemRef_phi1__phi[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction1_for[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:         Stmt_body1
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body1[i0, i1] : 0 <= i0 < n and 0 <= i1 < m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body1[i0, i1] -> [i0, 1, i1, 1] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body1[i0, i1] -> MemRef_add1[] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body1[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:         Stmt_reduction1_inc
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction1_inc[i0, i1] : 0 <= i0 < n and 0 <= i1 < m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction1_inc[i0, i1] -> [i0, 1, i1, 2] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction1_inc[i0, i1] -> MemRef_add1[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction1_inc[i0, i1] -> MemRef_phi1__phi[] };
+; CHECK-NEXT:         Stmt_body2
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body2[i0, i1] : 0 <= i0 < n and 0 <= i1 < m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body2[i0, i1] -> [i0, 2, i1, 0] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body2[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body2[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:     }
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'func':
+; CHECK-NEXT: Invalid Scop!

test/ScopInfo/delicm_LICM_loads.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m, double B[static const restrict n], double C[static const restrict n]) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        B[j] = A[j];
+;        double red = A[j];
+;        red += 5.1;
+;        for (int i = 0; i < m; i += 1) /* reduction loop */
+;          red += 4.2;
+;        A[j] = red;
+;        C[j] = A[j];
+;    }
+
+; Value of A[j] used, outside of reduction
+; Possible difficulties:
+; - Distinguish from case where uses of A[j] is between the reduction intial load and writeback.
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m, double* noalias nonnull %B, double* noalias nonnull %C) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %arrayidxB = getelementptr inbounds double, double* %B, i32 %j
+  %arrayidxC = getelementptr inbounds double, double* %C, i32 %j
+  %ld = load double, double* %arrayidx
+  %prep = fadd double %ld, 5.1
+  store double %ld, double* %arrayidxB
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction.for, label %return
+
+reduction.for:
+  %i = phi i32 [0, %parallel.for], [%i.inc, %reduction.inc]
+  %phi = phi double [%ld, %parallel.for], [%add, %reduction.inc]
+  %i.cmp = icmp slt i32 %i, %m
+  br i1 %i.cmp, label %body, label %parallel.inc
+
+body:
+  %add = fadd double %phi, 4.2
+  br label %reduction.inc
+
+reduction.inc:
+  %i.inc = add nuw nsw i32 %i, 1
+  br label %reduction.for
+
+parallel.inc:
+  store double %phi, double* %arrayidx
+  store double %phi, double* %arrayidxC
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK:      Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'parallel.for => return' in function 'func':
+; CHECK-NEXT:     Function: func
+; CHECK-NEXT:     Region: %parallel.for---%return
+; CHECK-NEXT:     Max Loop Depth:  2
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     [n, m] -> {  : -2147483648 <= n <= 2147483647 and -2147483648 <= m <= 2147483647 }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     Boundary Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     p0: %n
+; CHECK-NEXT:     p1: %m
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         double MemRef_A[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_B[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_C[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_phi__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_add; // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         double MemRef_A[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_B[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_C[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_phi__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_add; // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:         Stmt_parallel_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] : 0 <= i0 <= n; Stmt_parallel_for[0] : n < 0 };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> [i0, 0, 0, 0] : i0 <= n; Stmt_parallel_for[0] -> [0, 0, 0, 0] : n < 0 };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_B[i0] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:         Stmt_reduction_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] : 0 <= i0 < n and 0 <= i1 <= m; Stmt_reduction_for[i0, 0] : m < 0 and 0 <= i0 < n };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> [i0, 1, i1, 0] : i1 <= m; Stmt_reduction_for[i0, 0] -> [i0, 1, 0, 0] : m < 0 };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:         Stmt_body
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] : 0 <= i0 < n and 0 <= i1 < m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> [i0, 1, i1, 1] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:         Stmt_reduction_inc
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] : 0 <= i0 < n and 0 <= i1 < m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] -> [i0, 1, i1, 2] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:     }
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'func':
+; CHECK-NEXT: Invalid Scop!

test/ScopInfo/delicm_LICM_nested_reductions.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        double red = A[j];
+;        for (int i = 0; i < m; i += 1) /* reduction loop */
+;          for (int k = 0; k < m; k += 1) /* reduction loop */
+;            red += 4.2;
+;        A[j] = red;
+;    }
+
+; Two nested loop-carried phis able to reuse the same %arrayidx
+; Possible difficulties:
+; - Identify that both phis can use the same %arrayidx as scratch space
+; - Needs edge-level writes
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction_outer.for, label %return
+
+reduction_outer.for:
+  %i_outer = phi i32 [0, %parallel.for], [%i_outer.inc, %reduction_outer.inc]
+  %phi_outer = phi double [%ld, %parallel.for], [%phi_inner, %reduction_outer.inc]
+  %i_outer.cmp = icmp slt i32 %i_outer, %m
+  br i1 %i_outer.cmp, label %reduction_inner.for, label %parallel.inc
+
+reduction_inner.for:
+  %i_inner = phi i32 [0, %reduction_outer.for], [%i_inner.inc, %reduction_inner.inc]
+  %phi_inner = phi double [%ld, %reduction_outer.for], [%add, %reduction_inner.inc]
+  %i_inner.cmp = icmp slt i32 %i_inner, %m
+  br i1 %i_inner.cmp, label %body, label %reduction_outer.inc
+
+body:
+  %add = fadd double %phi_inner, 4.2
+  br label %reduction_inner.inc
+
+reduction_inner.inc:
+  %i_inner.inc = add nuw nsw i32 %i_inner, 1
+  br label %reduction_inner.for
+
+reduction_outer.inc:
+  %i_outer.inc = add nuw nsw i32 %i_outer, 1
+  br label %reduction_outer.for
+
+parallel.inc:
+  store double %phi_outer, double* %arrayidx
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK:      Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction_inner.for => reduction_outer.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction_outer.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'parallel.for => return' in function 'func':
+; CHECK-NEXT:     Function: func
+; CHECK-NEXT:     Region: %parallel.for---%return
+; CHECK-NEXT:     Max Loop Depth:  3
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     [n, m] -> {  : -2147483648 <= n <= 2147483647 and -2147483648 <= m <= 2147483647 }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     Boundary Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     p0: %n
+; CHECK-NEXT:     p1: %m
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         double MemRef_A[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_phi_outer__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_ld; [BasePtrOrigin: MemRef_A] // Element size 8
+; CHECK-NEXT:         double MemRef_phi_inner__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_phi_inner; // Element size 8
+; CHECK-NEXT:         double MemRef_add; // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         double MemRef_A[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_phi_outer__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_ld; [BasePtrOrigin: MemRef_A] // Element size 8
+; CHECK-NEXT:         double MemRef_phi_inner__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_phi_inner; // Element size 8
+; CHECK-NEXT:         double MemRef_add; // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:         Stmt_parallel_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] : 0 <= i0 <= n; Stmt_parallel_for[0] : n < 0 };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> [i0, 0, 0, 0, 0, 0] : i0 <= n; Stmt_parallel_for[0] -> [0, 0, 0, 0, 0, 0] : n < 0 };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_phi_outer__phi[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_ld[] };
+; CHECK-NEXT:         Stmt_reduction_outer_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_outer_for[i0, i1] : 0 <= i0 < n and 0 <= i1 <= m; Stmt_reduction_outer_for[i0, 0] : m < 0 and 0 <= i0 < n };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_outer_for[i0, i1] -> [i0, 1, i1, 0, 0, 0] : i1 <= m; Stmt_reduction_outer_for[i0, 0] -> [i0, 1, 0, 0, 0, 0] : m < 0 };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_outer_for[i0, i1] -> MemRef_phi_outer__phi[] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_outer_for[i0, i1] -> MemRef_ld[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_outer_for[i0, i1] -> MemRef_phi_inner__phi[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_outer_for[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:         Stmt_reduction_inner_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inner_for[i0, i1, i2] : 0 <= i0 < n and 0 <= i1 < m and 0 <= i2 <= m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inner_for[i0, i1, i2] -> [i0, 1, i1, 1, i2, 0] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inner_for[i0, i1, i2] -> MemRef_phi_inner[] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inner_for[i0, i1, i2] -> MemRef_phi_inner__phi[] };
+; CHECK-NEXT:         Stmt_body
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1, i2] : 0 <= i0 < n and 0 <= i1 < m and 0 <= i2 < m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1, i2] -> [i0, 1, i1, 1, i2, 1] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1, i2] -> MemRef_add[] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1, i2] -> MemRef_phi_inner[] };
+; CHECK-NEXT:         Stmt_reduction_inner_inc
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inner_inc[i0, i1, i2] : 0 <= i0 < n and 0 <= i1 < m and 0 <= i2 < m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inner_inc[i0, i1, i2] -> [i0, 1, i1, 1, i2, 2] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inner_inc[i0, i1, i2] -> MemRef_add[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inner_inc[i0, i1, i2] -> MemRef_phi_inner__phi[] };
+; CHECK-NEXT:         Stmt_reduction_outer_inc
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_outer_inc[i0, i1] : 0 <= i0 < n and 0 <= i1 < m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_outer_inc[i0, i1] -> [i0, 1, i1, 2, 0, 0] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_outer_inc[i0, i1] -> MemRef_phi_inner[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_outer_inc[i0, i1] -> MemRef_phi_outer__phi[] };
+; CHECK-NEXT:     }
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'func':
+; CHECK-NEXT: Invalid Scop!

test/ScopInfo/delicm_LICM_nonaffine.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        double red = A[j];
+;        for (int i = 0; i < m; i += 1) /* reduction loop */
+;          if (i*i == 0)
+;            red += 4.2;
+;        A[j] = red;
+;    }
+
+; Body is non-affine subregion
+; Possible difficulties:
+; - Can move through non-affine subregions?
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction.for, label %return
+
+reduction.for:
+  %i = phi i32 [0, %parallel.for], [%i.inc, %body], [%i.inc, %body.true]
+  %phi = phi double [%ld, %parallel.for], [%phi, %body], [%add, %body.true]
+  %i.cmp = icmp slt i32 %i, %m
+  %i.inc = add nuw nsw i32 %i, 1
+  br i1 %i.cmp, label %body, label %parallel.inc
+
+body:
+  %sqr = mul i32 %i, %i
+  %cond = icmp eq i32 %sqr, 0
+  br i1 %cond, label %body.true, label %reduction.for
+
+body.true:
+  %add = fadd double %phi, 4.2
+  br label %reduction.for
+
+parallel.inc:
+  store double %phi, double* %arrayidx
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK:      Statements {
+; CHECK-NEXT:     Stmt_body__TO__reduction_for
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             { Stmt_body__TO__reduction_for[] };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             { Stmt_body__TO__reduction_for[] -> [] };
+; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             { Stmt_body__TO__reduction_for[] -> MemRef_phi[] };
+; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             { Stmt_body__TO__reduction_for[] -> MemRef_i[] };
+; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             { Stmt_body__TO__reduction_for[] -> MemRef_phi[] };
+; CHECK-NEXT: }

test/ScopInfo/delicm_LICM_reduction.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        double red = A[j];
+;        for (int i = 0; i < m; i += 1) /* reduction loop */
+;          red += 4.2;
+;        A[j] = red;
+;    }
+
+; Nested reduction standard case; After LICM 
+; Possible difficulties:
+; - Put the store into %body or $reduction.inc
+; - Replace %phi in %body with a load, knowing that after the store has been placed in %body or %reduction.inc, it contains %phi
+; - Except the store, all instructions are "rematerializable", when applying the same logic to the loop-carried %phi, so the naive algorithm might try to move all instructions into %parallel.inc and remove the one in %body
+; - There can be no mapped store added to parallel.for (for the %phi) because it is not postdominated by the store  
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction.for, label %return
+
+reduction.for:
+  %i = phi i32 [0, %parallel.for], [%i.inc, %reduction.inc]
+  %phi = phi double [%ld, %parallel.for], [%add, %reduction.inc]
+  %i.cmp = icmp slt i32 %i, %m
+  br i1 %i.cmp, label %body, label %parallel.inc
+
+body:
+  %add = fadd double %phi, 4.2
+  br label %reduction.inc
+
+reduction.inc:
+  %i.inc = add nuw nsw i32 %i, 1
+  br label %reduction.for
+
+parallel.inc:
+  store double %phi, double* %arrayidx
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK:      Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'parallel.for => return' in function 'func':
+; CHECK-NEXT:     Function: func
+; CHECK-NEXT:     Region: %parallel.for---%return
+; CHECK-NEXT:     Max Loop Depth:  2
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     [n, m] -> {  : -2147483648 <= n <= 2147483647 and -2147483648 <= m <= 2147483647 }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     Boundary Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     p0: %n
+; CHECK-NEXT:     p1: %m
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         double MemRef_A[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_phi__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_add; // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         double MemRef_A[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_phi__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_add; // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:         Stmt_parallel_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] : 0 <= i0 <= n; Stmt_parallel_for[0] : n < 0 };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> [i0, 0, 0, 0] : i0 <= n; Stmt_parallel_for[0] -> [0, 0, 0, 0] : n < 0 };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:         Stmt_reduction_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] : 0 <= i0 < n and 0 <= i1 <= m; Stmt_reduction_for[i0, 0] : m < 0 and 0 <= i0 < n };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> [i0, 1, i1, 0] : i1 <= m; Stmt_reduction_for[i0, 0] -> [i0, 1, 0, 0] : m < 0 };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:         Stmt_body
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] : 0 <= i0 < n and 0 <= i1 < m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> [i0, 1, i1, 1] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:         Stmt_reduction_inc
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] : 0 <= i0 < n and 0 <= i1 < m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] -> [i0, 1, i1, 2] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:     }
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'func':
+; CHECK-NEXT: Invalid Scop!

test/ScopInfo/delicm_LICM_split.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m, double B[static const restrict m]) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        double red = A[j];
+;        for (int i = 0; i < m; i += 1) { /* reduction loop */
+;          red += B[i]; /* assume B[i] non-rematerializable */
+;          <split>
+;          red += B[m-i]; /* assume B[m-i] non-rematerializable */
+;        }
+;        A[j] = red;
+;    }
+
+; Body is split into multiple blocks
+; Some more complicated could between body and body.split might keep the block from being joind into one
+; Possible difficulties:
+; - Does body and body.split get their own stores?
+; - If not, does a scalar dependency between them remain?
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m, double* noalias nonnull %B) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction.for, label %return
+
+reduction.for:
+  %i = phi i32 [0, %parallel.for], [%i.inc, %reduction.inc]
+  %phi = phi double [%ld, %parallel.for], [%add2, %reduction.inc]
+  %i.cmp = icmp slt i32 %i, %m
+  br i1 %i.cmp, label %body, label %parallel.inc
+
+body:
+  %arrayidxB1 = getelementptr inbounds double, double* %B, i32 %i
+  %B1 = load double, double* %arrayidxB1  ; assume non-rematerializable
+  %add1 = fadd double %phi, %B1
+  br label %body.split
+
+body.split:
+  %minusi = sub nuw nsw i32 %m, %i
+  %arrayidxB2 = getelementptr inbounds double, double* %B, i32 %minusi
+  %B2 = load double, double* %arrayidxB2  ; assume non-rematerializable
+  %add2 = fadd double %add1, %B2
+  br label %reduction.inc
+
+reduction.inc:
+  %i.inc = add nuw nsw i32 %i, 1
+  br label %reduction.for
+  
+parallel.inc:
+  store double %phi, double* %arrayidx
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK:      Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'parallel.for => return' in function 'func':
+; CHECK-NEXT:     Function: func
+; CHECK-NEXT:     Region: %parallel.for---%return
+; CHECK-NEXT:     Max Loop Depth:  2
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     [n, m] -> {  : -2147483648 <= n <= 2147483647 and -2147483648 <= m <= 2147483647 }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     Boundary Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     p0: %n
+; CHECK-NEXT:     p1: %m
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         double MemRef_A[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_B[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_phi__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_add1; // Element size 8
+; CHECK-NEXT:         double MemRef_add2; // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         double MemRef_A[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_B[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_phi__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_add1; // Element size 8
+; CHECK-NEXT:         double MemRef_add2; // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:         Stmt_parallel_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] : 0 <= i0 <= n; Stmt_parallel_for[0] : n < 0 };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> [i0, 0, 0, 0] : i0 <= n; Stmt_parallel_for[0] -> [0, 0, 0, 0] : n < 0 };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:         Stmt_reduction_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] : 0 <= i0 < n and 0 <= i1 <= m; Stmt_reduction_for[i0, 0] : m < 0 and 0 <= i0 < n };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> [i0, 1, i1, 0] : i1 <= m; Stmt_reduction_for[i0, 0] -> [i0, 1, 0, 0] : m < 0 };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:         Stmt_body
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] : 0 <= i0 < n and 0 <= i1 < m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> [i0, 1, i1, 1] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_B[i1] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_add1[] };
+; CHECK-NEXT:         Stmt_body_split
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body_split[i0, i1] : 0 <= i0 < n and 0 <= i1 < m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body_split[i0, i1] -> [i0, 1, i1, 2] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body_split[i0, i1] -> MemRef_add2[] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body_split[i0, i1] -> MemRef_B[m - i1] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body_split[i0, i1] -> MemRef_add1[] };
+; CHECK-NEXT:         Stmt_reduction_inc
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] : 0 <= i0 < n and 0 <= i1 < m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] -> [i0, 1, i1, 3] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] -> MemRef_add2[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:     }
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'func':
+; CHECK-NEXT: Invalid Scop!

test/ScopInfo/delicm_LICM_two_reductions.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        double red1 = A[j];
+;        double red2 = 0.0;
+;        for (int i = 0; i < m; i += 1) { /* reduction loop */
+;          red1 += 4.2;
+;          red2 += 2.4;
+;        }
+;        A[j] = red1 + red2;
+;    }
+
+; Two reductions in the same loop 
+; Possible difficulties:
+; - Cannot use same %arraryidx for same loop-carried phi; must identify situation and choose one.
+; - If doing global analysis first, must somehow mark already used %arrayidx to avoid use by other reduction
+; - If transforming while doing analysis, analysis for second phi must work on updated MemoryAccesses
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction.for, label %return
+
+reduction.for:
+  %i = phi i32 [0, %parallel.for], [%i.inc, %reduction.inc]
+  %phi1 = phi double [%ld, %parallel.for], [%add1, %reduction.inc]
+  %phi2 = phi double [0.0, %parallel.for], [%add2, %reduction.inc]
+  %i.cmp = icmp slt i32 %i, %m
+  br i1 %i.cmp, label %body, label %parallel.inc
+
+body:
+  %add1 = fadd double %phi1, 4.2
+  %add2 = fadd double %phi2, 2.4
+  br label %reduction.inc
+
+reduction.inc:
+  %i.inc = add nuw nsw i32 %i, 1
+  br label %reduction.for
+
+parallel.inc:
+  %sum = fadd double %phi1, %phi2
+  store double %sum, double* %arrayidx
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+
+; CHECK:      Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'parallel.for => return' in function 'func':
+; CHECK-NEXT:     Function: func
+; CHECK-NEXT:     Region: %parallel.for---%return
+; CHECK-NEXT:     Max Loop Depth:  2
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     [n, m] -> {  : -2147483648 <= n <= 2147483647 and -2147483648 <= m <= 2147483647 }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     Boundary Context:
+; CHECK-NEXT:     [n, m] -> {  :  }
+; CHECK-NEXT:     p0: %n
+; CHECK-NEXT:     p1: %m
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         double MemRef_A[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_phi1__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_phi2__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_phi1; // Element size 8
+; CHECK-NEXT:         double MemRef_add1; // Element size 8
+; CHECK-NEXT:         double MemRef_add2; // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         double MemRef_A[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_phi1__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_phi2__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_phi1; // Element size 8
+; CHECK-NEXT:         double MemRef_add1; // Element size 8
+; CHECK-NEXT:         double MemRef_add2; // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:         Stmt_parallel_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] : 0 <= i0 <= n; Stmt_parallel_for[0] : n < 0 };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> [i0, 0, 0, 0] : i0 <= n; Stmt_parallel_for[0] -> [0, 0, 0, 0] : n < 0 };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_phi1__phi[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_for[i0] -> MemRef_phi2__phi[] };
+; CHECK-NEXT:         Stmt_reduction_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] : 0 <= i0 < n and 0 <= i1 <= m; Stmt_reduction_for[i0, 0] : m < 0 and 0 <= i0 < n };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> [i0, 1, i1, 0] : i1 <= m; Stmt_reduction_for[i0, 0] -> [i0, 1, 0, 0] : m < 0 };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> MemRef_phi1__phi[] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> MemRef_phi2__phi[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> MemRef_phi1[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:         Stmt_body
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] : 0 <= i0 < n and 0 <= i1 < m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> [i0, 1, i1, 1] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_add1[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_add2[] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_phi1[] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:         Stmt_reduction_inc
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] : 0 <= i0 < n and 0 <= i1 < m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] -> [i0, 1, i1, 2] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] -> MemRef_add1[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] -> MemRef_phi1__phi[] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] -> MemRef_add2[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_reduction_inc[i0, i1] -> MemRef_phi2__phi[] };
+; CHECK-NEXT:         Stmt_parallel_inc
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_inc[i0] : 0 <= i0 < n };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_inc[i0] -> [i0, 2, 0, 0] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_inc[i0] -> MemRef_phi1[] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_inc[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n, m] -> { Stmt_parallel_inc[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:     }
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'func':
+; CHECK-NEXT: Invalid Scop!

test/ScopInfo/delicm_LICM_writes.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m, int k) {
+;      for (int j = 0; j < n; j += 1) { /* parallel loop */
+;        A[k] = 2.1;
+;        double red = A[j];
+;        for (int i = 0; i < m; i += 1) /* reduction loop */
+;          red += 4.2;
+;        A[j] = red;
+;        A[k] = 2.3;
+;    }
+
+; %arraidx possibly overwritten, but not in anything relevant for the reduction
+; Possible difficulties:
+; - Store of 2.1 might overwrite A[j] if order reversed in %parallel.for (distinguish the two cases)
+; - Store of 2.3 might overwrite A[j]; distinguish from case where order is reversed in %parallel.inc
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m, i32 %k) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %arrayidxk = getelementptr inbounds double, double* %A, i32 %k
+  store double 2.1, double* %arrayidxk
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction.for, label %return
+
+reduction.for:
+  %i = phi i32 [0, %parallel.for], [%i.inc, %reduction.inc]
+  %phi = phi double [%ld, %parallel.for], [%add, %reduction.inc]
+  %i.cmp = icmp slt i32 %i, %m
+  br i1 %i.cmp, label %body, label %parallel.inc
+
+body:
+  %add = fadd double %phi, 4.2
+  br label %reduction.inc
+
+reduction.inc:
+  %i.inc = add nuw nsw i32 %i, 1
+  br label %reduction.for
+
+parallel.inc:
+  store double %phi, double* %arrayidx
+  store double 2.3, double* %arrayidxk
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+; CHECK:      Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'reduction.for => parallel.inc' in function 'func':
+; CHECK-NEXT: Invalid Scop!
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'parallel.for => return' in function 'func':
+; CHECK-NEXT:     Function: func
+; CHECK-NEXT:     Region: %parallel.for---%return
+; CHECK-NEXT:     Max Loop Depth:  2
+; CHECK-NEXT:     Invariant Accesses: {
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Context:
+; CHECK-NEXT:     [n, m, k] -> {  : -2147483648 <= n <= 2147483647 and -2147483648 <= m <= 2147483647 and -2147483648 <= k <= 2147483647 }
+; CHECK-NEXT:     Assumed Context:
+; CHECK-NEXT:     [n, m, k] -> {  :  }
+; CHECK-NEXT:     Boundary Context:
+; CHECK-NEXT:     [n, m, k] -> {  :  }
+; CHECK-NEXT:     p0: %n
+; CHECK-NEXT:     p1: %m
+; CHECK-NEXT:     p2: %k
+; CHECK-NEXT:     Arrays {
+; CHECK-NEXT:         double MemRef_A[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_phi__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_add; // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Arrays (Bounds as pw_affs) {
+; CHECK-NEXT:         double MemRef_A[*]; // Element size 8
+; CHECK-NEXT:         double MemRef_phi__phi; // Element size 8
+; CHECK-NEXT:         double MemRef_add; // Element size 8
+; CHECK-NEXT:     }
+; CHECK-NEXT:     Alias Groups (0):
+; CHECK-NEXT:         n/a
+; CHECK-NEXT:     Statements {
+; CHECK-NEXT:         Stmt_parallel_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_parallel_for[i0] : 0 <= i0 <= n; Stmt_parallel_for[0] : n < 0 };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_parallel_for[i0] -> [i0, 0, 0, 0] : i0 <= n; Stmt_parallel_for[0] -> [0, 0, 0, 0] : n < 0 };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_parallel_for[i0] -> MemRef_A[k] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_parallel_for[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_parallel_for[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:         Stmt_reduction_for
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_reduction_for[i0, i1] : 0 <= i0 < n and 0 <= i1 <= m; Stmt_reduction_for[i0, 0] : m < 0 and 0 <= i0 < n };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_reduction_for[i0, i1] -> [i0, 1, i1, 0] : i1 <= m; Stmt_reduction_for[i0, 0] -> [i0, 1, 0, 0] : m < 0 };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:         Stmt_body
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_body[i0, i1] : 0 <= i0 < n and 0 <= i1 < m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_body[i0, i1] -> [i0, 1, i1, 1] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_body[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:         Stmt_reduction_inc
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_reduction_inc[i0, i1] : 0 <= i0 < n and 0 <= i1 < m };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_reduction_inc[i0, i1] -> [i0, 1, i1, 2] };
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_reduction_inc[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:         Stmt_parallel_inc
+; CHECK-NEXT:             Domain :=
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_parallel_inc[i0] : 0 <= i0 < n };
+; CHECK-NEXT:             Schedule :=
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_parallel_inc[i0] -> [i0, 2, 0, 0] };
+; CHECK-NEXT:             MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n, m, k] -> { Stmt_parallel_inc[i0] -> MemRef_A[k] };
+; CHECK-NEXT:     }
+; CHECK-NEXT: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'func':
+; CHECK-NEXT: Invalid Scop!

test/ScopInfo/delicm_base.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    void func(int n, double A[static const restrict n], int m) {
+;      for (int j = 0; j < n; j += 1) /* parallel loop */
+;        for (int i = 0; i < m; i += 1) /* reduction loop */
+;          A[j] += 4.2;
+;    }
+;
+
+; Nested reduction standard case
+; Before DeLICM/LICM-Pre
+; Possible difficulties:
+; - No changes, code not to be modified
+
+define void @func(i32 %n, double* noalias nonnull %A, i32 %m) {
+entry:
+  br label %parallel.for
+
+parallel.for:
+  %j = phi i32 [0, %entry], [%j.inc, %parallel.inc]
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %reduction.for, label %return
+
+reduction.for:
+  %i = phi i32 [0, %parallel.for], [%i.inc, %reduction.inc]
+  %i.cmp = icmp slt i32 %i, %m
+  br i1 %i.cmp, label %body, label %parallel.inc
+
+body:
+  %arrayidx = getelementptr inbounds double, double* %A, i32 %j
+  %ld = load double, double* %arrayidx
+  %add = fadd double %ld, 4.2
+  store double %add, double* %arrayidx
+  br label %reduction.inc
+
+reduction.inc:
+  %i.inc = add nuw nsw i32 %i, 1
+  br label %reduction.for
+
+parallel.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %parallel.for
+
+return:
+  ret void
+}
+
+; CHECK:      Statements {
+; CHECK-NEXT:     Stmt_body
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [n, m] -> { Stmt_body[i0, i1] : 0 <= i0 < n and 0 <= i1 < m };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [n, m] -> { Stmt_body[i0, i1] -> [i0, i1] };
+; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n, m] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n, m] -> { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:     }

test/ScopInfo/licm_reduction.ll

 ; RUN: opt %loadPolly -basicaa -loop-rotate -indvars       -polly-prepare -polly-scops -analyze < %s | FileCheck %s
 ; RUN: opt %loadPolly -basicaa -loop-rotate -indvars -licm -polly-prepare -polly-scops -analyze < %s | FileCheck %s
 ;
-; XFAIL: *
-;
 ;    void test(int n, double B[static const restrict n], int j) {
 ;      for (int i = 0; i < n; i += 1) {
 ;        B[j] += i;
 ;      }
 ;    }
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 

 for.inc:                                          ; preds = %for.body
   %add1 = add nuw nsw i32 %i.0, 1
   br label %for.cond
 
 for.end:                                          ; preds = %for.cond
   ret void
 }
 
-
-; CHECK: Statements {
-; CHECK:     Stmt_for_body
-; CHECK-DAG:     ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
-; CHECK-NEXT:        [n, j] -> { Stmt_for_body[i0] -> MemRef_B[j] };
-; CHECK-DAG:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
-; CHECK-NEXT:        [n, j] -> { Stmt_for_body[i0] -> MemRef_B[j] };
-; CHECK: }
+; CHECK:      Statements {
+; CHECK-NEXT:     Stmt_for_body
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [n, j] -> { Stmt_for_body[i0] : 0 <= i0 < n };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [n, j] -> { Stmt_for_body[i0] -> [i0] };
+; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n, j] -> { Stmt_for_body[i0] -> MemRef_B[j] };
+; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n, j] -> { Stmt_for_body[i0] -> MemRef_B[j] };
+; CHECK-NEXT: }

test/ScopInfo/pointer-used-as-base-pointer-and-scalar-read.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 
 ; In this test case we pass a pointer %A into a PHI node and also use this
 ; pointer as base pointer of an array store. As a result, we get both scalar
 ; and array memory accesses to A[] and A[0].
 
 ; CHECK:      Arrays {
 ; CHECK-NEXT:     float MemRef_A[*]; // Element size 4
-; CHECK-NEXT:     float* MemRef_x__phi; // Element size 8
 ; CHECK-NEXT:     float* MemRef_C[*]; // Element size 8
+; CHECK-NEXT:     float* MemRef_x__phi; // Element size 8
 ; CHECK-NEXT: }
 ; CHECK:      Arrays (Bounds as pw_affs) {
 ; CHECK-NEXT:     float MemRef_A[*]; // Element size 4
-; CHECK-NEXT:     float* MemRef_x__phi; // Element size 8
 ; CHECK-NEXT:     float* MemRef_C[*]; // Element size 8
+; CHECK-NEXT:     float* MemRef_x__phi; // Element size 8
 ; CHECK-NEXT: }
 ; CHECK:      Alias Groups (0):
 ; CHECK-NEXT:     n/a
 ; CHECK:      Statements {
 ; CHECK-NEXT:     Stmt_then
 ; CHECK-NEXT:         Domain :=
 ; CHECK-NEXT:             [p] -> { Stmt_then[i0] : p = 32 and 0 <= i0 <= 999 };
 ; CHECK-NEXT:         Schedule :=

test/ScopInfo/same-base-address-scalar-and-array.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 ;
 ; Verify we introduce two ScopArrayInfo objects (or virtual arrays) for the %out variable
 ; as it is used as a memory base pointer (%0) but also as a scalar (%out.addr.0.lcssa).
 ;
 ; CHECK:         Arrays {
-; CHECK-NEXT:        float* MemRef_out_addr_0_lcssa; // Element size 8
 ; CHECK-NEXT:        float MemRef_out[*]; // Element size 4
+; CHECK-NEXT:        float* MemRef_out_addr_0_lcssa; // Element size 8
 ; CHECK-NEXT:    }
 ;
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 ; Function Attrs: nounwind ssp uwtable
 define void @ff_celp_lp_synthesis_filterf(float* %out) #0 {
 entry:
   br label %entry.split

test/ScopInfo/scalar_to_array.ll

for.cond:                                         ; preds = %for.inc, %entry
   %indvar = phi i64 [ %indvar.next, %for.inc ], [ 0, %entry ]
   %exitcond = icmp ne i64 %indvar, 1024
   br i1 %exitcond, label %for.body.a, label %return
 
 for.body.a:                                       ; preds = %for.cond
   %arrayidx = getelementptr [1024 x float], [1024 x float]* @A, i64 0, i64 %indvar
   %scalar = load float, float* %arrayidx
   br label %for.body.b
-; CHECK:      Stmt_for_body_a
-; CHECK:          ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
-; CHECK-NEXT:         { Stmt_for_body_a[i0] -> MemRef_A[i0] };
-; CHECK:          MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:         { Stmt_for_body_a[i0] -> MemRef_scalar[] };
 
 for.body.b:                                       ; preds = %for.body.a
   %arrayidx2 = getelementptr [1024 x float], [1024 x float]* @A, i64 0, i64 %indvar
   %float = uitofp i64 %indvar to float
   %sum = fadd float %scalar, %float
   store float %sum, float* %arrayidx2
   br label %for.inc
 ; CHECK:      Stmt_for_body_b
-; CHECK:          ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:          { Stmt_for_body_b[i0] -> MemRef_scalar[] };
+; CHECK:          ReadAccess :=       [Reduction Type: NONE] [Scalar: 0] [MAPPED]
+; CHECK-NEXT:         { Stmt_for_body_b[i0] -> MemRef_A[i0] };
 ; CHECK:          MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:         { Stmt_for_body_b[i0] -> MemRef_A[i0] };
 
 for.inc:                                          ; preds = %for.body.b
   %indvar.next = add i64 %indvar, 1
   br label %for.cond
 
 return:                                           ; preds = %for.cond

test/update_check.py

+#! /usr/bin/env python3
+# -*- coding: UTF-8 -*-
+
+import argparse
+import os
+import subprocess
+import shlex
+import re
+
+polly_src_dir = '''@POLLY_SOURCE_DIR@'''
+polly_lib_dir = '''@POLLY_LIB_DIR@'''
+shlibext = '''@LLVM_SHLIBEXT@'''
+llvm_tools_dir = '''@LLVM_TOOLS_DIR@'''
+link_polly_into_tools = not '''@LINK_POLLY_INTO_TOOLS@'''.lower() in {'','0','n','no','off','false','notfound','link_polly_into_tools-notfound'}
+
+runre = re.compile(r'\s*\;\s*RUN\s*\:\s*(?P<tool>.*)\|\s*(?P<filecheck>FileCheck\s.*)')
+
+def ltrim_emptylines(lines):
+    while not lines[0].strip():
+        del lines[0]
+
+def rtrim_emptylines(lines):
+    while not lines[-1].strip():
+        del lines[-1]
+
+def trim_emptylines(lines):
+  ltrim_emptylines(lines)
+  rtrim_emptylines(lines)
+
+
+def complete_exename(path, filename):
+    complpath = os.path.join(path, filename)
+    if os.path.isfile(complpath):
+        return complpath
+    elif os.path.isfile(complpath + '.exe'):
+        return complpath + '.exe'
+    return filename 
+
+
+def main():
+    parser = argparse.ArgumentParser(description="Update CHECK lines", add_help=False)
+    parser.add_argument('testfile')
+    parser.add_argument('--check',action='store_true')
+    parser.add_argument('--bindir')
+    known = parser.parse_args()
+
+    filecheckparser = argparse.ArgumentParser(add_help=False)
+    filecheckparser.add_argument('--check-prefix',default='CHECK')
+
+    filename = known.testfile
+    if  os.path.isdir(polly_src_dir):
+        absfilename = os.path.join(polly_src_dir,'test',filename)
+        if os.path.isfile(absfilename):
+            filename = absfilename
+    allcheckstr = ''
+    checkprefixes = []
+
+    with open(filename, 'r') as file:
+        oldlines = [line.rstrip('\r\n') for line in file.readlines()]
+
+    for line in oldlines:
+            m = runre.match(line)
+            if m:
+                tool, filecheck = m.group('tool', 'filecheck')
+                filecheck = shlex.split(filecheck)
+                tool = shlex.split(tool)
+                if known.bindir is not None:
+                    tool[0] = complete_exename(known.bindir, tool[0])
+                if os.path.isdir(llvm_tools_dir):
+                    tool[0] = complete_exename(llvm_tools_dir, tool[0])
+                newtool = []
+                for toolarg in tool:
+                    if toolarg == '%loadPolly':
+                        if not link_polly_into_tools:
+                            newtool+=['-load',os.path.join(polly_lib_dir,'LLVMPolly' + shlibext)]
+                        newtool.append('-polly-process-unprofitable')
+                    elif toolarg == '%s':
+                        newtool.append(filename)
+                    else:
+                        newtool.append(toolarg)
+                tool = newtool
+                check_prefix = filecheckparser.parse_known_args(filecheck)[0].check_prefix
+                checkprefixes.append(check_prefix)
+                retlines = subprocess.check_output(tool,shell=True,universal_newlines=True)
+                retlines = retlines.splitlines()
+                trim_emptylines(retlines)
+                if known.check:
+                    checkstr = '; ' + check_prefix + ':      ' + ('\n; ' + check_prefix + ': ').join(retlines)
+                else:
+                    checkstr = '; ' + check_prefix + ': ' + ('\n; ' + check_prefix + '-NEXT: ').join(retlines)
+                allcheckstr += '\n\n' + checkstr
+
+    if not checkprefixes:
+        return
+
+    checkre = re.compile(r'^\s*\;\s*(' + '|'.join([ re.escape(s) for s in checkprefixes]) + ')(\-NEXT|\-DAG)?\s*\:')
+    newlines = []
+    for line in oldlines:
+            if not checkre.match(line):
+                newlines.append(line)
+
+    rtrim_emptylines(newlines)
+
+    with open(filename,'w') as file:
+        for line in newlines:
+            file.write(line)
+            file.write('\n')
+        file.write(allcheckstr)
+        file.write('\n')
+
+    print('success!')
+
+if __name__ == '__main__':
+    main()