From a9376ff571e8dfcd97f909497d929e119ef16787 Mon Sep 17 00:00:00 2001 From: Tobias Grosser Date: Thu, 2 Jan 2014 23:39:18 +0000 Subject: [PATCH] Introduce -polly-canonicalize pass This ModulePass schedules the set of Polly canonicalization passes. It is a debugging tool that can be used to preoptimize .ll files for Polly processing. llvm-svn: 198376 --- polly/include/polly/Canonicalization.h | 30 ++++++++++++ polly/include/polly/LinkAllPasses.h | 3 ++ polly/lib/CMakeLists.txt | 1 + polly/lib/Canonicalization.cpp | 86 ++++++++++++++++++++++++++++++++++ polly/lib/RegisterPasses.cpp | 27 ++--------- polly/www/example_manual_matmul.html | 8 ++-- polly/www/experiments/matmul/runall.sh | 2 +- 7 files changed, 127 insertions(+), 30 deletions(-) create mode 100755 polly/include/polly/Canonicalization.h create mode 100644 polly/lib/Canonicalization.cpp diff --git a/polly/include/polly/Canonicalization.h b/polly/include/polly/Canonicalization.h new file mode 100755 index 0000000..146fa37 --- /dev/null +++ b/polly/include/polly/Canonicalization.h @@ -0,0 +1,30 @@ +//===--- Canonicalization.h - The set of canonicalization passes------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef POLLY_CANONICALIZATION_H +#define POLLY_CANONICALIZATION_H + +#include "llvm/PassManager.h" + +namespace polly { + +/// @brief Schedule a set of canonicalization passes to prepare for Polly +/// +/// The set of optimization passes was partially taken/copied from the +/// set of default optimization passes in LLVM. It is used to bring the code +/// into a canonical form that simplifies the analysis and optimization passes +/// of Polly. The set of optimization passes scheduled here is probably not yet +/// optimal. TODO: Optimize the set of canonicalization passes. +void registerCanonicalicationPasses(llvm::PassManagerBase &PM, + bool SCEVCodegen = false); + +} + + +#endif diff --git a/polly/include/polly/LinkAllPasses.h b/polly/include/polly/LinkAllPasses.h index aa4510a..67d559e 100644 --- a/polly/include/polly/LinkAllPasses.h +++ b/polly/include/polly/LinkAllPasses.h @@ -45,6 +45,7 @@ llvm::Pass *createJSONImporterPass(); #ifdef PLUTO_FOUND llvm::Pass *createPlutoOptimizerPass(); #endif +llvm::Pass *createPollyCanonicalizePass(); llvm::Pass *createScopDetectionPass(); llvm::Pass *createScopInfoPass(); llvm::Pass *createIslAstInfoPass(); @@ -100,6 +101,7 @@ struct PollyForcePassLinking { #ifdef PLUTO_FOUND createPlutoOptimizerPass(); #endif + createPollyCanonicalizePass(); createIslAstInfoPass(); createIslCodeGenerationPass(); createIslScheduleOptimizerPass(); @@ -134,6 +136,7 @@ void initializeIslScheduleOptimizerPass(llvm::PassRegistry &); #ifdef PLUTO_FOUND void initializePlutoOptimizerPass(llvm::PassRegistry &); #endif +void initializePollyCanonicalizePass(llvm::PassRegistry &); #ifdef SCOPLIB_FOUND void initializePoccPass(llvm::PassRegistry &); #endif diff --git a/polly/lib/CMakeLists.txt b/polly/lib/CMakeLists.txt index d82b0ce..dba1b85 100644 --- a/polly/lib/CMakeLists.txt +++ b/polly/lib/CMakeLists.txt @@ -24,6 +24,7 @@ set(LLVM_USED_LIBS ) add_polly_loadable_module(LLVMPolly + Canonicalization.cpp CodePreparation.cpp DeadCodeElimination.cpp IndependentBlocks.cpp diff --git a/polly/lib/Canonicalization.cpp b/polly/lib/Canonicalization.cpp new file mode 100644 index 0000000..d6ce12f --- /dev/null +++ b/polly/lib/Canonicalization.cpp @@ -0,0 +1,86 @@ +//===---- Canonicalization.cpp - Run canonicalization passes ======-------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Run the set of default canonicalization passes. +// +// This pass is mainly used for debugging. +// +//===----------------------------------------------------------------------===// + +#include "polly/LinkAllPasses.h" +#include "polly/Canonicalization.h" +#include "llvm/Transforms/Scalar.h" + +using namespace llvm; +using namespace polly; + +void polly::registerCanonicalicationPasses(llvm::PassManagerBase &PM, + bool SCEVCodegen) { + PM.add(llvm::createPromoteMemoryToRegisterPass()); + PM.add(llvm::createPromoteMemoryToRegisterPass()); + PM.add(llvm::createInstructionCombiningPass()); + PM.add(llvm::createCFGSimplificationPass()); + PM.add(llvm::createTailCallEliminationPass()); + PM.add(llvm::createCFGSimplificationPass()); + PM.add(llvm::createReassociatePass()); + PM.add(llvm::createLoopRotatePass()); + PM.add(llvm::createInstructionCombiningPass()); + + if (!SCEVCodegen) + PM.add(polly::createIndVarSimplifyPass()); + + PM.add(polly::createCodePreparationPass()); +} + +namespace { +class PollyCanonicalize : public ModulePass { + PollyCanonicalize(const PollyCanonicalize &) LLVM_DELETED_FUNCTION; + const PollyCanonicalize & + operator=(const PollyCanonicalize &) LLVM_DELETED_FUNCTION; + +public: + static char ID; + + explicit PollyCanonicalize() : ModulePass(ID) {} + ~PollyCanonicalize(); + + /// @name FunctionPass interface. + //@{ + virtual void getAnalysisUsage(AnalysisUsage &AU) const; + virtual void releaseMemory(); + virtual bool runOnModule(Module &M); + virtual void print(raw_ostream &OS, const Module *) const; + //@} +}; +} + +PollyCanonicalize::~PollyCanonicalize() {} + +void PollyCanonicalize::getAnalysisUsage(AnalysisUsage &AU) const {} + +void PollyCanonicalize::releaseMemory() {} + +bool PollyCanonicalize::runOnModule(Module &M) { + PassManager PM; + registerCanonicalicationPasses(PM); + PM.run(M); + + return true; +} + +void PollyCanonicalize::print(raw_ostream &OS, const Module *) const {} + +char PollyCanonicalize::ID = 0; + +Pass *polly::createPollyCanonicalizePass() { return new PollyCanonicalize(); } + +INITIALIZE_PASS_BEGIN(PollyCanonicalize, "polly-canonicalize", + "Polly - Run canonicalization passes", false, false) +INITIALIZE_PASS_END(PollyCanonicalize, "polly-canonicalize", + "Polly - Run canonicalization passes", false, false) diff --git a/polly/lib/RegisterPasses.cpp b/polly/lib/RegisterPasses.cpp index 03dca9c..5fd1960 100644 --- a/polly/lib/RegisterPasses.cpp +++ b/polly/lib/RegisterPasses.cpp @@ -20,6 +20,7 @@ //===----------------------------------------------------------------------===// #include "polly/RegisterPasses.h" +#include "polly/Canonicalization.h" #include "polly/CodeGen/BlockGenerators.h" #include "polly/CodeGen/Cloog.h" #include "polly/CodeGen/CodeGeneration.h" @@ -172,6 +173,7 @@ static void initializePollyPasses(PassRegistry &Registry) { initializePoccPass(Registry); #endif initializePollyIndVarSimplifyPass(Registry); + initializePollyCanonicalizePass(Registry); initializeScopDetectionPass(Registry); initializeScopInfoPass(Registry); initializeTempScopInfoPass(Registry); @@ -191,29 +193,6 @@ public: }; static StaticInitializer InitializeEverything; -/// @brief Schedule a set of canonicalization passes to prepare for Polly -/// -/// The set of optimization passes was partially taken/copied from the -/// set of default optimization passes in LLVM. It is used to bring the code -/// into a canonical form that simplifies the analysis and optimization passes -/// of Polly. The set of optimization passes scheduled here is probably not yet -/// optimal. TODO: Optimize the set of canonicalization passes. -static void registerCanonicalicationPasses(llvm::PassManagerBase &PM) { - PM.add(llvm::createPromoteMemoryToRegisterPass()); - PM.add(llvm::createInstructionCombiningPass()); - PM.add(llvm::createCFGSimplificationPass()); - PM.add(llvm::createTailCallEliminationPass()); - PM.add(llvm::createCFGSimplificationPass()); - PM.add(llvm::createReassociatePass()); - PM.add(llvm::createLoopRotatePass()); - PM.add(llvm::createInstructionCombiningPass()); - - if (!SCEVCodegen) - PM.add(polly::createIndVarSimplifyPass()); - - PM.add(polly::createCodePreparationPass()); -} - /// @brief Register Polly passes such that they form a polyhedral optimizer. /// /// The individual Polly passes are registered in the pass manager such that @@ -245,7 +224,7 @@ static void registerCanonicalicationPasses(llvm::PassManagerBase &PM) { /// code generator. For the moment, the CLooG code generator is enabled by /// default. static void registerPollyPasses(llvm::PassManagerBase &PM) { - registerCanonicalicationPasses(PM); + registerCanonicalicationPasses(PM, SCEVCodegen); PM.add(polly::createScopInfoPass()); diff --git a/polly/www/example_manual_matmul.html b/polly/www/example_manual_matmul.html index 9c9593a..1c3b6b4 100644 --- a/polly/www/example_manual_matmul.html +++ b/polly/www/example_manual_matmul.html @@ -54,11 +54,9 @@ alias opt="opt -load ${PATH_TO_POLLY_LIB}/LLVMPolly.so"

  • Prepare the LLVM-IR for Polly

    Polly is only able to work with code that matches a canonical form. To translate -the LLVM-IR into this form we use a set of canonicalication passes. For this -example only three passes are necessary. To get good coverage on more -complicated input files often more canonicalization passes are needed. pollycc -contains a list of passes that have shown to be beneficial. -
    opt -S -mem2reg -loop-simplify -polly-indvars matmul.s > matmul.preopt.ll
    • +the LLVM-IR into this form we use a set of canonicalication passes. They are +scheduled by using '-polly-canonicalize'. +
    opt -S -polly-canonicalize matmul.s > matmul.preopt.ll

  • Show the SCoPs detected by Polly (optional)

    diff --git a/polly/www/experiments/matmul/runall.sh b/polly/www/experiments/matmul/runall.sh index 6609d56..a8db82e 100755 --- a/polly/www/experiments/matmul/runall.sh +++ b/polly/www/experiments/matmul/runall.sh @@ -8,7 +8,7 @@ export PATH_TO_POLLY_LIB="~/polly/build/lib/" alias opt="opt -load ${PATH_TO_POLLY_LIB}/LLVMPolly.so" echo "--> 3. Prepare the LLVM-IR for Polly" -opt -S -mem2reg -loop-simplify -polly-indvars matmul.s > matmul.preopt.ll +opt -S -polly-canonicalize matmul.s > matmul.preopt.ll echo "--> 4. Show the SCoPs detected by Polly" opt -basicaa -polly-cloog -analyze -q matmul.preopt.ll -- 2.7.4