[Polly][ZoneAlgo/ForwardOpTree] Normalize PHIs to their known incoming values.

[Meinersbur]

Summary

Represent PHIs by their incoming values instead of an opaque value of themselves. This allows ForwardOpTree to "look through" the PHIs and forward the incoming values since forwardings PHIs is currently not supported.

This is particularly useful to cope with PHIs inserted by GVN LoadPRE. The incoming values all resolve to a load from a single array element which then can be forwarded.

It should in theory also reduce spurious conflicts in value mapping (DeLICM), but I have not yet found a profitable case yet.

To avoid transitive closure and potentially necessary overapproximations of those, PHIs that may reference themselves are excluded from normalization and keep their opaque self-representation.

The feature is disabled by default because it currently causes a significant compile time increase (when the max operations limit is disabled). Either we resolve this bottleneck (mostly in ZoneAlgorithm::computeKnownFromLoad()) or introduce support forwarding PHIs instead. In both cases, having the ability to remove any (non-recursive) PHI from the known content map is a good test to determine whether these cause a problem.

[Meinersbur]

Add selfrefphi test case

[grosser]

LGTM, otherwise.

test/ForwardOpTree/atax.ll

104

Do we need all these attributes?

[Meinersbur]

• Introduce isNormalizable to resolve TODO
• Remove unused function attributes in test-case
• Add example to NormalizedPHI doxygen

[bollu]

include/polly/ZoneAlgo.h

118

"We correctness" -> "We want correctness", perhaps?

309

