Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Utils/Evaluator.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- Evaluator.cpp - LLVM IR evaluator ----------------------------------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// Function evaluator for LLVM IR.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "llvm/Transforms/Utils/Evaluator.h"
14
#include "llvm/ADT/DenseMap.h"
15
#include "llvm/ADT/STLExtras.h"
16
#include "llvm/ADT/SmallPtrSet.h"
17
#include "llvm/ADT/SmallVector.h"
18
#include "llvm/Analysis/ConstantFolding.h"
19
#include "llvm/IR/BasicBlock.h"
20
#include "llvm/IR/CallSite.h"
21
#include "llvm/IR/Constant.h"
22
#include "llvm/IR/Constants.h"
23
#include "llvm/IR/DataLayout.h"
24
#include "llvm/IR/DerivedTypes.h"
25
#include "llvm/IR/Function.h"
26
#include "llvm/IR/GlobalAlias.h"
27
#include "llvm/IR/GlobalValue.h"
28
#include "llvm/IR/GlobalVariable.h"
29
#include "llvm/IR/InstrTypes.h"
30
#include "llvm/IR/Instruction.h"
31
#include "llvm/IR/Instructions.h"
32
#include "llvm/IR/IntrinsicInst.h"
33
#include "llvm/IR/Intrinsics.h"
34
#include "llvm/IR/Operator.h"
35
#include "llvm/IR/Type.h"
36
#include "llvm/IR/User.h"
37
#include "llvm/IR/Value.h"
38
#include "llvm/Support/Casting.h"
39
#include "llvm/Support/Debug.h"
40
#include "llvm/Support/raw_ostream.h"
41
#include <iterator>
42
43
#define DEBUG_TYPE "evaluator"
44
45
using namespace llvm;
46
47
static inline bool
48
isSimpleEnoughValueToCommit(Constant *C,
49
                            SmallPtrSetImpl<Constant *> &SimpleConstants,
50
                            const DataLayout &DL);
51
52
/// Return true if the specified constant can be handled by the code generator.
53
/// We don't want to generate something like:
54
///   void *X = &X/42;
55
/// because the code generator doesn't have a relocation that can handle that.
56
///
57
/// This function should be called if C was not found (but just got inserted)
58
/// in SimpleConstants to avoid having to rescan the same constants all the
59
/// time.
60
static bool
61
isSimpleEnoughValueToCommitHelper(Constant *C,
62
                                  SmallPtrSetImpl<Constant *> &SimpleConstants,
63
1.96k
                                  const DataLayout &DL) {
64
1.96k
  // Simple global addresses are supported, do not allow dllimport or
65
1.96k
  // thread-local globals.
66
1.96k
  if (auto *GV = dyn_cast<GlobalValue>(C))
67
274
    return !GV->hasDLLImportStorageClass() && 
!GV->isThreadLocal()270
;
68
1.68k
69
1.68k
  // Simple integer, undef, constant aggregate zero, etc are all supported.
70
1.68k
  if (C->getNumOperands() == 0 || 
isa<BlockAddress>(C)350
)
71
1.33k
    return true;
72
350
73
350
  // Aggregate values are safe if all their elements are.
74
350
  if (isa<ConstantAggregate>(C)) {
75
1
    for (Value *Op : C->operands())
76
2
      if (!isSimpleEnoughValueToCommit(cast<Constant>(Op), SimpleConstants, DL))
77
0
        return false;
78
1
    return true;
79
349
  }
80
349
81
349
  // We don't know exactly what relocations are allowed in constant expressions,
82
349
  // so we allow &global+constantoffset, which is safe and uniformly supported
83
349
  // across targets.
84
349
  ConstantExpr *CE = cast<ConstantExpr>(C);
85
349
  switch (CE->getOpcode()) {
86
349
  case Instruction::BitCast:
87
60
    // Bitcast is fine if the casted value is fine.
88
60
    return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
89
349
90
349
  case Instruction::IntToPtr:
91
23
  case Instruction::PtrToInt:
92
23
    // int <=> ptr is fine if the int type is the same size as the
93
23
    // pointer type.
94
23
    if (DL.getTypeSizeInBits(CE->getType()) !=
95
23
        DL.getTypeSizeInBits(CE->getOperand(0)->getType()))
96
2
      return false;
97
21
    return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
98
21
99
21
  // GEP is fine if it is simple + constant offset.
100
263
  case Instruction::GetElementPtr:
101
905
    for (unsigned i = 1, e = CE->getNumOperands(); i != e; 
++i642
)
102
642
      if (!isa<ConstantInt>(CE->getOperand(i)))
103
0
        return false;
104
263
    return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
105
263
106
263
  case Instruction::Add:
107
0
    // We allow simple+cst.
108
0
    if (!isa<ConstantInt>(CE->getOperand(1)))
109
0
      return false;
110
0
    return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
111
3
  }
112
3
  return false;
113
3
}
114
115
static inline bool
116
isSimpleEnoughValueToCommit(Constant *C,
117
                            SmallPtrSetImpl<Constant *> &SimpleConstants,
118
4.22k
                            const DataLayout &DL) {
119
4.22k
  // If we already checked this constant, we win.
120
4.22k
  if (!SimpleConstants.insert(C).second)
121
2.26k
    return true;
122
1.96k
  // Check the constant.
123
1.96k
  return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, DL);
