ConstraintElimination.cpp Source File (original) (raw)

46#include

47#include

49using namespace llvm;

52#define DEBUG_TYPE "constraint-elimination"

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

56 "Controls which conditions are eliminated");

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

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

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

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

73 return UserI;

74}

76namespace {

78struct ConditionTy {

79 CmpPredicate Pred;

80 Value *Op0 = nullptr;

81 Value *Op1 = nullptr;

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

86};

93struct FactOrCheck {

94 enum class EntryTy {

95 ConditionFact,

96 InstFact,

98 InstCheck,

100 UseCheck

101 };

102

103 union {

107 };

108

109

110

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

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

123 Ty(EntryTy::UseCheck) {}

124

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,

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

153 assert(!isConditionFact());

154 if (Ty == EntryTy::UseCheck)

156 return Inst;

157 }

158

159 Instruction *getInstructionToSimplify() const {

161 if (Ty == EntryTy::InstCheck)

162 return Inst;

163

165 }

166

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

168};

169

170

171struct State {

172 DominatorTree &DT;

173 LoopInfo &LI;

174 ScalarEvolution &SE;

175 TargetLibraryInfo &TLI;

177

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

179 TargetLibraryInfo &TLI)

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

181

182

183 void addInfoFor(BasicBlock &BB);

184

185

186

187 void addInfoForInductions(BasicBlock &BB);

188

189

190

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

203

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 {

214 SmallVector<ConditionTy, 2> Preconditions;

215

217

218 bool IsSigned = false;

219

220 ConstraintTy() = default;

221

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

232

233 bool isValid(const ConstraintInfo &Info) const;

234

235 bool isEq() const { return IsEq; }

236

237 bool isNe() const { return IsNe; }

238

239

240

241

242

243

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

245

246private:

247 bool IsEq = false;

248 bool IsNe = false;

249};

250

251

252

253

254

255

256

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

269 for (Value *Arg : FunctionArgs) {

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

297

299 unsigned NumOut, SmallVectorImpl &DFSInStack);

300

301

302

303

304

306 SmallVectorImpl<Value *> &NewVariables,

307 bool ForceSignedSystem = false) const;

308

309

310

311

312

313

314

315

317 Value *Op1) const;

318

319

320

322 unsigned NumIn, unsigned NumOut,

323 SmallVectorImpl &DFSInStack);

324

325private:

326

327

328

330 unsigned NumOut, SmallVectorImpl &DFSInStack,

331 bool ForceSignedSystem);

332};

333

334

335struct DecompEntry {

336 int64_t Coefficient;

338

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

348struct Decomposition {

349 int64_t Offset = 0;

351

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

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

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

355 }

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

358

359

360

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

362 return AddOverflow(Offset, OtherOffset, Offset);

363 }

364

365

366

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

369 return true;

371 return false;

372 }

373

374

375

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;

383 return false;

384 }

385

386

387

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

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

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)

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

410 }

411};

412}

413

414

415

416

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

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

421 Result.ConstantOffset))

422 return {};

423

424

425

429 bool CanCollectInner = InnerGEP->collectOffset(

430 DL, BitWidth, VariableOffsets2, ConstantOffset2);

431

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

433 VariableOffsets2.size() > 1 ||

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

435

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

450

455

459

460

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] =

468

469

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

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

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

487 }

488 }

489 return Result;

490}

491

492

493

494

498

499 auto MergeResults = [&Preconditions, IsSigned,

501 bool IsSignedB) -> std::optional {

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

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

514 return int64_t(0);

515

516 return V;

517 }

518

519

520

521

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

523 return V;

524

525 bool IsKnownNonNegative = false;

526

527

528 if (IsSigned) {

531 return CI->getSExtValue();

532 }

535

537 V = Op0;

539 V = Op0;

540 IsKnownNonNegative = true;

543 V = Op0;

544 }

545

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

548 return *Decomp;

549 return {V, IsKnownNonNegative};

550 }

551

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

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

564 return Result;

565 return {V, IsKnownNonNegative};

