summaryrefslogtreecommitdiff
path: root/clang/lib/Analysis/Interval.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'clang/lib/Analysis/Interval.cpp')
-rw-r--r--clang/lib/Analysis/Interval.cpp742
1 files changed, 742 insertions, 0 deletions
diff --git a/clang/lib/Analysis/Interval.cpp b/clang/lib/Analysis/Interval.cpp
new file mode 100644
index 0000000..ac96107
--- /dev/null
+++ b/clang/lib/Analysis/Interval.cpp
@@ -0,0 +1,742 @@
+#include "clang/Analysis/Analyses/Interval.h"
+#include "clang/AST/Stmt.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/Analysis/AnalysisContext.h"
+#include "clang/AST/StmtVisitor.h"
+
+#include "clang/Analysis/Analyses/IntervalSolver/Log.hpp"
+#include "clang/Analysis/Analyses/IntervalSolver/Complete.hpp"
+#include "clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp"
+#include "clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp"
+
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Support/Process.h"
+
+#include <deque>
+#include <algorithm>
+#include <vector>
+#include <map>
+#include <set>
+
+using namespace clang;
+
+std::string negate_string(const std::string& str) {
+ if (str[0] == '-')
+ return str.substr(1);
+ return '-' + str;
+}
+
+#include <sstream>
+template<typename T>
+std::string toString(const T& obj) {
+ std::stringstream stream;
+ stream << obj;
+ return stream.str();
+}
+
+#include <ostream>
+template<typename K,typename V>
+std::ostream& operator<<(std::ostream& cout, const std::pair<K,V>& v) {
+ cout << "(" << v.first << ", " << v.second << ")";
+ return cout;
+}
+
+template<typename V>
+std::ostream& operator<<(std::ostream& cout, const std::vector<V>& v) {
+ cout << "[";
+ for(typename std::vector<V>::const_iterator it = v.begin(), ei = v.end();
+ it != ei;
+ ++it) {
+ if (it != v.begin())
+ cout << ", ";
+ cout << *it;
+ }
+ cout << "]";
+ return cout;
+}
+
+template<typename K,typename V>
+std::ostream& operator<<(std::ostream& cout, const std::map<K,V>& v) {
+ cout << "{";
+ for (typename std::map<K,V>::const_iterator it = v.begin(), ei = v.end();
+ it != ei;
+ ++it) {
+ if (it != v.begin())
+ cout << ", ";
+ cout << it->first << ": " << it->second;
+ }
+ cout << "}";
+ return cout;
+}
+
+// Two pieces of state:
+// -> condition protecting a node
+// -> node's expression itself
+// We can then combine these in a straightforward way to
+// get out equation system, whereupon we can solve for what
+// we want to know. Then we can have program invariants!
+//
+// Hooray!
+
+typedef Complete<int64_t> ZBar;
+template<>
+ZBar infinity() {
+ return ZBar(1, true);
+}
+//typedef std::map<std::string, ZBar> Vector;
+
+struct Vector : public std::map<std::string, ZBar> {
+ Vector(const ZBar& val=0)
+ : _val(val) { }
+ ZBar operator[](const std::string& key) const {
+ if (this->find(key) != this->end())
+ return this->find(key)->second;
+ return _val;
+ }
+ ZBar& operator[](const std::string& key) {
+ if (this->find(key) != this->end())
+ return this->find(key)->second;
+ std::pair<iterator,bool> p = this->insert(std::pair<const std::string, ZBar>(key, _val));
+ return p.first->second;
+ }
+ ZBar _val;
+};
+
+Vector negate_vector(const Vector& v) {
+ Vector result;
+ for (Vector::const_iterator it = v.begin(),
+ ei = v.end();
+ it != ei;
+ ++it) {
+ result[negate_string(it->first)] = it->second;
+ }
+ return result;
+}
+
+typedef std::pair<Vector, ZBar> Result; // a "slice" of an equation
+
+Result negate_result(const Result& r) {
+ return Result(negate_vector(r.first), -r.second);
+}
+
+//typedef std::map<std::string, Result> LinearEquation; // one `Result` per variable
+struct LinearEquation : public std::map<std::string, Result> {
+ Result operator[](const std::string& key) const {
+ if (this->find(key) != this->end())
+ return this->find(key)->second;
+ Result r;
+ r.first[key] = 1;
+ r.second = 0;
+ return r;
+ }
+ Result& operator[](const std::string& key) {
+ if (this->find(key) != this->end())
+ return this->find(key)->second;
+ Result r;
+ r.first[key] = 1;
+ r.second = 0;
+ std::pair<iterator,bool> p = this->insert(std::pair<const std::string, Result>(key, r));
+ return p.first->second;
+ }
+};
+
+typedef Vector Condition;
+
+typedef EquationSystem<ZBar> EqnSys;
+typedef Expression<ZBar> EqnExpr;
+typedef Variable<ZBar> EqnVar;
+
+
+struct LinearOperator : public Operator<Vector> {
+ LinearOperator(const LinearEquation* result)
+ : _values(result) {}
+
+ Vector eval(const std::vector<Vector>& vector) const {
+ assert(vector.size() == 1);
+ const Vector& v = vector[0];
+ Vector result = v;
+ for (LinearEquation::const_iterator it = _values->begin(),
+ ei = _values->end();
+ it != ei;
+ ++it) {
+ ZBar subresult = 0;
+ for (Vector::const_iterator jt = it->second.first.begin(),
+ ej = it->second.first.end();
+ jt != ej;
+ ++jt) {
+ subresult += jt->second * v[jt->first];
+ }
+ subresult += it->second.second;
+ result[it->first] = subresult;
+ }
+ return result;
+ }
+
+ void print(std::ostream& cout) const {
+ cout << "linear[" << *_values << "]";
+ }
+
+ const LinearEquation* _values;
+};
+
+
+
+template<class F, class M>
+void transform_values(const F& f, M& map) {
+ for (typename M::iterator it = map.begin(),
+ ei = map.end();
+ it != ei;
+ ++it) {
+ it->second = f(it->second);
+ }
+}
+
+template<class M, class F>
+M merge_maps_with(const F& f, const M& left, const M& right) {
+ M result;
+ typename M::const_iterator first1 = left.begin(), last1 = left.end(),
+ first2 = right.begin(), last2 = right.end();
+ for (; first1 != last1 && first2 != last2;) {
+ if (first2->first < first1->first) {
+ result[first2->first] = first2->second;
+ ++first2;
+ } else if (first1->first == first2->first) {
+ result[first1->first] = f(first1->second, first2->second);
+ ++first1;
+ ++first2;
+ } else {
+ result[first1->first] = first1->second;
+ ++first1;
+ }
+ }
+ while (first1 != last1) {
+ result[first1->first] = first1->second;
+ ++first1;
+ }
+ while (first2 != last2) {
+ result[first2->first] = first2->second;
+ ++first2;
+ }
+ return result;
+}
+
+template<>
+Vector minimum(const Vector& l, const Vector& r) {
+ return (l < r ? l : r);
+ return merge_maps_with(minimum<ZBar>, l, r);
+}
+template<class T>
+T max(const T& l, const T& r) {
+ return (l < r ? l : r);
+}
+template<class T>
+T negate(const T& v) {
+ return -v;
+}
+template<class T>
+T addValues(const T& l, const T& r) {
+ return l + r;
+}
+
+Vector operator-(const Vector& vector) {
+ Vector result(-vector._val);
+ for (Vector::const_iterator it = vector.begin(),
+ ei = vector.end();
+ it != ei;
+ ++it) {
+ result[it->first] = -it->second;
+ }
+ return result;
+}
+
+Vector operator+(const Vector& left, const Vector& right) {
+ return merge_maps_with(addValues<ZBar>, left, right);
+}
+
+Vector operator-(const Vector& left, const Vector& right) {
+ return merge_maps_with(addValues<ZBar>, left, -right);
+}
+
+Vector operator*(const Vector& left, const ZBar& right) {
+ Vector result;
+ for (Vector::const_iterator it = left.begin(),
+ ei = left.end();
+ it != ei;
+ ++it) {
+ result[it->first] = (it->second * right);
+ }
+ return result;
+}
+Vector operator*(const ZBar& left, const Vector& right) {
+ return right * left;
+}
+bool operator<(const Vector& left, const Vector& right) {
+ bool equal = true;
+ for (Vector::const_iterator it = left.begin(),
+ ei = left.end();
+ it != ei;
+ ++it) {
+ if (it->second < right[it->first]) {
+ equal = false;
+ } else if (it->second > right[it->first]) {
+ return false;
+ }
+ }
+ for (Vector::const_iterator it = right.begin(),
+ ei = right.end();
+ it != ei;
+ ++it) {
+ if (left[it->first] < it->second) {
+ equal = false;
+ } else if (left[it->first] > it->second) {
+ return false;
+ }
+ }
+ return equal ? left._val < right._val : true;
+}
+
+template<>
+Vector infinity<Vector>() {
+ return Vector(infinity<ZBar>());
+}
+
+std::ostream& operator<<(std::ostream& cout, const Vector& v) {
+ cout << "{";
+ for (Vector::const_iterator it = v.begin(), ei = v.end();
+ it != ei;
+ ++it) {
+ cout << it->first << ": " << it->second << ", ";
+ }
+ cout << "_: " << v._val;
+ cout << "}";
+ return cout;
+}
+
+
+
+
+
+
+/* Expression functions */
+
+Result fromExpr(const Expr*);
+
+Result fromInteger(const IntegerLiteral* expr) {
+ return Result(Vector(0), *expr->getValue().getRawData());
+}
+
+Result fromDeclExpr(const DeclRefExpr* expr) {
+ Vector val;
+ val[expr->getNameInfo().getAsString()] = 1;
+ return Result(val, 0);
+}
+
+Result fromUnary(const UnaryOperator* op) {
+ switch (op->getOpcode()) {
+ case UO_PreInc:
+ break;
+ case UO_PostInc:
+ break;
+ }
+ return Result(Vector(0), 0);
+}
+
+Result operator*(const ZBar& l, const Result& r) {
+ return Result(l * r.first, l * r.second);
+}
+
+Result fromBinary(const BinaryOperator* op) {
+ Result left = fromExpr(op->getLHS()->IgnoreParenCasts());
+ Result right = fromExpr(op->getRHS()->IgnoreParenCasts());
+
+ switch (op->getOpcode()) {
+ case BO_Assign:
+ return right;
+ case BO_Sub:
+ right = negate_result(right);
+ //transform_values(negate<ZBar>, right.first);
+ //right.second *= -1;
+ case BO_Add:
+ {
+ Result result;
+ result.first = merge_maps_with(addValues<ZBar>,
+ left.first, right.first);
+ result.second = left.second + right.second;
+ return result;
+ }
+ case BO_Mul:
+ {
+ if (!left.first.empty() && !right.first.empty()) {
+ return Result(Vector(0), 0);
+ }
+ ZBar scalar = 0;
+ Result value;
+ if (left.first.empty()) {
+ scalar = left.second;
+ value = right;
+ } else {
+ scalar = right.second;
+ value = left;
+ }
+ if (scalar >= 0) {
+ return scalar * value;
+ } else {
+ return -scalar * negate_result(value);
+ }
+ }
+ case BO_LT:
+ case BO_LE:
+ case BO_GT:
+ case BO_GE:
+ break;
+ }
+ return Result();
+}
+
+Result fromExpr(const Expr* stmt) {
+ if (!stmt)
+ return Result();
+ //stmt->dump();
+ switch (stmt->getStmtClass()) {
+ case Stmt::IntegerLiteralClass:
+ return fromInteger(static_cast<const IntegerLiteral*>(stmt));
+ case Stmt::DeclRefExprClass:
+ return fromDeclExpr(static_cast<const DeclRefExpr*>(stmt));
+ case Stmt::UnaryOperatorClass:
+ return fromUnary(static_cast<const UnaryOperator*>(stmt));
+ case Stmt::BinaryOperatorClass:
+ return fromBinary(static_cast<const BinaryOperator*>(stmt));
+ }
+ const Expr* expr = stmt->IgnoreParenCasts();
+ if (stmt != expr)
+ return fromExpr(expr);
+ llvm::errs() << "we shouldn't get here...\n";
+ return Result();
+}
+
+
+/* Comparison stuff */
+
+Condition fromComparison(const BinaryOperator* op, bool negate) {
+ Condition cond(infinity<ZBar>());
+ if (!op) {
+ if (negate)
+ return -cond;
+ else
+ return cond;
+ }
+ if (op->isRelationalOp()) {
+ const Expr* left = op->getLHS()->IgnoreParenCasts();
+ const Expr* right = op->getRHS()->IgnoreParenCasts();
+
+ bool flip = false;
+ std::string name;
+ int64_t value;
+ if (left->getStmtClass() == Stmt::DeclRefExprClass) {
+ name = static_cast<const DeclRefExpr*>(left)->getNameInfo().getAsString();
+ } else if (right->getStmtClass() == Stmt::DeclRefExprClass) {
+ name = static_cast<const DeclRefExpr*>(right)->getNameInfo().getAsString();
+ flip = true;
+ } else {
+ return cond;
+ }
+
+ if (right->getStmtClass() == Stmt::IntegerLiteralClass) {
+ value = *static_cast<const IntegerLiteral*>(right)->getValue().getRawData();
+ } else if (left->getStmtClass() == Stmt::IntegerLiteralClass) {
+ value = *static_cast<const IntegerLiteral*>(left)->getValue().getRawData();
+ } else {
+ return cond;
+ }
+
+ BinaryOperator::Opcode operation = op->getOpcode();
+ if (flip) {
+ switch (operation) {
+ case BO_LT: operation = BO_GT; break;
+ case BO_GT: operation = BO_LT; break;
+ case BO_LE: operation = BO_GE; break;
+ case BO_GE: operation = BO_LE; break;
+ }
+ }
+
+ switch (operation) {
+ case BO_LT:
+ if (negate)
+ cond[negate_string(name)] = -value;
+ else
+ cond[name] = value - 1;
+ break;
+ case BO_LE:
+ if (negate)
+ cond[negate_string(name)] = -(value + 1);
+ else
+ cond[name] = value;
+ break;
+ case BO_GE:
+ if (negate)
+ cond[name] = value - 1;
+ else
+ cond[negate_string(name)] = -value;
+ break;
+ case BO_GT:
+ if (negate)
+ cond[name] = value;
+ else
+ cond['-' + name] = -(value + 1);
+ break;
+ }
+ }
+ return cond;
+}
+
+/* Blocks */
+
+typedef std::map<std::string, unsigned int> Counters;
+typedef std::map<std::string, EqnVar*> VarMap;
+typedef std::map<const CFGBlock*, std::set<std::string> > BlockVars;
+
+void runOnBlock(const CFGBlock* block, EqnSys& system, BlockVars& block_vars) {
+ Counters counters;
+ std::string block_id = toString(block->getBlockID());
+ VarMap vars;
+
+ for (std::set<std::string>::iterator it = block_vars[block].begin(),
+ ei = block_vars[block].end();
+ it != ei;
+ ++it) {
+ vars[*it] = &system.variable(*it + '-' + block_id + "-pre");
+ }
+
+ for (CFGBlock::const_iterator it = block->begin(),
+ ei = block->end();
+ it != ei;
+ ++it) {
+ const CFGStmt* cfg_stmt = it->getAs<CFGStmt>();
+ const Stmt* stmt = cfg_stmt->getStmt();
+
+ std::string name = "";
+ Result result;
+ if (stmt->getStmtClass() == Stmt::BinaryOperatorClass) {
+ const BinaryOperator* binop = static_cast<const BinaryOperator*>(stmt);
+ if (binop->isAssignmentOp()) {
+ const Expr* left = binop->getLHS()->IgnoreParenCasts();
+ const Expr* right = binop->getRHS()->IgnoreParenCasts();
+ if (left->getStmtClass() == Stmt::DeclRefExprClass) {
+ name = static_cast<const DeclRefExpr*>(left)->getNameInfo().getAsString();
+ result = fromExpr(right);
+ }
+ }
+ } else if (stmt->getStmtClass() == Stmt::DeclStmtClass) {
+ const DeclStmt* decl_stmt = static_cast<const DeclStmt*>(stmt);
+ for (DeclStmt::const_decl_iterator jt = decl_stmt->decl_begin(),
+ ej = decl_stmt->decl_end();
+ jt != ej;
+ ++jt) {
+ if ((*jt)->getKind() == Decl::Var) {
+ const VarDecl* decl = static_cast<const VarDecl*>(*jt);
+ name = decl->getNameAsString();
+ result = fromExpr(decl->getInit());
+ jt++;
+ if (jt != ej) {
+ llvm::errs() << "Only the first declaration in a multi-declaration statement is used.\n";
+ }
+ break; // only take the first one, for now
+ }
+ }
+ }
+ if (name == "")
+ continue;
+
+ std::string count = toString(counters[name]);
+ EqnVar* var = &system.variable(name + '-' + block_id + '[' + count + ']');
+ EqnVar* negative_var = &system.variable(negate_string(name) + '-' + block_id + '[' + count + ']');
+ counters[name]++;
+ for (int negative = 0; negative < 2; ++negative) { // one loop for positive, the other for negative
+ if (negative) {
+ result = negate_result(result);
+ }
+ EqnExpr* expression = &system.constant(result.second);
+ for (Vector::iterator it = result.first.begin(),
+ ei = result.first.end();
+ it != ei;
+ ++it) {
+ if (!vars[it->first])
+ vars[it->first] = &system.variable(it->first + '-' + block_id + "-pre");
+ std::vector<EqnExpr*> additionArgs;
+ additionArgs.push_back(expression);
+
+ if (it->second == 1) {
+ additionArgs.push_back(vars[it->first]);
+ } else {
+ std::vector<EqnExpr*> multiplicationArgs;
+ multiplicationArgs.push_back(vars[it->first]);
+ multiplicationArgs.push_back(&system.constant(it->second));
+ additionArgs.push_back(&system.expression(new Multiplication<ZBar>(), multiplicationArgs));
+ }
+
+ expression = &system.expression(new Addition<ZBar>(), additionArgs);
+ }
+
+ std::vector<EqnExpr*> maxArgs;
+ maxArgs.push_back(&system.constant(-infinity<ZBar>()));
+ maxArgs.push_back(expression);
+ if (negative)
+ system[*negative_var] = &system.maxExpression(maxArgs);
+ else
+ system[*var] = &system.maxExpression(maxArgs);
+ }
+ vars[name] = var;
+ vars[negate_string(name)] = negative_var;
+ block_vars[block].insert(name);
+ block_vars[block].insert(negate_string(name));
+ }
+
+ // add to our successor entry values
+ for (CFGBlock::const_succ_iterator
+ it = block->succ_begin(),
+ ei = block->succ_end();
+ it != ei;
+ ++it) {
+ bool negate_terminator = it != block->succ_begin(); // not the first means `false` branch
+ Condition cond = fromComparison(static_cast<const BinaryOperator*>(block->getTerminatorCondition()), negate_terminator);
+ for (VarMap::iterator jt = vars.begin(),
+ ej = vars.end();
+ jt != ej;
+ ++jt) {
+ block_vars[*it].insert(jt->first);
+
+ ZBar val = cond[jt->first];
+ EqnVar* var = &system.variable(jt->first + '-' + toString((*it)->getBlockID()) + "-pre");
+ if (system[*var] == NULL) {
+ std::vector<EqnExpr*> maxArgs;
+ maxArgs.push_back(&system.constant(-infinity<ZBar>()));
+ system[*var] = &system.maxExpression(maxArgs);
+ }
+
+ EqnExpr* expr = NULL;
+ if (val == -infinity<ZBar>()) {
+ // don't do anything here: min(-inf, x) = -inf (for all x)
+ } else if (val == infinity<ZBar>()) {
+ // no need to have a min here: min(inf, x) = x (for all x)
+ expr = jt->second;
+ } else {
+ // need a min here
+ std::vector<EqnExpr*> minArgs;
+ minArgs.push_back(&system.constant(val));
+ minArgs.push_back(jt->second);
+ expr = &system.expression(new Minimum<ZBar>(), minArgs);
+ }
+
+ if (expr) {
+ std::set<std::string> ignore;
+ for (VarMap::iterator
+ variables = vars.begin(),
+ variables_end = vars.end();
+ variables != variables_end;
+ ++variables) {
+ if (ignore.find(variables->first) != ignore.end())
+ continue;
+ ignore.insert(negate_string(variables->first));
+
+ std::vector<EqnExpr*> plusArgs;
+ for (int negate = 0; negate < 2; ++negate) {
+ std::string var_name = negate ? negate_string(variables->first) : variables->first;
+ std::vector<EqnExpr*> minArgs;
+ minArgs.push_back(vars[var_name]);
+ minArgs.push_back(&system.constant(cond[var_name]));
+ plusArgs.push_back(&system.expression(new Minimum<ZBar>(), minArgs));
+ }
+
+ std::vector<EqnExpr*> guard_args;
+ guard_args.push_back(&system.expression(new Addition<ZBar>(), plusArgs)); // value
+ guard_args.push_back(&system.constant(0)); // lower-bound (so value must be >= this)
+ guard_args.push_back(expr); // result
+ expr = &system.expression(new Guard<ZBar>(), guard_args);
+ }
+ system[*var]->arguments().push_back(expr);
+ }
+ }
+ }
+}
+
+
+
+
+
+
+IntervalAnalysis :: IntervalAnalysis(AnalysisDeclContext &context)
+ : context(&context) {
+}
+
+IntervalAnalysis :: ~IntervalAnalysis() {
+}
+
+void IntervalAnalysis::runOnAllBlocks() {
+ const CFG *cfg = this->context->getCFG();
+
+ cfg->dump(context->getASTContext().getLangOpts(),
+ llvm::sys::Process::StandardErrHasColors());
+
+ EqnSys system;
+ BlockVars block_vars;
+
+ std::set<const CFGBlock*> seen;
+ std::deque<const CFGBlock*> todo;
+ todo.push_back(&cfg->getEntry());
+
+ while (!todo.empty()) {
+ const CFGBlock* block = todo.front();
+ if (seen.find(todo.front()) != seen.end()) {
+ todo.pop_front();
+ continue;
+ }
+ seen.insert(block);
+ todo.pop_front();
+ runOnBlock(block, system, block_vars);
+ for (CFGBlock::const_succ_iterator it = block->succ_begin(),
+ ei = block->succ_end();
+ it != ei;
+ it++ ) {
+ todo.push_back(*it);
+ }
+ }
+
+ std::vector<EqnExpr*> a;
+
+ a.push_back(&system.constant(-infinity<ZBar>()));
+ a.push_back(&system.constant(0));
+ system[system.variable("x")] = &system.maxExpression(a);
+ a.clear();
+
+ system.variable("y");
+
+ a.push_back(&system.variable("x"));
+ a.push_back(&system.variable("z"));
+ EqnExpr* minExpr = &system.expression(new Maximum<ZBar>(), a);
+ a.clear();
+
+ a.push_back(&system.constant(-infinity<ZBar>()));
+ a.push_back(minExpr);
+ system[system.variable("y")] = &system.maxExpression(a);
+ a.clear();
+
+ a.push_back(&system.constant(-infinity<ZBar>()));
+ a.push_back(&system.variable("y"));
+ system[system.variable("z")] = &system.maxExpression(a);
+
+ llvm::errs() << toString(system) << "\n";
+
+ system.indexMaxExpressions();
+ DynamicMaxStrategy<ZBar> strategy(system);
+ DynamicVariableAssignment<ZBar> rho(system, strategy);
+ strategy.setRho(rho);
+
+ for (unsigned int i = 0, size = system.variableCount(); i < size; ++i) {
+ EqnVar& var = system.variable(size - i - 1);
+ llvm::errs() << toString(var.name()) << " = " << toString(rho[var]) << "\n";
+ }
+}
+
+
+const void *IntervalAnalysis::getTag() { static int x; return &x; }
generated by cgit v1.2.3 (git 2.46.0) at 2024-09-21 00:37:29 +0000