124
1.96k
}
125
126
/// Return true if this constant is simple enough for us to understand.  In
127
/// particular, if it is a cast to anything other than from one pointer type to
128
/// another pointer type, we punt.  We basically just support direct accesses to
129
/// globals and GEP's of globals.  This should be kept up to date with
130
/// CommitValueTo.
131
3.90k
static bool isSimpleEnoughPointerToCommit(Constant *C) {
132
3.90k
  // Conservatively, avoid aggregate types. This is because we don't
133
3.90k
  // want to worry about them partially overlapping other stores.
134
3.90k
  if (!cast<PointerType>(C->getType())->getElementType()->isSingleValueType())
135
0
    return false;
136
3.90k
137
3.90k
  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C))
138
676
    // Do not allow weak/*_odr/linkonce linkage or external globals.
139
676
    return GV->hasUniqueInitializer();
140
3.22k
141
3.22k
  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
142
3.22k
    // Handle a constantexpr gep.
143
3.22k
    if (CE->getOpcode() == Instruction::GetElementPtr &&
144
3.22k
        
isa<GlobalVariable>(CE->getOperand(0))3.17k
&&
145
3.22k
        
cast<GEPOperator>(CE)->isInBounds()3.17k
) {
146
3.17k
      GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
147
3.17k
      // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
148
3.17k
      // external globals.
149
3.17k
      if (!GV->hasUniqueInitializer())
150
2
        return false;
151
3.17k
152
3.17k
      // The first index must be zero.
153
3.17k
      ConstantInt *CI = dyn_cast<ConstantInt>(*std::next(CE->op_begin()));
154
3.17k
      if (!CI || !CI->isZero()) 
return false0
;
155
3.17k
156
3.17k
      // The remaining indices must be compile-time known integers within the
157
3.17k
      // notional bounds of the corresponding static array types.
158
3.17k
      if (!CE->isGEPWithNoNotionalOverIndexing())
159
0
        return false;
160
3.17k
161
3.17k
      return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE);
162
3.17k
163
3.17k
    // A constantexpr bitcast from a pointer to another pointer is a no-op,
164
3.17k
    // and we know how to evaluate it by moving the bitcast from the pointer
165
3.17k
    // operand to the value operand.
166
3.17k
    } else 
if (53
CE->getOpcode() == Instruction::BitCast53
&&
167
53
               
isa<GlobalVariable>(CE->getOperand(0))47
) {
168
42
      // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
169
42
      // external globals.
170
42
      return cast<GlobalVariable>(CE->getOperand(0))->hasUniqueInitializer();
171
42
    }
172
11
  }
173
11
174
11
  return false;
175
11
}
176
177
/// Apply 'Func' to Ptr. If this returns nullptr, introspect the pointer's
178
/// type and walk down through the initial elements to obtain additional
179
/// pointers to try. Returns the first non-null return value from Func, or
180
/// nullptr if the type can't be introspected further.
181
static Constant *
182
evaluateBitcastFromPtr(Constant *Ptr, const DataLayout &DL,
183
                       const TargetLibraryInfo *TLI,
184
108
                       std::function<Constant *(Constant *)> Func) {
185
108
  Constant *Val;
186
166
  while (!(Val = Func(Ptr))) {
187
121
    // If Ty is a struct, we can convert the pointer to the struct
188
121
    // into a pointer to its first member.
189
121
    // FIXME: This could be extended to support arrays as well.
190
121
    Type *Ty = cast<PointerType>(Ptr->getType())->getElementType();
191
121
    if (!isa<StructType>(Ty))
192
63
      break;
193
58
194
58
    IntegerType *IdxTy = IntegerType::get(Ty->getContext(), 32);
195
58
    Constant *IdxZero = ConstantInt::get(IdxTy, 0, false);
196
58
    Constant *const IdxList[] = {IdxZero, IdxZero};
197
58
198
58
    Ptr = ConstantExpr::getGetElementPtr(Ty, Ptr, IdxList);
199
58
    if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI))