566 }

567

568

569

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

586 return V;

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

588 }

589

592 IsKnownNonNegative = true;

593 V = Op0;

595 V = Op0;

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

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

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

601 V = Trunc->getOperand(0);

602 if (!Trunc->hasNoUnsignedWrap())

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

605 }

606 }

607 }

608

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

613 return *Decomp;

614 return {V, IsKnownNonNegative};

615 }

616

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

623 return *Decomp;

624 return {V, IsKnownNonNegative};

625 }

626

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

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

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

643 return *Decomp;

644 return {V, IsKnownNonNegative};

645 }

646

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

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

660 return Result;

661 return {V, IsKnownNonNegative};

662 }

663

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

678 bool ForceSignedSystem) const {

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

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

682

683 bool IsEq = false;

684 bool IsNe = false;

685

686

687 switch (Pred) {

694 break;

695 }

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

699 } else {

700 IsEq = true;

702 }

703 break;

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

708 } else {

709 IsNe = true;

711 }

712 break;

713 default:

714 break;

715 }

716

719 return {};

720

723 auto &Value2Index = getValue2Index(IsSigned);

725 Preconditions, IsSigned, DL);

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

736

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;

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

746 NewVariables.push_back(V);

747 return Insert.first->second;

748 };

749

750

752 GetOrAddIndex(KV.Variable);

753

754

755

756 ConstraintTy Res(

758 IsSigned, IsEq, IsNe);

759

760

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 {};

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

784 return {};

785 R[0] = OffsetSum;

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

787

788

789

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

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,

813 Value *Op1) const {

815

816

819 auto &Value2Index = getValue2Index(false);

820

822 false, false);

823 }

824

825

826

827

832

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 &&

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

844 });

845}

846

847std::optional

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

850

851 if (IsEq || IsNe) {

853 bool IsNegatedOrEqualImplied =

855

856

857

858

859 if (IsConditionImplied && IsNegatedOrEqualImplied)

860 return IsEq;

861

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

864

866 bool IsStrictLessThanImplied =

868

869

870

871

872

873 if (IsNegatedImplied || IsStrictLessThanImplied)

874 return IsNe;

875

876 return std::nullopt;

877 }

878

879 if (IsConditionImplied)

880 return true;

881

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

884 if (IsNegatedImplied)

885 return false;

886

887

888 return std::nullopt;

889}

890

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

894 return R.isValid(*this) &&

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

896}

897

898void ConstraintInfo::transferToOtherSystem(

900 unsigned NumOut, SmallVectorImpl &DFSInStack) {

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

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

904 };

905

906

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

908 return;

909

910

911

912 switch (Pred) {

913 default:

914 break;

917

918 if (IsKnownNonNegative(B)) {

920 NumOut, DFSInStack);

922 DFSInStack);

923 }

924 break;

927

928 if (IsKnownNonNegative(A)) {

930 NumOut, DFSInStack);

932 DFSInStack);

933 }

934 break;

936 if (IsKnownNonNegative(A))

938 break;

942 NumOut, DFSInStack);

943 if (IsKnownNonNegative(B))

945

946 break;

947 }

949 if (IsKnownNonNegative(B))

951 break;

952 }

953}

954

955#ifndef NDEBUG

956

963#endif

964

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

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

968 return;

969

972 CmpPredicate Pred;

973

976 return;

978 if (!PN) {

982 }

983

986 return;

987

993 else

994 return;

995

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

997 return;

998

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;

1007 StartValue = C->getValue();

1008 } else {

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

1011 }

1012

1016 bool MonotonicallyIncreasingUnsigned =

1018 bool MonotonicallyIncreasingSigned =

1020

1021

1022 if (MonotonicallyIncreasingUnsigned)

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

1025 if (MonotonicallyIncreasingSigned)

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

1028

1029 APInt StepOffset;

1031 StepOffset = C->getAPInt();

1032 else

1033 return;

1034

1035

1036 if (->isLoopInvariant(B))

1037 return;

1038

1039

1041

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

1043 return;

1044

1045

