summaryrefslogtreecommitdiffstats
path: root/polly/lib/Analysis/ScopBuilder.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'polly/lib/Analysis/ScopBuilder.cpp')
-rw-r--r--polly/lib/Analysis/ScopBuilder.cpp182
1 files changed, 180 insertions, 2 deletions
diff --git a/polly/lib/Analysis/ScopBuilder.cpp b/polly/lib/Analysis/ScopBuilder.cpp
index 88d9cc665df..008392c08f3 100644
--- a/polly/lib/Analysis/ScopBuilder.cpp
+++ b/polly/lib/Analysis/ScopBuilder.cpp
@@ -25,6 +25,7 @@
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
@@ -102,14 +103,16 @@ static cl::opt<bool> DisableMultiplicativeReductions(
cl::desc("Disable multiplicative reductions"), cl::Hidden, cl::ZeroOrMore,
cl::init(false), cl::cat(PollyCategory));
-enum class GranularityChoice { BasicBlocks };
+enum class GranularityChoice { BasicBlocks, ScalarIndepependence };
static cl::opt<GranularityChoice> StmtGranularity(
"polly-stmt-granularity",
cl::desc(
"Algorithm to use for splitting basic blocks into multiple statements"),
cl::values(clEnumValN(GranularityChoice::BasicBlocks, "bb",
- "One statement per basic block")),
+ "One statement per basic block"),
+ clEnumValN(GranularityChoice::ScalarIndepependence,
+ "scalar-indep", "Scalar independence heuristic")),
cl::init(GranularityChoice::BasicBlocks), cl::cat(PollyCategory));
void ScopBuilder::buildPHIAccesses(ScopStmt *PHIStmt, PHINode *PHI,
@@ -701,6 +704,178 @@ void ScopBuilder::buildSequentialBlockStmts(BasicBlock *BB) {
scop->addScopStmt(BB, SurroundingLoop, Instructions, Count);
}
+/// Is @p Inst an ordered instruction?
+///
+/// An unordered instruction is an instruction, such that a sequence of
+/// unordered instructions can be permuted without changing semantics. Any
+/// instruction for which this is not always the case is ordered.
+static bool isOrderedInstruction(Instruction *Inst) {
+ return Inst->mayHaveSideEffects() || Inst->mayReadOrWriteMemory();
+}
+
+/// Join instructions to the same statement if one uses the scalar result of the
+/// other.
+static void joinOperandTree(EquivalenceClasses<Instruction *> &UnionFind,
+ ArrayRef<Instruction *> ModeledInsts) {
+ for (Instruction *Inst : ModeledInsts) {
+ if (isa<PHINode>(Inst))
+ continue;
+
+ for (Use &Op : Inst->operands()) {
+ Instruction *OpInst = dyn_cast<Instruction>(Op.get());
+ if (!OpInst)
+ continue;
+
+ // Check if OpInst is in the BB and is a modeled instruction.
+ auto OpVal = UnionFind.findValue(OpInst);
+ if (OpVal == UnionFind.end())
+ continue;
+
+ UnionFind.unionSets(Inst, OpInst);
+ }
+ }
+}
+
+/// Join instructions that are used as incoming value in successor PHIs into the
+/// epilogue.
+static void
+joinIncomingPHIValuesIntoEpilogue(EquivalenceClasses<Instruction *> &UnionFind,
+ ArrayRef<Instruction *> ModeledInsts,
+ BasicBlock *BB) {
+ for (BasicBlock *Succ : successors(BB)) {
+ for (Instruction &SuccInst : *Succ) {
+ PHINode *SuccPHI = dyn_cast<PHINode>(&SuccInst);
+ if (!SuccPHI)
+ break;
+
+ Value *IncomingVal = SuccPHI->getIncomingValueForBlock(BB);
+ Instruction *IncomingInst = dyn_cast<Instruction>(IncomingVal);
+ if (!IncomingInst)
+ continue;
+ if (IncomingInst->getParent() != BB)
+ continue;
+ if (UnionFind.findValue(IncomingInst) == UnionFind.end())
+ continue;
+
+ UnionFind.unionSets(nullptr, IncomingInst);
+ }
+ }
+}
+
+/// Ensure that the order of ordered instructions does not change.
+///
+/// If we encounter an ordered instruction enclosed in instructions belonging to
+/// a different statement (which might as well contain ordered instructions, but
+/// this is not tested here), join them.
+static void
+joinOrderedInstructions(EquivalenceClasses<Instruction *> &UnionFind,
+ ArrayRef<Instruction *> ModeledInsts) {
+ SetVector<Instruction *> SeenLeaders;
+ for (Instruction *Inst : ModeledInsts) {
+ if (!isOrderedInstruction(Inst))
+ continue;
+
+ Instruction *Leader = UnionFind.getLeaderValue(Inst);
+ bool Inserted = SeenLeaders.insert(Leader);
+ if (Inserted)
+ continue;
+
+ // Merge statements to close holes. Say, we have already seen statements A
+ // and B, in this order. Then we see an instruction of A again and we would
+ // see the pattern "A B A". This function joins all statements until the
+ // only seen occurrence of A.
+ for (Instruction *Prev : reverse(SeenLeaders)) {
+ // Items added to 'SeenLeaders' are leaders, but may have lost their
+ // leadership status when merged into another statement.
+ Instruction *PrevLeader = UnionFind.getLeaderValue(SeenLeaders.back());
+ if (PrevLeader == Leader)
+ break;
+ UnionFind.unionSets(Prev, Leader);
+ }
+ }
+}
+
+/// Also ensure that the epilogue is the last statement relative to all ordered
+/// instructions.
+///
+/// This is basically joinOrderedInstructions() but using the epilogue as
+/// 'ordered instruction'.
+static void joinAllAfterEpilogue(EquivalenceClasses<Instruction *> &UnionFind,
+ ArrayRef<Instruction *> ModeledInsts) {
+ bool EpilogueSeen = false;
+ for (Instruction *Inst : ModeledInsts) {
+ auto PHIWritesLeader = UnionFind.findLeader(nullptr);
+ auto InstLeader = UnionFind.findLeader(Inst);
+
+ if (PHIWritesLeader == InstLeader)
+ EpilogueSeen = true;
+
+ if (!isOrderedInstruction(Inst))
+ continue;
+
+ if (EpilogueSeen)
+ UnionFind.unionSets(PHIWritesLeader, InstLeader);
+ }
+}
+
+void ScopBuilder::buildEqivClassBlockStmts(BasicBlock *BB) {
+ Loop *L = LI.getLoopFor(BB);
+
+ // Extracting out modeled instructions saves us from checking
+ // shouldModelInst() repeatedly.
+ SmallVector<Instruction *, 32> ModeledInsts;
+ EquivalenceClasses<Instruction *> UnionFind;
+ for (Instruction &Inst : *BB) {
+ if (!shouldModelInst(&Inst, L))
+ continue;
+ ModeledInsts.push_back(&Inst);
+ UnionFind.insert(&Inst);
+ }
+
+ // 'nullptr' represents the last statement for a basic block. It contains no
+ // instructions, but holds the PHI write accesses for successor basic blocks.
+ // If a PHI has an incoming value defined in this BB, it can also be merged
+ // with other statements.
+ // TODO: We wouldn't need this if we would add PHIWrites into the statement
+ // that defines the incoming value (if in the BB) instead of always the last,
+ // so we could unconditionally always add a last statement.
+ UnionFind.insert(nullptr);
+
+ joinOperandTree(UnionFind, ModeledInsts);
+ joinIncomingPHIValuesIntoEpilogue(UnionFind, ModeledInsts, BB);
+ joinOrderedInstructions(UnionFind, ModeledInsts);
+ joinAllAfterEpilogue(UnionFind, ModeledInsts);
+
+ // The list of instructions for statement (statement represented by the leader
+ // instruction). The order of statements instructions is reversed such that
+ // the epilogue is first. This makes it easier to ensure that the epilogue is
+ // the last statement.
+ MapVector<Instruction *, std::vector<Instruction *>> LeaderToInstList;
+
+ // Ensure that the epilogue is last.
+ LeaderToInstList[nullptr];
+
+ // Collect the instructions of all leaders. UnionFind's member iterator
+ // unfortunately are not in any specific order.
+ for (Instruction &Inst : reverse(*BB)) {
+ auto LeaderIt = UnionFind.findLeader(&Inst);
+ if (LeaderIt == UnionFind.member_end())
+ continue;
+
+ std::vector<Instruction *> &InstList = LeaderToInstList[*LeaderIt];
+ InstList.push_back(&Inst);
+ }
+
+ // Finally build the statements.
+ int Count = 0;
+ for (auto &Instructions : reverse(LeaderToInstList)) {
+ std::vector<Instruction *> &InstList = Instructions.second;
+ std::reverse(InstList.begin(), InstList.end());
+ scop->addScopStmt(BB, L, std::move(InstList), Count);
+ Count += 1;
+ }
+}
+
void ScopBuilder::buildStmts(Region &SR) {
if (scop->isNonAffineSubRegion(&SR)) {
std::vector<Instruction *> Instructions;
@@ -722,6 +897,9 @@ void ScopBuilder::buildStmts(Region &SR) {
case GranularityChoice::BasicBlocks:
buildSequentialBlockStmts(BB);
break;
+ case GranularityChoice::ScalarIndepependence:
+ buildEqivClassBlockStmts(BB);
+ break;
}
}
}
OpenPOWER on IntegriCloud