InstCombineInternal.h Source File (original) (raw)

15#ifndef LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H

16#define LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H

31#include

33#define DEBUG_TYPE "instcombine"

44namespace llvm {

46class AAResults;

47class APInt;

48class AssumptionCache;

49class BlockFrequencyInfo;

50class DataLayout;

51class DominatorTree;

52class GEPOperator;

53class GlobalVariable;

54class OptimizationRemarkEmitter;

55class ProfileSummaryInfo;

56class TargetLibraryInfo;

57class User;

61 public InstVisitor<InstCombinerImpl, Instruction *> {

62public:

70 : InstCombiner(Worklist, Builder, MinimizeSize, AA, AC, TLI, TTI, DT, ORE,

71 BFI, BPI, PSI, DL, RPOT) {}

76 bool prepareWorklist(Function &F);

81 bool run();

93 Value *OptimizePointerDifference(

104 bool simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I);

115 bool sinkNotIntoOtherHandOfLogicalOp(Instruction &I);

118 Value *reassociateShiftAmtsOfTwoSameDirectionShifts(

120 bool AnalyzeForSignBitExtraction = false);

121 Instruction *canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(

123 Instruction *foldVariableSignZeroExtensionOfVariableHighBitExtract(

152

170 foldAggregateConstructionIntoAggregateReuse(InsertValueInst &OrigIVI);

179 Value *pushFreezeToPreventPoisonFromPropagating(FreezeInst &FI);

180 bool freezeOtherUses(FreezeInst &FI);

183

184

186

187

188

189

192

193

195 const unsigned SIOpd);

196

198 const Twine &Suffix = "");

199

203 unsigned Depth = 0) const {

205 Val, FMF, Interested, Depth,

206 getSimplifyQuery().getWithInstruction(CtxI));

207 }

208

212 unsigned Depth = 0) const {

214 Val, Interested, Depth, getSimplifyQuery().getWithInstruction(CtxI));

215 }

216

217

218

221

223 Constant *TruncC = ConstantExpr::getTrunc(C, TruncTy);

226 if (ExtTruncC && ExtTruncC == C)

227 return TruncC;

228 return nullptr;

229 }

230

232 return getLosslessTrunc(C, TruncTy, Instruction::ZExt);

233 }

234

236 return getLosslessTrunc(C, TruncTy, Instruction::SExt);

237 }

238

239 std::optional<std::pair<Intrinsic::ID, SmallVector<Value *, 3>>>

240 convertOrOfShiftsToFunnelShift(Instruction &Or);

241

242private:

244 bool isDesirableIntType(unsigned BitWidth) const;

245 bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;

246 bool shouldChangeType(Type *From, Type *To) const;

247 Value *dyn_castNegVal(Value *V) const;

248

249

250

251

252

253

254

255

256

257

258 bool shouldOptimizeCast(CastInst *CI);

259

260

261

262

263

264

265

266

267

268

269

270

271

276

279 bool transformConstExprCastCall(CallBase &Call);

282

283

284

285

286

287

288

289 std::optional<std::pair<Value *, Value *>> matchSymmetricPair(Value *LHS,

291

296

297

298

299

300

301

302

303

304

305

307

309

314 OverflowResult::NeverOverflows;

315 }

316

317 bool willNotOverflowUnsignedAdd(const WithCache<const Value *> &LHS,

318 const WithCache<const Value *> &RHS,

319 const Instruction &CxtI) const {

320 return computeOverflowForUnsignedAdd(LHS, RHS, &CxtI) ==

321 OverflowResult::NeverOverflows;

322 }

323

324 bool willNotOverflowAdd(const Value *LHS, const Value *RHS,

325 const Instruction &CxtI, bool IsSigned) const {

326 return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CxtI)

327 : willNotOverflowUnsignedAdd(LHS, RHS, CxtI);

328 }

329

330 bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,

331 const Instruction &CxtI) const {

333 OverflowResult::NeverOverflows;

334 }

