GRConstants.cpp

//===-- GRConstants.cpp - Simple, Path-Sens. Constant Prop. ------*- C++ -*-==//
//   
//                     The LLValM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
//               Constant Propagation via Graph Reachability
//
//  This files defines a simple analysis that performs path-sensitive
//  constant propagation within a function.  An example use of this analysis
//  is to perform simple checks for NULL dereferences.
//
//===----------------------------------------------------------------------===//

#include "clang/Analysis/PathSensitive/GREngine.h"
#include "clang/AST/Expr.h"
#include "clang/AST/ASTContext.h"
#include "clang/Analysis/Analyses/LiveVariables.h"

#include "llvm/Support/Casting.h"
#include "llvm/Support/DataTypes.h"
#include "llvm/ADT/APSInt.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/ImmutableMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Streams.h"

#include <functional>

#ifndef NDEBUG
#include "llvm/Support/GraphWriter.h"
#include <sstream>
#endif

using namespace clang;
using llvm::dyn_cast;
using llvm::cast;
using llvm::APSInt;

//===----------------------------------------------------------------------===//
/// ValueKey - A variant smart pointer that wraps either a ValueDecl* or a
///  Stmt*.  Use cast<> or dyn_cast<> to get actual pointer type
//===----------------------------------------------------------------------===//
namespace {

class SymbolID {
  unsigned Data;
public:
  SymbolID() : Data(~0) {}
  SymbolID(unsigned x) : Data(x) {}
  
  bool isInitialized() const { return Data != (unsigned) ~0; }
  operator unsigned() const { assert (isInitialized()); return Data; }
};

class VISIBILITY_HIDDEN ValueKey {
  uintptr_t Raw;  
  void operator=(const ValueKey& RHS); // Do not implement.
  
public:
  enum  Kind { IsSubExpr=0x0, IsBlkExpr=0x1, IsDecl=0x2, // L-Value Bindings.
               IsSymbol=0x3, // Symbol Bindings.
               Flags=0x3 };
  
  inline Kind getKind() const {
    return (Kind) (Raw & Flags);
  }
  
  inline void* getPtr() const { 
    assert (getKind() != IsSymbol);
    return reinterpret_cast<void*>(Raw & ~Flags);
  }
  
  inline SymbolID getSymbolID() const {
    assert (getKind() == IsSymbol);
    return Raw >> 2;
  }
  
  ValueKey(const ValueDecl* VD)
    : Raw(reinterpret_cast<uintptr_t>(VD) | IsDecl) {
      assert(VD && "ValueDecl cannot be NULL.");
    }

  ValueKey(Stmt* S, bool isBlkExpr = false) 
    : Raw(reinterpret_cast<uintptr_t>(S) | (isBlkExpr ? IsBlkExpr : IsSubExpr)){
      assert(S && "Tracked statement cannot be NULL.");
    }
  
  ValueKey(SymbolID V)
    : Raw((V << 2) | IsSymbol) {}  
  
  bool isSymbol()  const { return getKind() == IsSymbol; }
  bool isSubExpr() const { return getKind() == IsSubExpr; }
  bool isBlkExpr() const { return getKind() == IsBlkExpr; }
  bool isDecl()    const { return getKind() == IsDecl; }
  bool isStmt()    const { return getKind() <= IsBlkExpr; }
  
  inline void Profile(llvm::FoldingSetNodeID& ID) const {
    ID.AddInteger(isSymbol() ? 1 : 0);

    if (isSymbol())
      ID.AddInteger(getSymbolID());
    else    
      ID.AddPointer(getPtr());
  }
  
  inline bool operator==(const ValueKey& X) const {
    return isSymbol() ? getSymbolID() == X.getSymbolID()
                      : getPtr() == X.getPtr();
  }
  
  inline bool operator!=(const ValueKey& X) const {
    return !operator==(X);
  }
  
  inline bool operator<(const ValueKey& X) const { 
    if (isSymbol())
      return X.isSymbol() ? getSymbolID() < X.getSymbolID() : false;
    
    return getPtr() < X.getPtr();
  }
};
} // end anonymous namespace

// Machinery to get cast<> and dyn_cast<> working with ValueKey.
namespace llvm {
  template<> inline bool isa<ValueDecl,ValueKey>(const ValueKey& V) {
    return V.getKind() == ValueKey::IsDecl;
  }
  template<> inline bool isa<Stmt,ValueKey>(const ValueKey& V) {
    return ((unsigned) V.getKind()) < ValueKey::IsDecl;
  }
  template<> struct VISIBILITY_HIDDEN cast_retty_impl<ValueDecl,ValueKey> {
    typedef const ValueDecl* ret_type;
  };
  template<> struct VISIBILITY_HIDDEN cast_retty_impl<Stmt,ValueKey> {
    typedef const Stmt* ret_type;
  };
  template<> struct VISIBILITY_HIDDEN simplify_type<ValueKey> {
    typedef void* SimpleType;
    static inline SimpleType getSimplifiedValue(const ValueKey &V) {
      return V.getPtr();
    }
  };
} // end llvm namespace


//===----------------------------------------------------------------------===//
// SymbolManager.
//===----------------------------------------------------------------------===//

namespace {
class VISIBILITY_HIDDEN SymbolData {
  uintptr_t Data;
public:
  enum Kind { ParmKind = 0x0, Mask = 0x3 };
  
  SymbolData(ParmVarDecl* D)
    : Data(reinterpret_cast<uintptr_t>(D) | ParmKind) {}
  
  inline Kind getKind() const { return (Kind) (Data & Mask); }
  inline void* getPtr() const { return reinterpret_cast<void*>(Data & ~Mask); }  
  inline bool operator==(const SymbolData& R) const { return Data == R.Data; }  
};
}

// Machinery to get cast<> and dyn_cast<> working with SymbolData.
namespace llvm {
  template<> inline bool isa<ParmVarDecl,SymbolData>(const SymbolData& V) {
    return V.getKind() == SymbolData::ParmKind;
  }
  template<> struct VISIBILITY_HIDDEN cast_retty_impl<ParmVarDecl,SymbolData> {
    typedef const ParmVarDecl* ret_type;
  };
  template<> struct VISIBILITY_HIDDEN simplify_type<SymbolData> {
    typedef void* SimpleType;
    static inline SimpleType getSimplifiedValue(const SymbolData &V) {
      return V.getPtr();
    }
  };
} // end llvm namespace

namespace {
class VISIBILITY_HIDDEN SymbolManager {
  std::vector<SymbolData> SymbolToData;
  
  typedef llvm::DenseMap<void*,SymbolID> MapTy;
  MapTy DataToSymbol;
  
public:
  SymbolData getSymbolData(SymbolID id) const {
    assert (id < SymbolToData.size());
    return SymbolToData[id];
  }