WebAssemblyCFGSort.cpp Source File (original) (raw)

33using namespace llvm;

37#define DEBUG_TYPE "wasm-cfg-sort"

44 "WebAssembly: Disable EH pad-first sort order. Testing purpose only."),

47namespace {

50 StringRef getPassName() const override { return "WebAssembly CFG Sort"; }

52 void getAnalysisUsage(AnalysisUsage &AU) const override {

54 AU.addRequired();

55 AU.addPreserved();

56 AU.addRequired();

57 AU.addPreserved();

58 AU.addRequired();

61 }

63 bool runOnMachineFunction(MachineFunction &MF) override;

65public:

66 static char ID;

67 WebAssemblyCFGSort() : MachineFunctionPass(ID) {}

68};

69}

71char WebAssemblyCFGSort::ID = 0;

73 "Reorders blocks in topological order", false, false)

76 return new WebAssemblyCFGSort();

77}

80#ifndef NDEBUG

81 bool AnyBarrier = false;

82#endif

83 bool AllAnalyzable = true;

85#ifndef NDEBUG

86 AnyBarrier |= Term.isBarrier();

87#endif

88 AllAnalyzable &= Term.isBranch() && !Term.isIndirectBranch();

89 }

90 assert((AnyBarrier || AllAnalyzable) &&

91 "analyzeBranch needs to analyze any block with a fallthrough");

98 : nullptr;

100 if (AllAnalyzable)

101 MBB->updateTerminator(OriginalSuccessor);

102}

103

104namespace {

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139struct CompareBlockNumbers {

140 bool operator()(const MachineBasicBlock *A,

141 const MachineBasicBlock *B) const {

143 if (A->isEHPad() && ->isEHPad())

144 return false;

145 if (->isEHPad() && B->isEHPad())

146 return true;

147 }

148

149 return A->getNumber() > B->getNumber();

150 }

151};

152

153struct CompareBlockNumbersBackwards {

154 bool operator()(const MachineBasicBlock *A,

155 const MachineBasicBlock *B) const {

157 if (A->isEHPad() && ->isEHPad())

158 return false;

159 if (->isEHPad() && B->isEHPad())

160 return true;

161 }

162

163 return A->getNumber() < B->getNumber();

164 }

165};

166

167

168struct Entry {

169 const SortRegion *TheRegion;

170 unsigned NumBlocksLeft;

171

172

173

174 std::vector<MachineBasicBlock *> Deferred;

175

176 explicit Entry(const SortRegion *R)

177 : TheRegion(R), NumBlocksLeft(R->getNumBlocks()) {}

178};

179}

180

181

182

183

184

188

189

192

193

194

197 unsigned N = MBB.pred_size();

199 if (L->getHeader() == &MBB)

201 if (L->contains(Pred))

202 --N;

203 NumPredsLeft[MBB.getNumber()] = N;

204 }

205

206

207

208

209

210

211

212

213

215 CompareBlockNumbers>

216 Preferred;

218 CompareBlockNumbersBackwards>

219 Ready;

220

222 SortRegionInfo SRI(MLI, WEI);

225 const SortRegion *R = SRI.getRegionFor(MBB);

226 if (R) {

227

228

229

230 if (R->getHeader() == MBB)

232

233

234

235 for (Entry &E : Entries)

236 if (E.TheRegion->contains(MBB) && --E.NumBlocksLeft == 0)

237 for (auto *DeferredBlock : E.Deferred)

238 Ready.push(DeferredBlock);

239 while (!Entries.empty() && Entries.back().NumBlocksLeft == 0)

240 Entries.pop_back();

241 }

242

244

246 if (SuccL->getHeader() == Succ && SuccL->contains(MBB))

247 continue;

248

