DemandedBits.cpp Source File (original) (raw)

40#include

41#include

43using namespace llvm;

46#define DEBUG_TYPE "demanded-bits"

49 return I->isTerminator() || I->isEHPad() || I->mayHaveSideEffects();

50}

52void DemandedBits::determineLiveOperandBits(

53 const Instruction *UserI, const Value *Val, unsigned OperandNo,

55 bool &KnownBitsComputed) {

64 auto ComputeKnownBits =

66 if (KnownBitsComputed)

67 return;

68 KnownBitsComputed = true;

74 if (V2) {

77 }

78 };

79 auto GetShiftedRange = [&](uint64_t Min, uint64_t Max, bool ShiftLeft) {

80 auto ShiftF = [ShiftLeft](const APInt &Mask, unsigned ShiftAmnt) {

81 return ShiftLeft ? Mask.shl(ShiftAmnt) : Mask.lshr(ShiftAmnt);

82 };

84 uint64_t LoopRange = Max - Min;

85 APInt Mask = AOut;

86 APInt Shifted = AOut;

87 for (unsigned ShiftAmnt = 1; ShiftAmnt <= LoopRange; ShiftAmnt <<= 1) {

88 if (LoopRange & ShiftAmnt) {

90 Mask |= ShiftF(Shifted, LoopRange - ShiftAmnt + 1);

92 LoopRange -= ShiftAmnt;

93 }

95 Shifted |= ShiftF(Shifted, ShiftAmnt);

96 }

97 AB = ShiftF(Mask, Min);

98 };

101 default: break;

102 case Instruction::Call:

103 case Instruction::Invoke:

105 switch (II->getIntrinsicID()) {

106 default: break;

107 case Intrinsic::bswap:

108

109

111 break;

112 case Intrinsic::bitreverse:

113

114

116 break;

117 case Intrinsic::ctlz:

118 if (OperandNo == 0) {

119

120

121

122 ComputeKnownBits(BitWidth, Val, nullptr);

125 }

126 break;

127 case Intrinsic::cttz:

128 if (OperandNo == 0) {

129

130

131

132 ComputeKnownBits(BitWidth, Val, nullptr);

135 }

136 break;

137 case Intrinsic::fshl:

138 case Intrinsic::fshr: {

139 const APInt *SA;

140 if (OperandNo == 2) {

141

142

146

147

149 if (II->getIntrinsicID() == Intrinsic::fshr)

150 ShiftAmt = BitWidth - ShiftAmt;

151

152 if (OperandNo == 0)

153 AB = AOut.lshr(ShiftAmt);

154 else if (OperandNo == 1)

156 }

157 break;

158 }

159 case Intrinsic::umax:

160 case Intrinsic::umin:

161 case Intrinsic::smax:

162 case Intrinsic::smin:

163

164

166 break;

167 }

168 }

169 break;

170 case Instruction::Add:

172 AB = AOut;

173 } else {

176 }

177 break;

178 case Instruction::Sub:

180 AB = AOut;

181 } else {

184 }

185 break;

186 case Instruction::Mul:

187

188

189

191 break;

192 case Instruction::Shl:

193 if (OperandNo == 0) {

194 const APInt *ShiftAmtC;

197 AB = AOut.lshr(ShiftAmt);

198

199

200

202 if (S->hasNoSignedWrap())

204 else if (S->hasNoUnsignedWrap())

206 } else {

210

211 GetShiftedRange(Min, Max, false);

213 if (S->hasNoSignedWrap())

215 else if (S->hasNoUnsignedWrap())

217 }

218 }

219 break;

220 case Instruction::LShr:

221 if (OperandNo == 0) {

222 const APInt *ShiftAmtC;

225 AB = AOut.shl(ShiftAmt);

226

227

228

231 } else {

235

236

237

238

239

240

241

242

243

244

245

246 GetShiftedRange(Min, Max, true);

249 }

250 }

251 break;

252 case Instruction::AShr:

253 if (OperandNo == 0) {

254 const APInt *ShiftAmtC;

257 AB = AOut.shl(ShiftAmt);

258

259

260

262 .getBoolValue())

