Evaluator.cpp Source File (original) (raw)

39#define DEBUG_TYPE "evaluator"

41using namespace llvm;

43static inline bool

56static bool

62 if (auto *GV = dyn_cast(C))

63 return !GV->hasDLLImportStorageClass() && !GV->isThreadLocal();

66 if (C->getNumOperands() == 0 || isa(C))

67 return true;

70 if (isa(C)) {

71 for (Value *Op : C->operands())

73 return false;

74 return true;

75 }

81 switch (CE->getOpcode()) {

82 case Instruction::BitCast:

86 case Instruction::IntToPtr:

87 case Instruction::PtrToInt:

90 if (DL.getTypeSizeInBits(CE->getType()) !=

91 DL.getTypeSizeInBits(CE->getOperand(0)->getType()))

92 return false;

96 case Instruction::GetElementPtr:

97 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)

98 if (!isa(CE->getOperand(i)))

99 return false;

101

102 case Instruction::Add:

103

104 if (!isa(CE->getOperand(1)))

105 return false;

107 }

108 return false;

109}

110

111static inline bool

115

116 if (!SimpleConstants.insert(C).second)

117 return true;

118

120}

121

122void Evaluator::MutableValue::clear() {

123 if (auto *Agg = dyn_cast_if_present<MutableAggregate *>(Val))

124 delete Agg;

125 Val = nullptr;

126}

127

130 TypeSize TySize = DL.getTypeStoreSize(Ty);

131 const MutableValue *V = this;

132 while (const auto *Agg = dyn_cast_if_present<MutableAggregate *>(V->Val)) {

133 Type *AggTy = Agg->Ty;

134 std::optional Index = DL.getGEPIndexForOffset(AggTy, Offset);

135 if (!Index || Index->uge(Agg->Elements.size()) ||

136 !TypeSize::isKnownLE(TySize, DL.getTypeStoreSize(AggTy)))

137 return nullptr;

138

139 V = &Agg->Elements[Index->getZExtValue()];

140 }

141

143}

144

145bool Evaluator::MutableValue::makeMutable() {

146 Constant *C = cast<Constant *>(Val);

147 Type *Ty = C->getType();

148 unsigned NumElements;

149 if (auto *VT = dyn_cast(Ty)) {

150 NumElements = VT->getNumElements();

151 } else if (auto *AT = dyn_cast(Ty))

152 NumElements = AT->getNumElements();

153 else if (auto *ST = dyn_cast(Ty))

154 NumElements = ST->getNumElements();

155 else

156 return false;

157

158 MutableAggregate *MA = new MutableAggregate(Ty);

159 MA->Elements.reserve(NumElements);

160 for (unsigned I = 0; I < NumElements; ++I)

161 MA->Elements.push_back(C->getAggregateElement(I));

162 Val = MA;

163 return true;

164}

165

168 Type *Ty = V->getType();

169 TypeSize TySize = DL.getTypeStoreSize(Ty);

170 MutableValue *MV = this;

171 while (Offset != 0 ||

173 if (isa<Constant *>(MV->Val) && !MV->makeMutable())

174 return false;

175

176 MutableAggregate *Agg = cast<MutableAggregate *>(MV->Val);

177 Type *AggTy = Agg->Ty;

178 std::optional Index = DL.getGEPIndexForOffset(AggTy, Offset);

179 if (!Index || Index->uge(Agg->Elements.size()) ||

180 !TypeSize::isKnownLE(TySize, DL.getTypeStoreSize(AggTy)))

181 return false;

182

183 MV = &Agg->Elements[Index->getZExtValue()];

184 }

185

186 Type *MVType = MV->getType();

187 MV->clear();

192 else if (Ty != MVType)

194 else

195 MV->Val = V;

196 return true;

197}

198

199Constant *Evaluator::MutableAggregate::toConstant() const {

201 for (const MutableValue &MV : Elements)

202 Consts.push_back(MV.toConstant());

203

204 if (auto *ST = dyn_cast(Ty))

206 if (auto *AT = dyn_cast(Ty))

208 assert(isa(Ty) && "Must be vector");

210}