249 if (--NumPredsLeft[Succ->getNumber()] == 0) {

250

251

252

253

254

255

256

257

258

259

260

261 if (EHInfo && EHInfo->hasUnwindSrcs(Succ)) {

263 EHInfo->getUnwindSrcs(Succ);

264 bool IsDeferred = false;

265 for (Entry &E : Entries) {

266 if (UnwindSrcs.count(E.TheRegion->getHeader())) {

267 E.Deferred.push_back(Succ);

268 IsDeferred = true;

269 break;

270 }

271 }

272 if (IsDeferred)

273 continue;

274 }

275 Preferred.push(Succ);

276 }

277 }

278

279

281 while (!Preferred.empty()) {

282 Next = Preferred.top();

283 Preferred.pop();

284

285

286 if (!Entries.empty() &&

288 Entries.back().Deferred.push_back(Next);

289 Next = nullptr;

290 continue;

291 }

292

293

294 if (Next->getNumber() < MBB->getNumber() &&

296 (!R || !R->contains(Next) ||

297 R->getHeader()->getNumber() < Next->getNumber())) {

298 Ready.push(Next);

299 Next = nullptr;

300 continue;

301 }

302 break;

303 }

304

305

307

308 if (Ready.empty()) {

310 break;

311 }

312 for (;;) {

313 Next = Ready.top();

314 Ready.pop();

315

316

317 if (!Entries.empty() &&

319 Entries.back().Deferred.push_back(Next);

320 continue;

321 }

322 break;

323 }

324 }

325

329 }

330 assert(Entries.empty() && "Active sort region list not finished");

333

334#ifndef NDEBUG

336

337

338

339

340 OnStack.insert(nullptr);

341

342 for (auto &MBB : MF) {

343 assert(MBB.getNumber() >= 0 && "Renumbered blocks should be non-negative.");

344 const SortRegion *Region = SRI.getRegionFor(&MBB);

345

347

348 if (Region->isLoop()) {

349

350

351 for (auto *Pred : MBB.predecessors())

353 (Pred->getNumber() < MBB.getNumber() || Region->contains(Pred)) &&

354 "Loop header predecessors must be loop predecessors or "

355 "backedges");

356 } else {

357

358 for (auto *Pred : MBB.predecessors())

359 assert(Pred->getNumber() < MBB.getNumber() &&

360 "Non-loop-header predecessors should be topologically sorted");

361 }

363 "Regions should be declared at most once.");

364

365 } else {

366

367 for (auto *Pred : MBB.predecessors())

368 assert(Pred->getNumber() < MBB.getNumber() &&

369 "Non-loop-header predecessors should be topologically sorted");

371 "Blocks must be nested in their regions");

372 }

373 while (OnStack.size() > 1 && &MBB == SRI.getBottom(OnStack.back()))

375 }

377 "The function entry block shouldn't actually be a region header");

379 "Control flow stack pushes and pops should be balanced.");

380#endif

381}

382

383bool WebAssemblyCFGSort::runOnMachineFunction(MachineFunction &MF) {

384 LLVM_DEBUG(dbgs() << "********** CFG Sorting **********\n"

385 "********** Function: "

386 << MF.getName() << '\n');

387

388 const auto &MLI = getAnalysis().getLI();

389 const auto &WEI = getAnalysis();

390 auto &MDT = getAnalysis().getDomTree();

391

393

394

396

397 return true;

398}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)

This file defines the PriorityQueue class.

This file implements a set that has insertion order iteration characteristics.

static void maybeUpdateTerminator(MachineBasicBlock *MBB)

Definition WebAssemblyCFGSort.cpp:79

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 implements regions used in CFGSort and CFGStackify.

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.

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

Add the specified Pass class to the set of analyses preserved by this pass.

LLVM_ABI 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.

DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...

bool dominates(const MachineInstr *A, const MachineInstr *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.

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.

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_arg_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.

void push_back(const T &Elt)

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.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

bool sortBlocks(Function &F)

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

FunctionAddr VTableAddr Next

FunctionPass * createWebAssemblyCFGSort()