263 AB.setSignBit();

264

265

266

269 } else {

273 GetShiftedRange(Min, Max, true);

274 if (Max &&

276

277

278

279

280

281

282

283 AB.setSignBit();

284 }

285

286

289 }

290 }

291 break;

292 case Instruction::And:

293 AB = AOut;

294

295

296

297

298

300 if (OperandNo == 0)

301 AB &= ~Known2.Zero;

302 else

303 AB &= ~(Known.Zero & ~Known2.Zero);

304 break;

305 case Instruction::Or:

306 AB = AOut;

307

308

309

310

311

313 if (OperandNo == 0)

314 AB &= ~Known2.One;

315 else

316 AB &= ~(Known.One & ~Known2.One);

317 break;

318 case Instruction::Xor:

319 case Instruction::PHI:

320 AB = AOut;

321 break;

322 case Instruction::Trunc:

324 break;

325 case Instruction::ZExt:

327 break;

328 case Instruction::SExt:

330

331

332

335 .getBoolValue())

336 AB.setSignBit();

337 break;

338 case Instruction::Select:

339 if (OperandNo != 0)

340 AB = AOut;

341 break;

342 case Instruction::ExtractElement:

343 if (OperandNo == 0)

344 AB = AOut;

345 break;

346 case Instruction::InsertElement:

347 case Instruction::ShuffleVector:

348 if (OperandNo == 0 || OperandNo == 1)

349 AB = AOut;

350 break;

351 }

352}

353

354void DemandedBits::performAnalysis() {

355 if (Analyzed)

356

357 return;

358 Analyzed = true;

359

360 Visited.clear();

361 AliveBits.clear();

362 DeadUses.clear();

363

364 SmallSetVector<Instruction*, 16> Worklist;

365

366

369 continue;

370

371 LLVM_DEBUG(dbgs() << "DemandedBits: Root: " << I << "\n");

372

373

374

375

376 Type *T = I.getType();

377 if (T->isIntOrIntVectorTy()) {

378 if (AliveBits.try_emplace(&I, T->getScalarSizeInBits(), 0).second)

380

381 continue;

382 }

383

384

385 for (Use &OI : I.operands()) {

387 Type *T = J->getType();

388 if (T->isIntOrIntVectorTy())

390 else

391 Visited.insert(J);

393 }

394 }

395

396

397

398

399 }

400

401

402 while (!Worklist.empty()) {

404

405 LLVM_DEBUG(dbgs() << "DemandedBits: Visiting: " << *UserI);

406 APInt AOut;

407 bool InputIsKnownDead = false;

409 AOut = AliveBits[UserI];

412

413

414

415 InputIsKnownDead = !AOut && isAlwaysLive (UserI);

416 }

418

419 KnownBits Known, Known2;

420 bool KnownBitsComputed = false;

421

422

423

424 for (Use &OI : UserI->operands()) {

425

426

429 continue;

430

431 Type *T = OI->getType();

432 if (T->isIntOrIntVectorTy()) {

433 unsigned BitWidth = T->getScalarSizeInBits();

435 if (InputIsKnownDead) {

437 } else {

438

439

440 determineLiveOperandBits(UserI, OI, OI.getOperandNo(), AOut, AB,

441 Known, Known2, KnownBitsComputed);

442

443

444 if (AB.isZero())

445 DeadUses.insert(&OI);

446 else

447 DeadUses.erase(&OI);

448 }

449

450 if (I) {

451

452

453

454 auto Res = AliveBits.try_emplace(I);

455 if (Res.second || (AB |= Res.first->second) != Res.first->second) {

456 Res.first->second = std::move(AB);

458 }

459 }

460 } else if (I && Visited.insert(I).second) {

462 }

463 }

464 }

465}

466

468 performAnalysis();

469

470 auto Found = AliveBits.find(I);

471 if (Found != AliveBits.end())

472 return Found->second;

473

475 return APInt::getAllOnes(DL.getTypeSizeInBits(I->getType()->getScalarType()));