1046

1047

1048 WorkList.push_back(FactOrCheck::getConditionFact(

1051 WorkList.push_back(FactOrCheck::getConditionFact(

1054

1055

1056 WorkList.push_back(FactOrCheck::getConditionFact(

1059 WorkList.push_back(FactOrCheck::getConditionFact(

1062 return;

1063 }

1064

1065

1066

1067

1069 return;

1070

1071 if (!StepOffset.isOne()) {

1072

1076 return;

1077 }

1078

1079

1080

1081

1082 if (!MonotonicallyIncreasingUnsigned)

1083 WorkList.push_back(FactOrCheck::getConditionFact(

1086 if (!MonotonicallyIncreasingSigned)

1087 WorkList.push_back(FactOrCheck::getConditionFact(

1090

1091 WorkList.push_back(FactOrCheck::getConditionFact(

1094 WorkList.push_back(FactOrCheck::getConditionFact(

1097

1098

1099

1100

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

1103 "unsupported predicate");

1106 L->getExitBlocks(ExitBBs);

1107 for (BasicBlock *EB : ExitBBs) {

1108

1110 WorkList.emplace_back(FactOrCheck::getConditionFact(

1112 }

1113 }

1114}

1115

1122 if ( Offset .NW.hasNoUnsignedWrap())

1123 return false;

1124

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

1126 return false;

1127

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

1130

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

1132 return false;

1133

1135

1137

1138

1140 std::optional Size =

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

1143 return false;

1144

1145

1146

1147

1148

1150 false, true) -

1151 Offset.ConstantOffset)

1152 .udiv(Scale);

1154 A = Index;

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

1156 return true;

1157}

1158

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

1160 addInfoForInductions(BB);

1162

1163

1164 bool GuaranteedToExecute = true;

1165

1166 for (Instruction &I : BB) {

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

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) {

1180 if ( GEP )

1181 return;

1182 TypeSize AccessSize = DL.getTypeStoreSize(AccessType);

1183 if (!AccessSize.isFixed())

1184 return;

1185 if (GuaranteedToExecute) {

1186 CmpPredicate Pred;

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

1190

1191

1192 WorkList.emplace_back(FactOrCheck::getConditionFact(

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

1194 }

1195 } else {

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

1198 }

1199 };

1200

1202 if (!LI->isVolatile())

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

1204 }

1206 if (->isVolatile())

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

1208 }

1209

1212 switch (ID) {

1213 case Intrinsic::assume: {

1215 CmpPredicate Pred;

1217 break;

1218 if (GuaranteedToExecute) {

1219

1220

1221 WorkList.emplace_back(FactOrCheck::getConditionFact(

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

1223 } else {

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

1226 }

1227 break;

1228 }

1229

1230 case Intrinsic::ssub_with_overflow:

1231 case Intrinsic::ucmp:

1232 case Intrinsic::scmp:

1235 break;

1236

1237 case Intrinsic::umin:

1238 case Intrinsic::umax:

1239 case Intrinsic::smin:

1240 case Intrinsic::smax:

1241

1244 [[fallthrough]];

1245 case Intrinsic::uadd_sat:

1246 case Intrinsic::usub_sat:

1247

1248

1250 break;

1251 [[fallthrough]];

1252 case Intrinsic::abs:

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

1254 break;

1255 }

1256

1258 }

1259

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(

1268 }

1269 return;

1270 }

1271

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

1274 return;

1275

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

1277

1278

1279

1280 Value *Op0, *Op1;

1285

1286

1287 if (IsOr && IsAnd)

1288 IsAnd = false;

1289

1291 if (canAddSuccessor(BB, Successor)) {

1293 SmallPtrSet<Value *, 8> SeenCond;

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

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

1297 };

1298 QueueValue(Op1);

1299 QueueValue(Op0);

1300 while (!CondWorkList.empty()) {

1303 WorkList.emplace_back(FactOrCheck::getConditionFact(

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

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

1307 continue;

1308 }

1310 QueueValue(Op1);

1311 QueueValue(Op0);

1312 continue;

1313 }

1315 QueueValue(Op1);

1316 QueueValue(Op0);

1317 continue;

1318 }

1319 }

1320 }

1321 return;

1322 }

1323

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

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

1341 LHS->printAsOperand(OS, true);

1342 OS << ", ";

1343 RHS->printAsOperand(OS, false);

1344}

1345#endif

1346

1347namespace {

1348

1349

1350

1351

1352struct ReproducerEntry {

1353 ICmpInst::Predicate Pred;

1356

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

1359};

1360}

1361

1362

1363

1364

1365

1366

1367

1368

1372 if (!M)

1373 return;

1374

1376

1378

1382

1383

1384

1385

1386

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

1390 while (!WorkList.empty()) {

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

1393 continue;

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

1395 continue;

1397 continue;

1398

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

1402 Old2New[V] = V;

1403 Args.push_back(V);

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

1405 } else {

1407 }

1408 }

1409 };

1410

1411 for (auto &Entry : Stack)

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

1415

1417 for (auto *P : Args)

1419

1421 false);

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

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

1425 M);

1426

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

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

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

1436

1437

1438

1439

1440

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

1445 while (!WorkList.empty()) {

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

1448 continue;

1449

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

1452 Old2New[V] = nullptr;

1455 }

1456 }

1457

1458 sort(ToClone,

1462 Old2New[I] = Cloned;

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

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

1467 }

1468 };