211

212

213

215 APInt Offset(DL.getIndexTypeSizeInBits(P->getType()), 0);

216 P = cast(P->stripAndAccumulateConstantOffsets(

217 DL, Offset, true));

218 Offset = Offset.sextOrTrunc(DL.getIndexTypeSizeInBits(P->getType()));

219 if (auto *GV = dyn_cast(P))

220 return ComputeLoadResult(GV, Ty, Offset);

221 return nullptr;

222}

223

226 auto It = MutatedMemory.find(GV);

227 if (It != MutatedMemory.end())

228 return It->second.read(Ty, Offset, DL);

229

231 return nullptr;

233}

234

236 if (auto *Fn = dyn_cast(C))

237 return Fn;

238

239 if (auto *Alias = dyn_cast(C))

240 if (auto *Fn = dyn_cast(Alias->getAliasee()))

241 return Fn;

242 return nullptr;

243}

244

246Evaluator::getCalleeWithFormalArgs(CallBase &CB,

250 return getFormalParams(CB, Fn, Formals) ? Fn : nullptr;

251 return nullptr;

252}

253

256 auto *FTy = F->getFunctionType();

259 return false;

260 }

261

264 return true;

265}

266

267

268

269

270

272 bool &StrippedPointerCastsForAliasAnalysis) {

273

274 while (true) {

275 Constant *InstResult = nullptr;

276

277 LLVM_DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n");

278

279 if (StoreInst *SI = dyn_cast(CurInst)) {

280 if (SI->isVolatile()) {

281 LLVM_DEBUG(dbgs() << "Store is volatile! Can not evaluate.\n");

282 return false;

283 }

286 if (Ptr != FoldedPtr) {

287 LLVM_DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr);

288 Ptr = FoldedPtr;

290 }

291

293 Ptr = cast(Ptr->stripAndAccumulateConstantOffsets(

294 DL, Offset, true));

295 Offset = Offset.sextOrTrunc(DL.getIndexTypeSizeInBits(Ptr->getType()));

296 auto *GV = dyn_cast(Ptr);

298 LLVM_DEBUG(dbgs() << "Store is not to global with unique initializer: "

299 << *Ptr << "\n");

300 return false;

301 }

302

303

304

305 Constant *Val = getVal(SI->getOperand(0));

307 LLVM_DEBUG(dbgs() << "Store value is too complex to evaluate store. "

308 << *Val << "\n");

309 return false;

310 }

311

312 auto Res = MutatedMemory.try_emplace(GV, GV->getInitializer());

313 if (!Res.first->second.write(Val, Offset, DL))

314 return false;

315 } else if (LoadInst *LI = dyn_cast(CurInst)) {

316 if (LI->isVolatile()) {

318 dbgs() << "Found a Load! Volatile load, can not evaluate.\n");

319 return false;

320 }

321

322 Constant *Ptr = getVal(LI->getOperand(0));

324 if (Ptr != FoldedPtr) {

325 Ptr = FoldedPtr;

326 LLVM_DEBUG(dbgs() << "Found a constant pointer expression, constant "

327 "folding: "

328 << *Ptr << "\n");

329 }

330 InstResult = ComputeLoadResult(Ptr, LI->getType());

331 if (!InstResult) {

333 dbgs() << "Failed to compute load result. Can not evaluate load."

334 "\n");

335 return false;

336 }

337

338 LLVM_DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n");

339 } else if (AllocaInst *AI = dyn_cast(CurInst)) {

340 if (AI->isArrayAllocation()) {

341 LLVM_DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n");

342 return false;

343 }

344 Type *Ty = AI->getAllocatedType();

345 AllocaTmps.push_back(std::make_unique(

348 AI->getType()->getPointerAddressSpace()));

349 InstResult = AllocaTmps.back().get();

350 LLVM_DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n");

351 } else if (isa(CurInst) || isa(CurInst)) {

352 CallBase &CB = *cast(&*CurInst);

353

354

355 if (isa(CB)) {

357 ++CurInst;

358 continue;

359 }

360

361

363 LLVM_DEBUG(dbgs() << "Found inline asm, can not evaluate.\n");

364 return false;

365 }