476}

477

479 Type *T = (*U)->getType();

482 unsigned BitWidth = DL.getTypeSizeInBits(T->getScalarType());

483

484

485

486 if (->isIntOrIntVectorTy())

488

491

492 performAnalysis();

493

497 bool KnownBitsComputed = false;

498

499 determineLiveOperandBits(UserI, *U, U->getOperandNo(), AOut, AB, Known,

500 Known2, KnownBitsComputed);

501

502 return AB;

503}

504

506 performAnalysis();

507

508 return !Visited.count(I) && !AliveBits.contains(I) && isAlwaysLive (I);

509}

510

512

513 if (!(*U)->getType()->isIntOrIntVectorTy())

514 return false;

515

516

519 return false;

520

521 performAnalysis();

522 if (DeadUses.count(U))

523 return true;

524

525

526

528 auto Found = AliveBits.find(UserI);

529 if (Found != AliveBits.end() && Found->second.isZero())

530 return true;

531 }

532

533 return false;

534}

535

538 OS << "DemandedBits: 0x" << Twine::utohexstr(A.getLimitedValue())

539 << " for ";

540 if (V) {

541 V->printAsOperand(OS, false);

542 OS << " in ";

543 }

544 OS << *I << '\n';

545 };

546

547 OS << "Printing analysis 'Demanded Bits Analysis' for function '" << F.getName() << "':\n";

548 performAnalysis();

549 for (auto &KV : AliveBits) {

551 PrintDB(I, KV.second);

552

553 for (Use &OI : I->operands()) {

555 }

556 }

557}

558

560 const APInt &AOut,

563 bool CarryZero, bool CarryOne) {

564 assert(!(CarryZero && CarryOne) &&

565 "Carry can't be zero and one at the same time");

566

567

568

569

570

571

572

573

575

576

577

578

579

580

583 APInt RProp = RAOut + (RAOut | ~RBound);

584 APInt RACarry = RProp ^ ~RBound;

586

587

588 APInt NeededToMaintainCarryZero;

589 APInt NeededToMaintainCarryOne;

590 if (OperandNo == 0) {

591 NeededToMaintainCarryZero = LHS.Zero | ~RHS.Zero;

592 NeededToMaintainCarryOne = LHS.One | ~RHS.One;

593 } else {

594 NeededToMaintainCarryZero = RHS.Zero | ~LHS.Zero;

595 NeededToMaintainCarryOne = RHS.One | ~LHS.One;

596 }

597

598

599 APInt PossibleSumZero = ~LHS.Zero + ~RHS.Zero + !CarryZero;

600 APInt PossibleSumOne = LHS.One + RHS.One + CarryOne;

601

602

603

604

605

606

607

608

609

610

611

612

613 APInt NeededToMaintainCarry = (~PossibleSumZero | NeededToMaintainCarryZero) &

614 (PossibleSumOne | NeededToMaintainCarryOne);

615

616 APInt AB = AOut | (ACarry & NeededToMaintainCarry);

617 return AB;

618}

619

621 const APInt &AOut,

625 false);

626}

627

629 const APInt &AOut,

633 NRHS.Zero = RHS.One;

634 NRHS.One = RHS.Zero;

636 true);

637}

638

640

647

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

This file implements a class to represent arbitrary precision integral constant values and operations...

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Expand Atomic instructions

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

static bool isAlwaysLive(Instruction *I)

Definition DemandedBits.cpp:48

static APInt determineLiveOperandBitsAddCarry(unsigned OperandNo, const APInt &AOut, const KnownBits &LHS, const KnownBits &RHS, bool CarryZero, bool CarryOne)

Definition DemandedBits.cpp:559

This header defines various interfaces for pass management in LLVM.

This defines the Use class.

uint64_t IntrinsicInst * II

This file implements a set that has insertion order iteration characteristics.

Class for arbitrary precision integers.

static APInt getAllOnes(unsigned numBits)

Return an APInt of a specified width with all bits set.

LLVM_ABI APInt zext(unsigned width) const

