Index: include/polly/CodeGen/IslExprBuilder.h =================================================================== --- include/polly/CodeGen/IslExprBuilder.h +++ include/polly/CodeGen/IslExprBuilder.h @@ -17,7 +17,8 @@ #include "isl/ast.h" namespace llvm { -class SCEVExpander; +class DataLayout; +class ScalarEvolution; } namespace polly { @@ -93,10 +94,10 @@ /// parameters and variables. /// @param Expander A SCEVExpander to create the indices for multi /// dimensional accesses. - IslExprBuilder(PollyIRBuilder &Builder, IDToValueTy &IDToValue, - llvm::SCEVExpander &Expander, llvm::DominatorTree &DT, - llvm::LoopInfo &LI) - : Builder(Builder), IDToValue(IDToValue), Expander(Expander), DT(DT), + IslExprBuilder(Scop &S, PollyIRBuilder &Builder, IDToValueTy &IDToValue, + const llvm::DataLayout &DL, llvm::ScalarEvolution &SE, + llvm::DominatorTree &DT, llvm::LoopInfo &LI) + : S(S), Builder(Builder), IDToValue(IDToValue), DL(DL), SE(SE), DT(DT), LI(LI) {} /// @brief Create LLVM-IR for an isl_ast_expr[ession]. @@ -124,12 +125,13 @@ llvm::IntegerType *getType(__isl_keep isl_ast_expr *Expr); private: + Scop &S; + PollyIRBuilder &Builder; IDToValueTy &IDToValue; - /// @brief A SCEVExpander to translate dimension sizes to llvm values. - llvm::SCEVExpander &Expander; - + const llvm::DataLayout &DL; + llvm::ScalarEvolution &SE; llvm::DominatorTree &DT; llvm::LoopInfo &LI; Index: include/polly/CodeGen/IslNodeBuilder.h =================================================================== --- include/polly/CodeGen/IslNodeBuilder.h +++ include/polly/CodeGen/IslNodeBuilder.h @@ -16,7 +16,6 @@ #include "polly/CodeGen/BlockGenerators.h" #include "polly/CodeGen/IslExprBuilder.h" #include "polly/CodeGen/LoopGenerators.h" -#include "llvm/Analysis/ScalarEvolutionExpander.h" #include "isl/ctx.h" #include "isl/union_map.h" @@ -30,8 +29,8 @@ IslNodeBuilder(PollyIRBuilder &Builder, ScopAnnotator &Annotator, Pass *P, const DataLayout &DL, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, Scop &S) - : S(S), Builder(Builder), Annotator(Annotator), Rewriter(SE, DL, "polly"), - ExprBuilder(Builder, IDToValue, Rewriter, DT, LI), + : S(S), Builder(Builder), Annotator(Annotator), + ExprBuilder(S, Builder, IDToValue, DL, SE, DT, LI), BlockGen(Builder, LI, SE, DT, ScalarMap, PHIOpMap, EscapeMap, &ExprBuilder), RegionGen(BlockGen), P(P), DL(DL), LI(LI), SE(SE), DT(DT) {} @@ -53,9 +52,6 @@ PollyIRBuilder &Builder; ScopAnnotator &Annotator; - /// @brief A SCEVExpander to create llvm values from SCEVs. - SCEVExpander Rewriter; - IslExprBuilder ExprBuilder; /// @brief Maps used by the block and region generator to demote scalars. Index: include/polly/Support/ScopHelper.h =================================================================== --- include/polly/Support/ScopHelper.h +++ include/polly/Support/ScopHelper.h @@ -27,6 +27,7 @@ class Pass; class BasicBlock; class StringRef; +class DataLayout; class DominatorTree; class RegionInfo; class ScalarEvolution; @@ -77,5 +78,11 @@ /// @param P The pass that currently running. /// void splitEntryBlockForAlloca(llvm::BasicBlock *EntryBlock, llvm::Pass *P); + +/// @brief TODO +llvm::Value *expandCodeFor(Scop &S, llvm::ScalarEvolution &SE, + const llvm::DataLayout &DL, const char *Name, + const llvm::SCEV *E, llvm::Type *Ty, + llvm::Instruction *IP); } #endif Index: lib/CodeGen/BlockGenerators.cpp =================================================================== --- lib/CodeGen/BlockGenerators.cpp +++ lib/CodeGen/BlockGenerators.cpp @@ -24,7 +24,6 @@ #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/RegionInfo.h" #include "llvm/Analysis/ScalarEvolution.h" -#include "llvm/Analysis/ScalarEvolutionExpander.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Module.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" @@ -116,17 +115,16 @@ VTV.insert(BBMap.begin(), BBMap.end()); VTV.insert(GlobalMap.begin(), GlobalMap.end()); NewScev = SCEVParameterRewriter::rewrite(NewScev, SE, VTV); - SCEVExpander Expander(SE, Stmt.getParent() - ->getRegion() - .getEntry() - ->getParent() - ->getParent() - ->getDataLayout(), - "polly"); - assert(Builder.GetInsertPoint() != Builder.GetInsertBlock()->end() && + + Scop &S = *Stmt.getParent(); + const DataLayout &DL = + S.getRegion().getEntry()->getParent()->getParent()->getDataLayout(); + auto IP = Builder.GetInsertPoint(); + + assert(IP != Builder.GetInsertBlock()->end() && "Only instructions can be insert points for SCEVExpander"); - Value *Expanded = Expander.expandCodeFor(NewScev, Old->getType(), - Builder.GetInsertPoint()); + Value *Expanded = + expandCodeFor(S, SE, DL, "polly", NewScev, Old->getType(), IP); BBMap[Old] = Expanded; return Expanded; @@ -376,6 +374,8 @@ void BlockGenerator::handleOutsideUsers(const Region &R, Instruction *Inst, Value *InstCopy) { + BasicBlock *EnteringBB = R.getEnteringBlock(); + EscapeUserVectorTy EscapeUsers; for (User *U : Inst->users()) { @@ -384,7 +384,7 @@ if (!UI) continue; - if (R.contains(UI)) + if (R.contains(UI) || EnteringBB == UI->getParent()) continue; EscapeUsers.push_back(UI); Index: lib/CodeGen/IslExprBuilder.cpp =================================================================== --- lib/CodeGen/IslExprBuilder.cpp +++ lib/CodeGen/IslExprBuilder.cpp @@ -12,7 +12,7 @@ #include "polly/CodeGen/IslExprBuilder.h" #include "polly/ScopInfo.h" #include "polly/Support/GICHelper.h" -#include "llvm/Analysis/ScalarEvolutionExpander.h" +#include "polly/Support/ScopHelper.h" #include "llvm/Support/Debug.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" @@ -148,8 +148,9 @@ break; const SCEV *DimSCEV = SAI->getDimensionSize(u - 1); - Value *DimSize = Expander.expandCodeFor(DimSCEV, DimSCEV->getType(), - Builder.GetInsertPoint()); + Value *DimSize = + expandCodeFor(S, SE, DL, "polly", DimSCEV, DimSCEV->getType(), + Builder.GetInsertPoint()); Type *Ty = getWidestType(DimSize->getType(), IndexOp->getType()); Index: lib/CodeGen/IslNodeBuilder.cpp =================================================================== --- lib/CodeGen/IslNodeBuilder.cpp +++ lib/CodeGen/IslNodeBuilder.cpp @@ -31,7 +31,6 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/PostDominators.h" -#include "llvm/Analysis/ScalarEvolutionExpander.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Module.h" #include "llvm/IR/Verifier.h" @@ -742,5 +741,6 @@ Value *IslNodeBuilder::generateSCEV(const SCEV *Expr) { Instruction *InsertLocation = --(Builder.GetInsertBlock()->end()); - return Rewriter.expandCodeFor(Expr, Expr->getType(), InsertLocation); + return expandCodeFor(S, SE, DL, "polly", Expr, Expr->getType(), + InsertLocation); } Index: lib/Support/ScopHelper.cpp =================================================================== --- lib/Support/ScopHelper.cpp +++ lib/Support/ScopHelper.cpp @@ -17,12 +17,14 @@ #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/RegionInfo.h" #include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/ScalarEvolutionExpander.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/IR/CFG.h" #include "llvm/Support/Debug.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" using namespace llvm; +using namespace polly; #define DEBUG_TYPE "polly-scop-helper" @@ -252,3 +254,99 @@ // splitBlock updates DT, LI and RI. splitBlock(EntryBlock, I, DT, LI, RI); } + +struct ScopExpander : SCEVVisitor { + friend struct SCEVVisitor; + + explicit ScopExpander(Scop &S, ScalarEvolution &SE, const DataLayout &DL, + const char *Name) + : Expander(SCEVExpander(SE, DL, Name)), SE(SE), S(S) {} + + Value *expandCodeFor(const SCEV *E, Type *Ty, Instruction *I) { + E = visit(E); + return Expander.expandCodeFor(E, Ty, I); + } + +private: + Instruction *StartIP; + SCEVExpander Expander; + ScalarEvolution &SE; + Scop &S; + + void setStartIP() { + StartIP = S.getRegion().getEnteringBlock()->getTerminator(); + } + + const SCEV *visitUnknown(const SCEVUnknown *E) { + Instruction *Inst = dyn_cast(E->getValue()); + if (!Inst || (Inst->getOpcode() != Instruction::SRem && + Inst->getOpcode() != Instruction::SDiv)) + return E; + + if (StartIP) + setStartIP(); + + const SCEV *LHSScev = visit(SE.getSCEV(Inst->getOperand(0))); + const SCEV *RHSScev = visit(SE.getSCEV(Inst->getOperand(1))); + + Value *LHS = Expander.expandCodeFor(LHSScev, E->getType(), StartIP); + Value *RHS = Expander.expandCodeFor(RHSScev, E->getType(), StartIP); + + Inst = + BinaryOperator::Create((Instruction::BinaryOps)Inst->getOpcode(), LHS, + RHS, Inst->getName() + ".polly.copy", StartIP); + return SE.getSCEV(Inst); + } + + const SCEV *visitConstant(const SCEVConstant *E) { return E; } + const SCEV *visitTruncateExpr(const SCEVTruncateExpr *E) { + return SE.getTruncateExpr(visit(E->getOperand()), E->getType()); + } + const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *E) { + return SE.getZeroExtendExpr(visit(E->getOperand()), E->getType()); + } + const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *E) { + return SE.getSignExtendExpr(visit(E->getOperand()), E->getType()); + } + const SCEV *visitUDivExpr(const SCEVUDivExpr *E) { + return SE.getUDivExpr(visit(E->getLHS()), visit(E->getRHS())); + } + const SCEV *visitAddExpr(const SCEVAddExpr *E) { + SmallVector NewOps; + for (const SCEV *Op : E->operands()) + NewOps.push_back(visit(Op)); + return SE.getAddExpr(NewOps); + } + const SCEV *visitMulExpr(const SCEVMulExpr *E) { + SmallVector NewOps; + for (const SCEV *Op : E->operands()) + NewOps.push_back(visit(Op)); + return SE.getMulExpr(NewOps); + } + const SCEV *visitUMaxExpr(const SCEVUMaxExpr *E) { + SmallVector NewOps; + for (const SCEV *Op : E->operands()) + NewOps.push_back(visit(Op)); + return SE.getUMaxExpr(NewOps); + } + const SCEV *visitSMaxExpr(const SCEVSMaxExpr *E) { + SmallVector NewOps; + for (const SCEV *Op : E->operands()) + NewOps.push_back(visit(Op)); + return SE.getSMaxExpr(NewOps); + } + const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) { + SmallVector NewOps; + for (const SCEV *Op : E->operands()) + NewOps.push_back(visit(Op)); + return SE.getAddRecExpr(NewOps, E->getLoop(), E->getNoWrapFlags()); + } +}; + +Value *polly::expandCodeFor(Scop &S, ScalarEvolution &SE, const DataLayout &DL, + const char *Name, const SCEV *E, Type *Ty, + Instruction *IP) { + errs() << "Expand: " << *E << "\n"; + ScopExpander Expander(S, SE, DL, Name); + return Expander.expandCodeFor(E, Ty, IP); +} Index: test/Isl/CodeGen/inner_scev.ll =================================================================== --- test/Isl/CodeGen/inner_scev.ll +++ test/Isl/CodeGen/inner_scev.ll @@ -8,7 +8,8 @@ ; computation of the SCEV to before the scop that references %div44, which is ; not available then. ; -; XFAIL: * +; CHECK: polly.split_new_and_old: +; CHECK-NEXT: %div23.neg.polly.copy = sdiv i64 0, -4 ; target triple = "x86_64-unknown-linux-gnu" Index: test/Isl/CodeGen/inner_scev_2.ll =================================================================== --- test/Isl/CodeGen/inner_scev_2.ll +++ test/Isl/CodeGen/inner_scev_2.ll @@ -1,11 +1,15 @@ ; RUN: opt %loadPolly -S -polly-no-early-exit -polly-detect-unprofitable -polly-codegen < %s | FileCheck %s -; XFAIL: * ; ; The SCEV expression in this test case refers to a sequence of sdiv ; instructions, which are part of different bbs in the SCoP. When code ; generating the parameter expressions, the code that is generated by the SCEV ; expander has still references to the in-scop instructions, which is invalid. - +; +; CHECK: polly.split_new_and_old: +; CHECK: %div23.neg.polly.copy = sdiv i64 0, -4 +; CHECK: %div43.polly.copy = sdiv i64 %param, 2 +; CHECK: %div44.polly.copy = sdiv i64 %div43.polly.copy, 2 +; target triple = "x86_64-unknown-linux-gnu" define void @_vorbis_apply_window(float* %d, i64 %param) {