BreakCriticalEdges.cpp Source File (original) (raw)

35using namespace llvm;

37#define DEBUG_TYPE "break-crit-edges"

39 STATISTIC(NumBroken, "Number of blocks inserted");

41namespace {

42struct BreakCriticalEdges : public FunctionPass {

43 static char ID;

46 }

49 auto *DTWP = getAnalysisIfAvailable();

50 auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;

52 auto *PDTWP = getAnalysisIfAvailable();

53 auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;

55 auto *LIWP = getAnalysisIfAvailable();

56 auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;

58 F, CriticalEdgeSplittingOptions(DT, LI, nullptr, PDT));

59 NumBroken += N;

60 return N > 0;

61 }

63 void getAnalysisUsage(AnalysisUsage &AU) const override {

69 }

70};

71}

73char BreakCriticalEdges::ID = 0;

75 "Break critical edges in CFG", false, false)

81 return new BreakCriticalEdges();

82}

89 NumBroken += N;

90 if (N == 0)

95 return PA;

96}

100

101

104 const Twine &BBName) {

106 return nullptr;

107

109}

110

114 const Twine &BBName) {

117

118

119

120

122 return nullptr;

123

124 if (Options.IgnoreUnreachableDests &&

126 return nullptr;

127

130

131

132

133 if (LI) {

134 if (Loop *TIL = LI->getLoopFor(TIBB)) {

135

136

137

138

139

140

141

142

143

144

146 if (P == TIBB)

147 continue;

148 if (LI->getLoopFor(P) != TIL) {

149

150 LoopPreds.clear();

151 break;

152 }

154 }

155

156

159 })) {

160 if (Options.PreserveLoopSimplify)

161 return nullptr;

162 LoopPreds.clear();

163 }

164 }

165 }

166

167

169 if (BBName.str() != "")

171 else

174 "_crit_edge");

175

178 if (auto *LoopMD = TI->getMetadata(LLVMContext::MD_loop))

179 NewBI->setMetadata(LLVMContext::MD_loop, LoopMD);

180

181

184 F.insert(++FBBI, NewBB);

185

186

188

189

190

191 {

192 unsigned BBIdx = 0;

194

195

196

198

199

200

201

202

203

207 }

208 }

209

210 unsigned NumSplitIdenticalEdges = 1;

211

212

213

214

215 if (Options.MergeIdenticalEdges) {

216 for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {

218

219

221

222

224

225

226 NumSplitIdenticalEdges++;

227 }

228 }

229

230

233 auto *MSSAU = Options.MSSAU;

234 if (MSSAU)

235 MSSAU->wireOldPredecessorsToNewImmediatePredecessor(

236 DestBB, NewBB, {TIBB}, Options.MergeIdenticalEdges);

237

238 if (!DT && !PDT && !LI)

239 return NewBB;

240

241 if (DT || PDT) {

242

243

244

245

246

247

248

249

250

256

257 if (DT)

258 DT->applyUpdates(Updates);

259 if (PDT)

260 PDT->applyUpdates(Updates);

261 }

262

263

264 if (LI) {

265 if (Loop *TIL = LI->getLoopFor(TIBB)) {

266

267

268 if (Loop *DestLoop = LI->getLoopFor(DestBB)) {

269 if (TIL == DestLoop) {

270

271 DestLoop->addBasicBlockToLoop(NewBB, *LI);

272 } else if (TIL->contains(DestLoop)) {

273

274 TIL->addBasicBlockToLoop(NewBB, *LI);

275 } else if (DestLoop->contains(TIL)) {

276

277 DestLoop->addBasicBlockToLoop(NewBB, *LI);

278 } else {

279

280

281

282

283 assert(DestLoop->getHeader() == DestBB &&

284 "Should not create irreducible loops!");

285 if (Loop *P = DestLoop->getParentLoop())

286 P->addBasicBlockToLoop(NewBB, *LI);

287 }

288 }

289

290

291

292 if (!TIL->contains(DestBB)) {

293 assert(!TIL->contains(NewBB) &&

294 "Split point for loop exit is contained in loop!");

295

296

297 if (Options.PreserveLCSSA) {

298

299

302 DestBB);

303 }

304

305 if (!LoopPreds.empty()) {

306 assert(!DestBB->isEHPad() && "We don't split edges to EH pads!");

308 DestBB, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA);

309 if (Options.PreserveLCSSA)

311 }

312 }

