ConstraintElimination.cpp

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

14#include "llvm/Transforms/Scalar/ConstraintElimination.h"

15#include "llvm/ADT/STLExtras.h"

16#include "llvm/ADT/ScopeExit.h"

17#include "llvm/ADT/SmallVector.h"

18#include "llvm/ADT/Statistic.h"

19#include "llvm/Analysis/ConstraintSystem.h"

20#include "llvm/Analysis/GlobalsModRef.h"

21#include "llvm/Analysis/LoopInfo.h"

22#include "llvm/Analysis/MemoryBuiltins.h"

23#include "llvm/Analysis/OptimizationRemarkEmitter.h"

24#include "llvm/Analysis/ScalarEvolution.h"

25#include "llvm/Analysis/ScalarEvolutionExpressions.h"

26#include "llvm/Analysis/TargetLibraryInfo.h"

27#include "llvm/Analysis/ValueTracking.h"

28#include "llvm/IR/DataLayout.h"

29#include "llvm/IR/DebugInfo.h"

30#include "llvm/IR/Dominators.h"

31#include "llvm/IR/Function.h"

32#include "llvm/IR/IRBuilder.h"

33#include "llvm/IR/InstrTypes.h"

34#include "llvm/IR/Instructions.h"

35#include "llvm/IR/Module.h"

36#include "llvm/IR/PatternMatch.h"

37#include "llvm/IR/Verifier.h"

38#include "llvm/Pass.h"

39#include "llvm/Support/CommandLine.h"

40#include "llvm/Support/Debug.h"

41#include "llvm/Support/DebugCounter.h"

42#include "llvm/Support/MathExtras.h"

43#include "llvm/Transforms/Utils/Cloning.h"

44#include "llvm/Transforms/Utils/ValueMapper.h"

45

46#include <optional>

47#include <string>

48

49using namespace llvm;

50using namespace PatternMatch;

51

52 #define DEBUG_TYPE "constraint-elimination"

53

54 STATISTIC(NumCondsRemoved, "Number of instructions removed");

55 DEBUG_COUNTER(EliminatedCounter, "conds-eliminated",

56 "Controls which conditions are eliminated");

57

58static cl::opt<unsigned>

59 MaxRows("constraint-elimination-max-rows", cl::init(500), cl::Hidden,

60 cl::desc("Maximum number of rows to keep in constraint system"));

61

62 static cl::opt<bool> DumpReproducers(

63 "constraint-elimination-dump-reproducers", cl::init(false), cl::Hidden,

64 cl::desc("Dump IR to reproduce successful transformations."));

65

66 static int64_t MaxConstraintValue = std::numeric_limits<int64_t>::max();

67 static int64_t MinSignedConstraintValue = std::numeric_limits<int64_t>::min();

68

69 static Instruction *getContextInstForUse(Use &U) {

70 Instruction *UserI = cast<Instruction>(U.getUser());

71 if (auto *Phi = dyn_cast<PHINode>(UserI))

72 UserI = Phi->getIncomingBlock(U)->getTerminator();

73 return UserI;

74}

75

76namespace {

77/// Struct to express a condition of the form %Op0 Pred %Op1.

78struct ConditionTy {

79 CmpPredicate Pred;

80 Value *Op0 = nullptr;

81 Value *Op1 = nullptr;

82

83 ConditionTy() = default;

84 ConditionTy(CmpPredicate Pred, Value *Op0, Value *Op1)

85 : Pred(Pred), Op0(Op0), Op1(Op1) {}

86};

87

88/// Represents either

89/// * a condition that holds on entry to a block (=condition fact)

90/// * an assume (=assume fact)

91/// * a use of a compare instruction to simplify.

92/// It also tracks the Dominator DFS in and out numbers for each entry.

93struct FactOrCheck {

94 enum class EntryTy {

95 ConditionFact, /// A condition that holds on entry to a block.

96 InstFact, /// A fact that holds after Inst executed (e.g. an assume or

97 /// min/mix intrinsic.

98 InstCheck, /// An instruction to simplify (e.g. an overflow math

99 /// intrinsics).

100 UseCheck /// An use of a compare instruction to simplify.

101 };

102

103 union {

104 Instruction *Inst;

105 Use *U;

106 ConditionTy Cond;

107 };

108

109 /// A pre-condition that must hold for the current fact to be added to the

110 /// system.

111 ConditionTy DoesHold;

112

113 unsigned NumIn;

114 unsigned NumOut;

115 EntryTy Ty;

116

117 FactOrCheck(EntryTy Ty, DomTreeNode *DTN, Instruction *Inst)

118 : Inst(Inst), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),

119 Ty(Ty) {}

120

121 FactOrCheck(DomTreeNode *DTN, Use *U)

122 : U(U), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),

123 Ty(EntryTy::UseCheck) {}

124

125 FactOrCheck(DomTreeNode *DTN, CmpPredicate Pred, Value *Op0, Value *Op1,

126 ConditionTy Precond = {})

127 : Cond(Pred, Op0, Op1), DoesHold(Precond), NumIn(DTN->getDFSNumIn()),

128 NumOut(DTN->getDFSNumOut()), Ty(EntryTy::ConditionFact) {}

129

130 static FactOrCheck getConditionFact(DomTreeNode *DTN, CmpPredicate Pred,

131 Value *Op0, Value *Op1,

132 ConditionTy Precond = {}) {

133 return FactOrCheck(DTN, Pred, Op0, Op1, Precond);

134 }

135

136 static FactOrCheck getInstFact(DomTreeNode *DTN, Instruction *Inst) {

137 return FactOrCheck(EntryTy::InstFact, DTN, Inst);

138 }

139

140 static FactOrCheck getCheck(DomTreeNode *DTN, Use *U) {

141 return FactOrCheck(DTN, U);

142 }

143

144 static FactOrCheck getCheck(DomTreeNode *DTN, CallInst *CI) {

145 return FactOrCheck(EntryTy::InstCheck, DTN, CI);

146 }

147

148 bool isCheck() const {

149 return Ty == EntryTy::InstCheck || Ty == EntryTy::UseCheck;

150 }

151

152 Instruction *getContextInst() const {

153 assert(!isConditionFact());

154 if (Ty == EntryTy::UseCheck)

155 return getContextInstForUse(*U);

156 return Inst;

157 }

158

159 Instruction *getInstructionToSimplify() const {

160 assert(isCheck());

161 if (Ty == EntryTy::InstCheck)

162 return Inst;

163 // The use may have been simplified to a constant already.

164 return dyn_cast<Instruction>(*U);

165 }

166

167 bool isConditionFact() const { return Ty == EntryTy::ConditionFact; }

168};

169

170/// Keep state required to build worklist.

171struct State {

172 DominatorTree &DT;

173 LoopInfo &LI;

174 ScalarEvolution &SE;

175 TargetLibraryInfo &TLI;

176 SmallVector<FactOrCheck, 64> WorkList;

177

178 State(DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE,

179 TargetLibraryInfo &TLI)

180 : DT(DT), LI(LI), SE(SE), TLI(TLI) {}

181

182 /// Process block \p BB and add known facts to work-list.

183 void addInfoFor(BasicBlock &BB);

184

185 /// Try to add facts for loop inductions (AddRecs) in EQ/NE compares

186 /// controlling the loop header.

187 void addInfoForInductions(BasicBlock &BB);

188

189 /// Returns true if we can add a known condition from BB to its successor

190 /// block Succ.

191 bool canAddSuccessor(BasicBlock &BB, BasicBlock *Succ) const {

192 return DT.dominates(BasicBlockEdge(&BB, Succ), Succ);

193 }

194};

195

196class ConstraintInfo;

197

198struct StackEntry {

199 unsigned NumIn;

200 unsigned NumOut;

201 bool IsSigned = false;

202 /// Variables that can be removed from the system once the stack entry gets

203 /// removed.

204 SmallVector<Value *, 2> ValuesToRelease;

205

206 StackEntry(unsigned NumIn, unsigned NumOut, bool IsSigned,

207 SmallVector<Value *, 2> ValuesToRelease)

208 : NumIn(NumIn), NumOut(NumOut), IsSigned(IsSigned),

209 ValuesToRelease(std::move(ValuesToRelease)) {}

210};

211

212struct ConstraintTy {

213 SmallVector<int64_t, 8> Coefficients;

214 SmallVector<ConditionTy, 2> Preconditions;

215

216 SmallVector<SmallVector<int64_t, 8>> ExtraInfo;

217

218 bool IsSigned = false;

219

220 ConstraintTy() = default;

221

222 ConstraintTy(SmallVector<int64_t, 8> Coefficients, bool IsSigned, bool IsEq,

223 bool IsNe)

224 : Coefficients(std::move(Coefficients)), IsSigned(IsSigned), IsEq(IsEq),

225 IsNe(IsNe) {}

226

227 unsigned size() const { return Coefficients.size(); }

228

229 unsigned empty() const { return Coefficients.empty(); }

230

231 /// Returns true if all preconditions for this list of constraints are

232 /// satisfied given \p Info.

233 bool isValid(const ConstraintInfo &Info) const;

234

235 bool isEq() const { return IsEq; }

236

237 bool isNe() const { return IsNe; }

238

239 /// Check if the current constraint is implied by the given ConstraintSystem.

240 ///

241 /// \return true or false if the constraint is proven to be respectively true,

242 /// or false. When the constraint cannot be proven to be either true or false,

243 /// std::nullopt is returned.

244 std::optional<bool> isImpliedBy(const ConstraintSystem &CS) const;

245

246private:

247 bool IsEq = false;

248 bool IsNe = false;

249};

250

251/// Wrapper encapsulating separate constraint systems and corresponding value

252/// mappings for both unsigned and signed information. Facts are added to and

253/// conditions are checked against the corresponding system depending on the

254/// signed-ness of their predicates. While the information is kept separate

255/// based on signed-ness, certain conditions can be transferred between the two

256/// systems.

257class ConstraintInfo {

258

259 ConstraintSystem UnsignedCS;

260 ConstraintSystem SignedCS;

261

262 const DataLayout &DL;

263

264public:

265 ConstraintInfo(const DataLayout &DL, ArrayRef<Value *> FunctionArgs)

266 : UnsignedCS(FunctionArgs), SignedCS(FunctionArgs), DL(DL) {

267 auto &Value2Index = getValue2Index(false);

268 // Add Arg > -1 constraints to unsigned system for all function arguments.

269 for (Value *Arg : FunctionArgs) {

270 ConstraintTy VarPos(SmallVector<int64_t, 8>(Value2Index.size() + 1, 0),

271 false, false, false);

272 VarPos.Coefficients[Value2Index[Arg]] = -1;

273 UnsignedCS.addVariableRow(VarPos.Coefficients);

274 }

275 }

276

277 DenseMap<Value *, unsigned> &getValue2Index(bool Signed) {

278 return Signed ? SignedCS.getValue2Index() : UnsignedCS.getValue2Index();

279 }

280 const DenseMap<Value *, unsigned> &getValue2Index(bool Signed) const {

281 return Signed ? SignedCS.getValue2Index() : UnsignedCS.getValue2Index();

282 }

283

284 ConstraintSystem &getCS(bool Signed) {

285 return Signed ? SignedCS : UnsignedCS;

286 }

287 const ConstraintSystem &getCS(bool Signed) const {

288 return Signed ? SignedCS : UnsignedCS;

289 }

290

291 void popLastConstraint(bool Signed) { getCS(Signed).popLastConstraint(); }

292 void popLastNVariables(bool Signed, unsigned N) {

293 getCS(Signed).popLastNVariables(N);

294 }

295

296 bool doesHold(CmpInst::Predicate Pred, Value *A, Value *B) const;

297

298 void addFact(CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,

299 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack);

300

301 /// Turn a comparison of the form \p Op0 \p Pred \p Op1 into a vector of

302 /// constraints, using indices from the corresponding constraint system.

303 /// New variables that need to be added to the system are collected in

304 /// \p NewVariables.

305 ConstraintTy getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,

306 SmallVectorImpl<Value *> &NewVariables,

307 bool ForceSignedSystem = false) const;

308

309 /// Turns a comparison of the form \p Op0 \p Pred \p Op1 into a vector of

310 /// constraints using getConstraint. Returns an empty constraint if the result

311 /// cannot be used to query the existing constraint system, e.g. because it

312 /// would require adding new variables. Also tries to convert signed

313 /// predicates to unsigned ones if possible to allow using the unsigned system

314 /// which increases the effectiveness of the signed <-> unsigned transfer

315 /// logic.

316 ConstraintTy getConstraintForSolving(CmpInst::Predicate Pred, Value *Op0,

317 Value *Op1) const;

318

319 /// Try to add information from \p A \p Pred \p B to the unsigned/signed

320 /// system if \p Pred is signed/unsigned.

321 void transferToOtherSystem(CmpInst::Predicate Pred, Value *A, Value *B,

322 unsigned NumIn, unsigned NumOut,

323 SmallVectorImpl<StackEntry> &DFSInStack);

324

325private:

326 /// Adds facts into constraint system. \p ForceSignedSystem can be set when

327 /// the \p Pred is eq/ne, and signed constraint system is used when it's

328 /// specified.

329 void addFactImpl(CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,

330 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack,

331 bool ForceSignedSystem);

332};

333

334/// Represents a (Coefficient * Variable) entry after IR decomposition.

335struct DecompEntry {

336 int64_t Coefficient;

337 Value *Variable;

338 /// True if the variable is known positive in the current constraint.

339 bool IsKnownNonNegative;

340

341 DecompEntry(int64_t Coefficient, Value *Variable,

342 bool IsKnownNonNegative = false)

343 : Coefficient(Coefficient), Variable(Variable),

344 IsKnownNonNegative(IsKnownNonNegative) {}

345};

346

347/// Represents an Offset + Coefficient1 * Variable1 + ... decomposition.

348struct Decomposition {

349 int64_t Offset = 0;

350 SmallVector<DecompEntry, 3> Vars;

351

352 Decomposition(int64_t Offset) : Offset(Offset) {}

353 Decomposition(Value *V, bool IsKnownNonNegative = false) {

354 Vars.emplace_back(1, V, IsKnownNonNegative);

355 }

356 Decomposition(int64_t Offset, ArrayRef<DecompEntry> Vars)

357 : Offset(Offset), Vars(Vars) {}

358

359 /// Add \p OtherOffset and return true if the operation overflows, i.e. the

360 /// new decomposition is invalid.

361 [[nodiscard]] bool add(int64_t OtherOffset) {

362 return AddOverflow(Offset, OtherOffset, Offset);

363 }

364

365 /// Add \p Other and return true if the operation overflows, i.e. the new

366 /// decomposition is invalid.

367 [[nodiscard]] bool add(const Decomposition &Other) {

368 if (add(Other.Offset))

369 return true;

370 append_range(Vars, Other.Vars);

371 return false;

372 }

373

374 /// Subtract \p Other and return true if the operation overflows, i.e. the new

375 /// decomposition is invalid.

376 [[nodiscard]] bool sub(const Decomposition &Other) {

377 Decomposition Tmp = Other;

378 if (Tmp.mul(-1))

379 return true;

380 if (add(Tmp.Offset))

381 return true;

382 append_range(Vars, Tmp.Vars);

383 return false;

384 }

385

386 /// Multiply all coefficients by \p Factor and return true if the operation

387 /// overflows, i.e. the new decomposition is invalid.

388 [[nodiscard]] bool mul(int64_t Factor) {

389 if (MulOverflow(Offset, Factor, Offset))

390 return true;

391 for (auto &Var : Vars)

392 if (MulOverflow(Var.Coefficient, Factor, Var.Coefficient))

393 return true;

394 return false;

395 }

396};

397

398// Variable and constant offsets for a chain of GEPs, with base pointer BasePtr.

399struct OffsetResult {

400 Value *BasePtr;

401 APInt ConstantOffset;

402 SmallMapVector<Value *, APInt, 4> VariableOffsets;

403 GEPNoWrapFlags NW;

404

405 OffsetResult() : BasePtr(nullptr), ConstantOffset(0, uint64_t(0)) {}

406

407 OffsetResult(GEPOperator &GEP, const DataLayout &DL)

408 : BasePtr(GEP.getPointerOperand()), NW(GEP.getNoWrapFlags()) {

409 ConstantOffset = APInt(DL.getIndexTypeSizeInBits(BasePtr->getType()), 0);

410 }

411};