200
58
      Ptr = FoldedPtr;
201
58
  }
202
108
  return Val;
203
108
}
204
205
162
static Constant *getInitializer(Constant *C) {
206
162
  auto *GV = dyn_cast<GlobalVariable>(C);
207
162
  return GV && GV->hasDefinitiveInitializer() ? 
GV->getInitializer()143
:
nullptr19
;
208
162
}
209
210
/// Return the value that would be computed by a load from P after the stores
211
/// reflected by 'memory' have been performed.  If we can't decide, return null.
212
895
Constant *Evaluator::ComputeLoadResult(Constant *P) {
213
895
  // If this memory location has been recently stored, use the stored value: it
214
895
  // is the most up-to-date.
215
965
  auto findMemLoc = [this](Constant *Ptr) {
216
965
    DenseMap<Constant *, Constant *>::const_iterator I =
217
965
        MutatedMemory.find(Ptr);
218
965
    return I != MutatedMemory.end() ? 
I->second641
:
nullptr324
;
219
965
  };
220
895
221
895
  if (Constant *Val = findMemLoc(P))
222
634
    return Val;
223
261
224
261
  // Access it.
225
261
  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) {
226
87
    if (GV->hasDefinitiveInitializer())
227
69
      return GV->getInitializer();
228
18
    return nullptr;
229
18
  }
230
174
231
174
  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(P)) {
232
171
    switch (CE->getOpcode()) {
233
171
    // Handle a constantexpr getelementptr.
234
171
    case Instruction::GetElementPtr:
235
103
      if (auto *I = getInitializer(CE->getOperand(0)))
236
99
        return ConstantFoldLoadThroughGEPConstantExpr(I, CE);
237
4
      break;
238
4
    // Handle a constantexpr bitcast.
239
66
    case Instruction::BitCast:
240
66
      // We're evaluating a load through a pointer that was bitcast to a
241
66
      // different type. See if the "from" pointer has recently been stored.
242
66
      // If it hasn't, we may still be able to find a stored pointer by
243
66
      // introspecting the type.
244
66
      Constant *Val =
245
66
          evaluateBitcastFromPtr(CE->getOperand(0), DL, TLI, findMemLoc);
246
66
      if (!Val)
247
59
        Val = getInitializer(CE->getOperand(0));
248
66
      if (Val)
249
51
        return ConstantFoldLoadThroughBitcast(
250
51
            Val, P->getType()->getPointerElementType(), DL);
251
15
      break;
252
171
    }
253
171
  }
254
24
255
24
  return nullptr;  // don't know how to evaluate.