313 }

314 }

315

316 return NewBB;

317}

318

319

320

321

322

325

326

327

330 Instruction *PredTerm = PredBB->getTerminator();

332 case Instruction::IndirectBr:

333 if (IBB)

334 return nullptr;

335 IBB = PredBB;

336 break;

337 case Instruction::Br:

338 case Instruction::Switch:

340 continue;

341 default:

342 return nullptr;

343 }

344 }

345

346 return IBB;

347}

348

350 bool IgnoreBlocksWithoutPHI,

353

354

355

357 for (auto &BB : F) {

360 }

361

362 if (Targets.empty())

363 return false;

364

365 bool ShouldUpdateAnalysis = BPI && BFI;

368 if (IgnoreBlocksWithoutPHI && Target->phis().empty())

369 continue;

370

373

374

375 if (!IBRPred || OtherPreds.empty())

376 continue;

377

378

379 auto FirstNonPHIIt = Target->getFirstNonPHIIt();

380 if (FirstNonPHIIt->isEHPad() || Target->isLandingPad())

381 continue;

382

383

385 if (ShouldUpdateAnalysis) {

386 EdgeProbabilities.reserve(Target->getTerminator()->getNumSuccessors());

387 for (unsigned I = 0, E = Target->getTerminator()->getNumSuccessors();

388 I < E; ++I)

391 }

392

393 BasicBlock *BodyBlock = Target->splitBasicBlock(FirstNonPHIIt, ".split");

394 if (ShouldUpdateAnalysis) {

395

398 }

399

400

401 if (IBRPred == Target)

402 IBRPred = BodyBlock;

403

404

405

406

409 if (!VMap.AtomMap.empty())

412

414 for (BasicBlock *Pred : OtherPreds) {

415

416

419 if (ShouldUpdateAnalysis)

420 BlockFreqForDirectSucc += BFI->getBlockFreq(Src) *

422 }

423 if (ShouldUpdateAnalysis) {

424 BFI->setBlockFreq(DirectSucc, BlockFreqForDirectSucc);

428 }

429

430

431

432

433

434

436 End = Target->getFirstNonPHIIt();

439

441 "Block was expected to only contain PHIs");

442

443 while (Indirect != End) {

447

448

449

451 Direct++;

452

453

454

455 Indirect++;

456

459 IBRPred);

461

462

463

467 MergePHI->addIncoming(DirPHI, DirectSucc);

470

473 }

474

476 }

477

479}

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

static BasicBlock * findIBRPredecessor(BasicBlock *BB, SmallVectorImpl< BasicBlock * > &OtherPreds)

Definition BreakCriticalEdges.cpp:324

static bool runOnFunction(Function &F, bool PostInlining)

This file provides various utilities for inspecting and working with the control flow graph in LLVM I...

static cl::opt< bool > SplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false), cl::Hidden, cl::desc("Split all critical edges during " "PHI elimination"))

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

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

This file defines the SmallVector class.

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

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

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

AnalysisUsage & addPreservedID(const void *ID)

AnalysisUsage & addPreserved()

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

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

LLVM_ABI const_iterator getFirstInsertionPt() const

Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...

const Function * getParent() const

Return the enclosing method, or null if none.

static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)

Creates a new BasicBlock.

InstListType::iterator iterator

Instruction iterators...

LLVM_ABI InstListType::const_iterator getFirstNonPHIOrDbgOrLifetime(bool SkipPseudoOp=true) const

Returns a pointer to the first instruction in this block that is not a PHINode, a debug intrinsic,...

bool isEHPad() const

Return true if this basic block is an exception handling block.

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)

Update PHI nodes in this BasicBlock before removal of predecessor Pred.

BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...

LLVM_ABI void setBlockFreq(const BasicBlock *BB, BlockFrequency Freq)

LLVM_ABI BlockFrequency getBlockFreq(const BasicBlock *BB) const

getblockFreq - Return block frequency.

Conditional or Unconditional Branch instruction.

static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)

Analysis providing branch probability information.

LLVM_ABI void eraseBlock(const BasicBlock *BB)

Forget analysis results for the given basic block.

LLVM_ABI void setEdgeProbability(const BasicBlock *Src, const SmallVectorImpl< BranchProbability > &Probs)

Set the raw probabilities for all edges from the given block.

LLVM_ABI BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const

Get an edge's probability, relative to other out-edges of the Src.

