Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Transforms/Utils/Evaluator.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- Evaluator.cpp - LLVM IR evaluator ----------------------------------===//
2
//
3
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
//
10
// Function evaluator for LLVM IR.
11
//
12
//===----------------------------------------------------------------------===//
13
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"
28
29
#define DEBUG_TYPE "evaluator"
30
31
using namespace llvm;
32
33
static inline bool
34
isSimpleEnoughValueToCommit(Constant *C,
35
                            SmallPtrSetImpl<Constant *> &SimpleConstants,
36
                            const DataLayout &DL);
37
38
/// Return true if the specified constant can be handled by the code generator.
39
/// We don't want to generate something like:
40
///   void *X = &X/42;
41
/// because the code generator doesn't have a relocation that can handle that.
42
///
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
45
/// time.
46
static bool
47
isSimpleEnoughValueToCommitHelper(Constant *C,
48
                                  SmallPtrSetImpl<Constant *> &SimpleConstants,
49
708
                                  const DataLayout &DL) {
50
708
  // Simple global addresses are supported, do not allow dllimport or
51
708
  // thread-local globals.
52
708
  if (auto *GV = dyn_cast<GlobalValue>(C))
53
214
    
return !GV->hasDLLImportStorageClass() && 214
!GV->isThreadLocal()210
;
54
494
55
494
  // Simple integer, undef, constant aggregate zero, etc are all supported.
56
494
  
if (494
C->getNumOperands() == 0 || 494
isa<BlockAddress>(C)257
)
57
237
    return true;
58
257
59
257
  // Aggregate values are safe if all their elements are.
60
257
  
if (257
isa<ConstantAggregate>(C)257
) {
61
1
    for (Value *Op : C->operands())
62
2
      
if (2
!isSimpleEnoughValueToCommit(cast<Constant>(Op), SimpleConstants, DL)2
)
63
0
        return false;
64
1
    return true;
65
1
  }
66
256
67
256
  // We don't know exactly what relocations are allowed in constant expressions,
68
256
  // so we allow &global+constantoffset, which is safe and uniformly supported
69
256
  // across targets.
70
256
  ConstantExpr *CE = cast<ConstantExpr>(C);
71
256
  switch (CE->getOpcode()) {
72
49
  case Instruction::BitCast:
73
49
    // Bitcast is fine if the casted value is fine.
74
49
    return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
75
256
76
4
  case Instruction::IntToPtr:
77
4
  case Instruction::PtrToInt:
78
4
    // int <=> ptr is fine if the int type is the same size as the
79
4
    // pointer type.
80
4
    if (DL.getTypeSizeInBits(CE->getType()) !=
81
4
        DL.getTypeSizeInBits(CE->getOperand(0)->getType()))
82
2
      return false;
83
2
    return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
84
2
85
2
  // GEP is fine if it is simple + constant offset.
86
201
  case Instruction::GetElementPtr:
87
649
    for (unsigned i = 1, e = CE->getNumOperands(); 
i != e649
;
++i448
)
88
448
      
if (448
!isa<ConstantInt>(CE->getOperand(i))448
)
89
0
        return false;
90
201
    return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
91
201
92
0
  case Instruction::Add:
93
0
    // We allow simple+cst.
94
0
    if (!isa<ConstantInt>(CE->getOperand(1)))
95
0
      return false;
96
0
    return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
97
2
  }
98
2
  return false;
99
2
}
100
101
static inline bool
102
isSimpleEnoughValueToCommit(Constant *C,
103
                            SmallPtrSetImpl<Constant *> &SimpleConstants,
104
1.64k
                            const DataLayout &DL) {
105
1.64k
  // If we already checked this constant, we win.
106
1.64k
  if (!SimpleConstants.insert(C).second)
107
937
    return true;
108
708
  // Check the constant.
109
708
  return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, DL);
