FixIrreducible.cpp Source File (original) (raw)

100

101

102

103

104

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

140

141#define DEBUG_TYPE "fix-irreducible"

142

143using namespace llvm;

144

145namespace {

147 static char ID;

150 }

151

152 void getAnalysisUsage(AnalysisUsage &AU) const override {

158 }

159

161};

162}

163

164char FixIrreducible::ID = 0;

165

167

169 "Convert irreducible control-flow into natural loops",

170 false , false )

174 "Convert irreducible control-flow into natural loops",

175 false , false )

176

177

178

181 auto &CandidateLoops = ParentLoop ? ParentLoop->getSubLoopsVector()

182 : LI.getTopLevelLoopsVector();

183

184

186 return NewLoop == L || !NewLoop->contains(L->getHeader());

187 });

189 CandidateLoops.erase(FirstChild, CandidateLoops.end());

190

191 for (Loop *Child : ChildLoops) {

192 LLVM_DEBUG(dbgs() << "child loop: " << Child->getHeader()->getName()

193 << "\n");

194

195

196 if (Child->getHeader() == OldHeader) {

197 for (auto *BB : Child->blocks()) {

198 if (LI.getLoopFor(BB) != Child)

199 continue;

200 LI.changeLoopFor(BB, NewLoop);

201 LLVM_DEBUG(dbgs() << "moved block from child: " << BB->getName()

202 << "\n");

203 }

204 std::vector<Loop *> GrandChildLoops;

205 std::swap(GrandChildLoops, Child->getSubLoopsVector());

206 for (auto *GrandChildLoop : GrandChildLoops) {

207 GrandChildLoop->setParentLoop(nullptr);

208 NewLoop->addChildLoop(GrandChildLoop);

209 }

210 LI.destroy(Child);

211 LLVM_DEBUG(dbgs() << "subsumed child loop (common header)\n");

212 continue;

213 }

214

215 Child->setParentLoop(nullptr);

216 NewLoop->addChildLoop(Child);

217 LLVM_DEBUG(dbgs() << "added child loop to new loop\n");

218 }

219}

220

223

224

225

228 if (ParentLoop && ParentLoop->getHeader() == CycleHeader)

230

231

233 if (ParentLoop) {

235 } else {

237 }

238

239

240

241

242

243

244 for (auto *G : GuardBlocks) {

245 LLVM_DEBUG(dbgs() << "added guard block to loop: " << G->getName() << "\n");

246 NewLoop->addBasicBlockToLoop(G, LI);

247 }

248

249 for (auto *BB : C.blocks()) {

250 NewLoop->addBlockEntry(BB);

251 if (LI.getLoopFor(BB) == ParentLoop) {

252 LLVM_DEBUG(dbgs() << "moved block from parent: " << BB->getName()

253 << "\n");

255 } else {

256 LLVM_DEBUG(dbgs() << "added block from child: " << BB->getName() << "\n");

257 }

258 }

260 << NewLoop->getHeader()->getName() << "\n");

261

263

265 NewLoop->verifyLoop();

266 if (ParentLoop) {

269 }

270}

271

272

273

274

277 if (C.isReducible())

278 return false;

280

281 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);

284

285

288 if (C.contains(P))

290 }

291

294

295 BasicBlock *Succ0 = Branch->getSuccessor(0) == Header ? Header : nullptr;

296 BasicBlock *Succ1 = Succ0 ? nullptr : Header;

297 assert(Succ0 || Branch->getSuccessor(1) == Header);

298 assert(Succ0 || Succ1);

300

304 << '\n');

306 for (unsigned I = 0; I < CallBr->getNumSuccessors(); ++I) {

307 BasicBlock *Succ = CallBr->getSuccessor(I);

308 if (Succ != Header)

309 continue;

315 }

316 } else {

318 }

319 }

320

321

322 Predecessors.clear();

325 if (.contains(P))

327 }

328 }

329

332 BasicBlock *Succ0 = Branch->getSuccessor(0);

333 Succ0 = C.contains(Succ0) ? Succ0 : nullptr;

335 Branch->isUnconditional() ? nullptr : Branch->getSuccessor(1);

336 Succ1 = Succ1 && C.contains(Succ1) ? Succ1 : nullptr;

338

342 << '\n');

344 for (unsigned I = 0; I < CallBr->getNumSuccessors(); ++I) {

345 BasicBlock *Succ = CallBr->getSuccessor(I);

346 if (.contains(Succ))

347 continue;

353 }

354 } else {

356 }

357 }

358

359

360

361

363

364

365

366

367

368

370 Entries.insert(C.entry_rbegin(), C.entry_rend());

371

372 CHub.finalize(&DTU, GuardBlocks, "irr");

373#if defined(EXPENSIVE_CHECKS)

374 assert(DT.verify(DominatorTree::VerificationLevel::Full));

375#else

376 assert(DT.verify(DominatorTree::VerificationLevel::Fast));

377#endif

378

379

380

381 if (LI)

383

384 for (auto *G : GuardBlocks) {

385 LLVM_DEBUG(dbgs() << "added guard block to cycle: " << G->getName()

386 << "\n");

388 }

389 C.setSingleEntry(GuardBlocks[0]);

390

391 C.verifyCycle();

392 if (Cycle *Parent = C.getParentCycle())

393 Parent->verifyCycle();

394

396 return true;

397}

398