1469

1470

1471

1472

1473

1474

1475 for (auto &Entry : Stack) {

1477 continue;

1478

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

1489

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

1493

1495}

1496

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

1511

1512

1513 for (auto &Row : R.ExtraInfo)

1514 CSToUse.addVariableRow(Row);

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

1517 CSToUse.popLastConstraint();

1518 });

1519

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

1522 return std::nullopt;

1523

1525 dbgs() << "Condition ";

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

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

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

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

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

1553 return false;

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

1555 UserI->comesBefore(ContextInst))

1556 return false;

1557

1558

1559

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

1562 Changed |= ShouldReplace;

1563 return ShouldReplace;

1564 });

1565 NumCondsRemoved++;

1566

1567

1568

1571

1572 for (auto *DVR : DVRUsers) {

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

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())

1587

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

1597

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

1610

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

1613 return true;

1614 };

1615

1620 return ReplaceMinMaxWithOperand(MinMax, *ImpliedCondition);

1623 return ReplaceMinMaxWithOperand(MinMax, !*ImpliedCondition);

1624 return false;

1625}

1626

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

1634 return true;

1635 }

1639 return true;

1640 }

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

1644 return true;

1645 }

1646 return false;

1647}

1648

1649static void

1651 Module *ReproducerModule,

1654 Info.popLastConstraint(E.IsSigned);

1655

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());

1661 if (ReproducerModule)

1662 ReproducerCondStack.pop_back();

1663}

1664

1665

1666

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

1672 Instruction *JoinOp = CB.getContextInst();

1674 return false;

1675

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

1678

1679

1680

1681

1683 return false;

1684

1685 unsigned OldSize = DFSInStack.size();

1687

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

1689 StackEntry E = DFSInStack.back();

1691 DFSInStack);

1692 }

1693 });

1696

1697 while (!Worklist.empty()) {

1698 Value *Val = Worklist.pop_back_val();

1702

1703 if (IsOr)

1705

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

1707 continue;

1708 }

1711 Worklist.push_back(LHS);

1712 Worklist.push_back(RHS);

1713 }

1714 }

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

1716 return false;

1717

1718

1719 if (auto ImpliedCondition =

1722 if (IsOr == *ImpliedCondition)

1725 else

1728 return true;

1729 }

1730

1731 return false;

1732}

1733

1735 unsigned NumIn, unsigned NumOut,

1736 SmallVectorImpl &DFSInStack) {

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

1738

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

1741}

1742

1744 unsigned NumIn, unsigned NumOut,

1745 SmallVectorImpl &DFSInStack,

