Remove code for scalar and PHI to array translation

This removes old code that has been disabled since several weeks and was hidden
behind the flags -disable-polly-intra-scop-scalar-to-array=false and
-polly-model-phi-nodes=false. Earlier, Polly used to translate scalars and
PHI nodes to single element arrays, as this avoided the need for their special
handling in Polly. With Johannes' patches adding native support for such scalar
references to Polly, this code is not needed any more. After this commit both
-polly-prepare and -polly-independent are now mostly no-ops. Only a couple of
simple transformations still remain, but they are scheduled for removal too.

Thanks again to Johannes Doerfert for his nice work in making all this code
obsolete.

llvm-svn: 240766

1 files changed, 4 insertions, 133 deletions

diff --git a/polly/lib/Transform/CodePreparation.cpp b/polly/lib/Transform/CodePreparation.cpp
index 9d4b55b24aa..78e256326fb 100644
--- a/polly/lib/Transform/CodePreparation.cpp
+++ b/polly/lib/Transform/CodePreparation.cpp
@@ -7,22 +7,12 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// The Polly code preparation pass is executed before SCoP detection. Its only
-// use is to translate all PHI nodes that can not be expressed by the code
-// generator into explicit memory dependences.
-//
-// Polly's code generation can code generate all PHI nodes that do not
-// reference parameters within the scop. As the code preparation pass is run
-// before scop detection, we can not check this condition, because without
-// a detected scop, we do not know SCEVUnknowns that appear in the SCEV of
-// a PHI node may later be within or outside of the SCoP. Hence, we follow a
-// heuristic and translate all PHI nodes that are either directly SCEVUnknown
-// or SCEVCouldNotCompute. This will hopefully get most of the PHI nodes that
-// are introduced due to conditional control flow, but not the ones that are
-// referencing loop counters.
+// The Polly code preparation pass is executed before SCoP detection. Its
+// currently only splits the entry block of the SCoP to make room for alloc
+// instructions as they are generated during code generation.
 //
 // XXX: In the future, we should remove the need for this pass entirely and
-// instead add support for scalar dependences to ScopInfo and code generation.
+// instead add this spitting to the code generation pass.
 //
 //===----------------------------------------------------------------------===//
 
@@ -41,27 +31,6 @@ 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 {
@@ -95,101 +64,6 @@ void CodePreparation::clear() {}
 
 CodePreparation::~CodePreparation() { clear(); }
 
-bool CodePreparation::eliminatePHINodes(Function &F) {
-  // 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 *> 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) {
-      PHINode *PN = cast<PHINode>(II);
-      if (SE->isSCEVable(PN->getType())) {
-        const SCEV *S = SE->getSCEV(PN);
-        if (!isa<SCEVUnknown>(S) && !isa<SCEVCouldNotCompute>(S)) {
-          PNtoPreserve.push_back(PN);
-          continue;
-        }
-      }
-
-      // As DemotePHIToStack does not support invoke edges, we preserve
-      // PHINodes that have invoke edges.
-      if (hasInvokeEdge(PN)) {
-        PNtoPreserve.push_back(PN);
-      } else {
-        if (PN->getNumIncomingValues() == 1)
-          PNtoDelete.push_back(PN);
-        else
-          PNtoDemote.push_back(PN);
-      }
-    }
-
-  if (PNtoDemote.empty() && PNtoDelete.empty())
-    return false;
-
-  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;
-    }
-
-    DemotePHI(TrivPN, PNallocMap, ValueLocToPhiMap);
-  }
-
-  // Move preserved PHINodes to the beginning of the BasicBlock.
-  while (!PNtoPreserve.empty()) {
-    PHINode *PN = PNtoPreserve.back();
-    PNtoPreserve.pop_back();
-
-    BasicBlock *BB = PN->getParent();
-    if (PN == BB->begin())
-      continue;
-
-    PN->moveBefore(BB->begin());
-  }
-
-  return true;
-}
-
 void CodePreparation::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<LoopInfoWrapperPass>();
   AU.addRequired<ScalarEvolution>();
@@ -206,9 +80,6 @@ bool CodePreparation::runOnFunction(Function &F) {
 
   splitEntryBlockForAlloca(&F.getEntryBlock(), this);
 
-  if (!PollyModelPHINodes)
-    eliminatePHINodes(F);
-
   return false;
 }