412} // namespace

413

414// Try to collect variable and constant offsets for \p GEP, partly traversing

415// nested GEPs. Returns an OffsetResult with nullptr as BasePtr of collecting

416// the offset fails.

417 static OffsetResult collectOffsets(GEPOperator &GEP, const DataLayout &DL) {

418 OffsetResult Result(GEP, DL);

419 unsigned BitWidth = Result.ConstantOffset.getBitWidth();

420 if (!GEP.collectOffset(DL, BitWidth, Result.VariableOffsets,

421 Result.ConstantOffset))

422 return {};

423

424 // If we have a nested GEP, check if we can combine the constant offset of the

425 // inner GEP with the outer GEP.

426 if (auto *InnerGEP = dyn_cast<GetElementPtrInst>(Result.BasePtr)) {

427 SmallMapVector<Value *, APInt, 4> VariableOffsets2;

428 APInt ConstantOffset2(BitWidth, 0);

429 bool CanCollectInner = InnerGEP->collectOffset(

430 DL, BitWidth, VariableOffsets2, ConstantOffset2);

431 // TODO: Support cases with more than 1 variable offset.

432 if (!CanCollectInner || Result.VariableOffsets.size() > 1 ||

433 VariableOffsets2.size() > 1 ||

434 (Result.VariableOffsets.size() >= 1 && VariableOffsets2.size() >= 1)) {

435 // More than 1 variable index, use outer result.

436 return Result;

437 }

438 Result.BasePtr = InnerGEP->getPointerOperand();

439 Result.ConstantOffset += ConstantOffset2;

440 if (Result.VariableOffsets.size() == 0 && VariableOffsets2.size() == 1)

441 Result.VariableOffsets = VariableOffsets2;

442 Result.NW &= InnerGEP->getNoWrapFlags();

443 }

444 return Result;

445}

446

447static Decomposition decompose(Value *V,

448 SmallVectorImpl<ConditionTy> &Preconditions,

449 bool IsSigned, const DataLayout &DL);

450

451 static bool canUseSExt(ConstantInt *CI) {

452 const APInt &Val = CI->getValue();

453 return Val.sgt(MinSignedConstraintValue) && Val.slt(MaxConstraintValue);

454}

455

456 static Decomposition decomposeGEP(GEPOperator &GEP,

457 SmallVectorImpl<ConditionTy> &Preconditions,

458 bool IsSigned, const DataLayout &DL) {

459 // Do not reason about pointers where the index size is larger than 64 bits,

460 // as the coefficients used to encode constraints are 64 bit integers.

461 if (DL.getIndexTypeSizeInBits(GEP.getPointerOperand()->getType()) > 64)

462 return &GEP;

463

464 assert(!IsSigned && "The logic below only supports decomposition for "

465 "unsigned predicates at the moment.");

466 const auto &[BasePtr, ConstantOffset, VariableOffsets, NW] =

467 collectOffsets(GEP, DL);

468 // We support either plain gep nuw, or gep nusw with non-negative offset,

469 // which implies gep nuw.

470 if (!BasePtr || NW == GEPNoWrapFlags::none())

471 return &GEP;

472

473 Decomposition Result(ConstantOffset.getSExtValue(), DecompEntry(1, BasePtr));

474 for (auto [Index, Scale] : VariableOffsets) {

475 auto IdxResult = decompose(Index, Preconditions, IsSigned, DL);

476 if (IdxResult.mul(Scale.getSExtValue()))

477 return &GEP;

478 if (Result.add(IdxResult))

479 return &GEP;

480

481 if (!NW.hasNoUnsignedWrap()) {

482 // Try to prove nuw from nusw and nneg.

483 assert(NW.hasNoUnsignedSignedWrap() && "Must have nusw flag");

484 if (!isKnownNonNegative(Index, DL))

485 Preconditions.emplace_back(CmpInst::ICMP_SGE, Index,

486 ConstantInt::get(Index->getType(), 0));

487 }

488 }

489 return Result;

490}

491

492// Decomposes \p V into a constant offset + list of pairs { Coefficient,

493// Variable } where Coefficient * Variable. The sum of the constant offset and

494// pairs equals \p V.

495 static Decomposition decompose(Value *V,

496 SmallVectorImpl<ConditionTy> &Preconditions,

497 bool IsSigned, const DataLayout &DL) {

498

499 auto MergeResults = [&Preconditions, IsSigned,

500 &DL](Value *A, Value *B,

501 bool IsSignedB) -> std::optional<Decomposition> {

502 auto ResA = decompose(A, Preconditions, IsSigned, DL);

503 auto ResB = decompose(B, Preconditions, IsSignedB, DL);

504 if (ResA.add(ResB))

505 return std::nullopt;

506 return ResA;

507 };

508

509 Type *Ty = V->getType()->getScalarType();

510 if (Ty->isPointerTy() && !IsSigned) {

511 if (auto *GEP = dyn_cast<GEPOperator>(V))

512 return decomposeGEP(*GEP, Preconditions, IsSigned, DL);

513 if (isa<ConstantPointerNull>(V))

514 return int64_t(0);

515

516 return V;

517 }

518

519 // Don't handle integers > 64 bit. Our coefficients are 64-bit large, so

520 // coefficient add/mul may wrap, while the operation in the full bit width

521 // would not.

522 if (!Ty->isIntegerTy() || Ty->getIntegerBitWidth() > 64)

523 return V;

524

525 bool IsKnownNonNegative = false;

526

527 // Decompose \p V used with a signed predicate.

528 if (IsSigned) {

529 if (auto *CI = dyn_cast<ConstantInt>(V)) {

530 if (canUseSExt(CI))

531 return CI->getSExtValue();

532 }

533 Value *Op0;

534 Value *Op1;

535

536 if (match(V, m_SExt(m_Value(Op0))))

537 V = Op0;

538 else if (match(V, m_NNegZExt(m_Value(Op0)))) {

539 V = Op0;

540 IsKnownNonNegative = true;

541 } else if (match(V, m_NSWTrunc(m_Value(Op0)))) {

542 if (Op0->getType()->getScalarSizeInBits() <= 64)

543 V = Op0;

544 }

545

546 if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1)))) {

547 if (auto Decomp = MergeResults(Op0, Op1, IsSigned))

548 return *Decomp;

549 return {V, IsKnownNonNegative};

550 }

551

552 if (match(V, m_NSWSub(m_Value(Op0), m_Value(Op1)))) {

553 auto ResA = decompose(Op0, Preconditions, IsSigned, DL);

554 auto ResB = decompose(Op1, Preconditions, IsSigned, DL);

555 if (!ResA.sub(ResB))

556 return ResA;

557 return {V, IsKnownNonNegative};

558 }

559

560 ConstantInt *CI;

561 if (match(V, m_NSWMul(m_Value(Op0), m_ConstantInt(CI))) && canUseSExt(CI)) {

562 auto Result = decompose(Op0, Preconditions, IsSigned, DL);

563 if (!Result.mul(CI->getSExtValue()))

564 return Result;

565 return {V, IsKnownNonNegative};

566 }

567

568 // (shl nsw x, shift) is (mul nsw x, (1<<shift)), with the exception of

569 // shift == bw-1.

570 if (match(V, m_NSWShl(m_Value(Op0), m_ConstantInt(CI)))) {

571 uint64_t Shift = CI->getValue().getLimitedValue();

572 if (Shift < Ty->getIntegerBitWidth() - 1) {

573 assert(Shift < 64 && "Would overflow");

574 auto Result = decompose(Op0, Preconditions, IsSigned, DL);

575 if (!Result.mul(int64_t(1) << Shift))

576 return Result;

577 return {V, IsKnownNonNegative};

578 }

579 }

580

581 return {V, IsKnownNonNegative};

582 }

583

584 if (auto *CI = dyn_cast<ConstantInt>(V)) {

585 if (CI->uge(MaxConstraintValue))

586 return V;

587 return int64_t(CI->getZExtValue());

588 }

589

590 Value *Op0;

591 if (match(V, m_ZExt(m_Value(Op0)))) {

592 IsKnownNonNegative = true;

593 V = Op0;

594 } else if (match(V, m_SExt(m_Value(Op0)))) {

595 V = Op0;

596 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0,

597 ConstantInt::get(Op0->getType(), 0));

598 } else if (auto *Trunc = dyn_cast<TruncInst>(V)) {

599 if (Trunc->getSrcTy()->getScalarSizeInBits() <= 64) {

600 if (Trunc->hasNoUnsignedWrap() || Trunc->hasNoSignedWrap()) {

601 V = Trunc->getOperand(0);

602 if (!Trunc->hasNoUnsignedWrap())

603 Preconditions.emplace_back(CmpInst::ICMP_SGE, V,

604 ConstantInt::get(V->getType(), 0));

605 }

606 }

607 }

608

609 Value *Op1;

610 ConstantInt *CI;

611 if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1)))) {

612 if (auto Decomp = MergeResults(Op0, Op1, IsSigned))

613 return *Decomp;

614 return {V, IsKnownNonNegative};

615 }

616

617 if (match(V, m_Add(m_Value(Op0), m_ConstantInt(CI))) && CI->isNegative() &&

618 canUseSExt(CI)) {

619 Preconditions.emplace_back(

620 CmpInst::ICMP_UGE, Op0,

621 ConstantInt::get(Op0->getType(), CI->getSExtValue() * -1));

622 if (auto Decomp = MergeResults(Op0, CI, true))

623 return *Decomp;

624 return {V, IsKnownNonNegative};

625 }

626

627 if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1)))) {

628 if (!isKnownNonNegative(Op0, DL))

629 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0,

630 ConstantInt::get(Op0->getType(), 0));

631 if (!isKnownNonNegative(Op1, DL))

632 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op1,

633 ConstantInt::get(Op1->getType(), 0));

634

635 if (auto Decomp = MergeResults(Op0, Op1, IsSigned))

636 return *Decomp;

637 return {V, IsKnownNonNegative};

638 }

639

640 // Decompose or as an add if there are no common bits between the operands.

641 if (match(V, m_DisjointOr(m_Value(Op0), m_ConstantInt(CI)))) {

642 if (auto Decomp = MergeResults(Op0, CI, IsSigned))

643 return *Decomp;

644 return {V, IsKnownNonNegative};

645 }

646

647 if (match(V, m_NUWShl(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI)) {

648 if (CI->getSExtValue() < 0 || CI->getSExtValue() >= 64)

649 return {V, IsKnownNonNegative};

650 auto Result = decompose(Op1, Preconditions, IsSigned, DL);

651 if (!Result.mul(int64_t{1} << CI->getSExtValue()))

652 return Result;

653 return {V, IsKnownNonNegative};

654 }

655

656 if (match(V, m_NUWMul(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI) &&

657 (!CI->isNegative())) {

658 auto Result = decompose(Op1, Preconditions, IsSigned, DL);

659 if (!Result.mul(CI->getSExtValue()))

660 return Result;

661 return {V, IsKnownNonNegative};

662 }

663

664 if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1)))) {

665 auto ResA = decompose(Op0, Preconditions, IsSigned, DL);

666 auto ResB = decompose(Op1, Preconditions, IsSigned, DL);

667 if (!ResA.sub(ResB))

668 return ResA;

669 return {V, IsKnownNonNegative};

670 }

671

672 return {V, IsKnownNonNegative};

673}

674

675ConstraintTy

676ConstraintInfo::getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,

677 SmallVectorImpl<Value *> &NewVariables,

678 bool ForceSignedSystem) const {

679 assert(NewVariables.empty() && "NewVariables must be empty when passed in");

680 assert((!ForceSignedSystem || CmpInst::isEquality(Pred)) &&

681 "signed system can only be forced on eq/ne");

682

683 bool IsEq = false;

684 bool IsNe = false;

685

686 // Try to convert Pred to one of ULE/ULT/SLE/SLT.

687 switch (Pred) {

688 case CmpInst::ICMP_UGT:

689 case CmpInst::ICMP_UGE:

690 case CmpInst::ICMP_SGT:

691 case CmpInst::ICMP_SGE: {

692 Pred = CmpInst::getSwappedPredicate(Pred);

693 std::swap(Op0, Op1);

694 break;

695 }

696 case CmpInst::ICMP_EQ:

697 if (!ForceSignedSystem && match(Op1, m_Zero())) {

698 Pred = CmpInst::ICMP_ULE;

699 } else {

700 IsEq = true;

701 Pred = CmpInst::ICMP_ULE;

702 }

703 break;

704 case CmpInst::ICMP_NE:

705 if (!ForceSignedSystem && match(Op1, m_Zero())) {

706 Pred = CmpInst::getSwappedPredicate(CmpInst::ICMP_UGT);

707 std::swap(Op0, Op1);

708 } else {

709 IsNe = true;

710 Pred = CmpInst::ICMP_ULE;

711 }

712 break;

713 default:

714 break;

715 }

716

717 if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT &&

718 Pred != CmpInst::ICMP_SLE && Pred != CmpInst::ICMP_SLT)

719 return {};

720

721 SmallVector<ConditionTy, 4> Preconditions;

722 bool IsSigned = ForceSignedSystem || CmpInst::isSigned(Pred);

723 auto &Value2Index = getValue2Index(IsSigned);

724 auto ADec = decompose(Op0->stripPointerCastsSameRepresentation(),

725 Preconditions, IsSigned, DL);

726 auto BDec = decompose(Op1->stripPointerCastsSameRepresentation(),

727 Preconditions, IsSigned, DL);

728 int64_t Offset1 = ADec.Offset;

729 int64_t Offset2 = BDec.Offset;

730 Offset1 *= -1;

731

732 auto &VariablesA = ADec.Vars;

733 auto &VariablesB = BDec.Vars;

734

735 // First try to look up \p V in Value2Index and NewVariables. Otherwise add a

736 // new entry to NewVariables.

737 SmallDenseMap<Value *, unsigned> NewIndexMap;

738 auto GetOrAddIndex = [&Value2Index, &NewVariables,

739 &NewIndexMap](Value *V) -> unsigned {

740 auto V2I = Value2Index.find(V);

741 if (V2I != Value2Index.end())

742 return V2I->second;

743 auto Insert =

744 NewIndexMap.insert({V, Value2Index.size() + NewVariables.size() + 1});

745 if (Insert.second)

746 NewVariables.push_back(V);

747 return Insert.first->second;

748 };

749

750 // Make sure all variables have entries in Value2Index or NewVariables.

751 for (const auto &KV : concat<DecompEntry>(VariablesA, VariablesB))

752 GetOrAddIndex(KV.Variable);

753

754 // Build result constraint, by first adding all coefficients from A and then

755 // subtracting all coefficients from B.

756 ConstraintTy Res(

757 SmallVector<int64_t, 8>(Value2Index.size() + NewVariables.size() + 1, 0),

758 IsSigned, IsEq, IsNe);

759 // Collect variables that are known to be positive in all uses in the

760 // constraint.

761 SmallDenseMap<Value *, bool> KnownNonNegativeVariables;

762 auto &R = Res.Coefficients;

763 for (const auto &KV : VariablesA) {

764 R[GetOrAddIndex(KV.Variable)] += KV.Coefficient;

765 auto I =

766 KnownNonNegativeVariables.insert({KV.Variable, KV.IsKnownNonNegative});

767 I.first->second &= KV.IsKnownNonNegative;

768 }

769

770 for (const auto &KV : VariablesB) {

771 auto &Coeff = R[GetOrAddIndex(KV.Variable)];

772 if (SubOverflow(Coeff, KV.Coefficient, Coeff))

773 return {};

774 auto I =

775 KnownNonNegativeVariables.insert({KV.Variable, KV.IsKnownNonNegative});

776 I.first->second &= KV.IsKnownNonNegative;

777 }

778

779 int64_t OffsetSum;

780 if (AddOverflow(Offset1, Offset2, OffsetSum))

781 return {};

782 if (Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_ULT)

783 if (AddOverflow(OffsetSum, int64_t(-1), OffsetSum))

784 return {};

785 R[0] = OffsetSum;

786 Res.Preconditions = std::move(Preconditions);

787

788 // Remove any (Coefficient, Variable) entry where the Coefficient is 0 for new

789 // variables.

790 while (!NewVariables.empty()) {

791 int64_t Last = R.back();

792 if (Last != 0)

793 break;

794 R.pop_back();

795 Value *RemovedV = NewVariables.pop_back_val();

796 NewIndexMap.erase(RemovedV);

797 }