335

336 bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,

337 const Instruction &CxtI) const {

339 OverflowResult::NeverOverflows;

340 }

341

342 bool willNotOverflowSub(const Value *LHS, const Value *RHS,

343 const Instruction &CxtI, bool IsSigned) const {

344 return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CxtI)

345 : willNotOverflowUnsignedSub(LHS, RHS, CxtI);

346 }

347

348 bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,

349 const Instruction &CxtI) const {

351 OverflowResult::NeverOverflows;

352 }

353

354 bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,

355 const Instruction &CxtI,

356 bool IsNSW = false) const {

358 OverflowResult::NeverOverflows;

359 }

360

361 bool willNotOverflowMul(const Value *LHS, const Value *RHS,

362 const Instruction &CxtI, bool IsSigned) const {

363 return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CxtI)

364 : willNotOverflowUnsignedMul(LHS, RHS, CxtI);

365 }

366

367 bool willNotOverflow(BinaryOperator::BinaryOps Opcode, const Value *LHS,

368 const Value *RHS, const Instruction &CxtI,

369 bool IsSigned) const {

370 switch (Opcode) {

371 case Instruction::Add: return willNotOverflowAdd(LHS, RHS, CxtI, IsSigned);

372 case Instruction::Sub: return willNotOverflowSub(LHS, RHS, CxtI, IsSigned);

373 case Instruction::Mul: return willNotOverflowMul(LHS, RHS, CxtI, IsSigned);

374 default: llvm_unreachable("Unexpected opcode for overflow query");

375 }

376 }

377

378 Value *EmitGEPOffset(GEPOperator *GEP, bool RewriteGEP = false);

379 Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);

380 Instruction *foldBitcastExtElt(ExtractElementInst &ExtElt);

381 Instruction *foldCastedBitwiseLogic(BinaryOperator &I);

382 Instruction *foldFBinOpOfIntCasts(BinaryOperator &I);

383

384 Instruction *foldFBinOpOfIntCastsFromSign(

385 BinaryOperator &BO, bool OpsFromSigned, std::array<Value *, 2> IntOps,

386 Constant *Op1FpC, SmallVectorImpl<WithCache<const Value *>> &OpsKnown);

387 Instruction *foldBinopOfSextBoolToSelect(BinaryOperator &I);

388 Instruction *narrowBinOp(TruncInst &Trunc);

389 Instruction *narrowMaskedBinOp(BinaryOperator &And);

390 Instruction *narrowMathIfNoOverflow(BinaryOperator &I);

391 Instruction *narrowFunnelShift(TruncInst &Trunc);

392 Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);

393 Instruction *matchSAddSubSat(IntrinsicInst &MinMax1);

394 Instruction *foldNot(BinaryOperator &I);

395 Instruction *foldBinOpOfDisplacedShifts(BinaryOperator &I);

396

397

398

399

400

401

402

403

404

405

406

407 Instruction::CastOps isEliminableCastPair(const CastInst *CI1,

408 const CastInst *CI2);

409 Value *simplifyIntToPtrRoundTripCast(Value *Val);

410

411 Value *foldAndOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &I,

412 bool IsAnd, bool IsLogical = false);

413 Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Xor);

414

415 Value *foldEqOfParts(Value *Cmp0, Value *Cmp1, bool IsAnd);

416

417 Value *foldAndOrOfICmpsUsingRanges(ICmpInst *ICmp1, ICmpInst *ICmp2,

418 bool IsAnd);

419

420

421

422

423 Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd,

424 bool IsLogicalSelect = false);

425

426 Instruction *foldLogicOfIsFPClass(BinaryOperator &Operator, Value *LHS,

427 Value *RHS);

428

429 Value *foldBooleanAndOr(Value *LHS, Value *RHS, Instruction &I, bool IsAnd,

430 bool IsLogical);

431

432 Value *reassociateBooleanAndOr(Value *LHS, Value *X, Value *Y, Instruction &I,

433 bool IsAnd, bool RHSIsLogical);

