| // 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, |
| QualType T) { |
| |
| 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::SymExprValKind: { |
| // Logical not? |
| if (!(Op == BinaryOperator::EQ && R.isZeroConstant())) |
| return UnknownVal(); |
| |
| const SymExpr &SE=*cast<nonloc::SymExprVal>(L).getSymbolicExpression(); |
| |
| // Only handle ($sym op constant) for now. |
| if (const SymIntExpr *E = dyn_cast<SymIntExpr>(&SE)) { |
| BinaryOperator::Opcode Opc = E->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]; |
| assert(E->getType(Eng.getContext()) == T); |
| E = Eng.getSymbolManager().getSymIntExpr(E->getLHS(), Opc, |
| E->getRHS(), T); |
| return nonloc::SymExprVal(E); |
| } |
| |
| return UnknownVal(); |
| } |
| |
| 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)) |
| return NonLoc::MakeVal(Eng.getSymbolManager(), |
| cast<nonloc::SymbolVal>(L).getSymbol(), Op, |
| cast<nonloc::ConcreteInt>(R).getValue(), T); |
| 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); |
| } |
| } |
| |
| 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. |
| // FIXME: All this logic will be revamped when we have MemRegion::getLocation() |
| // implemented. |
| |
| SVal GRSimpleVals::EvalEQ(GRExprEngine& Eng, Loc L, Loc R) { |
| |
| BasicValueFactory& BasicVals = Eng.getBasicVals(); |
| |
| 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 SymIntExpr *SE = |
| Eng.getSymbolManager().getSymIntExpr(cast<loc::SymbolVal>(R).getSymbol(), |
| BinaryOperator::EQ, |
| cast<loc::ConcreteInt>(L).getValue(), |
| Eng.getContext().IntTy); |
| |
| return nonloc::SymExprVal(SE); |
| } |
| |
| break; |
| |
| case loc::SymbolValKind: { |
| |
| if (isa<loc::ConcreteInt>(R)) { |
| const SymIntExpr *SE = |
| Eng.getSymbolManager().getSymIntExpr( |
| cast<loc::SymbolVal>(L).getSymbol(), |
| BinaryOperator::EQ, |
| cast<loc::ConcreteInt>(R).getValue(), |
| Eng.getContext().IntTy); |
| |
| return nonloc::SymExprVal(SE); |
| } |
| |
| // 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: { |
| if (SymbolRef LSym = L.getAsLocSymbol()) { |
| if (isa<loc::ConcreteInt>(R)) { |
| const SymIntExpr *SE = |
| Eng.getSymbolManager().getSymIntExpr(LSym, BinaryOperator::EQ, |
| cast<loc::ConcreteInt>(R).getValue(), |
| Eng.getContext().IntTy); |
| |
| return nonloc::SymExprVal(SE); |
| } |
| } |
| } |
| |
| // 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(); |
| |
| 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 (SymbolRef Sym = R.getAsSymbol()) { |
| const SymIntExpr * SE = |
| Eng.getSymbolManager().getSymIntExpr(Sym, BinaryOperator::NE, |
| cast<loc::ConcreteInt>(L).getValue(), |
| Eng.getContext().IntTy); |
| return nonloc::SymExprVal(SE); |
| } |
| |
| break; |
| |
| case loc::SymbolValKind: { |
| if (isa<loc::ConcreteInt>(R)) { |
| const SymIntExpr *SE = |
| Eng.getSymbolManager().getSymIntExpr( |
| cast<loc::SymbolVal>(L).getSymbol(), |
| BinaryOperator::NE, |
| cast<loc::ConcreteInt>(R).getValue(), |
| Eng.getContext().IntTy); |
| return nonloc::SymExprVal(SE); |
| } |
| |
| // 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: { |
| if (SymbolRef LSym = L.getAsLocSymbol()) { |
| if (isa<loc::ConcreteInt>(R)) { |
| const SymIntExpr* SE = |
| Eng.getSymbolManager().getSymIntExpr(LSym, BinaryOperator::NE, |
| cast<loc::ConcreteInt>(R).getValue(), |
| Eng.getContext().IntTy); |
| return nonloc::SymExprVal(SE); |
| } |
| } |
| // Fall through: |
| } |
| |
| 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(); |
| |
| SVal X = SVal::GetConjuredSymbolVal(Eng.getSymbolManager(), |
| Eng.getStoreManager().getRegionManager(), CE, Count); |
| |
| 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); |
| } |