798

799 // Add extra constraints for variables that are known positive.

800 for (auto &KV : KnownNonNegativeVariables) {

801 if (!KV.second ||

802 (!Value2Index.contains(KV.first) && !NewIndexMap.contains(KV.first)))

803 continue;

804 auto &C = Res.ExtraInfo.emplace_back(

805 Value2Index.size() + NewVariables.size() + 1, 0);

806 C[GetOrAddIndex(KV.first)] = -1;

807 }

808 return Res;

809}

810

811ConstraintTy ConstraintInfo::getConstraintForSolving(CmpInst::Predicate Pred,

812 Value *Op0,

813 Value *Op1) const {

814 Constant *NullC = Constant::getNullValue(Op0->getType());

815 // Handle trivially true compares directly to avoid adding V UGE 0 constraints

816 // for all variables in the unsigned system.

817 if ((Pred == CmpInst::ICMP_ULE && Op0 == NullC) ||

818 (Pred == CmpInst::ICMP_UGE && Op1 == NullC)) {

819 auto &Value2Index = getValue2Index(false);

820 // Return constraint that's trivially true.

821 return ConstraintTy(SmallVector<int64_t, 8>(Value2Index.size(), 0), false,

822 false, false);

823 }

824

825 // If both operands are known to be non-negative, change signed predicates to

826 // unsigned ones. This increases the reasoning effectiveness in combination

827 // with the signed <-> unsigned transfer logic.

828 if (CmpInst::isSigned(Pred) &&

829 isKnownNonNegative(Op0, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1) &&

830 isKnownNonNegative(Op1, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1))

831 Pred = ICmpInst::getUnsignedPredicate(Pred);

832

833 SmallVector<Value *> NewVariables;

834 ConstraintTy R = getConstraint(Pred, Op0, Op1, NewVariables);

835 if (!NewVariables.empty())

836 return {};

837 return R;

838}

839

840bool ConstraintTy::isValid(const ConstraintInfo &Info) const {

841 return Coefficients.size() > 0 &&

842 all_of(Preconditions, [&Info](const ConditionTy &C) {

843 return Info.doesHold(C.Pred, C.Op0, C.Op1);

844 });

845}

846

847std::optional<bool>

848ConstraintTy::isImpliedBy(const ConstraintSystem &CS) const {

849 bool IsConditionImplied = CS.isConditionImplied(Coefficients);

850

851 if (IsEq || IsNe) {

852 auto NegatedOrEqual = ConstraintSystem::negateOrEqual(Coefficients);

853 bool IsNegatedOrEqualImplied =

854 !NegatedOrEqual.empty() && CS.isConditionImplied(NegatedOrEqual);

855

856 // In order to check that `%a == %b` is true (equality), both conditions `%a

857 // >= %b` and `%a <= %b` must hold true. When checking for equality (`IsEq`

858 // is true), we return true if they both hold, false in the other cases.

859 if (IsConditionImplied && IsNegatedOrEqualImplied)

860 return IsEq;

861

862 auto Negated = ConstraintSystem::negate(Coefficients);

863 bool IsNegatedImplied = !Negated.empty() && CS.isConditionImplied(Negated);

864

865 auto StrictLessThan = ConstraintSystem::toStrictLessThan(Coefficients);

866 bool IsStrictLessThanImplied =

867 !StrictLessThan.empty() && CS.isConditionImplied(StrictLessThan);

868

869 // In order to check that `%a != %b` is true (non-equality), either

870 // condition `%a > %b` or `%a < %b` must hold true. When checking for

871 // non-equality (`IsNe` is true), we return true if one of the two holds,

872 // false in the other cases.

873 if (IsNegatedImplied || IsStrictLessThanImplied)

874 return IsNe;

875

876 return std::nullopt;

877 }

878

879 if (IsConditionImplied)

880 return true;

881

882 auto Negated = ConstraintSystem::negate(Coefficients);

883 auto IsNegatedImplied = !Negated.empty() && CS.isConditionImplied(Negated);

884 if (IsNegatedImplied)

885 return false;

886

887 // Neither the condition nor its negated holds, did not prove anything.

888 return std::nullopt;

889}

890

891bool ConstraintInfo::doesHold(CmpInst::Predicate Pred, Value *A,

892 Value *B) const {

893 auto R = getConstraintForSolving(Pred, A, B);

894 return R.isValid(*this) &&

895 getCS(R.IsSigned).isConditionImplied(R.Coefficients);

896}

897

898void ConstraintInfo::transferToOtherSystem(

899 CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,

900 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack) {

901 auto IsKnownNonNegative = [this](Value *V) {

902 return doesHold(CmpInst::ICMP_SGE, V, ConstantInt::get(V->getType(), 0)) ||

903 isKnownNonNegative(V, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1);

904 };

905 // Check if we can combine facts from the signed and unsigned systems to

906 // derive additional facts.

907 if (!A->getType()->isIntegerTy())

908 return;

909 // FIXME: This currently depends on the order we add facts. Ideally we

910 // would first add all known facts and only then try to add additional

911 // facts.

912 switch (Pred) {

913 default:

914 break;

915 case CmpInst::ICMP_ULT:

916 case CmpInst::ICMP_ULE:

917 // If B is a signed positive constant, then A >=s 0 and A <s (or <=s) B.

918 if (IsKnownNonNegative(B)) {

919 addFact(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0), NumIn,

920 NumOut, DFSInStack);

921 addFact(ICmpInst::getSignedPredicate(Pred), A, B, NumIn, NumOut,

922 DFSInStack);

923 }

924 break;

925 case CmpInst::ICMP_UGE:

926 case CmpInst::ICMP_UGT:

927 // If A is a signed positive constant, then B >=s 0 and A >s (or >=s) B.

928 if (IsKnownNonNegative(A)) {

929 addFact(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0), NumIn,

930 NumOut, DFSInStack);

931 addFact(ICmpInst::getSignedPredicate(Pred), A, B, NumIn, NumOut,

932 DFSInStack);

933 }

934 break;

935 case CmpInst::ICMP_SLT:

936 if (IsKnownNonNegative(A))

937 addFact(CmpInst::ICMP_ULT, A, B, NumIn, NumOut, DFSInStack);

938 break;

939 case CmpInst::ICMP_SGT: {

940 if (doesHold(CmpInst::ICMP_SGE, B, Constant::getAllOnesValue(B->getType())))

941 addFact(CmpInst::ICMP_UGE, A, ConstantInt::get(B->getType(), 0), NumIn,

942 NumOut, DFSInStack);

943 if (IsKnownNonNegative(B))

944 addFact(CmpInst::ICMP_UGT, A, B, NumIn, NumOut, DFSInStack);

945

946 break;

947 }

948 case CmpInst::ICMP_SGE:

949 if (IsKnownNonNegative(B))

950 addFact(CmpInst::ICMP_UGE, A, B, NumIn, NumOut, DFSInStack);

951 break;

952 }

953}

954

955#ifndef NDEBUG

956

957 static void dumpConstraint(ArrayRef<int64_t> C,

958 const DenseMap<Value *, unsigned> &Value2Index) {

959 ConstraintSystem CS(Value2Index);

960 CS.addVariableRowFill(C);

961 CS.dump();

962}

963#endif

964

965void State::addInfoForInductions(BasicBlock &BB) {

966 auto *L = LI.getLoopFor(&BB);

967 if (!L || L->getHeader() != &BB)

968 return;

969

970 Value *A;

971 Value *B;

972 CmpPredicate Pred;

973

974 if (!match(BB.getTerminator(),

975 m_Br(m_ICmp(Pred, m_Value(A), m_Value(B)), m_Value(), m_Value())))

976 return;

977 PHINode *PN = dyn_cast<PHINode>(A);

978 if (!PN) {

979 Pred = CmpInst::getSwappedPredicate(Pred);

980 std::swap(A, B);

981 PN = dyn_cast<PHINode>(A);

982 }

983

984 if (!PN || PN->getParent() != &BB || PN->getNumIncomingValues() != 2 ||

985 !SE.isSCEVable(PN->getType()))

986 return;

987

988 BasicBlock *InLoopSucc = nullptr;

989 if (Pred == CmpInst::ICMP_NE)

990 InLoopSucc = cast<BranchInst>(BB.getTerminator())->getSuccessor(0);

991 else if (Pred == CmpInst::ICMP_EQ)

992 InLoopSucc = cast<BranchInst>(BB.getTerminator())->getSuccessor(1);

993 else

994 return;

995

996 if (!L->contains(InLoopSucc) || !L->isLoopExiting(&BB) || InLoopSucc == &BB)

997 return;

998

999 auto *AR = dyn_cast_or_null<SCEVAddRecExpr>(SE.getSCEV(PN));

1000 BasicBlock *LoopPred = L->getLoopPredecessor();

1001 if (!AR || AR->getLoop() != L || !LoopPred)

1002 return;

1003

1004 const SCEV *StartSCEV = AR->getStart();

1005 Value *StartValue = nullptr;

1006 if (auto *C = dyn_cast<SCEVConstant>(StartSCEV)) {

1007 StartValue = C->getValue();

1008 } else {

1009 StartValue = PN->getIncomingValueForBlock(LoopPred);

1010 assert(SE.getSCEV(StartValue) == StartSCEV && "inconsistent start value");

1011 }

1012

1013 DomTreeNode *DTN = DT.getNode(InLoopSucc);

1014 auto IncUnsigned = SE.getMonotonicPredicateType(AR, CmpInst::ICMP_UGT);

1015 auto IncSigned = SE.getMonotonicPredicateType(AR, CmpInst::ICMP_SGT);

1016 bool MonotonicallyIncreasingUnsigned =

1017 IncUnsigned == ScalarEvolution::MonotonicallyIncreasing;

1018 bool MonotonicallyIncreasingSigned =

1019 IncSigned == ScalarEvolution::MonotonicallyIncreasing;

1020 // If SCEV guarantees that AR does not wrap, PN >= StartValue can be added

1021 // unconditionally.

1022 if (MonotonicallyIncreasingUnsigned)

1023 WorkList.push_back(

1024 FactOrCheck::getConditionFact(DTN, CmpInst::ICMP_UGE, PN, StartValue));

1025 if (MonotonicallyIncreasingSigned)

1026 WorkList.push_back(

1027 FactOrCheck::getConditionFact(DTN, CmpInst::ICMP_SGE, PN, StartValue));

1028

1029 APInt StepOffset;

1030 if (auto *C = dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE)))

1031 StepOffset = C->getAPInt();

1032 else

1033 return;

1034

1035 // Make sure the bound B is loop-invariant.

1036 if (!L->isLoopInvariant(B))

1037 return;

1038

1039 // Handle negative steps.

1040 if (StepOffset.isNegative()) {

1041 // TODO: Extend to allow steps > -1.

1042 if (!(-StepOffset).isOne())

1043 return;

1044

1045 // AR may wrap.

1046 // Add StartValue >= PN conditional on B <= StartValue which guarantees that

1047 // the loop exits before wrapping with a step of -1.

1048 WorkList.push_back(FactOrCheck::getConditionFact(

1049 DTN, CmpInst::ICMP_UGE, StartValue, PN,

1050 ConditionTy(CmpInst::ICMP_ULE, B, StartValue)));

1051 WorkList.push_back(FactOrCheck::getConditionFact(

1052 DTN, CmpInst::ICMP_SGE, StartValue, PN,

1053 ConditionTy(CmpInst::ICMP_SLE, B, StartValue)));

1054 // Add PN > B conditional on B <= StartValue which guarantees that the loop

1055 // exits when reaching B with a step of -1.

1056 WorkList.push_back(FactOrCheck::getConditionFact(

1057 DTN, CmpInst::ICMP_UGT, PN, B,

1058 ConditionTy(CmpInst::ICMP_ULE, B, StartValue)));

1059 WorkList.push_back(FactOrCheck::getConditionFact(

1060 DTN, CmpInst::ICMP_SGT, PN, B,

1061 ConditionTy(CmpInst::ICMP_SLE, B, StartValue)));

1062 return;

1063 }

1064

1065 // Make sure AR either steps by 1 or that the value we compare against is a

1066 // GEP based on the same start value and all offsets are a multiple of the

1067 // step size, to guarantee that the induction will reach the value.

1068 if (StepOffset.isZero() || StepOffset.isNegative())

1069 return;

1070

1071 if (!StepOffset.isOne()) {

1072 // Check whether B-Start is known to be a multiple of StepOffset.

1073 const SCEV *BMinusStart = SE.getMinusSCEV(SE.getSCEV(B), StartSCEV);

1074 if (isa<SCEVCouldNotCompute>(BMinusStart) ||

1075 !SE.getConstantMultiple(BMinusStart).urem(StepOffset).isZero())

1076 return;

1077 }

1078

1079 // AR may wrap. Add PN >= StartValue conditional on StartValue <= B which

1080 // guarantees that the loop exits before wrapping in combination with the

1081 // restrictions on B and the step above.

1082 if (!MonotonicallyIncreasingUnsigned)

1083 WorkList.push_back(FactOrCheck::getConditionFact(

1084 DTN, CmpInst::ICMP_UGE, PN, StartValue,

1085 ConditionTy(CmpInst::ICMP_ULE, StartValue, B)));

1086 if (!MonotonicallyIncreasingSigned)

1087 WorkList.push_back(FactOrCheck::getConditionFact(

1088 DTN, CmpInst::ICMP_SGE, PN, StartValue,

1089 ConditionTy(CmpInst::ICMP_SLE, StartValue, B)));

1090

1091 WorkList.push_back(FactOrCheck::getConditionFact(

1092 DTN, CmpInst::ICMP_ULT, PN, B,

1093 ConditionTy(CmpInst::ICMP_ULE, StartValue, B)));

1094 WorkList.push_back(FactOrCheck::getConditionFact(

1095 DTN, CmpInst::ICMP_SLT, PN, B,

1096 ConditionTy(CmpInst::ICMP_SLE, StartValue, B)));

1097

1098 // Try to add condition from header to the dedicated exit blocks. When exiting

1099 // either with EQ or NE in the header, we know that the induction value must

1100 // be u<= B, as other exits may only exit earlier.

1101 assert(!StepOffset.isNegative() && "induction must be increasing");

1102 assert((Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) &&

1103 "unsupported predicate");

1104 ConditionTy Precond = {CmpInst::ICMP_ULE, StartValue, B};

1105 SmallVector<BasicBlock *> ExitBBs;

1106 L->getExitBlocks(ExitBBs);

1107 for (BasicBlock *EB : ExitBBs) {

1108 // Bail out on non-dedicated exits.

1109 if (DT.dominates(&BB, EB)) {

1110 WorkList.emplace_back(FactOrCheck::getConditionFact(

1111 DT.getNode(EB), CmpInst::ICMP_ULE, A, B, Precond));

1112 }

1113 }

1114}

1115

1116 static bool getConstraintFromMemoryAccess(GetElementPtrInst &GEP,

1117 uint64_t AccessSize,

1118 CmpPredicate &Pred, Value *&A,

1119 Value *&B, const DataLayout &DL,

1120 const TargetLibraryInfo &TLI) {

1121 auto Offset = collectOffsets(cast<GEPOperator>(GEP), DL);

1122 if (!Offset.NW.hasNoUnsignedWrap())

1123 return false;

1124

1125 if (Offset.VariableOffsets.size() != 1)

1126 return false;

1127

1128 uint64_t BitWidth = Offset.ConstantOffset.getBitWidth();

1129 auto &[Index, Scale] = Offset.VariableOffsets.front();

1130 // Bail out on non-canonical GEPs.

1131 if (Index->getType()->getScalarSizeInBits() != BitWidth)

1132 return false;

1133

1134 ObjectSizeOpts Opts;

1135 // Workaround for gep inbounds, ptr null, idx.

1136 Opts.NullIsUnknownSize = true;

1137 // Be conservative since we are not clear on whether an out of bounds access

1138 // to the padding is UB or not.

1139 Opts.RoundToAlign = true;

1140 std::optional<TypeSize> Size =

1141 getBaseObjectSize(Offset.BasePtr, DL, &TLI, Opts);

1142 if (!Size || Size->isScalable())

1143 return false;

1144

1145 // Index * Scale + ConstOffset + AccessSize <= AllocSize

1146 // With nuw flag, we know that the index addition doesn't have unsigned wrap.

1147 // If (AllocSize - (ConstOffset + AccessSize)) wraps around, there is no valid

1148 // value for Index.

1149 APInt MaxIndex = (APInt(BitWidth, Size->getFixedValue() - AccessSize,

1150 /*isSigned=*/false, /*implicitTrunc=*/true) -

1151 Offset.ConstantOffset)

1152 .udiv(Scale);

1153 Pred = ICmpInst::ICMP_ULE;

1154 A = Index;

1155 B = ConstantInt::get(Index->getType(), MaxIndex);

1156 return true;

1157}

