LLVM 17.0.0git
ConstraintElimination.cpp
Go to the documentation of this file.
1//===-- ConstraintElimination.cpp - Eliminate conds using constraints. ----===//
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// Eliminate conditions based on constraints collected from dominating
10// conditions.
11//
12//===----------------------------------------------------------------------===//
13
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/ScopeExit.h"
18#include "llvm/ADT/Statistic.h"
23#include "llvm/IR/DataLayout.h"
24#include "llvm/IR/Dominators.h"
25#include "llvm/IR/Function.h"
27#include "llvm/IR/IRBuilder.h"
30#include "llvm/IR/Verifier.h"
31#include "llvm/Pass.h"
33#include "llvm/Support/Debug.h"
39
40#include <cmath>
41#include <string>
42
43using namespace llvm;
44using namespace PatternMatch;
45
46#define DEBUG_TYPE "constraint-elimination"
47
48STATISTIC(NumCondsRemoved, "Number of instructions removed");
49DEBUG_COUNTER(EliminatedCounter, "conds-eliminated",
50 "Controls which conditions are eliminated");
51
53 MaxRows("constraint-elimination-max-rows", cl::init(500), cl::Hidden,
54 cl::desc("Maximum number of rows to keep in constraint system"));
55
57 "constraint-elimination-dump-reproducers", cl::init(false), cl::Hidden,
58 cl::desc("Dump IR to reproduce successful transformations."));
59
60static int64_t MaxConstraintValue = std::numeric_limits<int64_t>::max();
61static int64_t MinSignedConstraintValue = std::numeric_limits<int64_t>::min();
62
63// A helper to multiply 2 signed integers where overflowing is allowed.
64static int64_t multiplyWithOverflow(int64_t A, int64_t B) {
65 int64_t Result;
66 MulOverflow(A, B, Result);
67 return Result;
68}
69
70// A helper to add 2 signed integers where overflowing is allowed.
71static int64_t addWithOverflow(int64_t A, int64_t B) {
72 int64_t Result;
73 AddOverflow(A, B, Result);
74 return Result;
75}
76
77namespace {
78
79class ConstraintInfo;
80
81struct StackEntry {
82 unsigned NumIn;
83 unsigned NumOut;
84 bool IsSigned = false;
85 /// Variables that can be removed from the system once the stack entry gets
86 /// removed.
87 SmallVector<Value *, 2> ValuesToRelease;
88
89 StackEntry(unsigned NumIn, unsigned NumOut, bool IsSigned,
90 SmallVector<Value *, 2> ValuesToRelease)
91 : NumIn(NumIn), NumOut(NumOut), IsSigned(IsSigned),
92 ValuesToRelease(ValuesToRelease) {}
93};
94
95/// Struct to express a pre-condition of the form %Op0 Pred %Op1.
96struct PreconditionTy {
98 Value *Op0;
99 Value *Op1;
100
101 PreconditionTy(CmpInst::Predicate Pred, Value *Op0, Value *Op1)
102 : Pred(Pred), Op0(Op0), Op1(Op1) {}
103};
104
105struct ConstraintTy {
106 SmallVector<int64_t, 8> Coefficients;
107 SmallVector<PreconditionTy, 2> Preconditions;
108
110
111 bool IsSigned = false;
112 bool IsEq = false;
113
114 ConstraintTy() = default;
115
116 ConstraintTy(SmallVector<int64_t, 8> Coefficients, bool IsSigned)
117 : Coefficients(Coefficients), IsSigned(IsSigned) {}
118
119 unsigned size() const { return Coefficients.size(); }
120
121 unsigned empty() const { return Coefficients.empty(); }
122
123 /// Returns true if all preconditions for this list of constraints are
124 /// satisfied given \p CS and the corresponding \p Value2Index mapping.
125 bool isValid(const ConstraintInfo &Info) const;
126};
127
128/// Wrapper encapsulating separate constraint systems and corresponding value
129/// mappings for both unsigned and signed information. Facts are added to and
130/// conditions are checked against the corresponding system depending on the
131/// signed-ness of their predicates. While the information is kept separate
132/// based on signed-ness, certain conditions can be transferred between the two
133/// systems.
134class ConstraintInfo {
135
136 ConstraintSystem UnsignedCS;
137 ConstraintSystem SignedCS;
138
139 const DataLayout &DL;
140
141public:
142 ConstraintInfo(const DataLayout &DL) : DL(DL) {}
143
144 DenseMap<Value *, unsigned> &getValue2Index(bool Signed) {
145 return Signed ? SignedCS.getValue2Index() : UnsignedCS.getValue2Index();
146 }
147 const DenseMap<Value *, unsigned> &getValue2Index(bool Signed) const {
148 return Signed ? SignedCS.getValue2Index() : UnsignedCS.getValue2Index();
149 }
150
151 ConstraintSystem &getCS(bool Signed) {
152 return Signed ? SignedCS : UnsignedCS;
153 }
154 const ConstraintSystem &getCS(bool Signed) const {
155 return Signed ? SignedCS : UnsignedCS;
156 }
157
158 void popLastConstraint(bool Signed) { getCS(Signed).popLastConstraint(); }
159 void popLastNVariables(bool Signed, unsigned N) {
160 getCS(Signed).popLastNVariables(N);
161 }
162
163 bool doesHold(CmpInst::Predicate Pred, Value *A, Value *B) const;
164
165 void addFact(CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,
166 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack);
167
168 /// Turn a comparison of the form \p Op0 \p Pred \p Op1 into a vector of
169 /// constraints, using indices from the corresponding constraint system.
170 /// New variables that need to be added to the system are collected in
171 /// \p NewVariables.
172 ConstraintTy getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,
173 SmallVectorImpl<Value *> &NewVariables) const;
174
175 /// Turns a comparison of the form \p Op0 \p Pred \p Op1 into a vector of
176 /// constraints using getConstraint. Returns an empty constraint if the result
177 /// cannot be used to query the existing constraint system, e.g. because it
178 /// would require adding new variables. Also tries to convert signed
179 /// predicates to unsigned ones if possible to allow using the unsigned system
180 /// which increases the effectiveness of the signed <-> unsigned transfer
181 /// logic.
182 ConstraintTy getConstraintForSolving(CmpInst::Predicate Pred, Value *Op0,
183 Value *Op1) const;
184
185 /// Try to add information from \p A \p Pred \p B to the unsigned/signed
186 /// system if \p Pred is signed/unsigned.
187 void transferToOtherSystem(CmpInst::Predicate Pred, Value *A, Value *B,
188 unsigned NumIn, unsigned NumOut,
189 SmallVectorImpl<StackEntry> &DFSInStack);
190};
191
192/// Represents a (Coefficient * Variable) entry after IR decomposition.
193struct DecompEntry {
194 int64_t Coefficient;
195 Value *Variable;
196 /// True if the variable is known positive in the current constraint.
197 bool IsKnownNonNegative;
198
199 DecompEntry(int64_t Coefficient, Value *Variable,
200 bool IsKnownNonNegative = false)
201 : Coefficient(Coefficient), Variable(Variable),
202 IsKnownNonNegative(IsKnownNonNegative) {}
203};
204
205/// Represents an Offset + Coefficient1 * Variable1 + ... decomposition.
206struct Decomposition {
207 int64_t Offset = 0;
209
210 Decomposition(int64_t Offset) : Offset(Offset) {}
211 Decomposition(Value *V, bool IsKnownNonNegative = false) {
212 Vars.emplace_back(1, V, IsKnownNonNegative);
213 }
214 Decomposition(int64_t Offset, ArrayRef<DecompEntry> Vars)
215 : Offset(Offset), Vars(Vars) {}
216
217 void add(int64_t OtherOffset) {
218 Offset = addWithOverflow(Offset, OtherOffset);
219 }
220
221 void add(const Decomposition &Other) {
222 add(Other.Offset);
223 append_range(Vars, Other.Vars);
224 }
225
226 void mul(int64_t Factor) {
227 Offset = multiplyWithOverflow(Offset, Factor);
228 for (auto &Var : Vars)
229 Var.Coefficient = multiplyWithOverflow(Var.Coefficient, Factor);
230 }
231};
232
233} // namespace
234
235static Decomposition decompose(Value *V,
236 SmallVectorImpl<PreconditionTy> &Preconditions,
237 bool IsSigned, const DataLayout &DL);
238
239static bool canUseSExt(ConstantInt *CI) {
240 const APInt &Val = CI->getValue();
242}
243
244static Decomposition
246 bool IsSigned, const DataLayout &DL) {
247 // Do not reason about pointers where the index size is larger than 64 bits,
248 // as the coefficients used to encode constraints are 64 bit integers.
249 if (DL.getIndexTypeSizeInBits(GEP.getPointerOperand()->getType()) > 64)
250 return &GEP;
251
252 if (!GEP.isInBounds())
253 return &GEP;
254
255 assert(!IsSigned && "The logic below only supports decomposition for "
256 "unsinged predicates at the moment.");
257 Type *PtrTy = GEP.getType()->getScalarType();
258 unsigned BitWidth = DL.getIndexTypeSizeInBits(PtrTy);
259 MapVector<Value *, APInt> VariableOffsets;
260 APInt ConstantOffset(BitWidth, 0);
261 if (!GEP.collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset))
262 return &GEP;
263
264 // Handle the (gep (gep ....), C) case by incrementing the constant
265 // coefficient of the inner GEP, if C is a constant.
266 auto *InnerGEP = dyn_cast<GEPOperator>(GEP.getPointerOperand());
267 if (VariableOffsets.empty() && InnerGEP && InnerGEP->getNumOperands() == 2) {
268 auto Result = decompose(InnerGEP, Preconditions, IsSigned, DL);
269 Result.add(ConstantOffset.getSExtValue());
270
271 if (ConstantOffset.isNegative()) {
272 unsigned Scale = DL.getTypeAllocSize(InnerGEP->getResultElementType());
273 int64_t ConstantOffsetI = ConstantOffset.getSExtValue();
274 if (ConstantOffsetI % Scale != 0)
275 return &GEP;
276 // Add pre-condition ensuring the GEP is increasing monotonically and
277 // can be de-composed.
278 // Both sides are normalized by being divided by Scale.
279 Preconditions.emplace_back(
280 CmpInst::ICMP_SGE, InnerGEP->getOperand(1),
281 ConstantInt::get(InnerGEP->getOperand(1)->getType(),
282 -1 * (ConstantOffsetI / Scale)));
283 }
284 return Result;
285 }
286
287 Decomposition Result(ConstantOffset.getSExtValue(),
288 DecompEntry(1, GEP.getPointerOperand()));
289 for (auto [Index, Scale] : VariableOffsets) {
290 auto IdxResult = decompose(Index, Preconditions, IsSigned, DL);
291 IdxResult.mul(Scale.getSExtValue());
292 Result.add(IdxResult);
293
294 // If Op0 is signed non-negative, the GEP is increasing monotonically and
295 // can be de-composed.
297 Preconditions.emplace_back(CmpInst::ICMP_SGE, Index,
298 ConstantInt::get(Index->getType(), 0));
299 }
300 return Result;
301}
302
303// Decomposes \p V into a constant offset + list of pairs { Coefficient,
304// Variable } where Coefficient * Variable. The sum of the constant offset and
305// pairs equals \p V.
306static Decomposition decompose(Value *V,
307 SmallVectorImpl<PreconditionTy> &Preconditions,
308 bool IsSigned, const DataLayout &DL) {
309
310 auto MergeResults = [&Preconditions, IsSigned, &DL](Value *A, Value *B,
311 bool IsSignedB) {
312 auto ResA = decompose(A, Preconditions, IsSigned, DL);
313 auto ResB = decompose(B, Preconditions, IsSignedB, DL);
314 ResA.add(ResB);
315 return ResA;
316 };
317
318 // Decompose \p V used with a signed predicate.
319 if (IsSigned) {
320 if (auto *CI = dyn_cast<ConstantInt>(V)) {
321 if (canUseSExt(CI))
322 return CI->getSExtValue();
323 }
324 Value *Op0;
325 Value *Op1;
326 if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1))))
327 return MergeResults(Op0, Op1, IsSigned);
328
329 return V;
330 }
331
332 if (auto *CI = dyn_cast<ConstantInt>(V)) {
333 if (CI->uge(MaxConstraintValue))
334 return V;
335 return int64_t(CI->getZExtValue());
336 }
337
338 if (auto *GEP = dyn_cast<GEPOperator>(V))
339 return decomposeGEP(*GEP, Preconditions, IsSigned, DL);
340
341 Value *Op0;
342 bool IsKnownNonNegative = false;
343 if (match(V, m_ZExt(m_Value(Op0)))) {
344 IsKnownNonNegative = true;
345 V = Op0;
346 }
347
348 Value *Op1;
349 ConstantInt *CI;
350 if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1)))) {
351 return MergeResults(Op0, Op1, IsSigned);
352 }
353 if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1)))) {
354 if (!isKnownNonNegative(Op0, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1))
355 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0,
356 ConstantInt::get(Op0->getType(), 0));
357 if (!isKnownNonNegative(Op1, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1))
358 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op1,
359 ConstantInt::get(Op1->getType(), 0));
360
361 return MergeResults(Op0, Op1, IsSigned);
362 }
363
364 if (match(V, m_Add(m_Value(Op0), m_ConstantInt(CI))) && CI->isNegative() &&
365 canUseSExt(CI)) {
366 Preconditions.emplace_back(
368 ConstantInt::get(Op0->getType(), CI->getSExtValue() * -1));
369 return MergeResults(Op0, CI, true);
370 }
371
372 // Decompose or as an add if there are no common bits between the operands.
373 if (match(V, m_Or(m_Value(Op0), m_ConstantInt(CI))) &&
374 haveNoCommonBitsSet(Op0, CI, DL)) {
375 return MergeResults(Op0, CI, IsSigned);
376 }
377
378 if (match(V, m_NUWShl(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI)) {
379 if (CI->getSExtValue() < 0 || CI->getSExtValue() >= 64)
380 return {V, IsKnownNonNegative};
381 auto Result = decompose(Op1, Preconditions, IsSigned, DL);
382 Result.mul(int64_t{1} << CI->getSExtValue());
383 return Result;
384 }
385
386 if (match(V, m_NUWMul(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI) &&
387 (!CI->isNegative())) {
388 auto Result = decompose(Op1, Preconditions, IsSigned, DL);
389 Result.mul(CI->getSExtValue());
390 return Result;
391 }
392
393 if (match(V, m_NUWSub(m_Value(Op0), m_ConstantInt(CI))) && canUseSExt(CI))
394 return {-1 * CI->getSExtValue(), {{1, Op0}}};
395 if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1))))
396 return {0, {{1, Op0}, {-1, Op1}}};
397
398 return {V, IsKnownNonNegative};
399}
400
401ConstraintTy
402ConstraintInfo::getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,
403 SmallVectorImpl<Value *> &NewVariables) const {
404 assert(NewVariables.empty() && "NewVariables must be empty when passed in");
405 bool IsEq = false;
406 // Try to convert Pred to one of ULE/SLT/SLE/SLT.
407 switch (Pred) {
411 case CmpInst::ICMP_SGE: {
412 Pred = CmpInst::getSwappedPredicate(Pred);
413 std::swap(Op0, Op1);
414 break;
415 }
416 case CmpInst::ICMP_EQ:
417 if (match(Op1, m_Zero())) {
418 Pred = CmpInst::ICMP_ULE;
419 } else {
420 IsEq = true;
421 Pred = CmpInst::ICMP_ULE;
422 }
423 break;
424 case CmpInst::ICMP_NE:
425 if (!match(Op1, m_Zero()))
426 return {};
428 std::swap(Op0, Op1);
429 break;
430 default:
431 break;
432 }
433
434 if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT &&
435 Pred != CmpInst::ICMP_SLE && Pred != CmpInst::ICMP_SLT)
436 return {};
437
438 SmallVector<PreconditionTy, 4> Preconditions;
439 bool IsSigned = CmpInst::isSigned(Pred);
440 auto &Value2Index = getValue2Index(IsSigned);
442 Preconditions, IsSigned, DL);
444 Preconditions, IsSigned, DL);
445 int64_t Offset1 = ADec.Offset;
446 int64_t Offset2 = BDec.Offset;
447 Offset1 *= -1;
448
449 auto &VariablesA = ADec.Vars;
450 auto &VariablesB = BDec.Vars;
451
452 // First try to look up \p V in Value2Index and NewVariables. Otherwise add a
453 // new entry to NewVariables.
454 DenseMap<Value *, unsigned> NewIndexMap;
455 auto GetOrAddIndex = [&Value2Index, &NewVariables,
456 &NewIndexMap](Value *V) -> unsigned {
457 auto V2I = Value2Index.find(V);
458 if (V2I != Value2Index.end())
459 return V2I->second;
460 auto Insert =
461 NewIndexMap.insert({V, Value2Index.size() + NewVariables.size() + 1});
462 if (Insert.second)
463 NewVariables.push_back(V);
464 return Insert.first->second;
465 };
466
467 // Make sure all variables have entries in Value2Index or NewVariables.
468 for (const auto &KV : concat<DecompEntry>(VariablesA, VariablesB))
469 GetOrAddIndex(KV.Variable);
470
471 // Build result constraint, by first adding all coefficients from A and then
472 // subtracting all coefficients from B.
473 ConstraintTy Res(
474 SmallVector<int64_t, 8>(Value2Index.size() + NewVariables.size() + 1, 0),
475 IsSigned);
476 // Collect variables that are known to be positive in all uses in the
477 // constraint.
478 DenseMap<Value *, bool> KnownNonNegativeVariables;
479 Res.IsEq = IsEq;
480 auto &R = Res.Coefficients;
481 for (const auto &KV : VariablesA) {
482 R[GetOrAddIndex(KV.Variable)] += KV.Coefficient;
483 auto I =
484 KnownNonNegativeVariables.insert({KV.Variable, KV.IsKnownNonNegative});
485 I.first->second &= KV.IsKnownNonNegative;
486 }
487
488 for (const auto &KV : VariablesB) {
489 R[GetOrAddIndex(KV.Variable)] -= KV.Coefficient;
490 auto I =
491 KnownNonNegativeVariables.insert({KV.Variable, KV.IsKnownNonNegative});
492 I.first->second &= KV.IsKnownNonNegative;
493 }
494
495 int64_t OffsetSum;
496 if (AddOverflow(Offset1, Offset2, OffsetSum))
497 return {};
498 if (Pred == (IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT))
499 if (AddOverflow(OffsetSum, int64_t(-1), OffsetSum))
500 return {};
501 R[0] = OffsetSum;
502 Res.Preconditions = std::move(Preconditions);
503
504 // Remove any (Coefficient, Variable) entry where the Coefficient is 0 for new
505 // variables.
506 while (!NewVariables.empty()) {
507 int64_t Last = R.back();
508 if (Last != 0)
509 break;
510 R.pop_back();
511 Value *RemovedV = NewVariables.pop_back_val();
512 NewIndexMap.erase(RemovedV);
513 }
514
515 // Add extra constraints for variables that are known positive.
516 for (auto &KV : KnownNonNegativeVariables) {
517 if (!KV.second ||
518 (!Value2Index.contains(KV.first) && !NewIndexMap.contains(KV.first)))
519 continue;
520 SmallVector<int64_t, 8> C(Value2Index.size() + NewVariables.size() + 1, 0);
521 C[GetOrAddIndex(KV.first)] = -1;
522 Res.ExtraInfo.push_back(C);
523 }
524 return Res;
525}
526
527ConstraintTy ConstraintInfo::getConstraintForSolving(CmpInst::Predicate Pred,
528 Value *Op0,
529 Value *Op1) const {
530 // If both operands are known to be non-negative, change signed predicates to
531 // unsigned ones. This increases the reasoning effectiveness in combination
532 // with the signed <-> unsigned transfer logic.
533 if (CmpInst::isSigned(Pred) &&
534 isKnownNonNegative(Op0, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1) &&
537
538 SmallVector<Value *> NewVariables;
539 ConstraintTy R = getConstraint(Pred, Op0, Op1, NewVariables);
540 if (R.IsEq || !NewVariables.empty())
541 return {};
542 return R;
543}
544
545bool ConstraintTy::isValid(const ConstraintInfo &Info) const {
546 return Coefficients.size() > 0 &&
547 all_of(Preconditions, [&Info](const PreconditionTy &C) {
548 return Info.doesHold(C.Pred, C.Op0, C.Op1);
549 });
550}
551
552bool ConstraintInfo::doesHold(CmpInst::Predicate Pred, Value *A,
553 Value *B) const {
554 auto R = getConstraintForSolving(Pred, A, B);
555 return R.Preconditions.empty() && !R.empty() &&
556 getCS(R.IsSigned).isConditionImplied(R.Coefficients);
557}
558
559void ConstraintInfo::transferToOtherSystem(
560 CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,
561 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack) {
562 // Check if we can combine facts from the signed and unsigned systems to
563 // derive additional facts.
564 if (!A->getType()->isIntegerTy())
565 return;
566 // FIXME: This currently depends on the order we add facts. Ideally we
567 // would first add all known facts and only then try to add additional
568 // facts.
569 switch (Pred) {
570 default:
571 break;
573 // If B is a signed positive constant, A >=s 0 and A <s B.
574 if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0))) {
575 addFact(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0), NumIn,
576 NumOut, DFSInStack);
577 addFact(CmpInst::ICMP_SLT, A, B, NumIn, NumOut, DFSInStack);
578 }
579 break;
581 if (doesHold(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0)))
582 addFact(CmpInst::ICMP_ULT, A, B, NumIn, NumOut, DFSInStack);
583 break;
585 if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), -1)))
586 addFact(CmpInst::ICMP_UGE, A, ConstantInt::get(B->getType(), 0), NumIn,
587 NumOut, DFSInStack);
588 break;
590 if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0))) {
591 addFact(CmpInst::ICMP_UGE, A, B, NumIn, NumOut, DFSInStack);
592 }
593 break;
594 }
595}
596
597namespace {
598/// Represents either
599/// * a condition that holds on entry to a block (=conditional fact)
600/// * an assume (=assume fact)
601/// * an instruction to simplify.
602/// It also tracks the Dominator DFS in and out numbers for each entry.
603struct FactOrCheck {
604 Instruction *Inst;
605 unsigned NumIn;
606 unsigned NumOut;
607 bool IsCheck;
608 bool Not;
609
610 FactOrCheck(DomTreeNode *DTN, Instruction *Inst, bool IsCheck, bool Not)
611 : Inst(Inst), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),
612 IsCheck(IsCheck), Not(Not) {}
613
614 static FactOrCheck getFact(DomTreeNode *DTN, Instruction *Inst,
615 bool Not = false) {
616 return FactOrCheck(DTN, Inst, false, Not);
617 }
618
619 static FactOrCheck getCheck(DomTreeNode *DTN, Instruction *Inst) {
620 return FactOrCheck(DTN, Inst, true, false);
621 }
622
623 bool isAssumeFact() const {
624 if (!IsCheck && isa<IntrinsicInst>(Inst)) {
625 assert(match(Inst, m_Intrinsic<Intrinsic::assume>()));
626 return true;
627 }
628 return false;
629 }
630
631 bool isConditionFact() const { return !IsCheck && isa<CmpInst>(Inst); }
632};
633
634/// Keep state required to build worklist.
635struct State {
636 DominatorTree &DT;
638
639 State(DominatorTree &DT) : DT(DT) {}
640
641 /// Process block \p BB and add known facts to work-list.
642 void addInfoFor(BasicBlock &BB);
643
644 /// Returns true if we can add a known condition from BB to its successor
645 /// block Succ.
646 bool canAddSuccessor(BasicBlock &BB, BasicBlock *Succ) const {
647 return DT.dominates(BasicBlockEdge(&BB, Succ), Succ);
648 }
649};
650
651} // namespace
652
653#ifndef NDEBUG
654
656 const DenseMap<Value *, unsigned> &Value2Index) {
657 ConstraintSystem CS(Value2Index);
659 CS.dump();
660}
661#endif
662
663void State::addInfoFor(BasicBlock &BB) {
664 // True as long as long as the current instruction is guaranteed to execute.
665 bool GuaranteedToExecute = true;
666 // Queue conditions and assumes.
667 for (Instruction &I : BB) {
668 if (auto Cmp = dyn_cast<ICmpInst>(&I)) {
669 WorkList.push_back(FactOrCheck::getCheck(DT.getNode(&BB), Cmp));
670 continue;
671 }
672
673 if (match(&I, m_Intrinsic<Intrinsic::ssub_with_overflow>())) {
674 WorkList.push_back(FactOrCheck::getCheck(DT.getNode(&BB), &I));
675 continue;
676 }
677
678 Value *Cond;
679 // For now, just handle assumes with a single compare as condition.
680 if (match(&I, m_Intrinsic<Intrinsic::assume>(m_Value(Cond))) &&
681 isa<ICmpInst>(Cond)) {
682 if (GuaranteedToExecute) {
683 // The assume is guaranteed to execute when BB is entered, hence Cond
684 // holds on entry to BB.
685 WorkList.emplace_back(FactOrCheck::getFact(DT.getNode(I.getParent()),
686 cast<Instruction>(Cond)));
687 } else {
688 WorkList.emplace_back(
689 FactOrCheck::getFact(DT.getNode(I.getParent()), &I));
690 }
691 }
692 GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(&I);
693 }
694
695 auto *Br = dyn_cast<BranchInst>(BB.getTerminator());
696 if (!Br || !Br->isConditional())
697 return;
698
699 Value *Cond = Br->getCondition();
700
701 // If the condition is a chain of ORs/AND and the successor only has the
702 // current block as predecessor, queue conditions for the successor.
703 Value *Op0, *Op1;
704 if (match(Cond, m_LogicalOr(m_Value(Op0), m_Value(Op1))) ||
705 match(Cond, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {
706 bool IsOr = match(Cond, m_LogicalOr());
707 bool IsAnd = match(Cond, m_LogicalAnd());
708 // If there's a select that matches both AND and OR, we need to commit to
709 // one of the options. Arbitrarily pick OR.
710 if (IsOr && IsAnd)
711 IsAnd = false;
712
713 BasicBlock *Successor = Br->getSuccessor(IsOr ? 1 : 0);
714 if (canAddSuccessor(BB, Successor)) {
715 SmallVector<Value *> CondWorkList;
717 auto QueueValue = [&CondWorkList, &SeenCond](Value *V) {
718 if (SeenCond.insert(V).second)
719 CondWorkList.push_back(V);
720 };
721 QueueValue(Op1);
722 QueueValue(Op0);
723 while (!CondWorkList.empty()) {
724 Value *Cur = CondWorkList.pop_back_val();
725 if (auto *Cmp = dyn_cast<ICmpInst>(Cur)) {
726 WorkList.emplace_back(
727 FactOrCheck::getFact(DT.getNode(Successor), Cmp, IsOr));
728 continue;
729 }
730 if (IsOr && match(Cur, m_LogicalOr(m_Value(Op0), m_Value(Op1)))) {
731 QueueValue(Op1);
732 QueueValue(Op0);
733 continue;
734 }
735 if (IsAnd && match(Cur, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {
736 QueueValue(Op1);
737 QueueValue(Op0);
738 continue;
739 }
740 }
741 }
742 return;
743 }
744
745 auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition());
746 if (!CmpI)
747 return;
748 if (canAddSuccessor(BB, Br->getSuccessor(0)))
749 WorkList.emplace_back(
750 FactOrCheck::getFact(DT.getNode(Br->getSuccessor(0)), CmpI));
751 if (canAddSuccessor(BB, Br->getSuccessor(1)))
752 WorkList.emplace_back(
753 FactOrCheck::getFact(DT.getNode(Br->getSuccessor(1)), CmpI, true));
754}
755
756namespace {
757/// Helper to keep track of a condition and if it should be treated as negated
758/// for reproducer construction.
759struct ReproducerEntry {
760 CmpInst *Cond;
761 bool IsNot;
762
763 ReproducerEntry(CmpInst *Cond, bool IsNot) : Cond(Cond), IsNot(IsNot) {}
764};
765} // namespace
766
767/// Helper function to generate a reproducer function for simplifying \p Cond.
768/// The reproducer function contains a series of @llvm.assume calls, one for
769/// each condition in \p Stack. For each condition, the operand instruction are
770/// cloned until we reach operands that have an entry in \p Value2Index. Those
771/// will then be added as function arguments. \p DT is used to order cloned
772/// instructions. The reproducer function will get added to \p M, if it is
773/// non-null. Otherwise no reproducer function is generated.
776 ConstraintInfo &Info, DominatorTree &DT) {
777 if (!M)
778 return;
779
780 LLVMContext &Ctx = Cond->getContext();
781
782 LLVM_DEBUG(dbgs() << "Creating reproducer for " << *Cond << "\n");
783
784 ValueToValueMapTy Old2New;
787 // Traverse Cond and its operands recursively until we reach a value that's in
788 // Value2Index or not an instruction, or not a operation that
789 // ConstraintElimination can decompose. Such values will be considered as
790 // external inputs to the reproducer, they are collected and added as function
791 // arguments later.
792 auto CollectArguments = [&](CmpInst *Cond) {
793 if (!Cond)
794 return;
795 auto &Value2Index =
796 Info.getValue2Index(CmpInst::isSigned(Cond->getPredicate()));
798 WorkList.push_back(Cond);
799 while (!WorkList.empty()) {
800 Value *V = WorkList.pop_back_val();
801 if (!Seen.insert(V).second)
802 continue;
803 if (Old2New.find(V) != Old2New.end())
804 continue;
805 if (isa<Constant>(V))
806 continue;
807
808 auto *I = dyn_cast<Instruction>(V);
809 if (Value2Index.contains(V) || !I ||
810 !isa<CmpInst, BinaryOperator, GEPOperator, CastInst>(V)) {
811 Old2New[V] = V;
812 Args.push_back(V);
813 LLVM_DEBUG(dbgs() << " found external input " << *V << "\n");
814 } else {
815 append_range(WorkList, I->operands());
816 }
817 }
818 };
819
820 for (auto &Entry : Stack)
821 CollectArguments(Entry.Cond);
822 CollectArguments(Cond);
823
824 SmallVector<Type *> ParamTys;
825 for (auto *P : Args)
826 ParamTys.push_back(P->getType());
827
828 FunctionType *FTy = FunctionType::get(Cond->getType(), ParamTys,
829 /*isVarArg=*/false);
830 Function *F = Function::Create(FTy, Function::ExternalLinkage,
831 Cond->getModule()->getName() +
832 Cond->getFunction()->getName() + "repro",
833 M);
834 // Add arguments to the reproducer function for each external value collected.
835 for (unsigned I = 0; I < Args.size(); ++I) {
836 F->getArg(I)->setName(Args[I]->getName());
837 Old2New[Args[I]] = F->getArg(I);
838 }
839
840 BasicBlock *Entry = BasicBlock::Create(Ctx, "entry", F);
841 IRBuilder<> Builder(Entry);
842 Builder.CreateRet(Builder.getTrue());
843 Builder.SetInsertPoint(Entry->getTerminator());
844
845 // Clone instructions in \p Ops and their operands recursively until reaching
846 // an value in Value2Index (external input to the reproducer). Update Old2New
847 // mapping for the original and cloned instructions. Sort instructions to
848 // clone by dominance, then insert the cloned instructions in the function.
849 auto CloneInstructions = [&](ArrayRef<Value *> Ops, bool IsSigned) {
850 SmallVector<Value *, 4> WorkList(Ops);
852 auto &Value2Index = Info.getValue2Index(IsSigned);
853 while (!WorkList.empty()) {
854 Value *V = WorkList.pop_back_val();
855 if (Old2New.find(V) != Old2New.end())
856 continue;
857
858 auto *I = dyn_cast<Instruction>(V);
859 if (!Value2Index.contains(V) && I) {
860 Old2New[V] = nullptr;
861 ToClone.push_back(I);
862 append_range(WorkList, I->operands());
863 }
864 }
865
866 sort(ToClone,
867 [&DT](Instruction *A, Instruction *B) { return DT.dominates(A, B); });
868 for (Instruction *I : ToClone) {
869 Instruction *Cloned = I->clone();
870 Old2New[I] = Cloned;
871 Old2New[I]->setName(I->getName());
872 Cloned->insertBefore(&*Builder.GetInsertPoint());
874 Cloned->setDebugLoc({});
875 }
876 };
877
878 // Materialize the assumptions for the reproducer using the entries in Stack.
879 // That is, first clone the operands of the condition recursively until we
880 // reach an external input to the reproducer and add them to the reproducer
881 // function. Then add an ICmp for the condition (with the inverse predicate if
882 // the entry is negated) and an assert using the ICmp.
883 for (auto &Entry : Stack) {
884 if (!Entry.Cond)
885 continue;
886
887 LLVM_DEBUG(dbgs() << " Materializing assumption " << *Entry.Cond << "\n");
888 CmpInst::Predicate Pred = Entry.Cond->getPredicate();
889 if (Entry.IsNot)
890 Pred = CmpInst::getInversePredicate(Pred);
891
892 CloneInstructions({Entry.Cond->getOperand(0), Entry.Cond->getOperand(1)},
893 CmpInst::isSigned(Entry.Cond->getPredicate()));
894
895 auto *Cmp = Builder.CreateICmp(Pred, Entry.Cond->getOperand(0),
896 Entry.Cond->getOperand(1));
897 Builder.CreateAssumption(Cmp);
898 }
899
900 // Finally, clone the condition to reproduce and remap instruction operands in
901 // the reproducer using Old2New.
902 CloneInstructions(Cond, CmpInst::isSigned(Cond->getPredicate()));
903 Entry->getTerminator()->setOperand(0, Cond);
904 remapInstructionsInBlocks({Entry}, Old2New);
905
906 assert(!verifyFunction(*F, &dbgs()));
907}
908
910 CmpInst *Cmp, ConstraintInfo &Info, Module *ReproducerModule,
911 ArrayRef<ReproducerEntry> ReproducerCondStack, DominatorTree &DT) {
912 LLVM_DEBUG(dbgs() << "Checking " << *Cmp << "\n");
913
914 CmpInst::Predicate Pred = Cmp->getPredicate();
915 Value *A = Cmp->getOperand(0);
916 Value *B = Cmp->getOperand(1);
917
918 auto R = Info.getConstraintForSolving(Pred, A, B);
919 if (R.empty() || !R.isValid(Info)){
920 LLVM_DEBUG(dbgs() << " failed to decompose condition\n");
921 return false;
922 }
923
924 auto &CSToUse = Info.getCS(R.IsSigned);
925
926 // If there was extra information collected during decomposition, apply
927 // it now and remove it immediately once we are done with reasoning
928 // about the constraint.
929 for (auto &Row : R.ExtraInfo)
930 CSToUse.addVariableRow(Row);
931 auto InfoRestorer = make_scope_exit([&]() {
932 for (unsigned I = 0; I < R.ExtraInfo.size(); ++I)
933 CSToUse.popLastConstraint();
934 });
935
936 bool Changed = false;
937 if (CSToUse.isConditionImplied(R.Coefficients)) {
938 if (!DebugCounter::shouldExecute(EliminatedCounter))
939 return false;
940
941 LLVM_DEBUG({
942 dbgs() << "Condition " << *Cmp << " implied by dominating constraints\n";
943 CSToUse.dump();
944 });
945 generateReproducer(Cmp, ReproducerModule, ReproducerCondStack, Info, DT);
946 Constant *TrueC =
948 Cmp->replaceUsesWithIf(TrueC, [](Use &U) {
949 // Conditions in an assume trivially simplify to true. Skip uses
950 // in assume calls to not destroy the available information.
951 auto *II = dyn_cast<IntrinsicInst>(U.getUser());
952 return !II || II->getIntrinsicID() != Intrinsic::assume;
953 });
954 NumCondsRemoved++;
955 Changed = true;
956 }
957 if (CSToUse.isConditionImplied(ConstraintSystem::negate(R.Coefficients))) {
958 if (!DebugCounter::shouldExecute(EliminatedCounter))
959 return false;
960
961 LLVM_DEBUG({
962 dbgs() << "Condition !" << *Cmp << " implied by dominating constraints\n";
963 CSToUse.dump();
964 });
965 generateReproducer(Cmp, ReproducerModule, ReproducerCondStack, Info, DT);
966 Constant *FalseC =
968 Cmp->replaceAllUsesWith(FalseC);
969 NumCondsRemoved++;
970 Changed = true;
971 }
972 return Changed;
973}
974
975void ConstraintInfo::addFact(CmpInst::Predicate Pred, Value *A, Value *B,
976 unsigned NumIn, unsigned NumOut,
977 SmallVectorImpl<StackEntry> &DFSInStack) {
978 // If the constraint has a pre-condition, skip the constraint if it does not
979 // hold.
980 SmallVector<Value *> NewVariables;
981 auto R = getConstraint(Pred, A, B, NewVariables);
982 if (!R.isValid(*this))
983 return;
984
985 LLVM_DEBUG(dbgs() << "Adding '" << Pred << " ";
986 A->printAsOperand(dbgs(), false); dbgs() << ", ";
987 B->printAsOperand(dbgs(), false); dbgs() << "'\n");
988 bool Added = false;
989 auto &CSToUse = getCS(R.IsSigned);
990 if (R.Coefficients.empty())
991 return;
992
993 Added |= CSToUse.addVariableRowFill(R.Coefficients);
994
995 // If R has been added to the system, add the new variables and queue it for
996 // removal once it goes out-of-scope.
997 if (Added) {
998 SmallVector<Value *, 2> ValuesToRelease;
999 auto &Value2Index = getValue2Index(R.IsSigned);
1000 for (Value *V : NewVariables) {
1001 Value2Index.insert({V, Value2Index.size() + 1});
1002 ValuesToRelease.push_back(V);
1003 }
1004
1005 LLVM_DEBUG({
1006 dbgs() << " constraint: ";
1007 dumpConstraint(R.Coefficients, getValue2Index(R.IsSigned));
1008 dbgs() << "\n";
1009 });
1010
1011 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,
1012 std::move(ValuesToRelease));
1013
1014 if (R.IsEq) {
1015 // Also add the inverted constraint for equality constraints.
1016 for (auto &Coeff : R.Coefficients)
1017 Coeff *= -1;
1018 CSToUse.addVariableRowFill(R.Coefficients);
1019
1020 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,
1022 }
1023 }
1024}
1025
1028 bool Changed = false;
1030 Value *Sub = nullptr;
1031 for (User *U : make_early_inc_range(II->users())) {
1032 if (match(U, m_ExtractValue<0>(m_Value()))) {
1033 if (!Sub)
1034 Sub = Builder.CreateSub(A, B);
1035 U->replaceAllUsesWith(Sub);
1036 Changed = true;
1037 } else if (match(U, m_ExtractValue<1>(m_Value()))) {
1038 U->replaceAllUsesWith(Builder.getFalse());
1039 Changed = true;
1040 } else
1041 continue;
1042
1043 if (U->use_empty()) {
1044 auto *I = cast<Instruction>(U);
1045 ToRemove.push_back(I);
1046 I->setOperand(0, PoisonValue::get(II->getType()));
1047 Changed = true;
1048 }
1049 }
1050
1051 if (II->use_empty()) {
1052 II->eraseFromParent();
1053 Changed = true;
1054 }
1055 return Changed;
1056}
1057
1058static bool
1061 auto DoesConditionHold = [](CmpInst::Predicate Pred, Value *A, Value *B,
1062 ConstraintInfo &Info) {
1063 auto R = Info.getConstraintForSolving(Pred, A, B);
1064 if (R.size() < 2 || !R.isValid(Info))
1065 return false;
1066
1067 auto &CSToUse = Info.getCS(R.IsSigned);
1068 return CSToUse.isConditionImplied(R.Coefficients);
1069 };
1070
1071 bool Changed = false;
1072 if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow) {
1073 // If A s>= B && B s>= 0, ssub.with.overflow(a, b) should not overflow and
1074 // can be simplified to a regular sub.
1075 Value *A = II->getArgOperand(0);
1076 Value *B = II->getArgOperand(1);
1077 if (!DoesConditionHold(CmpInst::ICMP_SGE, A, B, Info) ||
1078 !DoesConditionHold(CmpInst::ICMP_SGE, B,
1079 ConstantInt::get(A->getType(), 0), Info))
1080 return false;
1081 Changed = replaceSubOverflowUses(II, A, B, ToRemove);
1082 }
1083 return Changed;
1084}
1085
1088 bool Changed = false;
1089 DT.updateDFSNumbers();
1090
1091 ConstraintInfo Info(F.getParent()->getDataLayout());
1092 State S(DT);
1093 std::unique_ptr<Module> ReproducerModule(
1094 DumpReproducers ? new Module(F.getName(), F.getContext()) : nullptr);
1095
1096 // First, collect conditions implied by branches and blocks with their
1097 // Dominator DFS in and out numbers.
1098 for (BasicBlock &BB : F) {
1099 if (!DT.getNode(&BB))
1100 continue;
1101 S.addInfoFor(BB);
1102 }
1103
1104 // Next, sort worklist by dominance, so that dominating conditions to check
1105 // and facts come before conditions and facts dominated by them. If a
1106 // condition to check and a fact have the same numbers, conditional facts come
1107 // first. Assume facts and checks are ordered according to their relative
1108 // order in the containing basic block. Also make sure conditions with
1109 // constant operands come before conditions without constant operands. This
1110 // increases the effectiveness of the current signed <-> unsigned fact
1111 // transfer logic.
1112 stable_sort(S.WorkList, [](const FactOrCheck &A, const FactOrCheck &B) {
1113 auto HasNoConstOp = [](const FactOrCheck &B) {
1114 return !isa<ConstantInt>(B.Inst->getOperand(0)) &&
1115 !isa<ConstantInt>(B.Inst->getOperand(1));
1116 };
1117 // If both entries have the same In numbers, conditional facts come first.
1118 // Otherwise use the relative order in the basic block.
1119 if (A.NumIn == B.NumIn) {
1120 if (A.isConditionFact() && B.isConditionFact()) {
1121 bool NoConstOpA = HasNoConstOp(A);
1122 bool NoConstOpB = HasNoConstOp(B);
1123 return NoConstOpA < NoConstOpB;
1124 }
1125 if (A.isConditionFact())
1126 return true;
1127 if (B.isConditionFact())
1128 return false;
1129 return A.Inst->comesBefore(B.Inst);
1130 }
1131 return A.NumIn < B.NumIn;
1132 });
1133
1135
1136 // Finally, process ordered worklist and eliminate implied conditions.
1137 SmallVector<StackEntry, 16> DFSInStack;
1138 SmallVector<ReproducerEntry> ReproducerCondStack;
1139 for (FactOrCheck &CB : S.WorkList) {
1140 // First, pop entries from the stack that are out-of-scope for CB. Remove
1141 // the corresponding entry from the constraint system.
1142 while (!DFSInStack.empty()) {
1143 auto &E = DFSInStack.back();
1144 LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut
1145 << "\n");
1146 LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n");
1147 assert(E.NumIn <= CB.NumIn);
1148 if (CB.NumOut <= E.NumOut)
1149 break;
1150 LLVM_DEBUG({
1151 dbgs() << "Removing ";
1152 dumpConstraint(Info.getCS(E.IsSigned).getLastConstraint(),
1153 Info.getValue2Index(E.IsSigned));
1154 dbgs() << "\n";
1155 });
1156
1157 Info.popLastConstraint(E.IsSigned);
1158 // Remove variables in the system that went out of scope.
1159 auto &Mapping = Info.getValue2Index(E.IsSigned);
1160 for (Value *V : E.ValuesToRelease)
1161 Mapping.erase(V);
1162 Info.popLastNVariables(E.IsSigned, E.ValuesToRelease.size());
1163 DFSInStack.pop_back();
1164 if (ReproducerModule)
1165 ReproducerCondStack.pop_back();
1166 }
1167
1168 LLVM_DEBUG({
1169 dbgs() << "Processing ";
1170 if (CB.IsCheck)
1171 dbgs() << "condition to simplify: " << *CB.Inst;
1172 else
1173 dbgs() << "fact to add to the system: " << *CB.Inst;
1174 dbgs() << "\n";
1175 });
1176
1177 // For a block, check if any CmpInsts become known based on the current set
1178 // of constraints.
1179 if (CB.IsCheck) {
1180 if (auto *II = dyn_cast<WithOverflowInst>(CB.Inst)) {
1181 Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove);
1182 } else if (auto *Cmp = dyn_cast<ICmpInst>(CB.Inst)) {
1183 Changed |= checkAndReplaceCondition(Cmp, Info, ReproducerModule.get(),
1184 ReproducerCondStack, S.DT);
1185 }
1186 continue;
1187 }
1188
1190 Value *A, *B;
1191 Value *Cmp = CB.Inst;
1192 match(Cmp, m_Intrinsic<Intrinsic::assume>(m_Value(Cmp)));
1193 if (match(Cmp, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
1194 if (Info.getCS(CmpInst::isSigned(Pred)).size() > MaxRows) {
1195 LLVM_DEBUG(
1196 dbgs()
1197 << "Skip adding constraint because system has too many rows.\n");
1198 continue;
1199 }
1200
1201 // Use the inverse predicate if required.
1202 if (CB.Not)
1203 Pred = CmpInst::getInversePredicate(Pred);
1204
1205 Info.addFact(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);
1206 if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size())
1207 ReproducerCondStack.emplace_back(cast<CmpInst>(Cmp), CB.Not);
1208
1209 Info.transferToOtherSystem(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);
1210 if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size()) {
1211 // Add dummy entries to ReproducerCondStack to keep it in sync with
1212 // DFSInStack.
1213 for (unsigned I = 0,
1214 E = (DFSInStack.size() - ReproducerCondStack.size());
1215 I < E; ++I) {
1216 ReproducerCondStack.emplace_back(nullptr, false);
1217 }
1218 }
1219 }
1220 }
1221
1222 if (ReproducerModule && !ReproducerModule->functions().empty()) {
1223 std::string S;
1224 raw_string_ostream StringS(S);
1225 ReproducerModule->print(StringS, nullptr);
1226 StringS.flush();
1227 OptimizationRemark Rem(DEBUG_TYPE, "Reproducer", &F);
1228 Rem << ore::NV("module") << S;
1229 ORE.emit(Rem);
1230 }
1231
1232#ifndef NDEBUG
1233 unsigned SignedEntries =
1234 count_if(DFSInStack, [](const StackEntry &E) { return E.IsSigned; });
1235 assert(Info.getCS(false).size() == DFSInStack.size() - SignedEntries &&
1236 "updates to CS and DFSInStack are out of sync");
1237 assert(Info.getCS(true).size() == SignedEntries &&
1238 "updates to CS and DFSInStack are out of sync");
1239#endif
1240
1241 for (Instruction *I : ToRemove)
1242 I->eraseFromParent();
1243 return Changed;
1244}
1245
1248 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1250 if (!eliminateConstraints(F, DT, ORE))
1251 return PreservedAnalyses::all();
1252
1256 return PA;
1257}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
ReachingDefAnalysis InstSet & ToRemove
assume Assume Builder
SmallVector< MachineOperand, 4 > Cond
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
static int64_t MaxConstraintValue
static bool checkAndReplaceCondition(CmpInst *Cmp, ConstraintInfo &Info, Module *ReproducerModule, ArrayRef< ReproducerEntry > ReproducerCondStack, DominatorTree &DT)
static int64_t MinSignedConstraintValue
static bool canUseSExt(ConstantInt *CI)
static int64_t multiplyWithOverflow(int64_t A, int64_t B)
static void dumpConstraint(ArrayRef< int64_t > C, const DenseMap< Value *, unsigned > &Value2Index)
static cl::opt< unsigned > MaxRows("constraint-elimination-max-rows", cl::init(500), cl::Hidden, cl::desc("Maximum number of rows to keep in constraint system"))
static int64_t addWithOverflow(int64_t A, int64_t B)
static cl::opt< bool > DumpReproducers("constraint-elimination-dump-reproducers", cl::init(false), cl::Hidden, cl::desc("Dump IR to reproduce successful transformations."))
static void generateReproducer(CmpInst *Cond, Module *M, ArrayRef< ReproducerEntry > Stack, ConstraintInfo &Info, DominatorTree &DT)
Helper function to generate a reproducer function for simplifying Cond.
static Decomposition decompose(Value *V, SmallVectorImpl< PreconditionTy > &Preconditions, bool IsSigned, const DataLayout &DL)
static bool eliminateConstraints(Function &F, DominatorTree &DT, OptimizationRemarkEmitter &ORE)
static bool replaceSubOverflowUses(IntrinsicInst *II, Value *A, Value *B, SmallVectorImpl< Instruction * > &ToRemove)
static bool tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)
#define DEBUG_TYPE
static Decomposition decomposeGEP(GEPOperator &GEP, SmallVectorImpl< PreconditionTy > &Preconditions, bool IsSigned, const DataLayout &DL)
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
Definition: DebugCounter.h:182
#define LLVM_DEBUG(X)
Definition: Debug.h:101
std::optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1260
This is the interface for a simple mod/ref and alias analysis over globals.
Hexagon Common GEP
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
if(VerifyEach)
static StringRef getName(Value *V)
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
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)
Definition: Statistic.h:167
Class for arbitrary precision integers.
Definition: APInt.h:75
bool sgt(const APInt &RHS) const
Signed greater than comparison.
Definition: APInt.h:1179
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:312
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1108
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1516
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:105
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1353
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:708
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1054
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:718
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:747
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:748
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:742
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:741
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:745
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:743
@ ICMP_EQ
equal
Definition: InstrTypes.h:739
@ ICMP_NE
not equal
Definition: InstrTypes.h:740
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:746
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:744
bool isSigned() const
Definition: InstrTypes.h:957
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:859
Predicate getUnsignedPredicate()
For example, SLT->ULT, SLE->ULE, SGT->UGT, SGE->UGE, ULT->Failed assert.
Definition: InstrTypes.h:988
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:832
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
bool isNegative() const
Definition: Constants.h:192
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:833
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.
Definition: Constants.cpp:888
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:840
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
Definition: Constants.h:151
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:136
This is an important base class in LLVM.
Definition: Constant.h:41
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
DenseMap< Value *, unsigned > & getValue2Index()
static SmallVector< int64_t, 8 > negate(SmallVector< int64_t, 8 > R)
bool addVariableRowFill(ArrayRef< int64_t > R)
void dump() const
Print the constraints in the system.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:72
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
bool erase(const KeyT &Val)
Definition: DenseMap.h:315
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
Definition: DenseMap.h:145
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
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:166
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
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:136
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2558
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:88
const BasicBlock * getParent() const
Definition: Instruction.h:90
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:82
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:355
void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs)
Drop all unknown metadata except for debug locations.
Definition: Metadata.cpp:1401
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:54
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
bool empty() const
Definition: MapVector.h:80
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
The optimization diagnostic interface.
Diagnostic information for applied optimization remarks.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1750
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
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:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
iterator find(const KeyT &Val)
Definition: ValueMap.h:155
iterator end()
Definition: ValueMap.h:135
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
iterator_range< user_iterator > users()
Definition: Value.h:421
const Value * stripPointerCastsSameRepresentation() const
Strip off pointer casts, all-zero GEPs and address space casts but ensures the representation of the ...
Definition: Value.cpp:693
bool use_empty() const
Definition: Value.h:344
self_iterator getIterator()
Definition: ilist_node.h:82
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:642
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:979
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:147
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWShl(const LHS &L, const RHS &R)
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWMul(const LHS &L, const RHS &R)
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWSub(const LHS &L, const RHS &R)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:537
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
DiagnosticInfoOptimizationBase::Argument NV
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void stable_sort(R &&Range)
Definition: STLExtras.h:2063
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 ...
Definition: MathExtras.h:676
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:1819
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.
Definition: STLExtras.h:1777
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:59
bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
Definition: Verifier.cpp:6465
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2129
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:748
constexpr unsigned MaxAnalysisRecursionDepth
Definition: ValueTracking.h:46
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1744
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if LHS and RHS have no common bits set.
void remapInstructionsInBlocks(ArrayRef< BasicBlock * > Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:184
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
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.
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...
Definition: STLExtras.h:2018
std::enable_if_t< std::is_signed< T >::value, T > MulOverflow(T X, T Y, T &Result)
Multiply two signed integers, computing the two's complement truncated result, returning true if an o...
Definition: MathExtras.h:728
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
#define N