Zero extend to a new width.

unsigned getActiveBits() const

Compute the number of active bits in the value.

LLVM_ABI APInt trunc(unsigned width) const

Truncate to new width.

LLVM_ABI APInt urem(const APInt &RHS) const

Unsigned remainder operation.

unsigned getBitWidth() const

Return the number of bits in the APInt.

LLVM_ABI APInt reverseBits() const

unsigned countr_zero() const

Count the number of trailing zero bits.

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 isMask(unsigned numBits) const

APInt shl(unsigned shiftAmt) const

Left-shift function.

LLVM_ABI APInt byteSwap() const

static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)

Constructs an APInt value that has the bottom loBitsSet bits set.

static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)

Constructs an APInt value that has the top hiBitsSet bits set.

static APInt getZero(unsigned numBits)

Get the '0' value for the specified bit-width.

static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)

Constructs an APInt value that has a contiguous range of bits set.

APInt lshr(unsigned shiftAmt) const

Logical right-shift function.

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

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

A function analysis which provides an AssumptionCache.

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

An analysis that produces DemandedBits for a function.

LLVM_ABI DemandedBits run(Function &F, FunctionAnalysisManager &AM)

Run the analysis pass over a function and produce demanded bits information.

Definition DemandedBits.cpp:641

LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition DemandedBits.cpp:648

LLVM_ABI void print(raw_ostream &OS)

Definition DemandedBits.cpp:536

LLVM_ABI APInt getDemandedBits(Instruction *I)

Return the bits demanded from instruction I.

Definition DemandedBits.cpp:467

static LLVM_ABI APInt determineLiveOperandBitsAdd(unsigned OperandNo, const APInt &AOut, const KnownBits &LHS, const KnownBits &RHS)

Compute alive bits of one addition operand from alive output and known operand bits.

Definition DemandedBits.cpp:620

LLVM_ABI bool isInstructionDead(Instruction *I)

Return true if, during analysis, I could not be reached.

Definition DemandedBits.cpp:505

static LLVM_ABI APInt determineLiveOperandBitsSub(unsigned OperandNo, const APInt &AOut, const KnownBits &LHS, const KnownBits &RHS)

Compute alive bits of one subtraction operand from alive output and known operand bits.

Definition DemandedBits.cpp:628

LLVM_ABI bool isUseDead(Use *U)

Return whether this use is dead by means of not having any demanded bits.

Definition DemandedBits.cpp:511

Analysis pass which computes a DominatorTree.

unsigned getOpcode() const

Returns a member of one of the enums like Instruction::Add.

LLVM_ABI const DataLayout & getDataLayout() const

Get the data layout of the module this instruction belongs to.

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.

bool empty() const

Determine if the SetVector is empty or not.

bool insert(const value_type &X)

Insert a new element into the SetVector.

value_type pop_back_val()

static Twine utohexstr(uint64_t Val)

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

bool isIntOrIntVectorTy() const

Return true if this is an integer type or a vector of integer types.

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

Value * getOperand(unsigned i) const

LLVM Value Representation.

Type * getType() const

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

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

constexpr std::underlying_type_t< E > Mask()

Get a bitmask with 1s in all places up to the high-order bit of E's largest value.

ap_match< APInt > m_APInt(const APInt *&Res)

Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.

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

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)

decltype(auto) dyn_cast(const From &Val)

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

constexpr bool isPowerOf2_32(uint32_t Value)

Return true if the argument is a power of two > 0.

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.

bool isa(const From &Val)

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

constexpr unsigned BitWidth

decltype(auto) cast(const From &Val)

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

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

A special type used by analysis passes to provide an address that identifies that particular analysis...

unsigned countMaxTrailingZeros() const

Returns the maximum number of trailing zero bits possible.

APInt getMaxValue() const

Return the maximal unsigned value possible given these KnownBits.

APInt getMinValue() const

Return the minimal unsigned value possible given these KnownBits.

unsigned countMaxLeadingZeros() const

Returns the maximum number of leading zero bits possible.