WebAssemblyFixIrreducibleControlFlow.cpp Source File (original) (raw)

61using namespace llvm;

63#define DEBUG_TYPE "wasm-fix-irreducible-control-flow"

65namespace {

70static BlockVector getSortedEntries(const BlockSet &Entries) {

71 BlockVector SortedEntries(Entries.begin(), Entries.end());

74 auto ANum = A->getNumber();

75 auto BNum = B->getNumber();

76 return ANum < BNum;

77 });

78 return SortedEntries;

79}

84class ReachabilityGraph {

85public:

87 : Entry(Entry), Blocks(Blocks) {

88#ifndef NDEBUG

90 for (auto *MBB : Blocks) {

91 if (MBB != Entry) {

92 for (auto *Pred : MBB->predecessors()) {

93 assert(inRegion(Pred));

94 }

95 }

96 }

97#endif

98 calculate();

99 }

100

102 assert(inRegion(From) && inRegion(To));

103 auto I = Reachable.find(From);

104 if (I == Reachable.end())

105 return false;

106 return I->second.count(To);

107 }

108

109

110

111 const BlockSet &getLoopers() const { return Loopers; }

112

113

114 const BlockSet &getLoopEntries() const { return LoopEntries; }

115

116

118 assert(inRegion(LoopEntry));

119 auto I = LoopEnterers.find(LoopEntry);

120 assert(I != LoopEnterers.end());

121 return I->second;

122 }

123

124private:

127

128 BlockSet Loopers, LoopEntries;

130

132

133

135

136 void calculate() {

137

138

139 using BlockPair = std::pair<MachineBasicBlock *, MachineBasicBlock *>;

141

142

143 for (auto *MBB : Blocks) {

144 for (auto *Succ : MBB->successors()) {

145 if (Succ != Entry && inRegion(Succ)) {

146 Reachable[MBB].insert(Succ);

148 }

149 }

150 }

151

152 while (!WorkList.empty()) {

155 assert(inRegion(MBB) && Succ != Entry && inRegion(Succ));

156 if (MBB != Entry) {

157

158

159 for (auto *Pred : MBB->predecessors()) {

160 if (Reachable[Pred].insert(Succ).second) {

162 }

163 }

164 }

165 }

166

167

168 for (auto *MBB : Blocks) {

169 if (canReach(MBB, MBB)) {

170 Loopers.insert(MBB);

171 }

172 }

173 assert(!Loopers.count(Entry));

174

175

176

177 for (auto *Looper : Loopers) {

178 for (auto *Pred : Looper->predecessors()) {

179

180

181 if (!canReach(Looper, Pred)) {

182 LoopEntries.insert(Looper);

183 LoopEnterers[Looper].insert(Pred);

184 }

185 }

186 }

187 }

188};

189

190

191

192class LoopBlocks {

193public:

195 : Entry(Entry), Enterers(Enterers) {

196 calculate();

197 }

198

199 BlockSet &getBlocks() { return Blocks; }

200

201private:

204

206

207 void calculate() {

208

209

210 BlockVector WorkList;

212 Blocks.insert(Entry);

213 for (auto *Pred : Entry->predecessors()) {

214 if (!Enterers.count(Pred)) {

215 WorkList.push_back(Pred);

216 AddedToWorkList.insert(Pred);

217 }

218 }

219

220 while (!WorkList.empty()) {

221 auto *MBB = WorkList.pop_back_val();

223 if (Blocks.insert(MBB).second) {

224 for (auto *Pred : MBB->predecessors()) {

225 if (AddedToWorkList.insert(Pred).second)

226 WorkList.push_back(Pred);

227 }

228 }

229 }

230 }

231};

232

