[Polly][DeLICM] Known knowledge.

[Meinersbur]

Summary

Extend the Knowledge class to store information about the contents of array elements and which values are written. Two knowledges do not conflict the known content is the same. The content information if computed from writes to and loads from the array elements, and represented by "ValInst": isl spaces that compare equal if the value represented is the same.

This patch contains changes that I try to commit independently (introduction of distributeDomain/removal of AllElements, VirtualUse(?)).

[Meinersbur]

• Rebase to r298543
• Add switch to disable known information

[Meinersbur]

• Rebase to r298546
• Removed/activate commented code.

[Meinersbur]

• Remove spurious semicolon

[grosser]

Hi Michael,

thank you for pushing this forward. This is again a pretty large patch, even though the kind of different changes are now a lot smaller. Still, for proper and timely review, it would really help to get these patches smaller and upstream as much as possible independently. I did a first round over this patch, and trying to understand which parts are needed to get the tests working that you contributed. It seems indeed that e.g. VirtualUse is not really needed and to my surprise also the computeKnownFromWrite / computeKnownFromRead functions do not seem to be needed. At least all test cases pass even when I just return an empty known set. Did I make some wrong assumptions or is this functionality not tested and can be added later together with the corresponding test cases. (I stop now my review, to get first some feedback from you).

Best,
Tobias

include/polly/ScopInfo.h

1334 ↗

