Evaluator.cpp Source File (original) (raw)

39#define DEBUG_TYPE "evaluator"

41using namespace llvm;

43static inline bool

56static bool

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

67 return true;

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

73 return false;

74 return true;

75 }

81 if (!CE)

82 return false;

83 switch (CE->getOpcode()) {

84 case Instruction::BitCast:

88 case Instruction::IntToPtr:

89 case Instruction::PtrToInt:

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

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

94 return false;

98 case Instruction::GetElementPtr:

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

101 return false;

103

104 case Instruction::Add:

105

107 return false;

109 }

110 return false;

111}

112

113static inline bool

117

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

119 return true;

120

122}

123

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

126 delete Agg;

127 Val = nullptr;

128}

129

131 const DataLayout &DL) const {

132 TypeSize TySize = DL.getTypeStoreSize(Ty);

133 const MutableValue *V = this;

135 Type *AggTy = Agg->Ty;

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

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

139 return nullptr;

140

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

142 }

143

145}

146

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

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

150 unsigned NumElements;

152 NumElements = VT->getNumElements();

154 NumElements = AT->getNumElements();

156 NumElements = ST->getNumElements();

157 else

158 return false;

159

160 MutableAggregate *MA = new MutableAggregate(Ty);

161 MA->Elements.reserve(NumElements);

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

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

164 Val = MA;

165 return true;

166}

167

168bool Evaluator::MutableValue::write(Constant *V, APInt Offset,

169 const DataLayout &DL) {

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

171 TypeSize TySize = DL.getTypeStoreSize(Ty);

172 MutableValue *MV = this;

173 while (Offset != 0 ||

176 return false;

177

179 Type *AggTy = Agg->Ty;

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

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

183 return false;

184

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

186 }

187

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

189 MV->clear();

194 else if (Ty != MVType)

196 else

197 MV->Val = V;

198 return true;

199}

200

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

203 for (const MutableValue &MV : Elements)

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

205

212}

213

214

215

216Constant *Evaluator::ComputeLoadResult(Constant *P, Type *Ty) {

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

219 DL, Offset, true));

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

222 return ComputeLoadResult(GV, Ty, Offset);

223 return nullptr;

224}

225

226Constant *Evaluator::ComputeLoadResult(GlobalVariable *GV, Type *Ty,

227 const APInt &Offset) {

228 auto It = MutatedMemory.find(GV);

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

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

231

233 return nullptr;

235}

236

239 return Fn;

240

243 return Fn;

244 return nullptr;

245}

246

248Evaluator::getCalleeWithFormalArgs(CallBase &CB,

249 SmallVectorImpl<Constant *> &Formals) {

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

253 return nullptr;

254}

255

256bool Evaluator::getFormalParams(CallBase &CB, Function *F,

257 SmallVectorImpl<Constant *> &Formals) {

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

261 return false;

262 }

263

266 return true;

267}

268

269

270

271

272

273bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB,

274 bool &StrippedPointerCastsForAliasAnalysis) {

275

276 while (true) {

277 Constant *InstResult = nullptr;

278

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

280

282 if (SI->isVolatile()) {

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

284 return false;

285 }

286 Constant *Ptr = getVal(SI->getOperand(1));

288 if (Ptr != FoldedPtr) {

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

290 Ptr = FoldedPtr;

292 }

293

294 APInt Offset(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);

296 DL, Offset, true));

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

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

302 return false;

303 }

304

305

306

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

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

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

311 return false;

312 }

313

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

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

316 return false;

318 if (LI->isVolatile()) {

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

321 return false;

322 }

323

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

326 if (Ptr != FoldedPtr) {

327 Ptr = FoldedPtr;

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

329 "folding: "

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

331 }

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

333 if (!InstResult) {

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

336 "\n");

337 return false;

338 }

339

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

342 if (AI->isArrayAllocation()) {

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

344 return false;

345 }

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

347 AllocaTmps.push_back(std::make_unique(

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

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

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

355

356

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

359 return false;

360 }

361

364 if (MSI->isVolatile()) {

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

366 << "intrinsic.\n");

367 return false;

368 }

369

371 if (!LenC) {

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

373 return false;

374 }

375

376 Constant *Ptr = getVal(MSI->getDest());

377 APInt Offset(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);

379 DL, Offset, true));

381 if (!GV) {

383 return false;

384 }

385

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

387

388

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

392 APInt Len = LenC->getValue();

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

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

395 << Len << "\n");

396 return false;

397 }

398

399 while (Len != 0) {

401 if (DestVal != Val) {

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

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

404 return false;

405 }

408 }

409 }

410

412 ++CurInst;

413 continue;

414 }

415

416 if (II->isLifetimeStartOrEnd()) {

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

418 ++CurInst;

419 continue;

420 }