434

435 Instruction *

436 canonicalizeConditionalNegationViaMathToSelect(BinaryOperator &i);

437

438 Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D,

439 bool InvertFalseVal = false);

440 Value *getSelectCondition(Value *A, Value *B, bool ABIsTheSame);

441

442 Instruction *foldLShrOverflowBit(BinaryOperator &I);

443 Instruction *foldExtractOfOverflowIntrinsic(ExtractValueInst &EV);

444 Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);

445 Instruction *foldIntrinsicIsFPClass(IntrinsicInst &II);

446 Instruction *foldFPSignBitOps(BinaryOperator &I);

447 Instruction *foldFDivConstantDivisor(BinaryOperator &I);

448

449

450

451

452

453 Instruction *foldAndOrOfSelectUsingImpliedCond(Value *Op, SelectInst &SI,

454 bool IsAnd);

455

456 Instruction *hoistFNegAboveFMulFDiv(Value *FNegOp, Instruction &FMFSource);

457

458public:

459

460

463 auto *SI = new StoreInst(ConstantInt::getTrue(Ctx),

464 PoisonValue::get(PointerType::getUnqual(Ctx)),

465 false, Align(1));

467 }

468

469

470

471

472

473

476 assert(I.use_empty() && "Cannot erase instruction that is used!");

478

479

480

482 Worklist.remove(&I);

483 DC.removeValue(&I);

484 I.eraseFromParent();

486 Worklist.handleUseCountDecrement(Op);

487 MadeIRChange = true;

488 return nullptr;

489 }

490

494

495

496

497 bool SimplifyAssociativeOrCommutative(BinaryOperator &I);

498

499

500

501

502

503

504

505

507

508

509

510

511

512

514

515

516

519

520

521

523

524

525

526

527

529

530

531

532

533

535

536

537

539

540

541

542

543

544

548

549

550

552 KnownBits &Known, unsigned Depth,

554 using InstCombiner::SimplifyDemandedBits;

555 bool SimplifyDemandedBits(Instruction *I, unsigned Op,

557 unsigned Depth, const SimplifyQuery &Q) override;

558

559

560

561

563 const APInt &DemandedMask,

564 KnownBits &Known, unsigned Depth,

566

567

568

569 Value *simplifyShrShlDemandedBits(

572

573

574

575 bool SimplifyDemandedInstructionBits(Instruction &Inst);

577

578 Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,

579 APInt &PoisonElts, unsigned Depth = 0,

580 bool AllowMultipleUsers = false) override;

581

582

583

587 bool SimplifyDemandedFPClass(Instruction *I, unsigned Op,

589 unsigned Depth = 0);

590

591

593 bool NUW);

594

595

599

600

601

602

604 bool AllowMultipleUses = false);

605

606

607

608

609

610

611

612

613

615

616

617

618

619

621 bool FoldWithMultiUse = false);

622

623

625

627

630

631

632

641

642

643

644

645 bool foldDeadPhiWeb(PHINode &PN);

646

647

648

649

650 bool foldIntegerTypedPHI(PHINode &PN);

651

652

653

655

660 bool foldAllocaCmp(AllocaInst *Alloca);

670

686

687 Value *foldMultiplicationOverflowCheck(ICmpInst &Cmp);

688

720 const APInt &C1);

726 const APInt &C2);

728 const APInt &C2);

729

741

742

755 unsigned Depth = 0);

756

759 bool mergeStoreIntoSuccessor(StoreInst &SI);

760

761

762

763

765 bool MatchBitReversals);

766

769

771

773 void tryToSinkInstructionDbgValues(

776 void tryToSinkInstructionDbgVariableRecords(

779

780 bool removeInstructionsBeforeUnreachable(Instruction &I);

787 void freelyInvertAllUsersOf(Value *V, Value *IgnoredUser = nullptr);

788

789

790

791

792

793 Value *takeLog2(Value *Op, unsigned Depth, bool AssumeNonZero, bool DoFold);

794

796 if (takeLog2(Op, 0, AssumeNonZero, false))

797 return takeLog2(Op, 0, AssumeNonZero, true);

798 return nullptr;

799 }

800};