233class WebAssemblyFixIrreducibleControlFlow final : public MachineFunctionPass {

234 StringRef getPassName() const override {

235 return "WebAssembly Fix Irreducible Control Flow";

236 }

237

239

242

243 void makeSingleEntryLoop(BlockSet &Entries, BlockSet &Blocks,

245

246public:

247 static char ID;

249};

250

251bool WebAssemblyFixIrreducibleControlFlow::processRegion(

254

255

256 while (true) {

257 ReachabilityGraph Graph(Entry, Blocks);

258

259 bool FoundIrreducibility = false;

260

261 for (auto *LoopEntry : getSortedEntries(Graph.getLoopEntries())) {

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

288 MutualLoopEntries.insert(LoopEntry);

289 for (auto *OtherLoopEntry : Graph.getLoopEntries()) {

290 if (OtherLoopEntry != LoopEntry &&

291 Graph.canReach(LoopEntry, OtherLoopEntry) &&

292 Graph.canReach(OtherLoopEntry, LoopEntry)) {

293 MutualLoopEntries.insert(OtherLoopEntry);

294 }

295 }

296

297 if (MutualLoopEntries.size() > 1) {

298 makeSingleEntryLoop(MutualLoopEntries, Blocks, MF, Graph);

299 FoundIrreducibility = true;

301 break;

302 }

303 }

304

305

306

307

308

309

310 if (FoundIrreducibility) {

311 continue;

312 }

313

314 for (auto *LoopEntry : Graph.getLoopEntries()) {

315 LoopBlocks InnerBlocks(LoopEntry, Graph.getLoopEnterers(LoopEntry));

316

317

318

319

320

321

322 if (processRegion(LoopEntry, InnerBlocks.getBlocks(), MF)) {

324 }

325 }

326

328 }

329}

330

331

332

333

334

335

336

337void WebAssemblyFixIrreducibleControlFlow::makeSingleEntryLoop(

339 const ReachabilityGraph &Graph) {

340 assert(Entries.size() >= 2);

341

342

343 BlockVector SortedEntries = getSortedEntries(Entries);

344

345#ifndef NDEBUG

346 for (auto *Block : SortedEntries)

348 if (SortedEntries.size() > 1) {

349 for (auto I = SortedEntries.begin(), E = SortedEntries.end() - 1; I != E;

350 ++I) {

351 auto ANum = (*I)->getNumber();

352 auto BNum = (*(std::next(I)))->getNumber();

353 assert(ANum != BNum);

354 }

355 }

356#endif

357

358

361 Blocks.insert(Dispatch);

362

363

367

368

369

371 Register Reg = MRI.createVirtualRegister(&WebAssembly::I32RegClass);

373

374

375

377 for (auto *Entry : SortedEntries) {

380

382 Pair.first->second = Index;

383

386 }

387

388

389

390

391

392 BlockVector AllPreds;

393 for (auto *Entry : SortedEntries) {

394 for (auto *Pred : Entry->predecessors()) {

395 if (Pred != Dispatch) {

396 AllPreds.push_back(Pred);

397 }

398 }

399 }

400

401

403 for (auto *Pred : AllPreds) {

404 for (auto *Entry : Pred->successors()) {

405 if (!Entries.count(Entry))

406 continue;

407 if (Graph.canReach(Entry, Pred)) {

409 break;

410 }

411 }

412 }

413

414

415

417 EntryToLayoutPred;

418 for (auto *Pred : AllPreds) {

419 bool PredInLoop = InLoop.count(Pred);

420 for (auto *Entry : Pred->successors())

421 if (Entries.count(Entry) && Pred->isLayoutSuccessor(Entry))

422 EntryToLayoutPred[{Entry, PredInLoop}] = Pred;

423 }

424

425

426

427

428

430 Map;

431 for (auto *Pred : AllPreds) {

432 bool PredInLoop = InLoop.count(Pred);

433 for (auto *Entry : Pred->successors()) {

434 if (!Entries.count(Entry) || Map.count({Entry, PredInLoop}))

435 continue;

436

437

438

439 if (auto *OtherPred = EntryToLayoutPred.lookup({Entry, PredInLoop}))

440 if (OtherPred != Pred)

441 continue;

442

443

445 MF.insert(Pred->isLayoutSuccessor(Entry)

447 : MF.end(),

448 Routing);

449 Blocks.insert(Routing);

450

451

452

454 .addImm(Indices[Entry]);

457 Map[{Entry, PredInLoop}] = Routing;

458 }

459 }

460

461 for (auto *Pred : AllPreds) {

462 bool PredInLoop = InLoop.count(Pred);

463

464 for (MachineInstr &Term : Pred->terminators())

465 for (auto &Op : Term.explicit_uses())

466 if (Op.isMBB() && Indices.count(Op.getMBB()))

467 Op.setMBB(Map[{Op.getMBB(), PredInLoop}]);

468

469 for (auto *Succ : Pred->successors()) {

470 if (!Entries.count(Succ))

471 continue;

472 auto *Routing = Map[{Succ, PredInLoop}];

473 Pred->replaceSuccessor(Succ, Routing);

474 }

475 }

476

477

481}

482

483}

