lib/CodeGen/CodeGeneration.cpp

   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/CodeGeneration.h"
  23 #include "polly/CodeGen/IslAst.h"
  24 #include "polly/CodeGen/IslNodeBuilder.h"
  25 #include "polly/CodeGen/PerfMonitor.h"
  26 #include "polly/CodeGen/Utils.h"
  27 #include "polly/DependenceInfo.h"
  28 #include "polly/LinkAllPasses.h"
  29 #include "polly/Options.h"
  30 #include "polly/ScopInfo.h"
  31 #include "polly/Support/ScopHelper.h"
  32 #include "llvm/Analysis/AliasAnalysis.h"
  33 #include "llvm/Analysis/BasicAliasAnalysis.h"
  34 #include "llvm/Analysis/GlobalsModRef.h"
  35 #include "llvm/Analysis/LoopInfo.h"
  36 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
  37 #include "llvm/IR/Module.h"
  38 #include "llvm/IR/PassManager.h"
  39 #include "llvm/IR/Verifier.h"
  40 #include "llvm/Support/Debug.h"
  41
  42 using namespace polly;
  43 using namespace llvm;
  44
  45 #define DEBUG_TYPE "polly-codegen"
  46
  47 static cl::opt<bool> Verify("polly-codegen-verify",
  48                             cl::desc("Verify the function generated by Polly"),
  49                             cl::Hidden, cl::init(false), cl::ZeroOrMore,
  50                             cl::cat(PollyCategory));
  51
  52 static cl::opt<bool>
  53     PerfMonitoring("polly-codegen-perf-monitoring",
  54                    cl::desc("Add run-time performance monitoring"), cl::Hidden,
  55                    cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
  56
  57 namespace {
  58
  59 static void verifyGeneratedFunction(Scop &S, Function &F, IslAstInfo &AI) {
  60   if (!Verify || !verifyFunction(F, &errs()))
  61     return;
  62
  63   DEBUG({
  64     errs() << "== ISL Codegen created an invalid function ==\n\n== The "
  65               "SCoP ==\n";
  66     S.print(errs());
  67     errs() << "\n== The isl AST ==\n";
  68     AI.print(errs());
  69     errs() << "\n== The invalid function ==\n";
  70     F.print(errs());
  71   });
  72
  73   llvm_unreachable("Polly generated function could not be verified. Add "
  74                    "-polly-codegen-verify=false to disable this assertion.");
  75 }
  76
  77 // CodeGeneration adds a lot of BBs without updating the RegionInfo
  78 // We make all created BBs belong to the scop's parent region without any
  79 // nested structure to keep the RegionInfo verifier happy.
  80 static void fixRegionInfo(Function &F, Region &ParentRegion, RegionInfo &RI) {
  81   for (BasicBlock &BB : F) {
  82     if (RI.getRegionFor(&BB))
  83       continue;
  84
  85     RI.setRegionFor(&BB, &ParentRegion);
  86   }
  87 }
  88
  89 /// Mark a basic block unreachable.
  90 ///
  91 /// Marks the basic block @p Block unreachable by equipping it with an
  92 /// UnreachableInst.
  93 static void markBlockUnreachable(BasicBlock &Block, PollyIRBuilder &Builder) {
  94   auto *OrigTerminator = Block.getTerminator();
  95   Builder.SetInsertPoint(OrigTerminator);
  96   Builder.CreateUnreachable();
  97   OrigTerminator->eraseFromParent();
  98 }
  99
 100 /// Remove all lifetime markers (llvm.lifetime.start, llvm.lifetime.end) from
 101 /// @R.
 102 ///
 103 /// CodeGeneration does not copy lifetime markers into the optimized SCoP,
 104 /// which would leave the them only in the original path. This can transform
 105 /// code such as
 106 ///
 107 ///     llvm.lifetime.start(%p)
 108 ///     llvm.lifetime.end(%p)
 109 ///
 110 /// into
 111 ///
 112 ///     if (RTC) {
 113 ///       // generated code
 114 ///     } else {
 115 ///       // original code
 116 ///       llvm.lifetime.start(%p)
 117 ///     }
 118 ///     llvm.lifetime.end(%p)
 119 ///
 120 /// The current StackColoring algorithm cannot handle if some, but not all,
 121 /// paths from the end marker to the entry block cross the start marker. Same
 122 /// for start markers that do not always cross the end markers. We avoid any
 123 /// issues by removing all lifetime markers, even from the original code.
 124 ///
 125 /// A better solution could be to hoist all llvm.lifetime.start to the split
 126 /// node and all llvm.lifetime.end to the merge node, which should be
 127 /// conservatively correct.
 128 static void removeLifetimeMarkers(Region *R) {
 129   for (auto *BB : R->blocks()) {
 130     auto InstIt = BB->begin();
 131     auto InstEnd = BB->end();
 132
 133     while (InstIt != InstEnd) {
 134       auto NextIt = InstIt;
 135       ++NextIt;
 136
 137       if (auto *IT = dyn_cast<IntrinsicInst>(&*InstIt)) {
 138         switch (IT->getIntrinsicID()) {
 139         case llvm::Intrinsic::lifetime_start:
 140         case llvm::Intrinsic::lifetime_end:
 141           BB->getInstList().erase(InstIt);
 142           break;
 143         default:
 144           break;
 145         }
 146       }
 147
 148       InstIt = NextIt;
 149     }
 150   }
 151 }
 152
 153 static bool CodeGen(Scop &S, IslAstInfo &AI, LoopInfo &LI, DominatorTree &DT,
 154                     ScalarEvolution &SE, RegionInfo &RI) {
 155   // Check if we created an isl_ast root node, otherwise exit.
 156   isl_ast_node *AstRoot = AI.getAst();
 157   if (!AstRoot)
 158     return false;
 159
 160   auto &DL = S.getFunction().getParent()->getDataLayout();
 161   Region *R = &S.getRegion();
 162   assert(!R->isTopLevelRegion() && "Top level regions are not supported");
 163
 164   ScopAnnotator Annotator;
 165   Annotator.buildAliasScopes(S);
 166
 167   simplifyRegion(R, &DT, &LI, &RI);
 168   assert(R->isSimple());
 169   BasicBlock *EnteringBB = S.getEnteringBlock();
 170   assert(EnteringBB);
 171   PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator);
 172
 173   // Only build the run-time condition and parameters _after_ having
 174   // introduced the conditional branch. This is important as the conditional
 175   // branch will guard the original scop from new induction variables that
 176   // the SCEVExpander may introduce while code generating the parameters and
 177   // which may introduce scalar dependences that prevent us from correctly
 178   // code generating this scop.
 179   BasicBlock *StartBlock =
 180       executeScopConditionally(S, Builder.getTrue(), DT, RI, LI);
 181   removeLifetimeMarkers(R);
 182   auto *SplitBlock = StartBlock->getSinglePredecessor();
 183
 184   IslNodeBuilder NodeBuilder(Builder, Annotator, DL, LI, SE, DT, S, StartBlock);
 185
 186   if (PerfMonitoring) {
 187     PerfMonitor P(EnteringBB->getParent()->getParent());
 188     P.initialize();
 189     P.insertRegionStart(SplitBlock->getTerminator());
 190
 191     BasicBlock *MergeBlock = SplitBlock->getTerminator()
 192                                  ->getSuccessor(0)
 193                                  ->getUniqueSuccessor()
 194                                  ->getUniqueSuccessor();
 195     P.insertRegionEnd(MergeBlock->getTerminator());
 196   }
 197
 198   // First generate code for the hoisted invariant loads and transitively the
 199   // parameters they reference. Afterwards, for the remaining parameters that
 200   // might reference the hoisted loads. Finally, build the runtime check
 201   // that might reference both hoisted loads as well as parameters.
 202   // If the hoisting fails we have to bail and execute the original code.
 203   Builder.SetInsertPoint(SplitBlock->getTerminator());
 204   if (!NodeBuilder.preloadInvariantLoads()) {
 205
 206     // Patch the introduced branch condition to ensure that we always execute
 207     // the original SCoP.
 208     auto *FalseI1 = Builder.getFalse();
 209     auto *SplitBBTerm = Builder.GetInsertBlock()->getTerminator();
 210     SplitBBTerm->setOperand(0, FalseI1);
 211
 212     // Since the other branch is hence ignored we mark it as unreachable and
 213     // adjust the dominator tree accordingly.
 214     auto *ExitingBlock = StartBlock->getUniqueSuccessor();
 215     assert(ExitingBlock);
 216     auto *MergeBlock = ExitingBlock->getUniqueSuccessor();
 217     assert(MergeBlock);
 218     markBlockUnreachable(*StartBlock, Builder);
 219     markBlockUnreachable(*ExitingBlock, Builder);
 220     auto *ExitingBB = S.getExitingBlock();
 221     assert(ExitingBB);
 222     DT.changeImmediateDominator(MergeBlock, ExitingBB);
 223     DT.eraseNode(ExitingBlock);
 224
 225     isl_ast_node_free(AstRoot);
 226   } else {
 227     NodeBuilder.allocateNewArrays();
 228     NodeBuilder.addParameters(S.getContext());
 229     Value *RTC = NodeBuilder.createRTC(AI.getRunCondition());
 230
 231     Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC);
 232     Builder.SetInsertPoint(&StartBlock->front());
 233
 234     NodeBuilder.create(AstRoot);
 235     NodeBuilder.finalize();
 236     fixRegionInfo(*EnteringBB->getParent(), *R->getParent(), RI);
 237   }
 238
 239   Function *F = EnteringBB->getParent();
 240   verifyGeneratedFunction(S, *F, AI);
 241   for (auto *SubF : NodeBuilder.getParallelSubfunctions())
 242     verifyGeneratedFunction(S, *SubF, AI);
 243
 244   // Mark the function such that we run additional cleanup passes on this
 245   // function (e.g. mem2reg to rediscover phi nodes).
 246   F->addFnAttr("polly-optimized");
 247   return true;
 248 }
 249
 250 class CodeGeneration : public ScopPass {
 251 public:
 252   static char ID;
 253
 254   CodeGeneration() : ScopPass(ID) {}
 255
 256   /// The datalayout used
 257   const DataLayout *DL;
 258
 259   /// @name The analysis passes we need to generate code.
 260   ///
 261   ///{
 262   LoopInfo *LI;
 263   IslAstInfo *AI;
 264   DominatorTree *DT;
 265   ScalarEvolution *SE;
 266   RegionInfo *RI;
 267   ///}
 268
 269   /// Generate LLVM-IR for the SCoP @p S.
 270   bool runOnScop(Scop &S) override {
 271     AI = &getAnalysis<IslAstInfoWrapperPass>().getAI();
 272     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 273     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 274     SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 275     DL = &S.getFunction().getParent()->getDataLayout();
 276     RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
 277     return CodeGen(S, *AI, *LI, *DT, *SE, *RI);
 278   }
 279
 280   /// Register all analyses and transformation required.
 281   void getAnalysisUsage(AnalysisUsage &AU) const override {
 282     AU.addRequired<DominatorTreeWrapperPass>();
 283     AU.addRequired<IslAstInfoWrapperPass>();
 284     AU.addRequired<RegionInfoPass>();
 285     AU.addRequired<ScalarEvolutionWrapperPass>();
 286     AU.addRequired<ScopDetectionWrapperPass>();
 287     AU.addRequired<ScopInfoRegionPass>();
 288     AU.addRequired<LoopInfoWrapperPass>();
 289
 290     AU.addPreserved<DependenceInfo>();
 291
 292     AU.addPreserved<AAResultsWrapperPass>();
 293     AU.addPreserved<BasicAAWrapperPass>();
 294     AU.addPreserved<LoopInfoWrapperPass>();
 295     AU.addPreserved<DominatorTreeWrapperPass>();
 296     AU.addPreserved<GlobalsAAWrapperPass>();
 297     AU.addPreserved<IslAstInfoWrapperPass>();
 298     AU.addPreserved<ScopDetectionWrapperPass>();
 299     AU.addPreserved<ScalarEvolutionWrapperPass>();
 300     AU.addPreserved<SCEVAAWrapperPass>();
 301
 302     // FIXME: We do not yet add regions for the newly generated code to the
 303     //        region tree.
 304     AU.addPreserved<RegionInfoPass>();
 305     AU.addPreserved<ScopInfoRegionPass>();
 306   }
 307 };
 308 } // namespace
 309
 310 PreservedAnalyses
 311 polly::CodeGenerationPass::run(Scop &S, ScopAnalysisManager &SAM,
 312                                ScopStandardAnalysisResults &AR, SPMUpdater &U) {
 313   auto &AI = SAM.getResult<IslAstAnalysis>(S, AR);
 314   if (CodeGen(S, AI, AR.LI, AR.DT, AR.SE, AR.RI))
 315     return PreservedAnalyses::none();
 316
 317   return PreservedAnalyses::all();
 318 }
 319
 320 char CodeGeneration::ID = 1;
 321
 322 Pass *polly::createCodeGenerationPass() { return new CodeGeneration(); }
 323
 324 INITIALIZE_PASS_BEGIN(CodeGeneration, "polly-codegen",
 325                       "Polly - Create LLVM-IR from SCoPs", false, false);
 326 INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
 327 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
 328 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
 329 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
 330 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
 331 INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass);
 332 INITIALIZE_PASS_END(CodeGeneration, "polly-codegen",
 333                     "Polly - Create LLVM-IR from SCoPs", false, false)