InstCombiner.h Source File (original) (raw)

18#ifndef LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINER_H

19#define LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINER_H

30#include

32#define DEBUG_TYPE "instcombine"

35namespace llvm {

37class AAResults;

38class AssumptionCache;

39class OptimizationRemarkEmitter;

40class ProfileSummaryInfo;

41class TargetLibraryInfo;

42class TargetTransformInfo;

54public:

63protected:

101

102public:

115

117

118

119

120

123 if (!OneUseOnly || BitCast->hasOneUse())

124 return BitCast->getOperand(0);

125

126

127 return V;

128 }

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

148

152 return 2;

153

154 return 3;

155 }

156

157

158

159

160

161

163 switch (Pred) {

169

173 return false;

174 default:

175 return true;

176 }

177 }

178

179

183

184

188

199

200

201

202

203

204

205

206

207 Value *getFreelyInvertedImpl(Value *V, bool WillInvertAllUses,

208 BuilderTy *Builder, bool &DoesConsume,

210

213 DoesConsume = false;

215 0);

216 }

217

223

224

225

226

227

228

229

231 bool &DoesConsume) {

232 return getFreelyInverted(V, WillInvertAllUses, nullptr,

233 DoesConsume) != nullptr;

234 }

235

240

241

242

243

244

245

247

248 for (Use &U : V->uses()) {

249 if (U.getUser() == IgnoredUser)

250 continue;

251

253 switch (I->getOpcode()) {

254 case Instruction::Select:

255 if (U.getOperandNo() != 0)

256 return false;

258 return false;

259 break;

260 case Instruction::Br:

261 assert(U.getOperandNo() == 0 && "Must be branching on that value.");

262 break;

263 case Instruction::Xor:

264

266 return false;

267 break;

268 default:

269 return false;

270 }

271

272 }

273 return true;

274 }

275

276

277

278

279

280

283 bool IsRHSConstant) {

285

286 Type *EltTy = InVTy->getElementType();

288 if (!SafeC) {

289

290

291 if (IsRHSConstant) {

292 switch (Opcode) {

293 case Instruction::SRem:

294 case Instruction::URem:

295 SafeC = ConstantInt::get(EltTy, 1);

296 break;

297 case Instruction::FRem:

298 SafeC = ConstantFP::get(EltTy, 1.0);

299 break;

300 default:

302 "Only rem opcodes have no identity constant for RHS");

303 }

304 } else {

305 switch (Opcode) {

306 case Instruction::Shl:

307 case Instruction::LShr:

308 case Instruction::AShr:

309 case Instruction::SDiv:

310 case Instruction::UDiv:

311 case Instruction::SRem:

312 case Instruction::URem:

313 case Instruction::Sub:

314 case Instruction::FSub:

315 case Instruction::FDiv:

316 case Instruction::FRem:

318 break;

319 default:

320 llvm_unreachable("Expected to find identity constant for opcode");

321 }

322 }

323 }

324 assert(SafeC && "Must have safe constant for binop");

325 unsigned NumElts = InVTy->getNumElements();

327 for (unsigned i = 0; i != NumElts; ++i) {

328 Constant *C = In->getAggregateElement(i);

330 }

332 }

333

335

346

347

348 std::optional<Instruction *> targetInstCombineIntrinsic(IntrinsicInst &II);

349 std::optional<Value *>

350 targetSimplifyDemandedUseBitsIntrinsic(IntrinsicInst &II, APInt DemandedMask,

352 bool &KnownBitsComputed);

353 std::optional<Value *> targetSimplifyDemandedVectorEltsIntrinsic(

355 APInt &UndefElts2, APInt &UndefElts3,

357 SimplifyAndSetOp);

358

359 void computeBackEdges();

363 return BackEdges.contains({From, To});

364 }

365

366

367

368

369

371 assert(New && !New->getParent() &&

372 "New instruction already inserted into a basic block!");

373 New->insertBefore(Old);

375 return New;

376 }

377

378

380 New->setDebugLoc(Old->getDebugLoc());

382 }

383

384

385

386

387

388

389

391

392

393 if (I.use_empty()) return nullptr;

394

395 Worklist.pushUsersToWorkList(I);

396

397

398

399 if (&I == V)

401

403 << " with " << *V << '\n');

404

405

406 if (V->use_empty() && isa(V) && !V->hasName() && I.hasName())

407 V->takeName(&I);

