summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rwxr-xr-xpolly/include/polly/Support/ScopHelper.h1
-rw-r--r--polly/lib/CodeGeneration.cpp202
-rw-r--r--polly/lib/Support/ScopHelper.cpp33
-rw-r--r--polly/test/CodeGen/split_edges.ll39
-rw-r--r--polly/test/CodeGen/split_edges_2.ll35
5 files changed, 198 insertions, 112 deletions
diff --git a/polly/include/polly/Support/ScopHelper.h b/polly/include/polly/Support/ScopHelper.h
index dd00d0189cb..48866deb23e 100755
--- a/polly/include/polly/Support/ScopHelper.h
+++ b/polly/include/polly/Support/ScopHelper.h
@@ -72,7 +72,6 @@ namespace polly {
llvm::Value *getPointerOperand(llvm::Instruction &Inst);
// Helper function for LLVM-IR about Scop.
- llvm::BasicBlock *createSingleEntryEdge(llvm::Region *R, llvm::Pass *P);
llvm::BasicBlock *createSingleExitEdge(llvm::Region *R, llvm::Pass *P);
/// @brief Split the entry block of a function to store the newly inserted
diff --git a/polly/lib/CodeGeneration.cpp b/polly/lib/CodeGeneration.cpp
index 1f2b88e5293..60072fdacbb 100644
--- a/polly/lib/CodeGeneration.cpp
+++ b/polly/lib/CodeGeneration.cpp
@@ -34,6 +34,7 @@
#include "llvm/Support/IRBuilder.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Module.h"
#include "llvm/ADT/SetVector.h"
@@ -1271,6 +1272,7 @@ class CodeGeneration : public ScopPass {
CloogInfo *C;
LoopInfo *LI;
TargetData *TD;
+ RegionInfo *RI;
std::vector<std::string> parallelLoops;
@@ -1279,17 +1281,6 @@ class CodeGeneration : public ScopPass {
CodeGeneration() : ScopPass(ID) {}
- void createSeSeEdges(Region *R) {
- BasicBlock *newEntry = createSingleEntryEdge(R, this);
-
- for (Scop::iterator SI = S->begin(), SE = S->end(); SI != SE; ++SI)
- if ((*SI)->getBasicBlock() == R->getEntry())
- (*SI)->setBasicBlock(newEntry);
-
- createSingleExitEdge(R, this);
- }
-
-
// Adding prototypes required if OpenMP is enabled.
void addOpenMPDefinitions(IRBuilder<> &Builder)
{
@@ -1342,10 +1333,90 @@ class CodeGeneration : public ScopPass {
}
}
+ // Split the entry edge of the region and generate a new basic block on this
+ // edge. This function also updates ScopInfo and RegionInfo.
+ //
+ // @param region The region where the entry edge will be splitted.
+ BasicBlock *splitEdgeAdvanced(Region *region) {
+ BasicBlock *newBlock;
+ BasicBlock *splitBlock;
+
+ newBlock = SplitEdge(region->getEnteringBlock(), region->getEntry(), this);
+
+ if (DT->dominates(region->getEntry(), newBlock)) {
+ // Update ScopInfo.
+ for (Scop::iterator SI = S->begin(), SE = S->end(); SI != SE; ++SI)
+ if ((*SI)->getBasicBlock() == newBlock) {
+ (*SI)->setBasicBlock(newBlock);
+ break;
+ }
+
+ // Update RegionInfo.
+ splitBlock = region->getEntry();
+ region->replaceEntry(newBlock);
+ } else {
+ RI->setRegionFor(newBlock, region->getParent());
+ splitBlock = newBlock;
+ }
+
+ return splitBlock;
+ }
+
+ // Create a split block that branches either to the old code or to a new basic
+ // block where the new code can be inserted.
+ //
+ // @param builder A builder that will be set to point to a basic block, where
+ // the new code can be generated.
+ // @return The split basic block.
+ BasicBlock *addSplitAndStartBlock(IRBuilder<> *builder) {
+ BasicBlock *splitBlock = splitEdgeAdvanced(region);
+
+ splitBlock->setName("polly.enterScop");
+
+ Function *function = splitBlock->getParent();
+ BasicBlock *startBlock = BasicBlock::Create(function->getContext(),
+ "polly.start", function);
+ splitBlock->getTerminator()->eraseFromParent();
+ builder->SetInsertPoint(splitBlock);
+ builder->CreateCondBr(builder->getTrue(), startBlock, region->getEntry());
+ DT->addNewBlock(startBlock, splitBlock);
+
+ // Start code generation here.
+ builder->SetInsertPoint(startBlock);
+ return splitBlock;
+ }
+
+ // Merge the control flow of the newly generated code with the existing code.
+ //
+ // @param splitBlock The basic block where the control flow was split between
+ // old and new version of the Scop.
+ // @param builder An IRBuilder that points to the last instruction of the
+ // newly generated code.
+ void mergeControlFlow(BasicBlock *splitBlock, IRBuilder<> *builder) {
+ BasicBlock *mergeBlock;
+ Region *R = region;
+
+ if (R->getExit()->getSinglePredecessor())
+ // No splitEdge required. A block with a single predecessor cannot have
+ // PHI nodes that would complicate life.
+ mergeBlock = R->getExit();
+ else {
+ mergeBlock = SplitEdge(R->getExitingBlock(), R->getExit(), this);
+ // SplitEdge will never split R->getExit(), as R->getExit() has more than
+ // one predecessor. Hence, mergeBlock is always a newly generated block.
+ mergeBlock->setName("polly.finalMerge");
+ R->replaceExit(mergeBlock);
+ }
+
+ builder->CreateBr(mergeBlock);
+
+ if (DT->dominates(splitBlock, mergeBlock))
+ DT->changeImmediateDominator(mergeBlock, splitBlock);
+ }
+
bool runOnScop(Scop &scop) {
S = &scop;
region = &S->getRegion();
- Region *R = region;
DT = &getAnalysis<DominatorTree>();
Dependences *DP = &getAnalysis<Dependences>();
SE = &getAnalysis<ScalarEvolution>();
@@ -1353,91 +1424,66 @@ class CodeGeneration : public ScopPass {
C = &getAnalysis<CloogInfo>();
SD = &getAnalysis<ScopDetection>();
TD = &getAnalysis<TargetData>();
-
- Function *F = R->getEntry()->getParent();
+ RI = &getAnalysis<RegionInfo>();
parallelLoops.clear();
+ Function *F = region->getEntry()->getParent();
if (CodegenOnly != "" && CodegenOnly != F->getNameStr()) {
errs() << "Codegenerating only function '" << CodegenOnly
<< "' skipping '" << F->getNameStr() << "' \n";
return false;
}
- assert(R->isSimple() && "Only simple regions supported");
-
- createSeSeEdges(R);
+ assert(region->isSimple() && "Only simple regions are supported");
- // Create a basic block in which to start code generation.
- BasicBlock *PollyBB = BasicBlock::Create(F->getContext(), "pollyBB", F);
- IRBuilder<> Builder(PollyBB);
- DT->addNewBlock(PollyBB, R->getEntry());
-
- const clast_root *clast = (const clast_root *) C->getClast();
-
- ClastStmtCodeGen CodeGen(S, *SE, DT, SD, DP, TD, Builder);
+ // In the CFG and we generate next to original code of the Scop the
+ // optimized version. Both the new and the original version of the code
+ // remain in the CFG. A branch statement decides which version is executed.
+ // At the moment, we always execute the newly generated version (the old one
+ // is dead code eliminated by the cleanup passes). Later we may decide to
+ // execute the new version only under certain conditions. This will be the
+ // case if we support constructs for which we cannot prove all assumptions
+ // at compile time.
+ //
+ // Before transformation:
+ //
+ // bb0
+ // |
+ // orig_scop
+ // |
+ // bb1
+ //
+ // After transformation:
+ // bb0
+ // |
+ // polly.splitBlock
+ // / \
+ // | startBlock
+ // | |
+ // orig_scop new_scop
+ // \ /
+ // \ /
+ // bb1 (joinBlock)
+ IRBuilder<> builder(region->getEntry());
+
+ // The builder will be set to startBlock.
+ BasicBlock *splitBlock = addSplitAndStartBlock(&builder);
if (OpenMP)
- addOpenMPDefinitions(Builder);
+ addOpenMPDefinitions(builder);
- CodeGen.codegen(clast);
+ ClastStmtCodeGen CodeGen(S, *SE, DT, SD, DP, TD, builder);
+ CodeGen.codegen((const clast_root *) C->getClast());
- // Save the parallel loops generated.
parallelLoops.insert(parallelLoops.begin(),
CodeGen.getParallelLoops().begin(),
CodeGen.getParallelLoops().end());
- BasicBlock *AfterScop = *pred_begin(R->getExit());
- Builder.CreateBr(AfterScop);
-
- BasicBlock *successorBlock = *succ_begin(R->getEntry());
-
- // Update old PHI nodes to pass LLVM verification.
- std::vector<PHINode*> PHINodes;
- for (BasicBlock::iterator SI = successorBlock->begin(),
- SE = successorBlock->getFirstNonPHI(); SI != SE; ++SI) {
- PHINode *PN = static_cast<PHINode*>(&*SI);
- PHINodes.push_back(PN);
- }
-
- for (std::vector<PHINode*>::iterator PI = PHINodes.begin(),
- PE = PHINodes.end(); PI != PE; ++PI)
- (*PI)->removeIncomingValue(R->getEntry());
-
- DT->changeImmediateDominator(AfterScop, Builder.GetInsertBlock());
-
- BasicBlock *OldRegionEntry = *succ_begin(R->getEntry());
-
- // Enable the new polly code.
- R->getEntry()->getTerminator()->setSuccessor(0, PollyBB);
-
- // Remove old Scop nodes from dominator tree.
- std::vector<DomTreeNode*> ToVisit;
- std::vector<DomTreeNode*> Visited;
- ToVisit.push_back(DT->getNode(OldRegionEntry));
-
- while (!ToVisit.empty()) {
- DomTreeNode *Node = ToVisit.back();
-
- ToVisit.pop_back();
-
- if (AfterScop == Node->getBlock())
- continue;
-
- Visited.push_back(Node);
-
- std::vector<DomTreeNode*> Children = Node->getChildren();
- ToVisit.insert(ToVisit.end(), Children.begin(), Children.end());
- }
-
- for (std::vector<DomTreeNode*>::reverse_iterator I = Visited.rbegin(),
- E = Visited.rend(); I != E; ++I)
- DT->eraseNode((*I)->getBlock());
-
- R->getParent()->removeSubRegion(R);
+ mergeControlFlow(splitBlock, &builder);
- // And forget the Scop if we remove the region.
- SD->forgetScop(*R);
+ // Forget the Scop.
+ SD->forgetScop(*region);
return false;
}
diff --git a/polly/lib/Support/ScopHelper.cpp b/polly/lib/Support/ScopHelper.cpp
index dad9e62d74a..5cc096628ff 100644
--- a/polly/lib/Support/ScopHelper.cpp
+++ b/polly/lib/Support/ScopHelper.cpp
@@ -223,39 +223,6 @@ bool polly::hasInvokeEdge(const PHINode *PN) {
return false;
}
-// Helper function for LLVM-IR about Scop
-BasicBlock *polly::createSingleEntryEdge(Region *R, Pass *P) {
- BasicBlock *BB = R->getEntry();
-
- BasicBlock::iterator SplitIt = BB->begin();
-
- while (isa<PHINode>(SplitIt))
- ++SplitIt;
-
- BasicBlock *newBB = SplitBlock(BB, SplitIt, P);
-
- for (BasicBlock::iterator PI = BB->begin(); isa<PHINode>(PI); ++PI) {
- PHINode *PN = cast<PHINode>(PI);
- PHINode *NPN =
- PHINode::Create(PN->getType(), 2, PN->getName()+".ph", newBB->begin());
-
- for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
- if (R->contains(*PI)) {
- Value *V = PN->removeIncomingValue(*PI, false);
- NPN->addIncoming(V, *PI);
- }
- }
- PN->replaceAllUsesWith(NPN);
- NPN->addIncoming(PN,BB);
- }
-
- for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
- if (R->contains(*PI))
- (*PI)->getTerminator()->replaceUsesOfWith(BB, newBB);
-
- return newBB;
-}
-
BasicBlock *polly::createSingleExitEdge(Region *R, Pass *P) {
BasicBlock *BB = R->getExit();
diff --git a/polly/test/CodeGen/split_edges.ll b/polly/test/CodeGen/split_edges.ll
new file mode 100644
index 00000000000..be44e113a7a
--- /dev/null
+++ b/polly/test/CodeGen/split_edges.ll
@@ -0,0 +1,39 @@
+; RUN: opt %loadPolly -polly-codegen -verify-region-info -verify-dom-info -S %s | FileCheck %s
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+target triple = "x86_64-pc-linux-gnu"
+
+define void @loop_with_condition() nounwind {
+bb0:
+ call void @llvm.memory.barrier(i1 true, i1 true, i1 true, i1 true, i1 false)
+ br label %bb1
+
+bb1:
+ br i1 true, label %bb2, label %bb3
+
+bb2:
+ %ind1 = phi i32 [0, %bb1], [ %inc1, %bb2]
+ %inc1 = add i32 %ind1, 1
+ %cond1 = icmp eq i32 %ind1, 32
+ br i1 %cond1, label %bb4, label %bb2
+
+bb3:
+ %ind2 = phi i32 [0, %bb1], [ %inc2, %bb3]
+ %inc2 = add i32 %ind2, 1
+ br i1 true, label %bb4, label %bb3
+
+bb4:
+ br label %bb5
+
+bb5:
+ call void @llvm.memory.barrier(i1 true, i1 true, i1 true, i1 true, i1 false)
+ ret void
+
+}
+
+declare void @llvm.memory.barrier(i1, i1, i1, i1, i1) nounwind
+
+
+; CHECK: polly.enterScop
+; CHECK: polly.finalMerge
+; CHECK: polly.enterScop
+; CHECK: polly.finalMerge
diff --git a/polly/test/CodeGen/split_edges_2.ll b/polly/test/CodeGen/split_edges_2.ll
new file mode 100644
index 00000000000..5ad4ecc184c
--- /dev/null
+++ b/polly/test/CodeGen/split_edges_2.ll
@@ -0,0 +1,35 @@
+; RUN: opt %loadPolly -polly-codegen -verify-region-info -verify-dom-info -S %s | FileCheck %s
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+target triple = "x86_64-pc-linux-gnu"
+
+define void @loop_with_condition() nounwind {
+bb0:
+ call void @llvm.memory.barrier(i1 true, i1 true, i1 true, i1 true, i1 false)
+ br label %bb1
+
+bb1:
+ br label %bb2
+
+bb2:
+ %ind1 = phi i32 [0, %bb1], [ %inc1, %bb2]
+ %inc1 = add i32 %ind1, 1
+ %cond1 = icmp eq i32 %ind1, 32
+ br i1 %cond1, label %bb4, label %bb2
+
+bb4:
+ br label %bb5
+
+bb5:
+ call void @llvm.memory.barrier(i1 true, i1 true, i1 true, i1 true, i1 false)
+ ret void
+
+}
+
+declare void @llvm.memory.barrier(i1, i1, i1, i1, i1) nounwind
+
+; CHECK: polly.enterScop
+; CHECK-NOT: polly.finalMerge
+
+
+
OpenPOWER on IntegriCloud