366

368 if (MemSetInst *MSI = dyn_cast(II)) {

369 if (MSI->isVolatile()) {

370 LLVM_DEBUG(dbgs() << "Can not optimize a volatile memset "

371 << "intrinsic.\n");

372 return false;

373 }

374

375 auto *LenC = dyn_cast(getVal(MSI->getLength()));

376 if (!LenC) {

377 LLVM_DEBUG(dbgs() << "Memset with unknown length.\n");

378 return false;

379 }

380

383 Ptr = cast(Ptr->stripAndAccumulateConstantOffsets(

384 DL, Offset, true));

385 auto *GV = dyn_cast(Ptr);

386 if (!GV) {

388 return false;

389 }

390

391 Constant *Val = getVal(MSI->getValue());

392

393

394 if (!Val->isNullValue() || MutatedMemory.contains(GV) ||

397 APInt Len = LenC->getValue();

398 if (Len.ugt(64 * 1024)) {

399 LLVM_DEBUG(dbgs() << "Not evaluating large memset of size "

400 << Len << "\n");

401 return false;

402 }

403

404 while (Len != 0) {

406 if (DestVal != Val) {

407 LLVM_DEBUG(dbgs() << "Memset is not a no-op at offset "

408 << Offset << " of " << *GV << ".\n");

409 return false;

410 }

413 }

414 }

415

417 ++CurInst;

418 continue;

419 }

420

421 if (II->isLifetimeStartOrEnd()) {

422 LLVM_DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");

423 ++CurInst;

424 continue;

425 }

426

427 if (II->getIntrinsicID() == Intrinsic::invariant_start) {

428

429

430 if (->use_empty()) {

432 << "Found unused invariant_start. Can't evaluate.\n");

433 return false;

434 }

436 Value *PtrArg = getVal(II->getArgOperand(1));

440 if ( Size ->isMinusOne() &&

441 Size->getValue().getLimitedValue() >=

442 DL.getTypeStoreSize(ElemTy)) {

443 Invariants.insert(GV);

444 LLVM_DEBUG(dbgs() << "Found a global var that is an invariant: "

445 << *GV << "\n");

446 } else {

448 << "Found a global var, but can not treat it as an "

449 "invariant.\n");

450 }

451 }

452

453 ++CurInst;

454 continue;

455 } else if (II->getIntrinsicID() == Intrinsic::assume) {

456 LLVM_DEBUG(dbgs() << "Skipping assume intrinsic.\n");

457 ++CurInst;

458 continue;

459 } else if (II->getIntrinsicID() == Intrinsic::sideeffect) {

460 LLVM_DEBUG(dbgs() << "Skipping sideeffect intrinsic.\n");

461 ++CurInst;

462 continue;

463 } else if (II->getIntrinsicID() == Intrinsic::pseudoprobe) {

464 LLVM_DEBUG(dbgs() << "Skipping pseudoprobe intrinsic.\n");

465 ++CurInst;

466 continue;

467 } else {

469

470

471

472 if (Stripped != &*CurInst) {

473 InstResult = getVal(Stripped);

474 }

475 if (InstResult) {

477 << "Stripped pointer casts for alias analysis for "

478 "intrinsic call.\n");

479 StrippedPointerCastsForAliasAnalysis = true;

481 } else {

482 LLVM_DEBUG(dbgs() << "Unknown intrinsic. Cannot evaluate.\n");

483 return false;

484 }

485 }

486 }

487

488 if (!InstResult) {

489

491 Function *Callee = getCalleeWithFormalArgs(CB, Formals);

492 if (!Callee || Callee->isInterposable()) {

493 LLVM_DEBUG(dbgs() << "Can not resolve function pointer.\n");

494 return false;

495 }

496

497 if (Callee->isDeclaration()) {

498

500 InstResult = C;

501 LLVM_DEBUG(dbgs() << "Constant folded function call. Result: "

502 << *InstResult << "\n");

503 } else {

504 LLVM_DEBUG(dbgs() << "Can not constant fold function call.\n");

505 return false;

506 }

507 } else {

508 if (Callee->getFunctionType()->isVarArg()) {

510 << "Can not constant fold vararg function call.\n");

511 return false;

512 }

