Go to the documentation of this file.
37 using namespace PatternMatch;
39 #define DEBUG_TYPE "constraint-elimination"
41 STATISTIC(NumCondsRemoved,
"Number of instructions removed");
43 "Controls which conditions are eliminated");
56 bool IsSigned =
false;
61 StackEntry(
unsigned NumIn,
unsigned NumOut,
bool IsNot,
bool IsSigned,
63 : NumIn(NumIn), NumOut(NumOut), IsNot(IsNot), IsSigned(IsSigned),
64 ValuesToRelease(ValuesToRelease) {}
68 struct PreconditionTy {
74 : Pred(Pred), Op0(Op0), Op1(Op1) {}
81 bool IsSigned =
false;
84 ConstraintTy() =
default;
87 : Coefficients(Coefficients), IsSigned(IsSigned) {}
89 unsigned size()
const {
return Coefficients.size(); }
91 unsigned empty()
const {
return Coefficients.empty(); }
97 for (
unsigned I = 0;
I < NewIndices.
size(); ++
I) {
116 class ConstraintInfo {
125 return Signed ? SignedValue2Index : UnsignedValue2Index;
128 return Signed ? SignedValue2Index : UnsignedValue2Index;
132 return Signed ? SignedCS : UnsignedCS;
135 return Signed ? SignedCS : UnsignedCS;
139 void popLastNVariables(
bool Signed,
unsigned N) {
140 getCS(
Signed).popLastNVariables(
N);
146 unsigned NumIn,
unsigned NumOut,
161 Cmp->getOperand(1), NewIndices);
167 bool IsNegated,
unsigned NumIn,
unsigned NumOut,
182 const APInt &Val = CI->getValue();
187 if (
auto *CI = dyn_cast<ConstantInt>(V)) {
189 return {{CI->getSExtValue(),
nullptr}};
192 return {{0,
nullptr}, {1, V}};
195 if (
auto *CI = dyn_cast<ConstantInt>(V)) {
198 return {{CI->getZExtValue(),
nullptr}};
200 auto *
GEP = dyn_cast<GetElementPtrInst>(V);
201 if (
GEP &&
GEP->getNumOperands() == 2 &&
GEP->isInBounds()) {
206 if (
match(
GEP->getOperand(
GEP->getNumOperands() - 1),
210 return {{0,
nullptr},
211 {1,
GEP->getPointerOperand()},
216 {1,
GEP->getPointerOperand()},
218 return {{0,
nullptr}, {1,
GEP->getPointerOperand()}, {1, Op0}};
226 if (
match(
GEP->getOperand(
GEP->getNumOperands() - 1),
229 Result = {{0,
nullptr},
230 {1,
GEP->getPointerOperand()},
232 else if (
match(
GEP->getOperand(
GEP->getNumOperands() - 1),
236 {1,
GEP->getPointerOperand()},
239 Op0 =
GEP->getOperand(
GEP->getNumOperands() - 1);
240 Result = {{0,
nullptr}, {1,
GEP->getPointerOperand()}, {1, Op0}};
266 return {{0,
nullptr}, {1, Op0}, {1, Op1}};
271 return {{0,
nullptr}, {1, Op0}, {-1, Op1}};
273 return {{0,
nullptr}, {1, V}};
315 auto &Value2Index = getValue2Index(IsSigned);
317 Preconditions, IsSigned);
319 Preconditions, IsSigned);
321 if (ADec.empty() || BDec.empty())
324 int64_t Offset1 = ADec[0].first;
325 int64_t Offset2 = BDec[0].first;
334 auto GetOrAddIndex = [&Value2Index, &NewIndices](
Value *V) ->
unsigned {
335 auto V2I = Value2Index.find(V);
336 if (V2I != Value2Index.end())
339 NewIndices.
insert({V, Value2Index.size() + NewIndices.
size() + 1});
340 return Insert.first->second;
344 for (
const auto &KV :
345 concat<std::pair<int64_t, Value *>>(VariablesA, VariablesB))
346 GetOrAddIndex(KV.second);
354 auto &
R = Res.Coefficients;
355 for (
const auto &KV : VariablesA)
356 R[GetOrAddIndex(KV.second)] += KV.first;
358 for (
const auto &KV : VariablesB)
359 R[GetOrAddIndex(KV.second)] -= KV.first;
365 if (
AddOverflow(OffsetSum, int64_t(-1), OffsetSum))
368 Res.Preconditions =
std::move(Preconditions);
373 return Coefficients.size() > 0 &&
374 all_of(Preconditions, [&
Info](
const PreconditionTy &
C) {
375 return Info.doesHold(
C.Pred,
C.Op0,
C.Op1);
384 if (!NewIndices.
empty())
388 return NewIndices.
empty() &&
R.Preconditions.empty() && !
R.IsEq &&
393 void ConstraintInfo::transferToOtherSystem(
398 if (!
A->getType()->isIntegerTy())
410 IsNegated, NumIn, NumOut, DFSInStack);
421 IsNegated, NumIn, NumOut, DFSInStack);
434 struct ConstraintOrBlock {
445 : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(
true),
446 BB(DTN->getBlock()) {}
448 : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(
false),
449 Not(Not), Condition(Condition) {}
467 if (
BB.getSingleSuccessor()) {
468 assert(
BB.getSingleSuccessor() == Succ);
485 for (
auto &KV : Value2Index) {
486 Names[KV.second - 1] = std::string(
"%") + KV.first->getName().str();
503 bool GuaranteedToExecute =
true;
513 isa<ICmpInst>(
Cond)) {
514 if (GuaranteedToExecute) {
521 if (!canAddSuccessor(
BB, Succ))
530 auto *Br = dyn_cast<BranchInst>(
BB.getTerminator());
531 if (!Br || !Br->isConditional())
539 isa<ICmpInst>(Op0) && isa<ICmpInst>(Op1)) {
540 BasicBlock *FalseSuccessor = Br->getSuccessor(1);
541 if (canAddSuccessor(
BB, FalseSuccessor)) {
554 isa<ICmpInst>(Op0) && isa<ICmpInst>(Op1)) {
555 BasicBlock *TrueSuccessor = Br->getSuccessor(0);
556 if (canAddSuccessor(
BB, TrueSuccessor)) {
565 auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition());
568 if (canAddSuccessor(
BB, Br->getSuccessor(0)))
570 if (canAddSuccessor(
BB, Br->getSuccessor(1)))
575 bool IsNegated,
unsigned NumIn,
unsigned NumOut,
581 if (!
R.isValid(*
this))
587 "condition and constraint signs must match");
588 auto &CSToUse = getCS(
R.IsSigned);
589 if (
R.Coefficients.empty())
592 Added |= CSToUse.addVariableRowFill(
R.Coefficients);
598 for (
auto &KV : NewIndices) {
599 getValue2Index(
R.IsSigned).
insert(KV);
600 ValuesToRelease.push_back(KV.first);
604 dbgs() <<
" constraint: ";
608 DFSInStack.
emplace_back(NumIn, NumOut, IsNegated,
R.IsSigned,
613 for (
auto &Coeff :
R.Coefficients)
615 CSToUse.addVariableRowFill(
R.Coefficients);
617 DFSInStack.
emplace_back(NumIn, NumOut, IsNegated,
R.IsSigned,
627 ConstraintInfo &
Info) {
629 auto R =
Info.getConstraint(Pred, A,
B, NewIndices);
630 if (R.size() < 2 || R.needsNewIndices(NewIndices) || !R.isValid(
Info))
634 return CSToUse.isConditionImplied(R.Coefficients);
648 Value *Sub =
nullptr;
653 U->replaceAllUsesWith(Sub);
655 U->replaceAllUsesWith(
Builder.getFalse());
659 if (U->use_empty()) {
660 auto *
I = cast<Instruction>(U);
672 bool Changed =
false;
690 stable_sort(
S.WorkList, [](
const ConstraintOrBlock &A,
const ConstraintOrBlock &
B) {
691 return std::tie(A.NumIn, A.IsBlock) < std::tie(B.NumIn, B.IsBlock);
698 for (ConstraintOrBlock &CB :
S.WorkList) {
701 while (!DFSInStack.empty()) {
702 auto &
E = DFSInStack.back();
705 LLVM_DEBUG(
dbgs() <<
"CB: " << CB.NumIn <<
" " << CB.NumOut <<
"\n");
707 if (CB.NumOut <=
E.NumOut)
710 dbgs() <<
"Removing ";
712 Info.getValue2Index(
E.IsSigned));
716 Info.popLastConstraint(
E.IsSigned);
718 auto &Mapping =
Info.getValue2Index(
E.IsSigned);
719 for (
Value *V :
E.ValuesToRelease)
721 Info.popLastNVariables(
E.IsSigned,
E.ValuesToRelease.size());
722 DFSInStack.pop_back();
726 dbgs() <<
"Processing ";
730 dbgs() << *CB.Condition;
738 if (
auto *II = dyn_cast<WithOverflowInst>(&
I)) {
742 auto *Cmp = dyn_cast<ICmpInst>(&
I);
747 auto R =
Info.getConstraint(Cmp, NewIndices);
748 if (R.IsEq || R.empty() || R.needsNewIndices(NewIndices) ||
752 auto &CSToUse =
Info.getCS(R.IsSigned);
753 if (CSToUse.isConditionImplied(R.Coefficients)) {
758 dbgs() <<
"Condition " << *Cmp
759 <<
" implied by dominating constraints\n";
762 Cmp->replaceUsesWithIf(
766 auto *II = dyn_cast<IntrinsicInst>(U.getUser());
767 return !II || II->getIntrinsicID() != Intrinsic::assume;
772 if (CSToUse.isConditionImplied(
778 dbgs() <<
"Condition !" << *Cmp
779 <<
" implied by dominating constraints\n";
782 Cmp->replaceAllUsesWith(
793 auto *CI = dyn_cast<ICmpInst>(CB.Condition);
796 CI->setPredicate(CI->getInversePredicate());
800 CI->setPredicate(CI->getInversePredicate());
812 Info.addFact(Pred, A,
B, CB.Not, CB.NumIn, CB.NumOut, DFSInStack);
813 Info.transferToOtherSystem(Pred, A,
B, CB.Not, CB.NumIn, CB.NumOut,
819 unsigned SignedEntries =
820 count_if(DFSInStack, [](
const StackEntry &
E) {
return E.IsSigned; });
821 assert(
Info.getCS(
false).size() == DFSInStack.size() - SignedEntries &&
822 "updates to CS and DFSInStack are out of sync");
823 assert(
Info.getCS(
true).size() == SignedEntries &&
824 "updates to CS and DFSInStack are out of sync");
828 I->eraseFromParent();
855 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
872 "Constraint Elimination",
false,
false)
879 return new ConstraintElimination();
A set of analyses that are preserved following a run of a transformation pass.
static int64_t MaxConstraintValue
void initializeConstraintEliminationPass(PassRegistry &)
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Vector Rotate Left Mask Mask Insert
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
ReachingDefAnalysis InstSet & ToRemove
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWShl(const LHS &L, const RHS &R)
@ ICMP_SGT
signed greater than
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
DEBUG_COUNTER(EliminatedCounter, "conds-eliminated", "Controls which conditions are eliminated")
auto successors(MachineBasicBlock *BB)
@ ICMP_SLE
signed less or equal
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
LLVM_NODISCARD T pop_back_val()
static void dumpWithNames(const ConstraintSystem &CS, DenseMap< Value *, unsigned > &Value2Index)
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
LLVM Basic Block Representation.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
This is the shared class of boolean and integer constants.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
static bool eliminateConstraints(Function &F, DominatorTree &DT)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool match(Val *V, const Pattern &P)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
(vector float) vec_cmpeq(*A, *B) C
@ ICMP_ULE
unsigned less or equal
Represent the analysis usage information of a pass.
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
LLVM_NODISCARD detail::scope_exit< typename std::decay< Callable >::type > make_scope_exit(Callable &&F)
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
static bool shouldExecute(unsigned CounterName)
Legacy analysis pass which computes a DominatorTree.
STATISTIC(NumFunctions, "Total number of functions")
auto predecessors(MachineBasicBlock *BB)
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.
std::enable_if_t< std::is_signed< T >::value, T > AddOverflow(T X, T Y, T &Result)
Add two signed integers, computing the two's complement truncated result, returning true if overflow ...
Analysis containing CSE Info
void updateDFSNumbers() const
updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
static VConstraintType getConstraint(uint64_t TSFlags)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)
INITIALIZE_PASS_BEGIN(ConstraintElimination, "constraint-elimination", "Constraint Elimination", false, false) INITIALIZE_PASS_END(ConstraintElimination
This class is the base class for the comparison instructions.
const Value * stripPointerCastsSameRepresentation() const
Strip off pointer casts, all-zero GEPs and address space casts but ensures the representation of the ...
bool slt(const APInt &RHS) const
Signed less than comparison.
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
static SmallVector< int64_t, 8 > negate(SmallVector< int64_t, 8 > R)
LogicalOp_match< LHS, RHS, Instruction::Or > m_LogicalOr(const LHS &L, const RHS &R)
Matches L || R either in the form of L | R or L ? true : R.
Wrapper around LazyValueInfo.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
void preserve()
Mark an analysis as preserved.
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
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...
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&... Ranges)
Concatenated range across two or more ranges.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
@ ICMP_UGE
unsigned greater or equal
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Class for arbitrary precision integers.
@ ICMP_SLT
signed less than
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
SmallVector< MachineOperand, 4 > Cond
void setPreservesCFG()
This function should be called by the pass, iff they do not:
@ ICMP_ULT
unsigned less than
Type * getType() const
All values are typed, get the type of this value.
Represents analyses that only rely on functions' control flow.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
self_iterator getIterator()
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
static int64_t MinSignedConstraintValue
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
static ConstantInt * getFalse(LLVMContext &Context)
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
LLVM_NODISCARD bool empty() const
static bool runOnFunction(Function &F, bool PostInlining)
void stable_sort(R &&Range)
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
static ConstantInt * getTrue(LLVMContext &Context)
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
bool uge(uint64_t Num) const
This function will return true iff this constant represents a value with active bits bigger than 64 b...
@ ICMP_SGE
signed greater or equal
A wrapper class for inspecting calls to intrinsic functions.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWSub(const LHS &L, const RHS &R)
Analysis pass which computes a DominatorTree.
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
void preserveSet()
Mark an analysis set as preserved.
FunctionPass * createConstraintEliminationPass()
static void tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
@ ICMP_UGT
unsigned greater than
Value * getArgOperand(unsigned i) const
const BasicBlock * getParent() const
static SmallVector< std::pair< int64_t, Value * >, 4 > decompose(Value *V, SmallVector< PreconditionTy, 4 > &Preconditions, bool IsSigned)
Legacy wrapper pass to provide the GlobalsAAResult object.
bool addVariableRowFill(ArrayRef< int64_t > R)
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
bool sgt(const APInt &RHS) const
Signed greater than comparison.
A container for analyses that lazily runs them and caches their results.
FunctionPass class - This class is used to implement most global optimizations.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
AnalysisUsage & addRequired()
LLVM Value Representation.
iterator_range< user_iterator > users()
constraint Constraint Elimination
LogicalOp_match< LHS, RHS, Instruction::And > m_LogicalAnd(const LHS &L, const RHS &R)
Matches L && R either in the form of L & R or L ? R : false.
A Use represents the edge between a Value definition and its users.
reference emplace_back(ArgTypes &&... Args)
iterator insert(iterator I, T &&Elt)
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.