110
708
}
111
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
116
/// CommitValueTo.
117
1.40k
static bool isSimpleEnoughPointerToCommit(Constant *C) {
118
1.40k
  // Conservatively, avoid aggregate types. This is because we don't
119
1.40k
  // want to worry about them partially overlapping other stores.
120
1.40k
  if (!cast<PointerType>(C->getType())->getElementType()->isSingleValueType())
121
0
    return false;
122
1.40k
123
1.40k
  
if (GlobalVariable *1.40k
GV1.40k
= dyn_cast<GlobalVariable>(C))
124
1.40k
    // Do not allow weak/*_odr/linkonce linkage or external globals.
125
109
    return GV->hasUniqueInitializer();
126
1.29k
127
1.29k
  
if (ConstantExpr *1.29k
CE1.29k
= dyn_cast<ConstantExpr>(C)) {
128
1.29k
    // Handle a constantexpr gep.
129
1.29k
    if (CE->getOpcode() == Instruction::GetElementPtr &&
130
1.29k
        isa<GlobalVariable>(CE->getOperand(0)) &&
131
1.29k
        
cast<GEPOperator>(CE)->isInBounds()1.29k
) {
132
1.29k
      GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
133
1.29k
      // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
134
1.29k
      // external globals.
135
1.29k
      if (!GV->hasUniqueInitializer())
136
2
        return false;
137
1.28k
138
1.28k
      // The first index must be zero.
139
1.28k
      ConstantInt *CI = dyn_cast<ConstantInt>(*std::next(CE->op_begin()));
140
1.28k
      if (
!CI || 1.28k
!CI->isZero()1.28k
)
return false0
;
141
1.28k
142
1.28k
      // The remaining indices must be compile-time known integers within the
143
1.28k
      // notional bounds of the corresponding static array types.
144
1.28k
      
if (1.28k
!CE->isGEPWithNoNotionalOverIndexing()1.28k
)
145
0
        return false;
146
1.28k
147
1.28k
      return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE);
148
1.28k
149
1.28k
    // A constantexpr bitcast from a pointer to another pointer is a no-op,
150
1.28k
    // and we know how to evaluate it by moving the bitcast from the pointer
151
1.28k
    // operand to the value operand.
152
1
    } else 
if (1
CE->getOpcode() == Instruction::BitCast &&
153
1
               
isa<GlobalVariable>(CE->getOperand(0))1
) {
154
1
      // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
155
1
      // external globals.
156
1
      return cast<GlobalVariable>(CE->getOperand(0))->hasUniqueInitializer();
157
1
    }
158
0
  }
159
0
160
0
  return false;
161
0
}
162
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
279
Constant *Evaluator::ComputeLoadResult(Constant *P) {
166
279
  // If this memory location has been recently stored, use the stored value: it
167
279
  // is the most up-to-date.
168
279
  DenseMap<Constant*, Constant*>::const_iterator I = MutatedMemory.find(P);
169
279
  if (
I != MutatedMemory.end()279
)
return I->second207
;
170
72
171
72
  // Access it.
172
72
  
if (GlobalVariable *72
GV72
= dyn_cast<GlobalVariable>(P)) {
173
47
    if (GV->hasDefinitiveInitializer())
174
35
      return GV->getInitializer();
175
12
    return nullptr;
176
12
  }
177
25
178
25
  // Handle a constantexpr getelementptr.
179
25
  
if (ConstantExpr *25
CE25
= dyn_cast<ConstantExpr>(P))
180
22
    
if (22
CE->getOpcode() == Instruction::GetElementPtr &&
181
22
        
isa<GlobalVariable>(CE->getOperand(0))22
) {
182
22
      GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
183
22
      if (GV->hasDefinitiveInitializer())
184
18
        return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE);
185
7
    }
186
7
187
7
  return nullptr;  // don't know how to evaluate.