513

515

516 ValueStack.emplace_back();

518 LLVM_DEBUG(dbgs() << "Failed to evaluate function.\n");

519 return false;

520 }

521 ValueStack.pop_back();

522 InstResult = RetVal;

523 if (InstResult) {

524 LLVM_DEBUG(dbgs() << "Successfully evaluated function. Result: "

525 << *InstResult << "\n\n");

526 } else {

528 << "Successfully evaluated function. Result: 0\n\n");

529 }

530 }

531 }

532 } else if (CurInst->isTerminator()) {

533 LLVM_DEBUG(dbgs() << "Found a terminator instruction.\n");

534

535 if (BranchInst *BI = dyn_cast(CurInst)) {

536 if (BI->isUnconditional()) {

537 NextBB = BI->getSuccessor(0);

538 } else {

540 dyn_cast(getVal(BI->getCondition()));

541 if ( Cond ) return false;

542

543 NextBB = BI->getSuccessor( Cond ->getZExtValue());

544 }

545 } else if (SwitchInst *SI = dyn_cast(CurInst)) {

547 dyn_cast(getVal(SI->getCondition()));

548 if (!Val) return false;

549 NextBB = SI->findCaseValue(Val)->getCaseSuccessor();

550 } else if (IndirectBrInst *IBI = dyn_cast(CurInst)) {

552 if (BlockAddress *BA = dyn_cast(Val))

553 NextBB = BA->getBasicBlock();

554 else

555 return false;

556 } else if (isa(CurInst)) {

557 NextBB = nullptr;

558 } else {

559

561 return false;

562 }

563

564

565 LLVM_DEBUG(dbgs() << "Successfully evaluated block.\n");

566 return true;

567 } else {

569 for (Value *Op : CurInst->operands())

572 if (!InstResult) {

573 LLVM_DEBUG(dbgs() << "Cannot fold instruction: " << *CurInst << "\n");

574 return false;

575 }

576 LLVM_DEBUG(dbgs() << "Folded instruction " << *CurInst << " to "

577 << *InstResult << "\n");

578 }

579

580 if (!CurInst->use_empty()) {

582 setVal(&*CurInst, InstResult);

583 }

584

585

586 if (InvokeInst *II = dyn_cast(CurInst)) {

587 NextBB = II->getNormalDest();

588 LLVM_DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n");

589 return true;

590 }

591

592

593 ++CurInst;

594 }

595}

596

597

598

599

602 assert(ActualArgs.size() == F->arg_size() && "wrong number of arguments");

603

604

605

607 return false;

608

609 CallStack.push_back(F);

610

611

613 setVal(&Arg, ActualArgs[ArgNo]);

614

615

616

617

619

620

622

624

625 while (true) {

626 BasicBlock *NextBB = nullptr;

627 LLVM_DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");

628

629 bool StrippedPointerCastsForAliasAnalysis = false;

630

631 if (!EvaluateBlock(CurInst, NextBB, StrippedPointerCastsForAliasAnalysis))

632 return false;

633

634 if (!NextBB) {

635

636

639

640

641

642

643

644 if (StrippedPointerCastsForAliasAnalysis &&

646 return false;

647 }

649 }

650 CallStack.pop_back();

651 return true;

652 }

653

654

655

656

657 if (!ExecutedBlocks.insert(NextBB).second)

658 return false;

659

660

661

662

664 for (CurInst = NextBB->begin();

665 (PN = dyn_cast(CurInst)); ++CurInst)

667

668

669 CurBB = NextBB;

670 }

671}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

This file contains the declarations for the subclasses of Constant, which represent the different fla...

This file defines the DenseMap class.

static bool isSimpleEnoughValueToCommitHelper(Constant *C, SmallPtrSetImpl< Constant * > &SimpleConstants, const DataLayout &DL)

Return true if the specified constant can be handled by the code generator.