1158

1159void State::addInfoFor(BasicBlock &BB) {

1160 addInfoForInductions(BB);

1161 auto &DL = BB.getDataLayout();

1162

1163 // True as long as the current instruction is guaranteed to execute.

1164 bool GuaranteedToExecute = true;

1165 // Queue conditions and assumes.

1166 for (Instruction &I : BB) {

1167 if (auto *Cmp = dyn_cast<ICmpInst>(&I)) {

1168 for (Use &U : Cmp->uses()) {

1169 auto *UserI = getContextInstForUse(U);

1170 auto *DTN = DT.getNode(UserI->getParent());

1171 if (!DTN)

1172 continue;

1173 WorkList.push_back(FactOrCheck::getCheck(DTN, &U));

1174 }

1175 continue;

1176 }

1177

1178 auto AddFactFromMemoryAccess = [&](Value *Ptr, Type *AccessType) {

1179 auto *GEP = dyn_cast<GetElementPtrInst>(Ptr);

1180 if (!GEP)

1181 return;

1182 TypeSize AccessSize = DL.getTypeStoreSize(AccessType);

1183 if (!AccessSize.isFixed())

1184 return;

1185 if (GuaranteedToExecute) {

1186 CmpPredicate Pred;

1187 Value *A, *B;

1188 if (getConstraintFromMemoryAccess(*GEP, AccessSize.getFixedValue(),

1189 Pred, A, B, DL, TLI)) {

1190 // The memory access is guaranteed to execute when BB is entered,

1191 // hence the constraint holds on entry to BB.

1192 WorkList.emplace_back(FactOrCheck::getConditionFact(

1193 DT.getNode(I.getParent()), Pred, A, B));

1194 }

1195 } else {

1196 WorkList.emplace_back(

1197 FactOrCheck::getInstFact(DT.getNode(I.getParent()), &I));

1198 }

1199 };

1200

1201 if (auto *LI = dyn_cast<LoadInst>(&I)) {

1202 if (!LI->isVolatile())

1203 AddFactFromMemoryAccess(LI->getPointerOperand(), LI->getAccessType());

1204 }

1205 if (auto *SI = dyn_cast<StoreInst>(&I)) {

1206 if (!SI->isVolatile())

1207 AddFactFromMemoryAccess(SI->getPointerOperand(), SI->getAccessType());

1208 }

1209

1210 auto *II = dyn_cast<IntrinsicInst>(&I);

1211 Intrinsic::ID ID = II ? II->getIntrinsicID() : Intrinsic::not_intrinsic;

1212 switch (ID) {

1213 case Intrinsic::assume: {

1214 Value *A, *B;

1215 CmpPredicate Pred;

1216 if (!match(I.getOperand(0), m_ICmp(Pred, m_Value(A), m_Value(B))))

1217 break;

1218 if (GuaranteedToExecute) {

1219 // The assume is guaranteed to execute when BB is entered, hence Cond

1220 // holds on entry to BB.

1221 WorkList.emplace_back(FactOrCheck::getConditionFact(

1222 DT.getNode(I.getParent()), Pred, A, B));

1223 } else {

1224 WorkList.emplace_back(

1225 FactOrCheck::getInstFact(DT.getNode(I.getParent()), &I));

1226 }

1227 break;

1228 }

1229 // Enqueue ssub_with_overflow for simplification.

1230 case Intrinsic::ssub_with_overflow:

1231 case Intrinsic::ucmp:

1232 case Intrinsic::scmp:

1233 WorkList.push_back(

1234 FactOrCheck::getCheck(DT.getNode(&BB), cast<CallInst>(&I)));

1235 break;

1236 // Enqueue the intrinsics to add extra info.

1237 case Intrinsic::umin:

1238 case Intrinsic::umax:

1239 case Intrinsic::smin:

1240 case Intrinsic::smax:

1241 // TODO: handle llvm.abs as well

1242 WorkList.push_back(

1243 FactOrCheck::getCheck(DT.getNode(&BB), cast<CallInst>(&I)));

1244 [[fallthrough]];

1245 case Intrinsic::uadd_sat:

1246 case Intrinsic::usub_sat:

1247 // TODO: Check if it is possible to instead only added the min/max facts

1248 // when simplifying uses of the min/max intrinsics.

1249 if (!isGuaranteedNotToBePoison(&I))

1250 break;

1251 [[fallthrough]];

1252 case Intrinsic::abs:

1253 WorkList.push_back(FactOrCheck::getInstFact(DT.getNode(&BB), &I));

1254 break;

1255 }

1256

1257 GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(&I);

1258 }

1259

1260 if (auto *Switch = dyn_cast<SwitchInst>(BB.getTerminator())) {

1261 for (auto &Case : Switch->cases()) {

1262 BasicBlock *Succ = Case.getCaseSuccessor();

1263 Value *V = Case.getCaseValue();

1264 if (!canAddSuccessor(BB, Succ))

1265 continue;

1266 WorkList.emplace_back(FactOrCheck::getConditionFact(

1267 DT.getNode(Succ), CmpInst::ICMP_EQ, Switch->getCondition(), V));

1268 }

1269 return;

1270 }

1271

1272 auto *Br = dyn_cast<BranchInst>(BB.getTerminator());

1273 if (!Br || !Br->isConditional())

1274 return;

1275

1276 Value *Cond = Br->getCondition();

1277

1278 // If the condition is a chain of ORs/AND and the successor only has the

1279 // current block as predecessor, queue conditions for the successor.

1280 Value *Op0, *Op1;

1281 if (match(Cond, m_LogicalOr(m_Value(Op0), m_Value(Op1))) ||

1282 match(Cond, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {

1283 bool IsOr = match(Cond, m_LogicalOr());

1284 bool IsAnd = match(Cond, m_LogicalAnd());

1285 // If there's a select that matches both AND and OR, we need to commit to

1286 // one of the options. Arbitrarily pick OR.

1287 if (IsOr && IsAnd)

1288 IsAnd = false;

1289

1290 BasicBlock *Successor = Br->getSuccessor(IsOr ? 1 : 0);

1291 if (canAddSuccessor(BB, Successor)) {

1292 SmallVector<Value *> CondWorkList;

1293 SmallPtrSet<Value *, 8> SeenCond;

1294 auto QueueValue = [&CondWorkList, &SeenCond](Value *V) {

1295 if (SeenCond.insert(V).second)

1296 CondWorkList.push_back(V);

1297 };

1298 QueueValue(Op1);

1299 QueueValue(Op0);

1300 while (!CondWorkList.empty()) {

1301 Value *Cur = CondWorkList.pop_back_val();

1302 if (auto *Cmp = dyn_cast<ICmpInst>(Cur)) {

1303 WorkList.emplace_back(FactOrCheck::getConditionFact(

1304 DT.getNode(Successor),

1305 IsOr ? Cmp->getInverseCmpPredicate() : Cmp->getCmpPredicate(),

1306 Cmp->getOperand(0), Cmp->getOperand(1)));

1307 continue;

1308 }

1309 if (IsOr && match(Cur, m_LogicalOr(m_Value(Op0), m_Value(Op1)))) {

1310 QueueValue(Op1);

1311 QueueValue(Op0);

1312 continue;

1313 }

1314 if (IsAnd && match(Cur, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {

1315 QueueValue(Op1);

1316 QueueValue(Op0);

1317 continue;

1318 }

1319 }

1320 }

1321 return;

1322 }

1323

1324 auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition());

1325 if (!CmpI)

1326 return;

1327 if (canAddSuccessor(BB, Br->getSuccessor(0)))

1328 WorkList.emplace_back(FactOrCheck::getConditionFact(

1329 DT.getNode(Br->getSuccessor(0)), CmpI->getCmpPredicate(),

1330 CmpI->getOperand(0), CmpI->getOperand(1)));

1331 if (canAddSuccessor(BB, Br->getSuccessor(1)))

1332 WorkList.emplace_back(FactOrCheck::getConditionFact(

1333 DT.getNode(Br->getSuccessor(1)), CmpI->getInverseCmpPredicate(),

1334 CmpI->getOperand(0), CmpI->getOperand(1)));

1335}

1336

1337#ifndef NDEBUG

1338 static void dumpUnpackedICmp(raw_ostream &OS, ICmpInst::Predicate Pred,

1339 Value *LHS, Value *RHS) {

1340 OS << "icmp " << Pred << ' ';

1341 LHS->printAsOperand(OS, /*PrintType=*/true);

1342 OS << ", ";

1343 RHS->printAsOperand(OS, /*PrintType=*/false);

1344}

1345#endif

1346

1347namespace {

1348/// Helper to keep track of a condition and if it should be treated as negated

1349/// for reproducer construction.

1350/// Pred == Predicate::BAD_ICMP_PREDICATE indicates that this entry is a

1351/// placeholder to keep the ReproducerCondStack in sync with DFSInStack.

1352struct ReproducerEntry {

1353 ICmpInst::Predicate Pred;

1354 Value *LHS;

1355 Value *RHS;

1356

1357 ReproducerEntry(ICmpInst::Predicate Pred, Value *LHS, Value *RHS)

1358 : Pred(Pred), LHS(LHS), RHS(RHS) {}

1359};

1360} // namespace

1361

1362/// Helper function to generate a reproducer function for simplifying \p Cond.

1363/// The reproducer function contains a series of @llvm.assume calls, one for

1364/// each condition in \p Stack. For each condition, the operand instruction are

1365/// cloned until we reach operands that have an entry in \p Value2Index. Those

1366/// will then be added as function arguments. \p DT is used to order cloned

1367/// instructions. The reproducer function will get added to \p M, if it is

1368/// non-null. Otherwise no reproducer function is generated.

1369 static void generateReproducer(CmpInst *Cond, Module *M,

1370 ArrayRef<ReproducerEntry> Stack,

1371 ConstraintInfo &Info, DominatorTree &DT) {

1372 if (!M)

1373 return;

1374

1375 LLVMContext &Ctx = Cond->getContext();

1376

1377 LLVM_DEBUG(dbgs() << "Creating reproducer for " << *Cond << "\n");

1378

1379 ValueToValueMapTy Old2New;

1380 SmallVector<Value *> Args;

1381 SmallPtrSet<Value *, 8> Seen;

1382 // Traverse Cond and its operands recursively until we reach a value that's in

1383 // Value2Index or not an instruction, or not a operation that

1384 // ConstraintElimination can decompose. Such values will be considered as

1385 // external inputs to the reproducer, they are collected and added as function

1386 // arguments later.

1387 auto CollectArguments = [&](ArrayRef<Value *> Ops, bool IsSigned) {

1388 auto &Value2Index = Info.getValue2Index(IsSigned);

1389 SmallVector<Value *, 4> WorkList(Ops);

1390 while (!WorkList.empty()) {

1391 Value *V = WorkList.pop_back_val();

1392 if (!Seen.insert(V).second)

1393 continue;

1394 if (Old2New.find(V) != Old2New.end())

1395 continue;

1396 if (isa<Constant>(V))

1397 continue;

1398

1399 auto *I = dyn_cast<Instruction>(V);

1400 if (Value2Index.contains(V) || !I ||

1401 !isa<CmpInst, BinaryOperator, GEPOperator, CastInst>(V)) {

1402 Old2New[V] = V;

1403 Args.push_back(V);

1404 LLVM_DEBUG(dbgs() << " found external input " << *V << "\n");

1405 } else {

1406 append_range(WorkList, I->operands());

1407 }

1408 }

1409 };

1410

1411 for (auto &Entry : Stack)

1412 if (Entry.Pred != ICmpInst::BAD_ICMP_PREDICATE)

1413 CollectArguments({Entry.LHS, Entry.RHS}, ICmpInst::isSigned(Entry.Pred));

1414 CollectArguments(Cond, ICmpInst::isSigned(Cond->getPredicate()));

1415

1416 SmallVector<Type *> ParamTys;

1417 for (auto *P : Args)

1418 ParamTys.push_back(P->getType());

1419

1420 FunctionType *FTy = FunctionType::get(Cond->getType(), ParamTys,

1421 /*isVarArg=*/false);

1422 Function *F = Function::Create(FTy, Function::ExternalLinkage,

1423 Cond->getModule()->getName() +

1424 Cond->getFunction()->getName() + "repro",

1425 M);

1426 // Add arguments to the reproducer function for each external value collected.

1427 for (unsigned I = 0; I < Args.size(); ++I) {

1428 F->getArg(I)->setName(Args[I]->getName());

1429 Old2New[Args[I]] = F->getArg(I);

1430 }

1431

1432 BasicBlock *Entry = BasicBlock::Create(Ctx, "entry", F);

1433 IRBuilder<> Builder(Entry);

1434 Builder.CreateRet(Builder.getTrue());

1435 Builder.SetInsertPoint(Entry->getTerminator());

1436

1437 // Clone instructions in \p Ops and their operands recursively until reaching

1438 // an value in Value2Index (external input to the reproducer). Update Old2New

1439 // mapping for the original and cloned instructions. Sort instructions to

1440 // clone by dominance, then insert the cloned instructions in the function.

1441 auto CloneInstructions = [&](ArrayRef<Value *> Ops, bool IsSigned) {

1442 SmallVector<Value *, 4> WorkList(Ops);

1443 SmallVector<Instruction *> ToClone;

1444 auto &Value2Index = Info.getValue2Index(IsSigned);

1445 while (!WorkList.empty()) {

1446 Value *V = WorkList.pop_back_val();

1447 if (Old2New.find(V) != Old2New.end())

1448 continue;

1449

1450 auto *I = dyn_cast<Instruction>(V);

1451 if (!Value2Index.contains(V) && I) {

1452 Old2New[V] = nullptr;

1453 ToClone.push_back(I);

1454 append_range(WorkList, I->operands());

1455 }

1456 }

1457

1458 sort(ToClone,

1459 [&DT](Instruction *A, Instruction *B) { return DT.dominates(A, B); });

1460 for (Instruction *I : ToClone) {

1461 Instruction *Cloned = I->clone();

1462 Old2New[I] = Cloned;

1463 Old2New[I]->setName(I->getName());

1464 Cloned->insertBefore(Builder.GetInsertPoint());

1465 Cloned->dropUnknownNonDebugMetadata();

1466 Cloned->setDebugLoc({});

1467 }

1468 };

1469

1470 // Materialize the assumptions for the reproducer using the entries in Stack.

1471 // That is, first clone the operands of the condition recursively until we

1472 // reach an external input to the reproducer and add them to the reproducer

1473 // function. Then add an ICmp for the condition (with the inverse predicate if

1474 // the entry is negated) and an assert using the ICmp.

1475 for (auto &Entry : Stack) {

1476 if (Entry.Pred == ICmpInst::BAD_ICMP_PREDICATE)

1477 continue;

1478

1479 LLVM_DEBUG(dbgs() << " Materializing assumption ";

1480 dumpUnpackedICmp(dbgs(), Entry.Pred, Entry.LHS, Entry.RHS);

1481 dbgs() << "\n");

1482 CloneInstructions({Entry.LHS, Entry.RHS}, CmpInst::isSigned(Entry.Pred));

1483

1484 auto *Cmp = Builder.CreateICmp(Entry.Pred, Entry.LHS, Entry.RHS);

1485 Builder.CreateAssumption(Cmp);

1486 }

1487

1488 // Finally, clone the condition to reproduce and remap instruction operands in

1489 // the reproducer using Old2New.

1490 CloneInstructions(Cond, CmpInst::isSigned(Cond->getPredicate()));

1491 Entry->getTerminator()->setOperand(0, Cond);

1492 remapInstructionsInBlocks({Entry}, Old2New);

1493

1494 assert(!verifyFunction(*F, &dbgs()));

1495}

1496

1497 static std::optional<bool> checkCondition(CmpInst::Predicate Pred, Value *A,

1498 Value *B, Instruction *CheckInst,

1499 ConstraintInfo &Info) {

1500 LLVM_DEBUG(dbgs() << "Checking " << *CheckInst << "\n");

1501

1502 auto R = Info.getConstraintForSolving(Pred, A, B);

1503 if (R.empty() || !R.isValid(Info)) {

1504 LLVM_DEBUG(dbgs() << " failed to decompose condition\n");

1505 return std::nullopt;

1506 }

1507

1508 auto &CSToUse = Info.getCS(R.IsSigned);

1509

1510 // If there was extra information collected during decomposition, apply

1511 // it now and remove it immediately once we are done with reasoning

1512 // about the constraint.

1513 for (auto &Row : R.ExtraInfo)

1514 CSToUse.addVariableRow(Row);

1515 auto InfoRestorer = make_scope_exit([&]() {

1516 for (unsigned I = 0; I < R.ExtraInfo.size(); ++I)

1517 CSToUse.popLastConstraint();

1518 });

1519

1520 if (auto ImpliedCondition = R.isImpliedBy(CSToUse)) {

1521 if (!DebugCounter::shouldExecute(EliminatedCounter))

1522 return std::nullopt;

1523

1524 LLVM_DEBUG({

1525 dbgs() << "Condition ";

1526 dumpUnpackedICmp(

1527 dbgs(), *ImpliedCondition ? Pred : CmpInst::getInversePredicate(Pred),

1528 A, B);

1529 dbgs() << " implied by dominating constraints\n";

1530 CSToUse.dump();

1531 });

1532 return ImpliedCondition;

1533 }

1534

1535 return std::nullopt;

1536}

1537

1538 static bool checkAndReplaceCondition(

1539 ICmpInst *Cmp, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut,

1540 Instruction *ContextInst, Module *ReproducerModule,

1541 ArrayRef<ReproducerEntry> ReproducerCondStack, DominatorTree &DT,

1542 SmallVectorImpl<Instruction *> &ToRemove) {

1543 auto ReplaceCmpWithConstant = [&](CmpInst *Cmp, bool IsTrue) {

1544 generateReproducer(Cmp, ReproducerModule, ReproducerCondStack, Info, DT);

1545 Constant *ConstantC = ConstantInt::getBool(

1546 CmpInst::makeCmpResultType(Cmp->getType()), IsTrue);

1547 bool Changed = false;

1548 Cmp->replaceUsesWithIf(ConstantC, [&DT, NumIn, NumOut, ContextInst,

1549 &Changed](Use &U) {

1550 auto *UserI = getContextInstForUse(U);

1551 auto *DTN = DT.getNode(UserI->getParent());

1552 if (!DTN || DTN->getDFSNumIn() < NumIn || DTN->getDFSNumOut() > NumOut)

1553 return false;

1554 if (UserI->getParent() == ContextInst->getParent() &&

1555 UserI->comesBefore(ContextInst))

1556 return false;

1557

1558 // Conditions in an assume trivially simplify to true. Skip uses

1559 // in assume calls to not destroy the available information.

1560 auto *II = dyn_cast<IntrinsicInst>(U.getUser());

1561 bool ShouldReplace = !II || II->getIntrinsicID() != Intrinsic::assume;

1562 Changed |= ShouldReplace;

1563 return ShouldReplace;

1564 });

1565 NumCondsRemoved++;

1566

1567 // Update the debug value records that satisfy the same condition used

1568 // in replaceUsesWithIf.

1569 SmallVector<DbgVariableRecord *> DVRUsers;

1570 findDbgUsers(Cmp, DVRUsers);

1571

1572 for (auto *DVR : DVRUsers) {

1573 auto *DTN = DT.getNode(DVR->getParent());

1574 if (!DTN || DTN->getDFSNumIn() < NumIn || DTN->getDFSNumOut() > NumOut)

1575 continue;

1576

1577 auto *MarkedI = DVR->getInstruction();

1578 if (MarkedI->getParent() == ContextInst->getParent() &&

1579 MarkedI->comesBefore(ContextInst))

1580 continue;

1581

1582 DVR->replaceVariableLocationOp(Cmp, ConstantC);

1583 }

1584

1585 if (Cmp->use_empty())

1586 ToRemove.push_back(Cmp);

1587

1588 return Changed;

1589 };

1590

1591 if (auto ImpliedCondition =

1592 checkCondition(Cmp->getPredicate(), Cmp->getOperand(0),

1593 Cmp->getOperand(1), Cmp, Info))

1594 return ReplaceCmpWithConstant(Cmp, *ImpliedCondition);

1595

1596 // When the predicate is samesign and unsigned, we can also make use of the

1597 // signed predicate information.

1598 if (Cmp->hasSameSign() && Cmp->isUnsigned())

1599 if (auto ImpliedCondition =

1600 checkCondition(Cmp->getSignedPredicate(), Cmp->getOperand(0),

1601 Cmp->getOperand(1), Cmp, Info))

1602 return ReplaceCmpWithConstant(Cmp, *ImpliedCondition);

1603

1604 return false;

1605}

1606

1607 static bool checkAndReplaceMinMax(MinMaxIntrinsic *MinMax, ConstraintInfo &Info,

1608 SmallVectorImpl<Instruction *> &ToRemove) {

1609 auto ReplaceMinMaxWithOperand = [&](MinMaxIntrinsic *MinMax, bool UseLHS) {

1610 // TODO: generate reproducer for min/max.

1611 MinMax->replaceAllUsesWith(MinMax->getOperand(UseLHS ? 0 : 1));

1612 ToRemove.push_back(MinMax);

1613 return true;

1614 };

1615

1616 ICmpInst::Predicate Pred =

1617 ICmpInst::getNonStrictPredicate(MinMax->getPredicate());

1618 if (auto ImpliedCondition = checkCondition(

1619 Pred, MinMax->getOperand(0), MinMax->getOperand(1), MinMax, Info))

1620 return ReplaceMinMaxWithOperand(MinMax, *ImpliedCondition);

1621 if (auto ImpliedCondition = checkCondition(

1622 Pred, MinMax->getOperand(1), MinMax->getOperand(0), MinMax, Info))

1623 return ReplaceMinMaxWithOperand(MinMax, !*ImpliedCondition);

1624 return false;

1625}

1626

1627 static bool checkAndReplaceCmp(CmpIntrinsic *I, ConstraintInfo &Info,

1628 SmallVectorImpl<Instruction *> &ToRemove) {

1629 Value *LHS = I->getOperand(0);

1630 Value *RHS = I->getOperand(1);

1631 if (checkCondition(I->getGTPredicate(), LHS, RHS, I, Info).value_or(false)) {

1632 I->replaceAllUsesWith(ConstantInt::get(I->getType(), 1));

1633 ToRemove.push_back(I);

1634 return true;

1635 }

1636 if (checkCondition(I->getLTPredicate(), LHS, RHS, I, Info).value_or(false)) {

1637 I->replaceAllUsesWith(ConstantInt::getSigned(I->getType(), -1));

1638 ToRemove.push_back(I);

1639 return true;

1640 }

1641 if (checkCondition(ICmpInst::ICMP_EQ, LHS, RHS, I, Info).value_or(false)) {

1642 I->replaceAllUsesWith(ConstantInt::get(I->getType(), 0));

1643 ToRemove.push_back(I);

1644 return true;

1645 }

1646 return false;

1647}

1648

1649static void

1650 removeEntryFromStack(const StackEntry &E, ConstraintInfo &Info,

1651 Module *ReproducerModule,

1652 SmallVectorImpl<ReproducerEntry> &ReproducerCondStack,

1653 SmallVectorImpl<StackEntry> &DFSInStack) {

1654 Info.popLastConstraint(E.IsSigned);

1655 // Remove variables in the system that went out of scope.

1656 auto &Mapping = Info.getValue2Index(E.IsSigned);

1657 for (Value *V : E.ValuesToRelease)

1658 Mapping.erase(V);

1659 Info.popLastNVariables(E.IsSigned, E.ValuesToRelease.size());

1660 DFSInStack.pop_back();

1661 if (ReproducerModule)

1662 ReproducerCondStack.pop_back();

1663}

1664

1665/// Check if either the first condition of an AND or OR is implied by the

1666/// (negated in case of OR) second condition or vice versa.

1667 static bool checkOrAndOpImpliedByOther(

1668 FactOrCheck &CB, ConstraintInfo &Info, Module *ReproducerModule,

1669 SmallVectorImpl<ReproducerEntry> &ReproducerCondStack,

1670 SmallVectorImpl<StackEntry> &DFSInStack,

1671 SmallVectorImpl<Instruction *> &ToRemove) {

1672 Instruction *JoinOp = CB.getContextInst();

1673 if (JoinOp->use_empty())

1674 return false;

1675

1676 CmpInst *CmpToCheck = cast<CmpInst>(CB.getInstructionToSimplify());

1677 unsigned OtherOpIdx = JoinOp->getOperand(0) == CmpToCheck ? 1 : 0;

1678

1679 // Don't try to simplify the first condition of a select by the second, as

1680 // this may make the select more poisonous than the original one.

1681 // TODO: check if the first operand may be poison.

1682 if (OtherOpIdx != 0 && isa<SelectInst>(JoinOp))

1683 return false;

1684

1685 unsigned OldSize = DFSInStack.size();

1686 auto InfoRestorer = make_scope_exit([&]() {

1687 // Remove entries again.

1688 while (OldSize < DFSInStack.size()) {

1689 StackEntry E = DFSInStack.back();

1690 removeEntryFromStack(E, Info, ReproducerModule, ReproducerCondStack,

1691 DFSInStack);

1692 }

1693 });

1694 bool IsOr = match(JoinOp, m_LogicalOr());

1695 SmallVector<Value *, 4> Worklist({JoinOp->getOperand(OtherOpIdx)});

1696 // Do a traversal of the AND/OR tree to add facts from leaf compares.

1697 while (!Worklist.empty()) {

1698 Value *Val = Worklist.pop_back_val();

1699 Value *LHS, *RHS;

1700 CmpPredicate Pred;

1701 if (match(Val, m_ICmp(Pred, m_Value(LHS), m_Value(RHS)))) {

1702 // For OR, check if the negated condition implies CmpToCheck.

1703 if (IsOr)

1704 Pred = CmpInst::getInversePredicate(Pred);

1705 // Optimistically add fact from the other compares in the AND/OR.

1706 Info.addFact(Pred, LHS, RHS, CB.NumIn, CB.NumOut, DFSInStack);

1707 continue;

1708 }

1709 if (IsOr ? match(Val, m_LogicalOr(m_Value(LHS), m_Value(RHS)))

1710 : match(Val, m_LogicalAnd(m_Value(LHS), m_Value(RHS)))) {

1711 Worklist.push_back(LHS);

1712 Worklist.push_back(RHS);

1713 }

1714 }

1715 if (OldSize == DFSInStack.size())

1716 return false;

1717

1718 // Check if the second condition can be simplified now.

1719 if (auto ImpliedCondition =

1720 checkCondition(CmpToCheck->getPredicate(), CmpToCheck->getOperand(0),

1721 CmpToCheck->getOperand(1), CmpToCheck, Info)) {

1722 if (IsOr == *ImpliedCondition)

1723 JoinOp->replaceAllUsesWith(

1724 ConstantInt::getBool(JoinOp->getType(), *ImpliedCondition));

1725 else

1726 JoinOp->replaceAllUsesWith(JoinOp->getOperand(OtherOpIdx));

1727 ToRemove.push_back(JoinOp);

1728 return true;

1729 }

1730

1731 return false;

1732}

1733

1734void ConstraintInfo::addFact(CmpInst::Predicate Pred, Value *A, Value *B,

1735 unsigned NumIn, unsigned NumOut,

1736 SmallVectorImpl<StackEntry> &DFSInStack) {

1737 addFactImpl(Pred, A, B, NumIn, NumOut, DFSInStack, false);

1738 // If the Pred is eq/ne, also add the fact to signed system.

1739 if (CmpInst::isEquality(Pred))

1740 addFactImpl(Pred, A, B, NumIn, NumOut, DFSInStack, true);

1741}

1742

1743void ConstraintInfo::addFactImpl(CmpInst::Predicate Pred, Value *A, Value *B,

1744 unsigned NumIn, unsigned NumOut,

1745 SmallVectorImpl<StackEntry> &DFSInStack,

1746 bool ForceSignedSystem) {

1747 // If the constraint has a pre-condition, skip the constraint if it does not

1748 // hold.

1749 SmallVector<Value *> NewVariables;

1750 auto R = getConstraint(Pred, A, B, NewVariables, ForceSignedSystem);

1751

1752 // TODO: Support non-equality for facts as well.

1753 if (!R.isValid(*this) || R.isNe())

1754 return;

1755

1756 LLVM_DEBUG(dbgs() << "Adding '"; dumpUnpackedICmp(dbgs(), Pred, A, B);

1757 dbgs() << "'\n");

1758 auto &CSToUse = getCS(R.IsSigned);

1759 if (R.Coefficients.empty())

1760 return;

1761

1762 bool Added = CSToUse.addVariableRowFill(R.Coefficients);

1763 if (!Added)

1764 return;

1765

1766 // If R has been added to the system, add the new variables and queue it for

1767 // removal once it goes out-of-scope.

1768 SmallVector<Value *, 2> ValuesToRelease;

1769 auto &Value2Index = getValue2Index(R.IsSigned);

1770 for (Value *V : NewVariables) {

1771 Value2Index.insert({V, Value2Index.size() + 1});

1772 ValuesToRelease.push_back(V);

1773 }

1774

1775 LLVM_DEBUG({

1776 dbgs() << " constraint: ";

1777 dumpConstraint(R.Coefficients, getValue2Index(R.IsSigned));

1778 dbgs() << "\n";

1779 });

1780

1781 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,

1782 std::move(ValuesToRelease));

1783

1784 if (!R.IsSigned) {

1785 for (Value *V : NewVariables) {

1786 ConstraintTy VarPos(SmallVector<int64_t, 8>(Value2Index.size() + 1, 0),

1787 false, false, false);

1788 VarPos.Coefficients[Value2Index[V]] = -1;

1789 CSToUse.addVariableRow(VarPos.Coefficients);

1790 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,

1791 SmallVector<Value *, 2>());

1792 }

1793 }

1794

1795 if (R.isEq()) {

1796 // Also add the inverted constraint for equality constraints.

1797 for (auto &Coeff : R.Coefficients)

1798 Coeff *= -1;

1799 CSToUse.addVariableRowFill(R.Coefficients);

1800

1801 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,

1802 SmallVector<Value *, 2>());

1803 }

1804}

