[Polly][NewPM] Port CodeGen to the new PM

[philip.pfaffe]

Summary

To move CG to the new PM I outlined the various helper that were previously members of the CG class into free static functions. The CG class itself I moved into a header, which is required because we need to include it in RegisterPasses eventually.

[grosser]

LGTM

polly/trunk/include/polly/CodeGen/CodeGeneration.h

 //===------ polly/CodeGeneration.h - The Polly code generator *- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_CODEGENERATION_H
 #define POLLY_CODEGENERATION_H
 
 #include "polly/Config/config.h"
+#include "polly/ScopPass.h"
 #include "isl/map.h"
 #include "isl/set.h"
 
 namespace polly {
 enum VectorizerChoice {
   VECTORIZER_NONE,
   VECTORIZER_STRIPMINE,
   VECTORIZER_POLLY,
 };
 extern VectorizerChoice PollyVectorizerChoice;
+
+struct CodeGenerationPass : public PassInfoMixin<CodeGenerationPass> {
+  PreservedAnalyses run(Scop &S, ScopAnalysisManager &SAM,
+                        ScopStandardAnalysisResults &AR, SPMUpdater &U);
+};
 } // namespace polly
 
 #endif // POLLY_CODEGENERATION_H

polly/trunk/lib/CodeGen/CodeGeneration.cpp

 // Transformation passes can update the schedule (execution order) of statements
 // in the Scop. ISL is used to generate an abstract syntax tree that reflects
 // the updated execution order. This clast is used to create new LLVM-IR that is
 // computationally equivalent to the original control flow region, but executes
 // its code in the new execution order defined by the changed schedule.
 //
 //===----------------------------------------------------------------------===//
 