(On Diff #92718)

This can probably be committed separately and directly be used and tested in RegionGenerator::addOperandToPHI. No further review needed for this.

include/polly/Support/VirtualInstruction.h

37 ↗

(On Diff #92718)

An -> A

lib/Transform/DeLICM.cpp

391 ↗

(On Diff #92718)

This move also not seem to be needed without VirtualUse.

864 ↗

(On Diff #92718)

Not needed without VirtualUse?

901 ↗

(On Diff #92718)

Not needed without virtual use?

1209 ↗

(On Diff #92718)

Grammar: "look get"

1212 ↗

(On Diff #92718)

I prefer comments to be aligned to the start of the first line (otherwise they mix with the parameters).

1236 ↗

(On Diff #92718)

The only case currently tested seems to be VirtualUse::Constant. If I add a "break" at the beginning of each other case, all tests still pass as expected. Maybe we can first introduce the constant case, without virtual use and then look again at the virtual use?

1238 ↗

(On Diff #92718)

on the

1941 ↗

(On Diff #92718)

If I revert this change and use the original getInputAccessOf function, all tests still pass. This and the use where we check for Val to be a constant are the only uses of VirtualUse. If we drop them, this patch would become more targeted.

2017 ↗

(On Diff #92718)

If I add return makeEmptyUnionMap(); all tests still pass.

2030 ↗

(On Diff #92718)

If I add return makeEmptyUnionMap(); all tests still pass.

2117 ↗

(On Diff #92718)

Not needed without virtual Statement.

2250 ↗

(On Diff #92718)

Not needed without VirtualStmt.

2270 ↗

(On Diff #92718)

Not needed without VirtualStmt.

unittests/DeLICM/DeLICMTest.cpp

127 ↗

(On Diff #92718)

I assume we do not need this commented code to be committed.

[Meinersbur]

In D31247#708641, @grosser wrote:

thank you for pushing this forward. This is again a pretty large patch, even though the kind of different changes are now a lot smaller. Still, for proper and timely review, it would really help to get these patches smaller and upstream as much as possible independently. I did a first round over this patch, and trying to understand which parts are needed to get the tests working that you contributed. It seems indeed that e.g. VirtualUse is not really needed

See inline comment.

and to my surprise also the computeKnownFromWrite / computeKnownFromRead functions do not seem to be needed.

That was my laziness by making minimal changes to the reduction.ll test case to make it work. By doing this, only a particular kind of conflict occurs, namely conflicts with previously mapped values. This is not typical for GVE PRE-optimized code. I'll come up with better ones with the next update.

Michael

include/polly/Support/VirtualInstruction.h

37 ↗

(On Diff #92718)

It is pronounced "El El Vee Em", hence the article is correct.

Also compare
https://www.google.com/search?q="An+LLVM"
vs
https://www.google.com/search?q="A+LLVM"

lib/Transform/DeLICM.cpp

1236 ↗

(On Diff #92718)

You may have missed that the "VirtualUse::InterValue" case breaks as well because it is the longest and "main" case, to avoid handling it in a switch case. All other cases return, that is, for the two test cases we need to distinguish at least these two and if its none of them (to return "value unknown"), makes three cases.

The other cases are not that interesting, so no test case for those yet. It doesn't come up because the test cases were crafted that way. For instance, VirtualUse::IntraValue never occurs because there are never two instructions depending on each other in a single basic block. The same computational pattern is employed with only one instruction, so the test case uses the smaller one.

[Meinersbur]

• Not all synthesizable values are affine (e.g. undef)
• Not all affine values are synthezizable (e.g. load-hoisted values)
• Addresses some of Tobias' comments.
• More test cases.
• Remove computeKnownFromRead, seems not to be useful here.

Note this currently miscompiles External\SPEC\CINT2006\401.bzip2, looking into it.

[Meinersbur]

401.bzip2 fails even without its patch, look similar to http://llvm.org/PR32251 .

[grosser]

Hi Michael,

thanks for upstreaming already so much of this patch. I believe after this patch is rebased onto trunk, the diff should be small enough to review it as a whole.

Best,
Tobias

include/polly/Support/VirtualInstruction.h

37 ↗

(On Diff #92718)

You are right

[Meinersbur]

Rebase to r302234

[grosser]

Hi Michael,

this looks good to me. I just have a couple of minor typos. I also tried this of some of the polybench kernels, but it seems not yet enough to make them really faster. The one thing we need for a simple gemm kernel is -polly-delicm-overapproximate-writes=true, the second is an option to remove redundant writes. I assume these will be handled in later changes, so no need to block this patch.

Best,
Tobias

lib/Transform/DeLICM.cpp

119 ↗

(On Diff #97972)

A synthesizable

1202 ↗

(On Diff #97972)

uses.

1235 ↗

(On Diff #97972)

no need for comma here.

test/DeLICM/reduction_looprotate.ll

13 ↗

(On Diff #97972)

to DO in

[Meinersbur]

In D31247#747634, @grosser wrote:

Hi Michael,

this looks good to me. I just have a couple of minor typos. I also tried this of some of the polybench kernels, but it seems not yet enough to make them really faster. The one thing we need for a simple gemm kernel is -polly-delicm-overapproximate-writes=true, the second is an option to remove redundant writes. I assume these will be handled in later changes, so no need to block this patch.

For really being effective, we also need partial writes (MemoryAccesses that do not write in an entire's statement domain). This makes -polly-delicm-overapproximate-writes=true kind of redundant.

Depending on the benchmark, an extension determining that a PHINode is identical to one of their incoming values could be useful as well.

About the redundant writes, I still have to think about to do it correctly. the PHINode extension could be helpful.

[grosser]

Cool. Maybe let's pull out this discussion from the review thread to the ML. This seems to be go beyond what this patch coveres.

polly/trunk/include/polly/ScopInfo.h

 
 class MemoryAccess;
 class Scop;
 class ScopStmt;
 class ScopBuilder;
 
 //===---------------------------------------------------------------------===//
 
+extern bool UseInstructionNames;
+
 /// Enumeration of assumptions Polly can take.
 enum AssumptionKind {
   ALIASING,
   INBOUNDS,
   WRAPPING,
   UNSIGNED,
   PROFITABLE,
   ERRORBLOCK,

polly/trunk/lib/Analysis/ScopInfo.cpp

static cl::opt<bool> PollyIgnoreParamBounds(
     cl::Hidden, cl::init(false), cl::cat(PollyCategory));
 
 static cl::opt<bool> PollyPreciseFoldAccesses(
     "polly-precise-fold-accesses",
     cl::desc("Fold memory accesses to model more possible delinearizations "
              "(does not scale well)"),
     cl::Hidden, cl::init(false), cl::cat(PollyCategory));
 
-static cl::opt<bool> UseInstructionNames(
+bool polly::UseInstructionNames;
+static cl::opt<bool, true> XUseInstructionNames(
     "polly-use-llvm-names",
-    cl::desc("Use LLVM-IR names when deriving statement names"), cl::Hidden,
-    cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
+    cl::desc("Use LLVM-IR names when deriving statement names"),
+    cl::location(UseInstructionNames), cl::Hidden, cl::init(false),
+    cl::ZeroOrMore, 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,

polly/trunk/lib/Support/GICHelper.cpp

static void replace(std::string &str, const std::string &find,
   }
 }
 
 static void makeIslCompatible(std::string &str) {
   replace(str, ".", "_");
   replace(str, "\"", "_");
   replace(str, " ", "__");
   replace(str, "=>", "TO");
+  replace(str, "+", "_");
 }
 
 std::string polly::getIslCompatibleName(const std::string &Prefix,
                                         const std::string &Middle,
                                         const std::string &Suffix) {
   std::string S = Prefix + Middle + Suffix;
   makeIslCompatible(S);
   return S;

polly/trunk/lib/Transform/DeLICM.cpp

 //     isl_id_get_user: Pointer to ScopArrayInfo
 //
 // * Scatter[] - Scatter space or space of timepoints
 //     Has no tuple id
 //
 // * Zone[] - Range between timepoints as described above
 //     Has no tuple id
 //
+// * ValInst[] - An llvm::Value as defined at a specific timepoint.
+//
+//     A ValInst[] itself can be structured as one of:
+//
+//     * [] - An unknown value.
+//         Always zero dimensions
+//         Has no tuple id
+//
+//     * Value[] - An llvm::Value that is read-only in the SCoP, i.e. its
+//                 runtime content does not depend on the timepoint.
+//         Always zero dimensions
+//         isl_id_get_name: Val_<NameOfValue>
+//         isl_id_get_user: A pointer to an llvm::Value
+//
+//     * SCEV[...] - A synthesizable llvm::SCEV Expression.
+//         In contrast to a Value[] is has at least one dimension per
+//         SCEVAddRecExpr in the SCEV.
+//
+//     * [Domain[] -> Value[]] - An llvm::Value that may change during the
+//                               Scop's execution.
+//         The tuple itself has no id, but it wraps a map space holding a
+//         statement instance which defines the llvm::Value as the map's domain
+//         and llvm::Value itself as range.
+//
+// @see makeValInst()
+//
 // An annotation "{ Domain[] -> Scatter[] }" therefore means: A map from a
 // statement instance to a timepoint, aka a schedule. There is only one scatter
 // space, but most of the time multiple statements are processed in one set.
 // This is why most of the time isl_union_map has to be used.
 //
 // The basic algorithm works as follows:
 // At first we verify that the SCoP is compatible with this technique. For
 // instance, two writes cannot write to the same location at the same statement

 //
 //===----------------------------------------------------------------------===//
 
 #include "polly/DeLICM.h"
 #include "polly/Options.h"
 #include "polly/ScopInfo.h"
 #include "polly/ScopPass.h"
 #include "polly/Support/ISLTools.h"
+#include "polly/Support/VirtualInstruction.h"
 #include "llvm/ADT/Statistic.h"
 #define DEBUG_TYPE "polly-delicm"
 
 using namespace polly;
 using namespace llvm;
 
 namespace {
 
 cl::opt<int>
     DelicmMaxOps("polly-delicm-max-ops",
                  cl::desc("Maximum number of isl operations to invest for "
                           "lifetime analysis; 0=no limit"),
                  cl::init(1000000), cl::cat(PollyCategory));
 
 cl::opt<bool> DelicmOverapproximateWrites(
     "polly-delicm-overapproximate-writes",
     cl::desc(
         "Do more PHI writes than necessary in order to avoid partial accesses"),
     cl::init(false), cl::Hidden, cl::cat(PollyCategory));
 
+cl::opt<bool>
+    DelicmComputeKnown("polly-delicm-compute-known",
+                       cl::desc("Compute known content of array elements"),
+                       cl::init(true), cl::Hidden, cl::cat(PollyCategory));
+
 STATISTIC(DeLICMAnalyzed, "Number of successfully analyzed SCoPs");
 STATISTIC(DeLICMOutOfQuota,
           "Analyses aborted because max_operations was reached");
 STATISTIC(DeLICMIncompatible, "Number of SCoPs incompatible for analysis");
 STATISTIC(MappedValueScalars, "Number of mapped Value scalars");
 STATISTIC(MappedPHIScalars, "Number of mapped PHI scalars");
 STATISTIC(TargetsMapped, "Number of stores used for at least one mapping");
 STATISTIC(DeLICMScopsModified, "Number of SCoPs optimized");

 ///
 /// @param Domain { Domain[] }
 ///
 /// @return { Domain[] -> ValInst[] }
 isl::union_map makeUnknownForDomain(isl::union_set Domain) {
   return give(isl_union_map_from_domain(Domain.take()));
 }
 
-/// If InputVal is not defined in the stmt itself, return the MemoryAccess that
-/// reads the scalar. Return nullptr otherwise (if the value is defined in the
-/// scop, or is synthesizable).
-MemoryAccess *getInputAccessOf(Value *InputVal, ScopStmt *Stmt) {
-  for (auto *MA : *Stmt) {
-    if (!MA->isRead())
-      continue;
-    if (!MA->isLatestScalarKind())
-      continue;
-
-    assert(MA->getAccessValue() == MA->getBaseAddr());
-    if (MA->getAccessValue() == InputVal)
-      return MA;
-  }
-  return nullptr;
+/// Create a domain-to-unknown value mapping.
+///
+/// @see makeUnknownForDomain(isl::union_set)
+///
+/// @param Domain { Domain[] }
+///
+/// @return { Domain[] -> ValInst[] }
+isl::map makeUnknownForDomain(isl::set Domain) {
+  return give(isl_map_from_domain(Domain.take()));
 }
 
 /// Return whether @p Map maps to an unknown value.
 ///
 /// @param { [] -> ValInst[] }
 bool isMapToUnknown(const isl::map &Map) {
   auto Space = give(isl_space_range(isl_map_get_space(Map.keep())));
   return !isl_map_has_tuple_id(Map.keep(), isl_dim_set) &&

 
 public:
   /// Initialize a nullptr-Knowledge. This is only provided for convenience; do
   /// not use such an object.
   Knowledge() {}
 
   /// Create a new object with the given members.
   Knowledge(isl::union_set Occupied, isl::union_set Unused,
-            isl::union_set Written)
-      : Occupied(std::move(Occupied)), Unused(std::move(Unused)),
-        Known(isl::manage(
-            isl_union_map_empty(isl_union_set_get_space(Written.keep())))),
-        Written(isl::manage(isl_union_map_from_domain(Written.take()))) {
-    checkConsistency();
-  }
-
-  /// Create a new object with the given members.
-  Knowledge(isl::union_set Occupied, isl::union_set Unused,
             isl::union_map Known, isl::union_map Written)
       : Occupied(std::move(Occupied)), Unused(std::move(Unused)),
         Known(std::move(Known)), Written(std::move(Written)) {
     checkConsistency();
   }
 
   /// Return whether this object was not default-constructed.
   bool isUsable() const { return (Occupied || Unused) && Known && Written; }
protected:
   /// Cached reaching definitions for each ScopStmt.
   ///
   /// Use getScalarReachingDefinition() to get its contents.
   DenseMap<ScopStmt *, isl::map> ScalarReachDefZone;
 
   /// The analyzed Scop.
   Scop *S;
 
+  /// LoopInfo analysis used to determine whether values are synthesizable.
+  LoopInfo *LI;
+
   /// Parameter space that does not need realignment.
   isl::space ParamSpace;
 
   /// Space the schedule maps to.
   isl::space ScatterSpace;
 
   /// Cached version of the schedule and domains.
   isl::union_map Schedule;
 
   /// Combined access relations of all MemoryKind::Array READ accesses.
   /// { DomainRead[] -> Element[] }
   isl::union_map AllReads;
 
   /// Combined access relations of all MemoryKind::Array, MAY_WRITE accesses.
   /// { DomainMayWrite[] -> Element[] }
   isl::union_map AllMayWrites;
 
   /// Combined access relations of all MemoryKind::Array, MUST_WRITE accesses.
   /// { DomainMustWrite[] -> Element[] }
   isl::union_map AllMustWrites;
 
+  /// The value instances written to array elements of all write accesses.
+  /// { [Element[] -> DomainWrite[]] -> ValInst[] }
+  isl::union_map AllWriteValInst;
+
+  /// All reaching definitions for  MemoryKind::Array writes.
+  /// { [Element[] -> Zone[]] -> DomainWrite[] }
+  isl::union_map WriteReachDefZone;
+
+  /// Map llvm::Values to an isl identifier.
+  /// Used with -polly-use-llvm-names=false as an alternative method to get
+  /// unique ids that do not depend on pointer values.
+  DenseMap<Value *, isl::id> ValueIds;
+
   /// Prepare the object before computing the zones of @p S.
-  ZoneAlgorithm(Scop *S)
-      : IslCtx(S->getSharedIslCtx()), S(S), Schedule(give(S->getSchedule())) {
+  ZoneAlgorithm(Scop *S, LoopInfo *LI)
+      : IslCtx(S->getSharedIslCtx()), S(S), LI(LI),
+        Schedule(give(S->getSchedule())) {
 
     auto Domains = give(S->getDomains());
 
     Schedule =
         give(isl_union_map_intersect_domain(Schedule.take(), Domains.take()));
     ParamSpace = give(isl_union_map_get_space(Schedule.keep()));
     ScatterSpace = getScatterSpace(Schedule);
   }
void addArrayReadAccess(MemoryAccess *MA) {
     // { DomainRead[] -> Element[] }
     auto AccRel = getAccessRelationFor(MA);
     AllReads = give(isl_union_map_add_map(AllReads.take(), AccRel.copy()));
   }
 
   void addArrayWriteAccess(MemoryAccess *MA) {
     assert(MA->isLatestArrayKind());
     assert(MA->isWrite());
+    auto *Stmt = MA->getStatement();
 
     // { Domain[] -> Element[] }
     auto AccRel = getAccessRelationFor(MA);
 
     if (MA->isMustWrite())
       AllMustWrites =
           give(isl_union_map_add_map(AllMustWrites.take(), AccRel.copy()));
 
     if (MA->isMayWrite())
       AllMayWrites =
           give(isl_union_map_add_map(AllMayWrites.take(), AccRel.copy()));
+
+    // { Domain[] -> ValInst[] }
+    auto WriteValInstance =
+        makeValInst(MA->getAccessValue(), Stmt,
+                    LI->getLoopFor(MA->getAccessInstruction()->getParent()),
+                    MA->isMustWrite());
+
+    // { Domain[] -> [Element[] -> Domain[]] }
+    auto IncludeElement =
+        give(isl_map_curry(isl_map_domain_map(AccRel.copy())));
+
+    // { [Element[] -> DomainWrite[]] -> ValInst[] }
+    auto EltWriteValInst = give(
+        isl_map_apply_domain(WriteValInstance.take(), IncludeElement.take()));
+
+    AllWriteValInst = give(
+        isl_union_map_add_map(AllWriteValInst.take(), EltWriteValInst.take()));
   }
 
 protected:
   isl::union_set makeEmptyUnionSet() const {
     return give(isl_union_set_empty(ParamSpace.copy()));
   }
 
   isl::union_map makeEmptyUnionMap() const {
protected:
 
   /// Get the schedule for the statement instances of @p Domain.
   isl::map getScatterFor(isl::set Domain) const {
     auto ResultSpace = give(isl_space_map_from_domain_and_range(
         isl_set_get_space(Domain.keep()), ScatterSpace.copy()));
     auto UDomain = give(isl_union_set_from_set(Domain.copy()));
     auto UResult = getScatterFor(std::move(UDomain));
     auto Result = singleton(std::move(UResult), std::move(ResultSpace));
-    assert(isl_set_is_equal(give(isl_map_domain(Result.copy())).keep(),
+    assert(!Result ||
+           isl_set_is_equal(give(isl_map_domain(Result.copy())).keep(),
                             Domain.keep()) == isl_bool_true);
     return Result;
   }
 
   /// Get the domain of @p Stmt.
   isl::set getDomainFor(ScopStmt *Stmt) const {
     return give(Stmt->getDomain());
   }
isl::map getScalarReachingDefinition(ScopStmt *Stmt) {
     auto &Result = ScalarReachDefZone[Stmt];
     if (Result)
       return Result;
 
     auto Domain = getDomainFor(Stmt);
     Result = computeScalarReachingDefinition(Schedule, Domain, false, true);
     simplify(Result);
 
-    assert(Result);
     return Result;
   }
 
+  /// Get the reaching definition of a scalar defined in @p DefDomain.
+  ///
+  /// @param DomainDef { DomainDef[] }
+  ///              The write statements to get the reaching definition for.
+  ///
+  /// @return { Scatter[] -> DomainDef[] }
+  isl::map getScalarReachingDefinition(isl::set DomainDef) {
+    auto DomId = give(isl_set_get_tuple_id(DomainDef.keep()));
+    auto *Stmt = static_cast<ScopStmt *>(isl_id_get_user(DomId.keep()));
+
+    auto StmtResult = getScalarReachingDefinition(Stmt);
+
+    return give(isl_map_intersect_range(StmtResult.take(), DomainDef.take()));
+  }
+
+  /// Create a statement-to-unknown value mapping.
+  ///
+  /// @param Stmt The statement whose instances are mapped to unknown.
+  ///
+  /// @return { Domain[] -> ValInst[] }
+  isl::map makeUnknownForDomain(ScopStmt *Stmt) const {
+    return ::makeUnknownForDomain(getDomainFor(Stmt));
+  }
+
+  /// Create an isl_id that represents @p V.
+  isl::id makeValueId(Value *V) {
+    if (!V)
+      return nullptr;
+
+    auto &Id = ValueIds[V];
+    if (Id.is_null()) {
+      auto Name = getIslCompatibleName("Val_", V, ValueIds.size() - 1,
+                                       std::string(), UseInstructionNames);
+      Id = give(isl_id_alloc(IslCtx.get(), Name.c_str(), V));
+    }
+    return Id;
+  }
+
+  /// Create the space for an llvm::Value that is available everywhere.
+  isl::space makeValueSpace(Value *V) {
+    auto Result = give(isl_space_set_from_params(ParamSpace.copy()));
+    return give(isl_space_set_tuple_id(Result.take(), isl_dim_set,
+                                       makeValueId(V).take()));
+  }
+
+  /// Create a set with the llvm::Value @p V which is available everywhere.
+  isl::set makeValueSet(Value *V) {
+    auto Space = makeValueSpace(V);
+    return give(isl_set_universe(Space.take()));
+  }
+
+  /// Create a mapping from a statement instance to the instance of an
+  /// llvm::Value that can be used in there.
+  ///
+  /// Although LLVM IR uses single static assignment, llvm::Values can have
+  /// different contents in loops, when they get redefined in the last
+  /// iteration. This function tries to get the statement instance of the
+  /// previous definition, relative to a user.
+  ///
+  /// Example:
+  /// for (int i = 0; i < N; i += 1) {
+  /// DEF:
+  ///    int v = A[i];
+  /// USE:
+  ///    use(v);
+  ///  }
+  ///
+  /// The value instance used by statement instance USE[i] is DEF[i]. Hence,
+  /// makeValInst returns:
+  ///
+  /// { USE[i] -> [DEF[i] -> v[]] : 0 <= i < N }
+  ///
+  /// @param Val       The value to get the instance of.
+  /// @param UserStmt  The statement that uses @p Val. Can be nullptr.
+  /// @param Scope     Loop the using instruction resides in.
+  /// @param IsCertain Pass true if the definition of @p Val is a
+  ///                  MUST_WRITE or false if the write is conditional.
+  ///
+  /// @return { DomainUse[] -> ValInst[] }
+  isl::map makeValInst(Value *Val, ScopStmt *UserStmt, Loop *Scope,
+                       bool IsCertain = true) {
+    // When known knowledge is disabled, just return the unknown value. It will
+    // either get filtered out or conflict with itself.
+    if (!DelicmComputeKnown)
+      return makeUnknownForDomain(UserStmt);
+
+    // If the definition/write is conditional, the value at the location could
+    // be either the written value or the old value. Since we cannot know which
+    // one, consider the value to be unknown.
+    if (!IsCertain)
+      return makeUnknownForDomain(UserStmt);
+
+    auto DomainUse = getDomainFor(UserStmt);
+    auto VUse = VirtualUse::create(S, UserStmt, Scope, Val, true);
+    switch (VUse.getKind()) {
+    case VirtualUse::Constant:
+    case VirtualUse::Block:
+    case VirtualUse::Hoisted:
+    case VirtualUse::ReadOnly: {
+      // The definition does not depend on the statement which uses it.
+      auto ValSet = makeValueSet(Val);
+      return give(
+          isl_map_from_domain_and_range(DomainUse.take(), ValSet.take()));
+    }
+
+    case VirtualUse::Synthesizable: {
+      auto *ScevExpr = VUse.getScevExpr();
+      auto UseDomainSpace = give(isl_set_get_space(DomainUse.keep()));
+
+      // Construct the SCEV space.
+      // TODO: Add only the induction variables referenced in SCEVAddRecExpr
+      // expressions, not just all of them.
+      auto ScevId = give(isl_id_alloc(UseDomainSpace.get_ctx().get(), nullptr,
+                                      (void *)ScevExpr));
+      auto ScevSpace =
+          give(isl_space_drop_dims(UseDomainSpace.copy(), isl_dim_set, 0, 0));
+      ScevSpace = give(
+          isl_space_set_tuple_id(ScevSpace.take(), isl_dim_set, ScevId.copy()));
+
+      // { DomainUse[] -> ScevExpr[] }
+      auto ValInst = give(isl_map_identity(isl_space_map_from_domain_and_range(
+          UseDomainSpace.copy(), ScevSpace.copy())));
+      return ValInst;
+    }
+
+    case VirtualUse::Intra: {
+      // Definition and use is in the same statement. We do not need to compute
+      // a reaching definition.
+
+      // { llvm::Value }
+      auto ValSet = makeValueSet(Val);
+
+      // {  UserDomain[] -> llvm::Value }
+      auto ValInstSet =
+          give(isl_map_from_domain_and_range(DomainUse.take(), ValSet.take()));
+
+      // { UserDomain[] -> [UserDomain[] - >llvm::Value] }
+      auto Result =
+          give(isl_map_reverse(isl_map_domain_map(ValInstSet.take())));
+      simplify(Result);
+      return Result;
+    }
+
+    case VirtualUse::Inter: {
+      // The value is defined in a different statement.
+
+      auto *Inst = cast<Instruction>(Val);
+      auto *ValStmt = S->getStmtFor(Inst);
+
+      // If the llvm::Value is defined in a removed Stmt, we cannot derive its
+      // domain. We could use an arbitrary statement, but this could result in
+      // different ValInst[] for the same llvm::Value.
+      if (!ValStmt)
+        return ::makeUnknownForDomain(DomainUse);
+
+      // { DomainDef[] }
+      auto DomainDef = getDomainFor(ValStmt);
+
+      // { Scatter[] -> DomainDef[] }
+      auto ReachDef = getScalarReachingDefinition(DomainDef);
+
+      // { DomainUse[] -> Scatter[] }
+      auto UserSched = getScatterFor(DomainUse);
+
+      // { DomainUse[] -> DomainDef[] }
+      auto UsedInstance =
+          give(isl_map_apply_range(UserSched.take(), ReachDef.take()));
+
+      // { llvm::Value }
+      auto ValSet = makeValueSet(Val);
+
+      // { DomainUse[] -> llvm::Value[] }
+      auto ValInstSet =
+          give(isl_map_from_domain_and_range(DomainUse.take(), ValSet.take()));
+
+      // { DomainUse[] -> [DomainDef[] -> llvm::Value]  }
+      auto Result =
+          give(isl_map_range_product(UsedInstance.take(), ValInstSet.take()));
+
+      simplify(Result);
+      return Result;
+    }
+    }
+    llvm_unreachable("Unhandled use type");
+  }
+
   /// Compute the different zones.
   void computeCommon() {
     AllReads = makeEmptyUnionMap();
     AllMayWrites = makeEmptyUnionMap();
     AllMustWrites = makeEmptyUnionMap();
+    AllWriteValInst = makeEmptyUnionMap();
 
     for (auto &Stmt : *S) {
       for (auto *MA : Stmt) {
         if (!MA->isLatestArrayKind())
           continue;
 
         if (MA->isRead())
           addArrayReadAccess(MA);
 
         if (MA->isWrite())
           addArrayWriteAccess(MA);
       }
     }
 
     // { DomainWrite[] -> Element[] }
     auto AllWrites =
         give(isl_union_map_union(AllMustWrites.copy(), AllMayWrites.copy()));
+
+    // { [Element[] -> Zone[]] -> DomainWrite[] }
+    WriteReachDefZone =
+        computeReachingDefinition(Schedule, AllWrites, false, true);
+    simplify(WriteReachDefZone);
   }
 
   /// Print the current state of all MemoryAccesses to @p.
   void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const {
     OS.indent(Indent) << "After accesses {\n";
     for (auto &Stmt : *S) {
       OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";
       for (auto *MA : Stmt)
private:
   ///
   /// @return true if the scalar was successfully mapped.
   bool tryMapValue(const ScopArrayInfo *SAI, isl::map TargetElt) {
     assert(SAI->isValueKind());
 
     auto *DefMA = DefUse.getValueDef(SAI);
     assert(DefMA->isValueKind());
     assert(DefMA->isMustWrite());
+    auto *V = DefMA->getAccessValue();
+    auto *DefInst = DefMA->getAccessInstruction();
 
     // Stop if the scalar has already been mapped.
     if (!DefMA->getLatestScopArrayInfo()->isValueKind())
       return false;
 
     // { DomainDef[] -> Scatter[] }
     auto DefSched = getScatterFor(DefMA);
 
bool tryMapValue(const ScopArrayInfo *SAI, isl::map TargetElt) {
     std::tie(DefUses, Lifetime) = computeValueUses(SAI);
     DEBUG(dbgs() << "    Lifetime: " << Lifetime << '\n');
 
     /// { [Element[] -> Zone[]] }
     auto EltZone = give(
         isl_map_wrap(isl_map_apply_domain(Lifetime.copy(), DefTarget.copy())));
     simplify(EltZone);
 
-    // { [Element[] -> Scatter[]] }
-    auto DefEltSched = give(isl_map_wrap(isl_map_reverse(
-        isl_map_apply_domain(DefTarget.copy(), DefSched.copy()))));
+    // { DomainDef[] -> ValInst[] }
+    auto ValInst = makeValInst(V, DefMA->getStatement(),
+                               LI->getLoopFor(DefInst->getParent()));
+
+    // { DomainDef[] -> [Element[] -> Zone[]] }
+    auto EltKnownTranslator =
+        give(isl_map_range_product(DefTarget.copy(), Lifetime.copy()));
+
+    // { [Element[] -> Zone[]] -> ValInst[] }
+    auto EltKnown =
+        give(isl_map_apply_domain(ValInst.copy(), EltKnownTranslator.take()));
+    simplify(EltKnown);
+
+    // { DomainDef[] -> [Element[] -> Scatter[]] }
+    auto WrittenTranslator =
+        give(isl_map_range_product(DefTarget.copy(), DefSched.take()));
+
+    // { [Element[] -> Scatter[]] -> ValInst[] }
+    auto DefEltSched =
+        give(isl_map_apply_domain(ValInst.copy(), WrittenTranslator.take()));
     simplify(DefEltSched);
 
-    Knowledge Proposed(EltZone, nullptr, DefEltSched);
+    Knowledge Proposed(EltZone, nullptr, filterKnownValInst(EltKnown),
+                       DefEltSched);
     if (isConflicting(Proposed))
       return false;
 
     // { DomainUse[] -> Element[] }
     auto UseTarget = give(
         isl_union_map_apply_range(isl_union_map_reverse(DefUses.take()),
                                   isl_union_map_from_map(DefTarget.copy())));
 
void mapValue(const ScopArrayInfo *SAI, isl::map DefTarget,
     auto *WA = DefUse.getValueDef(SAI);
     WA->setNewAccessRelation(DefTarget.copy());
     applyLifetime(Proposed);
 
     MappedValueScalars++;
     NumberOfMappedValueScalars += 1;
   }
 
+  /// Express the incoming values of a PHI for each incoming statement in an
+  /// isl::union_map.
+  ///
+  /// @param SAI The PHI scalar represented by a ScopArrayInfo.
+  ///
+  /// @return { PHIWriteDomain[] -> ValInst[] }
+  isl::union_map determinePHIWrittenValues(const ScopArrayInfo *SAI) {
+    auto Result = makeEmptyUnionMap();
+
+    // Collect the incoming values.
+    for (auto *MA : DefUse.getPHIIncomings(SAI)) {
+      // { DomainWrite[] -> ValInst[] }
+      isl::union_map ValInst;
+      auto *WriteStmt = MA->getStatement();
+
+      auto Incoming = MA->getIncoming();
+      assert(!Incoming.empty());
+      if (Incoming.size() == 1) {
+        ValInst = makeValInst(Incoming[0].second, WriteStmt,
+                              LI->getLoopFor(Incoming[0].first));
+      } else {
+        // If the PHI is in a subregion's exit node it can have multiple
+        // incoming values (+ maybe another incoming edge from an unrelated
+        // block). We cannot directly represent it as a single llvm::Value.
+        // We currently model it as unknown value, but modeling as the PHIInst
+        // itself could be OK, too.
+        ValInst = makeUnknownForDomain(WriteStmt);
+      }
+
+      Result = give(isl_union_map_union(Result.take(), ValInst.take()));
+    }
+
+    assert(isl_union_map_is_single_valued(Result.keep()) == isl_bool_true &&
+           "Cannot have multiple incoming values for same incoming statement");
+    return Result;
+  }
+
   /// Try to map a MemoryKind::PHI scalar to a given array element.
   ///
   /// @param SAI       Representation of the scalar's memory to map.
   /// @param TargetElt { Scatter[] -> Element[] }
   ///                  Suggestion where to map the scalar to when at a
   ///                  timepoint.
   ///
   /// @return true if the PHI scalar has been mapped.
bool tryMapPHI(const ScopArrayInfo *SAI, isl::map TargetElt) {
     auto Lifetime = betweenScatter(PerPHIWriteScatter, PHISched, false, true);
     simplify(Lifetime);
     DEBUG(dbgs() << "    Lifetime: " << Lifetime << "\n");
 
     // { DomainWrite[] -> Zone[] }
     auto WriteLifetime = give(isl_union_map_apply_domain(
         isl_union_map_from_map(Lifetime.copy()), PerPHIWrites.copy()));
 
+    // { DomainWrite[] -> ValInst[] }
+    auto WrittenValue = determinePHIWrittenValues(SAI);
+
     // { DomainWrite[] -> [Element[] -> Scatter[]] }
     auto WrittenTranslator =
         give(isl_union_map_range_product(WritesTarget.copy(), Schedule.copy()));
 
-    // { [Element[] -> Scatter[]] }
-    auto Written = give(isl_union_map_range(WrittenTranslator.copy()));
+    // { [Element[] -> Scatter[]] -> ValInst[] }
+    auto Written = give(isl_union_map_apply_domain(WrittenValue.copy(),
+                                                   WrittenTranslator.copy()));
     simplify(Written);
 
     // { DomainWrite[] -> [Element[] -> Zone[]] }
     auto LifetimeTranslator = give(
-        isl_union_map_range_product(WritesTarget.copy(), WriteLifetime.take()));
+        isl_union_map_range_product(WritesTarget.copy(), WriteLifetime.copy()));
+
+    // { DomainWrite[] -> ValInst[] }
+    auto WrittenKnownValue = filterKnownValInst(WrittenValue);
+
+    // { [Element[] -> Zone[]] -> ValInst[] }
+    auto EltLifetimeInst = give(isl_union_map_apply_domain(
+        WrittenKnownValue.copy(), LifetimeTranslator.copy()));
+    simplify(EltLifetimeInst);
 
     // { [Element[] -> Zone[] }
     auto Occupied = give(isl_union_map_range(LifetimeTranslator.copy()));
     simplify(Occupied);
 
-    Knowledge Proposed(Occupied, nullptr, Written);
+    Knowledge Proposed(Occupied, nullptr, EltLifetimeInst, Written);
     if (isConflicting(Proposed))
       return false;
 
     mapPHI(SAI, std::move(PHITarget), std::move(WritesTarget),
            std::move(Lifetime), std::move(Proposed));
     return true;
   }
 
auto ProcessAllIncoming = [&](ScopStmt *Stmt) {
           continue;
 
         Worklist.push_back(MA);
       }
     };
 
     // Add initial scalar. Either the value written by the store, or all inputs
     // of its statement.
-    auto WrittenVal = TargetStoreMA->getAccessValue();
-    if (auto InputAcc = getInputAccessOf(WrittenVal, TargetStmt))
-      Worklist.push_back(InputAcc);
+    auto WrittenValUse = VirtualUse::create(
+        S, TargetStoreMA->getAccessInstruction()->getOperandUse(0), LI, true);
+    if (WrittenValUse.isInter())
+      Worklist.push_back(WrittenValUse.getMemoryAccess());
     else
       ProcessAllIncoming(TargetStmt);
 
     auto AnyMapped = false;
     auto &DL = S->getRegion().getEntry()->getModule()->getDataLayout();
     auto StoreSize =
         DL.getTypeAllocSize(TargetStoreMA->getAccessValue()->getType());
 
auto ArrayUnused = computeArrayUnused(Schedule, AllMustWrites, AllReads,
                                           false, false, true);
 
     auto Result = give(isl_union_map_wrap(ArrayUnused.copy()));
 
     simplify(Result);
     return Result;
   }
 
-  /// Determine when an array element is written to.
+  /// Compute which value an array element stores at every instant.
   ///
-  /// @return { [Element[] -> Scatter[]] }
-  isl::union_set computeWritten() const {
-    // { WriteDomain[] -> Element[] }
-    auto AllWrites =
-        give(isl_union_map_union(AllMustWrites.copy(), AllMayWrites.copy()));
+  /// @return { [Element[] -> Zone[]] -> ValInst[] }
+  isl::union_map computeKnown() const {
+    // { [Element[] -> Zone[]] -> [Element[] -> DomainWrite[]] }
+    auto EltReachdDef =
+        distributeDomain(give(isl_union_map_curry(WriteReachDefZone.copy())));
 
-    // { Scatter[] -> Element[] }
-    auto WriteTimepoints =
-        give(isl_union_map_apply_domain(AllWrites.copy(), Schedule.copy()));
+    // { [Element[] -> DomainWrite[]] -> ValInst[] }
+    auto AllKnownWriteValInst = filterKnownValInst(AllWriteValInst);
 
-    auto Result =
-        give(isl_union_map_wrap(isl_union_map_reverse(WriteTimepoints.copy())));
+    // { [Element[] -> Zone[]] -> ValInst[] }
+    return EltReachdDef.apply_range(AllKnownWriteValInst);
+  }
 
-    simplify(Result);
-    return Result;
+  /// Determine when an array element is written to, and which value instance is
+  /// written.
+  ///
+  /// @return { [Element[] -> Scatter[]] -> ValInst[] }
+  isl::union_map computeWritten() const {
+    // { [Element[] -> Scatter[]] -> ValInst[] }
+    auto EltWritten = applyDomainRange(AllWriteValInst, Schedule);
+
+    simplify(EltWritten);
+    return EltWritten;
   }
 
   /// Determine whether an access touches at most one element.
   ///
   /// The accessed element could be a scalar or accessing an array with constant
   /// subscript, such that all instances access only that element.
   ///
   /// @param MA The access to test.
OS.indent(Indent + 4) << "PHI scalars mapped:    "
                           << NumberOfMappedPHIScalars << '\n';
     OS.indent(Indent) << "}\n";
   }
 
   /// Return whether at least one transformation been applied.
   bool isModified() const { return NumberOfTargetsMapped > 0; }
 
 public:
-  DeLICMImpl(Scop *S) : ZoneAlgorithm(S) {}
+  DeLICMImpl(Scop *S, LoopInfo *LI) : ZoneAlgorithm(S, LI) {}
 
   /// Calculate the lifetime (definition to last use) of every array element.
   ///
   /// @return True if the computed lifetimes (#Zone) is usable.
   bool computeZone() {
     // Check that nothing strange occurs.
     if (!isCompatibleScop()) {
       DeLICMIncompatible++;
       return false;
     }
 
     DefUse.compute(S);
-    isl::union_set EltUnused, EltWritten;
+    isl::union_set EltUnused;
+    isl::union_map EltKnown, EltWritten;
 
     {
       IslMaxOperationsGuard MaxOpGuard(IslCtx.get(), DelicmMaxOps);
 
       computeCommon();
 
       EltUnused = computeLifetime();
+      EltKnown = computeKnown();
       EltWritten = computeWritten();
     }
     DeLICMAnalyzed++;
 
-    if (!EltUnused || !EltWritten) {
+    if (!EltUnused || !EltKnown || !EltWritten) {
       assert(isl_ctx_last_error(IslCtx.get()) == isl_error_quota &&
              "The only reason that these things have not been computed should "
              "be if the max-operations limit hit");
       DeLICMOutOfQuota++;
       DEBUG(dbgs() << "DeLICM analysis exceeded max_operations\n");
       DebugLoc Begin, End;
       getDebugLocations(getBBPairForRegion(&S->getRegion()), Begin, End);
       OptimizationRemarkAnalysis R(DEBUG_TYPE, "OutOfQuota", Begin,
                                    S->getEntry());
       R << "maximal number of operations exceeded during zone analysis";
       S->getFunction().getContext().diagnose(R);
       return false;
     }
 
-    Zone = OriginalZone = Knowledge(nullptr, EltUnused, EltWritten);
+    Zone = OriginalZone = Knowledge(nullptr, EltUnused, EltKnown, EltWritten);
     DEBUG(dbgs() << "Computed Zone:\n"; OriginalZone.print(dbgs(), 4));
 
     assert(Zone.isUsable() && OriginalZone.isUsable());
     return true;
   }
 
   /// Try to map as many scalars to unused array elements as possible.
   ///

 private:
   DeLICM(const DeLICM &) = delete;
   const DeLICM &operator=(const DeLICM &) = delete;
 
   /// The pass implementation, also holding per-scop data.
   std::unique_ptr<DeLICMImpl> Impl;
 
   void collapseToUnused(Scop &S) {
-    Impl = make_unique<DeLICMImpl>(&S);
+    auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+    Impl = make_unique<DeLICMImpl>(&S, &LI);
 
     if (!Impl->computeZone()) {
       DEBUG(dbgs() << "Abort because cannot reliably compute lifetimes\n");
       return;
     }
 
     DEBUG(dbgs() << "Collapsing scalars to unused array elements...\n");
     Impl->greedyCollapse();
 
     DEBUG(dbgs() << "\nFinal Scop:\n");
     DEBUG(S.print(dbgs()));
   }
 
 public:
   static char ID;
   explicit DeLICM() : ScopPass(ID) {}
 
   virtual void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequiredTransitive<ScopInfoRegionPass>();
+    AU.addRequired<LoopInfoWrapperPass>();
     AU.setPreservesAll();
   }
 
   virtual bool runOnScop(Scop &S) override {
     // Free resources for previous scop's computation, if not yet done.
     releaseMemory();
 
     collapseToUnused(S);

 char DeLICM::ID;
 } // anonymous namespace
 
 Pass *polly::createDeLICMPass() { return new DeLICM(); }
 
 INITIALIZE_PASS_BEGIN(DeLICM, "polly-delicm", "Polly - DeLICM/DePRE", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_END(DeLICM, "polly-delicm", "Polly - DeLICM/DePRE", false,
                     false)
 
 bool polly::isConflicting(
     isl::union_set ExistingOccupied, isl::union_set ExistingUnused,
     isl::union_map ExistingKnown, isl::union_map ExistingWrites,
     isl::union_set ProposedOccupied, isl::union_set ProposedUnused,
     isl::union_map ProposedKnown, isl::union_map ProposedWrites,
     llvm::raw_ostream *OS, unsigned Indent) {
   Knowledge Existing(std::move(ExistingOccupied), std::move(ExistingUnused),
                      std::move(ExistingKnown), std::move(ExistingWrites));
   Knowledge Proposed(std::move(ProposedOccupied), std::move(ProposedUnused),
                      std::move(ProposedKnown), std::move(ProposedWrites));
 
   return Knowledge::isConflicting(Existing, Proposed, OS, Indent);
 }

polly/trunk/test/DeLICM/reduction_constant_selfconflict.ll

+; RUN: opt %loadPolly -polly-flatten-schedule -polly-delicm-compute-known=true -polly-delicm -analyze < %s | FileCheck %s
+;
+;    void func(double *A) {
+;      for (int j = 0; j < 2; j += 1) { /* outer */
+;        double phi = 0.0;
+;        for (int i = 0; i < 4; i += 1) { /* reduction */
+;          phi += 4.2;
+;          A[j] = phi;
+;        }
+;        A[j] = phi;
+;      }
+;    }
+;
+define void @func(double* noalias nonnull %A) {
+entry:
+  br label %outer.preheader
+
+outer.preheader:
+  br label %outer.for
+
+outer.for:
+  %j = phi i32 [0, %outer.preheader], [%j.inc, %outer.inc]
+  %j.cmp = icmp slt i32 %j, 2
+  br i1 %j.cmp, label %reduction.preheader, label %outer.exit
+
+
+    reduction.preheader:
+      br label %reduction.for
+
+    reduction.for:
+      %i = phi i32 [0, %reduction.preheader], [%i.inc, %reduction.inc]
+      %phi = phi double [0.0, %reduction.preheader], [%add, %reduction.inc]
+      %i.cmp = icmp slt i32 %i, 4
+      %A_idx = getelementptr inbounds double, double* %A, i32 %j
+      br i1 %i.cmp, label %body, label %reduction.exit
+
+
+
+        body:
+          %add = fadd double %phi, 4.2
+          store double %add, double* %A_idx
+          br label %reduction.inc
+
+
+
+    reduction.inc:
+      %i.inc = add nuw nsw i32 %i, 1
+      br label %reduction.for
+
+    reduction.exit:
+      store double %phi, double* %A_idx
+      br label %outer.inc
+
+
+
+outer.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %outer.for
+
+outer.exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK:      After accesses {
+; CHECK-NEXT:     Stmt_reduction_preheader
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_preheader[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_preheader[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT:     Stmt_reduction_for
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 4 };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 4 };
+; CHECK-NEXT:     Stmt_body
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and i1 >= 0 and -5i0 <= i1 <= 8 - 5i0 and i1 <= 3 };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:     Stmt_reduction_inc
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : i1 >= 0 and -5i0 <= i1 <= 7 - 5i0 and i1 <= 3; Stmt_reduction_inc[1, 3] -> MemRef_A[1] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and i1 >= 0 and -5i0 <= i1 <= 3 };
+; CHECK-NEXT:     Stmt_reduction_exit
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_exit[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT: }

polly/trunk/test/DeLICM/reduction_looprotate.ll

+; RUN: opt %loadPolly -polly-flatten-schedule -polly-delicm -analyze < %s | FileCheck %s
+;
+;    void func(double *A) {
+;      for (int j = 0; j < 2; j += 1) { /* outer */
+;        for (int i = 0; i < 4; i += 1) { /* reduction */
+;          double phi = A[j];
+;          phi += 4.2;
+;          A[j] = phi;
+;        }
+;      }
+;    }
+;
+; There is nothing to do in this case. All accesses are in %body.
+;
+define void @func(double* noalias nonnull %A) {
+entry:
+  br label %outer.preheader
+
+outer.preheader:
+  br label %outer.for
+
+outer.for:
+  %j = phi i32 [0, %outer.preheader], [%j.inc, %outer.inc]
+  %j.cmp = icmp slt i32 %j, 2
+  br i1 %j.cmp, label %reduction.preheader, label %outer.exit
+
+
+    reduction.preheader:
+      br label %reduction.for
+
+    reduction.for:
+      %i = phi i32 [0, %reduction.preheader], [%i.inc, %reduction.inc]
+      br label %body
+
+
+
+        body:
+          %A_idx = getelementptr inbounds double, double* %A, i32 %j
+          %val = load double, double* %A_idx
+          %add = fadd double %val, 4.2
+          store double %add, double* %A_idx
+          br label %reduction.inc
+
+
+
+    reduction.inc:
+      %i.inc = add nuw nsw i32 %i, 1
+      %i.cmp = icmp slt i32 %i.inc, 4
+      br i1 %i.cmp, label %reduction.for, label %reduction.exit
+
+    reduction.exit:
+      br label %outer.inc
+
+
+
+outer.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %outer.for
+
+outer.exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK: No modification has been made

polly/trunk/test/DeLICM/reduction_looprotate_gvnpre.ll

+; RUN: opt %loadPolly -polly-flatten-schedule -polly-delicm-overapproximate-writes=true -polly-delicm-compute-known=true -polly-delicm -analyze < %s | FileCheck %s
+;
+;    void func(double *A) {
+;      for (int j = 0; j < 2; j += 1) { /* outer */
+;        double phi = 0.0;
+;        for (int i = 0; i < 4; i += 1) { /* reduction */
+;          phi += 4.2;
+;          A[j] = phi;
+;        }
+;      }
+;    }
+;
+define void @func(double* noalias nonnull %A) {
+entry:
+  br label %outer.preheader
+
+outer.preheader:
+  br label %outer.for
+
+outer.for:
+  %j = phi i32 [0, %outer.preheader], [%j.inc, %outer.inc]
+  %j.cmp = icmp slt i32 %j, 2
+  br i1 %j.cmp, label %reduction.preheader, label %outer.exit
+
+
+    reduction.preheader:
+      br label %reduction.for
+
+    reduction.for:
+      %i = phi i32 [0, %reduction.preheader], [%i.inc, %reduction.inc]
+      %phi = phi double [0.0, %reduction.preheader], [%add, %reduction.inc]
+      br label %body
+
+
+
+        body:
+          %add = fadd double %phi, 4.2
+          %A_idx = getelementptr inbounds double, double* %A, i32 %j
+          store double %add, double* %A_idx
+          br label %reduction.inc
+
+
+
+    reduction.inc:
+      %i.inc = add nuw nsw i32 %i, 1
+      %i.cmp = icmp slt i32 %i.inc, 4
+      br i1 %i.cmp, label %reduction.for, label %reduction.exit
+
+    reduction.exit:
+      br label %outer.inc
+
+
+
+outer.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %outer.for
+
+outer.exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK:      After accesses {
+; CHECK-NEXT:    Stmt_reduction_preheader
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_preheader[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_preheader[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT:     Stmt_reduction_for
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:     Stmt_body
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 and 3i1 <= 22 - 13i0 };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] : i0 >= 0 and 0 <= i1 <= 3 and 3i1 <= 21 - 13i0; Stmt_body[1, 3] -> MemRef_A[1] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:     Stmt_reduction_inc
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : i0 >= 0 and 0 <= i1 <= 3 and 3i1 <= 21 - 13i0; Stmt_reduction_inc[1, 3] -> MemRef_A[1] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT: }

polly/trunk/test/DeLICM/reduction_looprotate_hoisted.ll

+; RUN: opt %loadPolly -polly-invariant-load-hoisting -polly-flatten-schedule -polly-delicm-overapproximate-writes=true -polly-delicm-compute-known=true -polly-delicm -analyze < %s | FileCheck %s
+;
+;    void func(int *A, int* StartPtr) {
+;      for (int j = 0; j < 2; j += 1) { /* outer */
+;        int Start = *Startptr;
+;        int phi = Start;
+;        for (int i = Start; i < 4; i += 1) /* reduction */
+;          phi += 42;
+;        A[j] = phi;
+;      }
+;    }
+;
+define void @func(i32* noalias nonnull %A, i32* noalias nonnull %StartPtr) {
+entry:
+  br label %outer.preheader
+
+outer.preheader:
+  br label %outer.for
+
+outer.for:
+  %j = phi i32 [0, %outer.preheader], [%j.inc, %outer.inc]
+  %j.cmp = icmp slt i32 %j, 2
+  br i1 %j.cmp, label %reduction.preheader, label %outer.exit
+
+
+    reduction.preheader:
+      %Start = load i32, i32* %StartPtr
+      br label %reduction.for
+
+    reduction.for:
+      %i = phi i32 [%Start, %reduction.preheader], [%i.inc, %reduction.inc]
+      %phi = phi i32 [%Start, %reduction.preheader], [%mul, %reduction.inc]
+      br label %body
+
+
+
+        body:
+          %mul = mul i32 %phi, 2
+          br label %reduction.inc
+
+
+
+    reduction.inc:
+      %i.inc = add nuw nsw i32 %i, 1
+      %i.cmp = icmp slt i32 %i.inc, 4
+      br i1 %i.cmp, label %reduction.for, label %reduction.exit
+
+    reduction.exit:
+      %A_idx = getelementptr inbounds i32, i32* %A, i32 %j
+      store i32 %mul, i32* %A_idx
+      br label %outer.inc
+
+
+
+outer.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %outer.for
+
+outer.exit:
+  br label %return
+
+return:
+  ret void
+}
+
+; FIXME: The accesses for %i should not be there because, with
+; load-hoisting %Start is an affine loop. To be fixed in ScopBuilder.
+
+; CHECK:      After accesses {
+; CHECK-NEXT:     Stmt_reduction_preheader
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [Start] -> { Stmt_reduction_preheader[i0] -> MemRef_i__phi[] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [Start] -> { Stmt_reduction_preheader[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: [Start] -> { Stmt_reduction_preheader[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT:     Stmt_reduction_for
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [Start] -> { Stmt_reduction_for[i0, i1] -> MemRef_i__phi[] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [Start] -> { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: [Start] -> { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and -i0 < i1 <= 3 - Start; Stmt_reduction_for[1, 0] -> MemRef_A[1] : Start >= 4; Stmt_reduction_for[0, 0] -> MemRef_A[0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [Start] -> { Stmt_reduction_for[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: [Start] -> { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and i0 <= i1 <= 3 - Start; Stmt_reduction_for[i0, 0] -> MemRef_A[i0] : 0 <= i0 <= 1 and i0 <= -4 + Start; Stmt_reduction_for[1, 0] -> MemRef_A[1] : Start <= 4 };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [Start] -> { Stmt_reduction_for[i0, i1] -> MemRef_i[] };
+; CHECK-NEXT:     Stmt_body
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [Start] -> { Stmt_body[i0, i1] -> MemRef_mul[] };
+; CHECK-NEXT:            new: [Start] -> { Stmt_body[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and i0 <= i1 <= 3 - Start; Stmt_body[i0, 0] -> MemRef_A[i0] : 0 <= i0 <= 1 and i0 <= -4 + Start; Stmt_body[1, 0] -> MemRef_A[1] : Start <= 4 };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [Start] -> { Stmt_body[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: [Start] -> { Stmt_body[i0, i1] -> MemRef_A[i0] : Start <= 3 and 0 <= i0 <= 1 and i0 <= i1 <= 3 - Start; Stmt_body[1, 0] -> MemRef_A[1]; Stmt_body[0, 0] -> MemRef_A[0] : Start >= 4 };
+; CHECK-NEXT:     Stmt_reduction_inc
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [Start] -> { Stmt_reduction_inc[i0, i1] -> MemRef_i__phi[] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [Start] -> { Stmt_reduction_inc[i0, i1] -> MemRef_mul[] };
+; CHECK-NEXT:            new: [Start] -> { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : Start <= 3 and 0 <= i0 <= 1 and i0 <= i1 <= 3 - Start; Stmt_reduction_inc[1, 0] -> MemRef_A[1]; Stmt_reduction_inc[0, 0] -> MemRef_A[0] : Start >= 4 };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [Start] -> { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: [Start] -> { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 < i1 <= 3 - Start; Stmt_reduction_inc[i0, 0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [Start] -> { Stmt_reduction_inc[i0, i1] -> MemRef_i[] };
+; CHECK-NEXT:     Stmt_reduction_exit
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [Start] -> { Stmt_reduction_exit[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [Start] -> { Stmt_reduction_exit[i0] -> MemRef_mul[] };
+; CHECK-NEXT:            new: [Start] -> { Stmt_reduction_exit[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT: }

polly/trunk/test/DeLICM/reduction_looprotate_licm.ll

+; RUN: opt %loadPolly -polly-flatten-schedule -polly-delicm-overapproximate-writes=true -polly-delicm-compute-known=true -polly-delicm -analyze < %s | FileCheck %s
+;
+;    void func(double *A) {
+;      for (int j = 0; j < 2; j += 1) { /* outer */
+;        double phi = A[j];
+;        for (int i = 0; i < 4; i += 1) /* reduction */
+;          phi += 4.2;
+;        A[j] = phi;
+;      }
+;    }
+;
+define void @func(double* noalias nonnull %A) {
+entry:
+  br label %outer.preheader
+
+outer.preheader:
+  br label %outer.for
+
+outer.for:
+  %j = phi i32 [0, %outer.preheader], [%j.inc, %outer.inc]
+  %j.cmp = icmp slt i32 %j, 2
+  br i1 %j.cmp, label %reduction.preheader, label %outer.exit
+
+
+    reduction.preheader:
+      %A_idx = getelementptr inbounds double, double* %A, i32 %j
+      %init = load double, double* %A_idx
+      br label %reduction.for
+
+    reduction.for:
+      %i = phi i32 [0, %reduction.preheader], [%i.inc, %reduction.inc]
+      %phi = phi double [%init, %reduction.preheader], [%add, %reduction.inc]
+      br label %body
+
+
+
+        body:
+          %add = fadd double %phi, 4.2
+          br label %reduction.inc
+
+
+
+    reduction.inc:
+      %i.inc = add nuw nsw i32 %i, 1
+      %i.cmp = icmp slt i32 %i.inc, 4
+      br i1 %i.cmp, label %reduction.for, label %reduction.exit
+
+    reduction.exit:
+      store double %add, double* %A_idx
+      br label %outer.inc
+
+
+
+outer.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %outer.for
+
+outer.exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK:      After accesses {
+; CHECK-NEXT:     Stmt_reduction_preheader
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_reduction_preheader[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_preheader[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_preheader[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT:     Stmt_reduction_for
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:     Stmt_body
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] : 0 <= i1 <= 3 and -14i0 <= 3i1 <= 22 - 14i0; Stmt_body[1, 3] -> MemRef_A[1] };
+; CHECK-NEXT:     Stmt_reduction_inc
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : 0 <= i1 <= 3 and -14i0 <= 3i1 <= 22 - 14i0; Stmt_reduction_inc[1, 3] -> MemRef_A[1] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:     Stmt_reduction_exit
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_add[] };
+; CHECK-NEXT:            new: { Stmt_reduction_exit[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT: }

polly/trunk/test/DeLICM/reduction_looprotate_load.ll

+; RUN: opt %loadPolly -polly-flatten-schedule -polly-delicm-overapproximate-writes=true -polly-delicm-compute-known=true -polly-delicm -analyze < %s | FileCheck %s
+;
+;    void func(int *A, double* StartPtr) {
+;      for (int j = 0; j < 2; j += 1) { /* outer */
+;        int phi = *StartPtr;
+;        for (int i = 0; i < 4; i += 1) /* reduction */
+;          phi += 4.2;
+;        A[j] = phi;
+;      }
+;    }
+;
+define void @func(double* noalias nonnull %A, double* noalias nonnull %StartPtr) {
+entry:
+  br label %outer.preheader
+
+outer.preheader:
+  br label %outer.for
+
+outer.for:
+  %j = phi i32 [0, %outer.preheader], [%j.inc, %outer.inc]
+  %j.cmp = icmp slt i32 %j, 2
+  br i1 %j.cmp, label %reduction.preheader, label %outer.exit
+
+
+    reduction.preheader:
+      %Start = load double, double* %StartPtr
+      br label %reduction.for
+
+    reduction.for:
+      %i = phi i32 [0, %reduction.preheader], [%i.inc, %reduction.inc]
+      %phi = phi double [%Start, %reduction.preheader], [%add, %reduction.inc]
+      br label %body
+
+
+
+        body:
+          %add = fadd double %phi, 4.2
+          br label %reduction.inc
+
+
+
+    reduction.inc:
+      %i.inc = add nuw nsw i32 %i, 1
+      %i.cmp = icmp slt i32 %i.inc, 4
+      br i1 %i.cmp, label %reduction.for, label %reduction.exit
+
+    reduction.exit:
+      %A_idx = getelementptr inbounds double, double* %A, i32 %j
+      store double %add, double* %A_idx
+      br label %outer.inc
+
+
+
+outer.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %outer.for
+
+outer.exit:
+  br label %return
+
+return:
+  ret void
+}
+
+; CHECK:      After accesses {
+; CHECK-NEXT:     Stmt_reduction_preheader
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_reduction_preheader[i0] -> MemRef_StartPtr[0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_preheader[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_preheader[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT:     Stmt_reduction_for
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:     Stmt_body
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] : 0 <= i1 <= 3 and -14i0 <= 3i1 <= 22 - 14i0; Stmt_body[1, 3] -> MemRef_A[1] };
+; CHECK-NEXT:     Stmt_reduction_inc
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : 0 <= i1 <= 3 and -14i0 <= 3i1 <= 22 - 14i0; Stmt_reduction_inc[1, 3] -> MemRef_A[1] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:     Stmt_reduction_exit
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_add[] };
+; CHECK-NEXT:            new: { Stmt_reduction_exit[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT: }

polly/trunk/test/DeLICM/reduction_looprotate_readonly.ll

+; RUN: opt %loadPolly -polly-flatten-schedule -polly-delicm-overapproximate-writes=true -polly-delicm-compute-known=true -polly-delicm -analyze < %s | FileCheck %s
+;
+;    void func(double *A, double Start) {
+;      for (int j = 0; j < 2; j += 1) { /* outer */
+;        double phi = Start;
+;        for (int i = 0; i < 4; i += 1) /* reduction */
+;          phi += 4.2;
+;        A[j] = phi;
+;      }
+;    }
+;
+define void @func(double* noalias nonnull %A, double %Start) {
+entry:
+  br label %outer.preheader
+
+outer.preheader:
+  br label %outer.for
+
+outer.for:
+  %j = phi i32 [0, %outer.preheader], [%j.inc, %outer.inc]
+  %j.cmp = icmp slt i32 %j, 2
+  br i1 %j.cmp, label %reduction.preheader, label %outer.exit
+
+
+    reduction.preheader:
+      br label %reduction.for
+
+    reduction.for:
+      %i = phi i32 [0, %reduction.preheader], [%i.inc, %reduction.inc]
+      %phi = phi double [%Start, %reduction.preheader], [%add, %reduction.inc]
+      br label %body
+
+
+
+        body:
+          %add = fadd double %phi, 4.2
+          br label %reduction.inc
+
+
+
+    reduction.inc:
+      %i.inc = add nuw nsw i32 %i, 1
+      %i.cmp = icmp slt i32 %i.inc, 4
+      br i1 %i.cmp, label %reduction.for, label %reduction.exit
+
+    reduction.exit:
+      %A_idx = getelementptr inbounds double, double* %A, i32 %j
+      store double %add, double* %A_idx
+      br label %outer.inc
+
+
+
+outer.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %outer.for
+
+outer.exit:
+  br label %return
+
+return:
+  ret void
+}
+
+; CHECK:      After accesses {
+; CHECK-NEXT:     Stmt_reduction_preheader
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_preheader[i0] -> MemRef_Start[] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_preheader[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_preheader[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT:     Stmt_reduction_for
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:     Stmt_body
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] : 0 <= i1 <= 3 and -14i0 <= 3i1 <= 22 - 14i0; Stmt_body[1, 3] -> MemRef_A[1] };
+; CHECK-NEXT:     Stmt_reduction_inc
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : 0 <= i1 <= 3 and -14i0 <= 3i1 <= 22 - 14i0; Stmt_reduction_inc[1, 3] -> MemRef_A[1] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:     Stmt_reduction_exit
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_add[] };
+; CHECK-NEXT:            new: { Stmt_reduction_exit[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT: }

polly/trunk/test/DeLICM/reduction_looprotate_synthesizable.ll

+; RUN: opt %loadPolly -polly-flatten-schedule -polly-delicm-overapproximate-writes=true -polly-delicm-compute-known=true -polly-delicm -analyze < %s | FileCheck %s
+;
+;    void func(int *A) {
+;      for (int j = 0; j < 2; j += 1) { /* outer */
+;        int phi = j;
+;        for (int i = 0; i < 4; i += 1) /* reduction */
+;          phi += 42;
+;        A[j] = phi;
+;      }
+;    }
+;
+define void @func(i32* noalias nonnull %A) {
+entry:
+  br label %outer.preheader
+
+outer.preheader:
+  br label %outer.for
+
+outer.for:
+  %j = phi i32 [0, %outer.preheader], [%j.inc, %outer.inc]
+  %j.cmp = icmp slt i32 %j, 2
+  br i1 %j.cmp, label %reduction.preheader, label %outer.exit
+
+
+    reduction.preheader:
+      br label %reduction.for
+
+    reduction.for:
+      %i = phi i32 [0, %reduction.preheader], [%i.inc, %reduction.inc]
+      %phi = phi i32 [%j, %reduction.preheader], [%mul, %reduction.inc]
+      br label %body
+
+
+
+        body:
+          %mul = mul i32 %phi, 42
+          br label %reduction.inc
+
+
+
+    reduction.inc:
+      %i.inc = add nuw nsw i32 %i, 1
+      %i.cmp = icmp slt i32 %i.inc, 4
+      br i1 %i.cmp, label %reduction.for, label %reduction.exit
+
+    reduction.exit:
+      %A_idx = getelementptr inbounds i32, i32* %A, i32 %j
+      store i32 %mul, i32* %A_idx
+      br label %outer.inc
+
+
+
+outer.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %outer.for
+
+outer.exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK:      After accesses {
+; CHECK-NEXT:     Stmt_reduction_preheader
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_preheader[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_preheader[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT:     Stmt_reduction_for
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:     Stmt_body
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_mul[] };
+; CHECK-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] : 0 <= i1 <= 3 and -14i0 <= 3i1 <= 22 - 14i0; Stmt_body[1, 3] -> MemRef_A[1] };
+; CHECK-NEXT:     Stmt_reduction_inc
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_mul[] };
+; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : 0 <= i1 <= 3 and -14i0 <= 3i1 <= 22 - 14i0; Stmt_reduction_inc[1, 3] -> MemRef_A[1] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:     Stmt_reduction_exit
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_mul[] };
+; CHECK-NEXT:            new: { Stmt_reduction_exit[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT: }

polly/trunk/test/DeLICM/reduction_looprotate_undef.ll

+; RUN: opt %loadPolly -polly-flatten-schedule -polly-delicm-overapproximate-writes=true -polly-delicm-compute-known=true -polly-delicm -analyze < %s | FileCheck %s
+;
+;    void func(int *A) {
+;      for (int j = 0; j < 2; j += 1) { /* outer */
+;        int phi;
+;        for (int i = 0; i < 4; i += 1) /* reduction */
+;          phi += 42;
+;        A[j] = phi;
+;      }
+;    }
+;
+define void @func(i32* noalias nonnull %A) {
+entry:
+  br label %outer.preheader
+
+outer.preheader:
+  br label %outer.for
+
+outer.for:
+  %j = phi i32 [0, %outer.preheader], [%j.inc, %outer.inc]
+  %j.cmp = icmp slt i32 %j, 2
+  br i1 %j.cmp, label %reduction.preheader, label %outer.exit
+
+
+    reduction.preheader:
+      br label %reduction.for
+
+    reduction.for:
+      %i = phi i32 [0, %reduction.preheader], [%i.inc, %reduction.inc]
+      %phi = phi i32 [undef, %reduction.preheader], [%conv, %reduction.inc]
+      br label %body
+
+
+
+        body:
+          %fval = sitofp i32 %phi to double
+          %add = fadd double %fval, 4.2
+          %conv = fptosi double %add to i32
+          br label %reduction.inc
+
+
+
+    reduction.inc:
+      %i.inc = add nuw nsw i32 %i, 1
+      %i.cmp = icmp slt i32 %i.inc, 4
+      br i1 %i.cmp, label %reduction.for, label %reduction.exit
+
+    reduction.exit:
+      %A_idx = getelementptr inbounds i32, i32* %A, i32 %j
+      store i32 %conv, i32* %A_idx
+      br label %outer.inc
+
+
+
+outer.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %outer.for
+
+outer.exit:
+  br label %return
+
+return:
+  ret void
+}
+
+; CHECK:      After accesses {
+; CHECK-NEXT:     Stmt_reduction_preheader
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_preheader[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_preheader[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT:     Stmt_reduction_for
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:     Stmt_body
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_conv[] };
+; CHECK-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] : 0 <= i1 <= 3 and -14i0 <= 3i1 <= 22 - 14i0; Stmt_body[1, 3] -> MemRef_A[1] };
+; CHECK-NEXT:     Stmt_reduction_inc
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_conv[] };
+; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : 0 <= i1 <= 3 and -14i0 <= 3i1 <= 22 - 14i0; Stmt_reduction_inc[1, 3] -> MemRef_A[1] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:     Stmt_reduction_exit
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_conv[] };
+; CHECK-NEXT:            new: { Stmt_reduction_exit[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT: }

polly/trunk/test/DeLICM/reduction_overapproximate.ll

-; RUN: opt %loadPolly -polly-flatten-schedule -polly-delicm-overapproximate-writes=true -polly-delicm -analyze < %s | FileCheck %s --check-prefix=APPROX
-; RUN: opt %loadPolly -polly-flatten-schedule -polly-delicm-overapproximate-writes=false -polly-delicm -analyze < %s | FileCheck %s --check-prefix=EXACT
+; RUN: opt %loadPolly -polly-flatten-schedule -polly-delicm-compute-known=true -polly-delicm-overapproximate-writes=true -polly-delicm -analyze < %s | FileCheck %s --check-prefix=APPROX
+; RUN: opt %loadPolly -polly-flatten-schedule -polly-delicm-compute-known=true -polly-delicm-overapproximate-writes=false -polly-delicm -analyze < %s | FileCheck %s --check-prefix=EXACT
 ;
 ;    void func(double *A {
 ;      for (int j = -1; j < 3; j += 1) { /* outer */
 ;        double phi = 0.0;
 ;        if (0 < j)
 ;          for (int i = 0; i < j; i += 1) /* reduction */
 ;            phi += 4.2;
 ;        A[j] = phi;

 
 outer.exit:
   br label %return
 
 return:
   ret void
 }
 
-; TODO: MemRef_phi__phi[] should be mapped to A[j-1] as as well, but it is
-;       occupied by %add. It is actually the same value but DeLICM currently
-;       does not known without the "Known"-extension.
 
 ; APPROX:      After accesses {
 ; APPROX-NEXT:     Stmt_reduction_checkloop
 ; APPROX-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; APPROX-NEXT:                 { Stmt_reduction_checkloop[i0] -> MemRef_val__phi[] };
 ; APPROX-NEXT:            new: { Stmt_reduction_checkloop[i0] -> MemRef_A[-1 + i0] : 0 <= i0 <= 3 };
 ; APPROX-NEXT:     Stmt_reduction_preheader
 ; APPROX-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; APPROX-NEXT:                 { Stmt_reduction_preheader[i0] -> MemRef_phi__phi[] };
+; APPROX-NEXT:            new: { Stmt_reduction_preheader[i0] -> MemRef_A[-1 + i0] : 2 <= i0 <= 3 };
 ; APPROX-NEXT:     Stmt_reduction_for
 ; APPROX-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
 ; APPROX-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
+; APPROX-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[-1 + i0] : i0 <= 3 and i1 >= 0 and 2 - 3i0 <= i1 <= 11 - 3i0 and i1 <= 2 and i1 <= -2 + i0 };
 ; APPROX-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; APPROX-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi[] };
 ; APPROX-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[-1 + i0] : i0 <= 3 and i1 >= 0 and 2 - 3i0 <= i1 <= 11 - 3i0 and i1 <= 2 and i1 <= -2 + i0 };
 ; APPROX-NEXT:     Stmt_body
 ; APPROX-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; APPROX-NEXT:                { Stmt_body[i0, i1] -> MemRef_add[] };
 ; APPROX-NEXT:           new: { Stmt_body[i0, i1] -> MemRef_A[-1 + i0] : i0 <= 3 and i1 >= 0 and 2 - 3i0 <= i1 <= 10 - 3i0 and i1 <= 1 and i1 <= -2 + i0 };
 ; APPROX-NEXT:            ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
 ; APPROX-NEXT:                { Stmt_body[i0, i1] -> MemRef_phi[] };
 ; APPROX-NEXT:           new: { Stmt_body[i0, i1] -> MemRef_A[-1 + i0] : i0 <= 3 and 0 <= i1 <= -2 + i0 };
 ; APPROX-NEXT:     Stmt_reduction_inc
 ; APPROX-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
 ; APPROX-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_add[] };
 ; APPROX-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[-1 + i0] : i0 <= 3 and 0 <= i1 <= -2 + i0 };
 ; APPROX-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; APPROX-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
+; APPROX-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[2] : i0 <= 3 and 0 <= i1 <= -2 + i0 };
 ; APPROX-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; APPROX-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_val__phi[] };
 ; APPROX-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[-1 + i0] : 2 <= i0 <= 3 and 0 <= i1 <= -2 + i0 };
 ; APPROX-NEXT:     Stmt_reduction_exit
 ; APPROX-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
 ; APPROX-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_val__phi[] };
 ; APPROX-NEXT:            new: { Stmt_reduction_exit[i0] -> MemRef_A[-1 + i0] : 0 <= i0 <= 3 };
 ; APPROX-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; APPROX-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_A[-1 + i0] };
 ; APPROX-NEXT: }
 
 
 ; EXACT: No modification has been made