39#define DEBUG_TYPE "wasm-cfg-sort"
46 "WebAssembly: Disable EH pad-first sort order. Testing purpose only."),
73char WebAssemblyCFGSort::ID = 0;
75 "Reorders blocks in topological order",
false,
false)
78 return new WebAssemblyCFGSort();
83 bool AnyBarrier =
false;
85 bool AllAnalyzable =
true;
88 AnyBarrier |= Term.isBarrier();
90 AllAnalyzable &= Term.isBranch() && !Term.isIndirectBranch();
92 assert((AnyBarrier || AllAnalyzable) &&
93 "analyzeBranch needs to analyze any block with a fallthrough");
141struct CompareBlockNumbers {
145 if (
A->isEHPad() && !
B->isEHPad())
147 if (!
A->isEHPad() &&
B->isEHPad())
151 return A->getNumber() >
B->getNumber();
155struct CompareBlockNumbersBackwards {
159 if (
A->isEHPad() && !
B->isEHPad())
161 if (!
A->isEHPad() &&
B->isEHPad())
165 return A->getNumber() <
B->getNumber();
172 unsigned NumBlocksLeft;
176 std::vector<MachineBasicBlock *> Deferred;
179 : TheRegion(
R), NumBlocksLeft(
R->getNumBlocks()) {}
201 if (L->getHeader() == &
MBB)
203 if (L->contains(Pred))
220 CompareBlockNumbersBackwards>
232 if (R->getHeader() ==
MBB)
233 Entries.push_back(Entry(R));
237 for (Entry &E : Entries)
238 if (E.TheRegion->contains(
MBB) && --E.NumBlocksLeft == 0)
239 for (
auto *DeferredBlock : E.Deferred)
240 Ready.push(DeferredBlock);
241 while (!Entries.empty() && Entries.back().NumBlocksLeft == 0)
248 if (SuccL->getHeader() == Succ && SuccL->contains(
MBB))
251 if (--NumPredsLeft[Succ->getNumber()] == 0) {
263 if (EHInfo && EHInfo->hasUnwindSrcs(Succ)) {
265 EHInfo->getUnwindSrcs(Succ);
266 bool IsDeferred =
false;
267 for (Entry &E : Entries) {
268 if (UnwindSrcs.
count(E.TheRegion->getHeader())) {
269 E.Deferred.push_back(Succ);
277 Preferred.push(Succ);
283 while (!Preferred.empty()) {
284 Next = Preferred.top();
288 if (!Entries.empty() &&
289 !MDT.
dominates(Entries.back().TheRegion->getHeader(), Next)) {
290 Entries.back().Deferred.push_back(Next);
298 (!R || !R->contains(Next) ||
299 R->getHeader()->getNumber() < Next->
getNumber())) {
319 if (!Entries.empty() &&
320 !MDT.
dominates(Entries.back().TheRegion->getHeader(), Next)) {
321 Entries.back().Deferred.push_back(Next);
332 assert(Entries.empty() &&
"Active sort region list not finished");
344 for (
auto &
MBB : MF) {
356 "Loop header predecessors must be loop predecessors or "
362 "Non-loop-header predecessors should be topologically sorted");
365 "Regions should be declared at most once.");
371 "Non-loop-header predecessors should be topologically sorted");
373 "Blocks must be nested in their regions");
379 "The function entry block shouldn't actually be a region header");
381 "Control flow stack pushes and pops should be balanced.");
387 "********** Function: "
390 const auto &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
391 const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
392 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
This file defines the PriorityQueue class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
static void sortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI, const WebAssemblyExceptionInfo &WEI, MachineDominatorTree &MDT)
Sort the blocks, taking special care to make sure that regions are not interrupted by blocks not domi...
static void maybeUpdateTerminator(MachineBasicBlock *MBB)
static cl::opt< bool > WasmDisableEHPadSort("wasm-disable-ehpad-sort", cl::ReallyHidden, cl::desc("WebAssembly: Disable EH pad-first sort order. Testing purpose only."), cl::init(false))
This file implements WebAssemblyException information analysis.
This file provides WebAssembly-specific target descriptions.
This file implements regions used in CFGSort and CFGStackify.
This file declares the WebAssembly-specific subclass of TargetSubtarget.
This file contains the declaration of the WebAssembly-specific utility functions.
This file contains the entry points for global functions defined in the LLVM WebAssembly back-end.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
std::enable_if_t< GraphHasNodeNumbers< T * >, void > updateBlockNumbers()
Update dominator tree after renumbering blocks.
FunctionPass class - This class is used to implement most global optimizations.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
unsigned pred_size() const
bool isEHPad() const
Returns true if the block is a landing pad.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
void updateTerminator(MachineBasicBlock *PreviousLayoutSuccessor)
Update the terminator instructions in block to account for changes to block layout which may have bee...
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< iterator > terminators()
iterator_range< succ_iterator > successors()
iterator_range< pred_iterator > predecessors()
void moveAfter(MachineBasicBlock *NewBefore)
Analysis pass which computes a MachineDominatorTree.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
const WasmEHFuncInfo * getWasmEHFuncInfo() const
getWasmEHFuncInfo - Return information about how the current function uses Wasm exception handling.
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.
const MachineBasicBlock & front() const
Representation of each machine instruction.
void invalidateLiveness()
invalidateLiveness - Indicates that register liveness is no longer being tracked accurately.
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
PriorityQueue - This class behaves like std::priority_queue and provides a few additional convenience...
bool contains(const BlockT *BB) const
Check if the region contains a BasicBlock.
size_type size() const
Determine the number of elements in the SetVector.
const value_type & back() const
Return the last element of the SetVector.
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
void pop_back()
Remove the last element of the SetVector.
value_type pop_back_val()
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
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 is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
const SortRegion * getRegionFor(const MachineBasicBlock *MBB)
MachineBasicBlock * getBottom(const SortRegion *R)
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
FunctionPass * createWebAssemblyCFGSort()