188
7
}
189
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
1.56k
                              BasicBlock *&NextBB) {
195
1.56k
  // This is the main evaluation loop.
196
5.52k
  while (
15.52k
) {
197
5.52k
    Constant *InstResult = nullptr;
198
5.52k
199
5.52k
    DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n");
200
5.52k
201
5.52k
    if (StoreInst *
SI5.52k
= dyn_cast<StoreInst>(CurInst)) {
202
1.40k
      if (
!SI->isSimple()1.40k
) {
203
0
        DEBUG(dbgs() << "Store is not simple! Can not evaluate.\n");
204
0
        return false;  // no volatile/atomic accesses.
205
0
      }
206
1.40k
      Constant *Ptr = getVal(SI->getOperand(1));
207
1.40k
      if (auto *
FoldedPtr1.40k
= ConstantFoldConstant(Ptr, DL, TLI)) {
208
1.29k
        DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr);
209
1.29k
        Ptr = FoldedPtr;
210
1.29k
        DEBUG(dbgs() << "; To: " << *Ptr << "\n");
211
1.29k
      }
212
1.40k
      if (
!isSimpleEnoughPointerToCommit(Ptr)1.40k
) {
213
9
        // If this is too complex for us to commit, reject it.
214
9
        DEBUG(dbgs() << "Pointer is too complex for us to evaluate store.");
215
9
        return false;
216
9
      }
217
1.39k
218
1.39k
      Constant *Val = getVal(SI->getOperand(0));
219
1.39k
220
1.39k
      // If this might be too difficult for the backend to handle (e.g. the addr
221
1.39k
      // of one global variable divided by another) then we can't commit it.
222
1.39k
      if (
!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)1.39k
) {
223
12
        DEBUG(dbgs() << "Store value is too complex to evaluate store. " << *Val
224
12
              << "\n");
225
12
        return false;
226
12
      }
227
1.37k
228
1.37k
      
if (ConstantExpr *1.37k
CE1.37k
= dyn_cast<ConstantExpr>(Ptr)) {
229
1.28k
        if (
CE->getOpcode() == Instruction::BitCast1.28k
) {
230
1
          DEBUG(dbgs() << "Attempting to resolve bitcast on constant ptr.\n");
231
1
          // If we're evaluating a store through a bitcast, then we need
232
1
          // to pull the bitcast off the pointer type and push it onto the
233
1
          // stored value.
234
1
          Ptr = CE->getOperand(0);
235
1
236
1
          Type *NewTy = cast<PointerType>(Ptr->getType())->getElementType();
237
1
238
1
          // In order to push the bitcast onto the stored value, a bitcast
239
1
          // from NewTy to Val's type must be legal.  If it's not, we can try
240
1
          // introspecting NewTy to find a legal conversion.
241
2
          while (
!Val->getType()->canLosslesslyBitCastTo(NewTy)2
) {
242
1
            // If NewTy is a struct, we can convert the pointer to the struct
243
1
            // into a pointer to its first member.
244
1
            // FIXME: This could be extended to support arrays as well.
245
1
            if (StructType *
STy1
= dyn_cast<StructType>(NewTy)) {
246
1
              NewTy = STy->getTypeAtIndex(0U);
247
1
248
1
              IntegerType *IdxTy = IntegerType::get(NewTy->getContext(), 32);
249
1
              Constant *IdxZero = ConstantInt::get(IdxTy, 0, false);
250
1
              Constant * const IdxList[] = {IdxZero, IdxZero};
251
1
252
1
              Ptr = ConstantExpr::getGetElementPtr(nullptr, Ptr, IdxList);
253
1
              if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI))
254
1
                Ptr = FoldedPtr;
255
1
256
1
            // If we can't improve the situation by introspecting NewTy,
257
1
            // we have to give up.
258
0
            } else {
259
0
              DEBUG(dbgs() << "Failed to bitcast constant ptr, can not "
260
0
                    "evaluate.\n");
261
0
              return false;
262
0
            }
263
1
          }
264
1
265
1
          // If we found compatible types, go ahead and push the bitcast
266
1
          // onto the stored value.
267
1
          Val = ConstantExpr::getBitCast(Val, NewTy);
268
1
269
1
          DEBUG(dbgs() << "Evaluated bitcast: " << *Val << "\n");
270
1
        }
271
1.28k
      }
272
1.37k
273
1.37k
      MutatedMemory[Ptr] = Val;
274
5.52k
    } else 
if (BinaryOperator *4.12k
BO4.12k
= dyn_cast<BinaryOperator>(CurInst)) {
275
196
      InstResult = ConstantExpr::get(BO->getOpcode(),
276
196
                                     getVal(BO->getOperand(0)),
277
196
                                     getVal(BO->getOperand(1)));
278
196
      DEBUG(dbgs() << "Found a BinaryOperator! Simplifying: " << *InstResult
279
196
            << "\n");
280
4.12k
    } else 
if (CmpInst *3.92k
CI3.92k
= dyn_cast<CmpInst>(CurInst)) {
281
96
      InstResult = ConstantExpr::getCompare(CI->getPredicate(),
282
96
                                            getVal(CI->getOperand(0)),
283
96
                                            getVal(CI->getOperand(1)));
284
96
      DEBUG(dbgs() << "Found a CmpInst! Simplifying: " << *InstResult
285
96
            << "\n");
286
3.92k
    } else 