256
24
}
257
258
4.35k
static Function *getFunction(Constant *C) {
259
4.35k
  if (auto *Fn = dyn_cast<Function>(C))
260
4.35k
    return Fn;
261
4
262
4
  if (auto *Alias = dyn_cast<GlobalAlias>(C))
263
1
    if (auto *Fn = dyn_cast<Function>(Alias->getAliasee()))
264
1
      return Fn;
265
3
  return nullptr;
266
3
}
267
268
Function *
269
Evaluator::getCalleeWithFormalArgs(CallSite &CS,
270
4.35k
                                   SmallVector<Constant *, 8> &Formals) {
271
4.35k
  auto *V = CS.getCalledValue();
272
4.35k
  if (auto *Fn = getFunction(getVal(V)))
273
4.34k
    return getFormalParams(CS, Fn, Formals) ? 
Fn4.34k
:
nullptr4
;
274
3
275
3
  auto *CE = dyn_cast<ConstantExpr>(V);
276
3
  if (!CE || CE->getOpcode() != Instruction::BitCast ||
277
3
      !getFormalParams(CS, getFunction(CE->getOperand(0)), Formals))
278
0
    return nullptr;
279
3
280
3
  return dyn_cast<Function>(
281
3
      ConstantFoldLoadThroughBitcast(CE, CE->getOperand(0)->getType(), DL));
282
3
}
283
284
bool Evaluator::getFormalParams(CallSite &CS, Function *F,
285
4.35k
                                SmallVector<Constant *, 8> &Formals) {
286
4.35k
  if (!F)
287
0
    return false;
288
4.35k
289
4.35k
  auto *FTy = F->getFunctionType();
290
4.35k
  if (FTy->getNumParams() > CS.getNumArgOperands()) {
291
0
    LLVM_DEBUG(dbgs() << "Too few arguments for function.\n");
292
0
    return false;
293
0
  }
294
4.35k
295
4.35k
  auto ArgI = CS.arg_begin();
296
9.63k
  for (auto ParI = FTy->param_begin(), ParE = FTy->param_end(); ParI != ParE;
297
5.29k
       
++ParI5.28k
) {
298
5.29k
    auto *ArgC = ConstantFoldLoadThroughBitcast(getVal(*ArgI), *ParI, DL);
299
5.29k
    if (!ArgC) {
300
4
      LLVM_DEBUG(dbgs() << "Can not convert function argument.\n");
301
4
      return false;
302
4
    }
303
5.28k
    Formals.push_back(ArgC);
304
5.28k
    ++ArgI;
305
5.28k
  }
306
4.35k
  
return true4.34k
;
307
4.35k
}
308
309
/// If call expression contains bitcast then we may need to cast
310
/// evaluated return value to a type of the call expression.
311
2.63k
Constant *Evaluator::castCallResultIfNeeded(Value *CallExpr, Constant *RV) {
312
2.63k
  ConstantExpr *CE = dyn_cast<ConstantExpr>(CallExpr);
313
2.63k
  if (!RV || 
!CE1.99k
||
CE->getOpcode() != Instruction::BitCast2
)
314
2.63k
    return RV;
315
2
316
2
  if (auto *FT =
317
2
          dyn_cast<FunctionType>(CE->getType()->getPointerElementType())) {
318
2
    RV = ConstantFoldLoadThroughBitcast(RV, FT->getReturnType(), DL);
319
2
    if (!RV)
320
2
      LLVM_DEBUG(dbgs() << "Failed to fold bitcast call expr\n");
321
2
  }
322
2
  return RV;
323
2
}
324
325
/// Evaluate all instructions in block BB, returning true if successful, false
326
/// if we can't evaluate it.  NewBB returns the next BB that control flows into,
327
/// or null upon return.
328
bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst,
329
4.98k
                              BasicBlock *&NextBB) {
330
4.98k
  // This is the main evaluation loop.
331
19.0k
  while (true) {
332
19.0k
    Constant *InstResult = nullptr;
333
19.0k
334
19.0k
    LLVM_DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n");
335
19.0k
336
19.0k
    if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
337
3.93k
      if (!SI->isSimple()) {
338
32
        LLVM_DEBUG(dbgs() << "Store is not simple! Can not evaluate.\n");
339
32
        return false;  // no volatile/atomic accesses.
340
32
      }
341
3.90k
      Constant *Ptr = getVal(SI->getOperand(1));
342
3.90k
      if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI)) {
343
3.22k
        LLVM_DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr);
344
3.22k
        Ptr = FoldedPtr;
345
3.22k
        LLVM_DEBUG(dbgs() << "; To: " << *Ptr << "\n");
346
3.22k
      }
347
3.90k
      if (!isSimpleEnoughPointerToCommit(Ptr)) {
348
20
        // If this is too complex for us to commit, reject it.
349
20
        LLVM_DEBUG(
350
20
            dbgs() << "Pointer is too complex for us to evaluate store.");
351
20
        return false;
352
20
      }
353
3.88k
354
3.88k
      Constant *Val = getVal(SI->getOperand(0));
355
3.88k
356
3.88k
      // If this might be too difficult for the backend to handle (e.g. the addr
357
3.88k
      // of one global variable divided by another) then we can't commit it.
358
3.88k
      if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)) {
359
13
        LLVM_DEBUG(dbgs() << "Store value is too complex to evaluate store. "
360
13
                          << *Val << "\n");
361
13
        return false;
362
13
      }
363
3.86k
364
3.86k
      if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) {
365
3.20k
        if (CE->getOpcode() == Instruction::BitCast) {
366
42
          LLVM_DEBUG(dbgs()
367
42
                     << "Attempting to resolve bitcast on constant ptr.\n");
368
42
          // If we're evaluating a store through a bitcast, then we need
369
42
          // to pull the bitcast off the pointer type and push it onto the
370
42
          // stored value. In order to push the bitcast onto the stored value,
371
42
          // a bitcast from the pointer's element type to Val's type must be
372
42
          // legal. If it's not, we can try introspecting the type to find a
373
42
          // legal conversion.
374
42
375
96
          auto castValTy = [&](Constant *P) -> Constant * {
376
96
            Type *Ty = cast<PointerType>(P->getType())->getElementType();
377
96
            if (Constant *FV = ConstantFoldLoadThroughBitcast(Val, Ty, DL)) {
378
38
              Ptr = P;
379
38
              return FV;
380
38
            }
381
58
            return nullptr;
382
58
          };
383
42
384
42
          Constant *NewVal =
385
42
              evaluateBitcastFromPtr(CE->getOperand(0), DL, TLI, castValTy);
386
42
          if (!NewVal) {
387
4
            LLVM_DEBUG(dbgs() << "Failed to bitcast constant ptr, can not "
388
4
                                 "evaluate.\n");
389
4
            return false;
390
4
          }
391
38
392
38
          Val = NewVal;
393
38
          LLVM_DEBUG(dbgs() << "Evaluated bitcast: " << *Val << "\n");
394
38
        }
395
3.20k
      }
