path: root/lib/VMCore/Verifier.cpp

//===-- Verifier.cpp - Implement the Module Verifier -------------*- C++ -*-==//
// 
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
// 
//===----------------------------------------------------------------------===//
//
// This file defines the function verifier interface, that can be used for some
// sanity checking of input to the system.
//
// Note that this does not provide full 'java style' security and verifications,
// instead it just tries to ensure that code is well formed.
//
//  * Both of a binary operator's parameters are the same type
//  * Verify that the indices of mem access instructions match other operands
//  * Verify that arithmetic and other things are only performed on first class
//    types.  Verify that shifts & logicals only happen on integrals f.e.
//  . All of the constants in a switch statement are of the correct type
//  * The code is in valid SSA form
//  . It should be illegal to put a label into any other type (like a structure)
//    or to return one. [except constant arrays!]
//  * Only phi nodes can be self referential: 'add int %0, %0 ; <int>:0' is bad
//  * PHI nodes must have an entry for each predecessor, with no extras.
//  * PHI nodes must be the first thing in a basic block, all grouped together
//  * PHI nodes must have at least one entry
//  * All basic blocks should only end with terminator insts, not contain them
//  * The entry node to a function must not have predecessors
//  * All Instructions must be embedded into a basic block
//  . Function's cannot take a void typed parameter
//  * Verify that a function's argument list agrees with it's declared type.
//  * It is illegal to specify a name for a void value.
//  * It is illegal to have a internal global value with no initializer
//  * It is illegal to have a ret instruction that returns a value that does not
//    agree with the function return value type.
//  * Function call argument types match the function prototype
//  * All other things that are tested by asserts spread about the code...
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/Verifier.h"
#include "llvm/Pass.h"
#include "llvm/Module.h"
#include "llvm/DerivedTypes.h"
#include "llvm/iPHINode.h"
#include "llvm/iTerminators.h"
#include "llvm/iOther.h"
#include "llvm/iOperators.h"
#include "llvm/iMemory.h"
#include "llvm/SymbolTable.h"
#include "llvm/PassManager.h"
#include "llvm/Intrinsics.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/InstVisitor.h"
#include "Support/STLExtras.h"
#include <algorithm>

namespace {  // Anonymous namespace for class

  struct Verifier : public FunctionPass, InstVisitor<Verifier> {
    bool Broken;          // Is this module found to be broken?
    bool RealPass;        // Are we not being run by a PassManager?
    bool AbortBroken;     // If broken, should it or should it not abort?
    
    DominatorSet *DS; // Dominator set, caution can be null!

    Verifier() : Broken(false), RealPass(true), AbortBroken(true), DS(0) {}
    Verifier(bool AB) : Broken(false), RealPass(true), AbortBroken(AB), DS(0) {}
    Verifier(DominatorSet &ds) 
      : Broken(false), RealPass(false), AbortBroken(false), DS(&ds) {}


    bool doInitialization(Module &M) {
      verifySymbolTable(M.getSymbolTable());

      // If this is a real pass, in a pass manager, we must abort before
      // returning back to the pass manager, or else the pass manager may try to
      // run other passes on the broken module.
      //
      if (RealPass)
        abortIfBroken();
      return false;
    }

    bool runOnFunction(Function &F) {
      // Get dominator information if we are being run by PassManager
      if (RealPass) DS = &getAnalysis<DominatorSet>();
      visit(F);

      // If this is a real pass, in a pass manager, we must abort before
      // returning back to the pass manager, or else the pass manager may try to
      // run other passes on the broken module.
      //
      if (RealPass)
        abortIfBroken();

      return false;
    }

    bool doFinalization(Module &M) {
      // Scan through, checking all of the external function's linkage now...
      for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
        visitGlobalValue(*I);

      for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; ++I)
        if (I->isExternal() && I->hasInternalLinkage())
          CheckFailed("Global Variable is external with internal linkage!", I);