801

803

805

808

810

811 const bool IsTrulyNegation;

812

814

816 bool IsTrulyNegation);

817

818#if LLVM_ENABLE_STATS

819 unsigned NumValuesVisitedInThisNegator = 0;

821#endif

822

823 using Result = std::pair<ArrayRef<Instruction *> ,

824 Value * >;

825

826 std::array<Value *, 2> getSortedOperandsOfBinOp(Instruction *I);

827

828 [[nodiscard]] Value *visitImpl(Value *V, bool IsNSW, unsigned Depth);

829

830 [[nodiscard]] Value *negate(Value *V, bool IsNSW, unsigned Depth);

831

832

833

834 [[nodiscard]] std::optional run(Value *Root, bool IsNSW);

835

840

841public:

842

843

844 [[nodiscard]] static Value *Negate(bool LHSIsZero, bool IsNSW, Value *Root,

846};

847

848}

849

850#undef DEBUG_TYPE

851

852#endif

AMDGPU Register Bank Select

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

BlockVerifier::State From

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

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

static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

static bool foldICmpWithDominatingICmp(CmpInst *Cmp, const TargetLowering &TLI)

For pattern like:

#define LLVM_LIBRARY_VISIBILITY

static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")

static bool isSigned(unsigned int Opcode)

static constexpr unsigned NegatorMaxNodesSSO

static constexpr unsigned NegatorDefaultMaxDepth

This file provides the interface for the instcombine pass implementation.

uint64_t IntrinsicInst * II

static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")

StandardInstrumentations SI(Mod->getContext(), Debug, VerifyEach)

This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.

const SmallVectorImpl< MachineOperand > & Cond

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

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

static OverflowResult computeOverflowForSignedAdd(const WithCache< const Value * > &LHS, const WithCache< const Value * > &RHS, const AddOperator *Add, const SimplifyQuery &SQ)

support::ulittle16_t & Lo

support::ulittle16_t & Hi

static const uint32_t IV[8]

Class for arbitrary precision integers.

This class represents a conversion between pointers from one address space to another.

an instruction to allocate memory on the stack

This class represents any memset intrinsic.

A cache of @llvm.assume calls within a function.

an instruction that atomically reads a memory location, combines it with another value,...

LLVM Basic Block Representation.

InstListType::iterator iterator

Instruction iterators...

This class represents a no-op cast from one type to another.

BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...

Conditional or Unconditional Branch instruction.

Analysis providing branch probability information.

Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...

CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...

This class represents a function call, abstracting a target machine's calling convention.

This is the base class for all instructions that perform data casts.

This class is the base class for the comparison instructions.

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

This is the shared class of boolean and integer constants.

This is an important base class in LLVM.

This class represents an Operation in the Expression.

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

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

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

This class represents a cast from floating point to signed integer.

This class represents a cast from floating point to unsigned integer.

This class represents a truncation of floating point types.

Convenience struct for specifying and reasoning about fast-math flags.

An instruction for ordering other memory operations.

This class represents a freeze function that returns random concrete value if an operand is either a ...

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

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

This instruction inserts a single (scalar) element into a VectorType value.

This instruction inserts a struct field of array element value into an aggregate value.

Instruction * foldSelectToCmp(SelectInst &SI)

bool fmulByZeroIsZero(Value *MulVal, FastMathFlags FMF, const Instruction *CtxI) const

Check if fmul MulVal, +0.0 will yield +0.0 (or signed zero is ignorable).

virtual ~InstCombinerImpl()=default

KnownFPClass computeKnownFPClass(Value *Val, FastMathFlags FMF, FPClassTest Interested=fcAllFlags, const Instruction *CtxI=nullptr, unsigned Depth=0) const

