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"

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

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

//===----------------------------------------------------------------------===//
/// 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 VISIBILITY_HIDDEN ValueKey {
  uintptr_t Raw;
public:
  enum  Kind { IsSubExp=0x0, IsBlkExpr=0x1, IsDecl=0x2, Flags=0x3 };
  inline void* getPtr() const { return reinterpret_cast<void*>(Raw & ~Flags); }
  inline Kind getKind() const { return (Kind) (Raw & Flags); }
  
  ValueKey(const ValueDecl* VD)
    : Raw(reinterpret_cast<uintptr_t>(VD) | IsDecl) {}

  ValueKey(Stmt* S, bool isBlkExpr = false) 
    : Raw(reinterpret_cast<uintptr_t>(S) | (isBlkExpr ? IsBlkExpr : IsSubExp)){}
  
  bool isSubExpr() const { return getKind() == IsSubExp; }
  bool isDecl() const { return getKind() == IsDecl; }
  
  inline void Profile(llvm::FoldingSetNodeID& ID) const {
    ID.AddPointer(getPtr());
    ID.AddInteger((unsigned) getKind());
  }
  
  inline bool operator==(const ValueKey& X) const {
    return getPtr() == X.getPtr();
  }
  
  inline bool operator!=(const ValueKey& X) const {
    return !operator==(X);
  }
  
  inline bool operator<(const ValueKey& X) const { 
    Kind k = getKind(), Xk = X.getKind();
    
    if (k == IsDecl) {
      if (Xk != IsDecl)
        return false;
    }
    else {
      if (Xk == IsDecl)
        return true;
    }

    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

//===----------------------------------------------------------------------===//
// ValueManager.
//===----------------------------------------------------------------------===//

namespace {
  
typedef llvm::ImmutableSet<llvm::APSInt > APSIntSetTy;
    
class VISIBILITY_HIDDEN ValueManager {
  APSIntSetTy::Factory APSIntSetFactory;
  ASTContext* Ctx;
  
public:
  ValueManager() {}
  ~ValueManager() {}
  
  void setContext(ASTContext* ctx) { Ctx = ctx; }
  ASTContext* getContext() const { return Ctx; }
  
  APSIntSetTy GetEmptyAPSIntSet() {
    return APSIntSetFactory.GetEmptySet();
  }
  
  APSIntSetTy AddToSet(const APSIntSetTy& Set, const llvm::APSInt& Val) {
    return APSIntSetFactory.Add(Set, Val);
  }
};
} // end anonymous namespace

//===----------------------------------------------------------------------===//
// Expression Values.
//===----------------------------------------------------------------------===//
  
namespace {
  
class VISIBILITY_HIDDEN ExprValue {
public:
  enum Kind { // L-Values.
              LValueDeclKind = 0x0,
              // Special "Invalid" value.
              InvalidValueKind = 0x1, 
              // R-Values.
              RValueMayEqualSetKind = 0x2,
              // Note that the Lvalue and RValue "kinds" overlap; 
              // the "InvalidValue" class can be used either as
              // an LValue or RValue.  
              MinLValueKind = 0x0, MaxLValueKind = 0x1,
              MinRValueKind = 0x1, MaxRValueKind = 0x2 };
  
private:
  enum Kind kind;
  void* Data;
    
protected:
  ExprValue(Kind k, void* d) : kind(k), Data(d) {}
  
  void* getRawPtr() const { return Data; }
  
public:
  ~ExprValue() {};

  ExprValue EvalCast(ValueManager& ValMgr, Expr* CastExpr) const;
  
  void Profile(llvm::FoldingSetNodeID& ID) const {
    ID.AddInteger((unsigned) getKind());
    ID.AddPointer(Data);
  }
  
  bool operator==(const ExprValue& RHS) const {
    return kind == RHS.kind && Data == RHS.Data;
  }

  Kind getKind() const { return kind; }  
  bool isValid() const { return getKind() != InvalidValueKind; }
  
  void print(std::ostream& OS) const;
  void print() const { print(*llvm::cerr.stream()); }

  // Implement isa<T> support.
  static inline bool classof(const ExprValue*) { return true; }
};

class VISIBILITY_HIDDEN InvalidValue : public ExprValue {
public: