44#ifndef LLVM_ADT_GENERICUNIFORMITYIMPL_H
45#define LLVM_ADT_GENERICUNIFORMITYIMPL_H
57#define DEBUG_TYPE "uniformity"
92 using BlockT =
typename ContextT::BlockT;
101 bool empty()
const {
return Order.empty(); }
102 size_t size()
const {
return Order.size(); }
109 return Num < POIndex.size() && POIndex[Num] != InvalidIndex;
115 POIndex[Num] = Order.size();
116 Order.push_back(&BB);
118 <<
"): " << Context.print(&BB) <<
"\n");
119 if (IsReducibleCycleHeader)
120 ReducibleCycleHeaders.insert(&BB);
125 assert(Num < POIndex.size() && POIndex[Num] != InvalidIndex);
130 return ReducibleCycleHeaders.contains(BB);
139 const ContextT &Context;
149template <
typename>
class DivergencePropagator;
271 using BlockT =
typename ContextT::BlockT;
327 CachedControlDivDescs;
338 using BlockT =
typename ContextT::BlockT;
342 using UseT =
typename ContextT::UseT;
350 typename SyncDependenceAnalysisT::DivergenceDescriptor;
354 std::tuple<ConstValueRefT, InstructionT *, CycleRef>;
393 assert(
I.isTerminator() &&
"Expected a terminator instruction!");
408 if (ContextT::isAlwaysUniform(V))
485 void taintAndPushAllDefs(
const BlockT &JoinBlock);
489 void taintAndPushPhiNodes(
const BlockT &JoinBlock);
494 void propagateCycleExitDivergence(
const BlockT &DivExit,
CycleRef DivCycle);
497 void analyzeCycleExitDivergence(
CycleRef DefCycle);
509 bool isTemporalDivergent(
const BlockT &ObservingBlock,
513template <
typename ImplT>
521 using BlockT =
typename ContextT::BlockT;
531 typename SyncDependenceAnalysisT::DivergenceDescriptor;
547 std::unique_ptr<DivergenceDescriptorT>
DivDesc;
557 Out <<
"Propagator::BlockLabels {\n";
558 for (
int BlockIdx = (
int)
CyclePOT.size() - 1; BlockIdx >= 0; --BlockIdx) {
561 Out <<
Context.print(
Block) <<
"(" << BlockIdx <<
") : ";
565 Out <<
Context.print(Label) <<
"\n";
577 <<
"\tpushed label: " <<
Context.print(&PushedLabel)
579 <<
"\told label: " <<
Context.print(OldLabel) <<
"\n");
582 if (OldLabel == &PushedLabel)
585 if (OldLabel != &SuccBlock) {
586 auto SuccIdx =
CyclePOT.getIndex(&SuccBlock);
615 DivDesc->CycleDivBlocks.insert(&ExitBlock);
627 DivDesc->JoinDivBlocks.insert(&SuccBlock);
648 if (
CI.isReducible(
C))
651 if (
CI.isReducible(
P))
662 if (DivTermCycle && !
CI.contains(DivTermCycle, SuccBlock)) {
666 DivDesc->CycleDivBlocks.insert(SuccBlock);
668 <<
Context.print(SuccBlock) <<
"\n");
687 (!IrreducibleAncestor || !
CI.contains(IrreducibleAncestor,
Block)))
693 if (BlockIdx == DivTermIdx) {
699 << BlockIdx <<
"\n");
724 CI.getExitBlocks(BlockCycle, BlockCycleExits);
726 for (
auto *BlockCycleExit : BlockCycleExits) {
744 if (
CI.isReducible(
C)) {
750 CI.getExitBlocks(
C, Exits);
751 auto *Header =
CI.getHeader(
C);
753 for (
const auto *Exit : Exits) {
756 DivDesc->CycleDivBlocks.insert(Exit);
767template <
typename ContextT>
770 : CyclePO(Context), DT(DT), CI(CI) {
774template <
typename ContextT>
779 return EmptyDivergenceDesc;
783 auto ItCached = CachedControlDivDescs.find(DivTermBlock);
784 if (ItCached != CachedControlDivDescs.end())
785 return *ItCached->second;
795 for (
const auto *BB : Blocks) {
796 Out << LS << CI.getSSAContext().print(BB);
803 dbgs() <<
"\nResult (" << CI.getSSAContext().print(DivTermBlock)
804 <<
"):\n JoinDivBlocks: " << PrintBlockSet(DivDesc->JoinDivBlocks)
805 <<
" CycleDivBlocks: " << PrintBlockSet(DivDesc->CycleDivBlocks)
810 CachedControlDivDescs.try_emplace(DivTermBlock, std::move(DivDesc));
811 assert(ItInserted.second);
812 return *ItInserted.first->second;
815template <
typename ContextT>
828 if (
I.isTerminator()) {
832 <<
Context.print(
I.getParent()) <<
"\n");
842template <
typename ContextT>
852template <
typename ContextT>
855 UniformOverrides.insert(&Instr);
858template <
typename ContextT>
877template <
typename ContextT>
878void GenericUniformityAnalysisImpl<ContextT>::analyzeCycleExitDivergence(
881 CI.getExitBlocks(DefCycle, Exits);
882 for (
auto *Exit : Exits) {
883 for (
auto &Phi : Exit->phis()) {
884 if (usesValueFromCycle(Phi, DefCycle)) {
890 for (
auto *BB : CI.getBlocks(DefCycle)) {
892 [&](BlockT *Exit) {
return DT.dominates(BB, Exit); }))
894 for (
auto &
II : *BB) {
895 propagateTemporalDivergence(
II, DefCycle);
900template <
typename ContextT>
901void GenericUniformityAnalysisImpl<ContextT>::propagateCycleExitDivergence(
902 const BlockT &DivExit,
CycleRef InnerDivCycle) {
907 CycleRef ExitLevelCycle = CI.getCycle(&DivExit);
908 const unsigned CycleExitDepth =
909 ExitLevelCycle ? CI.getDepth(ExitLevelCycle) : 0;
912 while (DivCycle && CI.getDepth(DivCycle) > CycleExitDepth) {
914 <<
Context.print(CI.getHeader(DivCycle)) <<
"\n");
915 OuterDivCycle = DivCycle;
916 DivCycle = CI.getParentCycle(DivCycle);
919 <<
Context.print(CI.getHeader(OuterDivCycle)) <<
"\n");
921 if (!DivergentExitCycles.insert(OuterDivCycle))
926 for (
auto C : AssumedDivergent) {
927 if (CI.contains(
C, OuterDivCycle))
931 analyzeCycleExitDivergence(OuterDivCycle);
934template <
typename ContextT>
935void GenericUniformityAnalysisImpl<ContextT>::taintAndPushAllDefs(
938 for (
const auto &
I :
instrs(BB)) {
942 if (
I.isTerminator())
950template <
typename ContextT>
951void GenericUniformityAnalysisImpl<ContextT>::taintAndPushPhiNodes(
952 const BlockT &JoinBlock) {
955 for (
const auto &Phi : JoinBlock.phis()) {
963 if (ContextT::isConstantOrUndefValuePhi(Phi))
972template <
typename CycleInfoT>
976 [&](
CycleRef C) {
return CI.contains(
C, Candidate); }))
978 Cycles.push_back(Candidate);
987template <
typename CycleInfoT,
typename BlockT>
989 const BlockT *DivTermBlock,
const BlockT *JoinBlock) {
991 assert(CI.contains(Cycle, JoinBlock));
993 if (CI.contains(Cycle, DivTermBlock))
997 CycleRef Parent = CI.getParentCycle(Cycle);
998 while (Parent && !CI.contains(Parent, DivTermBlock)) {
1000 Parent = CI.getParentCycle(Cycle);
1006 (void)OriginalCycle;
1007 assert(Cycle == OriginalCycle || !CI.isReducible(Cycle));
1009 if (CI.isReducible(Cycle)) {
1010 assert(CI.getHeader(Cycle) == JoinBlock);
1014 LLVM_DEBUG(
dbgs() <<
"cycle made divergent by external branch\n");
1022template <
typename ContextT,
typename CycleInfoT,
typename BlockT,
1023 typename DominatorTreeT>
1025 const BlockT *DivTermBlock,
const BlockT *JoinBlock,
1026 const DominatorTreeT &DT, ContextT &Context) {
1028 <<
" for internal branch " << Context.print(DivTermBlock)
1030 if (DT.properlyDominates(DivTermBlock, JoinBlock))
1034 assert(Cycle && CI.contains(Cycle, JoinBlock));
1035 while (Cycle && !CI.contains(Cycle, DivTermBlock)) {
1036 Cycle = CI.getParentCycle(Cycle);
1038 if (!Cycle || CI.isReducible(Cycle))
1041 if (DT.properlyDominates(CI.getHeader(Cycle), JoinBlock))
1044 LLVM_DEBUG(
dbgs() <<
" header " << Context.print(CI.getHeader(Cycle))
1045 <<
" does not dominate join\n");
1047 CycleRef Parent = CI.getParentCycle(Cycle);
1048 while (Parent && !DT.properlyDominates(CI.getHeader(Parent), JoinBlock)) {
1049 LLVM_DEBUG(
dbgs() <<
" header " << Context.print(CI.getHeader(Parent))
1050 <<
" does not dominate join\n");
1052 Parent = CI.getParentCycle(Parent);
1055 LLVM_DEBUG(
dbgs() <<
" cycle made divergent by internal branch\n");
1059template <
typename ContextT,
typename CycleInfoT,
typename BlockT,
1060 typename DominatorTreeT>
1063 const BlockT *DivTermBlock,
const BlockT *JoinBlock,
1064 const DominatorTreeT &DT, ContextT &Context) {
1081template <
typename ContextT>
1082bool GenericUniformityAnalysisImpl<ContextT>::isTemporalDivergent(
1083 const BlockT &ObservingBlock,
const InstructionT &Def)
const {
1084 const BlockT *DefBlock = Def.getParent();
1085 for (
auto C = CI.getCycle(DefBlock);
C && !CI.contains(
C, &ObservingBlock);
1086 C = CI.getParentCycle(
C)) {
1087 if (DivergentExitCycles.contains(
C)) {
1094template <
typename ContextT>
1097 const auto *DivTermBlock = Term.getParent();
1103 if (!DT.isReachableFromEntry(DivTermBlock))
1106 const auto &DivDesc = SDA.getJoinBlocks(DivTermBlock);
1110 for (
const auto *JoinBlock : DivDesc.JoinDivBlocks) {
1115 CI,
C, DivTermBlock, JoinBlock, DT,
Context)) {
1120 taintAndPushPhiNodes(*JoinBlock);
1126 return CI.getDepth(
A) >
CI.getDepth(
B);
1134 for (
auto C : DivCycles) {
1138 for (
const BlockT *BB :
CI.getBlocks(
C)) {
1139 taintAndPushAllDefs(*BB);
1143 CycleRef BranchCycle =
CI.getCycle(DivTermBlock);
1144 assert(DivDesc.CycleDivBlocks.empty() || BranchCycle);
1145 for (
const auto *DivExitBlock : DivDesc.CycleDivBlocks) {
1146 propagateCycleExitDivergence(*DivExitBlock, BranchCycle);
1150template <
typename ContextT>
1162 if (
I->isTerminator()) {
1173template <
typename ContextT>
1179template <
typename ContextT>
1182 return UniformOverrides.contains(&Instr);
1185template <
typename ContextT>
1191template <
typename ContextT>
1195 DA.reset(
new ImplT{DT, CI,
TTI});
1198template <
typename ContextT>
1203 constexpr bool IsMIR = std::is_same<InstructionT, MachineInstr>::value;
1204 std::string NewLine = IsMIR ?
"" :
"\n";
1206 bool FoundDivergence =
false;
1210 if (!AssumedDivergent.empty()) {
1211 FoundDivergence =
true;
1212 OS <<
"CYCLES ASSUMED DIVERGENT:\n";
1213 for (
auto C : AssumedDivergent) {
1214 OS <<
" " <<
CI.print(
C) <<
'\n';
1218 if (!DivergentExitCycles.empty()) {
1219 FoundDivergence =
true;
1220 OS <<
"CYCLES WITH DIVERGENT EXIT:\n";
1221 for (
auto C : DivergentExitCycles) {
1222 OS <<
" " <<
CI.print(
C) <<
'\n';
1227 FoundDivergence =
true;
1228 OS <<
"\nTEMPORAL DIVERGENCE LIST:\n";
1231 OS <<
"Value :" <<
Context.print(Val) << NewLine
1232 <<
"Used by :" <<
Context.print(UseInst) << NewLine
1233 <<
"Outside cycle :" <<
CI.print(
C) <<
"\n\n";
1240 OS <<
"DEFINITIONS\n";
1243 for (
auto Value : Defs) {
1245 FoundDivergence =
true;
1246 OS <<
" DIVERGENT: ";
1253 OS <<
"TERMINATORS\n";
1257 if (DivergentTerminators)
1258 FoundDivergence =
true;
1259 for (
auto *
T : Terms) {
1260 if (DivergentTerminators)
1261 OS <<
" DIVERGENT: ";
1267 OS <<
"END BLOCK\n";
1270 if (!FoundDivergence)
1271 OS <<
"ALL VALUES UNIFORM\n";
1274template <
typename ContextT>
1278 return make_range(DA->TemporalDivergenceList.begin(),
1279 DA->TemporalDivergenceList.end());
1282template <
typename ContextT>
1283const typename ContextT::FunctionT &
1285 return DA->getFunction();
1288template <
typename ContextT>
1291 return DA->getCycleInfo();
1297template <
typename ContextT>
1299 return DA && DA->isDivergent(V);
1302template <
typename ContextT>
1305 assert(
I->isTerminator() &&
"Expected a terminator instruction!");
1306 return DA && DA->isDivergentTerminator(*
I);
1309template <
typename ContextT>
1311 return DA && DA->isDivergentUse(U);
1314template <
typename ContextT>
1316 return DA && DA->hasDivergentTerminator(
B);
1320template <
typename ContextT>
1323 Out <<
" Uniformity analysis not computed (no branch divergence).\n";
1329template <
typename ContextT>
1330void llvm::ModifiedPostOrder<ContextT>::computeStackPO(
1334 while (!Stack.empty()) {
1335 auto *NextBB = Stack.back();
1336 if (Finalized.
count(NextBB)) {
1340 LLVM_DEBUG(
dbgs() <<
" visiting " << CI.getSSAContext().print(NextBB)
1342 CycleRef NestedCycle = CI.getCycle(NextBB);
1343 if (
C != NestedCycle &&
1344 (!
C || (NestedCycle && CI.contains(
C, NestedCycle)))) {
1346 while (CI.getParentCycle(NestedCycle) !=
C)
1347 NestedCycle = CI.getParentCycle(NestedCycle);
1350 CI.getExitBlocks(NestedCycle, NestedExits);
1351 bool PushedNodes =
false;
1352 for (
auto *NestedExitBB : NestedExits) {
1354 << CI.getSSAContext().print(NestedExitBB) <<
"\n");
1355 if (
C && !CI.contains(
C, NestedExitBB))
1357 if (Finalized.
count(NestedExitBB))
1360 Stack.push_back(NestedExitBB);
1362 << CI.getSSAContext().print(NestedExitBB) <<
"\n");
1367 computeCyclePO(CI, NestedCycle, Finalized);
1374 bool PushedNodes =
false;
1377 << CI.getSSAContext().print(SuccBB) <<
"\n");
1378 if (
C && !CI.contains(
C, SuccBB))
1380 if (Finalized.
count(SuccBB))
1383 Stack.push_back(SuccBB);
1384 LLVM_DEBUG(
dbgs() <<
" pushed succ: " << CI.getSSAContext().print(SuccBB)
1390 << CI.getSSAContext().print(NextBB) <<
"\n");
1392 Finalized.
insert(NextBB);
1393 appendBlock(*NextBB);
1399template <
typename ContextT>
1400void ModifiedPostOrder<ContextT>::computeCyclePO(
1405 auto *CycleHeader = CI.getHeader(
C);
1408 << CI.getSSAContext().print(CycleHeader) <<
"\n");
1409 assert(!Finalized.count(CycleHeader));
1410 Finalized.insert(CycleHeader);
1414 << CI.getSSAContext().print(CycleHeader) <<
"\n");
1415 appendBlock(*CycleHeader, CI.isReducible(
C));
1419 LLVM_DEBUG(
dbgs() <<
" examine succ: " << CI.getSSAContext().print(BB)
1421 if (!CI.contains(
C, BB))
1423 if (BB == CycleHeader)
1425 if (!Finalized.count(BB)) {
1426 LLVM_DEBUG(
dbgs() <<
" pushed succ: " << CI.getSSAContext().print(BB)
1428 Stack.push_back(BB);
1433 computeStackPO(Stack, CI,
C, Finalized);
1439template <
typename ContextT>
1443 auto *
F = CI.getFunction();
1446 Stack.push_back(&
F->front());
1447 computeStackPO(Stack, CI,
CycleRef(), Finalized);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file defines the DenseSet and SmallDenseSet classes.
uint64_t IntrinsicInst * II
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SparseBitVector class.
static const unsigned InvalidIndex
Opaque handle to a cycle within a GenericCycleInfo that wraps the cycle's preorder index.
Implements a dense probed hash-table based set.
Compute divergence starting with a divergent branch.
typename SyncDependenceAnalysisT::BlockLabelMap BlockLabelMapT
const ModifiedPO & CyclePOT
GenericSyncDependenceAnalysis< ContextT > SyncDependenceAnalysisT
typename ContextT::DominatorTreeT DominatorTreeT
bool computeJoin(const BlockT &SuccBlock, const BlockT &PushedLabel)
const BlockT & DivTermBlock
std::unique_ptr< DivergenceDescriptorT > DivDesc
void printDefs(raw_ostream &Out)
typename ContextT::FunctionT FunctionT
GenericCycleInfo< ContextT > CycleInfoT
const DominatorTreeT & DT
ModifiedPostOrder< ContextT > ModifiedPO
std::unique_ptr< DivergenceDescriptorT > computeJoinPoints()
BlockLabelMapT & BlockLabels
SparseBitVector FreshLabels
bool visitCycleExitEdge(const BlockT &ExitBlock, const BlockT &Label)
typename ContextT::ValueRefT ValueRefT
typename ContextT::BlockT BlockT
DivergencePropagator(const ModifiedPO &CyclePOT, const DominatorTreeT &DT, const CycleInfoT &CI, const BlockT &DivTermBlock)
bool visitEdge(const BlockT &SuccBlock, const BlockT &Label)
typename SyncDependenceAnalysisT::DivergenceDescriptor DivergenceDescriptorT
Cycle information for a function.
Locate join blocks for disjoint paths starting at a divergent branch.
GenericSyncDependenceAnalysis(const ContextT &Context, const DominatorTreeT &DT, const CycleInfoT &CI)
ModifiedPostOrder< ContextT > ModifiedPO
DivergencePropagator< ContextT > DivergencePropagatorT
DenseMap< const BlockT *, const BlockT * > BlockLabelMap
SmallPtrSet< const BlockT *, 4 > ConstBlockSet
typename ContextT::DominatorTreeT DominatorTreeT
GenericCycleInfo< ContextT > CycleInfoT
typename ContextT::FunctionT FunctionT
typename ContextT::InstructionT InstructionT
typename ContextT::BlockT BlockT
typename ContextT::ValueRefT ValueRefT
const DivergenceDescriptor & getJoinBlocks(const BlockT *DivTermBlock)
Computes divergent join points and cycle exits caused by branch divergence in Term.
A helper class to return the specified delimiter string after the first invocation of operator String...
Construct a specially modified post-order traversal of cycles.
typename ContextT::FunctionT FunctionT
bool isReducibleCycleHeader(const BlockT *BB) const
void appendBlock(const BlockT &BB, bool IsReducibleCycleHeader=false)
const BlockT * operator[](size_t Idx) const
ModifiedPostOrder(const ContextT &C)
unsigned count(BlockT *BB) const
void compute(const CycleInfoT &CI)
Generically compute the modified post order.
GenericCycleInfo< ContextT > CycleInfoT
unsigned getIndex(const BlockT *BB) const
typename std::vector< BlockT * >::const_iterator const_iterator
typename ContextT::DominatorTreeT DominatorTreeT
typename ContextT::BlockT BlockT
Simple wrapper around std::function<void(raw_ostream&)>.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
LLVM Value Representation.
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
@ C
The default llvm calling convention, compatible with C.
This is an optimization pass for GlobalISel generic memory operations.
bool insertIfNotContained(const CycleInfoT &CI, SmallVector< CycleRef > &Cycles, CycleRef Candidate)
Add Candidate to Cycles if it is not already contained in Cycles.
CycleRef getExtDivCycle(const CycleInfoT &CI, CycleRef Cycle, const BlockT *DivTermBlock, const BlockT *JoinBlock)
Return the outermost cycle made divergent by branch outside it.
auto successors(const MachineBasicBlock *BB)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
CycleRef getOutermostDivergentCycle(const CycleInfoT &CI, CycleRef Cycle, const BlockT *DivTermBlock, const BlockT *JoinBlock, const DominatorTreeT &DT, ContextT &Context)
void sort(IteratorTy Start, IteratorTy End)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
auto succ_size(const MachineBasicBlock *BB)
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
auto instrs(const MachineBasicBlock &BB)
CycleRef getIntDivCycle(const CycleInfoT &CI, CycleRef Cycle, const BlockT *DivTermBlock, const BlockT *JoinBlock, const DominatorTreeT &DT, ContextT &Context)
Return the outermost cycle made divergent by branch inside it.
Information discovered by the sync dependence analysis for each divergent branch.
ConstBlockSet CycleDivBlocks
ConstBlockSet JoinDivBlocks
BlockLabelMap BlockLabels