36 #define DEBUG_TYPE "wasm-cfg-sort" 46 virtual unsigned getNumBlocks()
const = 0;
49 virtual bool isLoop()
const = 0;
52 template <
typename T>
class ConcreteRegion :
public Region {
56 ConcreteRegion(
const T *Region) :
Region(Region) {}
59 return Region->contains(MBB);
61 unsigned getNumBlocks()
const override {
return Region->getNumBlocks(); }
63 return Region->blocks();
65 bool isLoop()
const override {
return false; }
68 template <>
bool ConcreteRegion<MachineLoop>::isLoop()
const {
return true; }
75 std::vector<const Region *> Regions;
81 : MLI(MLI), WEI(WEI) {}
89 if ((ML && !WE) || (ML && WE && ML->getNumBlocks() < WE->getNumBlocks())) {
91 if (LoopMap.
count(ML))
92 return LoopMap[ML].
get();
93 LoopMap[ML] = llvm::make_unique<ConcreteRegion<MachineLoop>>(ML);
94 return LoopMap[ML].get();
97 if (ExceptionMap.
count(WE))
98 return ExceptionMap[WE].
get();
100 llvm::make_unique<ConcreteRegion<WebAssemblyException>>(WE);
101 return ExceptionMap[WE].get();
107 StringRef getPassName()
const override {
return "WebAssembly CFG Sort"; }
130 "Reorders blocks in topological order",
false,
false)
133 return new WebAssemblyCFGSort();
138 bool AnyBarrier =
false;
140 bool AllAnalyzable =
true;
143 AnyBarrier |= Term.isBarrier();
145 AllAnalyzable &= Term.isBranch() && !Term.isIndirectBranch();
147 assert((AnyBarrier || AllAnalyzable) &&
148 "AnalyzeBranch needs to analyze any block with a fallthrough");
188 struct CompareBlockNumbers {
200 struct CompareBlockNumbersBackwards {
216 unsigned NumBlocksLeft;
220 std::vector<MachineBasicBlock *> Deferred;
222 explicit Entry(
const class Region *R)
223 : TheRegion(R), NumBlocksLeft(R->getNumBlocks()) {}
239 unsigned N = MBB.pred_size();
241 if (L->getHeader() == &MBB)
243 if (L->contains(Pred))
245 NumPredsLeft[MBB.getNumber()] =
N;
260 CompareBlockNumbersBackwards>
271 if (R->getHeader() == MBB)
276 for (Entry &
E : Entries)
277 if (
E.TheRegion->contains(MBB) && --
E.NumBlocksLeft == 0)
278 for (
auto DeferredBlock :
E.Deferred)
279 Ready.push(DeferredBlock);
280 while (!Entries.empty() && Entries.back().NumBlocksLeft == 0)
287 if (SuccL->getHeader() == Succ && SuccL->contains(MBB))
290 if (--NumPredsLeft[Succ->getNumber()] == 0)
291 Preferred.push(Succ);
296 while (!Preferred.empty()) {
297 Next = Preferred.top();
301 if (!Entries.
empty() &&
302 !MDT.
dominates(Entries.
back().TheRegion->getHeader(), Next)) {
303 Entries.
back().Deferred.push_back(Next);
309 if (Next->
getNumber() < MBB->getNumber() &&
311 R->getHeader()->getNumber() < Next->
getNumber())) {
331 if (!Entries.
empty() &&
332 !MDT.
dominates(Entries.
back().TheRegion->getHeader(), Next)) {
333 Entries.
back().Deferred.push_back(Next);
344 assert(Entries.
empty() &&
"Active sort region list not finished");
355 for (
auto &MBB : MF) {
356 assert(MBB.getNumber() >= 0 &&
"Renumbered blocks should be non-negative.");
359 if (Region && &MBB == Region->getHeader()) {
360 if (Region->isLoop()) {
363 for (
auto Pred : MBB.predecessors())
365 (Pred->getNumber() < MBB.getNumber() || Region->contains(Pred)) &&
366 "Loop header predecessors must be loop predecessors or " 370 for (
auto Pred : MBB.predecessors())
371 assert(Pred->getNumber() < MBB.getNumber() &&
372 "Non-loop-header predecessors should be topologically sorted");
375 "Regions should be declared at most once.");
379 for (
auto Pred : MBB.predecessors())
380 assert(Pred->getNumber() < MBB.getNumber() &&
381 "Non-loop-header predecessors should be topologically sorted");
383 "Blocks must be nested in their regions");
389 "The function entry block shouldn't actually be a region header");
391 "Control flow stack pushes and pops should be balanced.");
397 "********** Function: " 400 const auto &MLI = getAnalysis<MachineLoopInfo>();
401 const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
402 auto &MDT = getAnalysis<MachineDominatorTree>();
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
LLVM_NODISCARD T pop_back_val()
This class represents lattice values for constants.
FunctionPass * createWebAssemblyCFGSort()
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them...
size_type size() const
Determine the number of elements in the SetVector.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
void push_back(const T &Elt)
INITIALIZE_PASS(WebAssemblyCFGSort, DEBUG_TYPE, "Reorders blocks in topological order", false, false) FunctionPass *llvm
void moveAfter(MachineBasicBlock *NewBefore)
const T & back() const
Return the last element of the SetVector.
This file contains the entry points for global functions defined in the LLVM WebAssembly back-end...
iterator_range< succ_iterator > successors()
AnalysisUsage & addRequired()
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
static void SortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI, const WebAssemblyExceptionInfo &WEI, const MachineDominatorTree &MDT)
Sort the blocks, taking special care to make sure that regions are not interrupted by blocks not domi...
iterator_range< iterator > terminators()
void pop_back()
Remove the last element of the SetVector.
block_range blocks()
Returns a range view of the basic blocks in the region.
bool insert(const value_type &X)
Insert a new element into the SetVector.
Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo *RI, DominatorTree *DT, Region *Parent=nullptr)
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
This file implements WebAssemblyException information analysis.
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
This file contains the declaration of the WebAssembly-specific utility functions. ...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file provides WebAssembly-specific target descriptions.
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
iterator_range< pred_iterator > predecessors()
WebAssemblyException * getExceptionFor(const MachineBasicBlock *MBB) const
This file declares the WebAssembly-specific subclass of TargetSubtarget.
A SetVector that performs no allocations if smaller than a certain size.
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
void updateTerminator()
Update the terminator instructions in block to account for changes to the layout. ...
void setPreservesCFG()
This function should be called by the pass, iff they do not:
void invalidateLiveness()
invalidateLiveness - Indicates that register liveness is no longer being tracked accurately.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
A range adaptor for a pair of iterators.
Representation of each machine instruction.
bool contains(const BlockT *BB) const
Check if the region contains a BasicBlock.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
bool isEHPad() const
Returns true if the block is a landing pad.
LLVM_NODISCARD bool empty() const
bool empty() const
Determine if the SetVector is empty or not.
block_iterator_wrapper< false > block_iterator
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
static void MaybeUpdateTerminator(MachineBasicBlock *MBB)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineBasicBlock * getBottom(const T *Unit)
Return the "bottom" block of an entity, which can be either a MachineLoop or WebAssemblyException.
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
StringRef - Represent a constant reference to a string, i.e.
PriorityQueue - This class behaves like std::priority_queue and provides a few additional convenience...
RegionT * getRegionFor(BlockT *BB) const
Get the smallest region that contains a BasicBlock.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...