396
3.86k
397
3.86k
      MutatedMemory[Ptr] = Val;
398
15.0k
    } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) {
399
256
      InstResult = ConstantExpr::get(BO->getOpcode(),
400
256
                                     getVal(BO->getOperand(0)),
401
256
                                     getVal(BO->getOperand(1)));
402
256
      LLVM_DEBUG(dbgs() << "Found a BinaryOperator! Simplifying: "
403
256
                        << *InstResult << "\n");
404
14.8k
    } else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) {
405
142
      InstResult = ConstantExpr::getCompare(CI->getPredicate(),
406
142
                                            getVal(CI->getOperand(0)),
407
142
                                            getVal(CI->getOperand(1)));
408
142
      LLVM_DEBUG(dbgs() << "Found a CmpInst! Simplifying: " << *InstResult
409
142
                        << "\n");
410
14.6k
    } else if (CastInst *CI = dyn_cast<CastInst>(CurInst)) {
411
1.36k
      InstResult = ConstantExpr::getCast(CI->getOpcode(),
412
1.36k
                                         getVal(CI->getOperand(0)),
413
1.36k
                                         CI->getType());
414
1.36k
      LLVM_DEBUG(dbgs() << "Found a Cast! Simplifying: " << *InstResult
415
1.36k
                        << "\n");
416
13.3k
    } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) {
417
24
      InstResult = ConstantExpr::getSelect(getVal(SI->getOperand(0)),
418
24
                                           getVal(SI->getOperand(1)),
419
24
                                           getVal(SI->getOperand(2)));
420
24
      LLVM_DEBUG(dbgs() << "Found a Select! Simplifying: " << *InstResult
421
24
                        << "\n");
422
13.2k
    } else if (auto *EVI = dyn_cast<ExtractValueInst>(CurInst)) {
423
2
      InstResult = ConstantExpr::getExtractValue(
424
2
          getVal(EVI->getAggregateOperand()), EVI->getIndices());
425
2
      LLVM_DEBUG(dbgs() << "Found an ExtractValueInst! Simplifying: "
426
2
                        << *InstResult << "\n");
427
13.2k
    } else if (auto *IVI = dyn_cast<InsertValueInst>(CurInst)) {
428
23
      InstResult = ConstantExpr::getInsertValue(
429
23
          getVal(IVI->getAggregateOperand()),
430
23
          getVal(IVI->getInsertedValueOperand()), IVI->getIndices());
431
23
      LLVM_DEBUG(dbgs() << "Found an InsertValueInst! Simplifying: "
432
23
                        << *InstResult << "\n");
433
13.2k
    } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) {
434
2.34k
      Constant *P = getVal(GEP->getOperand(0));
435
2.34k
      SmallVector<Constant*, 8> GEPOps;
436
2.34k
      for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end();
437
9.08k
           i != e; 
++i6.74k
)
438
6.74k
        GEPOps.push_back(getVal(*i));
439
2.34k
      InstResult =
440
2.34k
          ConstantExpr::getGetElementPtr(GEP->getSourceElementType(), P, GEPOps,
441
2.34k
                                         cast<GEPOperator>(GEP)->isInBounds());
442
2.34k
      LLVM_DEBUG(dbgs() << "Found a GEP! Simplifying: " << *InstResult << "\n");
443
10.9k
    } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) {
444
783
      if (!LI->isSimple()) {
445
4
        LLVM_DEBUG(
446
4
            dbgs() << "Found a Load! Not a simple load, can not evaluate.\n");
447
4
        return false;  // no volatile/atomic accesses.
448
4
      }
449
779
450
779
      Constant *Ptr = getVal(LI->getOperand(0));
451
779
      if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI)) {
452
136
        Ptr = FoldedPtr;
453
136
        LLVM_DEBUG(dbgs() << "Found a constant pointer expression, constant "
454
136
                             "folding: "
455
136
                          << *Ptr << "\n");
456
136
      }