if (CastInst *3.83k
CI3.83k
= dyn_cast<CastInst>(CurInst)) {
287
259
      InstResult = ConstantExpr::getCast(CI->getOpcode(),
288
259
                                         getVal(CI->getOperand(0)),
289
259
                                         CI->getType());
290
259
      DEBUG(dbgs() << "Found a Cast! Simplifying: " << *InstResult
291
259
            << "\n");
292
3.83k
    } else 
if (SelectInst *3.57k
SI3.57k
= dyn_cast<SelectInst>(CurInst)) {
293
8
      InstResult = ConstantExpr::getSelect(getVal(SI->getOperand(0)),
294
8
                                           getVal(SI->getOperand(1)),
295
8
                                           getVal(SI->getOperand(2)));
296
8
      DEBUG(dbgs() << "Found a Select! Simplifying: " << *InstResult
297
8
            << "\n");
298
3.57k
    } else 
if (auto *3.56k
EVI3.56k
= dyn_cast<ExtractValueInst>(CurInst)) {
299
338
      InstResult = ConstantExpr::getExtractValue(
300
338
          getVal(EVI->getAggregateOperand()), EVI->getIndices());
301
338
      DEBUG(dbgs() << "Found an ExtractValueInst! Simplifying: " << *InstResult
302
338
                   << "\n");
303
3.56k
    } else 
if (auto *3.22k
IVI3.22k
= dyn_cast<InsertValueInst>(CurInst)) {
304
175
      InstResult = ConstantExpr::getInsertValue(
305
175
          getVal(IVI->getAggregateOperand()),
306
175
          getVal(IVI->getInsertedValueOperand()), IVI->getIndices());
307
175
      DEBUG(dbgs() << "Found an InsertValueInst! Simplifying: " << *InstResult
308
175
                   << "\n");
309
3.22k
    } else 
if (GetElementPtrInst *3.05k
GEP3.05k
= dyn_cast<GetElementPtrInst>(CurInst)) {
310
742
      Constant *P = getVal(GEP->getOperand(0));
311
742
      SmallVector<Constant*, 8> GEPOps;
312
742
      for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end();
313
2.36k
           
i != e2.36k
;
++i1.62k
)
314
1.62k
        GEPOps.push_back(getVal(*i));
315
742
      InstResult =
316
742
          ConstantExpr::getGetElementPtr(GEP->getSourceElementType(), P, GEPOps,
317
742
                                         cast<GEPOperator>(GEP)->isInBounds());
318
742
      DEBUG(dbgs() << "Found a GEP! Simplifying: " << *InstResult
319
742
            << "\n");
320
3.05k
    } else 
if (LoadInst *2.30k
LI2.30k
= dyn_cast<LoadInst>(CurInst)) {
321
275
322
275
      if (
!LI->isSimple()275
) {
323
0
        DEBUG(dbgs() << "Found a Load! Not a simple load, can not evaluate.\n");
324
0
        return false;  // no volatile/atomic accesses.
325
0
      }
326
275
327
275
      Constant *Ptr = getVal(LI->getOperand(0));
328
275
      if (auto *
FoldedPtr275
= ConstantFoldConstant(Ptr, DL, TLI)) {
329
204
        Ptr = FoldedPtr;
330
204
        DEBUG(dbgs() << "Found a constant pointer expression, constant "
331
204
              "folding: " << *Ptr << "\n");
332
204
      }
333
275
      InstResult = ComputeLoadResult(Ptr);
334
275
      if (
!InstResult275
) {
335
16
        DEBUG(dbgs() << "Failed to compute load result. Can not evaluate load."
336
16
              "\n");
337
16
        return false; // Could not evaluate load.
338
16
      }
339
259
340
259
      
DEBUG259
(dbgs() << "Evaluated load: " << *InstResult << "\n");
341
2.30k
    } else 