408

409 I.replaceAllUsesWith(V);

410 return &I;

411 }

412

413

415 Value *OldOp = I.getOperand(OpNum);

416 I.setOperand(OpNum, V);

417 Worklist.handleUseCountDecrement(OldOp);

418 return &I;

419 }

420

421

423 Value *OldOp = U;

424 U = NewValue;

425 Worklist.handleUseCountDecrement(OldOp);

426 }

427

428

429

430

431

432

434

439

441 unsigned Depth = 0) const {

443 }

444

447 unsigned Depth = 0) {

450 }

451

454 unsigned Depth = 0) const {

456 }

457

460 unsigned Depth = 0) const {

462 }

463

466 unsigned Depth = 0) const {

468 }

469

473 bool IsNSW = false) const {

475 LHS, RHS, SQ.getWithInstruction(CxtI), IsNSW);

476 }

477

481 SQ.getWithInstruction(CxtI));

482 }

483

489 SQ.getWithInstruction(CxtI));

490 }

491

497 SQ.getWithInstruction(CxtI));

498 }

499

504 SQ.getWithInstruction(CxtI));

505 }

506

510 SQ.getWithInstruction(CxtI));

511 }

512

516 unsigned Depth = 0) = 0;

517

521 SQ.getWithInstruction(I));

522 }

523

526 unsigned Depth = 0,

527 bool AllowMultipleUsers = false) = 0;

528

530};

531

532}

533

534#undef DEBUG_TYPE

535

536#endif

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

#define LLVM_LIBRARY_VISIBILITY

uint64_t IntrinsicInst * II

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

Class for arbitrary precision integers.

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

LLVM Basic Block Representation.

InstListType::iterator iterator

Instruction iterators...

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

Analysis providing branch probability information.

@ ICMP_SLE

signed less or equal

@ FCMP_OGE

0 0 1 1 True if ordered and greater than or equal

@ ICMP_UGE

unsigned greater or equal

@ FCMP_ONE

0 1 1 0 True if ordered and operands are unequal

@ FCMP_OLE

0 1 0 1 True if ordered and less than or equal

@ ICMP_SGE

signed greater or equal

@ ICMP_ULE

unsigned less or equal

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

static LLVM_ABI Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)

static LLVM_ABI Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)

static LLVM_ABI Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false, bool NSZ=false)

Return the identity constant for a binary opcode.

static LLVM_ABI Constant * get(ArrayRef< Constant * > V)

This is an important base class in LLVM.

static LLVM_ABI Constant * getNullValue(Type *Ty)

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

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 provides a uniform API for creating instructions and inserting them into a basic block: either a...

OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const

Definition InstCombiner.h:507

SimplifyQuery SQ

Definition InstCombiner.h:79

const DataLayout & getDataLayout() const

Definition InstCombiner.h:339

unsigned ComputeMaxSignificantBits(const Value *Op, const Instruction *CxtI=nullptr, unsigned Depth=0) const

Definition InstCombiner.h:464

bool isFreeToInvert(Value *V, bool WillInvertAllUses)

Definition InstCombiner.h:236

virtual Instruction * eraseInstFromFunction(Instruction &I)=0

Combiner aware instruction erasure.

IRBuilder< TargetFolder, IRBuilderCallbackInserter > BuilderTy

An IRBuilder that automatically inserts new instructions into the worklist.

Definition InstCombiner.h:60

bool isFreeToInvert(Value *V, bool WillInvertAllUses, bool &DoesConsume)

Return true if the specified value is free to invert (apply ~ to).

Definition InstCombiner.h:230

DominatorTree & getDominatorTree() const

Definition InstCombiner.h:338

OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI, bool IsNSW=false) const

Definition InstCombiner.h:470

virtual ~InstCombiner()=default

Function & F

Definition InstCombiner.h:67

BlockFrequencyInfo * BFI

Definition InstCombiner.h:81

static unsigned getComplexity(Value *V)

Assign a complexity or rank value to LLVM Values.

Definition InstCombiner.h:145

SmallDenseMap< BasicBlock *, SmallVector< BasicBlock * >, 8 > PredOrder

Order of predecessors to canonicalize phi nodes towards.

Definition InstCombiner.h:94

TargetLibraryInfo & TLI

Definition InstCombiner.h:76

TargetLibraryInfo & getTargetLibraryInfo() const

Definition InstCombiner.h:337