1746 bool ForceSignedSystem) {

1747

1748

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

1751

1752

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

1754 return;

1755

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

1767

1768 SmallVector<Value *, 2> ValuesToRelease;

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

1770 for (Value *V : NewVariables) {

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

1773 }

1774

1776 dbgs() << " constraint: ";

1778 dbgs() << "\n";

1779 });

1780

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

1782 std::move(ValuesToRelease));

1783

1784 if (.IsSigned) {

1785 for (Value *V : NewVariables) {

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

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

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

1813 if ( Sub )

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

1815 U->replaceAllUsesWith(Sub);

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

1820 } else

1821 continue;

1822

1823 if (U->use_empty()) {

1828 }

1829 }

1830

1831 if (II->use_empty()) {

1832 II->eraseFromParent();

1834 }

1836}

1837

1838static bool

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

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

1853

1854

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

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

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

1860 return false;

1862 }

1864}

1865

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

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

1875 std::unique_ptr ReproducerModule(

1877

1878

1879

1882 continue;

1883 S.addInfoFor(BB);

1884 }

1885

1886

1887

1888

1889

1890

1891

1892

1893

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(V0) && !isa(V1);

1899 };

1900

1901

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

1920

1921

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

1925

1926

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;

1936 dbgs() << "Removing ";

1938 Info.getValue2Index(E.IsSigned));

1939 dbgs() << "\n";

1940 });

1942 DFSInStack);

1943 }

1944

1945

1946

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");

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

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

1959 if (!Simplified &&

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

1964 }

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: ";

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())

1987

1989

1990

1991

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

2002

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()) {

2016

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

2021 continue;

2022 }

2023

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

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

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

2028 continue;

2029 }

2031 switch (USatI->getIntrinsicID()) {

2032 default:

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;

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

2052 TLI))

2053 AddFact(Pred, A, B);

2054 };

2055

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

2058 continue;

2059 }

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;

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

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

2076 dbgs() << " because precondition ";

2078 CB.DoesHold.Op1);

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

2080 });

2081 continue;

2082 }

2083 } else {

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

2112 I->eraseFromParent();

2114}

2115

2125

2131 return PA;

2132}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

ReachingDefInfo InstSet & ToRemove

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

Analysis containing CSE Info

std::pair< ICmpInst *, unsigned > ConditionTy

static int64_t MaxConstraintValue

Definition ConstraintElimination.cpp:66

static int64_t MinSignedConstraintValue

Definition ConstraintElimination.cpp:67

static Instruction * getContextInstForUse(Use &U)

Definition ConstraintElimination.cpp:69

static Decomposition decomposeGEP(GEPOperator &GEP, SmallVectorImpl< ConditionTy > &Preconditions, bool IsSigned, const DataLayout &DL)

Definition ConstraintElimination.cpp:456

static bool canUseSExt(ConstantInt *CI)

Definition ConstraintElimination.cpp:451

static void dumpConstraint(ArrayRef< int64_t > C, const DenseMap< Value *, unsigned > &Value2Index)

Definition ConstraintElimination.cpp:957

static void removeEntryFromStack(const StackEntry &E, ConstraintInfo &Info, Module *ReproducerModule, SmallVectorImpl< ReproducerEntry > &ReproducerCondStack, SmallVectorImpl< StackEntry > &DFSInStack)

Definition ConstraintElimination.cpp:1650

static std::optional< bool > checkCondition(CmpInst::Predicate Pred, Value *A, Value *B, Instruction *CheckInst, ConstraintInfo &Info)

Definition ConstraintElimination.cpp:1497

static cl::opt< unsigned > MaxRows("constraint-elimination-max-rows", cl::init(500), cl::Hidden, cl::desc("Maximum number of rows to keep in constraint system"))

static cl::opt< bool > DumpReproducers("constraint-elimination-dump-reproducers", cl::init(false), cl::Hidden, cl::desc("Dump IR to reproduce successful transformations."))

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

static bool eliminateConstraints(Function &F, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, OptimizationRemarkEmitter &ORE, TargetLibraryInfo &TLI)