What does Normalized exactly refer to, here? I assume it refers to the PHI node normalization, but can we look for a better name? Normal is one of the most overloaded words there is :). Something like, isUnderstandablePHIRead? (I don't like that name either)

lib/Transform/ZoneAlgo.cpp

487

consider const PHINode *PHI? From what I can see, no mutation is required of the PHI, and all methods used from the Phi node have const versions.

771

Could you please document what Input and NormalizedPHIs are expected to look like?

773

consider const DenseSet<PHINode *> &TranslatedPHIs? It's only used to count.

961

Double negative: consider assert(PHIMap.is_single_valued().is_true())

[Meinersbur]

• Address Siddharth's remarks
• Fix one more TODO

[Meinersbur]

include/polly/ZoneAlgo.h

309

@see #ZoneAlgorithm::NormalizeMap which explains what is going on.

I agree that there might be a better name than "normalize", however I am 80% satisfied with the name. Due to the existence of PHIs, there are multiple ValInsts representing the same value. "Normalization" is the process of keeping (ideally) one of these.

"Computable" as used in ComputedPHIs might be an alternative. However, PHINodes are also not the only source of normalization. For instance, a LoadInst might always read a previously stored ValInst. We could normalize the ValInst for the loaded value by the ValInst that was stored before.

isUnderstandablePHIRead kind of implies to me that other PHIs are not understandable, what would that mean?

lib/Transform/ZoneAlgo.cpp

487

I did the change, but note that IMHO the const here is useless. The llvm::PHINode structure has not been designed around constness. E.g.

cast<PHINode>(Cur->op_begin()->getUser())

gets you a const-free object without any const-cast, the const gives a false sense that the object cannot be modified and adds clutter to declarations.

Generally, llvm::Value objects are identified by their address. That is, even after modifying it, we still means the same SSA value, so const does not accomplish anything,. This is different for e.g. SCEV, DenseSet.

In the past (eg. rL292480) we already had to remove const keywords that were added just because it could be added; it forced us to insert const_casts if we wanted to change code.

961

is_single_valued() returns a tri-valued isl::boolean. The intended meaning is

assert(PHIMap.is_single_valued().is_true_or_error());

Unfortunately is_true_or_error() did not make it into the isl API. Another alternative could be

assert(PHIMap.is_single_valued().is_error() || PHIMap.is_single_valued().is_true());

Unfortunately the quota limit could run out in the second call of is_single_valued(), such that the calls return different values.

include/polly/ZoneAlgo.h

 // Derive information about array elements between statements ("Zones").
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_ZONEALGO_H
 #define POLLY_ZONEALGO_H
 
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "isl/isl-noexceptions.h"
 #include <memory>
 
 namespace llvm {
 class Value;
 class LoopInfo;
 class Loop;
+class PHINode;
 } // namespace llvm
 
 namespace polly {
 class Scop;
 class ScopStmt;
 class MemoryAccess;
+class ScopArrayInfo;
 
 /// Return only the mappings that map to known values.
 ///
 /// @param UMap { [] -> ValInst[] }
 ///
 /// @return { [] -> ValInst[] }
 isl::union_map filterKnownValInst(const isl::union_map &UMap);
 
protected:
   /// Used with -polly-use-llvm-names=false as an alternative method to get
   /// unique ids that do not depend on pointer values.
   llvm::DenseMap<llvm::Value *, isl::id> ValueIds;
 
   /// Set of array elements that can be reliably used for zone analysis.
   /// { Element[] }
   isl::union_set CompatibleElts;
 
+  /// List of PHIs that may transitively refer to themselves.
+  ///
+  /// Computing them would require a polyhedral transitive closure operation,
+  /// for which isl may only return an approximation. We correctness, we always
+  /// require an exact result. Hence, we exclude such PHIs.
+  llvm::SmallPtrSet<llvm::PHINode *, 4> RecursivePHIs;
+
+  /// PHIs that have been computed.
+  ///
+  /// Computed PHIs are replaced by their incoming values.
+  llvm::DenseSet<llvm::PHINode *> ComputedPHIs;
+
+  /// For computed PHIs, contains the ValInst they stand for.
+  ///
+  /// Only ValInsts in #ComputedPHIs are present in this map. Other values are
+  /// assumed to represent themselves. This is to avoid adding lots of identity
+  /// entries to this map.
+  ///
+  /// { PHIValInst[] -> IncomingValInst[] }
+  isl::union_map NormalizedPHI;
+
+  /// Cache for computePerPHI(const ScopArrayInfo *)
+  llvm::SmallDenseMap<llvm::PHINode *, isl::union_map> PerPHIMaps;
+
   /// Prepare the object before computing the zones of @p S.
   ///
   /// @param PassName Name of the pass using this analysis.
   /// @param S        The SCoP to process.
   /// @param LI       LoopInfo analysis used to determine synthesizable values.
   ZoneAlgorithm(const char *PassName, Scop *S, llvm::LoopInfo *LI);
 
 private:
private:
 
   void addArrayReadAccess(MemoryAccess *MA);
 
   /// Return the ValInst write by a (must-)write access. Returns the 'unknown'
   /// ValInst if there is no single ValInst[] the array element written to will
   /// have.
   ///
   /// @return { ValInst[] }
-  isl::map getWrittenValue(MemoryAccess *MA, isl::map AccRel);
+  isl::union_map getWrittenValue(MemoryAccess *MA, isl::map AccRel);
 
   void addArrayWriteAccess(MemoryAccess *MA);
 
 protected:
   isl::union_set makeEmptyUnionSet() const;
 
   isl::union_map makeEmptyUnionMap() const;
 
+  /// For each 'execution' of a PHINode, get the incoming block that was
+  /// executed before.
+  ///
+  /// For each PHI instance we can directly determine which was the incoming
+  /// block, and hence derive which value the PHI has.
+  ///
+  /// @param SAI The ScopArrayInfo representing the PHI's storage.
+  ///
+  /// @return { DomainPHIRead[] -> DomainPHIWrite[] }
+  isl::union_map computePerPHI(const polly::ScopArrayInfo *SAI);
+
   /// Find the array elements that can be used for zone analysis.
   void collectCompatibleElts();
 
   /// Get the schedule for @p Stmt.
   ///
   /// The domain of the result is as narrow as possible.
   isl::map getScatterFor(ScopStmt *Stmt) const;
 
protected:
   /// @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(llvm::Value *Val, ScopStmt *UserStmt, llvm::Loop *Scope,
                        bool IsCertain = true);
 
+  /// Create and normalize a ValInst.
+  ///
+  /// @see makeValInst
+  /// @see normalizeValInst
+  isl::union_map makeNormalizedValInst(llvm::Value *Val, ScopStmt *UserStmt,
+                                       llvm::Loop *Scope,
+                                       bool IsCertain = true);
+
   /// Return whether @p MA can be used for transformations (e.g. OpTree load
   /// forwarding, DeLICM mapping).
   bool isCompatibleAccess(MemoryAccess *MA);
 
   /// Compute the different zones.
   void computeCommon();
 
+  ///  Compute the normalization map that replaces PHIs by their incoming
+  ///  values.
+  void computeNormalizedPHIs();
+
   /// Print the current state of all MemoryAccesses to @p.
   void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const;
 
+  /// @{
+  /// Determine whether the argument does not map to any computed PHI. Those
+  /// should have been replaced by their incoming values.
+  bool isNormalized(isl::map Map);
+  bool isNormalized(isl::union_map Map);
+  /// @}
+
 public:
   /// Return the SCoP this object is analyzing.
   Scop *getScop() const { return S; }
 
   /// A reaching definition zone is known to have the definition's written value
   /// if the definition is a MUST_WRITE.
   ///
   /// @return { [Element[] -> Zone[]] -> ValInst[] }

lib/Transform/DeLICM.cpp

computeValueUses(const ScopArrayInfo *SAI) {
     auto Lifetime = betweenScatter(WriteScatter, UseScatter, false, true);
 
     // { DomainDef[] -> DomainRead[] }
     auto DefUses = give(isl_union_map_domain_factor_domain(Uses.take()));
 
     return std::make_pair(DefUses, Lifetime);
   }
 
-  /// For each 'execution' of a PHINode, get the incoming block that was
-  /// executed before.
-  ///
-  /// For each PHI instance we can directly determine which was the incoming
-  /// block, and hence derive which value the PHI has.
-  ///
-  /// @param SAI The ScopArrayInfo representing the PHI's storage.
-  ///
-  /// @return { DomainPHIRead[] -> DomainPHIWrite[] }
-  isl::union_map computePerPHI(const ScopArrayInfo *SAI) {
-    assert(SAI->isPHIKind());
-
-    // { DomainPHIWrite[] -> Scatter[] }
-    auto PHIWriteScatter = makeEmptyUnionMap();
-
-    // Collect all incoming block timepoint.
-    for (auto *MA : S->getPHIIncomings(SAI)) {
-      auto Scatter = getScatterFor(MA);
-      PHIWriteScatter =
-          give(isl_union_map_add_map(PHIWriteScatter.take(), Scatter.take()));
-    }
-
-    // { DomainPHIRead[] -> Scatter[] }
-    auto PHIReadScatter = getScatterFor(S->getPHIRead(SAI));
-
-    // { DomainPHIRead[] -> Scatter[] }
-    auto BeforeRead = beforeScatter(PHIReadScatter, true);
-
-    // { Scatter[] }
-    auto WriteTimes = singleton(
-        give(isl_union_map_range(PHIWriteScatter.copy())), ScatterSpace);
-
-    // { DomainPHIRead[] -> Scatter[] }
-    auto PHIWriteTimes =
-        give(isl_map_intersect_range(BeforeRead.take(), WriteTimes.take()));
-    auto LastPerPHIWrites = give(isl_map_lexmax(PHIWriteTimes.take()));
-
-    // { DomainPHIRead[] -> DomainPHIWrite[] }
-    auto Result = give(isl_union_map_apply_range(
-        isl_union_map_from_map(LastPerPHIWrites.take()),
-        isl_union_map_reverse(PHIWriteScatter.take())));
-    assert(isl_union_map_is_single_valued(Result.keep()) == isl_bool_true);
-    assert(isl_union_map_is_injective(Result.keep()) == isl_bool_true);
-    return Result;
-  }
-
   /// Try to map a MemoryKind::Value to a given array element.
   ///
   /// @param SAI       Representation of the scalar's memory to map.
   /// @param TargetElt { Scatter[] -> Element[] }
   ///                  Suggestion where to map a scalar to when at a timepoint.
   ///
   /// @return true if the scalar was successfully mapped.
   bool tryMapValue(const ScopArrayInfo *SAI, isl::map TargetElt) {
isl::union_map EltKnown, EltWritten;
       computeCommon();
 
       EltUnused = computeLifetime();
       EltKnown = computeKnown(true, false);
       EltWritten = computeWritten();
     }
     DeLICMAnalyzed++;
 
-    if (!EltUnused || !EltKnown || !EltWritten) {
+    if (!NormalizedPHI || !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,

lib/Transform/ForwardOpTree.cpp

 using namespace llvm;
 using namespace polly;
 
 static cl::opt<bool>
     AnalyzeKnown("polly-optree-analyze-known",
                  cl::desc("Analyze array contents for load forwarding"),
                  cl::cat(PollyCategory), cl::init(true), cl::Hidden);
 
+static cl::opt<bool>
+    NormalizePHIs("polly-optree-normalize-phi",
+                  cl::desc("Replace PHIs by their incoming values"),
+                  cl::cat(PollyCategory), cl::init(false), cl::Hidden);
+
 static cl::opt<unsigned>
     MaxOps("polly-optree-max-ops",
            cl::desc("Maximum number of ISL operations to invest for known "
                     "analysis; 0=no limit"),
            cl::init(1000000), cl::cat(PollyCategory), cl::Hidden);
 
 STATISTIC(KnownAnalyzed, "Number of successfully analyzed SCoPs");
 STATISTIC(KnownOutOfQuota,
bool computeKnownValues() {
 
     // Check that nothing strange occurs.
     collectCompatibleElts();
 
     {
       IslQuotaScope QuotaScope = MaxOpGuard.enter();
 
       computeCommon();
+      if (NormalizePHIs)
+        computeNormalizedPHIs();
       Known = computeKnown(true, true);
 
       // Preexisting ValInsts use the known content analysis of themselves.
       Translator = makeIdentityMap(Known.range(), false);
     }
 
-    if (!Known || !Translator) {
+    if (!Known || !Translator || !NormalizedPHI) {
       assert(isl_ctx_last_error(IslCtx.get()) == isl_error_quota);
       Known = nullptr;
       Translator = nullptr;
+      NormalizedPHI = nullptr;
       DEBUG(dbgs() << "Known analysis exceeded max_operations\n");
       return false;
     }
 
     KnownAnalyzed++;
     DEBUG(dbgs() << "All known: " << Known << "\n");
 
     return true;
   }
 
   void printStatistics(raw_ostream &OS, int Indent = 0) {
     OS.indent(Indent) << "Statistics {\n";
     OS.indent(Indent + 4) << "Instructions copied: " << NumInstructionsCopied
                           << '\n';
     OS.indent(Indent + 4) << "Known loads forwarded: " << NumKnownLoadsForwarded
                           << '\n';
-  OS.indent(Indent + 4) << "Reloads: " << NumReloads<< '\n';
+    OS.indent(Indent + 4) << "Reloads: " << NumReloads << '\n';
     OS.indent(Indent + 4) << "Read-only accesses copied: " << NumReadOnlyCopied
                           << '\n';
     OS.indent(Indent + 4) << "Operand trees forwarded: " << NumForwardedTrees
                           << '\n';
     OS.indent(Indent + 4) << "Statements with forwarded operand trees: "
                           << NumModifiedStmts << '\n';
     OS.indent(Indent) << "}\n";
   }
ForwardingDecision forwardKnownLoad(ScopStmt *TargetStmt, Instruction *Inst,
     default:
       llvm_unreachable("Shouldn't return this");
     }
 
     IslQuotaScope QuotaScope = MaxOpGuard.enter(!DoIt);
 
     // { DomainDef[] -> ValInst[] }
     isl::map ExpectedVal = makeValInst(Inst, UseStmt, UseLoop);
+    assert(isNormalized(ExpectedVal) && "LoadInsts are always normalized");
 
     // { DomainTarget[] -> ValInst[] }
     isl::map TargetExpectedVal = ExpectedVal.apply_domain(UseToTarget);
     isl::union_map TranslatedExpectedVal =
         isl::union_map(TargetExpectedVal).apply_range(Translator);
 
     // { DomainTarget[] -> Element[] }
     isl::union_map Candidates = findSameContentElements(TranslatedExpectedVal);
ForwardingDecision reloadKnownContent(ScopStmt *TargetStmt, Instruction *Inst,
     MemoryAccess *Access = TargetStmt->lookupInputAccessOf(Inst);
     if (Access && Access->isLatestArrayKind()) {
       if (DoIt)
         return FD_DidForwardLeaf;
       return FD_CanForwardLeaf;
     }
 
     // { DomainDef[] -> ValInst[] }
-    isl::union_map ExpectedVal = makeValInst(Inst, UseStmt, UseLoop);
+    isl::union_map ExpectedVal = makeNormalizedValInst(Inst, UseStmt, UseLoop);
 
     // { DomainTarget[] -> ValInst[] }
     isl::union_map TargetExpectedVal = ExpectedVal.apply_domain(UseToTarget);
     isl::union_map TranslatedExpectedVal =
         TargetExpectedVal.apply_range(Translator);
 
     // { DomainTarget[] -> Element[] }
     isl::union_map Candidates = findSameContentElements(TranslatedExpectedVal);

lib/Transform/ZoneAlgo.cpp

 #include "polly/Support/ISLTools.h"
 #include "polly/Support/VirtualInstruction.h"
 #include "llvm/ADT/Statistic.h"
 
 #define DEBUG_TYPE "polly-zone"
 
 STATISTIC(NumIncompatibleArrays, "Number of not zone-analyzable arrays");
 STATISTIC(NumCompatibleArrays, "Number of zone-analyzable arrays");
+STATISTIC(NumRecursivePHIs, "Number of recursive PHIs");
+STATISTIC(NumNormalizablePHIs, "Number of normalizable PHIs");
+STATISTIC(NumPHINormialization, "Number of PHI executed normalizations");
 
 using namespace polly;
 using namespace llvm;
 
 static isl::union_map computeReachingDefinition(isl::union_map Schedule,
                                                 isl::union_map Writes,
                                                 bool InclDef, bool InclRedef) {
   return computeReachingWrite(Schedule, Writes, false, InclDef, InclRedef);
if (LoadInst *Load = dyn_cast_or_null<LoadInst>(MA->getAccessInstruction())) {
     isl::map EltLoadValInst =
         give(isl_map_apply_domain(LoadValInst.take(), IncludeElement.take()));
 
     AllReadValInst = give(
         isl_union_map_add_map(AllReadValInst.take(), EltLoadValInst.take()));
   }
 }
 
-isl::map ZoneAlgorithm::getWrittenValue(MemoryAccess *MA, isl::map AccRel) {
+isl::union_map ZoneAlgorithm::getWrittenValue(MemoryAccess *MA,
+                                              isl::map AccRel) {
   if (!MA->isMustWrite())
     return {};
 
   Value *AccVal = MA->getAccessValue();
   ScopStmt *Stmt = MA->getStatement();
   Instruction *AccInst = MA->getAccessInstruction();
 
   // Write a value to a single element.
   auto L = MA->isOriginalArrayKind() ? LI->getLoopFor(AccInst->getParent())
                                      : Stmt->getSurroundingLoop();
   if (AccVal &&
       AccVal->getType() == MA->getLatestScopArrayInfo()->getElementType() &&
       AccRel.is_single_valued().is_true())
-    return makeValInst(AccVal, Stmt, L);
+    return makeNormalizedValInst(AccVal, Stmt, L);
 
   // memset(_, '0', ) is equivalent to writing the null value to all touched
   // elements. isMustWrite() ensures that all of an element's bytes are
   // overwritten.
   if (auto *Memset = dyn_cast<MemSetInst>(AccInst)) {
     auto *WrittenConstant = dyn_cast<Constant>(Memset->getValue());
     Type *Ty = MA->getLatestScopArrayInfo()->getElementType();
     if (WrittenConstant && WrittenConstant->isZeroValue()) {
       Constant *Zero = Constant::getNullValue(Ty);
-      return makeValInst(Zero, Stmt, L);
+      return makeNormalizedValInst(Zero, Stmt, L);
     }
   }
 
   return {};
 }
 
 void ZoneAlgorithm::addArrayWriteAccess(MemoryAccess *MA) {
   assert(MA->isLatestArrayKind());
   assert(MA->isWrite());
   auto *Stmt = MA->getStatement();
 
   // { Domain[] -> Element[] }
   isl::map AccRel = intersectRange(getAccessRelationFor(MA), CompatibleElts);
 
   if (MA->isMustWrite())
     AllMustWrites = AllMustWrites.add_map(AccRel);
 
   if (MA->isMayWrite())
     AllMayWrites = AllMayWrites.add_map(AccRel);
 
   // { Domain[] -> ValInst[] }
-  isl::map WriteValInstance = getWrittenValue(MA, AccRel);
+  isl::union_map WriteValInstance = getWrittenValue(MA, AccRel);
   if (!WriteValInstance)
     WriteValInstance = makeUnknownForDomain(Stmt);
 
   // { Domain[] -> [Element[] -> Domain[]] }
   isl::map IncludeElement = AccRel.domain_map().curry();
 
   // { [Element[] -> DomainWrite[]] -> ValInst[] }
-  isl::map EltWriteValInst = WriteValInstance.apply_domain(IncludeElement);
+  isl::union_map EltWriteValInst =
+      WriteValInstance.apply_domain(IncludeElement);
 
-  AllWriteValInst = AllWriteValInst.add_map(EltWriteValInst);
+  AllWriteValInst = AllWriteValInst.unite(EltWriteValInst);
+}
+
+/// Return whether @p PHI refers (also transitively through other PHIs) to
+/// itself.
+///
+/// loop:
+///   %phi1 = phi [0, %preheader], [%phi1, %loop]
+///   br i1 %c, label %loop, label %exit
+///
+/// exit:
+///   %phi2 = phi [%phi1, %bb]
+///
+/// In this example, %phi1 is recursive, but %phi2 is not.
+static bool isRecursivePHI(PHINode *PHI) {
+  SmallVector<PHINode *, 8> Worklist;
+  SmallPtrSet<PHINode *, 8> Visited;
+  Worklist.push_back(PHI);
+
+  while (!Worklist.empty()) {
+    PHINode *Cur = Worklist.pop_back_val();
+
+    if (Visited.count(Cur))
+      continue;
+    Visited.insert(Cur);
+
+    for (Use &Incoming : Cur->incoming_values()) {
+      Value *IncomingVal = Incoming.get();
+      auto *IncomingPHI = dyn_cast<PHINode>(IncomingVal);
+      if (!IncomingPHI)
+        continue;
+
+      if (IncomingPHI == PHI)
+        return true;
+      Worklist.push_back(IncomingPHI);
+    }
+  }
+  return false;
+}
+
+isl::union_map ZoneAlgorithm::computePerPHI(const ScopArrayInfo *SAI) {
+  // TODO: If the PHI has an incoming block from before the SCoP, it is not
+  // represented in any ScopStmt.
+
+  auto *PHI = cast<PHINode>(SAI->getBasePtr());
+  auto It = PerPHIMaps.find(PHI);
+  if (It != PerPHIMaps.end())
+    return It->second;
+
+  assert(SAI->isPHIKind());
+
+  // { DomainPHIWrite[] -> Scatter[] }
+  isl::union_map PHIWriteScatter = makeEmptyUnionMap();
+
+  // Collect all incoming block timepoints.
+  for (MemoryAccess *MA : S->getPHIIncomings(SAI)) {
+    isl::map Scatter = getScatterFor(MA);
+    PHIWriteScatter = PHIWriteScatter.add_map(Scatter);
+  }
+
+  // { DomainPHIRead[] -> Scatter[] }
+  isl::map PHIReadScatter = getScatterFor(S->getPHIRead(SAI));
+
+  // { DomainPHIRead[] -> Scatter[] }
+  isl::map BeforeRead = beforeScatter(PHIReadScatter, true);
+
+  // { Scatter[] }
+  isl::set WriteTimes = singleton(PHIWriteScatter.range(), ScatterSpace);
+
+  // { DomainPHIRead[] -> Scatter[] }
+  isl::map PHIWriteTimes = BeforeRead.intersect_range(WriteTimes);
+  isl::map LastPerPHIWrites = PHIWriteTimes.lexmax();
+
+  // { DomainPHIRead[] -> DomainPHIWrite[] }
+  isl::union_map Result =
+      isl::union_map(LastPerPHIWrites).apply_range(PHIWriteScatter.reverse());
+  assert(!Result.is_single_valued().is_false());
+  assert(!Result.is_injective().is_false());
+
+  PerPHIMaps.insert({PHI, Result});
+  return Result;
 }
 
 isl::union_set ZoneAlgorithm::makeEmptyUnionSet() const {
   return give(isl_union_set_empty(ParamSpace.copy()));
 }
 
 isl::union_map ZoneAlgorithm::makeEmptyUnionMap() const {
   return give(isl_union_map_empty(ParamSpace.copy()));
case VirtualUse::Inter: {
 
     simplify(Result);
     return Result;
   }
   }
   llvm_unreachable("Unhandled use type");
 }
 
+/// Remove all computed PHIs out of @p Input and replace by their incoming
+/// value.
+static isl::union_map normalizeValInst(isl::union_map Input,
+                                       isl::union_map NormalizedPHIs,
+                                       DenseSet<PHINode *> &TranslatedPHIs) {
+  isl::union_map Result = isl::union_map::empty(Input.get_space());
+  Input.foreach_map(
+      [&Result, &NormalizedPHIs, &TranslatedPHIs](isl::map Map) -> isl::stat {
+        isl::space Space = Map.get_space();
+        isl::space RangeSpace = Space.range();
+
+        // Instructions within the SCoP are always wrapped. Non-wrapped tuples
+        // are therefore invariant in the SCoP and don't need normalization.
+        if (!RangeSpace.is_wrapping()) {
+          Result = Result.add_map(Map);
+          return isl::stat::ok;
+        }
+
+        auto *PHI = dyn_cast<PHINode>(static_cast<Value *>(
+            RangeSpace.unwrap().get_tuple_id(isl::dim::out).get_user()));
+
+        // If no normalization is necessary, then the ValInst stands for itself.
+        if (!TranslatedPHIs.count(PHI)) {
+          Result = Result.add_map(Map);
+          return isl::stat::ok;
+        }
+
+        // Otherwise, apply the normalization.
+        isl::union_map Mapped = isl::union_map(Map).apply_range(NormalizedPHIs);
+        Result = Result.unite(Mapped);
+        NumPHINormialization++;
+        return isl::stat::ok;
+      });
+  return Result;
+}
+
+isl::union_map ZoneAlgorithm::makeNormalizedValInst(llvm::Value *Val,
+                                                    ScopStmt *UserStmt,
+                                                    llvm::Loop *Scope,
+                                                    bool IsCertain) {
+  isl::map ValInst = makeValInst(Val, UserStmt, Scope, IsCertain);
+  isl::union_map Normalized =
+      normalizeValInst(ValInst, NormalizedPHI, this->ComputedPHIs);
+  return Normalized;
+}
+
 bool ZoneAlgorithm::isCompatibleAccess(MemoryAccess *MA) {
   if (!MA)
     return false;
   if (!MA->isLatestArrayKind())
     return false;
   Instruction *AccInst = MA->getAccessInstruction();
   return isa<StoreInst>(AccInst) || isa<LoadInst>(AccInst);
 }
 
+bool ZoneAlgorithm::isNormalized(isl::map Map) {
+  auto Space = Map.get_space();
+  auto RangeSpace = Space.range();
+
+  if (!RangeSpace.is_wrapping())
+    return true;
+
+  auto *PHI = dyn_cast<PHINode>(static_cast<Value *>(
+      RangeSpace.unwrap().get_tuple_id(isl::dim::out).get_user()));
+  if (!PHI)
+    return true;
+
+  // TODO: Check whether we really use the Incoming RegionStmt to identify the
+  // normalized value.
+  auto IncomingStmt = static_cast<ScopStmt *>(
+      RangeSpace.unwrap().get_tuple_id(isl::dim::in).get_user());
+  if (IncomingStmt->isRegionStmt())
+    return true;
+
+  if (RecursivePHIs.count(PHI))
+    return true;
+
+  return false;
+}
+
+bool ZoneAlgorithm::isNormalized(isl::union_map UMap) {
+  auto Result = UMap.foreach_map([this](isl::map Map) -> isl::stat {
+    if (isNormalized(Map))
+      return isl::stat::ok;
+    return isl::stat::error;
+  });
+  return Result == isl::stat::ok;
+}
+
 void ZoneAlgorithm::computeCommon() {
   AllReads = makeEmptyUnionMap();
   AllMayWrites = makeEmptyUnionMap();
   AllMustWrites = makeEmptyUnionMap();
   AllWriteValInst = makeEmptyUnionMap();
   AllReadValInst = makeEmptyUnionMap();
 
-  for (auto &Stmt : *S) {
-    for (auto *MA : Stmt) {
+  // Default to empty, i.e. no normalization/replacement is taking place. Call
+  // computeNormalizedPHIs() to initialize.
+  NormalizedPHI = makeEmptyUnionMap();
+  ComputedPHIs.clear();
+
+  for (ScopStmt &Stmt : *S) {
+    for (MemoryAccess *MA : Stmt) {
       if (!MA->isLatestArrayKind())
         continue;
 
       if (MA->isRead())
         addArrayReadAccess(MA);
 
       if (MA->isWrite())
         addArrayWriteAccess(MA);
     }
   }
 
   // { DomainWrite[] -> Element[] }
   AllWrites =
       give(isl_union_map_union(AllMustWrites.copy(), AllMayWrites.copy()));
 
   // { [Element[] -> Zone[]] -> DomainWrite[] }
   WriteReachDefZone =
       computeReachingDefinition(Schedule, AllWrites, false, true);
   simplify(WriteReachDefZone);
 }
 
+void ZoneAlgorithm::computeNormalizedPHIs() {
+  // Determine which PHIs can reference themselves. They are excluded from
+  // normalization to avoid problems with transitive closures.
+  for (ScopStmt &Stmt : *S) {
+    for (MemoryAccess *MA : Stmt) {
+      if (!MA->isPHIKind())
+        continue;
+      if (!MA->isRead())
+        continue;
+
+      // TODO: Can be more efficient since isRecursivePHI can theoretically
+      // determine recursiveness for multiple values and/or cache results.
+      auto *PHI = cast<PHINode>(MA->getAccessInstruction());
+      if (isRecursivePHI(PHI)) {
+        NumRecursivePHIs++;
+        RecursivePHIs.insert(PHI);
+      }
+    }
+  }
+
+  // { PHIValInst[] -> IncomingValInst[] }
+  isl::union_map AllPHIMaps = makeEmptyUnionMap();
+
+  // Discover new PHIs and try to normalize them.
+  DenseSet<PHINode *> AllPHIs;
+  for (ScopStmt &Stmt : *S) {
+    for (MemoryAccess *MA : Stmt) {
+      if (!MA->isOriginalPHIKind())
+        continue;
+      if (!MA->isRead())
+        continue;
+
+      auto *PHI = cast<PHINode>(MA->getAccessInstruction());
+      if (RecursivePHIs.count(PHI))
+        continue;
+
+      const ScopArrayInfo *SAI = MA->getOriginalScopArrayInfo();
+
+      // { PHIDomain[] -> PHIValInst[] }
+      isl::map PHIValInst = makeValInst(PHI, &Stmt, Stmt.getSurroundingLoop());
+
+      // { IncomingDomain[] -> IncomingValInst[] }
+      isl::union_map IncomingValInsts = makeEmptyUnionMap();
+
+      // Get all incoming values.
+      for (MemoryAccess *MA : S->getPHIIncomings(SAI)) {
+        ScopStmt *IncomingStmt = MA->getStatement();
+        auto Incoming = MA->getIncoming();
+        Value *IncomingVal = PHI;
+        if (Incoming.size() == 1)
+          IncomingVal = Incoming[0].second;
+
+        // TODO: For Incoming.size() > 1, ensure that
+        // [RegionStmtDomain[] -> Val_PHI[]]
+        // is the ValInst.
+
+        // { IncomingDomain[] -> IncomingValInst[] }
+        isl::map IncomingValInst = makeValInst(
+            IncomingVal, IncomingStmt, IncomingStmt->getSurroundingLoop());
+
+        IncomingValInsts = IncomingValInsts.add_map(IncomingValInst);
+      }
+
+      // Determine which instance of the PHI statement corresponds to which
+      // incoming value.
+      // { PHIDomain[] -> IncomingDomain[] }
+      isl::union_map PerPHI = computePerPHI(SAI);
+
+      // { PHIValInst[] -> IncomingValInst[] }
+      isl::union_map PHIMap =
+          PerPHI.apply_domain(PHIValInst).apply_range(IncomingValInsts);
+      assert(!PHIMap.is_single_valued().is_false());
+
+      // Resolve transitiveness: The incoming value of the newly discovered PHI
+      // may reference a previously normalized PHI. At the same time, already
+      // normalized PHIs might be normalized to the new PHI. At the end, none of
+      // the PHIs may appear on the right-hand-side of the normalization map.
+      PHIMap = normalizeValInst(PHIMap, AllPHIMaps, AllPHIs);
+      AllPHIs.insert(PHI);
+      AllPHIMaps = normalizeValInst(AllPHIMaps, PHIMap, AllPHIs);
+
+      AllPHIMaps = AllPHIMaps.unite(PHIMap);
+      NumNormalizablePHIs++;
+    }
+  }
+  simplify(AllPHIMaps);
+
+  // Apply the normalization.
+  ComputedPHIs = AllPHIs;
+  NormalizedPHI = AllPHIMaps;
+
+  assert(!NormalizedPHI || isNormalized(NormalizedPHI));
+}
+
 void ZoneAlgorithm::printAccesses(llvm::raw_ostream &OS, int Indent) const {
   OS.indent(Indent) << "After accesses {\n";
   for (auto &Stmt : *S) {
     OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";
     for (auto *MA : Stmt)
       MA->print(OS);
   }
   OS.indent(Indent) << "}\n";
 }
 
 isl::union_map ZoneAlgorithm::computeKnownFromMustWrites() const {
   // { [Element[] -> Zone[]] -> [Element[] -> DomainWrite[]] }
   isl::union_map EltReachdDef = distributeDomain(WriteReachDefZone.curry());
 
   // { [Element[] -> DomainWrite[]] -> ValInst[] }
   isl::union_map AllKnownWriteValInst = filterKnownValInst(AllWriteValInst);
 
   // { [Element[] -> Zone[]] -> ValInst[] }
   return EltReachdDef.apply_range(AllKnownWriteValInst);
 }
 
 isl::union_map ZoneAlgorithm::computeKnownFromLoad() const {
+
   // { Element[] }
   isl::union_set AllAccessedElts = AllReads.range().unite(AllWrites.range());
 
   // { Element[] -> Scatter[] }
   isl::union_map EltZoneUniverse = isl::union_map::from_domain_and_range(
       AllAccessedElts, isl::set::universe(ScatterSpace));
 
   // This assumes there are no "holes" in
   // isl_union_map_domain(WriteReachDefZone); alternatively, compute the zone
   // before the first write or that are not written at all.
   // { Element[] -> Scatter[] }
   isl::union_set NonReachDef =
       EltZoneUniverse.wrap().subtract(WriteReachDefZone.domain());
+  simplify(NonReachDef);
 
   // { [Element[] -> Zone[]] -> ReachDefId[] }
   isl::union_map DefZone =
       WriteReachDefZone.unite(isl::union_map::from_domain(NonReachDef));
 
   // { [Element[] -> Scatter[]] -> Element[] }
   isl::union_map EltZoneElt = EltZoneUniverse.domain_map();
 
isl::union_map ZoneAlgorithm::computeKnownFromLoad() const {
   // { [Element[] -> Scatter[]] -> ValInst[] }
   isl::union_map ScatterKnown = ReadsElt.apply_range(AllReadValInst);
 
   // { [Element[] -> ReachDefId[]] -> ValInst[] }
   isl::union_map DefidKnown =
       DefZoneEltDefId.apply_domain(ScatterKnown).reverse();
 
   // { [Element[] -> Zone[]] -> ValInst[] }
-  return DefZoneEltDefId.apply_range(DefidKnown);
+  auto Result = DefZoneEltDefId.apply_range(DefidKnown);
+
+  // TODO: Loads can be normalized to other ValInsts.
+
+  return Result;
 }
 
+// { [Element[] -> Zone[]] -> ValInst[] }
 isl::union_map ZoneAlgorithm::computeKnown(bool FromWrite,
                                            bool FromRead) const {
   isl::union_map Result = makeEmptyUnionMap();
 
   if (FromWrite)
     Result = Result.unite(computeKnownFromMustWrites());
 
   if (FromRead)
     Result = Result.unite(computeKnownFromLoad());
 
-  simplify(Result);
+  //  simplify(Result);
   return Result;
 }

test/ForwardOpTree/atax.ll

+; RUN: opt %loadPolly -polly-optree-normalize-phi=true -polly-optree -analyze < %s | FileCheck %s -match-full-lines
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+%struct._IO_FILE = type { i32, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, %struct._IO_marker*, %struct._IO_FILE*, i32, i32, i64, i16, i8, [1 x i8], i8*, i64, i8*, i8*, i8*, i8*, i64, i32, [20 x i8] }
+%struct._IO_marker = type { %struct._IO_marker*, %struct._IO_FILE*, i32 }
+
+@.str = private unnamed_addr constant [1 x i8] zeroinitializer, align 1
+@stderr = external local_unnamed_addr global %struct._IO_FILE*, align 8
+@.str.1 = private unnamed_addr constant [23 x i8] c"==BEGIN DUMP_ARRAYS==\0A\00", align 1
+@.str.2 = private unnamed_addr constant [15 x i8] c"begin dump: %s\00", align 1
+@.str.3 = private unnamed_addr constant [2 x i8] c"y\00", align 1
+@.str.4 = private unnamed_addr constant [2 x i8] c"\0A\00", align 1
+@.str.5 = private unnamed_addr constant [8 x i8] c"%0.2lf \00", align 1
+@.str.6 = private unnamed_addr constant [17 x i8] c"\0Aend   dump: %s\0A\00", align 1
+@.str.7 = private unnamed_addr constant [23 x i8] c"==END   DUMP_ARRAYS==\0A\00", align 1
+
+define internal fastcc void @kernel_atax([2100 x double]* nocapture readonly %A, double* nocapture readonly %x, double* nocapture %y, double* nocapture %tmp) unnamed_addr #2 {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  %y15 = bitcast double* %y to i8*
+  call void @llvm.memset.p0i8.i64(i8* %y15, i8 0, i64 16800, i32 8, i1 false)
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.inc40, %entry.split
+  %indvars.iv8 = phi i64 [ 0, %entry.split ], [ %indvars.iv.next9, %for.inc40 ]
+  %arrayidx5 = getelementptr inbounds double, double* %tmp, i64 %indvars.iv8
+  store double 0.000000e+00, double* %arrayidx5, align 8, !tbaa !6
+  br label %for.body8
+
+for.body8:                                        ; preds = %for.body8, %for.body3
+  %0 = phi double [ 0.000000e+00, %for.body3 ], [ %add, %for.body8 ]
+  %indvars.iv = phi i64 [ 0, %for.body3 ], [ %indvars.iv.next, %for.body8 ]
+  %arrayidx14 = getelementptr inbounds [2100 x double], [2100 x double]* %A, i64 %indvars.iv8, i64 %indvars.iv
+  %1 = load double, double* %arrayidx14, align 8, !tbaa !6
+  %arrayidx16 = getelementptr inbounds double, double* %x, i64 %indvars.iv
+  %2 = load double, double* %arrayidx16, align 8, !tbaa !6
+  %mul = fmul double %1, %2
+  %add = fadd double %0, %mul
+  store double %add, double* %arrayidx5, align 8, !tbaa !6
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 2
+  br i1 %exitcond, label %for.end21, label %for.body8
+
+for.end21:                                        ; preds = %for.body8
+  br label %for.body24
+
+for.body24:                                       ; preds = %for.body24.for.body24_crit_edge, %for.end21
+  %3 = phi double [ %add, %for.end21 ], [ %.pre, %for.body24.for.body24_crit_edge ]
+  %indvars.iv5 = phi i64 [ 0, %for.end21 ], [ %indvars.iv.next6, %for.body24.for.body24_crit_edge ]
+  %arrayidx26 = getelementptr inbounds double, double* %y, i64 %indvars.iv5
+  %4 = load double, double* %arrayidx26, align 8, !tbaa !6
+  %arrayidx30 = getelementptr inbounds [2100 x double], [2100 x double]* %A, i64 %indvars.iv8, i64 %indvars.iv5
+  %5 = load double, double* %arrayidx30, align 8, !tbaa !6
+  %mul33 = fmul double %5, %3
+  %add34 = fadd double %4, %mul33
+  store double %add34, double* %arrayidx26, align 8, !tbaa !6
+  %indvars.iv.next6 = add nuw nsw i64 %indvars.iv5, 1
+  %exitcond7 = icmp eq i64 %indvars.iv.next6, 2
+  br i1 %exitcond7, label %for.inc40, label %for.body24.for.body24_crit_edge
+
+for.body24.for.body24_crit_edge:                  ; preds = %for.body24
+  %.pre = load double, double* %arrayidx5, align 8, !tbaa !6
+  br label %for.body24
+
+for.inc40:                                        ; preds = %for.body24
+  %indvars.iv.next9 = add nuw nsw i64 %indvars.iv8, 1
+  %exitcond10 = icmp eq i64 %indvars.iv.next9, 2
+  br i1 %exitcond10, label %for.end42, label %for.body3
+
+for.end42:                                        ; preds = %for.inc40
+  ret void
+}
+
+; Function Attrs: nounwind readonly
+declare i32 @strcmp(i8* nocapture, i8* nocapture) local_unnamed_addr #3
+
+
+; Function Attrs: nounwind
+declare void @free(i8* nocapture) local_unnamed_addr #4
+
+; Function Attrs: nounwind
+declare i32 @fprintf(%struct._IO_FILE* nocapture, i8* nocapture readonly, ...) local_unnamed_addr #4
+
+; Function Attrs: nounwind
+declare i64 @fwrite(i8* nocapture, i64, i64, %struct._IO_FILE* nocapture) #5
+
+; Function Attrs: nounwind
+declare i32 @fputc(i32, %struct._IO_FILE* nocapture) #5
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.memset.p0i8.i64(i8* nocapture writeonly, i8, i64, i32, i1) #6
+
+attributes #0 = { noinline nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #2 = { noinline norecurse nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #3 = { nounwind readonly "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #4 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #5 = { nounwind }
+attributes #6 = { argmemonly nounwind }
+attributes #7 = { cold }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 6.0.0 (trunk 312565) (llvm/trunk 312564)"}
+!2 = !{!3, !3, i64 0}
+!3 = !{!"any pointer", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C/C++ TBAA"}
+!6 = !{!7, !7, i64 0}
+!7 = !{!"double", !4, i64 0}
+
+
+; CHECK: Statistics {
+; CHECK:     Operand trees forwarded: 2
+; CHECK:     Statements with forwarded operand trees: 2
+; CHECK: }
+
+; CHECK-NEXT: After statements {
+; CHECK-NEXT:     Stmt_for_body3
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_for_body3[i0] -> MemRef_tmp[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_for_body3[i0] -> MemRef1__phi[] };
+; CHECK-NEXT:             Instructions {
+; CHECK-NEXT:                   store double 0.000000e+00, double* %arrayidx5, align 8, !tbaa !2
+; CHECK-NEXT:             }
+; CHECK-NEXT:     Stmt_for_body8
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_for_body8[i0, i1] -> MemRef1__phi[] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_for_body8[i0, i1] -> MemRef1__phi[] };
+; CHECK-NEXT:            new: { Stmt_for_body8[i0, i1] -> MemRef_tmp[i0] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_for_body8[i0, i1] -> MemRef_A[i0, i1] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_for_body8[i0, i1] -> MemRef_x[i1] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_for_body8[i0, i1] -> MemRef_tmp[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_for_body8[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:             Instructions {
+; CHECK-NEXT:                   %0 = phi double [ 0.000000e+00, %for.body3 ], [ %add, %for.body8 ]
+; CHECK-NEXT:                   %1 = load double, double* %arrayidx14, align 8, !tbaa !2
+; CHECK-NEXT:                   %2 = load double, double* %arrayidx16, align 8, !tbaa !2
+; CHECK-NEXT:                   %mul = fmul double %1, %2
+; CHECK-NEXT:                   %add = fadd double %0, %mul
+; CHECK-NEXT:                   store double %add, double* %arrayidx5, align 8, !tbaa !2
+; CHECK-NEXT:                   %exitcond = icmp eq i64 %indvars.iv.next, 2
+; CHECK-NEXT:             }
+; CHECK-NEXT:     Stmt_for_end21
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_for_end21[i0] -> MemRef_add[] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_for_end21[i0] -> MemRef5__phi[] };
+; CHECK-NEXT:             Instructions {
+; CHECK-NEXT:             }
+; CHECK-NEXT:     Stmt_for_body24
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_for_body24[i0, i1] -> MemRef5__phi[] };
+; CHECK-NEXT:            new: { Stmt_for_body24[i0, i1] -> MemRef_tmp[i0] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_for_body24[i0, i1] -> MemRef_y[i1] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_for_body24[i0, i1] -> MemRef_A[i0, i1] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_for_body24[i0, i1] -> MemRef_y[i1] };
+; CHECK-NEXT:             Instructions {
+; CHECK-NEXT:                   %3 = phi double [ %add, %for.end21 ], [ %.pre, %for.body24.for.body24_crit_edge ]
+; CHECK-NEXT:                   %4 = load double, double* %arrayidx26, align 8, !tbaa !2
+; CHECK-NEXT:                   %5 = load double, double* %arrayidx30, align 8, !tbaa !2
+; CHECK-NEXT:                   %mul33 = fmul double %5, %3
+; CHECK-NEXT:                   %add34 = fadd double %4, %mul33
+; CHECK-NEXT:                   store double %add34, double* %arrayidx26, align 8, !tbaa !2
+; CHECK-NEXT:                   %exitcond7 = icmp eq i64 %indvars.iv.next6, 2
+; CHECK-NEXT:             }
+; CHECK-NEXT:     Stmt_for_body24_for_body24_crit_edge
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_for_body24_for_body24_crit_edge[i0, i1] -> MemRef5__phi[] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_for_body24_for_body24_crit_edge[i0, i1] -> MemRef_tmp[i0] };
+; CHECK-NEXT:             Instructions {
+; CHECK-NEXT:                   %.pre = load double, double* %arrayidx5, align 8, !tbaa !2
+; CHECK-NEXT:             }
+; CHECK-NEXT: }
+
+
+;                                                 tmp[0]
+; [ 0] Stmt_for_body3[0]
+;                                                 Val_1 (0.0)
+; [ 1] Stmt_for_body8[0]
+;
+; [ 2] Stmt_for_body8[1]
+;
+; [ 3] Stmt_for_end21[0]
+;                                                 Val__add
+; [ 4] Stmt_for_body24[0,0]
+;
+; [ 5] Stmt_for_body24_for_body24_crit_edge[0,0]
+;
+; [ 6] Stmt_for_body24[0,1]
+;
+; [ 7] Stmt_for_body3[1]
+;
+; [ 8] Stmt_for_body8[1,0]
+;
+; [ 9] Stmt_for_body8[1,0]
+;
+; [10] Stmt_for_end21[1]
+;
+; [11] Stmt_for_body24[1,0]
+;
+; [12] Stmt_for_body24_for_body24_crit_edge[1,0]
+;
+; [13] Stmt_for_body24[1,1]

test/ForwardOpTree/forward_phi_load.ll

+; RUN: opt %loadPolly -polly-optree-normalize-phi=true -polly-optree -analyze < %s | FileCheck %s -match-full-lines
+;
+; Rematerialize a load.
+;
+; for (int j = 0; j < n; j += 1) {
+; bodyA:
+;   double val = B[j];
+;
+; bodyB:
+;   double phi = val;
+;
+; bodyC:
+;   A[j] = phi;
+; }
+;
+define void @func(i32 %n, double* noalias nonnull %A, double* noalias nonnull %B) {
+entry:
+  br label %for
+
+for:
+  %j = phi i32 [0, %entry], [%j.inc, %inc]
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %bodyA, label %exit
+
+    bodyA:
+      %B_idx = getelementptr inbounds double, double* %B, i32 %j
+      %val = load double, double* %B_idx
+      br label %bodyB
+
+    bodyB:
+      %phi = phi double [%val, %bodyA]
+      br label %bodyC
+      
+    bodyC:
+      %A_idx = getelementptr inbounds double, double* %A, i32 %j
+      store double %phi, double* %A_idx
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK: Statistics {
+; CHECK:     Reloads: 2
+; CHECK: }
+
+; CHECK-NEXT: After statements {
+; CHECK-NEXT:     Stmt_bodyA
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n] -> { Stmt_bodyA[i0] -> MemRef_B[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n] -> { Stmt_bodyA[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:             Instructions {
+; CHECK-NEXT:                   %val = load double, double* %B_idx
+; CHECK-NEXT:             }
+; CHECK-NEXT:     Stmt_bodyB
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n] -> { Stmt_bodyB[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: [n] -> { Stmt_bodyB[i0] -> MemRef_B[i0] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n] -> { Stmt_bodyB[i0] -> MemRef_phi[] };
+; CHECK-NEXT:             Instructions {
+; CHECK-NEXT:                   %phi = phi double [ %val, %bodyA ]
+; CHECK-NEXT:             }
+; CHECK-NEXT:     Stmt_bodyC
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n] -> { Stmt_bodyC[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [n] -> { Stmt_bodyC[i0] -> MemRef_phi[] };
+; CHECK-NEXT:            new: [n] -> { Stmt_bodyC[i0] -> MemRef_B[i0] };
+; CHECK-NEXT:             Instructions {
+; CHECK-NEXT:                   store double %phi, double* %A_idx
+; CHECK-NEXT:             }
+; CHECK-NEXT: }

test/ForwardOpTree/jacobi-1d.ll

+; RUN: opt %loadPolly -polly-optree-normalize-phi=true -polly-optree -analyze < %s | FileCheck %s -match-full-lines
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+%struct._IO_FILE = type { i32, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, %struct._IO_marker*, %struct._IO_FILE*, i32, i32, i64, i16, i8, [1 x i8], i8*, i64, i8*, i8*, i8*, i8*, i64, i32, [20 x i8] }
+%struct._IO_marker = type { %struct._IO_marker*, %struct._IO_FILE*, i32 }
+
+@.str = private unnamed_addr constant [1 x i8] zeroinitializer, align 1
+@stderr = external local_unnamed_addr global %struct._IO_FILE*, align 8
+@.str.1 = private unnamed_addr constant [23 x i8] c"==BEGIN DUMP_ARRAYS==\0A\00", align 1
+@.str.2 = private unnamed_addr constant [15 x i8] c"begin dump: %s\00", align 1
+@.str.3 = private unnamed_addr constant [2 x i8] c"A\00", align 1
+@.str.4 = private unnamed_addr constant [2 x i8] c"\0A\00", align 1
+@.str.5 = private unnamed_addr constant [8 x i8] c"%0.2lf \00", align 1
+@.str.6 = private unnamed_addr constant [17 x i8] c"\0Aend   dump: %s\0A\00", align 1
+@.str.7 = private unnamed_addr constant [23 x i8] c"==END   DUMP_ARRAYS==\0A\00", align 1
+
+; Function Attrs: noinline norecurse nounwind uwtable
+define internal fastcc void @kernel_jacobi_1d(double* noalias nocapture %A, double* noalias nocapture %B) unnamed_addr #2 {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  %arrayidx6.phi.trans.insert = getelementptr inbounds double, double* %A, i64 1
+  %arrayidx21.phi.trans.insert = getelementptr inbounds double, double* %B, i64 1
+  br label %for.body
+
+for.body:                                         ; preds = %for.inc33, %entry.split
+  %t.03 = phi i32 [ 0, %entry.split ], [ %inc34, %for.inc33 ]
+  %.pre = load double, double* %A, align 8, !tbaa !6
+  %.pre10 = load double, double* %arrayidx6.phi.trans.insert, align 8, !tbaa !6
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.body3, %for.body
+  %0 = phi double [ %.pre10, %for.body ], [ %2, %for.body3 ]
+  %1 = phi double [ %.pre, %for.body ], [ %0, %for.body3 ]
+  %indvars.iv = phi i64 [ 1, %for.body ], [ %indvars.iv.next, %for.body3 ]
+  %add = fadd double %1, %0
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %arrayidx9 = getelementptr inbounds double, double* %A, i64 %indvars.iv.next
+  %2 = load double, double* %arrayidx9, align 8, !tbaa !6
+  %add10 = fadd double %add, %2
+  %mul = fmul double %add10, 3.333300e-01
+  %arrayidx12 = getelementptr inbounds double, double* %B, i64 %indvars.iv
+  store double %mul, double* %arrayidx12, align 8, !tbaa !6
+  %exitcond = icmp eq i64 %indvars.iv.next, 3
+  br i1 %exitcond, label %for.end, label %for.body3
+
+for.end:                                          ; preds = %for.body3
+  %.pre11 = load double, double* %B, align 8, !tbaa !6
+  %.pre12 = load double, double* %arrayidx21.phi.trans.insert, align 8, !tbaa !6
+  br label %for.inc33
+
+for.inc33:                                        ; preds = %for.body16
+  %inc34 = add nuw nsw i32 %t.03, 1
+  %exitcond9 = icmp eq i32 %inc34, 2
+  br i1 %exitcond9, label %for.end35, label %for.body
+
+for.end35:                                        ; preds = %for.inc33
+  ret void
+}
+
+
+; Function Attrs: nounwind
+declare void @free(i8* nocapture) local_unnamed_addr #4
+
+; Function Attrs: nounwind
+declare i32 @fprintf(%struct._IO_FILE* nocapture, i8* nocapture readonly, ...) local_unnamed_addr #4
+
+; Function Attrs: nounwind
+declare i64 @fwrite(i8* nocapture, i64, i64, %struct._IO_FILE* nocapture) #5
+
+; Function Attrs: nounwind
+declare i32 @fputc(i32, %struct._IO_FILE* nocapture) #5
+
+attributes #0 = { noinline nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #2 = { noinline norecurse nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #3 = { nounwind readonly "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #4 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #5 = { nounwind }
+attributes #6 = { cold }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 6.0.0  (llvm/trunk 312874)"}
+!2 = !{!3, !3, i64 0}
+!3 = !{!"any pointer", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C/C++ TBAA"}
+!6 = !{!7, !7, i64 0}
+!7 = !{!"double", !4, i64 0}
+
+
+; CHECK: Statistics {
+; CHECK:     Operand trees forwarded: 2
+; CHECK:     Statements with forwarded operand trees: 1
+; CHECK: }
+
+; CHECK-NEXT: After statements {
+; CHECK-NEXT:     Stmt_for_body
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_for_body[i0] -> MemRef_A[0] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_for_body[i0] -> MemRef_A[1] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_for_body[i0] -> MemRef1__phi[] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_for_body[i0] -> MemRef2__phi[] };
+; CHECK-NEXT:             Instructions {
+; CHECK-NEXT:                   %.pre = load double, double* %A, align 8, !tbaa !2
+; CHECK-NEXT:                   %.pre10 = load double, double* %arrayidx6.phi.trans.insert, align 8, !tbaa !2
+; CHECK-NEXT:             }
+; CHECK-NEXT:     Stmt_for_body3
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_for_body3[i0, i1] -> MemRef1__phi[] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_for_body3[i0, i1] -> MemRef1__phi[] };
+; CHECK-NEXT:            new: { Stmt_for_body3[i0, i1] -> MemRef_A[1 + i1] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_for_body3[i0, i1] -> MemRef2__phi[] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_for_body3[i0, i1] -> MemRef2__phi[] };
+; CHECK-NEXT:            new: { Stmt_for_body3[i0, i1] -> MemRef_A[i1] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_for_body3[i0, i1] -> MemRef_A[2 + i1] };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_for_body3[i0, i1] -> MemRef_B[1 + i1] };
+; CHECK-NEXT:             Instructions {
+; CHECK-NEXT:                   %0 = phi double [ %.pre10, %for.body ], [ %2, %for.body3 ]
+; CHECK-NEXT:                   %1 = phi double [ %.pre, %for.body ], [ %0, %for.body3 ]
+; CHECK-NEXT:                   %add = fadd double %1, %0
+; CHECK-NEXT:                   %2 = load double, double* %arrayidx9, align 8, !tbaa !2
+; CHECK-NEXT:                   %add10 = fadd double %add, %2
+; CHECK-NEXT:                   %mul = fmul double %add10, 3.333300e-01
+; CHECK-NEXT:                   store double %mul, double* %arrayidx12, align 8, !tbaa !2
+; CHECK-NEXT:                   %exitcond = icmp eq i64 %indvars.iv.next, 3
+; CHECK-NEXT:             }
+; CHECK-NEXT: }