unsigned ComputeNumSignBits(const Value *Op, const Instruction *CxtI=nullptr, unsigned Depth=0) const

Definition InstCombiner.h:458

BlockFrequencyInfo * getBlockFrequencyInfo() const

Definition InstCombiner.h:344

Instruction * InsertNewInstBefore(Instruction *New, BasicBlock::iterator Old)

Inserts an instruction New before instruction Old.

Definition InstCombiner.h:370

AAResults * AA

Definition InstCombiner.h:72

Instruction * replaceInstUsesWith(Instruction &I, Value *V)

A combiner-aware RAUW-like routine.

Definition InstCombiner.h:390

uint64_t MaxArraySizeForCombine

Maximum size of array considered when transforming.

Definition InstCombiner.h:56

static bool shouldAvoidAbsorbingNotIntoSelect(const SelectInst &SI)

Definition InstCombiner.h:189

bool ComputedBackEdges

Definition InstCombiner.h:100

OverflowResult computeOverflowForSignedAdd(const WithCache< const Value * > &LHS, const WithCache< const Value * > &RHS, const Instruction *CxtI) const

Definition InstCombiner.h:493

static Constant * SubOne(Constant *C)

Subtract one from a Constant.

Definition InstCombiner.h:185

void replaceUse(Use &U, Value *NewValue)

Replace use and add the previously used value to the worklist.

Definition InstCombiner.h:422

OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const

Definition InstCombiner.h:500

static bool isCanonicalPredicate(CmpPredicate Pred)

Predicate canonicalization reduces the number of patterns that need to be matched by other transforms...

Definition InstCombiner.h:162

InstructionWorklist & Worklist

A worklist of the instructions that need to be simplified.

Definition InstCombiner.h:65

Instruction * InsertNewInstWith(Instruction *New, BasicBlock::iterator Old)

Same as InsertNewInstBefore, but also sets the debug loc.

Definition InstCombiner.h:379

BranchProbabilityInfo * BPI

Definition InstCombiner.h:82

bool SimplifyDemandedBits(Instruction *I, unsigned OpNo, const APInt &DemandedMask, KnownBits &Known)

Definition InstCombiner.h:518

virtual bool SimplifyDemandedBits(Instruction *I, unsigned OpNo, const APInt &DemandedMask, KnownBits &Known, const SimplifyQuery &Q, unsigned Depth=0)=0

ReversePostOrderTraversal< BasicBlock * > & RPOT

Definition InstCombiner.h:86

const DataLayout & DL

Definition InstCombiner.h:78

DomConditionCache DC

Definition InstCombiner.h:84

const bool MinimizeSize

Definition InstCombiner.h:70

void computeKnownBits(const Value *V, KnownBits &Known, const Instruction *CxtI, unsigned Depth=0) const

Definition InstCombiner.h:435

virtual Value * SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &UndefElts, unsigned Depth=0, bool AllowMultipleUsers=false)=0

static Value * peekThroughBitcast(Value *V, bool OneUseOnly=false)

Return the source operand of a potentially bitcasted value while optionally checking if it has one us...

Definition InstCombiner.h:121

KnownBits computeKnownBits(const Value *V, const Instruction *CxtI, unsigned Depth=0) const

Definition InstCombiner.h:440

bool canFreelyInvertAllUsersOf(Instruction *V, Value *IgnoredUser)

Given i1 V, can every user of V be freely adapted if V is changed to !V ?

Definition InstCombiner.h:246

Value * getFreelyInverted(Value *V, bool WillInvertAllUses, BuilderTy *Builder)

Definition InstCombiner.h:218

AssumptionCache & AC

Definition InstCombiner.h:75

void addToWorklist(Instruction *I)

Definition InstCombiner.h:334

Value * getFreelyInvertedImpl(Value *V, bool WillInvertAllUses, BuilderTy *Builder, bool &DoesConsume, unsigned Depth)

Return nonnull value if V is free to invert under the condition of WillInvertAllUses.

SmallDenseSet< std::pair< const BasicBlock *, const BasicBlock * >, 8 > BackEdges

Backedges, used to avoid pushing instructions across backedges in cases where this may result in infi...

Definition InstCombiner.h:99

Instruction * replaceOperand(Instruction &I, unsigned OpNum, Value *V)

Replace operand of instruction and add old operand to the worklist.

Definition InstCombiner.h:414

