Index: polly/trunk/include/polly/CodeGen/CodeGeneration.h =================================================================== --- polly/trunk/include/polly/CodeGen/CodeGeneration.h +++ polly/trunk/include/polly/CodeGen/CodeGeneration.h @@ -13,6 +13,7 @@ #define POLLY_CODEGENERATION_H #include "polly/Config/config.h" +#include "polly/ScopPass.h" #include "isl/map.h" #include "isl/set.h" @@ -23,6 +24,11 @@ VECTORIZER_POLLY, }; extern VectorizerChoice PollyVectorizerChoice; + +struct CodeGenerationPass : public PassInfoMixin { + PreservedAnalyses run(Scop &S, ScopAnalysisManager &SAM, + ScopStandardAnalysisResults &AR, SPMUpdater &U); +}; } // namespace polly #endif // POLLY_CODEGENERATION_H Index: polly/trunk/lib/CodeGen/CodeGeneration.cpp =================================================================== --- polly/trunk/lib/CodeGen/CodeGeneration.cpp +++ polly/trunk/lib/CodeGen/CodeGeneration.cpp @@ -19,6 +19,7 @@ // //===----------------------------------------------------------------------===// +#include "polly/CodeGen/CodeGeneration.h" #include "polly/CodeGen/IslAst.h" #include "polly/CodeGen/IslNodeBuilder.h" #include "polly/CodeGen/PerfMonitor.h" @@ -31,8 +32,10 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" #include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" #include "llvm/IR/Verifier.h" #include "llvm/Support/Debug.h" @@ -52,6 +55,198 @@ cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory)); namespace { + +static void verifyGeneratedFunction(Scop &S, Function &F, IslAstInfo &AI) { + if (!Verify || !verifyFunction(F, &errs())) + return; + + DEBUG({ + errs() << "== ISL Codegen created an invalid function ==\n\n== The " + "SCoP ==\n"; + S.print(errs()); + errs() << "\n== The isl AST ==\n"; + AI.print(errs()); + errs() << "\n== The invalid function ==\n"; + F.print(errs()); + }); + + llvm_unreachable("Polly generated function could not be verified. Add " + "-polly-codegen-verify=false to disable this assertion."); +} + +// CodeGeneration adds a lot of BBs without updating the RegionInfo +// We make all created BBs belong to the scop's parent region without any +// nested structure to keep the RegionInfo verifier happy. +static void fixRegionInfo(Function &F, Region &ParentRegion, RegionInfo &RI) { + for (BasicBlock &BB : F) { + if (RI.getRegionFor(&BB)) + continue; + + RI.setRegionFor(&BB, &ParentRegion); + } +} + +/// Mark a basic block unreachable. +/// +/// Marks the basic block @p Block unreachable by equipping it with an +/// UnreachableInst. +static void markBlockUnreachable(BasicBlock &Block, PollyIRBuilder &Builder) { + auto *OrigTerminator = Block.getTerminator(); + Builder.SetInsertPoint(OrigTerminator); + Builder.CreateUnreachable(); + OrigTerminator->eraseFromParent(); +} + +/// Remove all lifetime markers (llvm.lifetime.start, llvm.lifetime.end) from +/// @R. +/// +/// CodeGeneration does not copy lifetime markers into the optimized SCoP, +/// which would leave the them only in the original path. This can transform +/// code such as +/// +/// llvm.lifetime.start(%p) +/// llvm.lifetime.end(%p) +/// +/// into +/// +/// if (RTC) { +/// // generated code +/// } else { +/// // original code +/// llvm.lifetime.start(%p) +/// } +/// llvm.lifetime.end(%p) +/// +/// The current StackColoring algorithm cannot handle if some, but not all, +/// paths from the end marker to the entry block cross the start marker. Same +/// for start markers that do not always cross the end markers. We avoid any +/// issues by removing all lifetime markers, even from the original code. +/// +/// A better solution could be to hoist all llvm.lifetime.start to the split +/// node and all llvm.lifetime.end to the merge node, which should be +/// conservatively correct. +static void removeLifetimeMarkers(Region *R) { + for (auto *BB : R->blocks()) { + auto InstIt = BB->begin(); + auto InstEnd = BB->end(); + + while (InstIt != InstEnd) { + auto NextIt = InstIt; + ++NextIt; + + if (auto *IT = dyn_cast(&*InstIt)) { + switch (IT->getIntrinsicID()) { + case llvm::Intrinsic::lifetime_start: + case llvm::Intrinsic::lifetime_end: + BB->getInstList().erase(InstIt); + break; + default: + break; + } + } + + InstIt = NextIt; + } + } +} + +static bool CodeGen(Scop &S, IslAstInfo &AI, LoopInfo &LI, DominatorTree &DT, + ScalarEvolution &SE, RegionInfo &RI) { + // Check if we created an isl_ast root node, otherwise exit. + isl_ast_node *AstRoot = AI.getAst(); + if (!AstRoot) + return false; + + auto &DL = S.getFunction().getParent()->getDataLayout(); + Region *R = &S.getRegion(); + assert(!R->isTopLevelRegion() && "Top level regions are not supported"); + + ScopAnnotator Annotator; + Annotator.buildAliasScopes(S); + + simplifyRegion(R, &DT, &LI, &RI); + assert(R->isSimple()); + BasicBlock *EnteringBB = S.getEnteringBlock(); + assert(EnteringBB); + PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator); + + // Only build the run-time condition and parameters _after_ having + // introduced the conditional branch. This is important as the conditional + // branch will guard the original scop from new induction variables that + // the SCEVExpander may introduce while code generating the parameters and + // which may introduce scalar dependences that prevent us from correctly + // code generating this scop. + BasicBlock *StartBlock = + executeScopConditionally(S, Builder.getTrue(), DT, RI, LI); + removeLifetimeMarkers(R); + auto *SplitBlock = StartBlock->getSinglePredecessor(); + + IslNodeBuilder NodeBuilder(Builder, Annotator, DL, LI, SE, DT, S, StartBlock); + + if (PerfMonitoring) { + PerfMonitor P(EnteringBB->getParent()->getParent()); + P.initialize(); + P.insertRegionStart(SplitBlock->getTerminator()); + + BasicBlock *MergeBlock = SplitBlock->getTerminator() + ->getSuccessor(0) + ->getUniqueSuccessor() + ->getUniqueSuccessor(); + P.insertRegionEnd(MergeBlock->getTerminator()); + } + + // First generate code for the hoisted invariant loads and transitively the + // parameters they reference. Afterwards, for the remaining parameters that + // might reference the hoisted loads. Finally, build the runtime check + // that might reference both hoisted loads as well as parameters. + // If the hoisting fails we have to bail and execute the original code. + Builder.SetInsertPoint(SplitBlock->getTerminator()); + if (!NodeBuilder.preloadInvariantLoads()) { + + // Patch the introduced branch condition to ensure that we always execute + // the original SCoP. + auto *FalseI1 = Builder.getFalse(); + auto *SplitBBTerm = Builder.GetInsertBlock()->getTerminator(); + SplitBBTerm->setOperand(0, FalseI1); + + // Since the other branch is hence ignored we mark it as unreachable and + // adjust the dominator tree accordingly. + auto *ExitingBlock = StartBlock->getUniqueSuccessor(); + assert(ExitingBlock); + auto *MergeBlock = ExitingBlock->getUniqueSuccessor(); + assert(MergeBlock); + markBlockUnreachable(*StartBlock, Builder); + markBlockUnreachable(*ExitingBlock, Builder); + auto *ExitingBB = S.getExitingBlock(); + assert(ExitingBB); + DT.changeImmediateDominator(MergeBlock, ExitingBB); + DT.eraseNode(ExitingBlock); + + isl_ast_node_free(AstRoot); + } else { + NodeBuilder.allocateNewArrays(); + NodeBuilder.addParameters(S.getContext()); + Value *RTC = NodeBuilder.createRTC(AI.getRunCondition()); + + Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC); + Builder.SetInsertPoint(&StartBlock->front()); + + NodeBuilder.create(AstRoot); + NodeBuilder.finalize(); + fixRegionInfo(*EnteringBB->getParent(), *R->getParent(), RI); + } + + Function *F = EnteringBB->getParent(); + verifyGeneratedFunction(S, *F, AI); + for (auto *SubF : NodeBuilder.getParallelSubfunctions()) + verifyGeneratedFunction(S, *SubF, AI); + + // Mark the function such that we run additional cleanup passes on this + // function (e.g. mem2reg to rediscover phi nodes). + F->addFnAttr("polly-optimized"); + return true; +} + class CodeGeneration : public ScopPass { public: static char ID; @@ -71,203 +266,15 @@ RegionInfo *RI; ///} - void verifyGeneratedFunction(Scop &S, Function &F) { - if (!Verify || !verifyFunction(F, &errs())) - return; - - DEBUG({ - errs() << "== ISL Codegen created an invalid function ==\n\n== The " - "SCoP ==\n"; - S.print(errs()); - errs() << "\n== The isl AST ==\n"; - AI->print(errs()); - errs() << "\n== The invalid function ==\n"; - F.print(errs()); - }); - - llvm_unreachable("Polly generated function could not be verified. Add " - "-polly-codegen-verify=false to disable this assertion."); - } - - // CodeGeneration adds a lot of BBs without updating the RegionInfo - // We make all created BBs belong to the scop's parent region without any - // nested structure to keep the RegionInfo verifier happy. - void fixRegionInfo(Function *F, Region *ParentRegion) { - for (BasicBlock &BB : *F) { - if (RI->getRegionFor(&BB)) - continue; - - RI->setRegionFor(&BB, ParentRegion); - } - } - - /// Mark a basic block unreachable. - /// - /// Marks the basic block @p Block unreachable by equipping it with an - /// UnreachableInst. - void markBlockUnreachable(BasicBlock &Block, PollyIRBuilder &Builder) { - auto *OrigTerminator = Block.getTerminator(); - Builder.SetInsertPoint(OrigTerminator); - Builder.CreateUnreachable(); - OrigTerminator->eraseFromParent(); - } - - /// Remove all lifetime markers (llvm.lifetime.start, llvm.lifetime.end) from - /// @R. - /// - /// CodeGeneration does not copy lifetime markers into the optimized SCoP, - /// which would leave the them only in the original path. This can transform - /// code such as - /// - /// llvm.lifetime.start(%p) - /// llvm.lifetime.end(%p) - /// - /// into - /// - /// if (RTC) { - /// // generated code - /// } else { - /// // original code - /// llvm.lifetime.start(%p) - /// } - /// llvm.lifetime.end(%p) - /// - /// The current StackColoring algorithm cannot handle if some, but not all, - /// paths from the end marker to the entry block cross the start marker. Same - /// for start markers that do not always cross the end markers. We avoid any - /// issues by removing all lifetime markers, even from the original code. - /// - /// A better solution could be to hoist all llvm.lifetime.start to the split - /// node and all llvm.lifetime.end to the merge node, which should be - /// conservatively correct. - void removeLifetimeMarkers(Region *R) { - for (auto *BB : R->blocks()) { - auto InstIt = BB->begin(); - auto InstEnd = BB->end(); - - while (InstIt != InstEnd) { - auto NextIt = InstIt; - ++NextIt; - - if (auto *IT = dyn_cast(&*InstIt)) { - switch (IT->getIntrinsicID()) { - case llvm::Intrinsic::lifetime_start: - case llvm::Intrinsic::lifetime_end: - BB->getInstList().erase(InstIt); - break; - default: - break; - } - } - - InstIt = NextIt; - } - } - } - /// Generate LLVM-IR for the SCoP @p S. bool runOnScop(Scop &S) override { AI = &getAnalysis().getAI(); - - // Check if we created an isl_ast root node, otherwise exit. - isl_ast_node *AstRoot = AI->getAst(); - if (!AstRoot) - return false; - LI = &getAnalysis().getLoopInfo(); DT = &getAnalysis().getDomTree(); SE = &getAnalysis().getSE(); DL = &S.getFunction().getParent()->getDataLayout(); RI = &getAnalysis().getRegionInfo(); - Region *R = &S.getRegion(); - assert(!R->isTopLevelRegion() && "Top level regions are not supported"); - - ScopAnnotator Annotator; - Annotator.buildAliasScopes(S); - - simplifyRegion(R, DT, LI, RI); - assert(R->isSimple()); - BasicBlock *EnteringBB = S.getEnteringBlock(); - assert(EnteringBB); - PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator); - - // Only build the run-time condition and parameters _after_ having - // introduced the conditional branch. This is important as the conditional - // branch will guard the original scop from new induction variables that - // the SCEVExpander may introduce while code generating the parameters and - // which may introduce scalar dependences that prevent us from correctly - // code generating this scop. - BasicBlock *StartBlock = - executeScopConditionally(S, Builder.getTrue(), *DT, *RI, *LI); - removeLifetimeMarkers(R); - auto *SplitBlock = StartBlock->getSinglePredecessor(); - - IslNodeBuilder NodeBuilder(Builder, Annotator, *DL, *LI, *SE, *DT, S, - StartBlock); - - if (PerfMonitoring) { - PerfMonitor P(EnteringBB->getParent()->getParent()); - P.initialize(); - P.insertRegionStart(SplitBlock->getTerminator()); - - BasicBlock *MergeBlock = SplitBlock->getTerminator() - ->getSuccessor(0) - ->getUniqueSuccessor() - ->getUniqueSuccessor(); - P.insertRegionEnd(MergeBlock->getTerminator()); - } - - // First generate code for the hoisted invariant loads and transitively the - // parameters they reference. Afterwards, for the remaining parameters that - // might reference the hoisted loads. Finally, build the runtime check - // that might reference both hoisted loads as well as parameters. - // If the hoisting fails we have to bail and execute the original code. - Builder.SetInsertPoint(SplitBlock->getTerminator()); - if (!NodeBuilder.preloadInvariantLoads()) { - - // Patch the introduced branch condition to ensure that we always execute - // the original SCoP. - auto *FalseI1 = Builder.getFalse(); - auto *SplitBBTerm = Builder.GetInsertBlock()->getTerminator(); - SplitBBTerm->setOperand(0, FalseI1); - - // Since the other branch is hence ignored we mark it as unreachable and - // adjust the dominator tree accordingly. - auto *ExitingBlock = StartBlock->getUniqueSuccessor(); - assert(ExitingBlock); - auto *MergeBlock = ExitingBlock->getUniqueSuccessor(); - assert(MergeBlock); - markBlockUnreachable(*StartBlock, Builder); - markBlockUnreachable(*ExitingBlock, Builder); - auto *ExitingBB = S.getExitingBlock(); - assert(ExitingBB); - DT->changeImmediateDominator(MergeBlock, ExitingBB); - DT->eraseNode(ExitingBlock); - - isl_ast_node_free(AstRoot); - } else { - NodeBuilder.allocateNewArrays(); - NodeBuilder.addParameters(S.getContext()); - Value *RTC = NodeBuilder.createRTC(AI->getRunCondition()); - - Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC); - Builder.SetInsertPoint(&StartBlock->front()); - - NodeBuilder.create(AstRoot); - NodeBuilder.finalize(); - fixRegionInfo(EnteringBB->getParent(), R->getParent()); - } - - Function *F = EnteringBB->getParent(); - verifyGeneratedFunction(S, *F); - for (auto *SubF : NodeBuilder.getParallelSubfunctions()) - verifyGeneratedFunction(S, *SubF); - - // Mark the function such that we run additional cleanup passes on this - // function (e.g. mem2reg to rediscover phi nodes). - F->addFnAttr("polly-optimized"); - - return true; + return CodeGen(S, *AI, *LI, *DT, *SE, *RI); } /// Register all analyses and transformation required. @@ -300,6 +307,16 @@ }; } // namespace +PreservedAnalyses +polly::CodeGenerationPass::run(Scop &S, ScopAnalysisManager &SAM, + ScopStandardAnalysisResults &AR, SPMUpdater &U) { + auto &AI = SAM.getResult(S, AR); + if (CodeGen(S, AI, AR.LI, AR.DT, AR.SE, AR.RI)) + return PreservedAnalyses::none(); + + return PreservedAnalyses::all(); +} + char CodeGeneration::ID = 1; Pass *polly::createCodeGenerationPass() { return new CodeGeneration(); }