1805

1806 static bool replaceSubOverflowUses(IntrinsicInst *II, Value *A, Value *B,

1807 SmallVectorImpl<Instruction *> &ToRemove) {

1808 bool Changed = false;

1809 IRBuilder<> Builder(II->getParent(), II->getIterator());

1810 Value *Sub = nullptr;

1811 for (User *U : make_early_inc_range(II->users())) {

1812 if (match(U, m_ExtractValue<0>(m_Value()))) {

1813 if (!Sub)

1814 Sub = Builder.CreateSub(A, B);

1815 U->replaceAllUsesWith(Sub);

1816 Changed = true;

1817 } else if (match(U, m_ExtractValue<1>(m_Value()))) {

1818 U->replaceAllUsesWith(Builder.getFalse());

1819 Changed = true;

1820 } else

1821 continue;

1822

1823 if (U->use_empty()) {

1824 auto *I = cast<Instruction>(U);

1825 ToRemove.push_back(I);

1826 I->setOperand(0, PoisonValue::get(II->getType()));

1827 Changed = true;

1828 }

1829 }

1830

1831 if (II->use_empty()) {

1832 II->eraseFromParent();

1833 Changed = true;

1834 }

1835 return Changed;

1836}

1837

1838static bool

1839 tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info,

1840 SmallVectorImpl<Instruction *> &ToRemove) {

1841 auto DoesConditionHold = [](CmpInst::Predicate Pred, Value *A, Value *B,

1842 ConstraintInfo &Info) {

1843 auto R = Info.getConstraintForSolving(Pred, A, B);

1844 if (R.size() < 2 || !R.isValid(Info))

1845 return false;

1846

1847 auto &CSToUse = Info.getCS(R.IsSigned);

1848 return CSToUse.isConditionImplied(R.Coefficients);

1849 };

1850

1851 bool Changed = false;

1852 if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow) {

1853 // If A s>= B && B s>= 0, ssub.with.overflow(a, b) should not overflow and

1854 // can be simplified to a regular sub.

1855 Value *A = II->getArgOperand(0);

1856 Value *B = II->getArgOperand(1);

1857 if (!DoesConditionHold(CmpInst::ICMP_SGE, A, B, Info) ||

1858 !DoesConditionHold(CmpInst::ICMP_SGE, B,

1859 ConstantInt::get(A->getType(), 0), Info))

1860 return false;

1861 Changed = replaceSubOverflowUses(II, A, B, ToRemove);

1862 }