421

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

423

424

425 if (->use_empty()) {

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

428 return false;

429 }

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

435 if ( Size ->isMinusOne() &&

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

437 DL.getTypeStoreSize(ElemTy)) {

438 Invariants.insert(GV);

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

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

441 } else {

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

444 "invariant.\n");

445 }

446 }

447

448 ++CurInst;

449 continue;

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

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

452 ++CurInst;

453 continue;

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

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

456 ++CurInst;

457 continue;

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

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

460 ++CurInst;

461 continue;

462 } else {

463 Value *Stripped = CurInst->stripPointerCastsForAliasAnalysis();

464

465

466

467 if (Stripped != &*CurInst) {

468 InstResult = getVal(Stripped);

469 }

470 if (InstResult) {

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

473 "intrinsic call.\n");

474 StrippedPointerCastsForAliasAnalysis = true;

476 } else {

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

478 return false;

479 }

480 }

481 }

482

483 if (!InstResult) {

484

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

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

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

489 return false;

490 }

491

492 if (Callee->isDeclaration()) {

493

495 InstResult = C;

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

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

498 } else {

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

500 return false;

501 }

502 } else {

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

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

506 return false;

507 }

508

510

511 ValueStack.emplace_back();

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

514 return false;

515 }

516 ValueStack.pop_back();

517 InstResult = RetVal;

518 if (InstResult) {

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

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

521 } else {

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

524 }

525 }

526 }

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

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

529

531 if (BI->isUnconditional()) {

532 NextBB = BI->getSuccessor(0);

533 } else {

534 ConstantInt *Cond =

536 if ( Cond ) return false;

537

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

539 }

541 ConstantInt *Val =

543 if (!Val) return false;

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

548 NextBB = BA->getBasicBlock();

549 else

550 return false;

552 NextBB = nullptr;

553 } else {

554

556 return false;

557 }

558

559

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

561 return true;

562 } else {

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

565 Ops.push_back(getVal(Op));

567 if (!InstResult) {

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

569 return false;

570 }

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

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

573 }

574

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

577 setVal(&*CurInst, InstResult);

578 }

579

580

582 NextBB = II->getNormalDest();

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

584 return true;

585 }

586

587

588 ++CurInst;

589 }

590}

591

592

593

594

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

598

599

600

602 return false;

603

604 CallStack.push_back(F);

605

606

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

609

610

611

612

614

615

617

619

620 while (true) {

621 BasicBlock *NextBB = nullptr;

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

623

624 bool StrippedPointerCastsForAliasAnalysis = false;

625

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

627 return false;

628

629 if (!NextBB) {

630

631

634

635

636

637

638

639 if (StrippedPointerCastsForAliasAnalysis &&

641 return false;

642 }

644 }

645 CallStack.pop_back();

646 return true;

647 }

648

649

650

651

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

653 return false;

654

655

656

657

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

662

663

664 CurBB = NextBB;

665 }

666}

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

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.

Definition Evaluator.cpp:57

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

Definition Evaluator.cpp:114

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

uint64_t IntrinsicInst * II

const SmallVectorImpl< MachineOperand > & Cond

This file defines the SmallPtrSet class.

This file defines the SmallVector class.

static Function * getFunction(FunctionType *Ty, const Twine &Name, Module *M)

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

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 LLVM_ABI 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 LLVM_ABI Constant * get(ArrayType *T, ArrayRef< Constant * > V)

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

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

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

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

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

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

This is an important base class in LLVM.

const Constant * stripPointerCasts() const

LLVM_ABI bool isNullValue() const

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

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.

Definition Evaluator.cpp:595

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

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)

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

LLVM_ABI const Value * stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset, bool AllowNonInbounds, bool AllowInvariantGroup=false, function_ref< bool(Value &Value, APInt &Offset)> ExternalAnalysis=nullptr, bool LookThroughIntToPtr=false) const

Accumulate the constant offset this value has compared to a base pointer.

LLVM_ABI const Value * stripPointerCasts() const

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

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

static constexpr bool isKnownLE(const FixedOrScalableQuantity &LHS, const FixedOrScalableQuantity &RHS)

@ C

The default llvm calling convention, compatible with C.

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

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

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

decltype(auto) dyn_cast(const From &Val)

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

auto dyn_cast_if_present(const Y &Val)

dyn_cast_if_present - Functionally identical to dyn_cast, except that a null (or none in the case ...

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

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

ConstantFoldConstant - Fold the constant using the specified DataLayout.

LLVM_ABI raw_ostream & dbgs()

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

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

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

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

DWARFExpression::Operation Op

decltype(auto) cast(const From &Val)

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

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

Returns true if Element is found in Range.

LLVM_ABI Constant * ConstantFoldInstOperands(const 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.