Instruction * foldSelectEqualityTest(SelectInst &SI)

Instruction * foldSelectValueEquivalence(SelectInst &SI, CmpInst &CI)

InstCombinerImpl(InstructionWorklist &Worklist, BuilderTy &Builder, bool MinimizeSize, AAResults *AA, AssumptionCache &AC, TargetLibraryInfo &TLI, TargetTransformInfo &TTI, DominatorTree &DT, OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI, BranchProbabilityInfo *BPI, ProfileSummaryInfo *PSI, const DataLayout &DL, ReversePostOrderTraversal< BasicBlock * > &RPOT)

Instruction * foldVectorSelect(SelectInst &Sel)

Instruction * foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1, Value *A, Value *B, Instruction &Outer, SelectPatternFlavor SPF2, Value *C)

Constant * getLosslessUnsignedTrunc(Constant *C, Type *TruncTy)

bool replaceInInstruction(Value *V, Value *Old, Value *New, unsigned Depth=0)

Instruction * eraseInstFromFunction(Instruction &I) override

Combiner aware instruction erasure.

Value * tryGetLog2(Value *Op, bool AssumeNonZero)

Instruction * foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI)

Constant * getLosslessTrunc(Constant *C, Type *TruncTy, unsigned ExtOp)

Instruction * visitInstruction(Instruction &I)

Specify what to return for unhandled instructions.

KnownFPClass computeKnownFPClass(Value *Val, FPClassTest Interested=fcAllFlags, const Instruction *CtxI=nullptr, unsigned Depth=0) const

Constant * getLosslessSignedTrunc(Constant *C, Type *TruncTy)

void CreateNonTerminatorUnreachable(Instruction *InsertAt)

Create and insert the idiom we use to indicate a block is unreachable without having to rewrite the C...

Instruction * visitSelectInst(SelectInst &SI)

Instruction * foldSelectOfBools(SelectInst &SI)

Instruction * foldSelectExtConst(SelectInst &Sel)

The core instruction combiner logic.

Base class for instruction visitors.

InstructionWorklist - This is the worklist management logic for InstCombine and other simplification ...

This class represents a cast from an integer to a pointer.

A wrapper class for inspecting calls to intrinsic functions.

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

The landingpad instruction holds all of the information necessary to generate correct exception handl...

An instruction for reading from memory.

This class represents min/max intrinsics.

static Value * Negate(bool LHSIsZero, bool IsNSW, Value *Root, InstCombinerImpl &IC)

Attempt to negate Root.

Analysis providing profile information.

This class represents a cast from a pointer to an integer.

Return a value (possibly void), from a function.

This class represents a sign extension of integer types.

This class represents the LLVM 'select' instruction.

This instruction constructs a fixed permutation of two input vectors.

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

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

An instruction for storing to memory.

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

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

This class represents a truncation of integer types.

Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...

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

This function has undefined behavior.

This represents the llvm.va_end intrinsic.

LLVM Value Representation.

LLVMContext & getContext() const

All values hold a context through their type.

This class represents zero extension of integer types.

self_iterator getIterator()

#define llvm_unreachable(msg)

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

@ C

The default llvm calling convention, compatible with C.

This is an optimization pass for GlobalISel generic memory operations.

void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)

Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...

OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const SimplifyQuery &SQ, bool IsNSW=false)

OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const SimplifyQuery &SQ)

SelectPatternFlavor

Specific patterns of select instructions we can match.

FPClassTest

Floating-point class tests, supported by 'is_fpclass' intrinsic.

raw_ostream & dbgs()

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

OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const SimplifyQuery &SQ)

Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)

Attempt to constant fold a cast with the specified operand.

OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const SimplifyQuery &SQ)

KnownFPClass computeKnownFPClass(const Value *V, const APInt &DemandedElts, FPClassTest InterestedClasses, unsigned Depth, const SimplifyQuery &SQ)

Determine which floating-point classes are valid for V, and return them in KnownFPClass bit sets.