FixIrreducible.cpp Source File (original) (raw)

94#define DEBUG_TYPE "fix-irreducible"

96using namespace llvm;

98namespace {

100 static char ID;

103 }

104

111 }

112

114};

115}

116

117char FixIrreducible::ID = 0;

118

120

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

123 false , false )

128 false , false )

129

130

131

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

135 : LI.getTopLevelLoopsVector();

136

137

138 auto FirstChild = std::partition(

139 CandidateLoops.begin(), CandidateLoops.end(), [&](Loop *L) {

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

141 });

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

144

145 for (Loop *Child : ChildLoops) {

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

147 << "\n");

148

149

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

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

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

153 continue;

154 LI.changeLoopFor(BB, NewLoop);

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

156 << "\n");

157 }

158 std::vector<Loop *> GrandChildLoops;

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

160 for (auto *GrandChildLoop : GrandChildLoops) {

161 GrandChildLoop->setParentLoop(nullptr);

162 NewLoop->addChildLoop(GrandChildLoop);

163 }

164 LI.destroy(Child);

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

166 continue;

167 }

168

169 Child->setParentLoop(nullptr);

170 NewLoop->addChildLoop(Child);

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

172 }

173}

174

177

178

179

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

184

185

187 if (ParentLoop) {

189 } else {

191 }

192

193

194

195

196

197

198 for (auto *G : GuardBlocks) {

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

200 NewLoop->addBasicBlockToLoop(G, LI);

201 }

202

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

204 NewLoop->addBlockEntry(BB);

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

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

207 << "\n");

209 } else {

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

211 }

212 }

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

215

217

219 NewLoop->verifyLoop();

220 if (ParentLoop) {

223 }

224}

225

226

227

228

231 if (C.isReducible())

232 return false;

234

237

238

241 if (C.contains(P))

243 }

244

246 auto *Branch = cast(P->getTerminator());

247

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

249 BasicBlock *Succ1 = Succ0 ? nullptr : Header;

250 if (!Succ0)

251 assert(Branch->getSuccessor(1) == Header);

252 assert(Succ0 || Succ1);

254

255 LLVM_DEBUG(dbgs() << "Added internal branch: " << P->getName() << " -> "

256 << (Succ0 ? Succ0->getName() : "") << " "

257 << (Succ1 ? Succ1->getName() : "") << "\n");

258 }

259

260

261 Predecessors.clear();

264 if (.contains(P))

266 }

267 }

268

270 auto *Branch = cast(P->getTerminator());

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

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

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

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

277

278 LLVM_DEBUG(dbgs() << "Added external branch: " << P->getName() << " -> "

279 << (Succ0 ? Succ0->getName() : "") << " "

280 << (Succ1 ? Succ1->getName() : "") << "\n");

281 }

282

283

284

285

287

288

289

290

291

292

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

295

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

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

298#if defined(EXPENSIVE_CHECKS)

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

300#else

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

302#endif

303

304

305

306 if (LI)

308

309 for (auto *G : GuardBlocks) {

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

311 << "\n");

313 }

314 C.setSingleEntry(GuardBlocks[0]);

315

316 C.verifyCycle();

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

318 Parent->verifyCycle();

319

321 return true;

322}

323

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

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

328

330

331 bool Changed = false;

335 }

336 }

337

338 if (!Changed)

339 return false;

340

341#if defined(EXPENSIVE_CHECKS)

343 if (LI) {

345 }

346#endif

347

348 return true;

349}

350

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

352 auto *LIWP = getAnalysisIfAvailable();

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

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

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

357}

358

364

367

372 return PA;

373}

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

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

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

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

fix Convert irreducible control flow into natural loops

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

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

A container for analyses that lazily runs them and caches their results.

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.

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.

virtual bool runOnFunction(Function &F)=0

runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.

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.

A possibly irreducible generalization of a Loop.

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 PassRegistry * getPassRegistry()

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

virtual void getAnalysisUsage(AnalysisUsage &) const

getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...

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.

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

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

StringRef getName() const

Return a constant reference to the value's name.

@ C

The default llvm calling convention, compatible with C.

unsigned ID

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

This is an optimization pass for GlobalISel generic memory operations.

bool hasOnlySimpleTerminator(const Function &F)

raw_ostream & dbgs()

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

FunctionPass * createFixIrreduciblePass()

void initializeFixIrreduciblePass(PassRegistry &)

auto predecessors(const MachineBasicBlock *BB)

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

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

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

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

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)