summaryrefslogtreecommitdiff
path: root/lib/Transforms/Scalar/StructurizeCFG.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms/Scalar/StructurizeCFG.cpp')
-rw-r--r--lib/Transforms/Scalar/StructurizeCFG.cpp173
1 files changed, 116 insertions, 57 deletions
diff --git a/lib/Transforms/Scalar/StructurizeCFG.cpp b/lib/Transforms/Scalar/StructurizeCFG.cpp
index 2972e1cff9a4..d650264176aa 100644
--- a/lib/Transforms/Scalar/StructurizeCFG.cpp
+++ b/lib/Transforms/Scalar/StructurizeCFG.cpp
@@ -40,6 +40,7 @@
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
#include <algorithm>
#include <cassert>
@@ -55,6 +56,12 @@ static const char *const FlowBlockName = "Flow";
namespace {
+static cl::opt<bool> ForceSkipUniformRegions(
+ "structurizecfg-skip-uniform-regions",
+ cl::Hidden,
+ cl::desc("Force whether the StructurizeCFG pass skips uniform regions"),
+ cl::init(false));
+
// Definition of the complex types used in this pass.
using BBValuePair = std::pair<BasicBlock *, Value *>;
@@ -120,7 +127,7 @@ public:
bool resultIsRememberedBlock() { return ResultIsRemembered; }
};
-/// @brief Transforms the control flow graph on one single entry/exit region
+/// Transforms the control flow graph on one single entry/exit region
/// at a time.
///
/// After the transform all "If"/"Then"/"Else" style control flow looks like
@@ -176,6 +183,7 @@ class StructurizeCFG : public RegionPass {
Function *Func;
Region *ParentRegion;
+ DivergenceAnalysis *DA;
DominatorTree *DT;
LoopInfo *LI;
@@ -196,6 +204,9 @@ class StructurizeCFG : public RegionPass {
void orderNodes();
+ Loop *getAdjustedLoop(RegionNode *RN);
+ unsigned getAdjustedLoopDepth(RegionNode *RN);
+
void analyzeLoops(RegionNode *N);
Value *invert(Value *Condition);
@@ -242,8 +253,11 @@ class StructurizeCFG : public RegionPass {
public:
static char ID;
- explicit StructurizeCFG(bool SkipUniformRegions = false)
- : RegionPass(ID), SkipUniformRegions(SkipUniformRegions) {
+ explicit StructurizeCFG(bool SkipUniformRegions_ = false)
+ : RegionPass(ID),
+ SkipUniformRegions(SkipUniformRegions_) {
+ if (ForceSkipUniformRegions.getNumOccurrences())
+ SkipUniformRegions = ForceSkipUniformRegions.getValue();
initializeStructurizeCFGPass(*PassRegistry::getPassRegistry());
}
@@ -278,7 +292,7 @@ INITIALIZE_PASS_DEPENDENCY(RegionInfoPass)
INITIALIZE_PASS_END(StructurizeCFG, "structurizecfg", "Structurize the CFG",
false, false)
-/// \brief Initialize the types and constants used in the pass
+/// Initialize the types and constants used in the pass
bool StructurizeCFG::doInitialization(Region *R, RGPassManager &RGM) {
LLVMContext &Context = R->getEntry()->getContext();
@@ -290,7 +304,27 @@ bool StructurizeCFG::doInitialization(Region *R, RGPassManager &RGM) {
return false;
}
-/// \brief Build up the general order of nodes
+/// Use the exit block to determine the loop if RN is a SubRegion.
+Loop *StructurizeCFG::getAdjustedLoop(RegionNode *RN) {
+ if (RN->isSubRegion()) {
+ Region *SubRegion = RN->getNodeAs<Region>();
+ return LI->getLoopFor(SubRegion->getExit());
+ }
+
+ return LI->getLoopFor(RN->getEntry());
+}
+
+/// Use the exit block to determine the loop depth if RN is a SubRegion.
+unsigned StructurizeCFG::getAdjustedLoopDepth(RegionNode *RN) {
+ if (RN->isSubRegion()) {
+ Region *SubR = RN->getNodeAs<Region>();
+ return LI->getLoopDepth(SubR->getExit());
+ }
+
+ return LI->getLoopDepth(RN->getEntry());
+}
+
+/// Build up the general order of nodes
void StructurizeCFG::orderNodes() {
ReversePostOrderTraversal<Region*> RPOT(ParentRegion);
SmallDenseMap<Loop*, unsigned, 8> LoopBlocks;
@@ -299,16 +333,15 @@ void StructurizeCFG::orderNodes() {
// to what we want. The only problem with it is that sometimes backedges
// for outer loops will be visited before backedges for inner loops.
for (RegionNode *RN : RPOT) {
- BasicBlock *BB = RN->getEntry();
- Loop *Loop = LI->getLoopFor(BB);
+ Loop *Loop = getAdjustedLoop(RN);
++LoopBlocks[Loop];
}
unsigned CurrentLoopDepth = 0;
Loop *CurrentLoop = nullptr;
for (auto I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
- BasicBlock *BB = (*I)->getEntry();
- unsigned LoopDepth = LI->getLoopDepth(BB);
+ RegionNode *RN = cast<RegionNode>(*I);
+ unsigned LoopDepth = getAdjustedLoopDepth(RN);
if (is_contained(Order, *I))
continue;
@@ -320,15 +353,14 @@ void StructurizeCFG::orderNodes() {
auto LoopI = I;
while (unsigned &BlockCount = LoopBlocks[CurrentLoop]) {
LoopI++;
- BasicBlock *LoopBB = (*LoopI)->getEntry();
- if (LI->getLoopFor(LoopBB) == CurrentLoop) {
+ if (getAdjustedLoop(cast<RegionNode>(*LoopI)) == CurrentLoop) {
--BlockCount;
Order.push_back(*LoopI);
}
}
}
- CurrentLoop = LI->getLoopFor(BB);
+ CurrentLoop = getAdjustedLoop(RN);
if (CurrentLoop)
LoopBlocks[CurrentLoop]--;
@@ -343,7 +375,7 @@ void StructurizeCFG::orderNodes() {
std::reverse(Order.begin(), Order.end());
}
-/// \brief Determine the end of the loops
+/// Determine the end of the loops
void StructurizeCFG::analyzeLoops(RegionNode *N) {
if (N->isSubRegion()) {
// Test for exit as back edge
@@ -362,15 +394,16 @@ void StructurizeCFG::analyzeLoops(RegionNode *N) {
}
}
-/// \brief Invert the given condition
+/// Invert the given condition
Value *StructurizeCFG::invert(Value *Condition) {
// First: Check if it's a constant
if (Constant *C = dyn_cast<Constant>(Condition))
return ConstantExpr::getNot(C);
// Second: If the condition is already inverted, return the original value
- if (match(Condition, m_Not(m_Value(Condition))))
- return Condition;
+ Value *NotCondition;
+ if (match(Condition, m_Not(m_Value(NotCondition))))
+ return NotCondition;
if (Instruction *Inst = dyn_cast<Instruction>(Condition)) {
// Third: Check all the users for an invert
@@ -394,7 +427,7 @@ Value *StructurizeCFG::invert(Value *Condition) {
llvm_unreachable("Unhandled condition to invert");
}
-/// \brief Build the condition for one edge
+/// Build the condition for one edge
Value *StructurizeCFG::buildCondition(BranchInst *Term, unsigned Idx,
bool Invert) {
Value *Cond = Invert ? BoolFalse : BoolTrue;
@@ -407,7 +440,7 @@ Value *StructurizeCFG::buildCondition(BranchInst *Term, unsigned Idx,
return Cond;
}
-/// \brief Analyze the predecessors of each block and build up predicates
+/// Analyze the predecessors of each block and build up predicates
void StructurizeCFG::gatherPredicates(RegionNode *N) {
RegionInfo *RI = ParentRegion->getRegionInfo();
BasicBlock *BB = N->getEntry();
@@ -465,7 +498,7 @@ void StructurizeCFG::gatherPredicates(RegionNode *N) {
}
}
-/// \brief Collect various loop and predicate infos
+/// Collect various loop and predicate infos
void StructurizeCFG::collectInfos() {
// Reset predicate
Predicates.clear();
@@ -478,10 +511,10 @@ void StructurizeCFG::collectInfos() {
Visited.clear();
for (RegionNode *RN : reverse(Order)) {
- DEBUG(dbgs() << "Visiting: "
- << (RN->isSubRegion() ? "SubRegion with entry: " : "")
- << RN->getEntry()->getName() << " Loop Depth: "
- << LI->getLoopDepth(RN->getEntry()) << "\n");
+ LLVM_DEBUG(dbgs() << "Visiting: "
+ << (RN->isSubRegion() ? "SubRegion with entry: " : "")
+ << RN->getEntry()->getName() << " Loop Depth: "
+ << LI->getLoopDepth(RN->getEntry()) << "\n");
// Analyze all the conditions leading to a node
gatherPredicates(RN);
@@ -494,7 +527,7 @@ void StructurizeCFG::collectInfos() {
}
}
-/// \brief Insert the missing branch conditions
+/// Insert the missing branch conditions
void StructurizeCFG::insertConditions(bool Loops) {
BranchVector &Conds = Loops ? LoopConds : Conditions;
Value *Default = Loops ? BoolTrue : BoolFalse;
@@ -540,14 +573,11 @@ void StructurizeCFG::insertConditions(bool Loops) {
}
}
-/// \brief Remove all PHI values coming from "From" into "To" and remember
+/// Remove all PHI values coming from "From" into "To" and remember
/// them in DeletedPhis
void StructurizeCFG::delPhiValues(BasicBlock *From, BasicBlock *To) {
PhiMap &Map = DeletedPhis[To];
- for (Instruction &I : *To) {
- if (!isa<PHINode>(I))
- break;
- PHINode &Phi = cast<PHINode>(I);
+ for (PHINode &Phi : To->phis()) {
while (Phi.getBasicBlockIndex(From) != -1) {
Value *Deleted = Phi.removeIncomingValue(From, false);
Map[&Phi].push_back(std::make_pair(From, Deleted));
@@ -555,19 +585,16 @@ void StructurizeCFG::delPhiValues(BasicBlock *From, BasicBlock *To) {
}
}
-/// \brief Add a dummy PHI value as soon as we knew the new predecessor
+/// Add a dummy PHI value as soon as we knew the new predecessor
void StructurizeCFG::addPhiValues(BasicBlock *From, BasicBlock *To) {
- for (Instruction &I : *To) {
- if (!isa<PHINode>(I))
- break;
- PHINode &Phi = cast<PHINode>(I);
+ for (PHINode &Phi : To->phis()) {
Value *Undef = UndefValue::get(Phi.getType());
Phi.addIncoming(Undef, From);
}
AddedPhis[To].push_back(From);
}
-/// \brief Add the real PHI value as soon as everything is set up
+/// Add the real PHI value as soon as everything is set up
void StructurizeCFG::setPhiValues() {
SSAUpdater Updater;
for (const auto &AddedPhi : AddedPhis) {
@@ -607,7 +634,7 @@ void StructurizeCFG::setPhiValues() {
assert(DeletedPhis.empty());
}
-/// \brief Remove phi values from all successors and then remove the terminator.
+/// Remove phi values from all successors and then remove the terminator.
void StructurizeCFG::killTerminator(BasicBlock *BB) {
TerminatorInst *Term = BB->getTerminator();
if (!Term)
@@ -617,10 +644,12 @@ void StructurizeCFG::killTerminator(BasicBlock *BB) {
SI != SE; ++SI)
delPhiValues(BB, *SI);
+ if (DA)
+ DA->removeValue(Term);
Term->eraseFromParent();
}
-/// \brief Let node exit(s) point to NewExit
+/// Let node exit(s) point to NewExit
void StructurizeCFG::changeExit(RegionNode *Node, BasicBlock *NewExit,
bool IncludeDominator) {
if (Node->isSubRegion()) {
@@ -666,7 +695,7 @@ void StructurizeCFG::changeExit(RegionNode *Node, BasicBlock *NewExit,
}
}
-/// \brief Create a new flow node and update dominator tree and region info
+/// Create a new flow node and update dominator tree and region info
BasicBlock *StructurizeCFG::getNextFlow(BasicBlock *Dominator) {
LLVMContext &Context = Func->getContext();
BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() :
@@ -678,7 +707,7 @@ BasicBlock *StructurizeCFG::getNextFlow(BasicBlock *Dominator) {
return Flow;
}
-/// \brief Create a new or reuse the previous node as flow node
+/// Create a new or reuse the previous node as flow node
BasicBlock *StructurizeCFG::needPrefix(bool NeedEmpty) {
BasicBlock *Entry = PrevNode->getEntry();
@@ -697,7 +726,7 @@ BasicBlock *StructurizeCFG::needPrefix(bool NeedEmpty) {
return Flow;
}
-/// \brief Returns the region exit if possible, otherwise just a new flow node
+/// Returns the region exit if possible, otherwise just a new flow node
BasicBlock *StructurizeCFG::needPostfix(BasicBlock *Flow,
bool ExitUseAllowed) {
if (!Order.empty() || !ExitUseAllowed)
@@ -709,13 +738,13 @@ BasicBlock *StructurizeCFG::needPostfix(BasicBlock *Flow,
return Exit;
}
-/// \brief Set the previous node
+/// Set the previous node
void StructurizeCFG::setPrevNode(BasicBlock *BB) {
PrevNode = ParentRegion->contains(BB) ? ParentRegion->getBBNode(BB)
: nullptr;
}
-/// \brief Does BB dominate all the predicates of Node?
+/// Does BB dominate all the predicates of Node?
bool StructurizeCFG::dominatesPredicates(BasicBlock *BB, RegionNode *Node) {
BBPredicates &Preds = Predicates[Node->getEntry()];
return llvm::all_of(Preds, [&](std::pair<BasicBlock *, Value *> Pred) {
@@ -723,7 +752,7 @@ bool StructurizeCFG::dominatesPredicates(BasicBlock *BB, RegionNode *Node) {
});
}
-/// \brief Can we predict that this node will always be called?
+/// Can we predict that this node will always be called?
bool StructurizeCFG::isPredictableTrue(RegionNode *Node) {
BBPredicates &Preds = Predicates[Node->getEntry()];
bool Dominated = false;
@@ -851,7 +880,7 @@ void StructurizeCFG::createFlow() {
}
/// Handle a rare case where the disintegrated nodes instructions
-/// no longer dominate all their uses. Not sure if this is really nessasary
+/// no longer dominate all their uses. Not sure if this is really necessary
void StructurizeCFG::rebuildSSA() {
SSAUpdater Updater;
for (BasicBlock *BB : ParentRegion->blocks())
@@ -884,30 +913,60 @@ void StructurizeCFG::rebuildSSA() {
}
}
-static bool hasOnlyUniformBranches(const Region *R,
+static bool hasOnlyUniformBranches(Region *R, unsigned UniformMDKindID,
const DivergenceAnalysis &DA) {
- for (const BasicBlock *BB : R->blocks()) {
- const BranchInst *Br = dyn_cast<BranchInst>(BB->getTerminator());
- if (!Br || !Br->isConditional())
- continue;
+ for (auto E : R->elements()) {
+ if (!E->isSubRegion()) {
+ auto Br = dyn_cast<BranchInst>(E->getEntry()->getTerminator());
+ if (!Br || !Br->isConditional())
+ continue;
- if (!DA.isUniform(Br->getCondition()))
- return false;
- DEBUG(dbgs() << "BB: " << BB->getName() << " has uniform terminator\n");
+ if (!DA.isUniform(Br))
+ return false;
+ LLVM_DEBUG(dbgs() << "BB: " << Br->getParent()->getName()
+ << " has uniform terminator\n");
+ } else {
+ // Explicitly refuse to treat regions as uniform if they have non-uniform
+ // subregions. We cannot rely on DivergenceAnalysis for branches in
+ // subregions because those branches may have been removed and re-created,
+ // so we look for our metadata instead.
+ //
+ // Warning: It would be nice to treat regions as uniform based only on
+ // their direct child basic blocks' terminators, regardless of whether
+ // subregions are uniform or not. However, this requires a very careful
+ // look at SIAnnotateControlFlow to make sure nothing breaks there.
+ for (auto BB : E->getNodeAs<Region>()->blocks()) {
+ auto Br = dyn_cast<BranchInst>(BB->getTerminator());
+ if (!Br || !Br->isConditional())
+ continue;
+
+ if (!Br->getMetadata(UniformMDKindID))
+ return false;
+ }
+ }
}
return true;
}
-/// \brief Run the transformation for each region found
+/// Run the transformation for each region found
bool StructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) {
if (R->isTopLevelRegion())
return false;
+ DA = nullptr;
+
if (SkipUniformRegions) {
// TODO: We could probably be smarter here with how we handle sub-regions.
- auto &DA = getAnalysis<DivergenceAnalysis>();
- if (hasOnlyUniformBranches(R, DA)) {
- DEBUG(dbgs() << "Skipping region with uniform control flow: " << *R << '\n');
+ // We currently rely on the fact that metadata is set by earlier invocations
+ // of the pass on sub-regions, and that this metadata doesn't get lost --
+ // but we shouldn't rely on metadata for correctness!
+ unsigned UniformMDKindID =
+ R->getEntry()->getContext().getMDKindID("structurizecfg.uniform");
+ DA = &getAnalysis<DivergenceAnalysis>();
+
+ if (hasOnlyUniformBranches(R, UniformMDKindID, *DA)) {
+ LLVM_DEBUG(dbgs() << "Skipping region with uniform control flow: " << *R
+ << '\n');
// Mark all direct child block terminators as having been treated as
// uniform. To account for a possible future in which non-uniform
@@ -919,7 +978,7 @@ bool StructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) {
continue;
if (Instruction *Term = E->getEntry()->getTerminator())
- Term->setMetadata("structurizecfg.uniform", MD);
+ Term->setMetadata(UniformMDKindID, MD);
}
return false;
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-08 00:47:14 +0000