path: root/Analysis/RValues.h

//== RValues.h - Abstract RValues for Path-Sens. Value Tracking -*- C++ -*--==//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
//  This files defines RValue, LValue, and NonLValue, classes that represent
//  abstract r-values for use with path-sensitive value tracking.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_ANALYSIS_RVALUE_H
#define LLVM_CLANG_ANALYSIS_RVALUE_H

// FIXME: reduce the number of includes.

#include "clang/Analysis/PathSensitive/GREngine.h"
#include "clang/AST/Expr.h"
#include "clang/AST/Decl.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/ADT/SmallPtrSet.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Streams.h"

#include <functional>

//==------------------------------------------------------------------------==//
//  RValue "management" data structures.
//==------------------------------------------------------------------------==// 

namespace clang {

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 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; }  
};

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

class ValueManager {
  typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<llvm::APSInt> >
          APSIntSetTy;
  
  ASTContext& Ctx;
  APSIntSetTy APSIntSet;
  llvm::BumpPtrAllocator BPAlloc;
  
public:
  ValueManager(ASTContext& ctx) : Ctx(ctx) {}
  ~ValueManager();
  
  ASTContext& getContext() const { return Ctx; }  
  llvm::APSInt& getValue(const llvm::APSInt& X);
  llvm::APSInt& getValue(uint64_t X, unsigned BitWidth, bool isUnsigned);
  llvm::APSInt& getValue(uint64_t X, QualType T,
                   SourceLocation Loc = SourceLocation());
};

//==------------------------------------------------------------------------==//
//  Base RValue types.
//==------------------------------------------------------------------------==// 

class RValue {
public:
  enum BaseKind { LValueKind=0x0,
                  NonLValueKind=0x1,
                  UninitializedKind=0x2,
                  InvalidKind=0x3 };
  
  enum { BaseBits = 2, 
         BaseMask = 0x3 };
  
private:
  void* Data;
  unsigned Kind;
  
protected:
  RValue(const void* d, bool isLValue, unsigned ValKind)
  : Data(const_cast<void*>(d)),
    Kind((isLValue ? LValueKind : NonLValueKind) | (ValKind << BaseBits)) {}
  
  explicit RValue(BaseKind k)
    : Data(0), Kind(k) {}
  
  void* getRawPtr() const {
    return reinterpret_cast<void*>(Data);
  }
  
public:
  ~RValue() {};
  
  RValue Cast(ValueManager& ValMgr, Expr* CastExpr) const;
  
  unsigned getRawKind() const { return Kind; }
  BaseKind getBaseKind() const { return (BaseKind) (Kind & BaseMask); }
  unsigned getSubKind() const { return (Kind & ~BaseMask) >> BaseBits; }
  
  void Profile(llvm::FoldingSetNodeID& ID) const {
    ID.AddInteger((unsigned) getRawKind());
    ID.AddPointer(reinterpret_cast<void*>(Data));
  }
  
  bool operator==(const RValue& RHS) const {
    return getRawKind() == RHS.getRawKind() && Data == RHS.Data;
  }
  
  static RValue GetSymbolValue(SymbolManager& SymMgr, ParmVarDecl *D);
  
  inline bool isValid() const { return getRawKind() != InvalidKind; }
  inline bool isInvalid() const { return getRawKind() == InvalidKind; }
  
  void print(std::ostream& OS) const;
  void print() const { print(*llvm::cerr.stream()); }
  
  // Implement isa<T> support.
  static inline bool classof(const RValue*) { return true; }
};

class InvalidValue : public RValue {
public:
  InvalidValue() : RValue(InvalidKind) {}
  
  static inline bool classof(const RValue* V) {
    return V->getBaseKind() == InvalidKind;
  }  
};

class UninitializedValue : public RValue {
public:
  UninitializedValue() : RValue(UninitializedKind) {}
  
  static inline bool classof(const RValue* V) {
    return V->getBaseKind() == UninitializedKind;
  }  
};

class NonLValue : public RValue {
protected:
  NonLValue(unsigned SubKind, const void* d) : RValue(d, false, SubKind) {}
  
public:
  void print(std::ostream& Out) const;
  
  // Arithmetic operators.
  NonLValue Add(ValueManager& ValMgr, const NonLValue& RHS) const;
  NonLValue Sub(ValueManager& ValMgr, const NonLValue& RHS) const;
  NonLValue Mul(ValueManager& ValMgr, const NonLValue& RHS) const;
  NonLValue Div(ValueManager& ValMgr, const NonLValue& RHS) const;
  NonLValue Rem(ValueManager& ValMgr, const NonLValue& RHS) const;
  NonLValue UnaryMinus(ValueManager& ValMgr, UnaryOperator* U) const;
  
  // Equality operators.
  NonLValue EQ(ValueManager& ValMgr, const NonLValue& RHS) const;
  NonLValue NE(ValueManager& ValMgr, const NonLValue& RHS) const;
  
  // Utility methods to create NonLValues.
  static NonLValue GetValue(ValueManager& ValMgr, uint64_t X, QualType T,
                            SourceLocation Loc = SourceLocation());
  
  static NonLValue GetValue(ValueManager& ValMgr, IntegerLiteral* I);
  
  static inline NonLValue GetIntTruthValue(ValueManager& ValMgr, bool X) {
    return GetValue(ValMgr, X ? 1U : 0U, ValMgr.getContext().IntTy);
  }
  
  // Implement isa<T> support.
  static inline bool classof(const RValue* V) {
    return V->getBaseKind() >= NonLValueKind;
  }
};

class LValue : public RValue {
protected:
  LValue(unsigned SubKind, void* D) : RValue(D, true, SubKind) {}
  
public:
  void print(std::ostream&