484

485char WebAssemblyFixIrreducibleControlFlow::ID = 0;

487 "Removes irreducible control flow", false, false)

488

490 return new WebAssemblyFixIrreducibleControlFlow();

491}

492

493

495 for (const auto &Def : MRI.def_instructions(Reg))

497 return true;

498 return false;

499}

500

501

502

503

508 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) {

510

511

512 if (MRI.use_nodbg_empty(Reg))

513 continue;

514

515

517 continue;

518

520 TII.get(WebAssembly::IMPLICIT_DEF), Reg);

521 }

522

523

524

527 MI.removeFromParent();

528 Entry.insert(Entry.begin(), &MI);

529 }

530 }

531}

532

533bool WebAssemblyFixIrreducibleControlFlow::runOnMachineFunction(

534 MachineFunction &MF) {

535 LLVM_DEBUG(dbgs() << "********** Fixing Irreducible Control Flow **********\n"

536 "********** Function: "

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

538

539

541 for (auto &MBB : MF) {

542 AllBlocks.insert(&MBB);

543 }

544

545 if (LLVM_UNLIKELY(processRegion(&*MF.begin(), AllBlocks, MF))) {

546

547 MF.RenumberBlocks();

548

549

550

551

552

553

554

556 return true;

557 }

558

559 return false;

560}

unsigned const MachineRegisterInfo * MRI

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

const TargetInstrInfo & TII

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 LLVM_UNLIKELY(EXPR)

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

std::unordered_set< BasicBlock * > BlockSet

static bool hasArgumentDef(unsigned Reg, const MachineRegisterInfo &MRI)

Definition WebAssemblyFixIrreducibleControlFlow.cpp:494

static void addImplicitDefs(MachineFunction &MF)

Definition WebAssemblyFixIrreducibleControlFlow.cpp:504

This file provides WebAssembly-specific target descriptions.

This file declares the WebAssembly-specific subclass of TargetSubtarget.

This file contains the entry points for global functions defined in the LLVM WebAssembly back-end.

ValueT lookup(const_arg_type_t< KeyT > Val) const

lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...

std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)

size_type count(const_arg_type_t< KeyT > Val) const

Return 1 if the specified key is in the map, 0 otherwise.

std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)

Implements a dense probed hash-table based set.

FunctionPass class - This class is used to implement most global optimizations.

LLVM_ABI void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())

Add Succ as a successor of this MachineBasicBlock.

MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...

const TargetSubtargetInfo & getSubtarget() const

getSubtarget - Return the subtarget for which this machine code is being compiled.

StringRef getName() const

getName - Return the name of the corresponding LLVM function.

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

BasicBlockListType::iterator iterator

MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *BB=nullptr, std::optional< UniqueBBID > BBID=std::nullopt)

CreateMachineInstr - Allocate a new MachineInstr.

void insert(iterator MBBI, MachineBasicBlock *MBB)

const MachineInstrBuilder & addImm(int64_t Val) const

Add a new immediate operand.

const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const

Add a new virtual register operand.

const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const

MachineInstr * getInstr() const

If conversion operators fail, use this method to get the MachineInstr explicitly.

Representation of each machine instruction.

LLVM_ABI unsigned getNumExplicitOperands() const

Returns the number of non-implicit operands.

const MachineOperand & getOperand(unsigned i) const

MachineBasicBlock * getMBB() const

MachineRegisterInfo - Keep track of information for virtual and physical registers,...

Wrapper class representing virtual and physical registers.

static Register index2VirtReg(unsigned Index)

Convert a 0-based index to a virtual register number.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

reference emplace_back(ArgTypes &&... Args)

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.

std::pair< iterator, bool > insert(const ValueT &V)

size_type count(const_arg_type_t< ValueT > V) const

Return 1 if the specified key is in the set, 0 otherwise.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

bool isArgument(unsigned Opc)

This is an optimization pass for GlobalISel generic memory operations.

MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)

Builder interface. Specify how to create the initial instruction itself.

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

void sort(IteratorTy Start, IteratorTy End)

LLVM_ABI raw_ostream & dbgs()

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

FunctionPass * createWebAssemblyFixIrreducibleControlFlow()

DWARFExpression::Operation Op