Definition ConstraintElimination.cpp:1866

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

Definition ConstraintElimination.cpp:417

static bool checkAndReplaceMinMax(MinMaxIntrinsic *MinMax, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)

Definition ConstraintElimination.cpp:1607

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

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

static bool getConstraintFromMemoryAccess(GetElementPtrInst &GEP, uint64_t AccessSize, CmpPredicate &Pred, Value *&A, Value *&B, const DataLayout &DL, const TargetLibraryInfo &TLI)

Definition ConstraintElimination.cpp:1116

static void dumpUnpackedICmp(raw_ostream &OS, ICmpInst::Predicate Pred, Value *LHS, Value *RHS)

Definition ConstraintElimination.cpp:1338

static Decomposition decompose(Value *V, SmallVectorImpl< ConditionTy > &Preconditions, bool IsSigned, const DataLayout &DL)

Definition ConstraintElimination.cpp:495

static bool replaceSubOverflowUses(IntrinsicInst *II, Value *A, Value *B, SmallVectorImpl< Instruction * > &ToRemove)

Definition ConstraintElimination.cpp:1806

static bool tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)

Definition ConstraintElimination.cpp:1839

static bool checkAndReplaceCmp(CmpIntrinsic *I, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)

Definition ConstraintElimination.cpp:1627

This file provides an implementation of debug counters.

#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)

This is the interface for a simple mod/ref and alias analysis over globals.

Module.h This file contains the declarations for the Module class.

const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]

Machine Check Debug Module

uint64_t IntrinsicInst * II

static StringRef getName(Value *V)

const SmallVectorImpl< MachineOperand > & Cond

static bool isValid(const char C)

Returns true if C is a valid mangled character: <0-9a-zA-Z_>.

This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...

This file defines the SmallVector class.

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")

Class for arbitrary precision integers.

bool sgt(const APInt &RHS) const

Signed greater than comparison.

bool isZero() const

Determine if this value is zero, i.e. all bits are clear.

LLVM_ABI APInt urem(const APInt &RHS) const

Unsigned remainder operation.

bool isNegative() const

Determine sign of this APInt.

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.

bool slt(const APInt &RHS) const

Signed less than comparison.

bool isOne() const

Determine if this is a value of 1.

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

LLVM Basic Block Representation.

static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)

Creates a new BasicBlock.

LLVM_ABI const DataLayout & getDataLayout() const

Get the data layout of the module this basic block belongs to.

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...

Represents analyses that only rely on functions' control flow.

This class is the base class for the comparison instructions.

static Type * makeCmpResultType(Type *opnd_type)

Create a result type for fcmp/icmp.

bool isEquality() const

Determine if this is an equals/not equals predicate.

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

@ ICMP_SLT

signed less than

@ ICMP_SLE

signed less or equal

@ ICMP_UGE

unsigned greater or equal

@ ICMP_UGT

unsigned greater than

@ ICMP_SGT

signed greater than

@ ICMP_ULT

unsigned less than

@ ICMP_SGE

signed greater or equal

@ ICMP_ULE

unsigned less or equal

Predicate getSwappedPredicate() const

For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.

Predicate getNonStrictPredicate() const

For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.

Predicate getInversePredicate() const

For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...

Predicate getPredicate() const

Return the predicate for this instruction.

This class represents a ucmp/scmp intrinsic.

An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...

bool hasSameSign() const

Query samesign information, for optimizations.

This is the shared class of boolean and integer constants.

static ConstantInt * getSigned(IntegerType *Ty, int64_t V)

Return a ConstantInt with the specified value for the specified type.

int64_t getSExtValue() const

Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...

const APInt & getValue() const

Return the constant as an APInt value reference.

static LLVM_ABI ConstantInt * getBool(LLVMContext &Context, bool V)

This is an important base class in LLVM.

static LLVM_ABI Constant * getAllOnesValue(Type *Ty)

static LLVM_ABI Constant * getNullValue(Type *Ty)

Constructor to create a '0' constant of arbitrary type.