if (AllocaInst *2.03k
AI2.03k
= dyn_cast<AllocaInst>(CurInst)) {
342
75
      if (
AI->isArrayAllocation()75
) {
343
0
        DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n");
344
0
        return false;  // Cannot handle array allocs.
345
0
      }
346
75
      Type *Ty = AI->getAllocatedType();
347
75
      AllocaTmps.push_back(
348
75
          make_unique<GlobalVariable>(Ty, false, GlobalValue::InternalLinkage,
349
75
                                      UndefValue::get(Ty), AI->getName()));
350
75
      InstResult = AllocaTmps.back().get();
351
75
      DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n");
352
2.03k
    } else 
if (1.95k
isa<CallInst>(CurInst) || 1.95k
isa<InvokeInst>(CurInst)751
) {
353
1.21k
      CallSite CS(&*CurInst);
354
1.21k
355
1.21k
      // Debug info can safely be ignored here.
356
1.21k
      if (
isa<DbgInfoIntrinsic>(CS.getInstruction())1.21k
) {
357
2
        DEBUG(dbgs() << "Ignoring debug info.\n");
358
2
        ++CurInst;
359
2
        continue;
360
2
      }
361
1.21k
362
1.21k
      // Cannot handle inline asm.
363
1.21k
      
if (1.21k
isa<InlineAsm>(CS.getCalledValue())1.21k
) {
364
4
        DEBUG(dbgs() << "Found inline asm, can not evaluate.\n");
365
4
        return false;
366
4
      }
367
1.21k
368
1.21k
      
if (IntrinsicInst *1.21k
II1.21k
= dyn_cast<IntrinsicInst>(CS.getInstruction())) {
369
26
        if (MemSetInst *
MSI26
= dyn_cast<MemSetInst>(II)) {
370
4
          if (
MSI->isVolatile()4
) {
371
0
            DEBUG(dbgs() << "Can not optimize a volatile memset " <<
372
0
                  "intrinsic.\n");
373
0
            return false;
374
0
          }
375
4
          Constant *Ptr = getVal(MSI->getDest());
376
4
          Constant *Val = getVal(MSI->getValue());
377
4
          Constant *DestVal = ComputeLoadResult(getVal(Ptr));
378
4
          if (
Val->isNullValue() && 4
DestVal4
&&
DestVal->isNullValue()1
) {
379
1
            // This memset is a no-op.
380
1
            DEBUG(dbgs() << "Ignoring no-op memset.\n");
381
1
            ++CurInst;
382
1
            continue;
383
1
          }
384
25
        }
385
25
386
25
        
if (25
II->getIntrinsicID() == Intrinsic::lifetime_start ||
387
25
            
II->getIntrinsicID() == Intrinsic::lifetime_end23
) {
388
4
          DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");
389
4
          ++CurInst;
390
4
          continue;
391
4
        }
392
21
393
21
        
if (21
II->getIntrinsicID() == Intrinsic::invariant_start21
) {
394
15
          // We don't insert an entry into Values, as it doesn't have a
395
15
          // meaningful return value.
396
15
          if (
!II->use_empty()15
) {
397
3
            DEBUG(dbgs() << "Found unused invariant_start. Can't evaluate.\n");
398
3
            return false;
399
3
          }
400
12
          ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0));
401
12
          Value *PtrArg = getVal(II->getArgOperand(1));
402
12
          Value *Ptr = PtrArg->stripPointerCasts();
403
12
          if (GlobalVariable *
GV12
= dyn_cast<GlobalVariable>(Ptr)) {
404
12
            Type *ElemTy = GV->getValueType();
405
12
            if (!Size->isMinusOne() &&
406
11
                Size->getValue().getLimitedValue() >=
407
12
                    DL.getTypeStoreSize(ElemTy)) {
408
9
              Invariants.insert(GV);
409
9
              DEBUG(dbgs() << "Found a global var that is an invariant: " << *GV
410
9
                    << "\n");
411
12
            } else {
412
3
              DEBUG(dbgs() << "Found a global var, but can not treat it as an "
413
3
                    "invariant.\n");
414
3
            }
415
12
          }
416
15
          // Continue even if we do nothing.
417
15
          ++CurInst;
418
15
          continue;
419
6
        } else 
if (6
II->getIntrinsicID() == Intrinsic::assume6
) {
420
1
          DEBUG(dbgs() << "Skipping assume intrinsic.\n");
421
6
          ++CurInst;
422
6
          continue;
423
6
        }
424
5
425
5
        
DEBUG5
(dbgs() << "Unknown intrinsic. Can not evaluate.\n");
426
5
        return false;
