blob: b0aa79e0670cc94a4d0e47a6a55de86da2d20988 [file] [log] [blame]
Ted Kremenek8ad19872008-03-07 20:13:31 +00001//=== BasicValueFactory.cpp - Basic values for Path Sens analysis --*- C++ -*-//
Ted Kremenek94e915e2008-02-16 01:12:31 +00002//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
Ted Kremenek8ad19872008-03-07 20:13:31 +000010// This file defines BasicValueFactory, a class that manages the lifetime
11// of APSInt objects and symbolic constraints used by GRExprEngine
12// and related classes.
Ted Kremenek94e915e2008-02-16 01:12:31 +000013//
14//===----------------------------------------------------------------------===//
15
Ted Kremenek8ad19872008-03-07 20:13:31 +000016#include "clang/Analysis/PathSensitive/BasicValueFactory.h"
Ted Kremenekfe1a0b12008-04-22 21:10:18 +000017#include "clang/Analysis/PathSensitive/RValues.h"
Ted Kremenek94e915e2008-02-16 01:12:31 +000018
19using namespace clang;
20
Ted Kremenek465f25a2008-04-29 22:17:41 +000021typedef std::pair<RVal, uintptr_t> RValData;
Ted Kremenekfe1a0b12008-04-22 21:10:18 +000022
23namespace llvm {
Ted Kremenek465f25a2008-04-29 22:17:41 +000024template<> struct FoldingSetTrait<RValData> {
25 static inline void Profile(const RValData& X, llvm::FoldingSetNodeID& ID) {
Ted Kremenekfe1a0b12008-04-22 21:10:18 +000026 X.first.Profile(ID);
Ted Kremenek465f25a2008-04-29 22:17:41 +000027 ID.AddPointer( (void*) X.second);
Ted Kremenekfe1a0b12008-04-22 21:10:18 +000028 }
29};
30}
31
Ted Kremenek465f25a2008-04-29 22:17:41 +000032typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<RValData> >
Ted Kremenekfe1a0b12008-04-22 21:10:18 +000033 PersistentRValsTy;
34
Ted Kremenek8ad19872008-03-07 20:13:31 +000035BasicValueFactory::~BasicValueFactory() {
Ted Kremenek94e915e2008-02-16 01:12:31 +000036 // Note that the dstor for the contents of APSIntSet will never be called,
37 // so we iterate over the set and invoke the dstor for each APSInt. This
38 // frees an aux. memory allocated to represent very large constants.
39 for (APSIntSetTy::iterator I=APSIntSet.begin(), E=APSIntSet.end(); I!=E; ++I)
40 I->getValue().~APSInt();
Ted Kremenekfe1a0b12008-04-22 21:10:18 +000041
42 delete (PersistentRValsTy*) PersistentRVals;
Ted Kremenek94e915e2008-02-16 01:12:31 +000043}
44
Ted Kremenek8ad19872008-03-07 20:13:31 +000045const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) {
Ted Kremenek94e915e2008-02-16 01:12:31 +000046 llvm::FoldingSetNodeID ID;
47 void* InsertPos;
48 typedef llvm::FoldingSetNodeWrapper<llvm::APSInt> FoldNodeTy;
49
50 X.Profile(ID);
51 FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos);
52
53 if (!P) {
54 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
55 new (P) FoldNodeTy(X);
56 APSIntSet.InsertNode(P, InsertPos);
57 }
58
59 return *P;
60}
61
Ted Kremenek8ad19872008-03-07 20:13:31 +000062const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth,
Ted Kremenek94e915e2008-02-16 01:12:31 +000063 bool isUnsigned) {
64 llvm::APSInt V(BitWidth, isUnsigned);
65 V = X;
66 return getValue(V);
67}
68
Ted Kremenek8ad19872008-03-07 20:13:31 +000069const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) {
Ted Kremenek94e915e2008-02-16 01:12:31 +000070
Chris Lattner8cd0e932008-03-05 18:54:05 +000071 unsigned bits = Ctx.getTypeSize(T);
Ted Kremenek94e915e2008-02-16 01:12:31 +000072 llvm::APSInt V(bits, T->isUnsignedIntegerType());
73 V = X;
74 return getValue(V);
75}
76
77const SymIntConstraint&
Ted Kremenek8ad19872008-03-07 20:13:31 +000078BasicValueFactory::getConstraint(SymbolID sym, BinaryOperator::Opcode Op,
Ted Kremenek94e915e2008-02-16 01:12:31 +000079 const llvm::APSInt& V) {
80
81 llvm::FoldingSetNodeID ID;
82 SymIntConstraint::Profile(ID, sym, Op, V);
83 void* InsertPos;
84
85 SymIntConstraint* C = SymIntCSet.FindNodeOrInsertPos(ID, InsertPos);
86
87 if (!C) {
88 C = (SymIntConstraint*) BPAlloc.Allocate<SymIntConstraint>();
89 new (C) SymIntConstraint(sym, Op, V);
90 SymIntCSet.InsertNode(C, InsertPos);
91 }
92
93 return *C;
94}
95
Ted Kremenekc2d07202008-02-28 20:32:03 +000096const llvm::APSInt*
Ted Kremenek8ad19872008-03-07 20:13:31 +000097BasicValueFactory::EvaluateAPSInt(BinaryOperator::Opcode Op,
Ted Kremenek94e915e2008-02-16 01:12:31 +000098 const llvm::APSInt& V1, const llvm::APSInt& V2) {
99
100 switch (Op) {
101 default:
102 assert (false && "Invalid Opcode.");
103
104 case BinaryOperator::Mul:
Ted Kremenekc2d07202008-02-28 20:32:03 +0000105 return &getValue( V1 * V2 );
Ted Kremenek94e915e2008-02-16 01:12:31 +0000106
107 case BinaryOperator::Div:
Ted Kremenekc2d07202008-02-28 20:32:03 +0000108 return &getValue( V1 / V2 );
Ted Kremenek94e915e2008-02-16 01:12:31 +0000109
110 case BinaryOperator::Rem:
Ted Kremenekc2d07202008-02-28 20:32:03 +0000111 return &getValue( V1 % V2 );
Ted Kremenek94e915e2008-02-16 01:12:31 +0000112
113 case BinaryOperator::Add:
Ted Kremenekc2d07202008-02-28 20:32:03 +0000114 return &getValue( V1 + V2 );
Ted Kremenek94e915e2008-02-16 01:12:31 +0000115
116 case BinaryOperator::Sub:
Ted Kremenekc2d07202008-02-28 20:32:03 +0000117 return &getValue( V1 - V2 );
Ted Kremenek94e915e2008-02-16 01:12:31 +0000118
Ted Kremenekc2d07202008-02-28 20:32:03 +0000119 case BinaryOperator::Shl: {
120
121 // FIXME: This logic should probably go higher up, where we can
122 // test these conditions symbolically.
Ted Kremenek94e915e2008-02-16 01:12:31 +0000123
Ted Kremenekc2d07202008-02-28 20:32:03 +0000124 // FIXME: Expand these checks to include all undefined behavior.
125
126 if (V2.isSigned() && V2.isNegative())
127 return NULL;
128
129 uint64_t Amt = V2.getZExtValue();
130
131 if (Amt > V1.getBitWidth())
132 return NULL;
133
134 return &getValue( V1.operator<<( (unsigned) Amt ));
135 }
136
137 case BinaryOperator::Shr: {
138
139 // FIXME: This logic should probably go higher up, where we can
140 // test these conditions symbolically.
141
142 // FIXME: Expand these checks to include all undefined behavior.
143
144 if (V2.isSigned() && V2.isNegative())
145 return NULL;
146
147 uint64_t Amt = V2.getZExtValue();
148
149 if (Amt > V1.getBitWidth())
150 return NULL;
151
152 return &getValue( V1.operator>>( (unsigned) Amt ));
153 }
Ted Kremenek94e915e2008-02-16 01:12:31 +0000154
155 case BinaryOperator::LT:
Ted Kremenekc2d07202008-02-28 20:32:03 +0000156 return &getTruthValue( V1 < V2 );
Ted Kremenek94e915e2008-02-16 01:12:31 +0000157
158 case BinaryOperator::GT:
Ted Kremenekc2d07202008-02-28 20:32:03 +0000159 return &getTruthValue( V1 > V2 );
Ted Kremenek94e915e2008-02-16 01:12:31 +0000160
161 case BinaryOperator::LE:
Ted Kremenekc2d07202008-02-28 20:32:03 +0000162 return &getTruthValue( V1 <= V2 );
Ted Kremenek94e915e2008-02-16 01:12:31 +0000163
164 case BinaryOperator::GE:
Ted Kremenekc2d07202008-02-28 20:32:03 +0000165 return &getTruthValue( V1 >= V2 );
Ted Kremenek94e915e2008-02-16 01:12:31 +0000166
167 case BinaryOperator::EQ:
Ted Kremenekc2d07202008-02-28 20:32:03 +0000168 return &getTruthValue( V1 == V2 );
Ted Kremenek94e915e2008-02-16 01:12:31 +0000169
170 case BinaryOperator::NE:
Ted Kremenekc2d07202008-02-28 20:32:03 +0000171 return &getTruthValue( V1 != V2 );
Ted Kremenek94e915e2008-02-16 01:12:31 +0000172
173 // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
174
175 case BinaryOperator::And:
Ted Kremenekc2d07202008-02-28 20:32:03 +0000176 return &getValue( V1 & V2 );
Ted Kremenek94e915e2008-02-16 01:12:31 +0000177
178 case BinaryOperator::Or:
Ted Kremenekc2d07202008-02-28 20:32:03 +0000179 return &getValue( V1 | V2 );
Ted Kremenek7c79a792008-02-19 20:53:37 +0000180
181 case BinaryOperator::Xor:
Ted Kremenekc2d07202008-02-28 20:32:03 +0000182 return &getValue( V1 ^ V2 );
Ted Kremenek94e915e2008-02-16 01:12:31 +0000183 }
184}
Ted Kremenekfe1a0b12008-04-22 21:10:18 +0000185
186
Ted Kremenek465f25a2008-04-29 22:17:41 +0000187const std::pair<RVal, uintptr_t>&
188BasicValueFactory::getPersistentRValWithData(const RVal& V, uintptr_t Data) {
Ted Kremenekfe1a0b12008-04-22 21:10:18 +0000189
190 // Lazily create the folding set.
191 if (!PersistentRVals) PersistentRVals = new PersistentRValsTy();
192
193 llvm::FoldingSetNodeID ID;
194 void* InsertPos;
195 V.Profile(ID);
Ted Kremenek465f25a2008-04-29 22:17:41 +0000196 ID.AddPointer((void*) Data);
Ted Kremenekfe1a0b12008-04-22 21:10:18 +0000197
198 PersistentRValsTy& Map = *((PersistentRValsTy*) PersistentRVals);
199
Ted Kremenek465f25a2008-04-29 22:17:41 +0000200 typedef llvm::FoldingSetNodeWrapper<RValData> FoldNodeTy;
Ted Kremenekfe1a0b12008-04-22 21:10:18 +0000201 FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
202
203 if (!P) {
204 P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
Ted Kremenek465f25a2008-04-29 22:17:41 +0000205 new (P) FoldNodeTy(std::make_pair(V, Data));
Ted Kremenekfe1a0b12008-04-22 21:10:18 +0000206 Map.InsertNode(P, InsertPos);
207 }
208
Ted Kremenek465f25a2008-04-29 22:17:41 +0000209 return P->getValue();
Ted Kremenekfe1a0b12008-04-22 21:10:18 +0000210}