1//===-- Lint.cpp - Check for common errors in LLVM IR ---------------------===//
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// This pass statically checks for common and easily-identified constructs
11// which produce undefined or likely unintended behavior in LLVM IR.
12//
13// It is not a guarantee of correctness, in two ways. First, it isn't
14// comprehensive. There are checks which could be done statically which are
15// not yet implemented. Some of these are indicated by TODO comments, but
16// those aren't comprehensive either. Second, many conditions cannot be
17// checked statically. This pass does no dynamic instrumentation, so it
18// can't check for all possible problems.
19//
20// Another limitation is that it assumes all code will be executed. A store
21// through a null pointer in a basic block which is never reached is harmless,
22// but this pass will warn about it anyway. This is the main reason why most
23// of these checks live here instead of in the Verifier pass.
24//
25// Optimization passes may make conditions that this pass checks for more or
26// less obvious. If an optimization pass appears to be introducing a warning,
27// it may be that the optimization pass is merely exposing an existing
28// condition in the code.
29//
30// This code may be run before instcombine. In many cases, instcombine checks
31// for the same kinds of things and turns instructions with undefined behavior
32// into unreachable (or equivalent). Because of this, this pass makes some
33// effort to look through bitcasts and so on.
34//
35//===----------------------------------------------------------------------===//
36
37#include "llvm/Analysis/Passes.h"
38#include "llvm/Analysis/AliasAnalysis.h"
39#include "llvm/Analysis/InstructionSimplify.h"
40#include "llvm/Analysis/ConstantFolding.h"
41#include "llvm/Analysis/Dominators.h"
42#include "llvm/Analysis/Lint.h"
43#include "llvm/Analysis/Loads.h"
44#include "llvm/Analysis/ValueTracking.h"
45#include "llvm/Assembly/Writer.h"
46#include "llvm/Target/TargetData.h"
47#include "llvm/Target/TargetLibraryInfo.h"
48#include "llvm/Pass.h"
49#include "llvm/PassManager.h"
50#include "llvm/IntrinsicInst.h"
51#include "llvm/Function.h"
52#include "llvm/Support/CallSite.h"
53#include "llvm/Support/Debug.h"
54#include "llvm/Support/InstVisitor.h"
55#include "llvm/Support/raw_ostream.h"
56#include "llvm/ADT/STLExtras.h"
57using namespace llvm;
58
59namespace {
60  namespace MemRef {
61    static unsigned Read     = 1;
62    static unsigned Write    = 2;
63    static unsigned Callee   = 4;
64    static unsigned Branchee = 8;
65  }
66
67  class Lint : public FunctionPass, public InstVisitor<Lint> {
68    friend class InstVisitor<Lint>;
69
70    void visitFunction(Function &F);
71
72    void visitCallSite(CallSite CS);
73    void visitMemoryReference(Instruction &I, Value *Ptr,
74                              uint64_t Size, unsigned Align,
75                              Type *Ty, unsigned Flags);
76
77    void visitCallInst(CallInst &I);
78    void visitInvokeInst(InvokeInst &I);
79    void visitReturnInst(ReturnInst &I);
80    void visitLoadInst(LoadInst &I);
81    void visitStoreInst(StoreInst &I);
82    void visitXor(BinaryOperator &I);
83    void visitSub(BinaryOperator &I);
84    void visitLShr(BinaryOperator &I);
85    void visitAShr(BinaryOperator &I);
86    void visitShl(BinaryOperator &I);
87    void visitSDiv(BinaryOperator &I);
88    void visitUDiv(BinaryOperator &I);
89    void visitSRem(BinaryOperator &I);
90    void visitURem(BinaryOperator &I);
91    void visitAllocaInst(AllocaInst &I);
92    void visitVAArgInst(VAArgInst &I);
93    void visitIndirectBrInst(IndirectBrInst &I);
94    void visitExtractElementInst(ExtractElementInst &I);
95    void visitInsertElementInst(InsertElementInst &I);
96    void visitUnreachableInst(UnreachableInst &I);
97
98    Value *findValue(Value *V, bool OffsetOk) const;
99    Value *findValueImpl(Value *V, bool OffsetOk,
100                         SmallPtrSet<Value *, 4> &Visited) const;
101
102  public:
103    Module *Mod;
104    AliasAnalysis *AA;
105    DominatorTree *DT;
106    TargetData *TD;
107    TargetLibraryInfo *TLI;
108
109    std::string Messages;
110    raw_string_ostream MessagesStr;
111
112    static char ID; // Pass identification, replacement for typeid
113    Lint() : FunctionPass(ID), MessagesStr(Messages) {
114      initializeLintPass(*PassRegistry::getPassRegistry());
115    }
116
117    virtual bool runOnFunction(Function &F);
118
119    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
120      AU.setPreservesAll();
121      AU.addRequired<AliasAnalysis>();
122      AU.addRequired<TargetLibraryInfo>();
123      AU.addRequired<DominatorTree>();
124    }
125    virtual void print(raw_ostream &O, const Module *M) const {}
126
127    void WriteValue(const Value *V) {
128      if (!V) return;
129      if (isa<Instruction>(V)) {
130        MessagesStr << *V << '\n';
131      } else {
132        WriteAsOperand(MessagesStr, V, true, Mod);
133        MessagesStr << '\n';
134      }
135    }
136
137    // CheckFailed - A check failed, so print out the condition and the message
138    // that failed.  This provides a nice place to put a breakpoint if you want
139    // to see why something is not correct.
140    void CheckFailed(const Twine &Message,
141                     const Value *V1 = 0, const Value *V2 = 0,
142                     const Value *V3 = 0, const Value *V4 = 0) {
143      MessagesStr << Message.str() << "\n";
144      WriteValue(V1);
145      WriteValue(V2);
146      WriteValue(V3);
147      WriteValue(V4);
148    }
149  };
150}
151
152char Lint::ID = 0;
153INITIALIZE_PASS_BEGIN(Lint, "lint", "Statically lint-checks LLVM IR",
154                      false, true)
155INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
156INITIALIZE_PASS_DEPENDENCY(DominatorTree)
157INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
158INITIALIZE_PASS_END(Lint, "lint", "Statically lint-checks LLVM IR",
159                    false, true)
160
161// Assert - We know that cond should be true, if not print an error message.
162#define Assert(C, M) \
163    do { if (!(C)) { CheckFailed(M); return; } } while (0)
164#define Assert1(C, M, V1) \
165    do { if (!(C)) { CheckFailed(M, V1); return; } } while (0)
166#define Assert2(C, M, V1, V2) \
167    do { if (!(C)) { CheckFailed(M, V1, V2); return; } } while (0)
168#define Assert3(C, M, V1, V2, V3) \
169    do { if (!(C)) { CheckFailed(M, V1, V2, V3); return; } } while (0)
170#define Assert4(C, M, V1, V2, V3, V4) \
171    do { if (!(C)) { CheckFailed(M, V1, V2, V3, V4); return; } } while (0)
172
173// Lint::run - This is the main Analysis entry point for a
174// function.
175//
176bool Lint::runOnFunction(Function &F) {
177  Mod = F.getParent();
178  AA = &getAnalysis<AliasAnalysis>();
179  DT = &getAnalysis<DominatorTree>();
180  TD = getAnalysisIfAvailable<TargetData>();
181  TLI = &getAnalysis<TargetLibraryInfo>();
182  visit(F);
183  dbgs() << MessagesStr.str();
184  Messages.clear();
185  return false;
186}
187
188void Lint::visitFunction(Function &F) {
189  // This isn't undefined behavior, it's just a little unusual, and it's a
190  // fairly common mistake to neglect to name a function.
191  Assert1(F.hasName() || F.hasLocalLinkage(),
192          "Unusual: Unnamed function with non-local linkage", &F);
193
194  // TODO: Check for irreducible control flow.
195}
196
197void Lint::visitCallSite(CallSite CS) {
198  Instruction &I = *CS.getInstruction();
199  Value *Callee = CS.getCalledValue();
200
201  visitMemoryReference(I, Callee, AliasAnalysis::UnknownSize,
202                       0, 0, MemRef::Callee);
203
204  if (Function *F = dyn_cast<Function>(findValue(Callee, /*OffsetOk=*/false))) {
205    Assert1(CS.getCallingConv() == F->getCallingConv(),
206            "Undefined behavior: Caller and callee calling convention differ",
207            &I);
208
209    FunctionType *FT = F->getFunctionType();
210    unsigned NumActualArgs = unsigned(CS.arg_end()-CS.arg_begin());
211
212    Assert1(FT->isVarArg() ?
213              FT->getNumParams() <= NumActualArgs :
214              FT->getNumParams() == NumActualArgs,
215            "Undefined behavior: Call argument count mismatches callee "
216            "argument count", &I);
217
218    Assert1(FT->getReturnType() == I.getType(),
219            "Undefined behavior: Call return type mismatches "
220            "callee return type", &I);
221
222    // Check argument types (in case the callee was casted) and attributes.
223    // TODO: Verify that caller and callee attributes are compatible.
224    Function::arg_iterator PI = F->arg_begin(), PE = F->arg_end();
225    CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end();
226    for (; AI != AE; ++AI) {
227      Value *Actual = *AI;
228      if (PI != PE) {
229        Argument *Formal = PI++;
230        Assert1(Formal->getType() == Actual->getType(),
231                "Undefined behavior: Call argument type mismatches "
232                "callee parameter type", &I);
233
234        // Check that noalias arguments don't alias other arguments. This is
235        // not fully precise because we don't know the sizes of the dereferenced
236        // memory regions.
237        if (Formal->hasNoAliasAttr() && Actual->getType()->isPointerTy())
238          for (CallSite::arg_iterator BI = CS.arg_begin(); BI != AE; ++BI)
239            if (AI != BI && (*BI)->getType()->isPointerTy()) {
240              AliasAnalysis::AliasResult Result = AA->alias(*AI, *BI);
241              Assert1(Result != AliasAnalysis::MustAlias &&
242                      Result != AliasAnalysis::PartialAlias,
243                      "Unusual: noalias argument aliases another argument", &I);
244            }
245
246        // Check that an sret argument points to valid memory.
247        if (Formal->hasStructRetAttr() && Actual->getType()->isPointerTy()) {
248          Type *Ty =
249            cast<PointerType>(Formal->getType())->getElementType();
250          visitMemoryReference(I, Actual, AA->getTypeStoreSize(Ty),
251                               TD ? TD->getABITypeAlignment(Ty) : 0,
252                               Ty, MemRef::Read | MemRef::Write);
253        }
254      }
255    }
256  }
257
258  if (CS.isCall() && cast<CallInst>(CS.getInstruction())->isTailCall())
259    for (CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end();
260         AI != AE; ++AI) {
261      Value *Obj = findValue(*AI, /*OffsetOk=*/true);
262      Assert1(!isa<AllocaInst>(Obj),
263              "Undefined behavior: Call with \"tail\" keyword references "
264              "alloca", &I);
265    }
266
267
268  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I))
269    switch (II->getIntrinsicID()) {
270    default: break;
271
272    // TODO: Check more intrinsics
273
274    case Intrinsic::memcpy: {
275      MemCpyInst *MCI = cast<MemCpyInst>(&I);
276      // TODO: If the size is known, use it.
277      visitMemoryReference(I, MCI->getDest(), AliasAnalysis::UnknownSize,
278                           MCI->getAlignment(), 0,
279                           MemRef::Write);
280      visitMemoryReference(I, MCI->getSource(), AliasAnalysis::UnknownSize,
281                           MCI->getAlignment(), 0,
282                           MemRef::Read);
283
284      // Check that the memcpy arguments don't overlap. The AliasAnalysis API
285      // isn't expressive enough for what we really want to do. Known partial
286      // overlap is not distinguished from the case where nothing is known.
287      uint64_t Size = 0;
288      if (const ConstantInt *Len =
289            dyn_cast<ConstantInt>(findValue(MCI->getLength(),
290                                            /*OffsetOk=*/false)))
291        if (Len->getValue().isIntN(32))
292          Size = Len->getValue().getZExtValue();
293      Assert1(AA->alias(MCI->getSource(), Size, MCI->getDest(), Size) !=
294              AliasAnalysis::MustAlias,
295              "Undefined behavior: memcpy source and destination overlap", &I);
296      break;
297    }
298    case Intrinsic::memmove: {
299      MemMoveInst *MMI = cast<MemMoveInst>(&I);
300      // TODO: If the size is known, use it.
301      visitMemoryReference(I, MMI->getDest(), AliasAnalysis::UnknownSize,
302                           MMI->getAlignment(), 0,
303                           MemRef::Write);
304      visitMemoryReference(I, MMI->getSource(), AliasAnalysis::UnknownSize,
305                           MMI->getAlignment(), 0,
306                           MemRef::Read);
307      break;
308    }
309    case Intrinsic::memset: {
310      MemSetInst *MSI = cast<MemSetInst>(&I);
311      // TODO: If the size is known, use it.
312      visitMemoryReference(I, MSI->getDest(), AliasAnalysis::UnknownSize,
313                           MSI->getAlignment(), 0,
314                           MemRef::Write);
315      break;
316    }
317
318    case Intrinsic::vastart:
319      Assert1(I.getParent()->getParent()->isVarArg(),
320              "Undefined behavior: va_start called in a non-varargs function",
321              &I);
322
323      visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize,
324                           0, 0, MemRef::Read | MemRef::Write);
325      break;
326    case Intrinsic::vacopy:
327      visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize,
328                           0, 0, MemRef::Write);
329      visitMemoryReference(I, CS.getArgument(1), AliasAnalysis::UnknownSize,
330                           0, 0, MemRef::Read);
331      break;
332    case Intrinsic::vaend:
333      visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize,
334                           0, 0, MemRef::Read | MemRef::Write);
335      break;
336
337    case Intrinsic::stackrestore:
338      // Stackrestore doesn't read or write memory, but it sets the
339      // stack pointer, which the compiler may read from or write to
340      // at any time, so check it for both readability and writeability.
341      visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize,
342                           0, 0, MemRef::Read | MemRef::Write);
343      break;
344    }
345}
346
347void Lint::visitCallInst(CallInst &I) {
348  return visitCallSite(&I);
349}
350
351void Lint::visitInvokeInst(InvokeInst &I) {
352  return visitCallSite(&I);
353}
354
355void Lint::visitReturnInst(ReturnInst &I) {
356  Function *F = I.getParent()->getParent();
357  Assert1(!F->doesNotReturn(),
358          "Unusual: Return statement in function with noreturn attribute",
359          &I);
360
361  if (Value *V = I.getReturnValue()) {
362    Value *Obj = findValue(V, /*OffsetOk=*/true);
363    Assert1(!isa<AllocaInst>(Obj),
364            "Unusual: Returning alloca value", &I);
365  }
366}
367
368// TODO: Check that the reference is in bounds.
369// TODO: Check readnone/readonly function attributes.
370void Lint::visitMemoryReference(Instruction &I,
371                                Value *Ptr, uint64_t Size, unsigned Align,
372                                Type *Ty, unsigned Flags) {
373  // If no memory is being referenced, it doesn't matter if the pointer
374  // is valid.
375  if (Size == 0)
376    return;
377
378  Value *UnderlyingObject = findValue(Ptr, /*OffsetOk=*/true);
379  Assert1(!isa<ConstantPointerNull>(UnderlyingObject),
380          "Undefined behavior: Null pointer dereference", &I);
381  Assert1(!isa<UndefValue>(UnderlyingObject),
382          "Undefined behavior: Undef pointer dereference", &I);
383  Assert1(!isa<ConstantInt>(UnderlyingObject) ||
384          !cast<ConstantInt>(UnderlyingObject)->isAllOnesValue(),
385          "Unusual: All-ones pointer dereference", &I);
386  Assert1(!isa<ConstantInt>(UnderlyingObject) ||
387          !cast<ConstantInt>(UnderlyingObject)->isOne(),
388          "Unusual: Address one pointer dereference", &I);
389
390  if (Flags & MemRef::Write) {
391    if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(UnderlyingObject))
392      Assert1(!GV->isConstant(),
393              "Undefined behavior: Write to read-only memory", &I);
394    Assert1(!isa<Function>(UnderlyingObject) &&
395            !isa<BlockAddress>(UnderlyingObject),
396            "Undefined behavior: Write to text section", &I);
397  }
398  if (Flags & MemRef::Read) {
399    Assert1(!isa<Function>(UnderlyingObject),
400            "Unusual: Load from function body", &I);
401    Assert1(!isa<BlockAddress>(UnderlyingObject),
402            "Undefined behavior: Load from block address", &I);
403  }
404  if (Flags & MemRef::Callee) {
405    Assert1(!isa<BlockAddress>(UnderlyingObject),
406            "Undefined behavior: Call to block address", &I);
407  }
408  if (Flags & MemRef::Branchee) {
409    Assert1(!isa<Constant>(UnderlyingObject) ||
410            isa<BlockAddress>(UnderlyingObject),
411            "Undefined behavior: Branch to non-blockaddress", &I);
412  }
413
414  if (TD) {
415    if (Align == 0 && Ty) Align = TD->getABITypeAlignment(Ty);
416
417    if (Align != 0) {
418      unsigned BitWidth = TD->getTypeSizeInBits(Ptr->getType());
419      APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
420      ComputeMaskedBits(Ptr, KnownZero, KnownOne, TD);
421      Assert1(!(KnownOne & APInt::getLowBitsSet(BitWidth, Log2_32(Align))),
422              "Undefined behavior: Memory reference address is misaligned", &I);
423    }
424  }
425}
426
427void Lint::visitLoadInst(LoadInst &I) {
428  visitMemoryReference(I, I.getPointerOperand(),
429                       AA->getTypeStoreSize(I.getType()), I.getAlignment(),
430                       I.getType(), MemRef::Read);
431}
432
433void Lint::visitStoreInst(StoreInst &I) {
434  visitMemoryReference(I, I.getPointerOperand(),
435                       AA->getTypeStoreSize(I.getOperand(0)->getType()),
436                       I.getAlignment(),
437                       I.getOperand(0)->getType(), MemRef::Write);
438}
439
440void Lint::visitXor(BinaryOperator &I) {
441  Assert1(!isa<UndefValue>(I.getOperand(0)) ||
442          !isa<UndefValue>(I.getOperand(1)),
443          "Undefined result: xor(undef, undef)", &I);
444}
445
446void Lint::visitSub(BinaryOperator &I) {
447  Assert1(!isa<UndefValue>(I.getOperand(0)) ||
448          !isa<UndefValue>(I.getOperand(1)),
449          "Undefined result: sub(undef, undef)", &I);
450}
451
452void Lint::visitLShr(BinaryOperator &I) {
453  if (ConstantInt *CI =
454        dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false)))
455    Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()),
456            "Undefined result: Shift count out of range", &I);
457}
458
459void Lint::visitAShr(BinaryOperator &I) {
460  if (ConstantInt *CI =
461        dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false)))
462    Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()),
463            "Undefined result: Shift count out of range", &I);
464}
465
466void Lint::visitShl(BinaryOperator &I) {
467  if (ConstantInt *CI =
468        dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false)))
469    Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()),
470            "Undefined result: Shift count out of range", &I);
471}
472
473static bool isZero(Value *V, TargetData *TD) {
474  // Assume undef could be zero.
475  if (isa<UndefValue>(V)) return true;
476
477  unsigned BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
478  APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
479  ComputeMaskedBits(V, KnownZero, KnownOne, TD);
480  return KnownZero.isAllOnesValue();
481}
482
483void Lint::visitSDiv(BinaryOperator &I) {
484  Assert1(!isZero(I.getOperand(1), TD),
485          "Undefined behavior: Division by zero", &I);
486}
487
488void Lint::visitUDiv(BinaryOperator &I) {
489  Assert1(!isZero(I.getOperand(1), TD),
490          "Undefined behavior: Division by zero", &I);
491}
492
493void Lint::visitSRem(BinaryOperator &I) {
494  Assert1(!isZero(I.getOperand(1), TD),
495          "Undefined behavior: Division by zero", &I);
496}
497
498void Lint::visitURem(BinaryOperator &I) {
499  Assert1(!isZero(I.getOperand(1), TD),
500          "Undefined behavior: Division by zero", &I);
501}
502
503void Lint::visitAllocaInst(AllocaInst &I) {
504  if (isa<ConstantInt>(I.getArraySize()))
505    // This isn't undefined behavior, it's just an obvious pessimization.
506    Assert1(&I.getParent()->getParent()->getEntryBlock() == I.getParent(),
507            "Pessimization: Static alloca outside of entry block", &I);
508
509  // TODO: Check for an unusual size (MSB set?)
510}
511
512void Lint::visitVAArgInst(VAArgInst &I) {
513  visitMemoryReference(I, I.getOperand(0), AliasAnalysis::UnknownSize, 0, 0,
514                       MemRef::Read | MemRef::Write);
515}
516
517void Lint::visitIndirectBrInst(IndirectBrInst &I) {
518  visitMemoryReference(I, I.getAddress(), AliasAnalysis::UnknownSize, 0, 0,
519                       MemRef::Branchee);
520
521  Assert1(I.getNumDestinations() != 0,
522          "Undefined behavior: indirectbr with no destinations", &I);
523}
524
525void Lint::visitExtractElementInst(ExtractElementInst &I) {
526  if (ConstantInt *CI =
527        dyn_cast<ConstantInt>(findValue(I.getIndexOperand(),
528                                        /*OffsetOk=*/false)))
529    Assert1(CI->getValue().ult(I.getVectorOperandType()->getNumElements()),
530            "Undefined result: extractelement index out of range", &I);
531}
532
533void Lint::visitInsertElementInst(InsertElementInst &I) {
534  if (ConstantInt *CI =
535        dyn_cast<ConstantInt>(findValue(I.getOperand(2),
536                                        /*OffsetOk=*/false)))
537    Assert1(CI->getValue().ult(I.getType()->getNumElements()),
538            "Undefined result: insertelement index out of range", &I);
539}
540
541void Lint::visitUnreachableInst(UnreachableInst &I) {
542  // This isn't undefined behavior, it's merely suspicious.
543  Assert1(&I == I.getParent()->begin() ||
544          prior(BasicBlock::iterator(&I))->mayHaveSideEffects(),
545          "Unusual: unreachable immediately preceded by instruction without "
546          "side effects", &I);
547}
548
549/// findValue - Look through bitcasts and simple memory reference patterns
550/// to identify an equivalent, but more informative, value.  If OffsetOk
551/// is true, look through getelementptrs with non-zero offsets too.
552///
553/// Most analysis passes don't require this logic, because instcombine
554/// will simplify most of these kinds of things away. But it's a goal of
555/// this Lint pass to be useful even on non-optimized IR.
556Value *Lint::findValue(Value *V, bool OffsetOk) const {
557  SmallPtrSet<Value *, 4> Visited;
558  return findValueImpl(V, OffsetOk, Visited);
559}
560
561/// findValueImpl - Implementation helper for findValue.
562Value *Lint::findValueImpl(Value *V, bool OffsetOk,
563                           SmallPtrSet<Value *, 4> &Visited) const {
564  // Detect self-referential values.
565  if (!Visited.insert(V))
566    return UndefValue::get(V->getType());
567
568  // TODO: Look through sext or zext cast, when the result is known to
569  // be interpreted as signed or unsigned, respectively.
570  // TODO: Look through eliminable cast pairs.
571  // TODO: Look through calls with unique return values.
572  // TODO: Look through vector insert/extract/shuffle.
573  V = OffsetOk ? GetUnderlyingObject(V, TD) : V->stripPointerCasts();
574  if (LoadInst *L = dyn_cast<LoadInst>(V)) {
575    BasicBlock::iterator BBI = L;
576    BasicBlock *BB = L->getParent();
577    SmallPtrSet<BasicBlock *, 4> VisitedBlocks;
578    for (;;) {
579      if (!VisitedBlocks.insert(BB)) break;
580      if (Value *U = FindAvailableLoadedValue(L->getPointerOperand(),
581                                              BB, BBI, 6, AA))
582        return findValueImpl(U, OffsetOk, Visited);
583      if (BBI != BB->begin()) break;
584      BB = BB->getUniquePredecessor();
585      if (!BB) break;
586      BBI = BB->end();
587    }
588  } else if (PHINode *PN = dyn_cast<PHINode>(V)) {
589    if (Value *W = PN->hasConstantValue())
590      if (W != V)
591        return findValueImpl(W, OffsetOk, Visited);
592  } else if (CastInst *CI = dyn_cast<CastInst>(V)) {
593    if (CI->isNoopCast(TD ? TD->getIntPtrType(V->getContext()) :
594                            Type::getInt64Ty(V->getContext())))
595      return findValueImpl(CI->getOperand(0), OffsetOk, Visited);
596  } else if (ExtractValueInst *Ex = dyn_cast<ExtractValueInst>(V)) {
597    if (Value *W = FindInsertedValue(Ex->getAggregateOperand(),
598                                     Ex->getIndices()))
599      if (W != V)
600        return findValueImpl(W, OffsetOk, Visited);
601  } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
602    // Same as above, but for ConstantExpr instead of Instruction.
603    if (Instruction::isCast(CE->getOpcode())) {
604      if (CastInst::isNoopCast(Instruction::CastOps(CE->getOpcode()),
605                               CE->getOperand(0)->getType(),
606                               CE->getType(),
607                               TD ? TD->getIntPtrType(V->getContext()) :
608                                    Type::getInt64Ty(V->getContext())))
609        return findValueImpl(CE->getOperand(0), OffsetOk, Visited);
610    } else if (CE->getOpcode() == Instruction::ExtractValue) {
611      ArrayRef<unsigned> Indices = CE->getIndices();
612      if (Value *W = FindInsertedValue(CE->getOperand(0), Indices))
613        if (W != V)
614          return findValueImpl(W, OffsetOk, Visited);
615    }
616  }
617
618  // As a last resort, try SimplifyInstruction or constant folding.
619  if (Instruction *Inst = dyn_cast<Instruction>(V)) {
620    if (Value *W = SimplifyInstruction(Inst, TD, TLI, DT))
621      return findValueImpl(W, OffsetOk, Visited);
622  } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
623    if (Value *W = ConstantFoldConstantExpression(CE, TD, TLI))
624      if (W != V)
625        return findValueImpl(W, OffsetOk, Visited);
626  }
627
628  return V;
629}
630
631//===----------------------------------------------------------------------===//
632//  Implement the public interfaces to this file...
633//===----------------------------------------------------------------------===//
634
635FunctionPass *llvm::createLintPass() {
636  return new Lint();
637}
638
639/// lintFunction - Check a function for errors, printing messages on stderr.
640///
641void llvm::lintFunction(const Function &f) {
642  Function &F = const_cast<Function&>(f);
643  assert(!F.isDeclaration() && "Cannot lint external functions");
644
645  FunctionPassManager FPM(F.getParent());
646  Lint *V = new Lint();
647  FPM.add(V);
648  FPM.run(F);
649}
650
651/// lintModule - Check a module for errors, printing messages on stderr.
652///
653void llvm::lintModule(const Module &M) {
654  PassManager PM;
655  Lint *V = new Lint();
656  PM.add(V);
657  PM.run(const_cast<Module&>(M));
658}
659