Analysis pass which computes a DominatorTree.

static constexpr UpdateKind Delete

static constexpr UpdateKind Insert

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

BasicBlockListType::iterator iterator

LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY

Return the number of successors that this instruction has.

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

LLVM_ABI void insertBefore(InstListType::iterator InsertPos)

Insert an unlinked instruction into a basic block immediately before the specified position.

LLVM_ABI InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

MDNode * getMetadata(unsigned KindID) const

Get the metadata of given kind attached to this Instruction.

LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY

Return the specified successor. This instruction must be a terminator.

LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)

Set the metadata of the specified kind to the specified node.

unsigned getOpcode() const

Returns a member of one of the enums like Instruction::Add.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

LLVM_ABI void setSuccessor(unsigned Idx, BasicBlock *BB)

Update the specified successor to point at the provided block.

LLVM_ABI void applyMergedLocation(DebugLoc LocA, DebugLoc LocB)

Merge 2 debug locations and apply it to the Instruction.

Analysis pass that exposes the LoopInfo for a function.

Represents a single loop in the control flow graph.

void addIncoming(Value *V, BasicBlock *BB)

Add an incoming value to the end of the PHI list.

void setIncomingBlock(unsigned i, BasicBlock *BB)

LLVM_ABI Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)

Remove an incoming value.

Value * getIncomingValueForBlock(const BasicBlock *BB) const

BasicBlock * getIncomingBlock(unsigned i) const

Return incoming basic block number i.

int getBasicBlockIndex(const BasicBlock *BB) const

Return the first index of the specified basic block in the value list for this PHI.

static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...

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.

void insert_range(Range &&R)

bool empty() const

Determine if the SetVector is empty or not.

A SetVector that performs no allocations if smaller than a certain size.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

reference emplace_back(ArgTypes &&... Args)

void reserve(size_type N)

void push_back(const T &Elt)

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

Target - Wrapper for Target specific information.

Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...

LLVM_ABI std::string str() const

Return the twine contents as a std::string.

LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)

Replace uses of one Value with another.

DMAtomT AtomMap

Map {(InlinedAt, old atom number) -> new atom number}.

Type * getType() const

All values are typed, get the type of this value.

LLVM_ABI void replaceAllUsesWith(Value *V)

Change all uses of this to point to a new Value.

LLVM_ABI LLVMContext & getContext() const

All values hold a context through their type.

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

const ParentTy * getParent() const

self_iterator getIterator()

unsigned ID

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

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ABI BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, bool MapAtoms=true)

Return a copy of the specified basic block, but without embedding the block into a particular functio...

auto successors(const MachineBasicBlock *BB)

LLVM_ABI FunctionPass * createBreakCriticalEdgesPass()

LLVM_ABI char & LoopSimplifyID

LLVM_ABI BasicBlock * SplitKnownCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")

If it is known that an edge is critical, SplitKnownCriticalEdge can be called directly,...

Definition BreakCriticalEdges.cpp:112

LLVM_ABI bool SplitIndirectBrCriticalEdges(Function &F, bool IgnoreBlocksWithoutPHI, BranchProbabilityInfo *BPI=nullptr, BlockFrequencyInfo *BFI=nullptr)

Definition BreakCriticalEdges.cpp:349

bool any_of(R &&range, UnaryPredicate P)

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

LLVM_ABI char & BreakCriticalEdgesID

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

LLVM_ABI BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)

This method introduces at least one new basic block into the function and moves some of the predecess...

LLVM_ABI void createPHIsForSplitLoopExit(ArrayRef< BasicBlock * > Preds, BasicBlock *SplitBB, BasicBlock *DestBB)

When a loop exit edge is split, LCSSA form may require new PHIs in the new exit block.

LLVM_ABI void initializeBreakCriticalEdgesPass(PassRegistry &)

LLVM_ABI BasicBlock * SplitCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")

If this edge is a critical edge, insert a new node to split the critical edge.

Definition BreakCriticalEdges.cpp:102

LLVM_ABI bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)

Return true if the specified edge is a critical edge.

ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy

decltype(auto) cast(const From &Val)

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

auto predecessors(const MachineBasicBlock *BB)

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

LLVM_ABI void RemapSourceAtom(Instruction *I, ValueToValueMapTy &VM)

Remap source location atom.

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition BreakCriticalEdges.cpp:84

Option class for critical edge splitting.