blob: e2dde76e2000f6a39313a6c68211bb34392978b0 [file] [log] [blame]
// GRSimpleVals.cpp - Transfer functions for tracking simple values -*- C++ -*--
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines GRSimpleVals, a sub-class of GRTransferFuncs that
// provides transfer functions for performing simple value tracking with
// limited support for symbolics.
//
//===----------------------------------------------------------------------===//
#include "GRSimpleVals.h"
#include "BasicObjCFoundationChecks.h"
#include "clang/Basic/SourceManager.h"
#include "clang/Analysis/PathDiagnostic.h"
#include "clang/Analysis/PathSensitive/GRState.h"
#include "clang/Analysis/PathSensitive/BugReporter.h"
#include "clang/Analysis/LocalCheckers.h"
#include "clang/Analysis/PathSensitive/GRExprEngine.h"
#include "llvm/Support/Compiler.h"
#include <sstream>
using namespace clang;
//===----------------------------------------------------------------------===//
// Transfer Function creation for External clients.
//===----------------------------------------------------------------------===//
GRTransferFuncs* clang::MakeGRSimpleValsTF() { return new GRSimpleVals(); }
//===----------------------------------------------------------------------===//
// Transfer function for Casts.
//===----------------------------------------------------------------------===//
SVal GRSimpleVals::EvalCast(GRExprEngine& Eng, NonLoc X, QualType T) {
if (!isa<nonloc::ConcreteInt>(X))
return UnknownVal();
bool isLocType = Loc::IsLocType(T);
// Only handle casts from integers to integers.
if (!isLocType && !T->isIntegerType())
return UnknownVal();
BasicValueFactory& BasicVals = Eng.getBasicVals();
llvm::APSInt V = cast<nonloc::ConcreteInt>(X).getValue();
V.setIsUnsigned(T->isUnsignedIntegerType() || Loc::IsLocType(T));
V.extOrTrunc(Eng.getContext().getTypeSize(T));
if (isLocType)
return loc::ConcreteInt(BasicVals.getValue(V));
else
return nonloc::ConcreteInt(BasicVals.getValue(V));
}
// Casts.
SVal GRSimpleVals::EvalCast(GRExprEngine& Eng, Loc X, QualType T) {
// Casts from pointers -> pointers, just return the lval.
//
// Casts from pointers -> references, just return the lval. These
// can be introduced by the frontend for corner cases, e.g
// casting from va_list* to __builtin_va_list&.
//
assert (!X.isUnknownOrUndef());
if (Loc::IsLocType(T) || T->isReferenceType())
return X;
// FIXME: Handle transparent unions where a value can be "transparently"
// lifted into a union type.
if (T->isUnionType())
return UnknownVal();
assert (T->isIntegerType());
BasicValueFactory& BasicVals = Eng.getBasicVals();
unsigned BitWidth = Eng.getContext().getTypeSize(T);
if (!isa<loc::ConcreteInt>(X))
return nonloc::LocAsInteger::Make(BasicVals, X, BitWidth);
llvm::APSInt V = cast<loc::ConcreteInt>(X).getValue();
V.setIsUnsigned(T->isUnsignedIntegerType() || Loc::IsLocType(T));
V.extOrTrunc(BitWidth);
return nonloc::ConcreteInt(BasicVals.getValue(V));
}
// Unary operators.
SVal GRSimpleVals::EvalMinus(GRExprEngine& Eng, UnaryOperator* U, NonLoc X){
switch (X.getSubKind()) {
case nonloc::ConcreteIntKind:
return cast<nonloc::ConcreteInt>(X).EvalMinus(Eng.getBasicVals(), U);
default:
return UnknownVal();
}
}
SVal GRSimpleVals::EvalComplement(GRExprEngine& Eng, NonLoc X) {
switch (X.getSubKind()) {
case nonloc::ConcreteIntKind:
return cast<nonloc::ConcreteInt>(X).EvalComplement(Eng.getBasicVals());
default:
return UnknownVal();
}
}
// Binary operators.
static unsigned char LNotOpMap[] = {
(unsigned char) BinaryOperator::GE, /* LT => GE */
(unsigned char) BinaryOperator::LE, /* GT => LE */
(unsigned char) BinaryOperator::GT, /* LE => GT */
(unsigned char) BinaryOperator::LT, /* GE => LT */
(unsigned char) BinaryOperator::NE, /* EQ => NE */
(unsigned char) BinaryOperator::EQ /* NE => EQ */
};
SVal GRSimpleVals::DetermEvalBinOpNN(GRExprEngine& Eng,
BinaryOperator::Opcode Op,
NonLoc L, NonLoc R) {
BasicValueFactory& BasicVals = Eng.getBasicVals();
unsigned subkind = L.getSubKind();
while (1) {
switch (subkind) {
default:
return UnknownVal();
case nonloc::LocAsIntegerKind: {
Loc LL = cast<nonloc::LocAsInteger>(L).getLoc();
switch (R.getSubKind()) {
case nonloc::LocAsIntegerKind:
return EvalBinOp(Eng, Op, LL,
cast<nonloc::LocAsInteger>(R).getLoc());
case nonloc::ConcreteIntKind: {
// Transform the integer into a location and compare.
ASTContext& Ctx = Eng.getContext();
llvm::APSInt V = cast<nonloc::ConcreteInt>(R).getValue();
V.setIsUnsigned(true);
V.extOrTrunc(Ctx.getTypeSize(Ctx.VoidPtrTy));
return EvalBinOp(Eng, Op, LL,
loc::ConcreteInt(BasicVals.getValue(V)));
}
default:
switch (Op) {
case BinaryOperator::EQ:
return NonLoc::MakeIntTruthVal(BasicVals, false);
case BinaryOperator::NE:
return NonLoc::MakeIntTruthVal(BasicVals, true);
default:
// This case also handles pointer arithmetic.
return UnknownVal();
}
}
}
case nonloc::SymIntConstraintValKind: {
// Logical not?
if (!(Op == BinaryOperator::EQ && R.isZeroConstant()))
return UnknownVal();
const SymIntConstraint& C =
cast<nonloc::SymIntConstraintVal>(L).getConstraint();
BinaryOperator::Opcode Opc = C.getOpcode();
if (Opc < BinaryOperator::LT || Opc > BinaryOperator::NE)
return UnknownVal();
// For comparison operators, translate the constraint by
// changing the opcode.
int idx = (unsigned) Opc - (unsigned) BinaryOperator::LT;
assert (idx >= 0 &&
(unsigned) idx < sizeof(LNotOpMap)/sizeof(unsigned char));
Opc = (BinaryOperator::Opcode) LNotOpMap[idx];
const SymIntConstraint& CNew =
BasicVals.getConstraint(C.getSymbol(), Opc, C.getInt());
return nonloc::SymIntConstraintVal(CNew);
}
case nonloc::ConcreteIntKind:
if (isa<nonloc::ConcreteInt>(R)) {
const nonloc::ConcreteInt& L_CI = cast<nonloc::ConcreteInt>(L);
const nonloc::ConcreteInt& R_CI = cast<nonloc::ConcreteInt>(R);
return L_CI.EvalBinOp(BasicVals, Op, R_CI);
}
else {
subkind = R.getSubKind();
NonLoc tmp = R;
R = L;
L = tmp;
// Swap the operators.
switch (Op) {
case BinaryOperator::LT: Op = BinaryOperator::GT; break;
case BinaryOperator::GT: Op = BinaryOperator::LT; break;
case BinaryOperator::LE: Op = BinaryOperator::GE; break;
case BinaryOperator::GE: Op = BinaryOperator::LE; break;
default: break;
}
continue;
}
case nonloc::SymbolValKind:
if (isa<nonloc::ConcreteInt>(R)) {
const SymIntConstraint& C =
BasicVals.getConstraint(cast<nonloc::SymbolVal>(L).getSymbol(), Op,
cast<nonloc::ConcreteInt>(R).getValue());
return nonloc::SymIntConstraintVal(C);
}
else
return UnknownVal();
}
}
}
// Binary Operators (except assignments and comma).
SVal GRSimpleVals::EvalBinOp(GRExprEngine& Eng, BinaryOperator::Opcode Op,
Loc L, Loc R) {
switch (Op) {
default:
return UnknownVal();
case BinaryOperator::EQ:
return EvalEQ(Eng, L, R);
case BinaryOperator::NE:
return EvalNE(Eng, L, R);
}
}
// Pointer arithmetic.
static Loc StripViews(Loc X) {
if (isa<loc::MemRegionVal>(X)) {
const SymbolicRegion *Region =
cast<loc::MemRegionVal>(X).getRegion()->getAs<SymbolicRegion>();
if (Region)
return Loc::MakeVal(Region->getSymbol());
}
return X;
}
SVal GRSimpleVals::EvalBinOp(GRExprEngine& Eng, BinaryOperator::Opcode Op,
Loc L, NonLoc R) {
// Delegate pointer arithmetic to store manager.
return Eng.getStoreManager().EvalBinOp(Op, L, R);
}
// Equality operators for Locs.
SVal GRSimpleVals::EvalEQ(GRExprEngine& Eng, Loc L, Loc R) {
BasicValueFactory& BasicVals = Eng.getBasicVals();
TryAgain:
switch (L.getSubKind()) {
default:
assert(false && "EQ not implemented for this Loc.");
return UnknownVal();
case loc::ConcreteIntKind:
if (isa<loc::ConcreteInt>(R)) {
bool b = cast<loc::ConcreteInt>(L).getValue() ==
cast<loc::ConcreteInt>(R).getValue();
return NonLoc::MakeIntTruthVal(BasicVals, b);
}
else if (isa<loc::SymbolVal>(R)) {
const SymIntConstraint& C =
BasicVals.getConstraint(cast<loc::SymbolVal>(R).getSymbol(),
BinaryOperator::EQ,
cast<loc::ConcreteInt>(L).getValue());
return nonloc::SymIntConstraintVal(C);
}
break;
case loc::SymbolValKind: {
if (isa<loc::ConcreteInt>(R)) {
const SymIntConstraint& C =
BasicVals.getConstraint(cast<loc::SymbolVal>(L).getSymbol(),
BinaryOperator::EQ,
cast<loc::ConcreteInt>(R).getValue());
return nonloc::SymIntConstraintVal(C);
}
// FIXME: Implement == for lval Symbols. This is mainly useful
// in iterator loops when traversing a buffer, e.g. while(z != zTerm).
// Since this is not useful for many checkers we'll punt on this for
// now.
return UnknownVal();
}
case loc::MemRegionKind: {
// See if 'L' and 'R' both wrap symbols.
Loc LTmp = StripViews(L);
Loc RTmp = StripViews(R);
if (LTmp != L || RTmp != R) {
L = LTmp;
R = RTmp;
goto TryAgain;
}
}
// Fall-through.
case loc::FuncValKind:
case loc::GotoLabelKind:
return NonLoc::MakeIntTruthVal(BasicVals, L == R);
}
return NonLoc::MakeIntTruthVal(BasicVals, false);
}
SVal GRSimpleVals::EvalNE(GRExprEngine& Eng, Loc L, Loc R) {
BasicValueFactory& BasicVals = Eng.getBasicVals();
TryAgain:
switch (L.getSubKind()) {
default:
assert(false && "NE not implemented for this Loc.");
return UnknownVal();
case loc::ConcreteIntKind:
if (isa<loc::ConcreteInt>(R)) {
bool b = cast<loc::ConcreteInt>(L).getValue() !=
cast<loc::ConcreteInt>(R).getValue();
return NonLoc::MakeIntTruthVal(BasicVals, b);
}
else if (isa<loc::SymbolVal>(R)) {
const SymIntConstraint& C =
BasicVals.getConstraint(cast<loc::SymbolVal>(R).getSymbol(),
BinaryOperator::NE,
cast<loc::ConcreteInt>(L).getValue());
return nonloc::SymIntConstraintVal(C);
}
break;
case loc::SymbolValKind: {
if (isa<loc::ConcreteInt>(R)) {
const SymIntConstraint& C =
BasicVals.getConstraint(cast<loc::SymbolVal>(L).getSymbol(),
BinaryOperator::NE,
cast<loc::ConcreteInt>(R).getValue());
return nonloc::SymIntConstraintVal(C);
}
// FIXME: Implement != for lval Symbols. This is mainly useful
// in iterator loops when traversing a buffer, e.g. while(z != zTerm).
// Since this is not useful for many checkers we'll punt on this for
// now.
return UnknownVal();
break;
}
case loc::MemRegionKind: {
// See if 'L' and 'R' both wrap symbols.
Loc LTmp = StripViews(L);
Loc RTmp = StripViews(R);
if (LTmp != L || RTmp != R) {
L = LTmp;
R = RTmp;
goto TryAgain;
}
}
case loc::FuncValKind:
case loc::GotoLabelKind:
return NonLoc::MakeIntTruthVal(BasicVals, L != R);
}
return NonLoc::MakeIntTruthVal(BasicVals, true);
}
//===----------------------------------------------------------------------===//
// Transfer function for function calls.
//===----------------------------------------------------------------------===//
void GRSimpleVals::EvalCall(ExplodedNodeSet<GRState>& Dst,
GRExprEngine& Eng,
GRStmtNodeBuilder<GRState>& Builder,
CallExpr* CE, SVal L,
ExplodedNode<GRState>* Pred) {
GRStateManager& StateMgr = Eng.getStateManager();
const GRState* St = Builder.GetState(Pred);
// Invalidate all arguments passed in by reference (Locs).
for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end();
I != E; ++I) {
SVal V = StateMgr.GetSVal(St, *I);
if (isa<loc::MemRegionVal>(V))
St = StateMgr.BindLoc(St, cast<Loc>(V), UnknownVal());
else if (isa<nonloc::LocAsInteger>(V))
St = StateMgr.BindLoc(St, cast<nonloc::LocAsInteger>(V).getLoc(),
UnknownVal());
}
// Make up a symbol for the return value of this function.
// FIXME: We eventually should handle structs and other compound types
// that are returned by value.
QualType T = CE->getType();
if (Loc::IsLocType(T) || (T->isIntegerType() && T->isScalarType())) {
unsigned Count = Builder.getCurrentBlockCount();
SymbolRef Sym = Eng.getSymbolManager().getConjuredSymbol(CE, Count);
SVal X = Loc::IsLocType(CE->getType())
? cast<SVal>(loc::SymbolVal(Sym))
: cast<SVal>(nonloc::SymbolVal(Sym));
St = StateMgr.BindExpr(St, CE, X, Eng.getCFG().isBlkExpr(CE), false);
}
Builder.MakeNode(Dst, CE, Pred, St);
}
//===----------------------------------------------------------------------===//
// Transfer function for Objective-C message expressions.
//===----------------------------------------------------------------------===//
void GRSimpleVals::EvalObjCMessageExpr(ExplodedNodeSet<GRState>& Dst,
GRExprEngine& Eng,
GRStmtNodeBuilder<GRState>& Builder,
ObjCMessageExpr* ME,
ExplodedNode<GRState>* Pred) {
// The basic transfer function logic for message expressions does nothing.
// We just invalidate all arguments passed in by references.
GRStateManager& StateMgr = Eng.getStateManager();
const GRState* St = Builder.GetState(Pred);
for (ObjCMessageExpr::arg_iterator I = ME->arg_begin(), E = ME->arg_end();
I != E; ++I) {
SVal V = StateMgr.GetSVal(St, *I);
if (isa<Loc>(V))
St = StateMgr.BindLoc(St, cast<Loc>(V), UnknownVal());
}
Builder.MakeNode(Dst, ME, Pred, St);
}