LLVM 19.0.0git
CodeMoverUtils.cpp
Go to the documentation of this file.
1//===- CodeMoverUtils.cpp - CodeMover Utilities ----------------------------==//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This family of functions perform movements on basic blocks, and instructions
10// contained within a function.
11//
12//===----------------------------------------------------------------------===//
13
15#include "llvm/ADT/Statistic.h"
19#include "llvm/IR/Dominators.h"
20
21using namespace llvm;
22
23#define DEBUG_TYPE "codemover-utils"
24
25STATISTIC(HasDependences,
26 "Cannot move across instructions that has memory dependences");
27STATISTIC(MayThrowException, "Cannot move across instructions that may throw");
28STATISTIC(NotControlFlowEquivalent,
29 "Instructions are not control flow equivalent");
30STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported");
31STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported");
32
33namespace {
34/// Represent a control condition. A control condition is a condition of a
35/// terminator to decide which successors to execute. The pointer field
36/// represents the address of the condition of the terminator. The integer field
37/// is a bool, it is true when the basic block is executed when V is true. For
38/// example, `br %cond, bb0, bb1` %cond is a control condition of bb0 with the
39/// integer field equals to true, while %cond is a control condition of bb1 with
40/// the integer field equals to false.
41using ControlCondition = PointerIntPair<Value *, 1, bool>;
42#ifndef NDEBUG
43raw_ostream &operator<<(raw_ostream &OS, const ControlCondition &C) {
44 OS << "[" << *C.getPointer() << ", " << (C.getInt() ? "true" : "false")
45 << "]";
46 return OS;
47}
48#endif
49
50/// Represent a set of control conditions required to execute ToBB from FromBB.
51class ControlConditions {
52 using ConditionVectorTy = SmallVector<ControlCondition, 6>;
53
54 /// A SmallVector of control conditions.
55 ConditionVectorTy Conditions;
56
57public:
58 /// Return a ControlConditions which stores all conditions required to execute
59 /// \p BB from \p Dominator. If \p MaxLookup is non-zero, it limits the
60 /// number of conditions to collect. Return std::nullopt if not all conditions
61 /// are collected successfully, or we hit the limit.
62 static const std::optional<ControlConditions>
63 collectControlConditions(const BasicBlock &BB, const BasicBlock &Dominator,
64 const DominatorTree &DT,
65 const PostDominatorTree &PDT,
66 unsigned MaxLookup = 6);
67
68 /// Return true if there exists no control conditions required to execute ToBB
69 /// from FromBB.
70 bool isUnconditional() const { return Conditions.empty(); }
71
72 /// Return a constant reference of Conditions.
73 const ConditionVectorTy &getControlConditions() const { return Conditions; }
74
75 /// Add \p V as one of the ControlCondition in Condition with IsTrueCondition
76 /// equals to \p True. Return true if inserted successfully.
77 bool addControlCondition(ControlCondition C);
78
79 /// Return true if for all control conditions in Conditions, there exists an
80 /// equivalent control condition in \p Other.Conditions.
81 bool isEquivalent(const ControlConditions &Other) const;
82
83 /// Return true if \p C1 and \p C2 are equivalent.
84 static bool isEquivalent(const ControlCondition &C1,
85 const ControlCondition &C2);
86
87private:
88 ControlConditions() = default;
89
90 static bool isEquivalent(const Value &V1, const Value &V2);
91 static bool isInverse(const Value &V1, const Value &V2);
92};
93} // namespace
94
95static bool domTreeLevelBefore(DominatorTree *DT, const Instruction *InstA,
96 const Instruction *InstB) {
97 // Use ordered basic block in case the 2 instructions are in the same
98 // block.
99 if (InstA->getParent() == InstB->getParent())
100 return InstA->comesBefore(InstB);
101
102 DomTreeNode *DA = DT->getNode(InstA->getParent());
103 DomTreeNode *DB = DT->getNode(InstB->getParent());
104 return DA->getLevel() < DB->getLevel();
105}
106
107const std::optional<ControlConditions>
108ControlConditions::collectControlConditions(const BasicBlock &BB,
109 const BasicBlock &Dominator,
110 const DominatorTree &DT,
111 const PostDominatorTree &PDT,
112 unsigned MaxLookup) {
113 assert(DT.dominates(&Dominator, &BB) && "Expecting Dominator to dominate BB");
114
115 ControlConditions Conditions;
116 unsigned NumConditions = 0;
117
118 // BB is executed unconditional from itself.
119 if (&Dominator == &BB)
120 return Conditions;
121
122 const BasicBlock *CurBlock = &BB;
123 // Walk up the dominator tree from the associated DT node for BB to the
124 // associated DT node for Dominator.
125 do {
126 assert(DT.getNode(CurBlock) && "Expecting a valid DT node for CurBlock");
127 BasicBlock *IDom = DT.getNode(CurBlock)->getIDom()->getBlock();
128 assert(DT.dominates(&Dominator, IDom) &&
129 "Expecting Dominator to dominate IDom");
130
131 // Limitation: can only handle branch instruction currently.
132 const BranchInst *BI = dyn_cast<BranchInst>(IDom->getTerminator());
133 if (!BI)
134 return std::nullopt;
135
136 bool Inserted = false;
137 if (PDT.dominates(CurBlock, IDom)) {
138 LLVM_DEBUG(dbgs() << CurBlock->getName()
139 << " is executed unconditionally from "
140 << IDom->getName() << "\n");
141 } else if (PDT.dominates(CurBlock, BI->getSuccessor(0))) {
142 LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \""
143 << *BI->getCondition() << "\" is true from "
144 << IDom->getName() << "\n");
145 Inserted = Conditions.addControlCondition(
146 ControlCondition(BI->getCondition(), true));
147 } else if (PDT.dominates(CurBlock, BI->getSuccessor(1))) {
148 LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \""
149 << *BI->getCondition() << "\" is false from "
150 << IDom->getName() << "\n");
151 Inserted = Conditions.addControlCondition(
152 ControlCondition(BI->getCondition(), false));
153 } else
154 return std::nullopt;
155
156 if (Inserted)
157 ++NumConditions;
158
159 if (MaxLookup != 0 && NumConditions > MaxLookup)
160 return std::nullopt;
161
162 CurBlock = IDom;
163 } while (CurBlock != &Dominator);
164
165 return Conditions;
166}
167
168bool ControlConditions::addControlCondition(ControlCondition C) {
169 bool Inserted = false;
170 if (none_of(Conditions, [&](ControlCondition &Exists) {
171 return ControlConditions::isEquivalent(C, Exists);
172 })) {
173 Conditions.push_back(C);
174 Inserted = true;
175 }
176
177 LLVM_DEBUG(dbgs() << (Inserted ? "Inserted " : "Not inserted ") << C << "\n");
178 return Inserted;
179}
180
181bool ControlConditions::isEquivalent(const ControlConditions &Other) const {
182 if (Conditions.empty() && Other.Conditions.empty())
183 return true;
184
185 if (Conditions.size() != Other.Conditions.size())
186 return false;
187
188 return all_of(Conditions, [&](const ControlCondition &C) {
189 return any_of(Other.Conditions, [&](const ControlCondition &OtherC) {
190 return ControlConditions::isEquivalent(C, OtherC);
191 });
192 });
193}
194
195bool ControlConditions::isEquivalent(const ControlCondition &C1,
196 const ControlCondition &C2) {
197 if (C1.getInt() == C2.getInt()) {
198 if (isEquivalent(*C1.getPointer(), *C2.getPointer()))
199 return true;
200 } else if (isInverse(*C1.getPointer(), *C2.getPointer()))
201 return true;
202
203 return false;
204}
205
206// FIXME: Use SCEV and reuse GVN/CSE logic to check for equivalence between
207// Values.
208// Currently, isEquivalent rely on other passes to ensure equivalent conditions
209// have the same value, e.g. GVN.
210bool ControlConditions::isEquivalent(const Value &V1, const Value &V2) {
211 return &V1 == &V2;
212}
213
214bool ControlConditions::isInverse(const Value &V1, const Value &V2) {
215 if (const CmpInst *Cmp1 = dyn_cast<CmpInst>(&V1))
216 if (const CmpInst *Cmp2 = dyn_cast<CmpInst>(&V2)) {
217 if (Cmp1->getPredicate() == Cmp2->getInversePredicate() &&
218 Cmp1->getOperand(0) == Cmp2->getOperand(0) &&
219 Cmp1->getOperand(1) == Cmp2->getOperand(1))
220 return true;
221
222 if (Cmp1->getPredicate() ==
223 CmpInst::getSwappedPredicate(Cmp2->getInversePredicate()) &&
224 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
225 Cmp1->getOperand(1) == Cmp2->getOperand(0))
226 return true;
227 }
228 return false;
229}
230
232 const DominatorTree &DT,
233 const PostDominatorTree &PDT) {
234 return isControlFlowEquivalent(*I0.getParent(), *I1.getParent(), DT, PDT);
235}
236
238 const DominatorTree &DT,
239 const PostDominatorTree &PDT) {
240 if (&BB0 == &BB1)
241 return true;
242
243 if ((DT.dominates(&BB0, &BB1) && PDT.dominates(&BB1, &BB0)) ||
244 (PDT.dominates(&BB0, &BB1) && DT.dominates(&BB1, &BB0)))
245 return true;
246
247 // If the set of conditions required to execute BB0 and BB1 from their common
248 // dominator are the same, then BB0 and BB1 are control flow equivalent.
249 const BasicBlock *CommonDominator = DT.findNearestCommonDominator(&BB0, &BB1);
250 LLVM_DEBUG(dbgs() << "The nearest common dominator of " << BB0.getName()
251 << " and " << BB1.getName() << " is "
252 << CommonDominator->getName() << "\n");
253
254 const std::optional<ControlConditions> BB0Conditions =
255 ControlConditions::collectControlConditions(BB0, *CommonDominator, DT,
256 PDT);
257 if (BB0Conditions == std::nullopt)
258 return false;
259
260 const std::optional<ControlConditions> BB1Conditions =
261 ControlConditions::collectControlConditions(BB1, *CommonDominator, DT,
262 PDT);
263 if (BB1Conditions == std::nullopt)
264 return false;
265
266 return BB0Conditions->isEquivalent(*BB1Conditions);
267}
268
270 llvm::Statistic &Stat) {
271 ++Stat;
272 LLVM_DEBUG(dbgs() << "Unable to move instruction: " << I << ". "
273 << Stat.getDesc());
274 return false;
275}
276
277/// Collect all instructions in between \p StartInst and \p EndInst, and store
278/// them in \p InBetweenInsts.
279static void
281 SmallPtrSetImpl<Instruction *> &InBetweenInsts) {
282 assert(InBetweenInsts.empty() && "Expecting InBetweenInsts to be empty");
283
284 /// Get the next instructions of \p I, and push them to \p WorkList.
285 auto getNextInsts = [](Instruction &I,
287 if (Instruction *NextInst = I.getNextNode())
288 WorkList.insert(NextInst);
289 else {
290 assert(I.isTerminator() && "Expecting a terminator instruction");
291 for (BasicBlock *Succ : successors(&I))
292 WorkList.insert(&Succ->front());
293 }
294 };
295
297 getNextInsts(StartInst, WorkList);
298 while (!WorkList.empty()) {
299 Instruction *CurInst = *WorkList.begin();
300 WorkList.erase(CurInst);
301
302 if (CurInst == &EndInst)
303 continue;
304
305 if (!InBetweenInsts.insert(CurInst).second)
306 continue;
307
308 getNextInsts(*CurInst, WorkList);
309 }
310}
311
313 DominatorTree &DT, const PostDominatorTree *PDT,
314 DependenceInfo *DI, bool CheckForEntireBlock) {
315 // Skip tests when we don't have PDT or DI
316 if (!PDT || !DI)
317 return false;
318
319 // Cannot move itself before itself.
320 if (&I == &InsertPoint)
321 return false;
322
323 // Not moved.
324 if (I.getNextNode() == &InsertPoint)
325 return true;
326
327 if (isa<PHINode>(I) || isa<PHINode>(InsertPoint))
328 return reportInvalidCandidate(I, NotMovedPHINode);
329
330 if (I.isTerminator())
331 return reportInvalidCandidate(I, NotMovedTerminator);
332
333 // TODO remove this limitation.
334 if (!isControlFlowEquivalent(I, InsertPoint, DT, *PDT))
335 return reportInvalidCandidate(I, NotControlFlowEquivalent);
336
337 if (isReachedBefore(&I, &InsertPoint, &DT, PDT))
338 for (const Use &U : I.uses())
339 if (auto *UserInst = dyn_cast<Instruction>(U.getUser())) {
340 // If InsertPoint is in a BB that comes after I, then we cannot move if
341 // I is used in the terminator of the current BB.
342 if (I.getParent() == InsertPoint.getParent() &&
343 UserInst == I.getParent()->getTerminator())
344 return false;
345 if (UserInst != &InsertPoint && !DT.dominates(&InsertPoint, U)) {
346 // If UserInst is an instruction that appears later in the same BB as
347 // I, then it is okay to move since I will still be available when
348 // UserInst is executed.
349 if (CheckForEntireBlock && I.getParent() == UserInst->getParent() &&
350 DT.dominates(&I, UserInst))
351 continue;
352 return false;
353 }
354 }
355 if (isReachedBefore(&InsertPoint, &I, &DT, PDT))
356 for (const Value *Op : I.operands())
357 if (auto *OpInst = dyn_cast<Instruction>(Op)) {
358 if (&InsertPoint == OpInst)
359 return false;
360 // If OpInst is an instruction that appears earlier in the same BB as
361 // I, then it is okay to move since OpInst will still be available.
362 if (CheckForEntireBlock && I.getParent() == OpInst->getParent() &&
363 DT.dominates(OpInst, &I))
364 continue;
365 if (!DT.dominates(OpInst, &InsertPoint))
366 return false;
367 }
368
369 DT.updateDFSNumbers();
370 const bool MoveForward = domTreeLevelBefore(&DT, &I, &InsertPoint);
371 Instruction &StartInst = (MoveForward ? I : InsertPoint);
372 Instruction &EndInst = (MoveForward ? InsertPoint : I);
374 collectInstructionsInBetween(StartInst, EndInst, InstsToCheck);
375 if (!MoveForward)
376 InstsToCheck.insert(&InsertPoint);
377
378 // Check if there exists instructions which may throw, may synchonize, or may
379 // never return, from I to InsertPoint.
381 if (llvm::any_of(InstsToCheck, [](Instruction *I) {
382 if (I->mayThrow())
383 return true;
384
385 const CallBase *CB = dyn_cast<CallBase>(I);
386 if (!CB)
387 return false;
388 if (!CB->hasFnAttr(Attribute::WillReturn))
389 return true;
390 if (!CB->hasFnAttr(Attribute::NoSync))
391 return true;
392
393 return false;
394 })) {
395 return reportInvalidCandidate(I, MayThrowException);
396 }
397
398 // Check if I has any output/flow/anti dependences with instructions from \p
399 // StartInst to \p EndInst.
400 if (llvm::any_of(InstsToCheck, [&DI, &I](Instruction *CurInst) {
401 auto DepResult = DI->depends(&I, CurInst, true);
402 if (DepResult && (DepResult->isOutput() || DepResult->isFlow() ||
403 DepResult->isAnti()))
404 return true;
405 return false;
406 }))
407 return reportInvalidCandidate(I, HasDependences);
408
409 return true;
410}
411
413 DominatorTree &DT, const PostDominatorTree *PDT,
414 DependenceInfo *DI) {
415 return llvm::all_of(BB, [&](Instruction &I) {
416 if (BB.getTerminator() == &I)
417 return true;
418
419 return isSafeToMoveBefore(I, InsertPoint, DT, PDT, DI,
420 /*CheckForEntireBlock=*/true);
421 });
422}
423
425 DominatorTree &DT,
426 const PostDominatorTree &PDT,
427 DependenceInfo &DI) {
428 for (Instruction &I :
430 Instruction *MovePos = ToBB.getFirstNonPHIOrDbg();
431
432 if (isSafeToMoveBefore(I, *MovePos, DT, &PDT, &DI))
433 I.moveBeforePreserving(MovePos);
434 }
435}
436
438 DominatorTree &DT,
439 const PostDominatorTree &PDT,
440 DependenceInfo &DI) {
441 Instruction *MovePos = ToBB.getTerminator();
442 while (FromBB.size() > 1) {
443 Instruction &I = FromBB.front();
444 if (isSafeToMoveBefore(I, *MovePos, DT, &PDT, &DI))
445 I.moveBeforePreserving(MovePos);
446 }
447}
448
450 const BasicBlock *OtherBlock,
451 const DominatorTree *DT,
452 const PostDominatorTree *PDT) {
453 assert(isControlFlowEquivalent(*ThisBlock, *OtherBlock, *DT, *PDT) &&
454 "ThisBlock and OtherBlock must be CFG equivalent!");
455 const BasicBlock *CommonDominator =
456 DT->findNearestCommonDominator(ThisBlock, OtherBlock);
457 if (CommonDominator == nullptr)
458 return false;
459
460 /// Recursively check the predecessors of \p ThisBlock up to
461 /// their common dominator, and see if any of them post-dominates
462 /// \p OtherBlock.
465 WorkList.push_back(ThisBlock);
466 while (!WorkList.empty()) {
467 const BasicBlock *CurBlock = WorkList.back();
468 WorkList.pop_back();
469 Visited.insert(CurBlock);
470 if (PDT->dominates(CurBlock, OtherBlock))
471 return true;
472
473 for (const auto *Pred : predecessors(CurBlock)) {
474 if (Pred == CommonDominator || Visited.count(Pred))
475 continue;
476 WorkList.push_back(Pred);
477 }
478 }
479 return false;
480}
481
483 const DominatorTree *DT,
484 const PostDominatorTree *PDT) {
485 const BasicBlock *BB0 = I0->getParent();
486 const BasicBlock *BB1 = I1->getParent();
487 if (BB0 == BB1)
488 return DT->dominates(I0, I1);
489
490 return nonStrictlyPostDominate(BB1, BB0, DT, PDT);
491}
static bool reportInvalidCandidate(const Instruction &I, llvm::Statistic &Stat)
static bool domTreeLevelBefore(DominatorTree *DT, const Instruction *InstA, const Instruction *InstB)
static void collectInstructionsInBetween(Instruction &StartInst, const Instruction &EndInst, SmallPtrSetImpl< Instruction * > &InBetweenInsts)
Collect all instructions in between StartInst and EndInst, and store them in InBetweenInsts.
#define LLVM_DEBUG(X)
Definition: Debug.h:101
std::optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1293
#define I(x, y, z)
Definition: MD5.cpp:58
if(VerifyEach)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
const Instruction & front() const
Definition: BasicBlock.h:453
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
Definition: BasicBlock.cpp:379
size_t size() const
Definition: BasicBlock.h:451
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...
Definition: BasicBlock.h:221
Conditional or Unconditional Branch instruction.
BasicBlock * getSuccessor(unsigned i) const
Value * getCondition() const
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1494
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:983
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:1167
This class represents an Operation in the Expression.
DependenceInfo - This class is the main dependence-analysis driver.
std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool PossiblyLoopIndependent)
depends - Tests for a dependence between the Src and Dst instructions.
DomTreeNodeBase * getIDom() const
NodeT * getBlock() const
void updateDFSNumbers() const
updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
Instruction * findNearestCommonDominator(Instruction *I1, Instruction *I2) const
Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced bef...
Definition: Dominators.cpp:344
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
const BasicBlock * getParent() const
Definition: Instruction.h:152
bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
PointerIntPair - This class implements a pair of a pointer and small integer.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
bool dominates(const Instruction *I1, const Instruction *I2) const
Return true if I1 dominates I2.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:321
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:356
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:360
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:342
iterator begin() const
Definition: SmallPtrSet.h:380
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:329
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1722
auto successors(const MachineBasicBlock *BB)
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...
Definition: STLExtras.h:656
void moveInstructionsToTheEnd(BasicBlock &FromBB, BasicBlock &ToBB, DominatorTree &DT, const PostDominatorTree &PDT, DependenceInfo &DI)
Move instructions, in an order-preserving manner, from FromBB to the end of ToBB when proven safe.
bool isReachedBefore(const Instruction *I0, const Instruction *I1, const DominatorTree *DT, const PostDominatorTree *PDT)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1729
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:419
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1736
bool isControlFlowEquivalent(const Instruction &I0, const Instruction &I1, const DominatorTree &DT, const PostDominatorTree &PDT)
Return true if I0 and I1 are control flow equivalent.
bool nonStrictlyPostDominate(const BasicBlock *ThisBlock, const BasicBlock *OtherBlock, const DominatorTree *DT, const PostDominatorTree *PDT)
In case that two BBs ThisBlock and OtherBlock are control flow equivalent but they do not strictly do...
void moveInstructionsToTheBeginning(BasicBlock &FromBB, BasicBlock &ToBB, DominatorTree &DT, const PostDominatorTree &PDT, DependenceInfo &DI)
Move instructions, in an order-preserving manner, from FromBB to the beginning of ToBB when proven sa...
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:293
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
auto predecessors(const MachineBasicBlock *BB)
bool isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint, DominatorTree &DT, const PostDominatorTree *PDT=nullptr, DependenceInfo *DI=nullptr, bool CheckForEntireBlock=false)
Return true if I can be safely moved before InsertPoint.