1 //===- Evaluator.cpp - LLVM IR evaluator ----------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Function evaluator for LLVM IR.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Transforms/Utils/Evaluator.h"
15 #include "llvm/Analysis/ConstantFolding.h"
16 #include "llvm/IR/BasicBlock.h"
17 #include "llvm/IR/CallSite.h"
18 #include "llvm/IR/Constants.h"
19 #include "llvm/IR/DataLayout.h"
20 #include "llvm/IR/DerivedTypes.h"
21 #include "llvm/IR/DiagnosticPrinter.h"
22 #include "llvm/IR/GlobalVariable.h"
23 #include "llvm/IR/Instructions.h"
24 #include "llvm/IR/IntrinsicInst.h"
25 #include "llvm/IR/Operator.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/raw_ostream.h"
29 #define DEBUG_TYPE "evaluator"
34 isSimpleEnoughValueToCommit(Constant *C,
35 SmallPtrSetImpl<Constant *> &SimpleConstants,
36 const DataLayout &DL);
38 /// Return true if the specified constant can be handled by the code generator.
39 /// We don't want to generate something like:
41 /// because the code generator doesn't have a relocation that can handle that.
43 /// This function should be called if C was not found (but just got inserted)
44 /// in SimpleConstants to avoid having to rescan the same constants all the
47 isSimpleEnoughValueToCommitHelper(Constant *C,
48 SmallPtrSetImpl<Constant *> &SimpleConstants,
49 const DataLayout &DL) {
50 // Simple global addresses are supported, do not allow dllimport or
51 // thread-local globals.
52 if (auto *GV = dyn_cast<GlobalValue>(C))
53 return !GV->hasDLLImportStorageClass() && !GV->isThreadLocal();
55 // Simple integer, undef, constant aggregate zero, etc are all supported.
56 if (C->getNumOperands() == 0 || isa<BlockAddress>(C))
59 // Aggregate values are safe if all their elements are.
60 if (isa<ConstantAggregate>(C)) {
61 for (Value *Op : C->operands())
62 if (!isSimpleEnoughValueToCommit(cast<Constant>(Op), SimpleConstants, DL))
67 // We don't know exactly what relocations are allowed in constant expressions,
68 // so we allow &global+constantoffset, which is safe and uniformly supported
70 ConstantExpr *CE = cast<ConstantExpr>(C);
71 switch (CE->getOpcode()) {
72 case Instruction::BitCast:
73 // Bitcast is fine if the casted value is fine.
74 return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
76 case Instruction::IntToPtr:
77 case Instruction::PtrToInt:
78 // int <=> ptr is fine if the int type is the same size as the
80 if (DL.getTypeSizeInBits(CE->getType()) !=
81 DL.getTypeSizeInBits(CE->getOperand(0)->getType()))
83 return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
85 // GEP is fine if it is simple + constant offset.
86 case Instruction::GetElementPtr:
87 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
88 if (!isa<ConstantInt>(CE->getOperand(i)))
90 return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
92 case Instruction::Add:
93 // We allow simple+cst.
94 if (!isa<ConstantInt>(CE->getOperand(1)))
96 return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
102 isSimpleEnoughValueToCommit(Constant *C,
103 SmallPtrSetImpl<Constant *> &SimpleConstants,
104 const DataLayout &DL) {
105 // If we already checked this constant, we win.
106 if (!SimpleConstants.insert(C).second)
108 // Check the constant.
109 return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, DL);
112 /// Return true if this constant is simple enough for us to understand. In
113 /// particular, if it is a cast to anything other than from one pointer type to
114 /// another pointer type, we punt. We basically just support direct accesses to
115 /// globals and GEP's of globals. This should be kept up to date with
117 static bool isSimpleEnoughPointerToCommit(Constant *C) {
118 // Conservatively, avoid aggregate types. This is because we don't
119 // want to worry about them partially overlapping other stores.
120 if (!cast<PointerType>(C->getType())->getElementType()->isSingleValueType())
123 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C))
124 // Do not allow weak/*_odr/linkonce linkage or external globals.
125 return GV->hasUniqueInitializer();
127 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
128 // Handle a constantexpr gep.
129 if (CE->getOpcode() == Instruction::GetElementPtr &&
130 isa<GlobalVariable>(CE->getOperand(0)) &&
131 cast<GEPOperator>(CE)->isInBounds()) {
132 GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
133 // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
135 if (!GV->hasUniqueInitializer())
138 // The first index must be zero.
139 ConstantInt *CI = dyn_cast<ConstantInt>(*std::next(CE->op_begin()));
140 if (!CI || !CI->isZero()) return false;
142 // The remaining indices must be compile-time known integers within the
143 // notional bounds of the corresponding static array types.
144 if (!CE->isGEPWithNoNotionalOverIndexing())
147 return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE);
149 // A constantexpr bitcast from a pointer to another pointer is a no-op,
150 // and we know how to evaluate it by moving the bitcast from the pointer
151 // operand to the value operand.
152 } else if (CE->getOpcode() == Instruction::BitCast &&
153 isa<GlobalVariable>(CE->getOperand(0))) {
154 // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
156 return cast<GlobalVariable>(CE->getOperand(0))->hasUniqueInitializer();
163 /// Return the value that would be computed by a load from P after the stores
164 /// reflected by 'memory' have been performed. If we can't decide, return null.
165 Constant *Evaluator::ComputeLoadResult(Constant *P) {
166 // If this memory location has been recently stored, use the stored value: it
167 // is the most up-to-date.
168 DenseMap<Constant*, Constant*>::const_iterator I = MutatedMemory.find(P);
169 if (I != MutatedMemory.end()) return I->second;
172 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) {
173 if (GV->hasDefinitiveInitializer())
174 return GV->getInitializer();
178 // Handle a constantexpr getelementptr.
179 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(P))
180 if (CE->getOpcode() == Instruction::GetElementPtr &&
181 isa<GlobalVariable>(CE->getOperand(0))) {
182 GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
183 if (GV->hasDefinitiveInitializer())
184 return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE);
187 return nullptr; // don't know how to evaluate.
190 /// Evaluate all instructions in block BB, returning true if successful, false
191 /// if we can't evaluate it. NewBB returns the next BB that control flows into,
192 /// or null upon return.
193 bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst,
194 BasicBlock *&NextBB) {
195 // This is the main evaluation loop.
197 Constant *InstResult = nullptr;
199 DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n");
201 if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
202 if (!SI->isSimple()) {
203 DEBUG(dbgs() << "Store is not simple! Can not evaluate.\n");
204 return false; // no volatile/atomic accesses.
206 Constant *Ptr = getVal(SI->getOperand(1));
207 if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI)) {
208 DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr);
210 DEBUG(dbgs() << "; To: " << *Ptr << "\n");
212 if (!isSimpleEnoughPointerToCommit(Ptr)) {
213 // If this is too complex for us to commit, reject it.
214 DEBUG(dbgs() << "Pointer is too complex for us to evaluate store.");
218 Constant *Val = getVal(SI->getOperand(0));
220 // If this might be too difficult for the backend to handle (e.g. the addr
221 // of one global variable divided by another) then we can't commit it.
222 if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)) {
223 DEBUG(dbgs() << "Store value is too complex to evaluate store. " << *Val
228 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) {
229 if (CE->getOpcode() == Instruction::BitCast) {
230 DEBUG(dbgs() << "Attempting to resolve bitcast on constant ptr.\n");
231 // If we're evaluating a store through a bitcast, then we need
232 // to pull the bitcast off the pointer type and push it onto the
234 Ptr = CE->getOperand(0);
236 Type *NewTy = cast<PointerType>(Ptr->getType())->getElementType();
238 // In order to push the bitcast onto the stored value, a bitcast
239 // from NewTy to Val's type must be legal. If it's not, we can try
240 // introspecting NewTy to find a legal conversion.
241 while (!Val->getType()->canLosslesslyBitCastTo(NewTy)) {
242 // If NewTy is a struct, we can convert the pointer to the struct
243 // into a pointer to its first member.
244 // FIXME: This could be extended to support arrays as well.
245 if (StructType *STy = dyn_cast<StructType>(NewTy)) {
246 NewTy = STy->getTypeAtIndex(0U);
248 IntegerType *IdxTy = IntegerType::get(NewTy->getContext(), 32);
249 Constant *IdxZero = ConstantInt::get(IdxTy, 0, false);
250 Constant * const IdxList[] = {IdxZero, IdxZero};
252 Ptr = ConstantExpr::getGetElementPtr(nullptr, Ptr, IdxList);
253 if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI))
256 // If we can't improve the situation by introspecting NewTy,
257 // we have to give up.
259 DEBUG(dbgs() << "Failed to bitcast constant ptr, can not "
265 // If we found compatible types, go ahead and push the bitcast
266 // onto the stored value.
267 Val = ConstantExpr::getBitCast(Val, NewTy);
269 DEBUG(dbgs() << "Evaluated bitcast: " << *Val << "\n");
273 MutatedMemory[Ptr] = Val;
274 } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) {
275 InstResult = ConstantExpr::get(BO->getOpcode(),
276 getVal(BO->getOperand(0)),
277 getVal(BO->getOperand(1)));
278 DEBUG(dbgs() << "Found a BinaryOperator! Simplifying: " << *InstResult
280 } else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) {
281 InstResult = ConstantExpr::getCompare(CI->getPredicate(),
282 getVal(CI->getOperand(0)),
283 getVal(CI->getOperand(1)));
284 DEBUG(dbgs() << "Found a CmpInst! Simplifying: " << *InstResult
286 } else if (CastInst *CI = dyn_cast<CastInst>(CurInst)) {
287 InstResult = ConstantExpr::getCast(CI->getOpcode(),
288 getVal(CI->getOperand(0)),
290 DEBUG(dbgs() << "Found a Cast! Simplifying: " << *InstResult
292 } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) {
293 InstResult = ConstantExpr::getSelect(getVal(SI->getOperand(0)),
294 getVal(SI->getOperand(1)),
295 getVal(SI->getOperand(2)));
296 DEBUG(dbgs() << "Found a Select! Simplifying: " << *InstResult
298 } else if (auto *EVI = dyn_cast<ExtractValueInst>(CurInst)) {
299 InstResult = ConstantExpr::getExtractValue(
300 getVal(EVI->getAggregateOperand()), EVI->getIndices());
301 DEBUG(dbgs() << "Found an ExtractValueInst! Simplifying: " << *InstResult
303 } else if (auto *IVI = dyn_cast<InsertValueInst>(CurInst)) {
304 InstResult = ConstantExpr::getInsertValue(
305 getVal(IVI->getAggregateOperand()),
306 getVal(IVI->getInsertedValueOperand()), IVI->getIndices());
307 DEBUG(dbgs() << "Found an InsertValueInst! Simplifying: " << *InstResult
309 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) {
310 Constant *P = getVal(GEP->getOperand(0));
311 SmallVector<Constant*, 8> GEPOps;
312 for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end();
314 GEPOps.push_back(getVal(*i));
316 ConstantExpr::getGetElementPtr(GEP->getSourceElementType(), P, GEPOps,
317 cast<GEPOperator>(GEP)->isInBounds());
318 DEBUG(dbgs() << "Found a GEP! Simplifying: " << *InstResult
320 } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) {
322 if (!LI->isSimple()) {
323 DEBUG(dbgs() << "Found a Load! Not a simple load, can not evaluate.\n");
324 return false; // no volatile/atomic accesses.
327 Constant *Ptr = getVal(LI->getOperand(0));
328 if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI)) {
330 DEBUG(dbgs() << "Found a constant pointer expression, constant "
331 "folding: " << *Ptr << "\n");
333 InstResult = ComputeLoadResult(Ptr);
335 DEBUG(dbgs() << "Failed to compute load result. Can not evaluate load."
337 return false; // Could not evaluate load.
340 DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n");
341 } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) {
342 if (AI->isArrayAllocation()) {
343 DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n");
344 return false; // Cannot handle array allocs.
346 Type *Ty = AI->getAllocatedType();
347 AllocaTmps.push_back(
348 make_unique<GlobalVariable>(Ty, false, GlobalValue::InternalLinkage,
349 UndefValue::get(Ty), AI->getName()));
350 InstResult = AllocaTmps.back().get();
351 DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n");
352 } else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) {
353 CallSite CS(&*CurInst);
355 // Debug info can safely be ignored here.
356 if (isa<DbgInfoIntrinsic>(CS.getInstruction())) {
357 DEBUG(dbgs() << "Ignoring debug info.\n");
362 // Cannot handle inline asm.
363 if (isa<InlineAsm>(CS.getCalledValue())) {
364 DEBUG(dbgs() << "Found inline asm, can not evaluate.\n");
368 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
369 if (MemSetInst *MSI = dyn_cast<MemSetInst>(II)) {
370 if (MSI->isVolatile()) {
371 DEBUG(dbgs() << "Can not optimize a volatile memset " <<
375 Constant *Ptr = getVal(MSI->getDest());
376 Constant *Val = getVal(MSI->getValue());
377 Constant *DestVal = ComputeLoadResult(getVal(Ptr));
378 if (Val->isNullValue() && DestVal && DestVal->isNullValue()) {
379 // This memset is a no-op.
380 DEBUG(dbgs() << "Ignoring no-op memset.\n");
386 if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
387 II->getIntrinsicID() == Intrinsic::lifetime_end) {
388 DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");
393 if (II->getIntrinsicID() == Intrinsic::invariant_start) {
394 // We don't insert an entry into Values, as it doesn't have a
395 // meaningful return value.
396 if (!II->use_empty()) {
397 DEBUG(dbgs() << "Found unused invariant_start. Can't evaluate.\n");
400 ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0));
401 Value *PtrArg = getVal(II->getArgOperand(1));
402 Value *Ptr = PtrArg->stripPointerCasts();
403 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
404 Type *ElemTy = GV->getValueType();
405 if (!Size->isMinusOne() &&
406 Size->getValue().getLimitedValue() >=
407 DL.getTypeStoreSize(ElemTy)) {
408 Invariants.insert(GV);
409 DEBUG(dbgs() << "Found a global var that is an invariant: " << *GV
412 DEBUG(dbgs() << "Found a global var, but can not treat it as an "
416 // Continue even if we do nothing.
419 } else if (II->getIntrinsicID() == Intrinsic::assume) {
420 DEBUG(dbgs() << "Skipping assume intrinsic.\n");
425 DEBUG(dbgs() << "Unknown intrinsic. Can not evaluate.\n");
429 // Resolve function pointers.
430 Function *Callee = dyn_cast<Function>(getVal(CS.getCalledValue()));
431 if (!Callee || Callee->isInterposable()) {
432 DEBUG(dbgs() << "Can not resolve function pointer.\n");
433 return false; // Cannot resolve.
436 SmallVector<Constant*, 8> Formals;
437 for (User::op_iterator i = CS.arg_begin(), e = CS.arg_end(); i != e; ++i)
438 Formals.push_back(getVal(*i));
440 if (Callee->isDeclaration()) {
441 // If this is a function we can constant fold, do it.
442 if (Constant *C = ConstantFoldCall(CS, Callee, Formals, TLI)) {
444 DEBUG(dbgs() << "Constant folded function call. Result: " <<
445 *InstResult << "\n");
447 DEBUG(dbgs() << "Can not constant fold function call.\n");
451 if (Callee->getFunctionType()->isVarArg()) {
452 DEBUG(dbgs() << "Can not constant fold vararg function call.\n");
456 Constant *RetVal = nullptr;
457 // Execute the call, if successful, use the return value.
458 ValueStack.emplace_back();
459 if (!EvaluateFunction(Callee, RetVal, Formals)) {
460 DEBUG(dbgs() << "Failed to evaluate function.\n");
463 ValueStack.pop_back();
467 DEBUG(dbgs() << "Successfully evaluated function. Result: "
468 << *InstResult << "\n\n");
470 DEBUG(dbgs() << "Successfully evaluated function. Result: 0\n\n");
473 } else if (isa<TerminatorInst>(CurInst)) {
474 DEBUG(dbgs() << "Found a terminator instruction.\n");
476 if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
477 if (BI->isUnconditional()) {
478 NextBB = BI->getSuccessor(0);
481 dyn_cast<ConstantInt>(getVal(BI->getCondition()));
482 if (!Cond) return false; // Cannot determine.
484 NextBB = BI->getSuccessor(!Cond->getZExtValue());
486 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) {
488 dyn_cast<ConstantInt>(getVal(SI->getCondition()));
489 if (!Val) return false; // Cannot determine.
490 NextBB = SI->findCaseValue(Val)->getCaseSuccessor();
491 } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) {
492 Value *Val = getVal(IBI->getAddress())->stripPointerCasts();
493 if (BlockAddress *BA = dyn_cast<BlockAddress>(Val))
494 NextBB = BA->getBasicBlock();
496 return false; // Cannot determine.
497 } else if (isa<ReturnInst>(CurInst)) {
500 // invoke, unwind, resume, unreachable.
501 DEBUG(dbgs() << "Can not handle terminator.");
502 return false; // Cannot handle this terminator.
505 // We succeeded at evaluating this block!
506 DEBUG(dbgs() << "Successfully evaluated block.\n");
509 // Did not know how to evaluate this!
510 DEBUG(dbgs() << "Failed to evaluate block due to unhandled instruction."
515 if (!CurInst->use_empty()) {
516 if (auto *FoldedInstResult = ConstantFoldConstant(InstResult, DL, TLI))
517 InstResult = FoldedInstResult;
519 setVal(&*CurInst, InstResult);
522 // If we just processed an invoke, we finished evaluating the block.
523 if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) {
524 NextBB = II->getNormalDest();
525 DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n");
529 // Advance program counter.
534 /// Evaluate a call to function F, returning true if successful, false if we
535 /// can't evaluate it. ActualArgs contains the formal arguments for the
537 bool Evaluator::EvaluateFunction(Function *F, Constant *&RetVal,
538 const SmallVectorImpl<Constant*> &ActualArgs) {
539 // Check to see if this function is already executing (recursion). If so,
540 // bail out. TODO: we might want to accept limited recursion.
541 if (is_contained(CallStack, F))
544 CallStack.push_back(F);
546 // Initialize arguments to the incoming values specified.
548 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
550 setVal(&*AI, ActualArgs[ArgNo]);
552 // ExecutedBlocks - We only handle non-looping, non-recursive code. As such,
553 // we can only evaluate any one basic block at most once. This set keeps
554 // track of what we have executed so we can detect recursive cases etc.
555 SmallPtrSet<BasicBlock*, 32> ExecutedBlocks;
557 // CurBB - The current basic block we're evaluating.
558 BasicBlock *CurBB = &F->front();
560 BasicBlock::iterator CurInst = CurBB->begin();
563 BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings.
564 DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");
566 if (!EvaluateBlock(CurInst, NextBB))
570 // Successfully running until there's no next block means that we found
571 // the return. Fill it the return value and pop the call stack.
572 ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator());
573 if (RI->getNumOperands())
574 RetVal = getVal(RI->getOperand(0));
575 CallStack.pop_back();
579 // Okay, we succeeded in evaluating this control flow. See if we have
580 // executed the new block before. If so, we have a looping function,
581 // which we cannot evaluate in reasonable time.
582 if (!ExecutedBlocks.insert(NextBB).second)
583 return false; // looped!
585 // Okay, we have never been in this block before. Check to see if there
586 // are any PHI nodes. If so, evaluate them with information about where
588 PHINode *PN = nullptr;
589 for (CurInst = NextBB->begin();
590 (PN = dyn_cast<PHINode>(CurInst)); ++CurInst)
591 setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB)));
593 // Advance to the next block.