Delete trivial PHI nodes (aka stack slot sharing)

During code preperation trivial PHI nodes (mainly introduced by lcssa) are
deleted to decrease the number of introduced allocas (==> dependences). However
simply replacing them by their only incoming value would cause the independent
block pass to introduce new allocas. To prevent this we try to share stack slots
during code preperarion, hence to reuse a already created alloca 'to demote' the
trivial PHI node. This works if we know that the value stored in this alloca
will be the incoming value of the trivial PHI at the end of the predecessor
block of this trivial PHI.

Contributed-by: Johannes Doerfert <doerfert@cs.uni-saarland.de>
llvm-svn: 205320

1 files changed, 83 insertions, 18 deletions

diff --git a/polly/lib/Transform/CodePreparation.cpp b/polly/lib/Transform/CodePreparation.cpp
index b0032498a8e..0989fe5f75b 100644
--- a/polly/lib/Transform/CodePreparation.cpp
+++ b/polly/lib/Transform/CodePreparation.cpp
@@ -49,6 +49,28 @@ using namespace llvm;
 using namespace polly;
 
 namespace {
+
+// Helper function which (for a given PHI node):
+//
+// 1) Remembers all incoming values and the associated basic blocks
+// 2) Demotes the phi node to the stack
+// 3) Remembers the correlation between the PHI node and the new alloca
+//
+// When we combine the information from 1) and 3) we know the values stored
+// in this alloca at the end of the predecessor basic blocks of the PHI.
+static void DemotePHI(
+    PHINode *PN, DenseMap<PHINode *, AllocaInst *> &PNallocMap,
+    DenseMap<std::pair<Value *, BasicBlock *>, PHINode *> &ValueLocToPhiMap) {
+
+  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
+    auto *InVal = PN->getIncomingValue(i);
+    auto *InBB = PN->getIncomingBlock(i);
+    ValueLocToPhiMap[std::make_pair(InVal, InBB)] = PN;
+  }
+
+  PNallocMap[PN] = DemotePHIToStack(PN);
+}
+
 /// @brief Prepare the IR for the scop detection.
 ///
 class CodePreparation : public FunctionPass {
@@ -84,12 +106,23 @@ void CodePreparation::clear() {}
 CodePreparation::~CodePreparation() { clear(); }
 
 bool CodePreparation::eliminatePHINodes(Function &F) {
-  // The PHINodes that will be deleted.
+  // The PHINodes that will be demoted.
+  std::vector<PHINode *> PNtoDemote;
+  // The PHINodes that will be deleted (stack slot sharing).
   std::vector<PHINode *> PNtoDelete;
   // The PHINodes that will be preserved.
-  std::vector<PHINode *> PreservedPNs;
-
-  // Scan the PHINodes in this function.
+  std::vector<PHINode *> PNtoPreserve;
+  // Map to remember values stored in PHINodes at the end of basic blocks.
+  DenseMap<std::pair<Value *, BasicBlock *>, PHINode *> ValueLocToPhiMap;
+  // Map from PHINodes to their alloca (after demotion) counterpart.
+  DenseMap<PHINode *, AllocaInst *> PNallocMap;
+
+  // Scan the PHINodes in this function and categorize them to be either:
+  // o Preserved, if they are (canonical) induction variables or can be
+  //              synthesized during code generation ('SCEVable')
+  // o Deleted, if they are trivial PHI nodes (one incoming value) and the
+  //            incoming value is a PHI node we will demote
+  // o Demoted, if they do not fit any of the previous categories
   for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI)
     for (BasicBlock::iterator II = BI->begin(), IE = BI->getFirstNonPHI();
          II != IE; ++II) {
@@ -98,7 +131,7 @@ bool CodePreparation::eliminatePHINodes(Function &F) {
         if (SE->isSCEVable(PN->getType())) {
           const SCEV *S = SE->getSCEV(PN);
           if (!isa<SCEVUnknown>(S) && !isa<SCEVCouldNotCompute>(S)) {
-            PreservedPNs.push_back(PN);
+            PNtoPreserve.push_back(PN);
             continue;
           }
         }
@@ -106,7 +139,7 @@ bool CodePreparation::eliminatePHINodes(Function &F) {
         if (Loop *L = LI->getLoopFor(BI)) {
           // Induction variables will be preserved.
           if (L->getCanonicalInductionVariable() == PN) {
-            PreservedPNs.push_back(PN);
+            PNtoPreserve.push_back(PN);
             continue;
           }
         }
@@ -114,26 +147,58 @@ bool CodePreparation::eliminatePHINodes(Function &F) {
 
       // As DemotePHIToStack does not support invoke edges, we preserve
       // PHINodes that have invoke edges.
-      if (hasInvokeEdge(PN))
-        PreservedPNs.push_back(PN);
-      else
-        PNtoDelete.push_back(PN);
+      if (hasInvokeEdge(PN)) {
+        PNtoPreserve.push_back(PN);
+      } else {
+        if (PN->getNumIncomingValues() == 1)
+          PNtoDelete.push_back(PN);
+        else
+          PNtoDemote.push_back(PN);
+      }
     }
 
-  if (PNtoDelete.empty())
+  if (PNtoDemote.empty() && PNtoDelete.empty())
     return false;
 
-  while (!PNtoDelete.empty()) {
-    PHINode *PN = PNtoDelete.back();
-    PNtoDelete.pop_back();
+  while (!PNtoDemote.empty()) {
+    PHINode *PN = PNtoDemote.back();
+    PNtoDemote.pop_back();
+    DemotePHI(PN, PNallocMap, ValueLocToPhiMap);
+  }
+
+  // For each trivial PHI we encountered (and we want to delete) we try to find
+  // the value it will hold in a alloca we already created by PHI demotion. If
+  // we succeed (the incoming value is stored in an alloca at the predecessor
+  // block), we can replace the trivial PHI by the value stored in the alloca.
+  // If not, we will demote this trivial PHI as any other one.
+  for (auto PNIt = PNtoDelete.rbegin(), PNEnd = PNtoDelete.rend();
+       PNIt != PNEnd; ++PNIt) {
+    PHINode *TrivPN = *PNIt;
+    assert(TrivPN->getNumIncomingValues() == 1 && "Assumed trivial PHI");
+
+    auto *InVal = TrivPN->getIncomingValue(0);
+    auto *InBB = TrivPN->getIncomingBlock(0);
+    const auto &ValLocIt = ValueLocToPhiMap.find(std::make_pair(InVal, InBB));
+    if (ValLocIt != ValueLocToPhiMap.end()) {
+      PHINode *InPHI = ValLocIt->second;
+      assert(PNallocMap.count(InPHI) &&
+             "Inconsitent state, PN was not demoted!");
+      auto *InPHIAlloca = PNallocMap[InPHI];
+      PNallocMap[TrivPN] = InPHIAlloca;
+      LoadInst *LI = new LoadInst(InPHIAlloca, "",
+                                  TrivPN->getParent()->getFirstInsertionPt());
+      TrivPN->replaceAllUsesWith(LI);
+      TrivPN->eraseFromParent();
+      continue;
+    }
 
-    DemotePHIToStack(PN);
+    DemotePHI(TrivPN, PNallocMap, ValueLocToPhiMap);
   }
 
   // Move preserved PHINodes to the beginning of the BasicBlock.
-  while (!PreservedPNs.empty()) {
-    PHINode *PN = PreservedPNs.back();
-    PreservedPNs.pop_back();
+  while (!PNtoPreserve.empty()) {
+    PHINode *PN = PNtoPreserve.back();
+    PNtoPreserve.pop_back();
 
     BasicBlock *BB = PN->getParent();
     if (PN == BB->begin())