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

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, so it is
not included here.

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.

Differential Revision: https://reviews.llvm.org/D39333

llvm-svn: 317008

3 files changed, 307 insertions, 54 deletions

diff --git a/polly/lib/Transform/DeLICM.cpp b/polly/lib/Transform/DeLICM.cpp
index 83a6bf99b3d..9709f426eae 100644
--- a/polly/lib/Transform/DeLICM.cpp
+++ b/polly/lib/Transform/DeLICM.cpp
@@ -660,52 +660,6 @@ private:
     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.
diff --git a/polly/lib/Transform/ForwardOpTree.cpp b/polly/lib/Transform/ForwardOpTree.cpp
index 1a745b5d4e4..65655d5e755 100644
--- a/polly/lib/Transform/ForwardOpTree.cpp
+++ b/polly/lib/Transform/ForwardOpTree.cpp
@@ -51,6 +51,11 @@ static cl::opt<bool>
                  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 "
@@ -280,16 +285,19 @@ public:
       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 || !NormalizeMap) {
       assert(isl_ctx_last_error(IslCtx.get()) == isl_error_quota);
       Known = nullptr;
       Translator = nullptr;
+      NormalizeMap = nullptr;
       DEBUG(dbgs() << "Known analysis exceeded max_operations\n");
       return false;
     }
@@ -462,6 +470,7 @@ public:
 
     // { 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);
@@ -578,7 +587,7 @@ public:
     }
 
     // { 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);
diff --git a/polly/lib/Transform/ZoneAlgo.cpp b/polly/lib/Transform/ZoneAlgo.cpp
index caa53a99d88..96bfac4263d 100644
--- a/polly/lib/Transform/ZoneAlgo.cpp
+++ b/polly/lib/Transform/ZoneAlgo.cpp
@@ -160,6 +160,9 @@
 
 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;
@@ -409,7 +412,8 @@ void ZoneAlgorithm::addArrayReadAccess(MemoryAccess *MA) {
   }
 }
 