1863 return Changed;

1864}

1865

1866 static bool eliminateConstraints(Function &F, DominatorTree &DT, LoopInfo &LI,

1867 ScalarEvolution &SE,

1868 OptimizationRemarkEmitter &ORE,

1869 TargetLibraryInfo &TLI) {

1870 bool Changed = false;

1871 DT.updateDFSNumbers();

1872 SmallVector<Value *> FunctionArgs(llvm::make_pointer_range(F.args()));

1873 ConstraintInfo Info(F.getDataLayout(), FunctionArgs);

1874 State S(DT, LI, SE, TLI);

1875 std::unique_ptr<Module> ReproducerModule(

1876 DumpReproducers ? new Module(F.getName(), F.getContext()) : nullptr);

1877

1878 // First, collect conditions implied by branches and blocks with their

1879 // Dominator DFS in and out numbers.

1880 for (BasicBlock &BB : F) {

1881 if (!DT.getNode(&BB))

1882 continue;

1883 S.addInfoFor(BB);

1884 }

1885

1886 // Next, sort worklist by dominance, so that dominating conditions to check

1887 // and facts come before conditions and facts dominated by them. If a

1888 // condition to check and a fact have the same numbers, conditional facts come

1889 // first. Assume facts and checks are ordered according to their relative

1890 // order in the containing basic block. Also make sure conditions with

1891 // constant operands come before conditions without constant operands. This

1892 // increases the effectiveness of the current signed <-> unsigned fact

1893 // transfer logic.

1894 stable_sort(S.WorkList, [](const FactOrCheck &A, const FactOrCheck &B) {

1895 auto HasNoConstOp = [](const FactOrCheck &B) {

1896 Value *V0 = B.isConditionFact() ? B.Cond.Op0 : B.Inst->getOperand(0);

1897 Value *V1 = B.isConditionFact() ? B.Cond.Op1 : B.Inst->getOperand(1);

1898 return !isa<ConstantInt>(V0) && !isa<ConstantInt>(V1);

1899 };

1900 // If both entries have the same In numbers, conditional facts come first.

1901 // Otherwise use the relative order in the basic block.

1902 if (A.NumIn == B.NumIn) {

1903 if (A.isConditionFact() && B.isConditionFact()) {

1904 bool NoConstOpA = HasNoConstOp(A);

1905 bool NoConstOpB = HasNoConstOp(B);

1906 return NoConstOpA < NoConstOpB;

1907 }

1908 if (A.isConditionFact())

1909 return true;

1910 if (B.isConditionFact())

1911 return false;

1912 auto *InstA = A.getContextInst();

1913 auto *InstB = B.getContextInst();

1914 return InstA->comesBefore(InstB);

1915 }

1916 return A.NumIn < B.NumIn;

1917 });

1918

1919 SmallVector<Instruction *> ToRemove;

1920

1921 // Finally, process ordered worklist and eliminate implied conditions.

1922 SmallVector<StackEntry, 16> DFSInStack;

1923 SmallVector<ReproducerEntry> ReproducerCondStack;

1924 for (FactOrCheck &CB : S.WorkList) {

1925 // First, pop entries from the stack that are out-of-scope for CB. Remove

1926 // the corresponding entry from the constraint system.

1927 while (!DFSInStack.empty()) {

1928 auto &E = DFSInStack.back();

1929 LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut

1930 << "\n");

1931 LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n");

1932 assert(E.NumIn <= CB.NumIn);

1933 if (CB.NumOut <= E.NumOut)

1934 break;

1935 LLVM_DEBUG({

1936 dbgs() << "Removing ";

1937 dumpConstraint(Info.getCS(E.IsSigned).getLastConstraint(),

1938 Info.getValue2Index(E.IsSigned));

1939 dbgs() << "\n";

1940 });

1941 removeEntryFromStack(E, Info, ReproducerModule.get(), ReproducerCondStack,

1942 DFSInStack);

1943 }

1944

1945 // For a block, check if any CmpInsts become known based on the current set

1946 // of constraints.

1947 if (CB.isCheck()) {

1948 Instruction *Inst = CB.getInstructionToSimplify();

1949 if (!Inst)

1950 continue;

1951 LLVM_DEBUG(dbgs() << "Processing condition to simplify: " << *Inst

1952 << "\n");

1953 if (auto *II = dyn_cast<WithOverflowInst>(Inst)) {

1954 Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove);

1955 } else if (auto *Cmp = dyn_cast<ICmpInst>(Inst)) {

1956 bool Simplified = checkAndReplaceCondition(

1957 Cmp, Info, CB.NumIn, CB.NumOut, CB.getContextInst(),

1958 ReproducerModule.get(), ReproducerCondStack, S.DT, ToRemove);

1959 if (!Simplified &&

1960 match(CB.getContextInst(), m_LogicalOp(m_Value(), m_Value()))) {

1961 Simplified = checkOrAndOpImpliedByOther(

1962 CB, Info, ReproducerModule.get(), ReproducerCondStack, DFSInStack,

1963 ToRemove);

1964 }

1965 Changed |= Simplified;

1966 } else if (auto *MinMax = dyn_cast<MinMaxIntrinsic>(Inst)) {

1967 Changed |= checkAndReplaceMinMax(MinMax, Info, ToRemove);

1968 } else if (auto *CmpIntr = dyn_cast<CmpIntrinsic>(Inst)) {

1969 Changed |= checkAndReplaceCmp(CmpIntr, Info, ToRemove);

1970 }

1971 continue;

1972 }

1973

1974 auto AddFact = [&](CmpPredicate Pred, Value *A, Value *B) {

1975 LLVM_DEBUG(dbgs() << "Processing fact to add to the system: ";

1976 dumpUnpackedICmp(dbgs(), Pred, A, B); dbgs() << "\n");

1977 if (Info.getCS(CmpInst::isSigned(Pred)).size() > MaxRows) {

1978 LLVM_DEBUG(

1979 dbgs()

1980 << "Skip adding constraint because system has too many rows.\n");

1981 return;

1982 }

1983

1984 Info.addFact(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);

1985 if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size())

1986 ReproducerCondStack.emplace_back(Pred, A, B);

1987

1988 if (ICmpInst::isRelational(Pred)) {

1989 // If samesign is present on the ICmp, simply flip the sign of the

1990 // predicate, transferring the information from the signed system to the

1991 // unsigned system, and viceversa.

1992 if (Pred.hasSameSign())

1993 Info.addFact(ICmpInst::getFlippedSignednessPredicate(Pred), A, B,

1994 CB.NumIn, CB.NumOut, DFSInStack);

1995 else

1996 Info.transferToOtherSystem(Pred, A, B, CB.NumIn, CB.NumOut,

1997 DFSInStack);

1998 }

1999

2000 if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size()) {

2001 // Add dummy entries to ReproducerCondStack to keep it in sync with

2002 // DFSInStack.

2003 for (unsigned I = 0,

2004 E = (DFSInStack.size() - ReproducerCondStack.size());

2005 I < E; ++I) {

2006 ReproducerCondStack.emplace_back(ICmpInst::BAD_ICMP_PREDICATE,

2007 nullptr, nullptr);

2008 }

2009 }

2010 };

2011

2012 CmpPredicate Pred;

2013 if (!CB.isConditionFact()) {

2014 Value *X;

2015 if (match(CB.Inst, m_Intrinsic<Intrinsic::abs>(m_Value(X)))) {

2016 // If is_int_min_poison is true then we may assume llvm.abs >= 0.

2017 if (cast<ConstantInt>(CB.Inst->getOperand(1))->isOne())

2018 AddFact(CmpInst::ICMP_SGE, CB.Inst,

2019 ConstantInt::get(CB.Inst->getType(), 0));

2020 AddFact(CmpInst::ICMP_SGE, CB.Inst, X);

2021 continue;

2022 }

2023

2024 if (auto *MinMax = dyn_cast<MinMaxIntrinsic>(CB.Inst)) {

2025 Pred = ICmpInst::getNonStrictPredicate(MinMax->getPredicate());

2026 AddFact(Pred, MinMax, MinMax->getLHS());

2027 AddFact(Pred, MinMax, MinMax->getRHS());

2028 continue;

2029 }

2030 if (auto *USatI = dyn_cast<SaturatingInst>(CB.Inst)) {

2031 switch (USatI->getIntrinsicID()) {

2032 default:

2033 llvm_unreachable("Unexpected intrinsic.");

2034 case Intrinsic::uadd_sat:

2035 AddFact(ICmpInst::ICMP_UGE, USatI, USatI->getLHS());

2036 AddFact(ICmpInst::ICMP_UGE, USatI, USatI->getRHS());

2037 break;

2038 case Intrinsic::usub_sat:

2039 AddFact(ICmpInst::ICMP_ULE, USatI, USatI->getLHS());

2040 break;

2041 }

2042 continue;

2043 }

2044

2045 auto &DL = F.getDataLayout();

2046 auto AddFactsAboutIndices = [&](Value *Ptr, Type *AccessType) {

2047 CmpPredicate Pred;

2048 Value *A, *B;

2049 if (getConstraintFromMemoryAccess(

2050 *cast<GetElementPtrInst>(Ptr),

2051 DL.getTypeStoreSize(AccessType).getFixedValue(), Pred, A, B, DL,

2052 TLI))

2053 AddFact(Pred, A, B);

2054 };

2055

2056 if (auto *LI = dyn_cast<LoadInst>(CB.Inst)) {

2057 AddFactsAboutIndices(LI->getPointerOperand(), LI->getAccessType());

2058 continue;

2059 }

2060 if (auto *SI = dyn_cast<StoreInst>(CB.Inst)) {

2061 AddFactsAboutIndices(SI->getPointerOperand(), SI->getAccessType());

2062 continue;

2063 }

2064 }

2065

2066 Value *A = nullptr, *B = nullptr;

2067 if (CB.isConditionFact()) {

2068 Pred = CB.Cond.Pred;

2069 A = CB.Cond.Op0;

2070 B = CB.Cond.Op1;

2071 if (CB.DoesHold.Pred != CmpInst::BAD_ICMP_PREDICATE &&

2072 !Info.doesHold(CB.DoesHold.Pred, CB.DoesHold.Op0, CB.DoesHold.Op1)) {

2073 LLVM_DEBUG({

2074 dbgs() << "Not adding fact ";

2075 dumpUnpackedICmp(dbgs(), Pred, A, B);

2076 dbgs() << " because precondition ";

2077 dumpUnpackedICmp(dbgs(), CB.DoesHold.Pred, CB.DoesHold.Op0,

2078 CB.DoesHold.Op1);

2079 dbgs() << " does not hold.\n";

2080 });

2081 continue;

2082 }

2083 } else {

2084 bool Matched = match(CB.Inst, m_Intrinsic<Intrinsic::assume>(

2085 m_ICmp(Pred, m_Value(A), m_Value(B))));

2086 (void)Matched;

2087 assert(Matched && "Must have an assume intrinsic with a icmp operand");

2088 }

2089 AddFact(Pred, A, B);

2090 }

2091

2092 if (ReproducerModule && !ReproducerModule->functions().empty()) {

2093 std::string S;

2094 raw_string_ostream StringS(S);

2095 ReproducerModule->print(StringS, nullptr);

2096 OptimizationRemark Rem(DEBUG_TYPE, "Reproducer", &F);

2097 Rem << ore::NV("module") << S;

2098 ORE.emit(Rem);

2099 }

2100

2101#ifndef NDEBUG

2102 unsigned SignedEntries =

2103 count_if(DFSInStack, [](const StackEntry &E) { return E.IsSigned; });

2104 assert(Info.getCS(false).size() - FunctionArgs.size() ==

2105 DFSInStack.size() - SignedEntries &&

2106 "updates to CS and DFSInStack are out of sync");

2107 assert(Info.getCS(true).size() == SignedEntries &&

2108 "updates to CS and DFSInStack are out of sync");

2109#endif

2110

2111 for (Instruction *I : ToRemove)

2112 I->eraseFromParent();

2113 return Changed;

2114}

2115

2116 PreservedAnalyses ConstraintEliminationPass::run(Function &F,

2117 FunctionAnalysisManager &AM) {

2118 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);

2119 auto &LI = AM.getResult<LoopAnalysis>(F);

2120 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);

2121 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);

2122 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);

2123 if (!eliminateConstraints(F, DT, LI, SE, ORE, TLI))

2124 return PreservedAnalyses::all();

2125

2126 PreservedAnalyses PA;

2127 PA.preserve<DominatorTreeAnalysis>();

2128 PA.preserve<LoopAnalysis>();

2129 PA.preserve<ScalarEvolutionAnalysis>();

2130 PA.preserveSet<CFGAnalyses>();

2131 return PA;

2132}

assert

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

ToRemove

ReachingDefInfo InstSet & ToRemove

Definition ARMLowOverheadLoops.cpp:527

DL

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Definition ARMSLSHardening.cpp:73

A

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

E

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

B

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

Info

Analysis containing CSE Info

Definition CSEInfo.cpp:27

ConditionTy

std::pair< ICmpInst *, unsigned > ConditionTy

Definition CallSiteSplitting.cpp:124

Cloning.h

CommandLine.h

MaxConstraintValue

static int64_t MaxConstraintValue

Definition ConstraintElimination.cpp:66

MinSignedConstraintValue

static int64_t MinSignedConstraintValue

Definition ConstraintElimination.cpp:67

getContextInstForUse

static Instruction * getContextInstForUse(Use &U)

Definition ConstraintElimination.cpp:69

decomposeGEP

static Decomposition decomposeGEP(GEPOperator &GEP, SmallVectorImpl< ConditionTy > &Preconditions, bool IsSigned, const DataLayout &DL)

Definition ConstraintElimination.cpp:456

canUseSExt

static bool canUseSExt(ConstantInt *CI)

Definition ConstraintElimination.cpp:451

dumpConstraint

static void dumpConstraint(ArrayRef< int64_t > C, const DenseMap< Value *, unsigned > &Value2Index)

Definition ConstraintElimination.cpp:957

removeEntryFromStack

static void removeEntryFromStack(const StackEntry &E, ConstraintInfo &Info, Module *ReproducerModule, SmallVectorImpl< ReproducerEntry > &ReproducerCondStack, SmallVectorImpl< StackEntry > &DFSInStack)

Definition ConstraintElimination.cpp:1650

checkCondition

static std::optional< bool > checkCondition(CmpInst::Predicate Pred, Value *A, Value *B, Instruction *CheckInst, ConstraintInfo &Info)

Definition ConstraintElimination.cpp:1497

MaxRows

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"))

DumpReproducers

static cl::opt< bool > DumpReproducers("constraint-elimination-dump-reproducers", cl::init(false), cl::Hidden, cl::desc("Dump IR to reproduce successful transformations."))

checkOrAndOpImpliedByOther

static bool checkOrAndOpImpliedByOther(FactOrCheck &CB, ConstraintInfo &Info, Module *ReproducerModule, SmallVectorImpl< ReproducerEntry > &ReproducerCondStack, SmallVectorImpl< StackEntry > &DFSInStack, SmallVectorImpl< Instruction * > &ToRemove)

Check if either the first condition of an AND or OR is implied by the (negated in case of OR) second ...

Definition ConstraintElimination.cpp:1667

eliminateConstraints

static bool eliminateConstraints(Function &F, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, OptimizationRemarkEmitter &ORE, TargetLibraryInfo &TLI)

Definition ConstraintElimination.cpp:1866

collectOffsets

static OffsetResult collectOffsets(GEPOperator &GEP, const DataLayout &DL)

Definition ConstraintElimination.cpp:417

checkAndReplaceMinMax

static bool checkAndReplaceMinMax(MinMaxIntrinsic *MinMax, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)

