diff options
Diffstat (limited to 'polly/lib/Transform/CodePreparation.cpp')
| -rw-r--r-- | polly/lib/Transform/CodePreparation.cpp | 182 |
1 files changed, 182 insertions, 0 deletions
diff --git a/polly/lib/Transform/CodePreparation.cpp b/polly/lib/Transform/CodePreparation.cpp new file mode 100644 index 00000000000..b0032498a8e --- /dev/null +++ b/polly/lib/Transform/CodePreparation.cpp @@ -0,0 +1,182 @@ +//===---- CodePreparation.cpp - Code preparation for Scop Detection -------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// 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. Depending of the code generation +// strategy different PHI nodes are translated: +// +// - indvars based code generation: +// +// The indvars based code generation requires explicit canonical induction +// variables. Such variables are generated before scop detection and +// also before the code preparation pass. All PHI nodes that are not canonical +// induction variables are not supported by the indvars based code generation +// and are consequently translated into explict memory accesses. +// +// - scev based code generation: +// +// The scev based 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. +// +// 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. +// +//===----------------------------------------------------------------------===// + +#include "polly/LinkAllPasses.h" +#include "polly/CodeGen/BlockGenerators.h" +#include "polly/Support/ScopHelper.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/RegionInfo.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Transforms/Utils/Local.h" + +using namespace llvm; +using namespace polly; + +namespace { +/// @brief Prepare the IR for the scop detection. +/// +class CodePreparation : public FunctionPass { + CodePreparation(const CodePreparation &) LLVM_DELETED_FUNCTION; + const CodePreparation & + operator=(const CodePreparation &) LLVM_DELETED_FUNCTION; + + LoopInfo *LI; + ScalarEvolution *SE; + + void clear(); + + bool eliminatePHINodes(Function &F); + +public: + static char ID; + + explicit CodePreparation() : FunctionPass(ID) {} + ~CodePreparation(); + + /// @name FunctionPass interface. + //@{ + virtual void getAnalysisUsage(AnalysisUsage &AU) const; + virtual void releaseMemory(); + virtual bool runOnFunction(Function &F); + virtual void print(raw_ostream &OS, const Module *) const; + //@} +}; +} + +void CodePreparation::clear() {} + +CodePreparation::~CodePreparation() { clear(); } + +bool CodePreparation::eliminatePHINodes(Function &F) { + // The PHINodes that will be deleted. + std::vector<PHINode *> PNtoDelete; + // The PHINodes that will be preserved. + std::vector<PHINode *> PreservedPNs; + + // Scan the PHINodes in this function. + 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 (SCEVCodegen) { + if (SE->isSCEVable(PN->getType())) { + const SCEV *S = SE->getSCEV(PN); + if (!isa<SCEVUnknown>(S) && !isa<SCEVCouldNotCompute>(S)) { + PreservedPNs.push_back(PN); + continue; + } + } + } else { + if (Loop *L = LI->getLoopFor(BI)) { + // Induction variables will be preserved. + if (L->getCanonicalInductionVariable() == PN) { + PreservedPNs.push_back(PN); + continue; + } + } + } + + // 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 (PNtoDelete.empty()) + return false; + + while (!PNtoDelete.empty()) { + PHINode *PN = PNtoDelete.back(); + PNtoDelete.pop_back(); + + DemotePHIToStack(PN); + } + + // Move preserved PHINodes to the beginning of the BasicBlock. + while (!PreservedPNs.empty()) { + PHINode *PN = PreservedPNs.back(); + PreservedPNs.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<LoopInfo>(); + AU.addRequired<ScalarEvolution>(); + + AU.addPreserved<LoopInfo>(); + AU.addPreserved<RegionInfo>(); + AU.addPreserved<DominatorTreeWrapperPass>(); + AU.addPreserved<DominanceFrontier>(); +} + +bool CodePreparation::runOnFunction(Function &F) { + LI = &getAnalysis<LoopInfo>(); + SE = &getAnalysis<ScalarEvolution>(); + + splitEntryBlockForAlloca(&F.getEntryBlock(), this); + + eliminatePHINodes(F); + + return false; +} + +void CodePreparation::releaseMemory() { clear(); } + +void CodePreparation::print(raw_ostream &OS, const Module *) const {} + +char CodePreparation::ID = 0; +char &polly::CodePreparationID = CodePreparation::ID; + +Pass *polly::createCodePreparationPass() { return new CodePreparation(); } + +INITIALIZE_PASS_BEGIN(CodePreparation, "polly-prepare", + "Polly - Prepare code for polly", false, false) +INITIALIZE_PASS_DEPENDENCY(LoopInfo) +INITIALIZE_PASS_END(CodePreparation, "polly-prepare", + "Polly - Prepare code for polly", false, false) |