+#include "polly/CodeGen/CodeGeneration.h"
 #include "polly/CodeGen/IslAst.h"
 #include "polly/CodeGen/IslNodeBuilder.h"
 #include "polly/CodeGen/PerfMonitor.h"
 #include "polly/CodeGen/Utils.h"
 #include "polly/DependenceInfo.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/Options.h"
 #include "polly/ScopInfo.h"
 #include "polly/Support/ScopHelper.h"
 #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"
 
 using namespace polly;
 using namespace llvm;
 
 #define DEBUG_TYPE "polly-codegen"
 
 static cl::opt<bool> Verify("polly-codegen-verify",
                             cl::desc("Verify the function generated by Polly"),
                             cl::Hidden, cl::init(false), cl::ZeroOrMore,
                             cl::cat(PollyCategory));
 
 static cl::opt<bool>
     PerfMonitoring("polly-codegen-perf-monitoring",
                    cl::desc("Add run-time performance monitoring"), cl::Hidden,
                    cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
 
 namespace {
-class CodeGeneration : public ScopPass {
-public:
-  static char ID;
-
-  CodeGeneration() : ScopPass(ID) {}
-
-  /// The datalayout used
-  const DataLayout *DL;
-
-  /// @name The analysis passes we need to generate code.
-  ///
-  ///{
-  LoopInfo *LI;
-  IslAstInfo *AI;
-  DominatorTree *DT;
-  ScalarEvolution *SE;
-  RegionInfo *RI;
-  ///}
 
-  void verifyGeneratedFunction(Scop &S, Function &F) {
-    if (!Verify || !verifyFunction(F, &errs()))
-      return;
+static void verifyGeneratedFunction(Scop &S, Function &F, IslAstInfo &AI) {
 
-    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());
-    });
+    AI.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;
+static void fixRegionInfo(Function &F, Region &ParentRegion, RegionInfo &RI) {
+  for (BasicBlock &BB : F) {
+    if (RI.getRegionFor(&BB))
 
-      RI->setRegionFor(&BB, ParentRegion);
-    }
-  }
+    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();
-  }
+static void markBlockUnreachable(BasicBlock &Block, PollyIRBuilder &Builder) {
 
-  /// 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();
+static void removeLifetimeMarkers(Region *R) {
 
-      while (InstIt != InstEnd) {
-        auto NextIt = InstIt;
-        ++NextIt;
 
-        if (auto *IT = dyn_cast<IntrinsicInst>(&*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<IslAstInfoWrapperPass>().getAI();
-
-    // Check if we created an isl_ast root node, otherwise exit.
-    isl_ast_node *AstRoot = AI->getAst();
-    if (!AstRoot)
-      return false;
+static bool CodeGen(Scop &S, IslAstInfo &AI, LoopInfo &LI, DominatorTree &DT,
+                    ScalarEvolution &SE, RegionInfo &RI) {
+  isl_ast_node *AstRoot = AI.getAst();
 
-    LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
-    DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-    SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
-    DL = &S.getFunction().getParent()->getDataLayout();
-    RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
-    Region *R = &S.getRegion();
-    assert(!R->isTopLevelRegion() && "Top level regions are not supported");
+  auto &DL = S.getFunction().getParent()->getDataLayout();
 
-    ScopAnnotator Annotator;
-    Annotator.buildAliasScopes(S);
 
-    simplifyRegion(R, DT, LI, RI);
-    assert(R->isSimple());
-    BasicBlock *EnteringBB = S.getEnteringBlock();
-    assert(EnteringBB);
-    PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator);
+  simplifyRegion(R, &DT, &LI, &RI);
 
-    // 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();
+      executeScopConditionally(S, Builder.getTrue(), DT, RI, LI);
 
-    IslNodeBuilder NodeBuilder(Builder, Annotator, *DL, *LI, *SE, *DT, S,
-                               StartBlock);
+  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);
+    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());
+    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());
-    }
+    fixRegionInfo(*EnteringBB->getParent(), *R->getParent(), RI);
 
-    Function *F = EnteringBB->getParent();
-    verifyGeneratedFunction(S, *F);
-    for (auto *SubF : NodeBuilder.getParallelSubfunctions())
-      verifyGeneratedFunction(S, *SubF);
+  verifyGeneratedFunction(S, *F, AI);
+    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;
+
+  CodeGeneration() : ScopPass(ID) {}
+
+  /// The datalayout used
+  const DataLayout *DL;
+
+  /// @name The analysis passes we need to generate code.
+  ///
+  ///{
+  LoopInfo *LI;
+  IslAstInfo *AI;
+  DominatorTree *DT;
+  ScalarEvolution *SE;
+  RegionInfo *RI;
+  ///}
+
+  /// Generate LLVM-IR for the SCoP @p S.
+  bool runOnScop(Scop &S) override {
+    AI = &getAnalysis<IslAstInfoWrapperPass>().getAI();
+    LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+    DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+    SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
+    DL = &S.getFunction().getParent()->getDataLayout();
+    RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
+    return CodeGen(S, *AI, *LI, *DT, *SE, *RI);
+  }
+
   /// Register all analyses and transformation required.
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<IslAstInfoWrapperPass>();
     AU.addRequired<RegionInfoPass>();
     AU.addRequired<ScalarEvolutionWrapperPass>();
     AU.addRequired<ScopDetectionWrapperPass>();
     AU.addRequired<ScopInfoRegionPass>();
void getAnalysisUsage(AnalysisUsage &AU) const override {
     // FIXME: We do not yet add regions for the newly generated code to the
     //        region tree.
     AU.addPreserved<RegionInfoPass>();
     AU.addPreserved<ScopInfoRegionPass>();
   }
 };
 } // namespace
 
+PreservedAnalyses
+polly::CodeGenerationPass::run(Scop &S, ScopAnalysisManager &SAM,
+                               ScopStandardAnalysisResults &AR, SPMUpdater &U) {
+  auto &AI = SAM.getResult<IslAstAnalysis>(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(); }
 
 INITIALIZE_PASS_BEGIN(CodeGeneration, "polly-codegen",
                       "Polly - Create LLVM-IR from SCoPs", false, false);
 INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
 INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass);
 INITIALIZE_PASS_END(CodeGeneration, "polly-codegen",
                     "Polly - Create LLVM-IR from SCoPs", false, false)