457
779
      InstResult = ComputeLoadResult(Ptr);
458
779
      if (!InstResult) {
459
64
        LLVM_DEBUG(
460
64
            dbgs() << "Failed to compute load result. Can not evaluate load."
461
64
                      "\n");
462
64
        return false; // Could not evaluate load.
463
64
      }
464
715
465
715
      LLVM_DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n");
466
10.1k
    } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) {
467
1.72k
      if (AI->isArrayAllocation()) {
468
0
        LLVM_DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n");
469
0
        return false;  // Cannot handle array allocs.
470
0
      }
471
1.72k
      Type *Ty = AI->getAllocatedType();
472
1.72k
      AllocaTmps.push_back(llvm::make_unique<GlobalVariable>(
473
1.72k
          Ty, false, GlobalValue::InternalLinkage, UndefValue::get(Ty),
474
1.72k
          AI->getName(), /*TLMode=*/GlobalValue::NotThreadLocal,
475
1.72k
          AI->getType()->getPointerAddressSpace()));
476
1.72k
      InstResult = AllocaTmps.back().get();
477
1.72k
      LLVM_DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n");
478
8.40k
    } else if (isa<CallInst>(CurInst) || 
isa<InvokeInst>(CurInst)3.11k
) {
479
5.32k
      CallSite CS(&*CurInst);
480
5.32k
481
5.32k
      // Debug info can safely be ignored here.
482
5.32k
      if (isa<DbgInfoIntrinsic>(CS.getInstruction())) {
483
0
        LLVM_DEBUG(dbgs() << "Ignoring debug info.\n");
484
0
        ++CurInst;
485
0
        continue;
486
0
      }
487
5.32k
488
5.32k
      // Cannot handle inline asm.
489
5.32k
      if (isa<InlineAsm>(CS.getCalledValue())) {
490
4
        LLVM_DEBUG(dbgs() << "Found inline asm, can not evaluate.\n");
491
4
        return false;
492
4
      }
493
5.32k
494
5.32k
      if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
495
971
        if (MemSetInst *MSI = dyn_cast<MemSetInst>(II)) {
496
116
          if (MSI->isVolatile()) {
497
0
            LLVM_DEBUG(dbgs() << "Can not optimize a volatile memset "
498
0
                              << "intrinsic.\n");
499
0
            return false;
500
0
          }
501
116
          Constant *Ptr = getVal(MSI->getDest());
502
116
          Constant *Val = getVal(MSI->getValue());
503
116
          Constant *DestVal = ComputeLoadResult(getVal(Ptr));
504
116
          if (Val->isNullValue() && DestVal && 
DestVal->isNullValue()113
) {
505
106
            // This memset is a no-op.
506
106
            LLVM_DEBUG(dbgs() << "Ignoring no-op memset.\n");
507
106
            ++CurInst;
508
106
            continue;
509
106
          }
510
865
        }
511
865
512
865
        if (II->isLifetimeStartOrEnd()) {
513
719
          LLVM_DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");
514
719
          ++CurInst;
515
719
          continue;
516
719
        }
517
146
518
146
        if (II->getIntrinsicID() == Intrinsic::invariant_start) {
519
119
          // We don't insert an entry into Values, as it doesn't have a
520
119
          // meaningful return value.
521
119
          if (!II->use_empty()) {
522
3
            LLVM_DEBUG(dbgs()
523
3
                       << "Found unused invariant_start. Can't evaluate.\n");
524
3
            return false;
525
3
          }
526
116
          ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0));
527
116
          Value *PtrArg = getVal(II->getArgOperand(1));
528
116
          Value *Ptr = PtrArg->stripPointerCasts();
529
116
          if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
530
116
            Type *ElemTy = GV->getValueType();
531
116
            if (!Size->isMinusOne() &&
532
116
                Size->getValue().getLimitedValue() >=
533
115
                    DL.getTypeStoreSize(ElemTy)) {
534
113
              Invariants.insert(GV);
535
113
              LLVM_DEBUG(dbgs() << "Found a global var that is an invariant: "
536
113
                                << *GV << "\n");
537
113
            } else {
538
3
              LLVM_DEBUG(dbgs()
539
3
                         << "Found a global var, but can not treat it as an "
540
3
                            "invariant.\n");
541
3
            }
542
116
          }
543
116
          // Continue even if we do nothing.
544
116
          ++CurInst;
545
116
          continue;
546
116
        } else 
