1 //===------ CodeGeneration.cpp - Code generate the Scops using ISL. ----======// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // The CodeGeneration pass takes a Scop created by ScopInfo and translates it 11 // back to LLVM-IR using the ISL code generator. 12 // 13 // The Scop describes the high level memory behaviour of a control flow region. 14 // Transformation passes can update the schedule (execution order) of statements 15 // in the Scop. ISL is used to generate an abstract syntax tree that reflects 16 // the updated execution order. This clast is used to create new LLVM-IR that is 17 // computationally equivalent to the original control flow region, but executes 18 // its code in the new execution order defined by the changed schedule. 19 // 20 //===----------------------------------------------------------------------===// 21 22 #include "polly/CodeGen/IslNodeBuilder.h" 23 #include "polly/CodeGen/IslAst.h" 24 #include "polly/CodeGen/Utils.h" 25 #include "polly/DependenceInfo.h" 26 #include "polly/LinkAllPasses.h" 27 #include "polly/ScopInfo.h" 28 #include "polly/Support/ScopHelper.h" 29 #include "llvm/Analysis/AliasAnalysis.h" 30 #include "llvm/Analysis/BasicAliasAnalysis.h" 31 #include "llvm/Analysis/GlobalsModRef.h" 32 #include "llvm/Analysis/PostDominators.h" 33 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" 34 #include "llvm/IR/Module.h" 35 #include "llvm/IR/Verifier.h" 36 #include "llvm/Support/Debug.h" 37 38 using namespace polly; 39 using namespace llvm; 40 41 #define DEBUG_TYPE "polly-codegen" 42 43 namespace { 44 class CodeGeneration : public ScopPass { 45 public: 46 static char ID; 47 48 CodeGeneration() : ScopPass(ID) {} 49 50 /// @brief The datalayout used 51 const DataLayout *DL; 52 53 /// @name The analysis passes we need to generate code. 54 /// 55 ///{ 56 LoopInfo *LI; 57 IslAstInfo *AI; 58 DominatorTree *DT; 59 ScalarEvolution *SE; 60 RegionInfo *RI; 61 ///} 62 63 /// @brief Build the runtime condition. 64 /// 65 /// Build the condition that evaluates at run-time to true iff all 66 /// assumptions taken for the SCoP hold, and to false otherwise. 67 /// 68 /// @return A value evaluating to true/false if execution is save/unsafe. 69 Value *buildRTC(PollyIRBuilder &Builder, IslExprBuilder &ExprBuilder) { 70 Builder.SetInsertPoint(Builder.GetInsertBlock()->getTerminator()); 71 Value *RTC = ExprBuilder.create(AI->getRunCondition()); 72 if (!RTC->getType()->isIntegerTy(1)) 73 RTC = Builder.CreateIsNotNull(RTC); 74 return RTC; 75 } 76 77 bool verifyGeneratedFunction(Scop &S, Function &F) { 78 if (!verifyFunction(F)) 79 return false; 80 81 DEBUG({ 82 errs() << "== ISL Codegen created an invalid function ==\n\n== The " 83 "SCoP ==\n"; 84 S.print(errs()); 85 errs() << "\n== The isl AST ==\n"; 86 AI->printScop(errs(), S); 87 errs() << "\n== The invalid function ==\n"; 88 F.print(errs()); 89 errs() << "\n== The errors ==\n"; 90 verifyFunction(F, &errs()); 91 }); 92 93 return true; 94 } 95 96 // CodeGeneration adds a lot of BBs without updating the RegionInfo 97 // We make all created BBs belong to the scop's parent region without any 98 // nested structure to keep the RegionInfo verifier happy. 99 void fixRegionInfo(Function *F, Region *ParentRegion) { 100 for (BasicBlock &BB : *F) { 101 if (RI->getRegionFor(&BB)) 102 continue; 103 104 RI->setRegionFor(&BB, ParentRegion); 105 } 106 } 107 108 /// @brief Generate LLVM-IR for the SCoP @p S. 109 bool runOnScop(Scop &S) override { 110 AI = &getAnalysis<IslAstInfo>(); 111 112 // Check if we created an isl_ast root node, otherwise exit. 113 isl_ast_node *AstRoot = AI->getAst(); 114 if (!AstRoot) 115 return false; 116 117 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 118 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 119 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 120 DL = &S.getRegion().getEntry()->getParent()->getParent()->getDataLayout(); 121 RI = &getAnalysis<RegionInfoPass>().getRegionInfo(); 122 Region *R = &S.getRegion(); 123 assert(!R->isTopLevelRegion() && "Top level regions are not supported"); 124 125 ScopAnnotator Annotator; 126 Annotator.buildAliasScopes(S); 127 128 simplifyRegion(R, DT, LI, RI); 129 assert(R->isSimple()); 130 BasicBlock *EnteringBB = S.getRegion().getEnteringBlock(); 131 assert(EnteringBB); 132 PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator); 133 134 IslNodeBuilder NodeBuilder(Builder, Annotator, this, *DL, *LI, *SE, *DT, S); 135 136 // Only build the run-time condition and parameters _after_ having 137 // introduced the conditional branch. This is important as the conditional 138 // branch will guard the original scop from new induction variables that 139 // the SCEVExpander may introduce while code generating the parameters and 140 // which may introduce scalar dependences that prevent us from correctly 141 // code generating this scop. 142 BasicBlock *StartBlock = 143 executeScopConditionally(S, this, Builder.getTrue()); 144 auto SplitBlock = StartBlock->getSinglePredecessor(); 145 146 // First generate code for the hoisted invariant loads and transitively the 147 // parameters they reference. Afterwards, for the remaining parameters that 148 // might reference the hoisted loads. Finally, build the runtime check 149 // that might reference both hoisted loads as well as parameters. 150 Builder.SetInsertPoint(SplitBlock->getTerminator()); 151 NodeBuilder.preloadInvariantLoads(); 152 NodeBuilder.addParameters(S.getContext()); 153 154 Value *RTC = buildRTC(Builder, NodeBuilder.getExprBuilder()); 155 Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC); 156 Builder.SetInsertPoint(StartBlock->begin()); 157 158 NodeBuilder.create(AstRoot); 159 160 NodeBuilder.finalizeSCoP(S); 161 fixRegionInfo(EnteringBB->getParent(), R->getParent()); 162 163 assert(!verifyGeneratedFunction(S, *EnteringBB->getParent()) && 164 "Verification of generated function failed"); 165 return true; 166 } 167 168 /// @brief Register all analyses and transformation required. 169 void getAnalysisUsage(AnalysisUsage &AU) const override { 170 AU.addRequired<DominatorTreeWrapperPass>(); 171 AU.addRequired<IslAstInfo>(); 172 AU.addRequired<RegionInfoPass>(); 173 AU.addRequired<ScalarEvolutionWrapperPass>(); 174 AU.addRequired<ScopDetection>(); 175 AU.addRequired<ScopInfo>(); 176 AU.addRequired<LoopInfoWrapperPass>(); 177 178 AU.addPreserved<DependenceInfo>(); 179 180 AU.addPreserved<AAResultsWrapperPass>(); 181 AU.addPreserved<BasicAAWrapperPass>(); 182 AU.addPreserved<LoopInfoWrapperPass>(); 183 AU.addPreserved<DominatorTreeWrapperPass>(); 184 AU.addPreserved<GlobalsAAWrapperPass>(); 185 AU.addPreserved<PostDominatorTree>(); 186 AU.addPreserved<IslAstInfo>(); 187 AU.addPreserved<ScopDetection>(); 188 AU.addPreserved<ScalarEvolutionWrapperPass>(); 189 AU.addPreserved<SCEVAAWrapperPass>(); 190 191 // FIXME: We do not yet add regions for the newly generated code to the 192 // region tree. 193 AU.addPreserved<RegionInfoPass>(); 194 AU.addPreserved<ScopInfo>(); 195 } 196 }; 197 } 198 199 char CodeGeneration::ID = 1; 200 201 Pass *polly::createCodeGenerationPass() { return new CodeGeneration(); } 202 203 INITIALIZE_PASS_BEGIN(CodeGeneration, "polly-codegen", 204 "Polly - Create LLVM-IR from SCoPs", false, false); 205 INITIALIZE_PASS_DEPENDENCY(DependenceInfo); 206 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass); 207 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass); 208 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass); 209 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass); 210 INITIALIZE_PASS_DEPENDENCY(ScopDetection); 211 INITIALIZE_PASS_END(CodeGeneration, "polly-codegen", 212 "Polly - Create LLVM-IR from SCoPs", false, false) 213