Definition ConstraintElimination.cpp:1607

generateReproducer

static void generateReproducer(CmpInst *Cond, Module *M, ArrayRef< ReproducerEntry > Stack, ConstraintInfo &Info, DominatorTree &DT)

Helper function to generate a reproducer function for simplifying Cond.

Definition ConstraintElimination.cpp:1369

checkAndReplaceCondition

static bool checkAndReplaceCondition(ICmpInst *Cmp, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut, Instruction *ContextInst, Module *ReproducerModule, ArrayRef< ReproducerEntry > ReproducerCondStack, DominatorTree &DT, SmallVectorImpl< Instruction * > &ToRemove)

Definition ConstraintElimination.cpp:1538

getConstraintFromMemoryAccess

static bool getConstraintFromMemoryAccess(GetElementPtrInst &GEP, uint64_t AccessSize, CmpPredicate &Pred, Value *&A, Value *&B, const DataLayout &DL, const TargetLibraryInfo &TLI)

Definition ConstraintElimination.cpp:1116

dumpUnpackedICmp

static void dumpUnpackedICmp(raw_ostream &OS, ICmpInst::Predicate Pred, Value *LHS, Value *RHS)

Definition ConstraintElimination.cpp:1338

decompose

static Decomposition decompose(Value *V, SmallVectorImpl< ConditionTy > &Preconditions, bool IsSigned, const DataLayout &DL)

Definition ConstraintElimination.cpp:495

replaceSubOverflowUses

static bool replaceSubOverflowUses(IntrinsicInst *II, Value *A, Value *B, SmallVectorImpl< Instruction * > &ToRemove)

Definition ConstraintElimination.cpp:1806

tryToSimplifyOverflowMath

static bool tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)

Definition ConstraintElimination.cpp:1839

checkAndReplaceCmp

static bool checkAndReplaceCmp(CmpIntrinsic *I, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)

Definition ConstraintElimination.cpp:1627

ConstraintElimination.h

ConstraintSystem.h

DataLayout.h

DebugCounter.h

This file provides an implementation of debug counters.

DEBUG_COUNTER

#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)

Definition DebugCounter.h:197

Dominators.h

DEBUG_TYPE

#define DEBUG_TYPE

Definition GenericCycleImpl.h:31

GlobalsModRef.h

This is the interface for a simple mod/ref and alias analysis over globals.

GEP

Hexagon Common GEP

Definition HexagonCommonGEP.cpp:164

IRBuilder.h

Function.h

Module.h

Module.h This file contains the declarations for the Module class.

InlinePriorityMode::Size

@ Size

Definition InlineOrder.cpp:25

InstrTypes.h

Instructions.h

TemplateParamKind::Type

@ Type

Definition ItaniumDemangle.h:1243

Ops

const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]

Definition ItaniumDemangle.h:3368

LoopInfo.h

F

#define F(x, y, z)

Definition MD5.cpp:55

I

#define I(x, y, z)

Definition MD5.cpp:58

Module

Machine Check Debug Module

Definition MachineCheckDebugify.cpp:124

MathExtras.h

MemoryBuiltins.h

II

uint64_t IntrinsicInst * II

Definition NVVMIntrRange.cpp:46

OptimizationRemarkEmitter.h

P

#define P(N)

if

if(PassOpts->AAPipeline)

Definition PassBuilderBindings.cpp:64

Pass.h

PatternMatch.h

getName

static StringRef getName(Value *V)

Definition ProvenanceAnalysisEvaluator.cpp:20

Cond

const SmallVectorImpl< MachineOperand > & Cond

Definition RISCVRedundantCopyElimination.cpp:71

isValid

static bool isValid(const char C)

Returns true if C is a valid mangled character: <0-9a-zA-Z_>.

Definition RustDemangle.cpp:181

STLExtras.h

This file contains some templates that are useful if you are working with the STL at all.

ScalarEvolutionExpressions.h

ScalarEvolution.h

ScopeExit.h

This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...

SmallVector.h

This file defines the SmallVector class.

Statistic.h

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

STATISTIC

#define STATISTIC(VARNAME, DESC)

Definition Statistic.h:171

Debug.h

LLVM_DEBUG

#define LLVM_DEBUG(...)

Definition Debug.h:114

X

static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")

Ptr

@ Ptr

Definition TargetLibraryInfo.cpp:77

RHS

Value * RHS

Definition X86PartialReduction.cpp:81

LHS

Value * LHS

Definition X86PartialReduction.cpp:80

FunctionType

Definition ItaniumDemangle.h:835

llvm::APInt

Class for arbitrary precision integers.

Definition APInt.h:78

llvm::APInt::sgt

bool sgt(const APInt &RHS) const

Signed greater than comparison.

Definition APInt.h:1202

llvm::APInt::isZero

bool isZero() const

Determine if this value is zero, i.e. all bits are clear.

Definition APInt.h:381

llvm::APInt::urem

LLVM_ABI APInt urem(const APInt &RHS) const

Unsigned remainder operation.

Definition APInt.cpp:1666

llvm::APInt::isNegative

bool isNegative() const

Determine sign of this APInt.

Definition APInt.h:330

llvm::APInt::getLimitedValue

uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const

If this value is smaller than the specified limit, return it, otherwise return the limit value.

Definition APInt.h:476

llvm::APInt::slt

bool slt(const APInt &RHS) const

Signed less than comparison.

Definition APInt.h:1131

llvm::APInt::isOne

bool isOne() const

Determine if this is a value of 1.

Definition APInt.h:390

llvm::AnalysisManager::getResult

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

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

Definition PassManager.h:412

llvm::ArrayRef

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

Definition ArrayRef.h:41

llvm::BasicBlock

LLVM Basic Block Representation.

Definition BasicBlock.h:62

llvm::BasicBlock::Create

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

Creates a new BasicBlock.

Definition BasicBlock.h:206

llvm::BasicBlock::getDataLayout

LLVM_ABI const DataLayout & getDataLayout() const

Get the data layout of the module this basic block belongs to.

Definition BasicBlock.cpp:252

llvm::BasicBlock::getTerminator

const Instruction * getTerminator() const LLVM_READONLY

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

Definition BasicBlock.h:233

llvm::CFGAnalyses

Represents analyses that only rely on functions' control flow.

Definition Analysis.h:73

llvm::CmpInst

This class is the base class for the comparison instructions.

Definition InstrTypes.h:664

llvm::CmpInst::makeCmpResultType

static Type * makeCmpResultType(Type *opnd_type)

Create a result type for fcmp/icmp.

Definition InstrTypes.h:982

llvm::CmpInst::isEquality

bool isEquality() const

Determine if this is an equals/not equals predicate.

Definition InstrTypes.h:915

llvm::CmpInst::Predicate

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

Definition InstrTypes.h:676

llvm::CmpInst::BAD_ICMP_PREDICATE

@ BAD_ICMP_PREDICATE

Definition InstrTypes.h:709

llvm::CmpInst::ICMP_SLT

@ ICMP_SLT

signed less than

Definition InstrTypes.h:705

llvm::CmpInst::ICMP_SLE

@ ICMP_SLE

signed less or equal

Definition InstrTypes.h:706

llvm::CmpInst::ICMP_UGE

@ ICMP_UGE

unsigned greater or equal

Definition InstrTypes.h:700

llvm::CmpInst::ICMP_UGT

@ ICMP_UGT

unsigned greater than

Definition InstrTypes.h:699

llvm::CmpInst::ICMP_SGT

@ ICMP_SGT

signed greater than

Definition InstrTypes.h:703

llvm::CmpInst::ICMP_ULT

@ ICMP_ULT

unsigned less than

Definition InstrTypes.h:701

llvm::CmpInst::ICMP_EQ

@ ICMP_EQ

equal

Definition InstrTypes.h:697

llvm::CmpInst::ICMP_NE

@ ICMP_NE

not equal

Definition InstrTypes.h:698

llvm::CmpInst::ICMP_SGE

@ ICMP_SGE

signed greater or equal

Definition InstrTypes.h:704

llvm::CmpInst::ICMP_ULE

@ ICMP_ULE

unsigned less or equal

Definition InstrTypes.h:702

llvm::CmpInst::isSigned

bool isSigned() const

Definition InstrTypes.h:930

llvm::CmpInst::getSwappedPredicate

Predicate getSwappedPredicate() const

For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.

Definition InstrTypes.h:827

llvm::CmpInst::getNonStrictPredicate

Predicate getNonStrictPredicate() const

For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.

Definition InstrTypes.h:871

llvm::CmpInst::getInversePredicate

Predicate getInversePredicate() const

For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...

Definition InstrTypes.h:789

llvm::CmpInst::getPredicate

Predicate getPredicate() const

Return the predicate for this instruction.

Definition InstrTypes.h:765

llvm::CmpIntrinsic

This class represents a ucmp/scmp intrinsic.

Definition IntrinsicInst.h:875

llvm::CmpPredicate

An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...

Definition CmpPredicate.h:23

llvm::CmpPredicate::hasSameSign

bool hasSameSign() const

Query samesign information, for optimizations.

Definition CmpPredicate.h:43

llvm::ConstantInt

This is the shared class of boolean and integer constants.

Definition Constants.h:87

llvm::ConstantInt::isNegative

bool isNegative() const

Definition Constants.h:209

llvm::ConstantInt::getSigned

static ConstantInt * getSigned(IntegerType *Ty, int64_t V)

Return a ConstantInt with the specified value for the specified type.

Definition Constants.h:131

llvm::ConstantInt::getSExtValue

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:169

llvm::ConstantInt::getValue

const APInt & getValue() const

Return the constant as an APInt value reference.

Definition Constants.h:154

llvm::ConstantInt::getBool

static LLVM_ABI ConstantInt * getBool(LLVMContext &Context, bool V)

Definition Constants.cpp:885

llvm::Constant

This is an important base class in LLVM.

Definition Constant.h:43

llvm::Constant::getAllOnesValue

static LLVM_ABI Constant * getAllOnesValue(Type *Ty)

Definition Constants.cpp:420

llvm::Constant::getNullValue

static LLVM_ABI Constant * getNullValue(Type *Ty)

Constructor to create a '0' constant of arbitrary type.

Definition Constants.cpp:373

llvm::ConstraintEliminationPass::run

PreservedAnalyses run(Function &F, FunctionAnalysisManager &)

Definition ConstraintElimination.cpp:2116

llvm::ConstraintSystem

Definition ConstraintSystem.h:23

llvm::ConstraintSystem::negate

static SmallVector< int64_t, 8 > negate(SmallVector< int64_t, 8 > R)

Definition ConstraintSystem.h:114

llvm::ConstraintSystem::isConditionImplied

LLVM_ABI bool isConditionImplied(SmallVector< int64_t, 8 > R) const

Definition ConstraintSystem.cpp:215

llvm::ConstraintSystem::toStrictLessThan

static SmallVector< int64_t, 8 > toStrictLessThan(SmallVector< int64_t, 8 > R)

Converts the given vector to form a strict less than inequality.

Definition ConstraintSystem.h:139

llvm::ConstraintSystem::negateOrEqual

static SmallVector< int64_t, 8 > negateOrEqual(SmallVector< int64_t, 8 > R)

Multiplies each coefficient in the given vector by -1.

Definition ConstraintSystem.h:127

llvm::ConstraintSystem::addVariableRowFill

bool addVariableRowFill(ArrayRef< int64_t > R)

Definition ConstraintSystem.h:101

llvm::ConstraintSystem::dump

LLVM_ABI void dump() const

Print the constraints in the system.

Definition ConstraintSystem.cpp:180

llvm::DataLayout

A parsed version of the target data layout string in and methods for querying it.

Definition DataLayout.h:63

llvm::DebugCounter::shouldExecute

static bool shouldExecute(unsigned CounterName)

Definition DebugCounter.h:88

llvm::DenseMapBase::erase

bool erase(const KeyT &Val)

Definition DenseMap.h:322

llvm::DenseMapBase::contains

bool contains(const_arg_type_t< KeyT > Val) const

Return true if the specified key is in the map, false otherwise.

Definition DenseMap.h:169

llvm::DenseMapBase::insert

std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)

Definition DenseMap.h:233

llvm::DenseMap

Definition DenseMap.h:713

llvm::DomTreeNodeBase::getDFSNumIn

unsigned getDFSNumIn() const

getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.

Definition GenericDomTree.h:140

llvm::DomTreeNodeBase::getDFSNumOut

unsigned getDFSNumOut() const

Definition GenericDomTree.h:141

llvm::DominatorTreeAnalysis

Analysis pass which computes a DominatorTree.

Definition Dominators.h:284

llvm::DominatorTreeBase::updateDFSNumbers

void updateDFSNumbers() const

updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.

Definition GenericDomTree.h:805

llvm::DominatorTreeBase::getNode

DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const

getNode - return the (Post)DominatorTree node for the specified basic block.

Definition GenericDomTree.h:401

llvm::DominatorTree

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

Definition Dominators.h:165

llvm::DominatorTree::dominates

LLVM_ABI 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:135

llvm::FunctionType::get

static LLVM_ABI FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)

This static method is the primary way of constructing a FunctionType.

llvm::Function

Definition Function.h:64

llvm::Function::Create

static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)

Definition Function.h:166

llvm::GEPNoWrapFlags::none

static GEPNoWrapFlags none()

Definition GEPNoWrapFlags.h:46

llvm::GEPOperator

Definition Operator.h:420

llvm::GetElementPtrInst

an instruction for type-safe pointer arithmetic to access elements of arrays and structs

Definition Instructions.h:950

llvm::GlobalValue::ExternalLinkage

@ ExternalLinkage

Externally visible function.

Definition GlobalValue.h:53

llvm::ICmpInst

This instruction compares its operands according to the predicate given to the constructor.

Definition Instructions.h:1178

llvm::ICmpInst::getFlippedSignednessPredicate

Predicate getFlippedSignednessPredicate() const

For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->EQ.

Definition Instructions.h:1297

llvm::ICmpInst::getSignedPredicate

Predicate getSignedPredicate() const

For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.

Definition Instructions.h:1270

llvm::ICmpInst::isRelational

bool isRelational() const

Return true if the predicate is relational (not EQ or NE).

Definition Instructions.h:1337

llvm::ICmpInst::getUnsignedPredicate

Predicate getUnsignedPredicate() const

For example, EQ->EQ, SLE->ULE, UGT->UGT, etc.

Definition Instructions.h:1281

llvm::IRBuilder

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

Definition IRBuilder.h:2788

llvm::Instruction

Definition Instruction.h:69

llvm::Instruction::insertBefore

LLVM_ABI void insertBefore(InstListType::iterator InsertPos)

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

Definition Instruction.cpp:119

llvm::Instruction::dropUnknownNonDebugMetadata

LLVM_ABI void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs={})

Drop all unknown metadata except for debug locations.

Definition Metadata.cpp:1701

llvm::Instruction::setDebugLoc

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

Definition Instruction.h:510

llvm::IntrinsicInst

A wrapper class for inspecting calls to intrinsic functions.

Definition IntrinsicInst.h:49

llvm::LLVMContext

This is an important class for using LLVM in a threaded context.

Definition LLVMContext.h:68

llvm::LoopAnalysis

Analysis pass that exposes the LoopInfo for a function.

Definition LoopInfo.h:569

llvm::LoopInfoBase::getLoopFor

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

Definition GenericLoopInfo.h:606

llvm::LoopInfo

Definition LoopInfo.h:408

llvm::MapVector::size

size_type size() const

Definition MapVector.h:56

llvm::MinMaxIntrinsic

This class represents min/max intrinsics.

Definition IntrinsicInst.h:764

llvm::Module

A Module instance is used to store all the information related to an LLVM module.

Definition Module.h:67

llvm::OptimizationRemarkEmitterAnalysis

Definition OptimizationRemarkEmitter.h:168

llvm::OptimizationRemarkEmitter

The optimization diagnostic interface.

Definition OptimizationRemarkEmitter.h:33

llvm::PHINode::getIncomingValueForBlock

Value * getIncomingValueForBlock(const BasicBlock *BB) const

Definition Instructions.h:2815

llvm::PHINode::getNumIncomingValues

unsigned getNumIncomingValues() const

Return the number of incoming edges.

Definition Instructions.h:2710

llvm::PoisonValue::get

static LLVM_ABI PoisonValue * get(Type *T)

Static factory methods - Return an 'poison' object of the specified type.