if (27
II->getIntrinsicID() == Intrinsic::assume27
) {
547
1
          LLVM_DEBUG(dbgs() << "Skipping assume intrinsic.\n");
548
1
          ++CurInst;
549
1
          continue;
550
26
        } else if (II->getIntrinsicID() == Intrinsic::sideeffect) {
551
1
          LLVM_DEBUG(dbgs() << "Skipping sideeffect intrinsic.\n");
552
1
          ++CurInst;
553
1
          continue;
554
1
        }
555
25
556
25
        LLVM_DEBUG(dbgs() << "Unknown intrinsic. Can not evaluate.\n");
557
25
        return false;
558
25
      }
559
4.35k
560
4.35k
      // Resolve function pointers.
561
4.35k
      SmallVector<Constant *, 8> Formals;
562
4.35k
      Function *Callee = getCalleeWithFormalArgs(CS, Formals);
563
4.35k
      if (!Callee || 
Callee->isInterposable()4.34k
) {
564
4
        LLVM_DEBUG(dbgs() << "Can not resolve function pointer.\n");
565
4
        return false;  // Cannot resolve.
566
4
      }
567
4.34k
568
4.34k
      if (Callee->isDeclaration()) {
569
707
        // If this is a function we can constant fold, do it.
570
707
        if (Constant *C = ConstantFoldCall(cast<CallBase>(CS.getInstruction()),
571
2
                                           Callee, Formals, TLI)) {
572
2
          InstResult = castCallResultIfNeeded(CS.getCalledValue(), C);
573
2
          if (!InstResult)
574
0
            return false;
575
2
          LLVM_DEBUG(dbgs() << "Constant folded function call. Result: "
576
2
                            << *InstResult << "\n");
577
705
        } else {
578
705
          LLVM_DEBUG(dbgs() << "Can not constant fold function call.\n");
579
705
          return false;
580
705
        }
581
3.64k
      } else {
582
3.64k
        if (Callee->getFunctionType()->isVarArg()) {
583
0
          LLVM_DEBUG(dbgs() << "Can not constant fold vararg function call.\n");
584
0
          return false;
585
0
        }
586
3.64k
587
3.64k
        Constant *RetVal = nullptr;
588
3.64k
        // Execute the call, if successful, use the return value.
589
3.64k
        ValueStack.emplace_back();
590
3.64k
        if (!EvaluateFunction(Callee, RetVal, Formals)) {
591
1.00k
          LLVM_DEBUG(dbgs() << "Failed to evaluate function.\n");
592
1.00k
          return false;
593
1.00k
        }
594
2.63k
        ValueStack.pop_back();
595
2.63k
        InstResult = castCallResultIfNeeded(CS.getCalledValue(), RetVal);
596
2.63k
        if (RetVal && 
!InstResult1.98k
)
597
0
          return false;
598
2.63k
599
2.63k
        if (InstResult) {
600
1.98k
          LLVM_DEBUG(dbgs() << "Successfully evaluated function. Result: "
601
1.98k
                            << *InstResult << "\n\n");
602
1.98k
        } else {
603
646
          LLVM_DEBUG(dbgs()
604
646
                     << "Successfully evaluated function. Result: 0\n\n");
605
646
        }
606
2.63k
      }
607
4.34k
    } else 
if (3.07k
CurInst->isTerminator()3.07k
) {
608
3.07k
      LLVM_DEBUG(dbgs() << "Found a terminator instruction.\n");
609
3.07k
610
3.07k
      if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
611
259
        if (BI->isUnconditional()) {
612
106
          NextBB = BI->getSuccessor(0);
613
153
        } else {
614
153
          ConstantInt *Cond =
615
153
            dyn_cast<ConstantInt>(getVal(BI->getCondition()));
616
153
          if (!Cond) 
return false0
; // Cannot determine.
617
153
618
153
          NextBB = BI->getSuccessor(!Cond->getZExtValue());
619
153
        }
620
2.81k
      } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) {
621
0
        ConstantInt *Val =
622
0
          dyn_cast<ConstantInt>(getVal(SI->getCondition()));
623
0
        if (!Val) return false;  // Cannot determine.
624
0
        NextBB = SI->findCaseValue(Val)->getCaseSuccessor();
625
2.81k
      } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) {
626
0
        Value *Val = getVal(IBI->getAddress())->stripPointerCasts();
627
0
        if (BlockAddress *BA = dyn_cast<BlockAddress>(Val))
628
0
          NextBB = BA->getBasicBlock();
629
0
        else
630
0
          return false;  // Cannot determine.
631
2.81k
      } else if (isa<ReturnInst>(CurInst)) {
632
2.81k
        NextBB = nullptr;
633
2.81k
      } else {
634
0
        // invoke, unwind, resume, unreachable.
635
0
        LLVM_DEBUG(dbgs() << "Can not handle terminator.");
636
0
        return false;  // Cannot handle this terminator.
637
0
      }
