lib/Analysis/Lint.cpp

   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.
  23
  24 // Optimization passes may make conditions that this pass checks for more or
  25 // less obvious. If an optimization pass appears to be introducing a warning,
  26 // it may be that the optimization pass is merely exposing an existing
  27 // condition in the code.
  28 //
  29 // This code may be run before instcombine. In many cases, instcombine checks
  30 // for the same kinds of things and turns instructions with undefined behavior
  31 // into unreachable (or equivalent). Because of this, this pass makes some
  32 // effort to look through bitcasts and so on.
  33 //
  34 //===----------------------------------------------------------------------===//
  35
  36 #include "llvm/Analysis/Passes.h"
  37 #include "llvm/Analysis/AliasAnalysis.h"
  38 #include "llvm/Analysis/Lint.h"
  39 #include "llvm/Analysis/ValueTracking.h"
  40 #include "llvm/Assembly/Writer.h"
  41 #include "llvm/Target/TargetData.h"
  42 #include "llvm/Pass.h"
  43 #include "llvm/PassManager.h"
  44 #include "llvm/IntrinsicInst.h"
  45 #include "llvm/Function.h"
  46 #include "llvm/Support/CallSite.h"
  47 #include "llvm/Support/Debug.h"
  48 #include "llvm/Support/InstVisitor.h"
  49 #include "llvm/Support/raw_ostream.h"
  50 using namespace llvm;
  51
  52 namespace {
  53   class Lint : public FunctionPass, public InstVisitor<Lint> {
  54     friend class InstVisitor<Lint>;
  55
  56     void visitCallSite(CallSite CS);
  57     void visitMemoryReference(Instruction &I, Value *Ptr, unsigned Align,
  58                               const Type *Ty);
  59
  60     void visitInstruction(Instruction &I);
  61     void visitCallInst(CallInst &I);
  62     void visitInvokeInst(InvokeInst &I);
  63     void visitReturnInst(ReturnInst &I);
  64     void visitLoadInst(LoadInst &I);
  65     void visitStoreInst(StoreInst &I);
  66     void visitLShr(BinaryOperator &I);
  67     void visitAShr(BinaryOperator &I);
  68     void visitShl(BinaryOperator &I);
  69     void visitSDiv(BinaryOperator &I);
  70     void visitUDiv(BinaryOperator &I);
  71     void visitSRem(BinaryOperator &I);
  72     void visitURem(BinaryOperator &I);
  73     void visitAllocaInst(AllocaInst &I);
  74     void visitVAArgInst(VAArgInst &I);
  75     void visitIndirectBrInst(IndirectBrInst &I);
  76     void visitExtractElementInst(ExtractElementInst &I);
  77     void visitInsertElementInst(InsertElementInst &I);
  78
  79   public:
  80     Module *Mod;
  81     AliasAnalysis *AA;
  82     TargetData *TD;
  83
  84     std::string Messages;
  85     raw_string_ostream MessagesStr;
  86
  87     static char ID; // Pass identification, replacement for typeid
  88     Lint() : FunctionPass(&ID), MessagesStr(Messages) {}
  89
  90     virtual bool runOnFunction(Function &F);
  91
  92     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  93       AU.setPreservesAll();
  94       AU.addRequired<AliasAnalysis>();
  95     }
  96     virtual void print(raw_ostream &O, const Module *M) const {}
  97
  98     void WriteValue(const Value *V) {
  99       if (!V) return;
 100       if (isa<Instruction>(V)) {
 101         MessagesStr << *V << '\n';
 102       } else {
 103         WriteAsOperand(MessagesStr, V, true, Mod);
 104         MessagesStr << '\n';
 105       }
 106     }
 107
 108     void WriteType(const Type *T) {
 109       if (!T) return;
 110       MessagesStr << ' ';
 111       WriteTypeSymbolic(MessagesStr, T, Mod);
 112     }
 113
 114     // CheckFailed - A check failed, so print out the condition and the message
 115     // that failed.  This provides a nice place to put a breakpoint if you want
 116     // to see why something is not correct.
 117     void CheckFailed(const Twine &Message,
 118                      const Value *V1 = 0, const Value *V2 = 0,
 119                      const Value *V3 = 0, const Value *V4 = 0) {
 120       MessagesStr << Message.str() << "\n";
 121       WriteValue(V1);
 122       WriteValue(V2);
 123       WriteValue(V3);
 124       WriteValue(V4);
 125     }
 126
 127     void CheckFailed(const Twine &Message, const Value *V1,
 128                      const Type *T2, const Value *V3 = 0) {
 129       MessagesStr << Message.str() << "\n";
 130       WriteValue(V1);
 131       WriteType(T2);
 132       WriteValue(V3);
 133     }
 134
 135     void CheckFailed(const Twine &Message, const Type *T1,
 136                      const Type *T2 = 0, const Type *T3 = 0) {
 137       MessagesStr << Message.str() << "\n";
 138       WriteType(T1);
 139       WriteType(T2);
 140       WriteType(T3);
 141     }
 142   };
 143 }
 144
 145 char Lint::ID = 0;
 146 static RegisterPass<Lint>
 147 X("lint", "Statically lint-checks LLVM IR", false, true);
 148
 149 // Assert - We know that cond should be true, if not print an error message.
 150 #define Assert(C, M) \
 151     do { if (!(C)) { CheckFailed(M); return; } } while (0)
 152 #define Assert1(C, M, V1) \
 153     do { if (!(C)) { CheckFailed(M, V1); return; } } while (0)
 154 #define Assert2(C, M, V1, V2) \
 155     do { if (!(C)) { CheckFailed(M, V1, V2); return; } } while (0)
 156 #define Assert3(C, M, V1, V2, V3) \
 157     do { if (!(C)) { CheckFailed(M, V1, V2, V3); return; } } while (0)
 158 #define Assert4(C, M, V1, V2, V3, V4) \
 159     do { if (!(C)) { CheckFailed(M, V1, V2, V3, V4); return; } } while (0)
 160
 161 // Lint::run - This is the main Analysis entry point for a
 162 // function.
 163 //
 164 bool Lint::runOnFunction(Function &F) {
 165   Mod = F.getParent();
 166   AA = &getAnalysis<AliasAnalysis>();
 167   TD = getAnalysisIfAvailable<TargetData>();
 168   visit(F);
 169   dbgs() << MessagesStr.str();
 170   return false;
 171 }
 172
 173 void Lint::visitInstruction(Instruction &I) {
 174 }
 175
 176 void Lint::visitCallSite(CallSite CS) {
 177   Instruction &I = *CS.getInstruction();
 178   Value *Callee = CS.getCalledValue();
 179
 180   // TODO: Check function alignment?
 181   visitMemoryReference(I, Callee, 0, 0);
 182
 183   if (Function *F = dyn_cast<Function>(Callee->stripPointerCasts())) {
 184     Assert1(CS.getCallingConv() == F->getCallingConv(),
 185             "Caller and callee calling convention differ", &I);
 186
 187     const FunctionType *FT = F->getFunctionType();
 188     unsigned NumActualArgs = unsigned(CS.arg_end()-CS.arg_begin());
 189
 190     Assert1(FT->isVarArg() ?
 191               FT->getNumParams() <= NumActualArgs :
 192               FT->getNumParams() == NumActualArgs,
 193             "Call argument count mismatches callee argument count", &I);
 194
 195     // TODO: Check argument types (in case the callee was casted)
 196
 197     // TODO: Check ABI-significant attributes.
 198
 199     // TODO: Check noalias attribute.
 200
 201     // TODO: Check sret attribute.
 202   }
 203
 204   // TODO: Check the "tail" keyword constraints.
 205
 206   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I))
 207     switch (II->getIntrinsicID()) {
 208     default: break;
 209
 210     // TODO: Check more intrinsics
 211
 212     case Intrinsic::memcpy: {
 213       MemCpyInst *MCI = cast<MemCpyInst>(&I);
 214       visitMemoryReference(I, MCI->getSource(), MCI->getAlignment(), 0);
 215       visitMemoryReference(I, MCI->getDest(), MCI->getAlignment(), 0);
 216
 217       unsigned Size = 0;
 218       if (const ConstantInt *Len =
 219             dyn_cast<ConstantInt>(MCI->getLength()->stripPointerCasts()))
 220         if (Len->getValue().isIntN(32))
 221           Size = Len->getValue().getZExtValue();
 222       Assert1(AA->alias(MCI->getSource(), Size, MCI->getDest(), Size) !=
 223               AliasAnalysis::MustAlias,
 224               "memcpy source and destination overlap", &I);
 225       break;
 226     }
 227     case Intrinsic::memmove: {
 228       MemMoveInst *MMI = cast<MemMoveInst>(&I);
 229       visitMemoryReference(I, MMI->getSource(), MMI->getAlignment(), 0);
 230       visitMemoryReference(I, MMI->getDest(), MMI->getAlignment(), 0);
 231       break;
 232     }
 233     case Intrinsic::memset: {
 234       MemSetInst *MSI = cast<MemSetInst>(&I);
 235       visitMemoryReference(I, MSI->getDest(), MSI->getAlignment(), 0);
 236       break;
 237     }
 238
 239     case Intrinsic::vastart:
 240       visitMemoryReference(I, CS.getArgument(0), 0, 0);
 241       break;
 242     case Intrinsic::vacopy:
 243       visitMemoryReference(I, CS.getArgument(0), 0, 0);
 244       visitMemoryReference(I, CS.getArgument(1), 0, 0);
 245       break;
 246     case Intrinsic::vaend:
 247       visitMemoryReference(I, CS.getArgument(0), 0, 0);
 248       break;
 249
 250     case Intrinsic::stackrestore:
 251       visitMemoryReference(I, CS.getArgument(0), 0, 0);
 252       break;
 253     }
 254 }
 255
 256 void Lint::visitCallInst(CallInst &I) {
 257   return visitCallSite(&I);
 258 }
 259
 260 void Lint::visitInvokeInst(InvokeInst &I) {
 261   return visitCallSite(&I);
 262 }
 263
 264 void Lint::visitReturnInst(ReturnInst &I) {
 265   Function *F = I.getParent()->getParent();
 266   Assert1(!F->doesNotReturn(),
 267           "Return statement in function with noreturn attribute", &I);
 268 }
 269
 270 // TODO: Add a length argument and check that the reference is in bounds
 271 // TODO: Add read/write/execute flags and check for writing to read-only
 272 //       memory or jumping to suspicious writeable memory
 273 void Lint::visitMemoryReference(Instruction &I,
 274                                 Value *Ptr, unsigned Align, const Type *Ty) {
 275   Assert1(!isa<ConstantPointerNull>(Ptr->getUnderlyingObject()),
 276           "Null pointer dereference", &I);
 277   Assert1(!isa<UndefValue>(Ptr->getUnderlyingObject()),
 278           "Undef pointer dereference", &I);
 279
 280   if (TD) {
 281     if (Align == 0 && Ty) Align = TD->getABITypeAlignment(Ty);
 282
 283     if (Align != 0) {
 284       unsigned BitWidth = TD->getTypeSizeInBits(Ptr->getType());
 285       APInt Mask = APInt::getAllOnesValue(BitWidth),
 286                    KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
 287       ComputeMaskedBits(Ptr, Mask, KnownZero, KnownOne, TD);
 288       Assert1(!(KnownOne & APInt::getLowBitsSet(BitWidth, Log2_32(Align))),
 289               "Memory reference address is misaligned", &I);
 290     }
 291   }
 292 }
 293
 294 void Lint::visitLoadInst(LoadInst &I) {
 295   visitMemoryReference(I, I.getPointerOperand(), I.getAlignment(), I.getType());
 296 }
 297
 298 void Lint::visitStoreInst(StoreInst &I) {
 299   visitMemoryReference(I, I.getPointerOperand(), I.getAlignment(),
 300                   I.getOperand(0)->getType());
 301 }
 302
 303 void Lint::visitLShr(BinaryOperator &I) {
 304   if (ConstantInt *CI =
 305         dyn_cast<ConstantInt>(I.getOperand(1)->stripPointerCasts()))
 306     Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()),
 307             "Shift count out of range", &I);
 308 }
 309
 310 void Lint::visitAShr(BinaryOperator &I) {
 311   if (ConstantInt *CI =
 312         dyn_cast<ConstantInt>(I.getOperand(1)->stripPointerCasts()))
 313     Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()),
 314             "Shift count out of range", &I);
 315 }
 316
 317 void Lint::visitShl(BinaryOperator &I) {
 318   if (ConstantInt *CI =
 319         dyn_cast<ConstantInt>(I.getOperand(1)->stripPointerCasts()))
 320     Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()),
 321             "Shift count out of range", &I);
 322 }
 323
 324 static bool isZero(Value *V, TargetData *TD) {
 325   unsigned BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
 326   APInt Mask = APInt::getAllOnesValue(BitWidth),
 327                KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
 328   ComputeMaskedBits(V, Mask, KnownZero, KnownOne, TD);
 329   return KnownZero.isAllOnesValue();
 330 }
 331
 332 void Lint::visitSDiv(BinaryOperator &I) {
 333   Assert1(!isZero(I.getOperand(1), TD), "Division by zero", &I);
 334 }
 335
 336 void Lint::visitUDiv(BinaryOperator &I) {
 337   Assert1(!isZero(I.getOperand(1), TD), "Division by zero", &I);
 338 }
 339
 340 void Lint::visitSRem(BinaryOperator &I) {
 341   Assert1(!isZero(I.getOperand(1), TD), "Division by zero", &I);
 342 }
 343
 344 void Lint::visitURem(BinaryOperator &I) {
 345   Assert1(!isZero(I.getOperand(1), TD), "Division by zero", &I);
 346 }
 347
 348 void Lint::visitAllocaInst(AllocaInst &I) {
 349   if (isa<ConstantInt>(I.getArraySize()))
 350     // This isn't undefined behavior, it's just an obvious pessimization.
 351     Assert1(&I.getParent()->getParent()->getEntryBlock() == I.getParent(),
 352             "Static alloca outside of entry block", &I);
 353 }
 354
 355 void Lint::visitVAArgInst(VAArgInst &I) {
 356   visitMemoryReference(I, I.getOperand(0), 0, 0);
 357 }
 358
 359 void Lint::visitIndirectBrInst(IndirectBrInst &I) {
 360   visitMemoryReference(I, I.getAddress(), 0, 0);
 361 }
 362
 363 void Lint::visitExtractElementInst(ExtractElementInst &I) {
 364   if (ConstantInt *CI =
 365         dyn_cast<ConstantInt>(I.getIndexOperand()->stripPointerCasts()))
 366     Assert1(CI->getValue().ult(I.getVectorOperandType()->getNumElements()),
 367             "extractelement index out of range", &I);
 368 }
 369
 370 void Lint::visitInsertElementInst(InsertElementInst &I) {
 371   if (ConstantInt *CI =
 372         dyn_cast<ConstantInt>(I.getOperand(2)->stripPointerCasts()))
 373     Assert1(CI->getValue().ult(I.getType()->getNumElements()),
 374             "insertelement index out of range", &I);
 375 }
 376
 377 //===----------------------------------------------------------------------===//
 378 //  Implement the public interfaces to this file...
 379 //===----------------------------------------------------------------------===//
 380
 381 FunctionPass *llvm::createLintPass() {
 382   return new Lint();
 383 }
 384
 385 /// lintFunction - Check a function for errors, printing messages on stderr.
 386 ///
 387 void llvm::lintFunction(const Function &f) {
 388   Function &F = const_cast<Function&>(f);
 389   assert(!F.isDeclaration() && "Cannot lint external functions");
 390
 391   FunctionPassManager FPM(F.getParent());
 392   Lint *V = new Lint();
 393   FPM.add(V);
 394   FPM.run(F);
 395 }
 396
 397 /// lintModule - Check a module for errors, printing messages on stderr.
 398 /// Return true if the module is corrupt.
 399 ///
 400 void llvm::lintModule(const Module &M, std::string *ErrorInfo) {
 401   PassManager PM;
 402   Lint *V = new Lint();
 403   PM.add(V);
 404   PM.run(const_cast<Module&>(M));
 405
 406   if (ErrorInfo)
 407     *ErrorInfo = V->MessagesStr.str();
 408 }