summaryrefslogtreecommitdiff
path: root/clang/lib/Analysis
diff options
context:
space:
mode:
Diffstat (limited to 'clang/lib/Analysis')
-rw-r--r--clang/lib/Analysis/CMakeLists.txt5
-rw-r--r--clang/lib/Analysis/Interval.cpp568
2 files changed, 311 insertions, 262 deletions
diff --git a/clang/lib/Analysis/CMakeLists.txt b/clang/lib/Analysis/CMakeLists.txt
index bede002..3d2251e 100644
--- a/clang/lib/Analysis/CMakeLists.txt
+++ b/clang/lib/Analysis/CMakeLists.txt
@@ -21,5 +21,8 @@ add_clang_library(clangAnalysis
UninitializedValues.cpp
)
+add_library(lib_lemon IMPORTED emon)
+
add_dependencies(clangAnalysis ClangAttrClasses ClangAttrList
- ClangDiagnosticAnalysis ClangDeclNodes ClangStmtNodes)
+ ClangDiagnosticAnalysis ClangDeclNodes ClangStmtNodes
+ lib_lemon)
diff --git a/clang/lib/Analysis/Interval.cpp b/clang/lib/Analysis/Interval.cpp
index 96dd841..ac96107 100644
--- a/clang/lib/Analysis/Interval.cpp
+++ b/clang/lib/Analysis/Interval.cpp
@@ -21,6 +21,12 @@
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) {
@@ -36,6 +42,20 @@ std::ostream& operator<<(std::ostream& cout, const std::pair<K,V>& v) {
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 << "{";
@@ -50,14 +70,6 @@ std::ostream& operator<<(std::ostream& cout, const std::map<K,V>& v) {
return cout;
}
-
-IntervalAnalysis :: IntervalAnalysis(AnalysisDeclContext &context)
- : context(&context) {
-}
-
-IntervalAnalysis :: ~IntervalAnalysis() {
-}
-
// Two pieces of state:
// -> condition protecting a node
// -> node's expression itself
@@ -68,10 +80,14 @@ IntervalAnalysis :: ~IntervalAnalysis() {
// 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=infinity<ZBar>())
+ Vector(const ZBar& val=0)
: _val(val) { }
ZBar operator[](const std::string& key) const {
if (this->find(key) != this->end())
@@ -87,8 +103,23 @@ struct Vector : public std::map<std::string, ZBar> {
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 {
@@ -112,21 +143,21 @@ struct LinearEquation : public std::map<std::string, Result> {
typedef Vector Condition;
-typedef EquationSystem<Vector> EqnSys;
-typedef Expression<Vector> EqnExpr;
-typedef Variable<Vector> EqnVar;
+typedef EquationSystem<ZBar> EqnSys;
+typedef Expression<ZBar> EqnExpr;
+typedef Variable<ZBar> EqnVar;
struct LinearOperator : public Operator<Vector> {
- LinearOperator(const LinearEquation& result)
+ 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();
+ for (LinearEquation::const_iterator it = _values->begin(),
+ ei = _values->end();
it != ei;
++it) {
ZBar subresult = 0;
@@ -143,10 +174,10 @@ struct LinearOperator : public Operator<Vector> {
}
void print(std::ostream& cout) const {
- cout << "linear[" << _values << "]";
+ cout << "linear[" << *_values << "]";
}
- LinearEquation _values;
+ const LinearEquation* _values;
};
@@ -192,6 +223,7 @@ M merge_maps_with(const F& f, const M& left, const M& right) {
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>
@@ -240,12 +272,15 @@ 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]) {
- return true;
+ equal = false;
+ } else if (it->second > right[it->first]) {
+ return false;
}
}
for (Vector::const_iterator it = right.begin(),
@@ -253,10 +288,12 @@ bool operator<(const Vector& left, const Vector& right) {
it != ei;
++it) {
if (left[it->first] < it->second) {
- return true;
+ equal = false;
+ } else if (left[it->first] > it->second) {
+ return false;
}
}
- return false;
+ return equal ? left._val < right._val : true;
}
template<>
@@ -277,10 +314,16 @@ std::ostream& operator<<(std::ostream& cout, const Vector& v) {
}
-Result fromStmt(const Stmt*);
+
+
+
+
+/* Expression functions */
+
+Result fromExpr(const Expr*);
Result fromInteger(const IntegerLiteral* expr) {
- return Result(Vector(), *expr->getValue().getRawData());
+ return Result(Vector(0), *expr->getValue().getRawData());
}
Result fromDeclExpr(const DeclRefExpr* expr) {
@@ -296,19 +339,24 @@ Result fromUnary(const UnaryOperator* op) {
case UO_PostInc:
break;
}
- return Result(Vector(), 0);
+ 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 = fromStmt(op->getLHS()->IgnoreParenCasts());
- Result right = fromStmt(op->getRHS()->IgnoreParenCasts());
+ Result left = fromExpr(op->getLHS()->IgnoreParenCasts());
+ Result right = fromExpr(op->getRHS()->IgnoreParenCasts());
switch (op->getOpcode()) {
case BO_Assign:
return right;
case BO_Sub:
- transform_values(negate<ZBar>, right.first);
- right.second *= -1;
+ right = negate_result(right);
+ //transform_values(negate<ZBar>, right.first);
+ //right.second *= -1;
case BO_Add:
{
Result result;
@@ -320,7 +368,7 @@ Result fromBinary(const BinaryOperator* op) {
case BO_Mul:
{
if (!left.first.empty() && !right.first.empty()) {
- return Result(Vector(), 0);
+ return Result(Vector(0), 0);
}
ZBar scalar = 0;
Result value;
@@ -331,30 +379,11 @@ Result fromBinary(const BinaryOperator* op) {
scalar = right.second;
value = left;
}
- if (scalar > 0) {
- for (Vector::iterator it = value.first.begin(),
- ei = value.first.end();
- it != ei;
- ++it) {
- it->second *= scalar;
- }
+ if (scalar >= 0) {
+ return scalar * value;
} else {
- Vector newValue;
- for (Vector::iterator it = value.first.begin(),
- ei = value.first.end();
- it != ei;
- ++it) {
- std::string name;
- if (it->first[0] == '-') {
- name = it->first.substr(1);
- } else {
- name = '-' + it->first;
- }
- newValue[name] = (-scalar) * it->second;
- }
+ return -scalar * negate_result(value);
}
- right.second *= scalar;
- return value;
}
case BO_LT:
case BO_LE:
@@ -365,65 +394,7 @@ Result fromBinary(const BinaryOperator* op) {
return Result();
}
-Result fromDeclStmt(const DeclStmt* stmt) {
- for (DeclStmt::const_decl_iterator it = stmt->decl_begin(),
- ei = stmt->decl_end();
- it != ei;
- ++it) {
- if ((*it)->getKind() == Decl::Var) {
- const VarDecl* decl = static_cast<const VarDecl*>(*it);
- llvm::errs() << decl->getNameAsString() << " = ";
-
- Result expr = fromStmt(decl->getInit());
- for (Vector::iterator it = expr.first.begin(),
- ei = expr.first.end();
- it != ei;
- ++it) {
- if (it != expr.first.begin())
- llvm::errs() << " + ";
- llvm::errs() << toString(it->second) << "*" << toString(it->first);
- }
- llvm::errs() << " + " << toString(expr.second) << "\n";
-
-
- llvm::errs() << "-" << decl->getNameAsString() << " = ";
- for (Vector::iterator it = expr.first.begin(),
- ei = expr.first.end();
- it != ei;
- ++it) {
- if (it != expr.first.begin())
- llvm::errs() << " + ";
- llvm::errs() << toString(it->second) << "*" << toString(it->first);
- }
- llvm::errs() << " - " << toString(expr.second) << "\n";
- }
- }
-
- return Result();
-}
-
-Result fromAssignment(const BinaryOperator* op) {
- const Expr* left = op->getLHS()->IgnoreParenCasts();
- if (left->getStmtClass() == Stmt::DeclRefExprClass) {
- std::string name = static_cast<const DeclRefExpr*>(left)->getNameInfo().getAsString();
-
- Result expr = fromStmt(op->getRHS()->IgnoreParenCasts());
- llvm::errs() << name << " = ";
- for (Vector::iterator it = expr.first.begin(),
- ei = expr.first.end();
- it != ei;
- ++it) {
- if (it != expr.first.begin())
- llvm::errs() << " + ";
- llvm::errs() << toString(it->second) << "*" << toString(it->first);
- }
- llvm::errs() << " + " << toString(expr.second) << "\n";
- return expr;
- }
- return Result();
-}
-
-Result fromStmt(const Stmt* stmt) {
+Result fromExpr(const Expr* stmt) {
if (!stmt)
return Result();
//stmt->dump();
@@ -434,93 +405,109 @@ Result fromStmt(const Stmt* stmt) {
return fromDeclExpr(static_cast<const DeclRefExpr*>(stmt));
case Stmt::UnaryOperatorClass:
return fromUnary(static_cast<const UnaryOperator*>(stmt));
- case Stmt::DeclStmtClass:
- return fromDeclStmt(static_cast<const DeclStmt*>(stmt));
case Stmt::BinaryOperatorClass:
return fromBinary(static_cast<const BinaryOperator*>(stmt));
}
- const Expr* expr = dyn_cast<const Expr>(stmt);
- if (expr) {
- const Expr* expr2 = expr->IgnoreParenCasts();
- if (expr != expr2)
- return fromStmt(expr2);
- }
+ const Expr* expr = stmt->IgnoreParenCasts();
+ if (stmt != expr)
+ return fromExpr(expr);
llvm::errs() << "we shouldn't get here...\n";
return Result();
}
-Condition fromComparison(const BinaryOperator* op) {
+
+/* 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();
- Condition cond;
+ bool flip = false;
std::string name;
int64_t value;
if (left->getStmtClass() == Stmt::DeclRefExprClass) {
- if (right->getStmtClass() == Stmt::IntegerLiteralClass) {
- name = static_cast<const DeclRefExpr*>(left)->getNameInfo().getAsString();
- value = *static_cast<const IntegerLiteral*>(right)->getValue().getRawData();
- switch (op->getOpcode()) {
- case BO_LT:
- cond[name] = value - 1;
- break;
- case BO_LE:
- cond[name] = value;
- break;
- case BO_GE:
- cond['-' + name] = -value;
- break;
- case BO_GT:
- cond['-' + name] = -(value + 1);
- break;
- }
- return cond;
- } else {
- return Condition();
- }
+ name = static_cast<const DeclRefExpr*>(left)->getNameInfo().getAsString();
} else if (right->getStmtClass() == Stmt::DeclRefExprClass) {
- if (left->getStmtClass() == Stmt::IntegerLiteralClass) {
- name = static_cast<const DeclRefExpr*>(right)->getNameInfo().getAsString();
- value = *static_cast<const IntegerLiteral*>(left)->getValue().getRawData();
- switch (op->getOpcode()) {
- case BO_LT:
- cond['-' + name] = -(value + 1);
- break;
- case BO_LE:
- cond['-' + name] = -value;
- break;
- case BO_GE:
- cond[name] = value;
- break;
- case BO_GT:
- cond[name] = value - 1;
- break;
- }
- return cond;
- } else {
- return Condition();
+ 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;
}
}
- return Condition();
+
+ 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 Condition();
+ return cond;
}
-std::map<const CFGBlock*, EqnVar*> seen_blocks;
-EqnVar* runOnBlock(const CFGBlock* block, EqnSys& system) {
- if (seen_blocks.find(block) != seen_blocks.end())
- return seen_blocks.find(block)->second;
+/* Blocks */
- std::string id = toString(block->getBlockID());
- unsigned int counter = 0;
-
- // detemine equations for this block
- LinearEquation eqn;
- EqnVar* var;
- Result current;
+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;
- var = &system.variable(id);
+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;
@@ -529,7 +516,7 @@ EqnVar* runOnBlock(const CFGBlock* block, EqnSys& system) {
const Stmt* stmt = cfg_stmt->getStmt();
std::string name = "";
- Result expr;
+ Result result;
if (stmt->getStmtClass() == Stmt::BinaryOperatorClass) {
const BinaryOperator* binop = static_cast<const BinaryOperator*>(stmt);
if (binop->isAssignmentOp()) {
@@ -537,11 +524,10 @@ EqnVar* runOnBlock(const CFGBlock* block, EqnSys& system) {
const Expr* right = binop->getRHS()->IgnoreParenCasts();
if (left->getStmtClass() == Stmt::DeclRefExprClass) {
name = static_cast<const DeclRefExpr*>(left)->getNameInfo().getAsString();
- expr = fromStmt(right);
+ result = fromExpr(right);
}
}
} else if (stmt->getStmtClass() == Stmt::DeclStmtClass) {
- stmt->dump();
const DeclStmt* decl_stmt = static_cast<const DeclStmt*>(stmt);
for (DeclStmt::const_decl_iterator jt = decl_stmt->decl_begin(),
ej = decl_stmt->decl_end();
@@ -550,104 +536,150 @@ EqnVar* runOnBlock(const CFGBlock* block, EqnSys& system) {
if ((*jt)->getKind() == Decl::Var) {
const VarDecl* decl = static_cast<const VarDecl*>(*jt);
name = decl->getNameAsString();
- expr = fromStmt(decl->getInit());
- if (jt+1 != ej) {
+ result = fromExpr(decl->getInit());
+ jt++;
+ if (jt != ej) {
llvm::errs() << "Only the first declaration in a multi-declaration statement is used.\n";
}
- llvm::errs() << "Name: " << name << "\n";
- llvm::errs() << toString(expr) << "\n";
break; // only take the first one, for now
- } else {
- llvm::errs() << (*jt)->getDeclKindName() << "\n";
}
}
}
if (name == "")
continue;
- // by here we expect `name` and `expr` to be set correctly
-
- bool newBlock = false;
- for (Vector::const_iterator jt = expr.first.begin(),
- ej = expr.first.end();
- jt != ej;
- ++jt) {
- // new block if we read from any variable we've already written to
- newBlock |= (eqn.find(jt->first) != eqn.end());
+ 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));
+ }
- if (newBlock) {
- EqnVar* lastVar = var;
- var = &system.variable(id + "-" + toString(++counter));
-
- // the linear expression
- std::vector<EqnExpr*> args;
- args.push_back(lastVar);
- EqnExpr* expr = &system.expression(new LinearOperator(eqn), args);
+ // 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);
+ }
- // the max expression
- std::vector<EqnExpr*> maxArgs;
- maxArgs.push_back(&system.constant(-infinity<Vector>()));
- maxArgs.push_back(expr);
- system[*var] = &system.maxExpression(args);
- eqn = LinearEquation();
+ 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);
+ }
}
-
- eqn[name] = expr;
- expr.first = expr.first;
- expr.second = -expr.second;
- eqn["-"+name] = expr;
}
+}
- EqnVar* lastVar = var;
- var = &system.variable(id + "-" + toString(++counter));
- // the linear expression
- std::vector<EqnExpr*> args;
- args.push_back(lastVar);
- EqnExpr* expr = &system.expression(new LinearOperator(eqn), args);
- // the max expression
- std::vector<EqnExpr*> maxArgs;
- maxArgs.push_back(&system.constant(-infinity<Vector>()));
- maxArgs.push_back(expr);
- system[*var] = &system.maxExpression(maxArgs);
- // save the last variable we used (the final values from this block)
- seen_blocks[block] = var;
- // determine predecessor variables/conditions
- // we have to do this last to prevent an infinite loop situation
- std::vector<EqnExpr*> preArgs;
- for (CFGBlock::const_pred_iterator it = block->pred_begin(),
- ei = block->pred_end();
- it != ei;
- ++it) {
- if ((*it)->getTerminatorCondition()) {
- const BinaryOperator* binop = static_cast<const BinaryOperator*>((*it)->getTerminatorCondition());
- std::vector<EqnExpr*> args;
- args.push_back(&system.constant(fromComparison(binop)));
- args.push_back(runOnBlock(*it, system));
- preArgs.push_back(&system.expression(new Minimum<Vector>(), args));
- } else {
- preArgs.push_back(runOnBlock(*it, system));
- }
- }
- EqnVar* preVar = &system.variable(id);
- if (preArgs.empty())
- preArgs.push_back(&system.constant(infinity<Vector>()));
- system[*preVar] = &system.maxExpression(preArgs);
- // return the final value we used
- return var;
+IntervalAnalysis :: IntervalAnalysis(AnalysisDeclContext &context)
+ : context(&context) {
}
-void IntervalAnalysis::runOnAllBlocks() {
- llvm::errs() << "Enter run on all blocks\n";
+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;
@@ -659,37 +691,51 @@ void IntervalAnalysis::runOnAllBlocks() {
todo.pop_front();
continue;
}
- llvm::errs() << block->getBlockID() << "\n";
seen.insert(block);
todo.pop_front();
- runOnBlock(block, system);
- llvm::errs() << "-> ";
+ runOnBlock(block, system, block_vars);
for (CFGBlock::const_succ_iterator it = block->succ_begin(),
ei = block->succ_end();
it != ei;
it++ ) {
- llvm::errs() << (*it)->getBlockID() << ", ";
todo.push_back(*it);
}
- llvm::errs() << "\n\n";
}
- llvm::errs() << "Exit run on all blocks\n";
+ 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<Vector> strategy(system);
- DynamicVariableAssignment<Vector> rho(system, strategy);
+ DynamicMaxStrategy<ZBar> strategy(system);
+ DynamicVariableAssignment<ZBar> rho(system, strategy);
strategy.setRho(rho);
for (unsigned int i = 0, size = system.variableCount(); i < size; ++i) {
- Variable<Vector>& var = system.variable(i);
+ EqnVar& var = system.variable(size - i - 1);
llvm::errs() << toString(var.name()) << " = " << toString(rho[var]) << "\n";
}
-
- // cfg->dump(context->getASTContext().getLangOpts(),
- // llvm::sys::Process::StandardErrHasColors());
}
generated by cgit v1.2.3 (git 2.46.2) at 2024-12-25 17:31:53 +0000