lib/VMCore/Verifier.cpp

   1 //===-- Verifier.cpp - Implement the Module Verifier -------------*- C++ -*-==//
   2 //
   3 // This file defines the function verifier interface, that can be used for some
   4 // sanity checking of input to the system.
   5 //
   6 // Note that this does not provide full 'java style' security and verifications,
   7 // instead it just tries to ensure that code is well formed.
   8 //
   9 //  * Both of a binary operator's parameters are the same type
  10 //  * Verify that the indices of mem access instructions match other operands
  11 //  * Verify that arithmetic and other things are only performed on first class
  12 //    types.  Verify that shifts & logicals only happen on integrals f.e.
  13 //  . All of the constants in a switch statement are of the correct type
  14 //  * The code is in valid SSA form
  15 //  . It should be illegal to put a label into any other type (like a structure)
  16 //    or to return one. [except constant arrays!]
  17 //  * Only phi nodes can be self referential: 'add int %0, %0 ; <int>:0' is bad
  18 //  * PHI nodes must have an entry for each predecessor, with no extras.
  19 //  * PHI nodes must be the first thing in a basic block, all grouped together
  20 //  * All basic blocks should only end with terminator insts, not contain them
  21 //  * The entry node to a function must not have predecessors
  22 //  * All Instructions must be embeded into a basic block
  23 //  . Function's cannot take a void typed parameter
  24 //  * Verify that a function's argument list agrees with it's declared type.
  25 //  . Verify that arrays and structures have fixed elements: No unsized arrays.
  26 //  * It is illegal to specify a name for a void value.
  27 //  * It is illegal to have a internal function that is just a declaration
  28 //  * It is illegal to have a ret instruction that returns a value that does not
  29 //    agree with the function return value type.
  30 //  * Function call argument types match the function prototype
  31 //  * All other things that are tested by asserts spread about the code...
  32 //
  33 //===----------------------------------------------------------------------===//
  34
  35 #include "llvm/Analysis/Verifier.h"
  36 #include "llvm/Pass.h"
  37 #include "llvm/Module.h"
  38 #include "llvm/DerivedTypes.h"
  39 #include "llvm/iPHINode.h"
  40 #include "llvm/iTerminators.h"
  41 #include "llvm/iOther.h"
  42 #include "llvm/iOperators.h"
  43 #include "llvm/iMemory.h"
  44 #include "llvm/SymbolTable.h"
  45 #include "llvm/PassManager.h"
  46 #include "llvm/Analysis/Dominators.h"
  47 #include "llvm/Support/CFG.h"
  48 #include "llvm/Support/InstVisitor.h"
  49 #include "Support/STLExtras.h"
  50 #include <algorithm>
  51 #include <iostream>
  52
  53 namespace {  // Anonymous namespace for class
  54
  55   struct Verifier : public FunctionPass, InstVisitor<Verifier> {
  56     bool Broken;          // Is this module found to be broken?
  57     bool RealPass;        // Are we not being run by a PassManager?
  58     bool AbortBroken;     // If broken, should it or should it not abort?
  59
  60     DominatorSet *DS; // Dominator set, caution can be null!
  61
  62     Verifier() : Broken(false), RealPass(true), AbortBroken(true), DS(0) {}
  63     Verifier(bool AB) : Broken(false), RealPass(true), AbortBroken(AB), DS(0) {}
  64     Verifier(DominatorSet &ds)
  65       : Broken(false), RealPass(false), AbortBroken(false), DS(&ds) {}
  66
  67
  68     bool doInitialization(Module &M) {
  69       verifySymbolTable(M.getSymbolTable());
  70       return false;
  71     }
  72
  73     bool runOnFunction(Function &F) {
  74       // Get dominator information if we are being run by PassManager
  75       if (RealPass) DS = &getAnalysis<DominatorSet>();
  76       visit(F);
  77       return false;
  78     }
  79
  80     bool doFinalization(Module &M) {
  81       // Scan through, checking all of the external function's linkage now...
  82       for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  83         if (I->isExternal() && I->hasInternalLinkage())
  84           CheckFailed("Function Declaration has Internal Linkage!", I);
  85
  86       if (Broken && AbortBroken) {
  87         std::cerr << "Broken module found, compilation aborted!\n";
  88         abort();
  89       }
  90       return false;
  91     }
  92
  93     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  94       AU.setPreservesAll();
  95       if (RealPass)
  96         AU.addRequired<DominatorSet>();
  97     }
  98
  99     // Verification methods...
 100     void verifySymbolTable(SymbolTable *ST);
 101     void visitFunction(Function &F);
 102     void visitBasicBlock(BasicBlock &BB);
 103     void visitPHINode(PHINode &PN);
 104     void visitBinaryOperator(BinaryOperator &B);
 105     void visitShiftInst(ShiftInst &SI);
 106     void visitCallInst(CallInst &CI);
 107     void visitGetElementPtrInst(GetElementPtrInst &GEP);
 108     void visitLoadInst(LoadInst &LI);
 109     void visitStoreInst(StoreInst &SI);
 110     void visitInstruction(Instruction &I);
 111     void visitTerminatorInst(TerminatorInst &I);
 112     void visitReturnInst(ReturnInst &RI);
 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     //
 118     inline void CheckFailed(const std::string &Message,
 119                             const Value *V1 = 0, const Value *V2 = 0,
 120                             const Value *V3 = 0, const Value *V4 = 0) {
 121       std::cerr << Message << "\n";
 122       if (V1) std::cerr << *V1 << "\n";
 123       if (V2) std::cerr << *V2 << "\n";
 124       if (V3) std::cerr << *V3 << "\n";
 125       if (V4) std::cerr << *V4 << "\n";
 126       Broken = true;
 127     }
 128   };
 129
 130   RegisterPass<Verifier> X("verify", "Module Verifier");
 131 }
 132
 133 // Assert - We know that cond should be true, if not print an error message.
 134 #define Assert(C, M) \
 135   do { if (!(C)) { CheckFailed(M); return; } } while (0)
 136 #define Assert1(C, M, V1) \
 137   do { if (!(C)) { CheckFailed(M, V1); return; } } while (0)
 138 #define Assert2(C, M, V1, V2) \
 139   do { if (!(C)) { CheckFailed(M, V1, V2); return; } } while (0)
 140 #define Assert3(C, M, V1, V2, V3) \
 141   do { if (!(C)) { CheckFailed(M, V1, V2, V3); return; } } while (0)
 142 #define Assert4(C, M, V1, V2, V3, V4) \
 143   do { if (!(C)) { CheckFailed(M, V1, V2, V3, V4); return; } } while (0)
 144
 145
 146 // verifySymbolTable - Verify that a function or module symbol table is ok
 147 //
 148 void Verifier::verifySymbolTable(SymbolTable *ST) {
 149   if (ST == 0) return;   // No symbol table to process
 150
 151   // Loop over all of the types in the symbol table...
 152   for (SymbolTable::iterator TI = ST->begin(), TE = ST->end(); TI != TE; ++TI)
 153     for (SymbolTable::type_iterator I = TI->second.begin(),
 154            E = TI->second.end(); I != E; ++I) {
 155       Value *V = I->second;
 156
 157       // Check that there are no void typed values in the symbol table.  Values
 158       // with a void type cannot be put into symbol tables because they cannot
 159       // have names!
 160       Assert1(V->getType() != Type::VoidTy,
 161               "Values with void type are not allowed to have names!", V);
 162     }
 163 }
 164
 165
 166 // visitFunction - Verify that a function is ok.
 167 //
 168 void Verifier::visitFunction(Function &F) {
 169   if (F.isExternal()) return;
 170
 171   verifySymbolTable(F.getSymbolTable());
 172
 173   // Check function arguments...
 174   const FunctionType *FT = F.getFunctionType();
 175   unsigned NumArgs = F.getArgumentList().size();
 176
 177   Assert2(!FT->isVarArg(), "Cannot define varargs functions in LLVM!", &F, FT);
 178   Assert2(FT->getParamTypes().size() == NumArgs,
 179           "# formal arguments must match # of arguments for function type!",
 180           &F, FT);
 181
 182   // Check that the argument values match the function type for this function...
 183   if (FT->getParamTypes().size() == NumArgs) {
 184     unsigned i = 0;
 185     for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I, ++i)
 186       Assert2(I->getType() == FT->getParamType(i),
 187               "Argument value does not match function argument type!",
 188               I, FT->getParamType(i));
 189   }
 190
 191   // Check the entry node
 192   BasicBlock *Entry = &F.getEntryNode();
 193   Assert1(pred_begin(Entry) == pred_end(Entry),
 194           "Entry block to function must not have predecessors!", Entry);
 195 }
 196
 197
 198 // verifyBasicBlock - Verify that a basic block is well formed...
 199 //
 200 void Verifier::visitBasicBlock(BasicBlock &BB) {
 201   // Ensure that basic blocks have terminators!
 202   Assert1(BB.getTerminator(), "Basic Block does not have terminator!", &BB);
 203 }
 204
 205 void Verifier::visitTerminatorInst(TerminatorInst &I) {
 206   // Ensure that terminators only exist at the end of the basic block.
 207   Assert1(&I == I.getParent()->getTerminator(),
 208           "Terminator found in the middle of a basic block!", I.getParent());
 209   visitInstruction(I);
 210 }
 211
 212 void Verifier::visitReturnInst(ReturnInst &RI) {
 213   Function *F = RI.getParent()->getParent();
 214   if (RI.getNumOperands() == 0)
 215     Assert1(F->getReturnType() == Type::VoidTy,
 216             "Function returns no value, but ret instruction found that does!",
 217             &RI);
 218   else
 219     Assert2(F->getReturnType() == RI.getOperand(0)->getType(),
 220             "Function return type does not match operand "
 221             "type of return inst!", &RI, F->getReturnType());
 222
 223   // Check to make sure that the return value has neccesary properties for
 224   // terminators...
 225   visitTerminatorInst(RI);
 226 }
 227
 228
 229 // visitPHINode - Ensure that a PHI node is well formed.
 230 void Verifier::visitPHINode(PHINode &PN) {
 231   // Ensure that the PHI nodes are all grouped together at the top of the block.
 232   // This can be tested by checking whether the instruction before this is
 233   // either nonexistant (because this is begin()) or is a PHI node.  If not,
 234   // then there is some other instruction before a PHI.
 235   Assert2(PN.getPrev() == 0 || isa<PHINode>(PN.getPrev()),
 236           "PHI nodes not grouped at top of basic block!",
 237           &PN, PN.getParent());
 238
 239   std::vector<BasicBlock*> Preds(pred_begin(PN.getParent()),
 240                                  pred_end(PN.getParent()));
 241   // Loop over all of the incoming values, make sure that there are
 242   // predecessors for each one...
 243   //
 244   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
 245     // Make sure all of the incoming values are the right types...
 246     Assert2(PN.getType() == PN.getIncomingValue(i)->getType(),
 247             "PHI node argument type does not agree with PHI node type!",
 248             &PN, PN.getIncomingValue(i));
 249
 250     BasicBlock *BB = PN.getIncomingBlock(i);
 251     std::vector<BasicBlock*>::iterator PI =
 252       find(Preds.begin(), Preds.end(), BB);
 253     Assert2(PI != Preds.end(), "PHI node has entry for basic block that"
 254             " is not a predecessor!", &PN, BB);
 255     Preds.erase(PI);
 256   }
 257
 258   // There should be no entries left in the predecessor list...
 259   for (std::vector<BasicBlock*>::iterator I = Preds.begin(),
 260          E = Preds.end(); I != E; ++I)
 261     Assert2(0, "PHI node does not have entry for a predecessor basic block!",
 262             &PN, *I);
 263
 264   // Now we go through and check to make sure that if there is more than one
 265   // entry for a particular basic block in this PHI node, that the incoming
 266   // values are all identical.
 267   //
 268   std::vector<std::pair<BasicBlock*, Value*> > Values;
 269   Values.reserve(PN.getNumIncomingValues());
 270   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
 271     Values.push_back(std::make_pair(PN.getIncomingBlock(i),
 272                                     PN.getIncomingValue(i)));
 273
 274   // Sort the Values vector so that identical basic block entries are adjacent.
 275   std::sort(Values.begin(), Values.end());
 276
 277   // Check for identical basic blocks with differing incoming values...
 278   for (unsigned i = 1, e = PN.getNumIncomingValues(); i < e; ++i)
 279     Assert4(Values[i].first  != Values[i-1].first ||
 280             Values[i].second == Values[i-1].second,
 281             "PHI node has multiple entries for the same basic block with "
 282             "different incoming values!", &PN, Values[i].first,
 283             Values[i].second, Values[i-1].second);
 284
 285   visitInstruction(PN);
 286 }
 287
 288 void Verifier::visitCallInst(CallInst &CI) {
 289   Assert1(isa<PointerType>(CI.getOperand(0)->getType()),
 290           "Called function must be a pointer!", &CI);
 291   const PointerType *FPTy = cast<PointerType>(CI.getOperand(0)->getType());
 292   Assert1(isa<FunctionType>(FPTy->getElementType()),
 293           "Called function is not pointer to function type!", &CI);
 294
 295   const FunctionType *FTy = cast<FunctionType>(FPTy->getElementType());
 296
 297   // Verify that the correct number of arguments are being passed
 298   if (FTy->isVarArg())
 299     Assert1(CI.getNumOperands()-1 >= FTy->getNumParams(),
 300             "Called function requires more parameters than were provided!",&CI);
 301   else
 302     Assert1(CI.getNumOperands()-1 == FTy->getNumParams(),
 303             "Incorrect number of arguments passed to called function!", &CI);
 304
 305   // Verify that all arguments to the call match the function type...
 306   for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
 307     Assert2(CI.getOperand(i+1)->getType() == FTy->getParamType(i),
 308             "Call parameter type does not match function signature!",
 309             CI.getOperand(i+1), FTy->getParamType(i));
 310
 311   visitInstruction(CI);
 312 }
 313
 314 // visitBinaryOperator - Check that both arguments to the binary operator are
 315 // of the same type!
 316 //
 317 void Verifier::visitBinaryOperator(BinaryOperator &B) {
 318   Assert1(B.getOperand(0)->getType() == B.getOperand(1)->getType(),
 319           "Both operands to a binary operator are not of the same type!", &B);
 320
 321   // Check that logical operators are only used with integral operands.
 322   if (B.getOpcode() == Instruction::And || B.getOpcode() == Instruction::Or ||
 323       B.getOpcode() == Instruction::Xor) {
 324     Assert1(B.getType()->isIntegral(),
 325             "Logical operators only work with integral types!", &B);
 326     Assert1(B.getType() == B.getOperand(0)->getType(),
 327             "Logical operators must have same type for operands and result!",
 328             &B);
 329   } else if (isa<SetCondInst>(B)) {
 330     // Check that setcc instructions return bool
 331     Assert1(B.getType() == Type::BoolTy,
 332             "setcc instructions must return boolean values!", &B);
 333   } else {
 334     // Arithmetic operators only work on integer or fp values
 335     Assert1(B.getType() == B.getOperand(0)->getType(),
 336             "Arithmetic operators must have same type for operands and result!",
 337             &B);
 338     Assert1(B.getType()->isInteger() || B.getType()->isFloatingPoint(),
 339             "Arithmetic oeprators must have integer or fp type!", &B);
 340   }
 341
 342   visitInstruction(B);
 343 }
 344
 345 void Verifier::visitShiftInst(ShiftInst &SI) {
 346   Assert1(SI.getType()->isInteger(),
 347           "Shift must return an integer result!", &SI);
 348   Assert1(SI.getType() == SI.getOperand(0)->getType(),
 349           "Shift return type must be same as first operand!", &SI);
 350   Assert1(SI.getOperand(1)->getType() == Type::UByteTy,
 351           "Second operand to shift must be ubyte type!", &SI);
 352   visitInstruction(SI);
 353 }
 354
 355
 356
 357 void Verifier::visitGetElementPtrInst(GetElementPtrInst &GEP) {
 358   const Type *ElTy =
 359     GetElementPtrInst::getIndexedType(GEP.getOperand(0)->getType(),
 360                    std::vector<Value*>(GEP.idx_begin(), GEP.idx_end()), true);
 361   Assert1(ElTy, "Invalid indices for GEP pointer type!", &GEP);
 362   Assert2(PointerType::get(ElTy) == GEP.getType(),
 363           "GEP is not of right type for indices!", &GEP, ElTy);
 364   visitInstruction(GEP);
 365 }
 366
 367 void Verifier::visitLoadInst(LoadInst &LI) {
 368   const Type *ElTy =
 369     cast<PointerType>(LI.getOperand(0)->getType())->getElementType();
 370   Assert2(ElTy == LI.getType(),
 371           "Load is not of right type for indices!", &LI, ElTy);
 372   visitInstruction(LI);
 373 }
 374
 375 void Verifier::visitStoreInst(StoreInst &SI) {
 376   const Type *ElTy =
 377     cast<PointerType>(SI.getOperand(1)->getType())->getElementType();
 378   Assert2(ElTy == SI.getOperand(0)->getType(),
 379           "Stored value is not of right type for indices!", &SI, ElTy);
 380   visitInstruction(SI);
 381 }
 382
 383
 384 // verifyInstruction - Verify that an instruction is well formed.
 385 //
 386 void Verifier::visitInstruction(Instruction &I) {
 387   BasicBlock *BB = I.getParent();
 388   Assert1(BB, "Instruction not embedded in basic block!", &I);
 389
 390   // Check that all uses of the instruction, if they are instructions
 391   // themselves, actually have parent basic blocks.  If the use is not an
 392   // instruction, it is an error!
 393   //
 394   for (User::use_iterator UI = I.use_begin(), UE = I.use_end();
 395        UI != UE; ++UI) {
 396     Assert1(isa<Instruction>(*UI), "Use of instruction is not an instruction!",
 397             *UI);
 398     Instruction *Used = cast<Instruction>(*UI);
 399     Assert2(Used->getParent() != 0, "Instruction referencing instruction not"
 400             " embeded in a basic block!", &I, Used);
 401   }
 402
 403   if (!isa<PHINode>(I)) {   // Check that non-phi nodes are not self referential
 404     for (Value::use_iterator UI = I.use_begin(), UE = I.use_end();
 405          UI != UE; ++UI)
 406       Assert1(*UI != (User*)&I,
 407               "Only PHI nodes may reference their own value!", &I);
 408   }
 409
 410   // Check that void typed values don't have names
 411   Assert1(I.getType() != Type::VoidTy || !I.hasName(),
 412           "Instruction has a name, but provides a void value!", &I);
 413
 414   // Check that a definition dominates all of its uses.
 415   //
 416   for (User::use_iterator UI = I.use_begin(), UE = I.use_end();
 417        UI != UE; ++UI) {
 418     Instruction *Use = cast<Instruction>(*UI);
 419
 420     // PHI nodes are more difficult than other nodes because they actually
 421     // "use" the value in the predecessor basic blocks they correspond to.
 422     if (PHINode *PN = dyn_cast<PHINode>(Use)) {
 423       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 424         if (&I == PN->getIncomingValue(i)) {
 425           // Make sure that I dominates the end of pred(i)
 426           BasicBlock *Pred = PN->getIncomingBlock(i);
 427
 428           // Use must be dominated by by definition unless use is unreachable!
 429           Assert2(DS->dominates(BB, Pred) ||
 430                   !DS->dominates(&BB->getParent()->getEntryNode(), Pred),
 431                   "Instruction does not dominate all uses!",
 432                   &I, PN);
 433         }
 434
 435     } else {
 436       // Use must be dominated by by definition unless use is unreachable!
 437       Assert2(DS->dominates(&I, Use) ||
 438               !DS->dominates(&BB->getParent()->getEntryNode(),Use->getParent()),
 439               "Instruction does not dominate all uses!", &I, Use);
 440     }
 441   }
 442 }
 443
 444
 445 //===----------------------------------------------------------------------===//
 446 //  Implement the public interfaces to this file...
 447 //===----------------------------------------------------------------------===//
 448
 449 Pass *createVerifierPass() {
 450   return new Verifier();
 451 }
 452
 453
 454 // verifyFunction - Create
 455 bool verifyFunction(const Function &f) {
 456   Function &F = (Function&)f;
 457   assert(!F.isExternal() && "Cannot verify external functions");
 458
 459   DominatorSet DS;
 460   DS.doInitialization(*F.getParent());
 461   DS.runOnFunction(F);
 462
 463   Verifier V(DS);
 464   V.runOnFunction(F);
 465
 466   DS.doFinalization(*F.getParent());
 467
 468   return V.Broken;
 469 }
 470
 471 // verifyModule - Check a module for errors, printing messages on stderr.
 472 // Return true if the module is corrupt.
 473 //
 474 bool verifyModule(const Module &M) {
 475   PassManager PM;
 476   Verifier *V = new Verifier();
 477   PM.add(V);
 478   PM.run((Module&)M);
 479   return V->Broken;
 480 }