68#define DEBUG_TYPE "guard-widening"
70STATISTIC(GuardsEliminated,
"Number of eliminated guards");
71STATISTIC(CondBranchEliminated,
"Number of eliminated conditional branches");
72STATISTIC(FreezeAdded,
"Number of freeze instruction introduced");
76 cl::desc(
"Whether or not we should widen guards "
77 "expressed as branches by widenable conditions"),
85 assert(GI->getIntrinsicID() == Intrinsic::experimental_guard &&
86 "Bad guard intrinsic?");
87 return GI->getArgOperand(0);
94 return cast<BranchInst>(
I)->getCondition();
101 assert(GI->getIntrinsicID() == Intrinsic::experimental_guard &&
102 "Bad guard intrinsic?");
103 GI->setArgOperand(0, NewCond);
106 cast<BranchInst>(
I)->setCondition(NewCond);
127 Value *Condition, *WC;
130 return cast<Instruction>(WC);
134class GuardWideningImpl {
158 bool eliminateInstrViaWidening(
161 GuardsPerBlock,
bool InvertCondition =
false);
166 WS_IllegalOrNegative,
181 static StringRef scoreTypeToString(WideningScore WS);
186 WideningScore computeWideningScore(
Instruction *DominatedInstr,
193 return canBeHoistedTo(V, InsertPos, Visited);
211 Value *&Result,
bool InvertCondition);
232 void setBase(
const Value *NewBase) {
Base = NewBase; }
235 const Value *getBase()
const {
return Base; }
237 const APInt &getOffsetValue()
const {
return getOffset()->getValue(); }
239 ICmpInst *getCheckInst()
const {
return CheckInst; }
243 Base->printAsOperand(
OS, PrintTypes);
245 Offset->printAsOperand(
OS, PrintTypes);
247 Length->printAsOperand(
OS, PrintTypes);
261 return parseRangeChecks(CheckCond, Checks, Visited);
276 bool isWideningCondProfitable(
Value *Cond0,
Value *Cond1,
bool InvertCond) {
278 return widenCondCommon(Cond0, Cond1,
nullptr, ResultUnused,
286 bool InvertCondition) {
288 Instruction *InsertPt = findInsertionPointForWideCondition(ToWiden);
289 widenCondCommon(getCondition(ToWiden), NewCondition, InsertPt, Result,
295 setCondition(ToWiden, Result);
302 std::function<
bool(
BasicBlock *)> BlockFilter)
303 : DT(DT), PDT(PDT), LI(LI), AC(AC), MSSAU(MSSAU), Root(Root),
304 BlockFilter(BlockFilter) {}
319bool GuardWideningImpl::run() {
321 bool Changed =
false;
324 auto *BB = (*DFI)->getBlock();
325 if (!BlockFilter(BB))
328 auto &CurrentList = GuardsInBlock[BB];
332 CurrentList.push_back(cast<Instruction>(&
I));
334 for (
auto *II : CurrentList)
335 Changed |= eliminateInstrViaWidening(II, DFI, GuardsInBlock);
338 assert(EliminatedGuardsAndBranches.
empty() || Changed);
339 for (
auto *
I : EliminatedGuardsAndBranches)
340 if (!WidenedGuards.
count(
I)) {
341 assert(isa<ConstantInt>(getCondition(
I)) &&
"Should be!");
343 eliminateGuard(
I, MSSAU);
346 "Eliminated something other than guard or branch?");
347 ++CondBranchEliminated;
354bool GuardWideningImpl::eliminateInstrViaWidening(
357 GuardsInBlock,
bool InvertCondition) {
361 if (isa<ConstantInt>(getCondition(Instr)))
365 auto BestScoreSoFar = WS_IllegalOrNegative;
369 for (
unsigned i = 0, e = DFSI.
getPathLength(); i != e; ++i) {
370 auto *CurBB = DFSI.
getPath(i)->getBlock();
371 if (!BlockFilter(CurBB))
373 assert(GuardsInBlock.
count(CurBB) &&
"Must have been populated by now!");
374 const auto &GuardsInCurBB = GuardsInBlock.
find(CurBB)->second;
376 auto I = GuardsInCurBB.begin();
378 : GuardsInCurBB.
end();
383 for (
auto &
I : *CurBB) {
384 if (
Index == GuardsInCurBB.size())
386 if (GuardsInCurBB[
Index] == &
I)
390 "Guards expected to be in order!");
397 auto Score = computeWideningScore(Instr, Candidate, InvertCondition);
399 <<
" and " << *getCondition(Candidate) <<
" is "
400 << scoreTypeToString(Score) <<
"\n");
401 if (Score > BestScoreSoFar) {
402 BestScoreSoFar = Score;
403 BestSoFar = Candidate;
408 if (BestScoreSoFar == WS_IllegalOrNegative) {
409 LLVM_DEBUG(
dbgs() <<
"Did not eliminate guard " << *Instr <<
"\n");
413 assert(BestSoFar != Instr &&
"Should have never visited same guard!");
416 LLVM_DEBUG(
dbgs() <<
"Widening " << *Instr <<
" into " << *BestSoFar
417 <<
" with score " << scoreTypeToString(BestScoreSoFar)
419 widenGuard(BestSoFar, getCondition(Instr), InvertCondition);
420 auto NewGuardCondition = InvertCondition
423 setCondition(Instr, NewGuardCondition);
424 EliminatedGuardsAndBranches.push_back(Instr);
425 WidenedGuards.
insert(BestSoFar);
429GuardWideningImpl::WideningScore
430GuardWideningImpl::computeWideningScore(
Instruction *DominatedInstr,
435 bool HoistingOutOfLoop =
false;
437 if (DominatingGuardLoop != DominatedInstrLoop) {
440 if (DominatingGuardLoop &&
441 !DominatingGuardLoop->
contains(DominatedInstrLoop))
442 return WS_IllegalOrNegative;
444 HoistingOutOfLoop =
true;
447 auto *WideningPoint = findInsertionPointForWideCondition(DominatingGuard);
448 if (!canBeHoistedTo(getCondition(DominatedInstr), WideningPoint))
449 return WS_IllegalOrNegative;
450 if (!canBeHoistedTo(getCondition(DominatingGuard), WideningPoint))
451 return WS_IllegalOrNegative;
461 if (isWideningCondProfitable(getCondition(DominatedInstr),
462 getCondition(DominatingGuard), InvertCond))
463 return HoistingOutOfLoop ? WS_VeryPositive : WS_Positive;
465 if (HoistingOutOfLoop)
471 if (
auto *UniqueSucc = BB->getUniqueSuccessor())
473 auto *
Term = BB->getTerminator();
475 const BasicBlock *IfTrue =
nullptr, *IfFalse =
nullptr;
476 using namespace PatternMatch;
481 if (
auto *ConstCond = dyn_cast<ConstantInt>(
Cond))
482 return ConstCond->isAllOnesValue() ? IfTrue : IfFalse;
497 auto MaybeHoistingToHotterBlock = [&]() {
498 const auto *DominatingBlock = DominatingGuard->
getParent();
499 const auto *DominatedBlock = DominatedInstr->
getParent();
504 assert(DT.
dominates(DominatingBlock, DominatedBlock) &&
"No dominance");
505 while (DominatedBlock != DominatingBlock) {
506 auto *LikelySucc = GetLikelySuccessor(DominatingBlock);
513 DominatingBlock = LikelySucc;
517 if (DominatedBlock == DominatingBlock)
521 if (!DT.
dominates(DominatingBlock, DominatedBlock))
524 if (!PDT)
return true;
525 return !PDT->
dominates(DominatedBlock, DominatingBlock);
528 return MaybeHoistingToHotterBlock() ? WS_IllegalOrNegative : WS_Neutral;
531bool GuardWideningImpl::canBeHoistedTo(
534 auto *Inst = dyn_cast<Instruction>(V);
539 Inst->mayReadFromMemory())
545 assert(!isa<PHINode>(Loc) &&
546 "PHIs should return false for isSafeToSpeculativelyExecute");
548 "We did a DFS from the block entry!");
549 return all_of(Inst->operands(),
550 [&](
Value *Op) { return canBeHoistedTo(Op, Loc, Visited); });
554 auto *Inst = dyn_cast<Instruction>(V);
559 !Inst->mayReadFromMemory() &&
560 "Should've checked with canBeHoistedTo!");
562 for (
Value *Op : Inst->operands())
563 makeAvailableAt(Op, Loc);
565 Inst->moveBefore(Loc);
571 auto *
I = dyn_cast<Instruction>(V);
575 auto *Res =
I->getInsertionPointAfterDef();
583 Instruction *User = cast<Instruction>(U);
584 return Res != User && DT.dominates(I, User) && !DT.dominates(Res, User);
595 return new FreezeInst(Orig,
"gw.freeze", InsertPt);
601 while (!Worklist.
empty()) {
603 if (!Visited.
insert(V).second)
618 return isa<Instruction>(Op) && !getFreezeInsertPt(Op, DT);
627 I->dropPoisonGeneratingFlagsAndMetadata();
630 for (
Value *V : NeedFreeze) {
636 V->replaceUsesWithIf(FI, [&](
Use & U)->
bool {
return U.getUser() != FI; });
642bool GuardWideningImpl::widenCondCommon(
Value *Cond0,
Value *Cond1,
644 bool InvertCondition) {
655 Pred1 = ICmpInst::getInversePredicate(Pred1);
665 if (std::optional<ConstantRange> Intersect =
669 if (Intersect->getEquivalentICmp(Pred, NewRHSAP)) {
673 assert(canBeHoistedTo(LHS, InsertPt) &&
"must be");
674 makeAvailableAt(LHS, InsertPt);
686 if (!InvertCondition &&
687 parseRangeChecks(Cond0, Checks) && parseRangeChecks(Cond1, Checks) &&
688 combineRangeChecks(Checks, CombinedChecks)) {
691 for (
auto &RC : CombinedChecks) {
692 makeAvailableAt(RC.getCheckInst(), InsertPt);
694 Result = BinaryOperator::CreateAnd(RC.getCheckInst(), Result,
"",
697 Result = RC.getCheckInst();
699 assert(Result &&
"Failed to find result value");
700 Result->setName(
"wide.chk");
701 Result = freezeAndPush(Result, InsertPt);
710 makeAvailableAt(Cond0, InsertPt);
711 makeAvailableAt(Cond1, InsertPt);
714 Cond1 = freezeAndPush(Cond1, InsertPt);
715 Result = BinaryOperator::CreateAnd(Cond0, Cond1,
"wide.chk", InsertPt);
722bool GuardWideningImpl::parseRangeChecks(
725 if (!Visited.
insert(CheckCond).second)
731 Value *AndLHS, *AndRHS;
733 return parseRangeChecks(AndLHS, Checks) &&
734 parseRangeChecks(AndRHS, Checks);
737 auto *IC = dyn_cast<ICmpInst>(CheckCond);
738 if (!IC || !IC->getOperand(0)->getType()->isIntegerTy() ||
739 (IC->getPredicate() != ICmpInst::ICMP_ULT &&
740 IC->getPredicate() != ICmpInst::ICMP_UGT))
743 const Value *CmpLHS = IC->getOperand(0), *CmpRHS = IC->getOperand(1);
744 if (IC->getPredicate() == ICmpInst::ICMP_UGT)
747 auto &
DL = IC->getModule()->getDataLayout();
749 GuardWideningImpl::RangeCheck
Check(
750 CmpLHS, cast<ConstantInt>(ConstantInt::getNullValue(CmpRHS->getType())),
768 auto *BaseInst = dyn_cast<Instruction>(
Check.getBase());
770 "Unreachable instruction?");
774 Check.setBase(OpLHS);
782 Check.setBase(OpLHS);
794bool GuardWideningImpl::combineRangeChecks(
797 unsigned OldCount = Checks.
size();
798 while (!Checks.
empty()) {
801 const Value *CurrentBase = Checks.
front().getBase();
802 const Value *CurrentLength = Checks.
front().getLength();
806 auto IsCurrentCheck = [&](GuardWideningImpl::RangeCheck &RC) {
807 return RC.getBase() == CurrentBase && RC.getLength() == CurrentLength;
810 copy_if(Checks, std::back_inserter(CurrentChecks), IsCurrentCheck);
813 assert(CurrentChecks.
size() != 0 &&
"We know we have at least one!");
815 if (CurrentChecks.
size() < 3) {
823 llvm::sort(CurrentChecks, [&](
const GuardWideningImpl::RangeCheck &LHS,
824 const GuardWideningImpl::RangeCheck &RHS) {
825 return LHS.getOffsetValue().slt(
RHS.getOffsetValue());
834 if ((MaxOffset->
getValue() - MinOffset->getValue())
838 APInt MaxDiff = MaxOffset->
getValue() - MinOffset->getValue();
840 auto OffsetOK = [&](
const GuardWideningImpl::RangeCheck &RC) {
841 return (HighOffset - RC.getOffsetValue()).ult(MaxDiff);
886 assert(RangeChecksOut.
size() <= OldCount &&
"We pessimized!");
887 return RangeChecksOut.
size() != OldCount;
891StringRef GuardWideningImpl::scoreTypeToString(WideningScore WS) {
893 case WS_IllegalOrNegative:
894 return "IllegalOrNegative";
899 case WS_VeryPositive:
900 return "VeryPositive";
914 std::unique_ptr<MemorySSAUpdater> MSSAU;
916 MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAA->getMSSA());
917 if (!GuardWideningImpl(DT, &PDT, LI, AC, MSSAU ? MSSAU.get() :
nullptr,
933 RootBB = L.getHeader();
935 return BB == RootBB || L.contains(BB);
937 std::unique_ptr<MemorySSAUpdater> MSSAU;
939 MSSAU = std::make_unique<MemorySSAUpdater>(AR.
MSSA);
940 if (!GuardWideningImpl(AR.
DT,
nullptr, AR.
LI, AR.
AC,
941 MSSAU ? MSSAU.get() :
nullptr, AR.
DT.
getNode(RootBB),
963 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
964 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
965 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
966 auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
967 auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
968 std::unique_ptr<MemorySSAUpdater> MSSAU;
970 MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAWP->getMSSA());
971 return GuardWideningImpl(DT, &PDT, LI, AC, MSSAU ? MSSAU.get() :
nullptr,
988struct LoopGuardWideningLegacyPass :
public LoopPass {
991 LoopGuardWideningLegacyPass() :
LoopPass(
ID) {
998 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
999 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1000 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
1001 *
L->getHeader()->getParent());
1002 auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
1003 auto *PDT = PDTWP ? &PDTWP->getPostDomTree() :
nullptr;
1004 auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
1005 std::unique_ptr<MemorySSAUpdater> MSSAU;
1007 MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAWP->getMSSA());
1011 RootBB =
L->getHeader();
1013 return BB == RootBB ||
L->contains(BB);
1015 return GuardWideningImpl(DT, PDT, LI, AC, MSSAU ? MSSAU.get() :
nullptr,
1016 DT.
getNode(RootBB), BlockFilter)
1029char GuardWideningLegacyPass::ID = 0;
1030char LoopGuardWideningLegacyPass::ID = 0;
1051 return new GuardWideningLegacyPass();
1055 return new LoopGuardWideningLegacyPass();
static SDValue Widen(SelectionDAG *CurDAG, SDValue N)
SmallVector< AArch64_IMM::ImmInsnModel, 4 > Insn
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
SmallVector< MachineOperand, 4 > Cond
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
static bool runOnFunction(Function &F, bool PostInlining)
static cl::opt< bool > WidenBranchGuards("guard-widening-widen-branch-guards", cl::Hidden, cl::desc("Whether or not we should widen guards " "expressed as branches by widenable conditions"), cl::init(true))
static bool isSupportedGuardInstruction(const Instruction *Insn)
static Instruction * getFreezeInsertPt(Value *V, const DominatorTree &DT)
static Constant * getTrue(Type *Ty)
For a boolean type or a vector of boolean type, return true or a vector with every element true.
modulo schedule Modulo Schedule test pass
#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())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Class for arbitrary precision integers.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool isMinValue() const
Determine if this is the smallest unsigned value.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
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.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
const_iterator getFirstNonPHIOrDbgOrAlloca() const
Returns an iterator to the first instruction in this block that is not a PHINode, a debug intrinsic,...
const CallInst * getPostdominatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize that is present either in current ...
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Represents analyses that only rely on functions' control flow.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
This is the shared class of boolean and integer constants.
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
static ConstantInt * getFalse(LLVMContext &Context)
const APInt & getValue() const
Return the constant as an APInt value reference.
This class represents a range of values.
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
std::optional< ConstantRange > exactIntersectWith(const ConstantRange &CR) const
Intersect the two ranges and return the result if it can be represented exactly, otherwise return std...
iterator find(const_arg_type_t< KeyT > Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Implements a dense probed hash-table based set.
Analysis pass which computes a DominatorTree.
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
This class represents a freeze function that returns random concrete value if an operand is either a ...
FunctionPass class - This class is used to implement most global optimizations.
This instruction compares its operands according to the predicate given to the constructor.
const BasicBlock * getParent() const
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
A wrapper class for inspecting calls to intrinsic functions.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Analysis pass that exposes the LoopInfo for a function.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this 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.
An analysis that produces MemorySSA for a function.
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
Legacy analysis pass which computes MemorySSA.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
Analysis pass which computes a PostDominatorTree.
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 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 preserveSet()
Mark an analysis set as preserved.
void preserve()
Mark an analysis as preserved.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
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.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
LLVMContext & getContext() const
All values hold a context through their type.
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 getPathLength() const
getPathLength - Return the length of the path from the entry node to the current node,...
NodeRef getPath(unsigned n) const
getPath - Return the n'th node in the path from the entry node to the current node.
This class implements an extremely fast bulk output stream that can only output to a stream.
#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.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
const_iterator end(StringRef path)
Get end iterator over path.
This is an optimization pass for GlobalISel generic memory operations.
FunctionPass * createGuardWideningPass()
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
void initializeLoopGuardWideningLegacyPassPass(PassRegistry &)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
df_iterator< T > df_begin(const T &G)
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
static Error getOffset(const SymbolRef &Sym, SectionRef Sec, uint64_t &Result)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
void setWidenableBranchCond(BranchInst *WidenableBR, Value *Cond)
Given a branch we know is widenable (defined per Analysis/GuardUtils.h), set it's condition such that...
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
bool parseWidenableBranch(const User *U, Value *&Condition, Value *&WidenableCondition, BasicBlock *&IfTrueBB, BasicBlock *&IfFalseBB)
If U is widenable branch looking like: cond = ... wc = call i1 @llvm.experimental....
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool canCreateUndefOrPoison(const Operator *Op, bool ConsiderFlagsAndMetadata=true)
canCreateUndefOrPoison returns true if Op can create undef or poison from non-undef & non-poison oper...
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
bool isGuardAsWidenableBranch(const User *U)
Returns true iff U has semantics of a guard expressed in a form of a widenable conditional branch to ...
void initializeGuardWideningLegacyPassPass(PassRegistry &)
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 ...
constexpr unsigned BitWidth
bool isKnownNonNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Returns true if the give value is known to be non-negative.
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
df_iterator< T > df_end(const T &G)
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Pass * createLoopGuardWideningPass()
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...