638
3.07k
639
3.07k
      // We succeeded at evaluating this block!
640
3.07k
      LLVM_DEBUG(dbgs() << "Successfully evaluated block.\n");
641
3.07k
      return true;
642
3.07k
    } else {
643
0
      // Did not know how to evaluate this!
644
0
      LLVM_DEBUG(
645
0
          dbgs() << "Failed to evaluate block due to unhandled instruction."
646
0
                    "\n");
647
0
      return false;
648
0
    }
649
13.0k
650
13.0k
    if (!CurInst->use_empty()) {
651
6.67k
      if (auto *FoldedInstResult = ConstantFoldConstant(InstResult, DL, TLI))
652
3.65k
        InstResult = FoldedInstResult;
653
6.67k
654
6.67k
      setVal(&*CurInst, InstResult);
655
6.67k
    }
656
13.0k
657
13.0k
    // If we just processed an invoke, we finished evaluating the block.
658
13.0k
    if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) {
659
29
      NextBB = II->getNormalDest();
660
29
      LLVM_DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n");
661
29
      return true;
662
29
    }
663
13.0k
664
13.0k
    // Advance program counter.
665
13.0k
    ++CurInst;
666
13.0k
  }
667
4.98k
}
668
669
/// Evaluate a call to function F, returning true if successful, false if we
670
/// can't evaluate it.  ActualArgs contains the formal arguments for the
671
/// function.
672
bool Evaluator::EvaluateFunction(Function *F, Constant *&RetVal,
673
4.74k
                                 const SmallVectorImpl<Constant*> &ActualArgs) {
674
4.74k
  // Check to see if this function is already executing (recursion).  If so,
675
4.74k
  // bail out.  TODO: we might want to accept limited recursion.
676
4.74k
  if (is_contained(CallStack, F))
677
0
    return false;
678
4.74k
679
4.74k
  CallStack.push_back(F);
680
4.74k
681
4.74k
  // Initialize arguments to the incoming values specified.
682
4.74k
  unsigned ArgNo = 0;
683
9.46k
  for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
684
4.74k
       
++AI, ++ArgNo4.71k
)
685
4.71k
    setVal(&*AI, ActualArgs[ArgNo]);
686
4.74k
687
4.74k
  // ExecutedBlocks - We only handle non-looping, non-recursive code.  As such,
688
4.74k
  // we can only evaluate any one basic block at most once.  This set keeps
689
4.74k
  // track of what we have executed so we can detect recursive cases etc.
690
4.74k
  SmallPtrSet<BasicBlock*, 32> ExecutedBlocks;
691
4.74k
692
4.74k
  // CurBB - The current basic block we're evaluating.
693
4.74k
  BasicBlock *CurBB = &F->front();
694
4.74k
695
4.74k
  BasicBlock::iterator CurInst = CurBB->begin();
696
4.74k
697
4.98k
  while (true) {
698
4.98k
    BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings.
699
4.98k
    LLVM_DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");
700
4.98k
701
4.98k
    if (!EvaluateBlock(CurInst, NextBB))
702
1.88k
      return false;
703
3.10k
704
3.10k
    if (!NextBB) {
705
2.81k
      // Successfully running until there's no next block means that we found
706
2.81k
      // the return.  Fill it the return value and pop the call stack.
707
2.81k
      ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator());
708
2.81k
      if (RI->getNumOperands())
709
2.07k
        RetVal = getVal(RI->getOperand(0));
710
2.81k
      CallStack.pop_back();
711
2.81k
      return true;
712
2.81k
    }
713
288
714
288
    // Okay, we succeeded in evaluating this control flow.  See if we have
715
288
    // executed the new block before.  If so, we have a looping function,
716
288
    // which we cannot evaluate in reasonable time.
717
288
    if (!ExecutedBlocks.insert(NextBB).second)
718
48
      return false;  // looped!
719
240
720
240
    // Okay, we have never been in this block before.  Check to see if there
721
240
    // are any PHI nodes.  If so, evaluate them with information about where
722
240
    // we came from.
723
240
    PHINode *PN = nullptr;
724
240
    for (CurInst = NextBB->begin();
725
366
         (PN = dyn_cast<PHINode>(CurInst)); 
++CurInst126
)
726
126
      setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB)));
727
240
728
240
    // Advance to the next block.
729
240
    CurBB = NextBB;
730
240
  }
731
4.74k
}