401 LLVM_DEBUG(dbgs() << "===== Fix irreducible control-flow in function: "

402 << F.getName() << "\n");

403

408 }

409 }

410

412 return false;

413

414#if defined(EXPENSIVE_CHECKS)

416 if (LI) {

418 }

419#endif

420

421 return true;

422}

423

424bool FixIrreducible::runOnFunction(Function &F) {

425 auto *LIWP = getAnalysisIfAvailable();

426 LoopInfo *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;

427 auto &CI = getAnalysis().getResult();

428 auto &DT = getAnalysis().getDomTree();

430}

431

437

440

445 return PA;

446}

for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))

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

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

This file declares an analysis pass that computes CycleInfo for LLVM IR, specialized from GenericCycl...

static bool runOnFunction(Function &F, bool PostInlining)

fix Convert irreducible control flow into natural static false void reconnectChildLoops(LoopInfo &LI, Loop *ParentLoop, Loop *NewLoop, BasicBlock *OldHeader)

Definition FixIrreducible.cpp:179

static void updateLoopInfo(LoopInfo &LI, Cycle &C, ArrayRef< BasicBlock * > GuardBlocks)

Definition FixIrreducible.cpp:221

static bool FixIrreducibleImpl(Function &F, CycleInfo &CI, DominatorTree &DT, LoopInfo *LI)

Definition FixIrreducible.cpp:399

static bool fixIrreducible(Cycle &C, CycleInfo &CI, DominatorTree &DT, LoopInfo *LI)

Definition FixIrreducible.cpp:275

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

PassT::Result * getCachedResult(IRUnitT &IR) const

Get the cached result of an analysis pass for a given IR unit.

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

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.

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

LLVM Basic Block Representation.

Conditional or Unconditional Branch instruction.

CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...

Analysis pass which computes a CycleInfo.

Legacy analysis pass which computes a CycleInfo.

Analysis pass which computes a DominatorTree.

bool verify(VerificationLevel VL=VerificationLevel::Full) const

verify - checks if the tree is correct.

Legacy analysis pass which computes a DominatorTree.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

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

void verify() const

Verify that the entire cycle tree well-formed.

void addBlockToCycle(BlockT *Block, CycleT *Cycle)

Assumes that Cycle is the innermost cycle containing Block.

iterator_range< const_toplevel_iterator > toplevel_cycles() const

void print(raw_ostream &Out) const

Print the cycle info.

Analysis pass that exposes the LoopInfo for a function.

void verifyLoop() const

Verify loop structure.

BlockT * getHeader() const

void print(raw_ostream &OS, bool Verbose=false, bool PrintNested=true, unsigned Depth=0) const

Print loop with all the BBs inside it.

void addChildLoop(LoopT *NewChild)

Add the specified loop to be a child of this loop.

LoopT * getParentLoop() const

Return the parent loop if it exists or nullptr for top level loops.

void verify(const DominatorTreeBase< BlockT, false > &DomTree) const

void addTopLevelLoop(LoopT *New)

This adds the specified loop to the collection of top-level loops.

LoopT * AllocateLoop(ArgsTy &&...Args)

void changeLoopFor(BlockT *BB, LoopT *L)

Change the top-level loop that contains BB to the specified loop.

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

The legacy pass manager's analysis pass to compute loop information.

Represents a single loop in the control flow graph.

static LLVM_ABI PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

PreservedAnalyses & preserve()

Mark an analysis as preserved.

A vector that has set insertion semantics.

void clear()

Completely clear the SetVector.

bool insert(const value_type &X)

Insert a new element into the SetVector.

iterator erase(const_iterator CI)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

unsigned ID

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

@ C

The default llvm calling convention, compatible with C.

This is an optimization pass for GlobalISel generic memory operations.

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

LLVM_ABI BasicBlock * SplitCallBrEdge(BasicBlock *CallBrBlock, BasicBlock *Succ, unsigned SuccIdx, DomTreeUpdater *DTU=nullptr, CycleInfo *CI=nullptr, LoopInfo *LI=nullptr, bool *UpdatedLI=nullptr)

Create a new intermediate target block for a callbr edge.

LLVM_ABI raw_ostream & dbgs()

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

LLVM_ABI FunctionPass * createFixIrreduciblePass()

Definition FixIrreducible.cpp:166

auto partition(R &&Range, UnaryPredicate P)

Provide wrappers to std::partition which take ranges instead of having to pass begin/end explicitly.

LLVM_ABI Printable printBasicBlock(const BasicBlock *BB)

Print BasicBlock BB as an operand or print "" if BB is a nullptr.

auto predecessors(const MachineBasicBlock *BB)

iterator_range< df_iterator< T > > depth_first(const T &G)

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

LLVM_ABI void initializeFixIrreduciblePass(PassRegistry &)

GenericCycleInfo< SSAContext > CycleInfo

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

Given a set of branch descriptors [BB, Succ0, Succ1], create a "hub" such that the control flow from ...

void addBranch(BasicBlock *BB, BasicBlock *Succ0, BasicBlock *Succ1=nullptr)

std::pair< BasicBlock *, bool > finalize(DomTreeUpdater *DTU, SmallVectorImpl< BasicBlock * > &GuardBlocks, const StringRef Prefix, std::optional< unsigned > MaxControlFlowBooleans=std::nullopt)

Return the unified loop exit block and a flag indicating if the CFG was changed at all.

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition FixIrreducible.cpp:432