[Polly] IR cleanup after CodeGeneration

[Meinersbur]

Summary

Re-run canonicalization passes after Polly's code generation.

The set of passes currently added here are nearly all the passes between --polly-position=early and --polly-position=before-vectorizer, i.e. all passes that would usually run after Polly.

In order to run these only if Polly actually modified the code, we add a function attribute "polly-optimzed" to a function that contains generated code. The cleanup pass is skipped if the function does have this attribute.

There is no support by the (legacy) PassManager to run passes only under some conditions. One could have wrapped all transformation passes to run only when CodeGeneration changed the code, but the analyses would run anyway. This patch creates an independent pass manager. The disadvantages are that all analyses have to re-run even if preserved and it does not honor compiler switches like the PassManagerBuilder does.

[Meinersbur]

test/ScopInfo/new-domain-construction-schedule-not-freed.ll

6 ↗

(On Diff #39206)

The scop is sometimes removed completely because it has no side effects. This should not be specific to this patch, but occurred occasionally when testing it.

[grosser]

Hi Michael,

sorry for the delay. This patch is clearly needed. The approach looks generally fine, but I am slightly concerned about the introduction of a RememberCodegenPass, as pass manager "abuses" are often fragile and I am not 100% convinced this will work with the new pass manager. Instead of trying to figure out if/how to make this work, I would propose to just pass the "is-modified" information as function level metadata or a named function attribute.

Best,
Tobias

test/ScopInfo/new-domain-construction-schedule-not-freed.ll

6 ↗

(On Diff #39206)

I am confused. Why does a change in the pass manager pipeline affect this test case. The pass manager is not even involved here, no?

[Meinersbur]

Instead of a RememberCodegen pass, use a "polly-optimized" function attribute.

[Meinersbur]

Remove bogus pass dependency

[grosser]

Hi Michael,

this LGFM.

Tobias

include/polly/CodeGen/CodegenCleanup.h

+#ifndef POLLY_CODEGENCLEANUP_H
+#define POLLY_CODEGENCLEANUP_H
+
+namespace llvm {
+class FunctionPass;
+class PassRegistry;
+}
+
+namespace polly {
+llvm::FunctionPass *createCodegenCleanupPass();
+}
+
+namespace llvm {
+void initializeCodegenCleanupPass(llvm::PassRegistry &);
+}
+
+#endif

lib/CMakeLists.txt

add_polly_library(Polly
   Analysis/ScopGraphPrinter.cpp
   Analysis/ScopPass.cpp
   CodeGen/BlockGenerators.cpp
   ${ISL_CODEGEN_FILES}
   CodeGen/LoopGenerators.cpp
   CodeGen/IRBuilder.cpp
   CodeGen/Utils.cpp
   CodeGen/RuntimeDebugBuilder.cpp
+  CodeGen/CodegenCleanup.cpp
   ${GPGPU_CODEGEN_FILES}
   Exchange/JSONExporter.cpp
   Support/GICHelper.cpp
   Support/SCEVAffinator.cpp
   Support/SCEVValidator.cpp
   Support/RegisterPasses.cpp
   Support/ScopHelper.cpp
   Support/ScopLocation.cpp

lib/CodeGen/CodeGeneration.cpp

if (!NodeBuilder.preloadInvariantLoads()) {
       NodeBuilder.create(AstRoot);
 
       NodeBuilder.finalizeSCoP(S);
       fixRegionInfo(EnteringBB->getParent(), R->getParent());
     }
 
     assert(!verifyGeneratedFunction(S, *EnteringBB->getParent()) &&
            "Verification of generated function failed");
+
+    // Mark the function such that we run additional cleanup passes on this
+    // function (e.g. mem2reg to rediscover phi nodes).
+    Function *F = EnteringBB->getParent();
+    F->addFnAttr("polly-optimized");
+
     return true;
   }
 
   /// @brief Register all analyses and transformation required.
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<IslAstInfo>();
     AU.addRequired<RegionInfoPass>();

lib/CodeGen/CodegenCleanup.cpp

+#include "polly/CodeGen/CodegenCleanup.h"
+
+#include "llvm/Analysis/CFLAliasAnalysis.h"
+#include "llvm/Analysis/ScopedNoAliasAA.h"
+#include "llvm/Analysis/TypeBasedAliasAnalysis.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/LegacyPassManager.h"
+#include "llvm/PassInfo.h"
+#include "llvm/PassRegistry.h"
+#include "llvm/PassSupport.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Transforms/Scalar.h"
+#define DEBUG_TYPE "polly-cleanup"
+
+using namespace llvm;
+using namespace polly;
+
+namespace {
+
+class CodegenCleanup : public FunctionPass {
+private:
+  CodegenCleanup(const CodegenCleanup &) = delete;
+  const CodegenCleanup &operator=(const CodegenCleanup &) = delete;
+
+  llvm::legacy::FunctionPassManager *FPM;
+
+public:
+  static char ID;
+  explicit CodegenCleanup() : FunctionPass(ID), FPM(nullptr) {}
+
+  /// @name FunctionPass interface
+  //@{
+  virtual void getAnalysisUsage(llvm::AnalysisUsage &AU) const override {}
+
+  virtual bool doInitialization(Module &M) override {
+    assert(!FPM);
+
+    FPM = new llvm::legacy::FunctionPassManager(&M);
+
+    // TODO: How to make parent passes discoverable?
+    // TODO: Should be sensitive to compiler options in PassManagerBuilder, to
+    // which wo do not have access here.
+    FPM->add(createCFLAAWrapperPass());
+    FPM->add(createScopedNoAliasAAWrapperPass());
+    FPM->add(createTypeBasedAAWrapperPass());
+    FPM->add(createAAResultsWrapperPass());
+
+    // TODO: These are non-conditional passes that run between
+    // EP_ModuleOptimizerEarly and EP_VectorizerStart just to ensure we do not
+    // miss any optimization that would have run after Polly with
+    // -polly-position=early. This can probably be reduced to a more compact set
+    // of passes.
+    FPM->add(createCFGSimplificationPass());
+    FPM->add(createScalarReplAggregatesPass());
+    FPM->add(createEarlyCSEPass());
+    FPM->add(createInstructionCombiningPass());
+    FPM->add(createJumpThreadingPass());
+    FPM->add(createCorrelatedValuePropagationPass());
+    FPM->add(createCFGSimplificationPass());
+    FPM->add(createInstructionCombiningPass());
+    FPM->add(createCFGSimplificationPass());
+    FPM->add(createReassociatePass());
+    FPM->add(createLoopRotatePass());
+    FPM->add(createLICMPass());
+    FPM->add(createLoopUnswitchPass());
+    FPM->add(createCFGSimplificationPass());
+    FPM->add(createInstructionCombiningPass());
+    FPM->add(createIndVarSimplifyPass());
+    FPM->add(createLoopIdiomPass());
+    FPM->add(createLoopDeletionPass());
+    FPM->add(createLoopInterchangePass());
+    FPM->add(createCFGSimplificationPass());
+    FPM->add(createSimpleLoopUnrollPass());
+    FPM->add(createMergedLoadStoreMotionPass());
+    FPM->add(createMemCpyOptPass());
+    FPM->add(createBitTrackingDCEPass());
+    FPM->add(createInstructionCombiningPass());
+    FPM->add(createJumpThreadingPass());
+    FPM->add(createCorrelatedValuePropagationPass());
+    FPM->add(createDeadStoreEliminationPass());
+    FPM->add(createLICMPass());
+    FPM->add(createLoopRerollPass());
+    FPM->add(createLoadCombinePass());
+    FPM->add(createAggressiveDCEPass());
+    FPM->add(createCFGSimplificationPass());
+    FPM->add(createInstructionCombiningPass());
+
+    return FPM->doInitialization();
+  }
+
+  virtual bool doFinalization(Module &M) override {
+    bool Result = FPM->doFinalization();
+
+    delete FPM;
+    FPM = nullptr;
+
+    return Result;
+  }
+
+  virtual bool runOnFunction(llvm::Function &F) override {
+    if (!F.hasFnAttribute("polly-optimized")) {
+      DEBUG(dbgs() << F.getName()
+                   << ": Skipping cleanup because Polly did not optimize it.");
+      return false;
+    }
+
+    DEBUG(dbgs() << F.getName() << ": Running codegen cleanup...");
+    return FPM->run(F);
+  }
+  //@}
+};
+
+char CodegenCleanup::ID;
+}
+
+FunctionPass *polly::createCodegenCleanupPass() { return new CodegenCleanup(); }
+
+INITIALIZE_PASS_BEGIN(CodegenCleanup, "polly-cleanup",
+                      "Polly - Cleanup after code generation", false, false)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+INITIALIZE_PASS_END(CodegenCleanup, "polly-cleanup",
+                    "Polly - Cleanup after code generation", false, false)

lib/Support/RegisterPasses.cpp

 // passes are registered such that the default behaviour of the compiler is not
 // changed, but that the flag '-polly' provided at optimization level '-O3'
 // enables additional polyhedral optimizations.
 //===----------------------------------------------------------------------===//
 
 #include "polly/RegisterPasses.h"
 #include "polly/Canonicalization.h"
 #include "polly/CodeGen/CodeGeneration.h"
+#include "polly/CodeGen/CodegenCleanup.h"
 #include "polly/DependenceInfo.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/Options.h"
 #include "polly/ScopDetection.h"
 #include "polly/ScopInfo.h"
 #include "llvm/Analysis/CFGPrinter.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
void initializePollyPasses(PassRegistry &Registry) {
   initializeDependenceInfoPass(Registry);
   initializeJSONExporterPass(Registry);
   initializeJSONImporterPass(Registry);
   initializeIslAstInfoPass(Registry);
   initializeIslScheduleOptimizerPass(Registry);
   initializePollyCanonicalizePass(Registry);
   initializeScopDetectionPass(Registry);
   initializeScopInfoPass(Registry);
+  initializeCodegenCleanupPass(Registry);
 }
 
 /// @brief Register Polly passes such that they form a polyhedral optimizer.
 ///
 /// The individual Polly passes are registered in the pass manager such that
 /// they form a full polyhedral optimizer. The flow of the optimizer starts with
 /// a set of preparing transformations that canonicalize the LLVM-IR such that
 /// the LLVM-IR is easier for us to understand and to optimizes. On the
registerPollyLoopOptimizerEndPasses(const llvm::PassManagerBuilder &Builder,
   if (!polly::shouldEnablePolly())
     return;
 
   if (PassPosition != POSITION_AFTER_LOOPOPT)
     return;
 
   PM.add(polly::createCodePreparationPass());
   polly::registerPollyPasses(PM);
-  // TODO: Add some cleanup passes
+  PM.add(createCodegenCleanupPass());
 }
 
 static void
 registerPollyScalarOptimizerLatePasses(const llvm::PassManagerBuilder &Builder,
                                        llvm::legacy::PassManagerBase &PM) {
   if (!polly::shouldEnablePolly())
     return;
 
   if (PassPosition != POSITION_BEFORE_VECTORIZER)
     return;
 
   PM.add(polly::createCodePreparationPass());
   polly::registerPollyPasses(PM);
-  // TODO: Add some cleanup passes
+  PM.add(createCodegenCleanupPass());
 }
 
 /// @brief Register Polly to be available as an optimizer
 ///
 ///
 /// We can currently run Polly at three different points int the pass manager.
 /// a) very early, b) after the canonicalizing loop transformations and c) right
 /// before the vectorizer.