Index: include/polly/LinkAllPasses.h =================================================================== --- include/polly/LinkAllPasses.h +++ include/polly/LinkAllPasses.h @@ -55,6 +55,7 @@ llvm::Pass *createIslScheduleOptimizerPass(); llvm::Pass *createFlattenSchedulePass(); llvm::Pass *createDeLICMPass(); +llvm::Pass *createMaximalStaticExpansionPass(); extern char &CodePreparationID; } // namespace polly @@ -88,6 +89,7 @@ polly::createPPCGCodeGenerationPass(); #endif polly::createIslScheduleOptimizerPass(); + polly::createMaximalStaticExpansionPass(); polly::createFlattenSchedulePass(); polly::createDeLICMPass(); polly::createDumpModulePass("", true); @@ -109,6 +111,7 @@ void initializePPCGCodeGenerationPass(llvm::PassRegistry &); #endif void initializeIslScheduleOptimizerPass(llvm::PassRegistry &); +void initializeMaximalStaticExpanderPass(llvm::PassRegistry &); void initializePollyCanonicalizePass(llvm::PassRegistry &); void initializeFlattenSchedulePass(llvm::PassRegistry &); void initializeDeLICMPass(llvm::PassRegistry &); Index: lib/Support/RegisterPasses.cpp =================================================================== --- lib/Support/RegisterPasses.cpp +++ lib/Support/RegisterPasses.cpp @@ -140,6 +140,11 @@ cl::desc("Import the polyhedral description of the detected Scops"), cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory)); +static cl::opt FullyIndexedStaticExpansion( + "polly-mse", + cl::desc("Fully expand the memory accesses of the detected Scops"), + cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory)); + static cl::opt ExportJScop( "polly-export", cl::desc("Export the polyhedral description of the detected Scops"), @@ -237,6 +242,7 @@ initializeDependenceInfoWrapperPassPass(Registry); initializeJSONExporterPass(Registry); initializeJSONImporterPass(Registry); + initializeMaximalStaticExpanderPass(Registry); initializeIslAstInfoWrapperPassPass(Registry); initializeIslScheduleOptimizerPass(Registry); initializePollyCanonicalizePass(Registry); @@ -310,6 +316,9 @@ if (ImportJScop) PM.add(polly::createJSONImporterPass()); + if (FullyIndexedStaticExpansion) + PM.add(polly::createMaximalStaticExpansionPass()); + if (DeadCodeElim) PM.add(polly::createDeadCodeElimPass()); Index: lib/Transform/MaximalStaticExpansion.cpp =================================================================== --- /dev/null +++ lib/Transform/MaximalStaticExpansion.cpp @@ -0,0 +1,120 @@ +//===- MaximalStaticExpansion.cpp - Expand the memory access -------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass fully expand the memory accesses of a Scop to get rid of +// dependencies. +//===----------------------------------------------------------------------===// + +#include "polly/DependenceInfo.h" +#include "polly/LinkAllPasses.h" +#include "polly/Options.h" +#include "polly/ScopInfo.h" +#include "polly/Support/GICHelper.h" +#include "polly/Support/ISLOStream.h" +#include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/Support/Debug.h" + +using namespace llvm; +using namespace polly; + +namespace { +class MaximalStaticExpander : public ScopPass { +public: + static char ID; + explicit MaximalStaticExpander() : ScopPass(ID) {} + + ~MaximalStaticExpander() {} + + /// Expand the scalar write of the SCoP @p S. + bool runOnScop(Scop &S) override; + + /// Print the new schedule for the SCoP @p S. + void printScop(raw_ostream &OS, Scop &S) const override; + + /// Register all analyses and transformation required. + void getAnalysisUsage(AnalysisUsage &AU) const override; +}; +} // namespace + +char MaximalStaticExpander::ID = 0; + +// For now, this pass is just expanding the write access of scalar. +// For instance, the folowing code : +// +// for(int i = 0; iisOriginalScalarKind() && MA->isWrite()) { + + // Get the new access map (AM) + isl_map *NewAccessMap = nullptr; // TODO + + // Get the current AM + isl_map *CurrentAccessMap = MA->getAccessRelation(); + + // Get the current AM out id + // Simple case because we only take care of scalar + ist_id *NewOutId = isl_map_get_tuple_id(CurrentAccessMap); + + // Set the out id of the new AM to the current AM out id + NewAccessMap = + isl_map_set_tuple_id(NewAccessMap, isl_dim_out, NewOutId); + + // Copy the isl_ids for the parameter dimensions to the new AM + for (unsigned i = 0; i < isl_map_dim(CurrentAccessMap, isl_dim_param); + i++) { + isl_id *Id = isl_map_get_dim_id(CurrentAccessMap, isl_dim_param, i); + NewAccessMap = isl_map_set_dim_id(NewAccessMap, isl_dim_param, i, Id); + } + + // Copy the old tuple id to the new AM + isl_id *Id = isl_map_get_tuple_id(CurrentAccessMap, isl_dim_in); + NewAccessMap = isl_map_set_tuple_id(NewAccessMap, isl_dim_in, Id); + + // Check if the two map are equals + // If yes it is useless to do something + if (!isl_map_is_equal(CurrentAccessMap, NewAccessMap)) { + MA->setNewAccessRelation(NewAccessMap); + isl_map_free(CurrentAccessMap); + } else { + isl_map_free(NewAccessMap); + } + } + } + } + errs() << "### END DEBUG MAXIMAL STATIC EXPANSION\n"; + return false; +} + +void MaximalStaticExpander::printScop(raw_ostream &OS, Scop &) const {} + +void MaximalStaticExpander::getAnalysisUsage(AnalysisUsage &AU) const { + ScopPass::getAnalysisUsage(AU); +} + +Pass *polly::createMaximalStaticExpansionPass() { + return new MaximalStaticExpander(); +} + +INITIALIZE_PASS_BEGIN(MaximalStaticExpander, "polly-opt-mse", + "Polly - Maximal static expansion of SCoP", false, false); +INITIALIZE_PASS_DEPENDENCY(DependenceInfo); +INITIALIZE_PASS_END(MaximalStaticExpander, "polly-opt-mse", + "Polly - Maximal static expansion of SCoP", false, false) Index: test/MaximalStaticExpansion/mse___%for.body---%for.end.jscop =================================================================== --- /dev/null +++ test/MaximalStaticExpansion/mse___%for.body---%for.end.jscop @@ -0,0 +1,64 @@ +{ + "arrays" : [ + { + "name" : "MemRef_A", + "sizes" : [ "*" ], + "type" : "double" + } + ], + "context" : "{ : }", + "name" : "%for.body---%for.end", + "statements" : [ + { + "accesses" : [ + { + "kind" : "write", + "relation" : "{ Stmt_for_body[i0] -> MemRef_tmp_07__phi[] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_body[i0] -> MemRef_tmp_07__phi[] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_body[i0] -> MemRef_A[8i0] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_body[i0] -> MemRef_A[1 + 8i0] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_body[i0] -> MemRef_A[2 + 8i0] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_body[i0] -> MemRef_A[3 + 8i0] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_body[i0] -> MemRef_A[4 + 8i0] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_body[i0] -> MemRef_A[5 + 8i0] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_body[i0] -> MemRef_A[6 + 8i0] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_body[i0] -> MemRef_A[7 + 8i0] }" + }, + { + "kind" : "write", + "relation" : "{ Stmt_for_body[i0] -> MemRef_mul_7[] }" + } + ], + "domain" : "{ Stmt_for_body[i0] : 0 <= i0 <= 249 }", + "name" : "Stmt_for_body", + "schedule" : "{ Stmt_for_body[i0] -> [i0] }" + } + ] +} Index: test/MaximalStaticExpansion/no_optim.ll =================================================================== --- /dev/null +++ test/MaximalStaticExpansion/no_optim.ll @@ -0,0 +1,42 @@ +; ModuleID = 'pure_c_main.c' +source_filename = "pure_c_main.c" +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +; Function Attrs: noinline nounwind optnone uwtable +define double @mse(double* %A) { +entry: + %A.addr = alloca double*, align 8 + %i = alloca i32, align 4 + %tmp = alloca double, align 8 + store double* %A, double** %A.addr, align 8 + store double 2.000000e+00, double* %tmp, align 8 + store i32 0, i32* %i, align 4 + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %0 = load i32, i32* %i, align 4 + %cmp = icmp slt i32 %0, 2000 + br i1 %cmp, label %for.body, label %for.end + +for.body: ; preds = %for.cond + %1 = load double*, double** %A.addr, align 8 + %2 = load i32, i32* %i, align 4 + %idxprom = sext i32 %2 to i64 + %arrayidx = getelementptr inbounds double, double* %1, i64 %idxprom + %3 = load double, double* %arrayidx, align 8 + %4 = load double, double* %tmp, align 8 + %mul = fmul double %3, %4 + store double %mul, double* %tmp, align 8 + br label %for.inc + +for.inc: ; preds = %for.body + %5 = load i32, i32* %i, align 4 + %inc = add nsw i32 %5, 1 + store i32 %inc, i32* %i, align 4 + br label %for.cond + +for.end: ; preds = %for.cond + %6 = load double, double* %tmp, align 8 + ret double %6 +}