PreservedAnalyses run(Function &F, FunctionAnalysisManager &)

Definition ConstraintElimination.cpp:2116

static SmallVector< int64_t, 8 > negate(SmallVector< int64_t, 8 > R)

LLVM_ABI bool isConditionImplied(SmallVector< int64_t, 8 > R) const

static SmallVector< int64_t, 8 > toStrictLessThan(SmallVector< int64_t, 8 > R)

Converts the given vector to form a strict less than inequality.

static SmallVector< int64_t, 8 > negateOrEqual(SmallVector< int64_t, 8 > R)

Multiplies each coefficient in the given vector by -1.

bool addVariableRowFill(ArrayRef< int64_t > R)

LLVM_ABI void dump() const

Print the constraints in the system.

A parsed version of the target data layout string in and methods for querying it.

static bool shouldExecute(CounterInfo &Counter)

bool erase(const KeyT &Val)

bool contains(const_arg_type_t< KeyT > Val) const

Return true if the specified key is in the map, false otherwise.

std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)

unsigned getDFSNumIn() const

getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.

unsigned getDFSNumOut() const

Analysis pass which computes a DominatorTree.

void updateDFSNumbers() const

updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.

DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const

getNode - return the (Post)DominatorTree node for the specified basic block.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

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.

static LLVM_ABI FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)

This static method is the primary way of constructing a FunctionType.

static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)

static GEPNoWrapFlags none()

an instruction for type-safe pointer arithmetic to access elements of arrays and structs

@ ExternalLinkage

Externally visible function.

This instruction compares its operands according to the predicate given to the constructor.

Predicate getFlippedSignednessPredicate() const

For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->EQ.

Predicate getSignedPredicate() const

For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.

bool isRelational() const

Return true if the predicate is relational (not EQ or NE).

Predicate getUnsignedPredicate() const

For example, EQ->EQ, SLE->ULE, UGT->UGT, etc.

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

LLVM_ABI void insertBefore(InstListType::iterator InsertPos)

Insert an unlinked instruction into a basic block immediately before the specified position.

LLVM_ABI void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs={})

Drop all unknown metadata except for debug locations.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

A wrapper class for inspecting calls to intrinsic functions.

This is an important class for using LLVM in a threaded context.

Analysis pass that exposes the LoopInfo for a function.

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

This class represents min/max intrinsics.

A Module instance is used to store all the information related to an LLVM module.

Value * getIncomingValueForBlock(const BasicBlock *BB) const

unsigned getNumIncomingValues() const

Return the number of incoming edges.

static LLVM_ABI PoisonValue * get(Type *T)

Static factory methods - Return an 'poison' object of the specified type.

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

PreservedAnalyses & preserveSet()

Mark an analysis set as preserved.

PreservedAnalyses & preserve()

Mark an analysis as preserved.

Analysis pass that exposes the ScalarEvolution for a function.

The main scalar evolution driver.

LLVM_ABI const SCEV * getSCEV(Value *V)

Return a SCEV expression for the full generality of the specified expression.

LLVM_ABI bool isSCEVable(Type *Ty) const

Test if values of the given type are analyzable within the SCEV framework.

@ MonotonicallyIncreasing

LLVM_ABI const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)

Return LHS-RHS.

LLVM_ABI APInt getConstantMultiple(const SCEV *S, const Instruction *CtxI=nullptr)

Returns the max constant multiple of S.

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,...

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

reference emplace_back(ArgTypes &&... Args)

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

Analysis pass providing the TargetLibraryInfo.

Provides information about what library functions are available for the current target.

The instances of the Type class are immutable: once they are created, they are never changed.

Type * getScalarType() const

If this is a vector type, return the element type, otherwise return 'this'.

LLVM_ABI unsigned getScalarSizeInBits() const LLVM_READONLY

If this is a vector type, return the getPrimitiveSizeInBits value for the element type.

A Use represents the edge between a Value definition and its users.

Value * getOperand(unsigned i) const

iterator find(const KeyT &Val)

LLVM Value Representation.

Type * getType() const