static bool isSimpleEnoughValueToCommit(Constant *C, SmallPtrSetImpl< Constant * > &SimpleConstants, const DataLayout &DL)

static Function * getFunction(Constant *C)

uint64_t IntrinsicInst * II

const SmallVectorImpl< MachineOperand > & Cond

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

This file defines the SmallPtrSet class.

This file defines the SmallVector class.

Class for arbitrary precision integers.

an instruction to allocate memory on the stack

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

InstListType::iterator iterator

Instruction iterators...

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

The address of a basic block.

Conditional or Unconditional Branch instruction.

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

bool isInlineAsm() const

Check if this call is an inline asm statement.

Value * getCalledOperand() const

FunctionType * getFunctionType() const

iterator_range< User::op_iterator > args()

Iteration adapter for range-for loops.

static bool isBitOrNoopPointerCastable(Type *SrcTy, Type *DestTy, const DataLayout &DL)

Check whether a bitcast, inttoptr, or ptrtoint cast between these types is valid and a no-op.

static Constant * get(ArrayType *T, ArrayRef< Constant * > V)

A constant value that is initialized with an expression using other constant values.

static Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)

static Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)

static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)

This is the shared class of boolean and integer constants.

static Constant * get(StructType *T, ArrayRef< Constant * > V)

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

This is an important base class in LLVM.

const Constant * stripPointerCasts() const

bool isNullValue() const

Return true if this is the value that would be returned by getNullValue.

This class represents an Operation in the Expression.

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

bool EvaluateFunction(Function *F, Constant *&RetVal, const SmallVectorImpl< Constant * > &ActualArgs)

Evaluate a call to function F, returning true if successful, false if we can't evaluate it.

@ InternalLinkage

Rename collisions when linking (static functions).

Type * getValueType() const

const Constant * getInitializer() const

getInitializer - Return the initializer for this global variable.

bool hasUniqueInitializer() const

hasUniqueInitializer - Whether the global variable has an initializer, and any changes made to the in...

bool hasDefinitiveInitializer() const

hasDefinitiveInitializer - Whether the global variable has an initializer, and any other instances of...

Indirect Branch Instruction.

A wrapper class for inspecting calls to intrinsic functions.

An instruction for reading from memory.

This class wraps the llvm.memset and llvm.memset.inline intrinsics.

Value * getIncomingValueForBlock(const BasicBlock *BB) const

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

Value * getReturnValue() const

Convenience accessor. Returns null if there is no return value.

A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...

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

void push_back(const T &Elt)

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

An instruction for storing to memory.

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

bool isPointerTy() const

True if this is an instance of PointerType.

bool isIntegerTy() const

True if this is an instance of IntegerType.

bool isVoidTy() const

Return true if this is 'void'.

static UndefValue * get(Type *T)

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

Value * getOperand(unsigned i) const

unsigned getNumOperands() const

LLVM Value Representation.

Type * getType() const

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

const Value * stripPointerCasts() const

Strip off pointer casts, all-zero GEPs and address space casts.

StringRef getName() const

Return a constant reference to the value's name.

const Value * stripPointerCastsForAliasAnalysis() const

Strip off pointer casts, all-zero GEPs, single-argument phi nodes and invariant group info.

@ C

The default llvm calling convention, compatible with C.

This is an optimization pass for GlobalISel generic memory operations.

auto enumerate(FirstRange &&First, RestRanges &&...Rest)

Given two or more input ranges, returns a new range whose values are tuples (A, B,...

Constant * ConstantFoldCall(const CallBase *Call, Function *F, ArrayRef< Constant * > Operands, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)

ConstantFoldCall - Attempt to constant fold a call to the specified function with the specified argum...

Constant * ConstantFoldConstant(const Constant *C, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)

ConstantFoldConstant - Fold the constant using the specified DataLayout.

raw_ostream & dbgs()

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

Constant * ConstantFoldInstOperands(Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)

ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.

Constant * ConstantFoldLoadFromConst(Constant *C, Type *Ty, const APInt &Offset, const DataLayout &DL)

Extract value of C at the given Offset reinterpreted as Ty.

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.