427
5
      }
428
1.18k
429
1.18k
      // Resolve function pointers.
430
1.18k
      Function *Callee = dyn_cast<Function>(getVal(CS.getCalledValue()));
431
1.18k
      if (
!Callee || 1.18k
Callee->isInterposable()1.18k
) {
432
2
        DEBUG(dbgs() << "Can not resolve function pointer.\n");
433
2
        return false;  // Cannot resolve.
434
2
      }
435
1.18k
436
1.18k
      SmallVector<Constant*, 8> Formals;
437
2.72k
      for (User::op_iterator i = CS.arg_begin(), e = CS.arg_end(); 
i != e2.72k
;
++i1.54k
)
438
1.54k
        Formals.push_back(getVal(*i));
439
1.18k
440
1.18k
      if (
Callee->isDeclaration()1.18k
) {
441
175
        // If this is a function we can constant fold, do it.
442
175
        if (Constant *
C175
= ConstantFoldCall(CS, Callee, Formals, TLI)) {
443
1
          InstResult = C;
444
1
          DEBUG(dbgs() << "Constant folded function call. Result: " <<
445
1
                *InstResult << "\n");
446
175
        } else {
447
174
          DEBUG(dbgs() << "Can not constant fold function call.\n");
448
174
          return false;
449
174
        }
450
1.00k
      } else {
451
1.00k
        if (
Callee->getFunctionType()->isVarArg()1.00k
) {
452
0
          DEBUG(dbgs() << "Can not constant fold vararg function call.\n");
453
0
          return false;
454
0
        }
455
1.00k
456
1.00k
        Constant *RetVal = nullptr;
457
1.00k
        // Execute the call, if successful, use the return value.
458
1.00k
        ValueStack.emplace_back();
459
1.00k
        if (
!EvaluateFunction(Callee, RetVal, Formals)1.00k
) {
460
597
          DEBUG(dbgs() << "Failed to evaluate function.\n");
461
597
          return false;
462
597
        }
463
411
        ValueStack.pop_back();
464
411
        InstResult = RetVal;
465
411
466
411
        if (
InstResult411
) {
467
293
          DEBUG(dbgs() << "Successfully evaluated function. Result: "
468
293
                       << *InstResult << "\n\n");
469
411
        } else {
470
118
          DEBUG(dbgs() << "Successfully evaluated function. Result: 0\n\n");
471
118
        }
472
1.00k
      }
473
1.95k
    } else 
if (742
isa<TerminatorInst>(CurInst)742
) {
474
742
      DEBUG(dbgs() << "Found a terminator instruction.\n");
475
742
476
742
      if (BranchInst *
BI742
= dyn_cast<BranchInst>(CurInst)) {
477
191
        if (
BI->isUnconditional()191
) {
478
100
          NextBB = BI->getSuccessor(0);
479
191
        } else {
480
91
          ConstantInt *Cond =
481
91
            dyn_cast<ConstantInt>(getVal(BI->getCondition()));
482
91
          if (
!Cond91
)
return false0
; // Cannot determine.
483
91
484
91
          NextBB = BI->getSuccessor(!Cond->getZExtValue());
485
91
        }
486
742
      } else 
if (SwitchInst *551
SI551
= dyn_cast<SwitchInst>(CurInst)) {
487
0
        ConstantInt *Val =
488
0
          dyn_cast<ConstantInt>(getVal(SI->getCondition()));
489
0
        if (
!Val0
)
return false0
; // Cannot determine.
490
0
        NextBB = SI->findCaseValue(Val)->getCaseSuccessor();
491
551
      } else 
if (IndirectBrInst *551
IBI551
= dyn_cast<IndirectBrInst>(CurInst)) {
492
0
        Value *Val = getVal(IBI->getAddress())->stripPointerCasts();
493
0
        if (BlockAddress *BA = dyn_cast<BlockAddress>(Val))
494
0
          NextBB = BA->getBasicBlock();
495
0
        else
496
0
          return false;  // Cannot determine.
497
551
      } else 
if (551
isa<ReturnInst>(CurInst)551
) {
498
551
        NextBB = nullptr;
499
551
      } else {
500
0
        // invoke, unwind, resume, unreachable.
501
0
        DEBUG(dbgs() << "Can not handle terminator.");
502
551
        return false;  // Cannot handle this terminator.
503
551
      }
504
742
505
742
      // We succeeded at evaluating this block!
506
742
      
DEBUG742
(dbgs() << "Successfully evaluated block.\n");
507
742
      return true;
508
0
    } else {
509
0
      // Did not know how to evaluate this!
510
0
      DEBUG(dbgs() << "Failed to evaluate block due to unhandled instruction."
511
4.12k
            "\n");
512
4.12k
      return false;
513
4.12k
    }