bool MaskedValueIsZero(const Value *V, const APInt &Mask, const Instruction *CxtI=nullptr, unsigned Depth=0) const

Definition InstCombiner.h:452

DominatorTree & DT

Definition InstCombiner.h:77

static Constant * getSafeVectorConstantForBinop(BinaryOperator::BinaryOps Opcode, Constant *In, bool IsRHSConstant)

Some binary operators require special handling to avoid poison and undefined behavior.

Definition InstCombiner.h:282

OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const

Definition InstCombiner.h:478

ProfileSummaryInfo * getProfileSummaryInfo() const

Definition InstCombiner.h:345

OptimizationRemarkEmitter & getOptimizationRemarkEmitter() const

Definition InstCombiner.h:341

ProfileSummaryInfo * PSI

Definition InstCombiner.h:83

SmallDenseSet< std::pair< BasicBlock *, BasicBlock * >, 8 > DeadEdges

Edges that are known to never be taken.

Definition InstCombiner.h:91

bool MadeIRChange

Definition InstCombiner.h:88

BuilderTy & Builder

Definition InstCombiner.h:61

AssumptionCache & getAssumptionCache() const

Definition InstCombiner.h:336

OptimizationRemarkEmitter & ORE

Definition InstCombiner.h:80

bool isValidAddrSpaceCast(unsigned FromAS, unsigned ToAS) const

OverflowResult computeOverflowForUnsignedAdd(const WithCache< const Value * > &LHS, const WithCache< const Value * > &RHS, const Instruction *CxtI) const

Definition InstCombiner.h:485

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

Definition InstCombiner.h:103

Value * getFreelyInverted(Value *V, bool WillInvertAllUses, BuilderTy *Builder, bool &DoesConsume)

Definition InstCombiner.h:211

const SimplifyQuery & getSimplifyQuery() const

Definition InstCombiner.h:340

bool isBackEdge(const BasicBlock *From, const BasicBlock *To)

Definition InstCombiner.h:360

static Constant * AddOne(Constant *C)

Add one to a Constant.

Definition InstCombiner.h:180

bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero=false, const Instruction *CxtI=nullptr, unsigned Depth=0)

Definition InstCombiner.h:445

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

A wrapper class for inspecting calls to intrinsic functions.

static LLVM_ABI PoisonValue * get(Type *T)

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

Analysis providing profile information.

This class represents the LLVM 'select' instruction.

Implements a dense probed hash-table based set with some number of buckets stored inline.

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

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.

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

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

LLVM Value Representation.

iterator_range< use_iterator > uses()

#define llvm_unreachable(msg)

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

@ C

The default llvm calling convention, compatible with C.

BinaryOp_match< SpecificConstantMatch, SrcTy, TargetOpcode::G_SUB > m_Neg(const SrcTy &&Src)

Matches a register negated by a G_SUB.

BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)

Matches a register not-ed by a G_XOR.

LogicalOp_match< LHS, RHS, Instruction::And > m_LogicalAnd(const LHS &L, const RHS &R)

Matches L && R either in the form of L & R or L ?

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

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

FNeg_match< OpTy > m_FNeg(const OpTy &X)

Match 'fneg X' as 'fsub -0.0, X'.

LogicalOp_match< LHS, RHS, Instruction::Or > m_LogicalOr(const LHS &L, const RHS &R)

Matches L || R either in the form of L | R or L ?

This is an optimization pass for GlobalISel generic memory operations.

decltype(auto) dyn_cast(const From &Val)

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

LLVM_ABI bool MaskedValueIsZero(const Value *V, const APInt &Mask, const SimplifyQuery &SQ, unsigned Depth=0)

Return true if 'V & Mask' is known to be zero.

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

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

LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)

Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...

LLVM_ABI raw_ostream & dbgs()

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

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

bool isa(const From &Val)

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

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

DWARFExpression::Operation Op

LLVM_ABI unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)

Return the number of times the sign bit of the register is replicated into the other bits.

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

decltype(auto) cast(const From &Val)

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

LLVM_ABI unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)

Get the upper bound on bit size for this Value Op as a signed integer.

LLVM_ABI OverflowResult computeOverflowForUnsignedAdd(const WithCache< const Value * > &LHS, const WithCache< const Value * > &RHS, const SimplifyQuery &SQ)

LLVM_ABI bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL, bool OrZero=false, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)

Return true if the given value is known to have exactly one bit set when defined.