All values are typed, get the type of this value.

LLVM_ABI void replaceAllUsesWith(Value *V)

Change all uses of this to point to a new Value.

LLVM_ABI const Value * stripPointerCastsSameRepresentation() const

Strip off pointer casts, all-zero GEPs and address space casts but ensures the representation of the ...

constexpr ScalarTy getFixedValue() const

constexpr bool isFixed() const

Returns true if the quantity is not scaled by vscale.

const ParentTy * getParent() const

This class implements an extremely fast bulk output stream that can only output to a stream.

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

@ C

The default llvm calling convention, compatible with C.

@ BasicBlock

Various leaf nodes.

BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)

OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)

auto m_LogicalOp()

Matches either L && R or L || R where L and R are arbitrary values.

OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWSub(const LHS &L, const RHS &R)

bool match(Val *V, const Pattern &P)

DisjointOr_match< LHS, RHS > m_DisjointOr(const LHS &L, const RHS &R)

class_match< ConstantInt > m_ConstantInt()

Match an arbitrary ConstantInt and ignore it.

IntrinsicID_match m_Intrinsic()

Match intrinsic calls like this: m_IntrinsicIntrinsic::fabs(m_Value(X))

ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)

Match a single index ExtractValue instruction.

NoWrapTrunc_match< OpTy, TruncInst::NoSignedWrap > m_NSWTrunc(const OpTy &Op)

Matches trunc nsw.

NNegZExt_match< OpTy > m_NNegZExt(const OpTy &Op)

auto m_LogicalOr()

Matches L || R where L and R are arbitrary values.

OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoSignedWrap > m_NSWShl(const LHS &L, const RHS &R)

CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)

Matches ZExt.

OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWShl(const LHS &L, const RHS &R)

OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWMul(const LHS &L, const RHS &R)

brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)

OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWSub(const LHS &L, const RHS &R)

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)

CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)

auto m_LogicalAnd()

Matches L && R where L and R are arbitrary values.

CastInst_match< OpTy, SExtInst > m_SExt(const OpTy &Op)

Matches SExt.

is_zero m_Zero()

Match any null constant or a vector with all elements equal to 0.

OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap > m_NSWMul(const LHS &L, const RHS &R)

initializer< Ty > init(const Ty &Val)

@ Switch

The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...

DiagnosticInfoOptimizationBase::Argument NV

NodeAddr< UseNode * > Use

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

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...

void stable_sort(R &&Range)

bool all_of(R &&range, UnaryPredicate P)

Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.

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.

detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

LLVM_ABI bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)

Check a function for errors, useful for use when debugging a pass.

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

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...

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...

detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&...Ranges)

Returns a concatenated range across two or more ranges.

const Value * getPointerOperand(const Value *V)

A helper function that returns the pointer operand of a load, store or GEP instruction.

DomTreeNodeBase< BasicBlock > DomTreeNode

auto dyn_cast_or_null(const Y &Val)

constexpr unsigned MaxAnalysisRecursionDepth

void sort(IteratorTy Start, IteratorTy End)

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

@ Sub

Subtraction of integers.

LLVM_ABI void remapInstructionsInBlocks(ArrayRef< BasicBlock * > Blocks, ValueToValueMapTy &VMap)

Remaps instructions in Blocks using the mapping in VMap.

ArrayRef(const T &OneElt) -> ArrayRef< T >

constexpr unsigned BitWidth

ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy

OutputIt move(R &&Range, OutputIt Out)

Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.

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...

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...

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)

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 ...

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

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...

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.

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.

LLVM_ABI void findDbgUsers(Value *V, SmallVectorImpl< DbgVariableRecord * > &DbgVariableRecords)

Finds the debug info records describing a value.

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

Various options to control the behavior of getObjectSize.

bool NullIsUnknownSize

If this is true, null pointers in address space 0 will be treated as though they can't be evaluated.

bool RoundToAlign

Whether to round the result up to the alignment of allocas, byval arguments, and global variables.

A MapVector that performs no allocations if smaller than a certain size.