-isl::map ZoneAlgorithm::getWrittenValue(MemoryAccess *MA, isl::map AccRel) {
+isl::union_map ZoneAlgorithm::getWrittenValue(MemoryAccess *MA,
+                                              isl::map AccRel) {
   if (!MA->isMustWrite())
     return {};
 
@@ -423,7 +427,7 @@ isl::map ZoneAlgorithm::getWrittenValue(MemoryAccess *MA, isl::map AccRel) {
   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
@@ -433,7 +437,7 @@ isl::map ZoneAlgorithm::getWrittenValue(MemoryAccess *MA, isl::map AccRel) {
     Type *Ty = MA->getLatestScopArrayInfo()->getElementType();
     if (WrittenConstant && WrittenConstant->isZeroValue()) {
       Constant *Zero = Constant::getNullValue(Ty);
-      return makeValInst(Zero, Stmt, L);
+      return makeNormalizedValInst(Zero, Stmt, L);
     }
   }
 
@@ -455,7 +459,7 @@ void ZoneAlgorithm::addArrayWriteAccess(MemoryAccess *MA) {
     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);
 
@@ -463,9 +467,90 @@ void ZoneAlgorithm::addArrayWriteAccess(MemoryAccess *MA) {
   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(const PHINode *PHI) {
+  SmallVector<const PHINode *, 8> Worklist;
+  SmallPtrSet<const PHINode *, 8> Visited;
+  Worklist.push_back(PHI);
+
+  while (!Worklist.empty()) {
+    const PHINode *Cur = Worklist.pop_back_val();
+
+    if (Visited.count(Cur))
+      continue;
+    Visited.insert(Cur);
+
+    for (const 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 {
@@ -681,6 +766,57 @@ isl::map ZoneAlgorithm::makeValInst(Value *Val, ScopStmt *UserStmt, Loop *Scope,
   llvm_unreachable("Unhandled use type");
 }
 
+/// Remove all computed PHIs out of @p Input and replace by their incoming
+/// value.
+///
+/// @param Input        { [] -> ValInst[] }
+/// @param ComputedPHIs Set of PHIs that are replaced. Its ValInst must appear
+///                     on the LHS of @p NormalizeMap.
+/// @param NormalizeMap { ValInst[] -> ValInst[] }
+static isl::union_map normalizeValInst(isl::union_map Input,
+                                       const DenseSet<PHINode *> &ComputedPHIs,
+                                       isl::union_map NormalizeMap) {
+  isl::union_map Result = isl::union_map::empty(Input.get_space());
+  Input.foreach_map(
+      [&Result, &ComputedPHIs, &NormalizeMap](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 (!ComputedPHIs.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(NormalizeMap);
+        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, ComputedPHIs, NormalizeMap);
+  return Normalized;
+}
+
 bool ZoneAlgorithm::isCompatibleAccess(MemoryAccess *MA) {
   if (!MA)
     return false;
@@ -690,6 +826,64 @@ bool ZoneAlgorithm::isCompatibleAccess(MemoryAccess *MA) {
   return isa<StoreInst>(AccInst) || isa<LoadInst>(AccInst);
 }
 
+bool ZoneAlgorithm::isNormalizable(MemoryAccess *MA) {
+  assert(MA->isRead());
+
+  // Exclude ExitPHIs, we are assuming that a normalizable PHI has a READ
+  // MemoryAccess.
+  if (!MA->isOriginalPHIKind())
+    return false;
+
+  // Exclude recursive PHIs, normalizing them would require a transitive
+  // closure.
+  auto *PHI = cast<PHINode>(MA->getAccessInstruction());
+  if (RecursivePHIs.count(PHI))
+    return false;
+
+  // Ensure that each incoming value can be represented by a ValInst[].
+  // We do represent values from statements associated to multiple incoming
+  // value by the PHI itself, but we do not handle this case yet (especially
+  // isNormalized()) when normalizing.
+  const ScopArrayInfo *SAI = MA->getOriginalScopArrayInfo();
+  auto Incomings = S->getPHIIncomings(SAI);
+  for (MemoryAccess *Incoming : Incomings) {
+    if (Incoming->getIncoming().size() != 1)
+      return false;
+  }
+
+  return true;
+}
+
+bool ZoneAlgorithm::isNormalized(isl::map Map) {
+  isl::space Space = Map.get_space();
+  isl::space 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;
+
+  auto *IncomingStmt = static_cast<ScopStmt *>(
+      RangeSpace.unwrap().get_tuple_id(isl::dim::in).get_user());
+  MemoryAccess *PHIRead = IncomingStmt->lookupPHIReadOf(PHI);
+  if (!isNormalizable(PHIRead))
+    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();
@@ -697,6 +891,11 @@ void ZoneAlgorithm::computeCommon() {
   AllWriteValInst = makeEmptyUnionMap();
   AllReadValInst = makeEmptyUnionMap();
 
+  // Default to empty, i.e. no normalization/replacement is taking place. Call
+  // computeNormalizedPHIs() to initialize.
+  NormalizeMap = makeEmptyUnionMap();
+  ComputedPHIs.clear();
+
   for (auto &Stmt : *S) {
     for (auto *MA : Stmt) {
       if (!MA->isLatestArrayKind())
@@ -720,6 +919,97 @@ void ZoneAlgorithm::computeCommon() {
   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;
+      if (!isNormalizable(MA))
+        continue;
+
+      auto *PHI = cast<PHINode>(MA->getAccessInstruction());
+      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();
+        assert(Incoming.size() == 1 && "The incoming value must be "
+                                       "representable by something else than "
+                                       "the PHI itself");
+        Value *IncomingVal = Incoming[0].second;
+
+        // { 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, AllPHIs, AllPHIMaps);
+      AllPHIs.insert(PHI);
+      AllPHIMaps = normalizeValInst(AllPHIMaps, AllPHIs, PHIMap);
+
+      AllPHIMaps = AllPHIMaps.unite(PHIMap);
+      NumNormalizablePHIs++;
+    }
+  }
+  simplify(AllPHIMaps);
+
+  // Apply the normalization.
+  ComputedPHIs = AllPHIs;
+  NormalizeMap = AllPHIMaps;
+
+  assert(!NormalizeMap || isNormalized(NormalizeMap));
+}
+
 void ZoneAlgorithm::printAccesses(llvm::raw_ostream &OS, int Indent) const {
   OS.indent(Indent) << "After accesses {\n";
   for (auto &Stmt : *S) {