514
3.93k
515
3.93k
    
if (3.93k
!CurInst->use_empty()3.93k
) {
516
1.99k
      if (auto *FoldedInstResult = ConstantFoldConstant(InstResult, DL, TLI))
517
928
        InstResult = FoldedInstResult;
518
1.99k
519
1.99k
      setVal(&*CurInst, InstResult);
520
1.99k
    }
521
3.93k
522
3.93k
    // If we just processed an invoke, we finished evaluating the block.
523
3.93k
    if (InvokeInst *
II3.93k
= dyn_cast<InvokeInst>(CurInst)) {
524
1
      NextBB = II->getNormalDest();
525
1
      DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n");
526
1
      return true;
527
1
    }
528
3.93k
529
3.93k
    // Advance program counter.
530
3.93k
    ++CurInst;
531
3.93k
  }
532
1.56k
}
533
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
536
/// function.
537
bool Evaluator::EvaluateFunction(Function *F, Constant *&RetVal,
538
1.40k
                                 const SmallVectorImpl<Constant*> &ActualArgs) {
539
1.40k
  // Check to see if this function is already executing (recursion).  If so,
540
1.40k
  // bail out.  TODO: we might want to accept limited recursion.
541
1.40k
  if (is_contained(CallStack, F))
542
0
    return false;
543
1.40k
544
1.40k
  CallStack.push_back(F);
545
1.40k
546
1.40k
  // Initialize arguments to the incoming values specified.
547
1.40k
  unsigned ArgNo = 0;
548
2.92k
  for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
549
1.51k
       ++AI, ++ArgNo)
550
1.51k
    setVal(&*AI, ActualArgs[ArgNo]);
551
1.40k
552
1.40k
  // ExecutedBlocks - We only handle non-looping, non-recursive code.  As such,
553
1.40k
  // we can only evaluate any one basic block at most once.  This set keeps
554
1.40k
  // track of what we have executed so we can detect recursive cases etc.
555
1.40k
  SmallPtrSet<BasicBlock*, 32> ExecutedBlocks;
556
1.40k
557
1.40k
  // CurBB - The current basic block we're evaluating.
558
1.40k
  BasicBlock *CurBB = &F->front();
559
1.40k
560
1.40k
  BasicBlock::iterator CurInst = CurBB->begin();
561
1.40k
562
1.56k
  while (
11.56k
) {
563
1.56k
    BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings.
564
1.56k
    DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");
565
1.56k
566
1.56k
    if (!EvaluateBlock(CurInst, NextBB))
567
822
      return false;
568
743
569
743
    
if (743
!NextBB743
) {
570
551
      // Successfully running until there's no next block means that we found
571
551
      // the return.  Fill it the return value and pop the call stack.
572
551
      ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator());
573
551
      if (RI->getNumOperands())
574
383
        RetVal = getVal(RI->getOperand(0));
575
551
      CallStack.pop_back();
576
551
      return true;
577
551
    }
578
192
579
192
    // Okay, we succeeded in evaluating this control flow.  See if we have
580
192
    // executed the new block before.  If so, we have a looping function,
581
192
    // which we cannot evaluate in reasonable time.
582
192
    
if (192
!ExecutedBlocks.insert(NextBB).second192
)
583
32
      return false;  // looped!
584
160
585
160
    // Okay, we have never been in this block before.  Check to see if there
586
160
    // are any PHI nodes.  If so, evaluate them with information about where
587
160
    // we came from.
588
160
    PHINode *PN = nullptr;
589
160
    for (CurInst = NextBB->begin();
590
246
         
(PN = dyn_cast<PHINode>(CurInst))246
;
++CurInst86
)
591
86
      setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB)));
592
1.56k
593
1.56k
    // Advance to the next block.
594
1.56k
    CurBB = NextBB;
595
1.56k
  }
596
1.40k
}
597