From 6213913244e0e6df307830ee7c7d6144ca2a258e Mon Sep 17 00:00:00 2001 From: Tobias Grosser Date: Sun, 2 Aug 2015 16:17:41 +0000 Subject: [PATCH] Use the branch instruction to define the location of a PHI-node write We use the branch instruction as the location at which a PHI-node write takes place, instead of the PHI-node itself. This allows us to identify the basic-block in a region statement which is on the incoming edge of the PHI-node and for which the write access was originally introduced. As a result we can, during code generation, avoid generating PHI-node write accesses for basic blocks that do not preceed the PHI node without having to look at the IR again. This change fixes a bug which was introduced in r243420, when we started to explicitly model PHI-node reads and writes, but dropped some additional checks that where still necessary during code generation to not emit PHI-node writes for basic-blocks that are not on incoming edges of the original PHI node. Compared to the code before r243420 the new code does not need to inspect the IR any more and we also do not generate multiple redundant writes. llvm-svn: 243852 --- polly/include/polly/Support/ScopHelper.h | 3 -- polly/lib/Analysis/ScopInfo.cpp | 14 +++++- polly/lib/Analysis/TempScopInfo.cpp | 6 +-- polly/lib/CodeGen/BlockGenerators.cpp | 4 ++ polly/lib/Support/ScopHelper.cpp | 8 --- .../Isl/CodeGen/non-affine-phi-node-expansion-2.ll | 58 ++++++++++++++++++++++ 6 files changed, 78 insertions(+), 15 deletions(-) create mode 100644 polly/test/Isl/CodeGen/non-affine-phi-node-expansion-2.ll diff --git a/polly/include/polly/Support/ScopHelper.h b/polly/include/polly/Support/ScopHelper.h index 9277c22c..4397bb3 100644 --- a/polly/include/polly/Support/ScopHelper.h +++ b/polly/include/polly/Support/ScopHelper.h @@ -53,9 +53,6 @@ bool hasInvokeEdge(const llvm::PHINode *PN); llvm::Value *getPointerOperand(llvm::Instruction &Inst); llvm::BasicBlock *createSingleExitEdge(llvm::Region *R, llvm::Pass *P); -/// @brief Return the type of the access. -llvm::Type *getAccessInstType(llvm::Instruction *AccInst); - /// @brief Simplify the region in a SCoP to have a single unconditional entry /// edge and a single exit edge. /// diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp index 3081f1a..21772f1 100644 --- a/polly/lib/Analysis/ScopInfo.cpp +++ b/polly/lib/Analysis/ScopInfo.cpp @@ -880,6 +880,18 @@ void ScopStmt::restrictDomain(__isl_take isl_set *NewDomain) { Domain = NewDomain; } +// @brief Get the data-type of the elements accessed +static Type *getAccessType(IRAccess &Access, Instruction *AccessInst) { + if (Access.isPHI()) + return Access.getBase()->getType(); + + if (StoreInst *Store = dyn_cast(AccessInst)) + return Store->getValueOperand()->getType(); + if (BranchInst *Branch = dyn_cast(AccessInst)) + return Branch->getCondition()->getType(); + return AccessInst->getType(); +} + void ScopStmt::buildAccesses(TempScop &tempScop, BasicBlock *Block, bool isApproximated) { AccFuncSetType *AFS = tempScop.getAccessFunctions(Block); @@ -889,8 +901,8 @@ void ScopStmt::buildAccesses(TempScop &tempScop, BasicBlock *Block, for (auto &AccessPair : *AFS) { IRAccess &Access = AccessPair.first; Instruction *AccessInst = AccessPair.second; + Type *ElementType = getAccessType(Access, AccessInst); - Type *ElementType = getAccessInstType(AccessInst); const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo( Access.getBase(), ElementType, Access.Sizes, Access.isPHI()); diff --git a/polly/lib/Analysis/TempScopInfo.cpp b/polly/lib/Analysis/TempScopInfo.cpp index b476b68..6b17084 100644 --- a/polly/lib/Analysis/TempScopInfo.cpp +++ b/polly/lib/Analysis/TempScopInfo.cpp @@ -134,10 +134,10 @@ void TempScopInfo::buildPHIAccesses(PHINode *PHI, Region &R, } } - // If the operand is a constant, global or argument we need an access - // instruction and just choose the PHI. + // If the operand is a constant, global or argument we use the terminator + // of the incoming basic block as the access instruction. if (!OpI) - OpI = PHI; + OpI = OpBB->getTerminator(); Written = true; diff --git a/polly/lib/CodeGen/BlockGenerators.cpp b/polly/lib/CodeGen/BlockGenerators.cpp index 67619f74..22722a5 100644 --- a/polly/lib/CodeGen/BlockGenerators.cpp +++ b/polly/lib/CodeGen/BlockGenerators.cpp @@ -1136,6 +1136,10 @@ void RegionGenerator::generateScalarStores(ScopStmt &Stmt, BasicBlock *BB, Instruction *ScalarInst = MA->getAccessInstruction(); PHINode *ScalarBasePHI = dyn_cast(ScalarBase); + // Only generate accesses that belong to this basic block. + if (ScalarInst->getParent() != BB) + continue; + Value *Val = nullptr; AllocaInst *ScalarAddr = nullptr; diff --git a/polly/lib/Support/ScopHelper.cpp b/polly/lib/Support/ScopHelper.cpp index 7a8b994..176b30d 100644 --- a/polly/lib/Support/ScopHelper.cpp +++ b/polly/lib/Support/ScopHelper.cpp @@ -67,14 +67,6 @@ Value *polly::getPointerOperand(Instruction &Inst) { return 0; } -Type *polly::getAccessInstType(Instruction *AccInst) { - if (StoreInst *Store = dyn_cast(AccInst)) - return Store->getValueOperand()->getType(); - if (BranchInst *Branch = dyn_cast(AccInst)) - return Branch->getCondition()->getType(); - return AccInst->getType(); -} - bool polly::hasInvokeEdge(const PHINode *PN) { for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) if (InvokeInst *II = dyn_cast(PN->getIncomingValue(i))) diff --git a/polly/test/Isl/CodeGen/non-affine-phi-node-expansion-2.ll b/polly/test/Isl/CodeGen/non-affine-phi-node-expansion-2.ll new file mode 100644 index 0000000..4bdf308 --- /dev/null +++ b/polly/test/Isl/CodeGen/non-affine-phi-node-expansion-2.ll @@ -0,0 +1,58 @@ +; RUN: opt %loadPolly -polly-codegen -polly-no-early-exit -S < %s | FileCheck %s +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + + +; CHECK: polly.stmt.bb3: ; preds = %polly.stmt.bb3.entry +; CHECK: %polly.subregion.iv = phi i32 [ 0, %polly.stmt.bb3.entry ] +; CHECK: %polly.tmp = phi i64 [ %tmp.phiops.reload, %polly.stmt.bb3.entry ] +; CHECK: %tmp6_p_scalar_ = load double, double* %arg11, !alias.scope !0, !noalias !2 +; CHECK: %p_tmp7 = fadd double undef, %tmp6_p_scalar_ +; CHECK: %p_tmp8 = fcmp olt double undef, %p_tmp7 +; CHECK: %polly.subregion.iv.inc = add i32 %polly.subregion.iv, 1 +; CHECK: br i1 %p_tmp8, label %polly.stmt.bb9, label %polly.stmt.bb10 + +; CHECK: polly.stmt.bb9: ; preds = %polly.stmt.bb3 +; CHECK: store double 1.000000e+00, double* %tmp12.phiops +; CHECK: br label %polly.stmt.bb11.exit + +; CHECK: polly.stmt.bb10: ; preds = %polly.stmt.bb3 +; CHECK: store double 2.000000e+00, double* %tmp12.phiops +; CHECK: br label %polly.stmt.bb11.exit + + +define void @hoge(i32 %arg, [1024 x double]* %arg1) { +bb: + br label %bb2 + +bb2: ; preds = %bb + br label %bb3 + +bb3: ; preds = %bb11, %bb2 + %tmp = phi i64 [ 0, %bb11 ], [ 0, %bb2 ] + %tmp4 = icmp sgt i32 %arg, 0 + %tmp5 = getelementptr inbounds [1024 x double], [1024 x double]* %arg1, i64 0, i64 0 + %tmp6 = load double, double* %tmp5 + %tmp7 = fadd double undef, %tmp6 + %tmp8 = fcmp olt double undef, %tmp7 + br i1 %tmp8, label %bb9, label %bb10 + +bb9: ; preds = %bb3 + br label %bb11 + +bb10: ; preds = %bb3 + br label %bb11 + +bb11: ; preds = %bb10, %bb9 + %tmp12 = phi double [ 1.0, %bb9 ], [ 2.0, %bb10 ] + %tmp13 = getelementptr inbounds [1024 x double], [1024 x double]* %arg1, i64 %tmp, i64 0 + store double %tmp12, double* %tmp13 + %tmp14 = add nuw nsw i64 0, 1 + %tmp15 = trunc i64 %tmp14 to i32 + br i1 false, label %bb3, label %bb16 + +bb16: ; preds = %bb11 + br label %bb17 + +bb17: ; preds = %bb16 + ret void +} -- 2.7.4