52 #define DEBUG_TYPE "structurizecfg" 60 "structurizecfg-skip-uniform-regions",
62 cl::desc(
"Force whether the StructurizeCFG pass skips uniform regions"),
66 RelaxedUniformRegions(
"structurizecfg-relaxed-uniform-regions",
cl::Hidden,
67 cl::desc(
"Allow relaxed uniform region checks"),
72 using BBValuePair = std::pair<BasicBlock *, Value *>;
94 class NearestCommonDominator {
97 bool ResultIsRemembered =
false;
100 void addBlock(
BasicBlock *BB,
bool Remember) {
103 ResultIsRemembered = Remember;
108 if (NewResult != Result)
109 ResultIsRemembered =
false;
111 ResultIsRemembered |= Remember;
116 explicit NearestCommonDominator(
DominatorTree *DomTree) : DT(DomTree) {}
132 bool resultIsRememberedBlock() {
return ResultIsRemembered; }
181 bool SkipUniformRegions;
198 BBPhiMap DeletedPhis;
199 BB2BBVecMap AddedPhis;
202 BranchVector Conditions;
206 BranchVector LoopConds;
213 unsigned getAdjustedLoopDepth(
RegionNode *RN);
225 void insertConditions(
bool Loops);
236 bool IncludeDominator);
250 void wireFlow(
bool ExitUseAllowed,
BasicBlock *LoopEnd);
252 void handleLoops(
bool ExitUseAllowed,
BasicBlock *LoopEnd);
261 explicit StructurizeCFG(
bool SkipUniformRegions_ =
false)
263 SkipUniformRegions(SkipUniformRegions_) {
265 SkipUniformRegions = ForceSkipUniformRegions.
getValue();
273 StringRef getPassName()
const override {
return "Structurize control flow"; }
276 if (SkipUniformRegions)
316 return LI->getLoopFor(SubRegion->
getExit());
319 return LI->getLoopFor(RN->
getEntry());
323 unsigned StructurizeCFG::getAdjustedLoopDepth(
RegionNode *RN) {
326 return LI->getLoopDepth(SubR->
getExit());
329 return LI->getLoopDepth(RN->
getEntry());
333 void StructurizeCFG::orderNodes() {
345 unsigned CurrentLoopDepth = 0;
346 Loop *CurrentLoop =
nullptr;
347 for (
auto I = RPOT.begin(),
E = RPOT.end();
I !=
E; ++
I) {
349 unsigned LoopDepth = getAdjustedLoopDepth(RN);
354 if (LoopDepth < CurrentLoopDepth) {
359 while (
unsigned &BlockCount = LoopBlocks[CurrentLoop]) {
361 if (getAdjustedLoop(cast<RegionNode>(*LoopI)) == CurrentLoop) {
363 Order.push_back(*LoopI);
368 CurrentLoop = getAdjustedLoop(RN);
370 LoopBlocks[CurrentLoop]--;
372 CurrentLoopDepth = LoopDepth;
388 if (Visited.count(Exit))
397 if (Visited.count(Succ))
403 Value *StructurizeCFG::invert(
Value *Condition) {
405 if (
Constant *
C = dyn_cast<Constant>(Condition))
413 if (
Instruction *Inst = dyn_cast<Instruction>(Condition)) {
425 if (
Argument *
Arg = dyn_cast<Argument>(Condition)) {
428 Arg->getName() +
".inv",
438 Value *Cond = Invert ? BoolFalse : BoolTrue;
442 if (Idx != (
unsigned)Invert)
449 void StructurizeCFG::gatherPredicates(
RegionNode *N) {
450 RegionInfo *RI = ParentRegion->getRegionInfo();
452 BBPredicates &Pred = Predicates[BB];
453 BBPredicates &LPred = LoopPreds[BB];
457 if (!ParentRegion->contains(
P))
461 if (R == ParentRegion) {
463 BranchInst *Term = cast<BranchInst>(
P->getTerminator());
469 if (Visited.count(
P)) {
474 if (Visited.count(Other) && !
Loops.count(Other) &&
475 !Pred.count(Other) && !Pred.count(
P)) {
477 Pred[Other] = BoolFalse;
482 Pred[
P] = buildCondition(Term, i,
false);
485 LPred[
P] = buildCondition(Term, i,
true);
498 if (Visited.count(Entry))
499 Pred[Entry] = BoolTrue;
501 LPred[Entry] = BoolFalse;
507 void StructurizeCFG::collectInfos() {
520 << (RN->
isSubRegion() ?
"SubRegion with entry: " :
"")
521 << RN->
getEntry()->getName() <<
" Loop Depth: " 522 << LI->getLoopDepth(RN->
getEntry()) <<
"\n");
525 gatherPredicates(RN);
536 void StructurizeCFG::insertConditions(
bool Loops) {
537 BranchVector &Conds = Loops ? LoopConds : Conditions;
538 Value *Default = Loops ? BoolTrue : BoolFalse;
552 BBPredicates &Preds = Loops ? LoopPreds[SuccFalse] : Predicates[SuccTrue];
554 NearestCommonDominator Dominator(DT);
555 Dominator.addBlock(Parent);
557 Value *ParentValue =
nullptr;
558 for (std::pair<BasicBlock *, Value *> BBAndPred : Preds) {
560 Value *Pred = BBAndPred.second;
567 Dominator.addAndRememberBlock(BB);
573 if (!Dominator.resultIsRememberedBlock())
584 PhiMap &Map = DeletedPhis[To];
586 while (Phi.getBasicBlockIndex(From) != -1) {
588 Map[&Phi].push_back(std::make_pair(From, Deleted));
597 Phi.addIncoming(Undef, From);
599 AddedPhis[To].push_back(From);
603 void StructurizeCFG::setPhiValues() {
606 for (
const auto &AddedPhi : AddedPhis) {
608 const BBVector &From = AddedPhi.second;
610 if (!DeletedPhis.count(To))
613 PhiMap &Map = DeletedPhis[To];
614 for (
const auto &PI : Map) {
621 NearestCommonDominator Dominator(DT);
622 Dominator.addBlock(To);
623 for (
const auto &
VI : PI.second) {
625 Dominator.addAndRememberBlock(
VI.first);
628 if (!Dominator.resultIsRememberedBlock())
635 DeletedPhis.erase(To);
637 assert(DeletedPhis.empty());
646 for (
size_t i = 0; i < InsertedPhis.
size(); ++i) {
647 PHINode *Phi = InsertedPhis[i];
651 InsertedPhis[i] = InsertedPhis.
back();
661 void StructurizeCFG::killTerminator(
BasicBlock *BB) {
668 delPhiValues(BB, *
SI);
671 DA->removeValue(Term);
677 bool IncludeDominator) {
692 delPhiValues(BB, OldExit);
694 addPhiValues(BB, NewExit);
697 if (IncludeDominator) {
701 Dominator = DT->findNearestCommonDominator(Dominator, BB);
707 DT->changeImmediateDominator(NewExit, Dominator);
715 addPhiValues(BB, NewExit);
716 if (IncludeDominator)
717 DT->changeImmediateDominator(NewExit, BB);
724 BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() :
725 Order.back()->getEntry();
728 DT->addNewBlock(Flow, Dominator);
729 ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion);
734 BasicBlock *StructurizeCFG::needPrefix(
bool NeedEmpty) {
737 if (!PrevNode->isSubRegion()) {
738 killTerminator(Entry);
747 changeExit(PrevNode, Flow,
true);
748 PrevNode = ParentRegion->getBBNode(Flow);
754 bool ExitUseAllowed) {
755 if (!Order.empty() || !ExitUseAllowed)
756 return getNextFlow(Flow);
759 DT->changeImmediateDominator(Exit, Flow);
760 addPhiValues(Flow, Exit);
765 void StructurizeCFG::setPrevNode(
BasicBlock *BB) {
766 PrevNode = ParentRegion->contains(BB) ? ParentRegion->getBBNode(BB)
772 BBPredicates &Preds = Predicates[Node->
getEntry()];
773 return llvm::all_of(Preds, [&](std::pair<BasicBlock *, Value *> Pred) {
774 return DT->dominates(BB, Pred.first);
779 bool StructurizeCFG::isPredictableTrue(
RegionNode *Node) {
780 BBPredicates &Preds = Predicates[Node->
getEntry()];
781 bool Dominated =
false;
787 for (std::pair<BasicBlock*, Value*> Pred : Preds) {
789 Value *V = Pred.second;
794 if (!Dominated && DT->dominates(BB, PrevNode->getEntry()))
803 void StructurizeCFG::wireFlow(
bool ExitUseAllowed,
808 if (isPredictableTrue(Node)) {
811 changeExit(PrevNode, Node->
getEntry(),
true);
820 BasicBlock *Next = needPostfix(Flow, ExitUseAllowed);
824 addPhiValues(Flow, Entry);
825 DT->changeImmediateDominator(Entry, Flow);
828 while (!Order.empty() && !Visited.count(LoopEnd) &&
829 dominatesPredicates(Entry, Order.
back())) {
830 handleLoops(
false, LoopEnd);
833 changeExit(PrevNode, Next,
false);
838 void StructurizeCFG::handleLoops(
bool ExitUseAllowed,
843 if (!Loops.count(LoopStart)) {
844 wireFlow(ExitUseAllowed, LoopEnd);
848 if (!isPredictableTrue(Node))
849 LoopStart = needPrefix(
true);
852 wireFlow(
false, LoopEnd);
853 while (!Visited.count(LoopEnd)) {
854 handleLoops(
false, LoopEnd);
861 LoopStart->
setName(
"entry.orig");
869 DT->setNewRoot(NewEntry);
873 LoopEnd = needPrefix(
false);
874 BasicBlock *Next = needPostfix(LoopEnd, ExitUseAllowed);
876 BoolUndef, LoopEnd));
877 addPhiValues(LoopEnd, LoopStart);
883 void StructurizeCFG::createFlow() {
885 bool EntryDominatesExit = DT->dominates(ParentRegion->getEntry(), Exit);
895 while (!Order.empty()) {
896 handleLoops(EntryDominatesExit,
nullptr);
900 changeExit(PrevNode, Exit, EntryDominatesExit);
902 assert(EntryDominatesExit);
907 void StructurizeCFG::rebuildSSA() {
911 bool Initialized =
false;
914 for (
auto UI =
I.use_begin(),
E =
I.use_end(); UI !=
E;) {
919 }
else if (
PHINode *UserPN = dyn_cast<PHINode>(User)) {
920 if (UserPN->getIncomingBlock(U) == BB)
924 if (DT->dominates(&
I, User))
942 bool SubRegionsAreUniform =
true;
944 unsigned ConditionalDirectChildren = 0;
947 if (!
E->isSubRegion()) {
949 if (!Br || !Br->isConditional())
956 ConditionalDirectChildren++;
959 <<
" has uniform terminator\n");
972 if (!Br || !Br->isConditional())
975 if (!Br->getMetadata(UniformMDKindID)) {
977 if (!RelaxedUniformRegions)
980 SubRegionsAreUniform =
false;
993 return SubRegionsAreUniform || (ConditionalDirectChildren <= 1);
1003 if (SkipUniformRegions) {
1008 unsigned UniformMDKindID =
1009 R->
getEntry()->getContext().getMDKindID(
"structurizecfg.uniform");
1010 DA = &getAnalysis<LegacyDivergenceAnalysis>();
1013 LLVM_DEBUG(
dbgs() <<
"Skipping region with uniform control flow: " << *R
1022 if (
E->isSubRegion())
1025 if (
Instruction *Term =
E->getEntry()->getTerminator())
1036 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1037 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1042 insertConditions(
false);
1043 insertConditions(
true);
1050 DeletedPhis.clear();
1062 return new StructurizeCFG(SkipUniformRegions);
Pass interface - Implemented by all 'passes'.
T * getNodeAs() const
Get the content of this RegionNode.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
static ConstantInt * getFalse(LLVMContext &Context)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static IntegerType * getInt1Ty(LLVMContext &C)
Helper class for SSA formation on a set of values defined in multiple blocks.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents an incoming formal argument to a Function.
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
This class represents lattice values for constants.
void Initialize(Type *Ty, StringRef Name)
Reset this object to get ready for a new set of SSA updates with type 'Ty'.
void setIncomingValueForBlock(const BasicBlock *BB, Value *V)
Set every incoming value(s) for block BB to V.
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value...
Optional< std::vector< StOtherPiece > > Other
NodeT * findNearestCommonDominator(NodeT *A, NodeT *B) const
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B...
This class implements a map that also provides access to all stored values in a deterministic order...
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
BasicBlock * getSuccessor(unsigned i) const
static const char *const FlowBlockName
Value * getCondition() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
This defines the Use class.
BlockT * getExit() const
Get the exit BasicBlock of the Region.
bool isSubRegion() const
Is this RegionNode a subregion?
LLVMContext & getContext() const
Get the context in which this basic block lives.
The pass manager to schedule RegionPasses.
bool match(Val *V, const Pattern &P)
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
'undef' values are things that do not have specified contents.
unsigned getNumSuccessors() const
A Use represents the edge between a Value definition and its users.
void setName(const Twine &Name)
Change the name of the value.
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
block_range blocks()
Returns a range view of the basic blocks in the region.
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
BlockT * getEntry() const
Get the entry BasicBlock of this RegionNode.
Type * getType() const
All values are typed, get the type of this value.
static bool hasOnlyUniformBranches(Region *R, unsigned UniformMDKindID, const LegacyDivergenceAnalysis &DA)
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Interval::succ_iterator succ_end(Interval *I)
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
const BasicBlock & getEntryBlock() const
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
initializer< Ty > init(const Ty &Val)
Value * GetValueInMiddleOfBlock(BasicBlock *BB)
Construct SSA form, materializing a value that is live in the middle of the specified block...
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
LLVM Basic Block Representation.
The instances of the Type class are immutable: once they are created, they are never changed...
This is an important class for using LLVM in a threaded context.
void RewriteUseAfterInsertions(Use &U)
Rewrite a use like RewriteUse but handling in-block definitions.
Conditional or Unconditional Branch instruction.
A pass that runs on each Region in a function.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
void replaceExit(BlockT *BB)
Replace the exit basic block of the region with the new basic block.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
int getNumOccurrences() const
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Represent the analysis usage information of a pass.
const Instruction & back() const
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Interval::pred_iterator pred_end(Interval *I)
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
static Constant * getNot(Constant *C)
bool isTopLevelRegion() const
Check if a Region is the TopLevel region.
INITIALIZE_PASS_BEGIN(StructurizeCFG, "structurizecfg", "Structurize the CFG", false, false) INITIALIZE_PASS_END(StructurizeCFG
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
void initializeStructurizeCFGPass(PassRegistry &)
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
This is the shared class of boolean and integer constants.
BlockVerifier::State From
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
AnalysisUsage & addRequiredID(const void *ID)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
bool isConditional() const
pred_range predecessors(BasicBlock *BB)
static ConstantInt * getTrue(LLVMContext &Context)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
iterator_range< user_iterator > users()
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
bool contains(const BlockT *BB) const
Check if the region contains a BasicBlock.
Represents a single loop in the control flow graph.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
void setCondition(Value *V)
RegionT * getParent() const
Get the parent of the Region.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
bool isUniform(const Value *V) const
The legacy pass manager's analysis pass to compute loop information.
StringRef - Represent a constant reference to a string, i.e.
Legacy analysis pass which computes a DominatorTree.
Value * GetValueAtEndOfBlock(BasicBlock *BB)
Construct SSA form, materializing a value that is live at the end of the specified block...
Pass * createStructurizeCFGPass(bool SkipUniformRegions=false)
When SkipUniformRegions is true the structizer will not structurize regions that only contain uniform...
iterator_range< element_iterator > elements()
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
RegionT * getRegionFor(BlockT *BB) const
Get the smallest region that contains a BasicBlock.
BinaryOp_match< ValTy, cst_pred_ty< is_all_ones >, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
const BasicBlock * getParent() const
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.