      // If the module is broken, abort at this time.
      abortIfBroken();
      return false;
    }

    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.setPreservesAll();
      if (RealPass)
        AU.addRequired<DominatorSet>();
    }

    // abortIfBroken - If the module is broken and we are supposed to abort on
    // this condition, do so.
    //
    void abortIfBroken() const {
      if (Broken && AbortBroken) {
        std::cerr << "Broken module found, compilation aborted!\n";
        abort();
      }
    }


    // Verification methods...
    void verifySymbolTable(SymbolTable &ST);
    void visitGlobalValue(GlobalValue &GV);
    void visitFunction(Function &F);
    void visitBasicBlock(BasicBlock &BB);
    void visitPHINode(PHINode &PN);
    void visitBinaryOperator(BinaryOperator &B);
    void visitShiftInst(ShiftInst &SI);
    void visitVANextInst(VANextInst &VAN) { visitInstruction(VAN); }
    void visitVAArgInst(VAArgInst &VAA) { visitInstruction(VAA); }
    void visitCallInst(CallInst &CI);
    void visitGetElementPtrInst(GetElementPtrInst &GEP);
    void visitLoadInst(LoadInst &LI);
    void visitStoreInst(StoreInst &SI);
    void visitInstruction(Instruction &I);
    void visitTerminatorInst(TerminatorInst &I);
    void visitReturnInst(ReturnInst &RI);
    void visitUserOp1(Instruction &I);
    void visitUserOp2(Instruction &I) { visitUserOp1(I); }
    void visitIntrinsicFunctionCall(LLVMIntrinsic::ID ID, CallInst &CI);

    // CheckFailed - A check failed, so print out the condition and the message
    // that failed.  This provides a nice place to put a breakpoint if you want
    // to see why something is not correct.
    //
    inline void CheckFailed(const std::string &Message,
                            const Value *V1 = 0, const Value *V2 = 0,
                            const Value *V3 = 0, const Value *V4 = 0) {
      std::cerr << Message << "\n";
      if (V1) std::cerr << *V1 << "\n";
      if (V2) std::cerr << *V2 << "\n";
      if (V3) std::cerr << *V3 << "\n";
      if (V4) std::cerr << *V4 << "\n";
      Broken = true;
    }
  };

  RegisterPass<Verifier> X("verify", "Module Verifier");
}

// Assert - We know that cond should be true, if not print an error message.
#define Assert(C, M) \
  do { if (!(C)) { CheckFailed(M); return; } } while (0)
#define Assert1(C, M, V1) \
  do { if (!(C)) { CheckFailed(M, V1); return; } } while (0)
#define Assert2(C, M, V1, V2) \
  do { if (!(C)) { CheckFailed(M, V1, V2); return; } } while (0)
#define Assert3(C, M, V1, V2, V3) \
  do { if (!(C)) { CheckFailed(M, V1, V2, V3); return; } } while (0)
#define Assert4(C, M, V1, V2, V3, V4) \
  do { if (!(C)) { CheckFailed(M, V1, V2, V3, V4); return; } } while (0)


void Verifier::visitGlobalValue(GlobalValue &GV) {
  Assert1(!GV.isExternal() || GV.hasExternalLinkage(),
          "Global value has Internal Linkage!", &GV);
  Assert1(!GV.hasAppendingLinkage() || isa<GlobalVariable>(GV),
          "Only global variables can have appending linkage!", &GV);

  if (GV.hasAppendingLinkage()) {
    GlobalVariable &GVar = cast<GlobalVariable>(GV);
    Assert1(isa<ArrayType>(GVar.getType()->getElementType()),
            "Only global arrays can have appending linkage!", &GV);
  }
}

// verifySymbolTable - Verify that a function or module symbol table is ok
//
void Verifier::verifySymbolTable(SymbolTable &ST) {
  // Loop over all of the types in the symbol table...
  for (SymbolTable::iterator TI = ST.begin(), TE = ST.end(); TI != TE; ++TI)
    for (SymbolTable::type_iterator I = TI->second.begin(),
           E = TI->second.end(); I