Definition Constants.cpp:1888

llvm::PreservedAnalyses

A set of analyses that are preserved following a run of a transformation pass.

Definition Analysis.h:112

llvm::PreservedAnalyses::all

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

Definition Analysis.h:118

llvm::PreservedAnalyses::preserveSet

PreservedAnalyses & preserveSet()

Mark an analysis set as preserved.

Definition Analysis.h:151

llvm::PreservedAnalyses::preserve

PreservedAnalyses & preserve()

Mark an analysis as preserved.

Definition Analysis.h:132

llvm::ScalarEvolutionAnalysis

Analysis pass that exposes the ScalarEvolution for a function.

Definition ScalarEvolution.h:2367

llvm::ScalarEvolution

The main scalar evolution driver.

Definition ScalarEvolution.h:448

llvm::ScalarEvolution::getSCEV

LLVM_ABI const SCEV * getSCEV(Value *V)

Return a SCEV expression for the full generality of the specified expression.

Definition ScalarEvolution.cpp:4587

llvm::ScalarEvolution::isSCEVable

LLVM_ABI bool isSCEVable(Type *Ty) const

Test if values of the given type are analyzable within the SCEV framework.

Definition ScalarEvolution.cpp:4481

llvm::ScalarEvolution::MonotonicallyIncreasing

@ MonotonicallyIncreasing

Definition ScalarEvolution.h:1217

llvm::ScalarEvolution::getMinusSCEV

LLVM_ABI const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)

Return LHS-RHS.

Definition ScalarEvolution.cpp:4689

llvm::ScalarEvolution::getConstantMultiple

LLVM_ABI APInt getConstantMultiple(const SCEV *S, const Instruction *CtxI=nullptr)

Returns the max constant multiple of S.

Definition ScalarEvolution.cpp:6433

llvm::ScalarEvolution::getMonotonicPredicateType

LLVM_ABI std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)

If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...

Definition ScalarEvolution.cpp:11229

llvm::SmallPtrSetImpl::insert

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:389

llvm::SmallPtrSet

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

Definition SmallPtrSet.h:527

llvm::SmallVectorImpl

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

Definition SmallVector.h:574

llvm::SmallVectorImpl::pop_back_val

T pop_back_val()

Definition SmallVector.h:674

llvm::SmallVectorImpl::emplace_back

reference emplace_back(ArgTypes &&... Args)

Definition SmallVector.h:944

llvm::SmallVectorTemplateBase::pop_back

void pop_back()

Definition SmallVector.h:429

llvm::SmallVectorTemplateBase::push_back

void push_back(const T &Elt)

Definition SmallVector.h:417

llvm::SmallVectorTemplateCommon::size

size_t size() const

Definition SmallVector.h:80

llvm::SmallVectorTemplateCommon::back

reference back()

Definition SmallVector.h:312

llvm::SmallVectorTemplateCommon::empty

bool empty() const

Definition SmallVector.h:83

llvm::SmallVector

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

Definition SmallVector.h:1203

llvm::TargetLibraryAnalysis

Analysis pass providing the TargetLibraryInfo.

Definition TargetLibraryInfo.h:625

llvm::TargetLibraryInfo

Provides information about what library functions are available for the current target.

Definition TargetLibraryInfo.h:285

llvm::Type

The instances of the Type class are immutable: once they are created, they are never changed.

Definition Type.h:45

llvm::Type::getScalarType

Type * getScalarType() const

If this is a vector type, return the element type, otherwise return 'this'.

Definition Type.h:352

llvm::Type::getScalarSizeInBits

LLVM_ABI unsigned getScalarSizeInBits() const LLVM_READONLY

If this is a vector type, return the getPrimitiveSizeInBits value for the element type.

Definition Type.cpp:231

llvm::Use

A Use represents the edge between a Value definition and its users.

Definition Use.h:35

llvm::User

Definition User.h:44

llvm::User::getOperand

Value * getOperand(unsigned i) const

Definition User.h:232

llvm::ValueMap::find

iterator find(const KeyT &Val)

Definition ValueMap.h:160

llvm::ValueMap::end

iterator end()

Definition ValueMap.h:139

llvm::Value

LLVM Value Representation.

Definition Value.h:75

llvm::Value::getType

Type * getType() const

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

Definition Value.h:256

llvm::Value::replaceAllUsesWith

LLVM_ABI void replaceAllUsesWith(Value *V)

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

Definition Value.cpp:546

llvm::Value::stripPointerCastsSameRepresentation

LLVM_ABI const Value * stripPointerCastsSameRepresentation() const

Strip off pointer casts, all-zero GEPs and address space casts but ensures the representation of the ...

Definition Value.cpp:709

llvm::Value::use_empty

bool use_empty() const

Definition Value.h:346

llvm::cl::opt

Definition CommandLine.h:1455

llvm::details::FixedOrScalableQuantity::getFixedValue

constexpr ScalarTy getFixedValue() const

Definition TypeSize.h:201

llvm::details::FixedOrScalableQuantity::isFixed

constexpr bool isFixed() const

Returns true if the quantity is not scaled by vscale.

Definition TypeSize.h:172

llvm::ilist_detail::node_parent_access::getParent

const ParentTy * getParent() const

Definition ilist_node.h:34

llvm::raw_ostream

This class implements an extremely fast bulk output stream that can only output to a stream.

Definition raw_ostream.h:53

uint64_t

Changed

Definition ObjCARCOpts.cpp:2369

DebugInfo.h

llvm_unreachable

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

Definition ErrorHandling.h:164

llvm::ARM_AM::sub

@ sub

Definition ARMAddressingModes.h:38

llvm::ARM_AM::add

@ add

Definition ARMAddressingModes.h:39

llvm::CallingConv::ID

unsigned ID

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

Definition CallingConv.h:24

llvm::CallingConv::C

@ C

The default llvm calling convention, compatible with C.

Definition CallingConv.h:34

llvm::ISD::BasicBlock

@ BasicBlock

Various leaf nodes.

Definition ISDOpcodes.h:81

llvm::ISD::Constant

@ Constant

Definition ISDOpcodes.h:86

llvm::Intrinsic::not_intrinsic

@ not_intrinsic

Definition Intrinsics.h:46

llvm::Intrinsic::ID

unsigned ID

Definition GenericSSAContext.h:28

llvm::JumpTable::Simplified

@ Simplified

Definition TargetOptions.h:41

llvm::M68k::MemAddrModeKind::U

@ U

Definition M68kBaseInfo.h:61

llvm::M68k::MemAddrModeKind::V

@ V

Definition M68kBaseInfo.h:63

llvm::M68k::MemAddrModeKind::L

@ L

Definition M68kBaseInfo.h:70

llvm::PatternMatch

Definition PatternMatch.h:47

llvm::PatternMatch::m_Add

BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)

Definition PatternMatch.h:1194

llvm::PatternMatch::m_NUWAdd

OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)

Definition PatternMatch.h:1453

llvm::PatternMatch::m_LogicalOp

auto m_LogicalOp()

Matches either L && R or L || R where L and R are arbitrary values.

Definition PatternMatch.h:3295

llvm::PatternMatch::m_NSWSub

OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWSub(const LHS &L, const RHS &R)

Definition PatternMatch.h:1428

llvm::PatternMatch::match

bool match(Val *V, const Pattern &P)

Definition PatternMatch.h:49

llvm::PatternMatch::m_DisjointOr

DisjointOr_match< LHS, RHS > m_DisjointOr(const LHS &L, const RHS &R)

Definition PatternMatch.h:1534

llvm::PatternMatch::m_ConstantInt

class_match< ConstantInt > m_ConstantInt()

Match an arbitrary ConstantInt and ignore it.

Definition PatternMatch.h:181

llvm::PatternMatch::m_Intrinsic

IntrinsicID_match m_Intrinsic()

Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))

Definition PatternMatch.h:2796

llvm::PatternMatch::m_ExtractValue

ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)

Match a single index ExtractValue instruction.

Definition PatternMatch.h:3153

llvm::PatternMatch::m_NSWTrunc

NoWrapTrunc_match< OpTy, TruncInst::NoSignedWrap > m_NSWTrunc(const OpTy &Op)

Matches trunc nsw.

Definition PatternMatch.h:2249

llvm::PatternMatch::m_NNegZExt

NNegZExt_match< OpTy > m_NNegZExt(const OpTy &Op)

Definition PatternMatch.h:2272

llvm::PatternMatch::m_LogicalOr

auto m_LogicalOr()

Matches L || R where L and R are arbitrary values.

Definition PatternMatch.h:3275

llvm::PatternMatch::m_NSWShl

OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoSignedWrap > m_NSWShl(const LHS &L, const RHS &R)

Definition PatternMatch.h:1444

llvm::PatternMatch::m_ZExt

CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)

Matches ZExt.

Definition PatternMatch.h:2267

llvm::PatternMatch::m_NUWShl

OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWShl(const LHS &L, const RHS &R)

Definition PatternMatch.h:1487

llvm::PatternMatch::m_NUWMul

OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWMul(const LHS &L, const RHS &R)

Definition PatternMatch.h:1479

llvm::PatternMatch::m_Br

brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)

Definition PatternMatch.h:2388

llvm::PatternMatch::m_NUWSub

OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWSub(const LHS &L, const RHS &R)

Definition PatternMatch.h:1471

llvm::PatternMatch::m_Value

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

Definition PatternMatch.h:105

llvm::PatternMatch::m_NSWAdd

OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)

Definition PatternMatch.h:1412

llvm::PatternMatch::m_ICmp

CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)

Definition PatternMatch.h:1766

llvm::PatternMatch::m_LogicalAnd

auto m_LogicalAnd()

Matches L && R where L and R are arbitrary values.

Definition PatternMatch.h:3257

llvm::PatternMatch::m_SExt

CastInst_match< OpTy, SExtInst > m_SExt(const OpTy &Op)

Matches SExt.

Definition PatternMatch.h:2261

llvm::PatternMatch::m_Zero

is_zero m_Zero()

Match any null constant or a vector with all elements equal to 0.

Definition PatternMatch.h:624

llvm::PatternMatch::m_NSWMul

OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap > m_NSWMul(const LHS &L, const RHS &R)

Definition PatternMatch.h:1436

llvm::RISCVFenceField::R

@ R

Definition RISCVBaseInfo.h:462

llvm::SIEncodingFamily::SI

@ SI

Definition SIDefines.h:36

llvm::X86::FirstMacroFusionInstKind::Cmp

@ Cmp

Definition X86BaseInfo.h:109

llvm::cfg::UpdateKind::Insert

@ Insert

Definition CFGUpdate.h:26

llvm::cl::Hidden

@ Hidden

Definition CommandLine.h:139

llvm::cl::init

initializer< Ty > init(const Ty &Val)

Definition CommandLine.h:445

llvm::codeview::EncodedFramePtrReg::BasePtr

@ BasePtr

Definition CodeView.h:528

llvm::coro::ABI::Switch

@ Switch

The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...

Definition CoroShape.h:31

llvm::logicalview::LVComparePass::Added

@ Added

Definition LVObject.h:100

llvm::ore::NV

DiagnosticInfoOptimizationBase::Argument NV

Definition OptimizationRemarkEmitter.h:139

llvm::rdf::Use

NodeAddr< UseNode * > Use

Definition RDFGraph.h:385

llvm::sandboxir::empty

bool empty() const

Definition BasicBlock.h:101

llvm::sandboxir::Instruction

friend class Instruction

Iterator for Instructions in a `BasicBlock.

Definition BasicBlock.h:73

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition AddressRanges.h:18

llvm::Offset

@ Offset

Definition DWP.cpp:477

llvm::Value

FunctionAddr VTableAddr Value

Definition InstrProf.h:137

llvm::MulOverflow

std::enable_if_t< std::is_signed_v< T >, 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:753

llvm::stable_sort

void stable_sort(R &&Range)

Definition STLExtras.h:2058

llvm::all_of

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:1725

llvm::size

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:1655

llvm::make_scope_exit

detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)

Definition ScopeExit.h:59

llvm::Successor

@ Successor

Definition SIMachineScheduler.h:35

llvm::dyn_cast

decltype(auto) dyn_cast(const From &Val)

dyn_cast<X> - Return the argument parameter cast to the specified type.

Definition Casting.h:643

llvm::verifyFunction

LLVM_ABI bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)

Check a function for errors, useful for use when debugging a pass.

Definition Verifier.cpp:7603

llvm::append_range

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

Definition STLExtras.h:2136

llvm::make_early_inc_range

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:632

llvm::getBaseObjectSize

LLVM_ABI std::optional< TypeSize > getBaseObjectSize(const Value *Ptr, const DataLayout &DL, const TargetLibraryInfo *TLI, ObjectSizeOpts Opts={})

Like getObjectSize(), but only returns the size of base objects (like allocas, global variables and a...

Definition MemoryBuiltins.cpp:592

llvm::concat

detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&...Ranges)

Returns a concatenated range across two or more ranges.

Definition STLExtras.h:1150

llvm::getPointerOperand

const Value * getPointerOperand(const Value *V)

A helper function that returns the pointer operand of a load, store or GEP instruction.

Definition Instructions.h:5106

llvm::DomTreeNode

DomTreeNodeBase< BasicBlock > DomTreeNode

Definition Dominators.h:95

llvm::dyn_cast_or_null

auto dyn_cast_or_null(const Y &Val)

Definition Casting.h:753

llvm::MaxAnalysisRecursionDepth

constexpr unsigned MaxAnalysisRecursionDepth

Definition ValueTracking.h:47

llvm::sort

void sort(IteratorTy Start, IteratorTy End)

Definition STLExtras.h:1622

llvm::dbgs

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

Definition Debug.cpp:207

llvm::SmallVector

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

Definition SmallVector.h:1129

llvm::isa

bool isa(const From &Val)

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

Definition Casting.h:547

llvm::IRMemLocation::Other

@ Other

Any other memory.

Definition ModRef.h:68

llvm::LEB128Sign::Signed

@ Signed

Definition LEB128.h:232

llvm::RecurKind::Sub

@ Sub

Subtraction of integers.

Definition IVDescriptors.h:38

llvm::remapInstructionsInBlocks

LLVM_ABI void remapInstructionsInBlocks(ArrayRef< BasicBlock * > Blocks, ValueToValueMapTy &VMap)

Remaps instructions in Blocks using the mapping in VMap.

Definition CloneFunction.cpp:992

llvm::ArrayRef

ArrayRef(const T &OneElt) -> ArrayRef< T >

llvm::BitWidth

constexpr unsigned BitWidth

Definition BitmaskEnum.h:220

llvm::ValueToValueMapTy

ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy

Definition MemorySSAUpdater.h:51

llvm::move

OutputIt move(R &&Range, OutputIt Out)

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

Definition STLExtras.h:1867

llvm::isGuaranteedToTransferExecutionToSuccessor

LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)

Return true if this function can prove that the instruction I will always transfer execution to one o...

Definition ValueTracking.cpp:7783

llvm::PseudoProbeReservedId::Last

@ Last

Definition PseudoProbe.h:28

llvm::count_if

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:1961

llvm::cast

decltype(auto) cast(const From &Val)

cast<X> - Return the argument parameter cast to the specified type.

Definition Casting.h:559

llvm::make_pointer_range

iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)

Definition iterator.h:363

llvm::AddOverflow

std::enable_if_t< std::is_signed_v< T >, 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:701

llvm::FunctionAnalysisManager

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

Definition PassManager.h:564

llvm::SubOverflow

std::enable_if_t< std::is_signed_v< T >, T > SubOverflow(T X, T Y, T &Result)

Subtract two signed integers, computing the two's complement truncated result, returning true if an o...

Definition MathExtras.h:727

llvm::isGuaranteedNotToBePoison

LLVM_ABI bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)

Returns true if V cannot be poison, but may be undef.

Definition ValueTracking.cpp:7712

llvm::isKnownNonNegative

LLVM_ABI bool isKnownNonNegative(const Value *V, const SimplifyQuery &SQ, unsigned Depth=0)

Returns true if the give value is known to be non-negative.

Definition ValueTracking.cpp:281

llvm::findDbgUsers

LLVM_ABI void findDbgUsers(Value *V, SmallVectorImpl< DbgVariableRecord * > &DbgVariableRecords)

Finds the debug info records describing a value.

Definition DebugInfo.cpp:130

std::swap

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)