From 684045e9e843ed9b8be30728482ce3d69d63b527 Mon Sep 17 00:00:00 2001 From: "Zancanaro; Carlo" Date: Thu, 4 Oct 2012 17:11:33 +1000 Subject: Lets keep trying with this here equation system. Still not there, but more non-functional code is there. Splitting blocks into sub-blocks now works, as does some of the guard stuff and the general "shape" of the resulting equation system. --- clang/lib/Analysis/Interval.cpp | 535 ++++++++++++++++++++++++++++++++-------- 1 file changed, 435 insertions(+), 100 deletions(-) (limited to 'clang/lib/Analysis/Interval.cpp') diff --git a/clang/lib/Analysis/Interval.cpp b/clang/lib/Analysis/Interval.cpp index 726c6de..96dd841 100644 --- a/clang/lib/Analysis/Interval.cpp +++ b/clang/lib/Analysis/Interval.cpp @@ -17,12 +17,10 @@ #include #include #include +#include using namespace clang; -typedef EquationSystem > EqnSys; -typedef Expression > EqnExpr; - #include template std::string toString(const T& obj) { @@ -31,6 +29,28 @@ std::string toString(const T& obj) { return stream.str(); } +#include +template +std::ostream& operator<<(std::ostream& cout, const std::pair& v) { + cout << "(" << v.first << ", " << v.second << ")"; + return cout; +} + +template +std::ostream& operator<<(std::ostream& cout, const std::map& v) { + cout << "{"; + for (typename std::map::const_iterator it = v.begin(), ei = v.end(); + it != ei; + ++it) { + if (it != v.begin()) + cout << ", "; + cout << it->first << ": " << it->second; + } + cout << "}"; + return cout; +} + + IntervalAnalysis :: IntervalAnalysis(AnalysisDeclContext &context) : context(&context) { } @@ -48,9 +68,89 @@ IntervalAnalysis :: ~IntervalAnalysis() { // Hooray! typedef Complete ZBar; -typedef std::map Vector; +//typedef std::map Vector; + +struct Vector : public std::map { + Vector(const ZBar& val=infinity()) + : _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 p = this->insert(std::pair(key, _val)); + return p.first->second; + } + ZBar _val; +}; + typedef std::pair Result; // a "slice" of an equation +//typedef std::map LinearEquation; // one `Result` per variable +struct LinearEquation : public std::map { + 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 p = this->insert(std::pair(key, r)); + return p.first->second; + } +}; + +typedef Vector Condition; + +typedef EquationSystem EqnSys; +typedef Expression EqnExpr; +typedef Variable EqnVar; + + +struct LinearOperator : public Operator { + LinearOperator(const LinearEquation& result) + : _values(result) {} + + Vector eval(const std::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 << "]"; + } + + LinearEquation _values; +}; + + + template void transform_values(const F& f, M& map) { for (typename M::iterator it = map.begin(), @@ -90,6 +190,14 @@ M merge_maps_with(const F& f, const M& left, const M& right) { return result; } +template<> +Vector minimum(const Vector& l, const Vector& r) { + return merge_maps_with(minimum, l, r); +} +template +T max(const T& l, const T& r) { + return (l < r ? l : r); +} template T negate(const T& v) { return -v; @@ -98,25 +206,90 @@ template T addValues(const T& l, const T& r) { return l + r; } -template -T subValues(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, left, right); +} + +Vector operator-(const Vector& left, const Vector& right) { + return merge_maps_with(addValues, 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) { + for (Vector::const_iterator it = left.begin(), + ei = left.end(); + it != ei; + ++it) { + if (it->second < right[it->first]) { + return true; + } + } + for (Vector::const_iterator it = right.begin(), + ei = right.end(); + it != ei; + ++it) { + if (left[it->first] < it->second) { + return true; + } + } + return false; +} + +template<> +Vector infinity() { + return Vector(infinity()); +} + +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; } -Result fromStmt(const Stmt*, EqnSys&); +Result fromStmt(const Stmt*); -Result fromInteger(const IntegerLiteral* expr, EqnSys& system) { +Result fromInteger(const IntegerLiteral* expr) { return Result(Vector(), *expr->getValue().getRawData()); } -Result fromDeclExpr(const DeclRefExpr* expr, EqnSys& system) { +Result fromDeclExpr(const DeclRefExpr* expr) { Vector val; val[expr->getNameInfo().getAsString()] = 1; return Result(val, 0); } -Result fromUnary(const UnaryOperator* op, EqnSys& system) { +Result fromUnary(const UnaryOperator* op) { switch (op->getOpcode()) { case UO_PreInc: break; @@ -126,18 +299,16 @@ Result fromUnary(const UnaryOperator* op, EqnSys& system) { return Result(Vector(), 0); } - -Addition >* add = new Addition >(); -Subtraction >* sub = new Subtraction >(); -Multiplication >* mul = new Multiplication >(); - -Result fromBinary(const BinaryOperator* op, EqnSys& system) { - Result left = fromStmt(op->getLHS()->IgnoreParenCasts(), system); - Result right = fromStmt(op->getRHS()->IgnoreParenCasts(), system); +Result fromBinary(const BinaryOperator* op) { + Result left = fromStmt(op->getLHS()->IgnoreParenCasts()); + Result right = fromStmt(op->getRHS()->IgnoreParenCasts()); switch (op->getOpcode()) { + case BO_Assign: + return right; case BO_Sub: transform_values(negate, right.first); + right.second *= -1; case BO_Add: { Result result; @@ -160,11 +331,27 @@ Result fromBinary(const BinaryOperator* op, EqnSys& system) { scalar = right.second; value = left; } - for (Vector::iterator it = value.first.begin(), - ei = value.first.end(); - it != ei; - ++it) { - it->second *= scalar; + if (scalar > 0) { + for (Vector::iterator it = value.first.begin(), + ei = value.first.end(); + it != ei; + ++it) { + it->second *= scalar; + } + } 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; + } } right.second *= scalar; return value; @@ -178,21 +365,7 @@ Result fromBinary(const BinaryOperator* op, EqnSys& system) { return Result(); } -Result fromDeclStmt(const DeclStmt* stmt, EqnSys& system) { - /*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(*it); - Variable > var = system.variable(decl->getNameAsString()); - std::vector args; - args.push_back(&system.constant(-infinity >())); - args.push_back(fromStmt(decl->getInit(), system)); - system[var] = &system.maxExpression(args); - } - }*/ - +Result fromDeclStmt(const DeclStmt* stmt) { for (DeclStmt::const_decl_iterator it = stmt->decl_begin(), ei = stmt->decl_end(); it != ei; @@ -201,110 +374,272 @@ Result fromDeclStmt(const DeclStmt* stmt, EqnSys& system) { const VarDecl* decl = static_cast(*it); llvm::errs() << decl->getNameAsString() << " = "; - Result expr = fromStmt(decl->getInit(), system); - llvm::errs() << "<{ "; + 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->first) << " = " << toString(it->second); + llvm::errs() << " + "; + llvm::errs() << toString(it->second) << "*" << toString(it->first); } - llvm::errs() << " }, " << toString(expr.second) << ">\n"; + 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, EqnSys& system) { - /*EqnExpr* left = fromStmt(op->getLHS()->IgnoreParenCasts(), system); - EqnExpr* right = fromStmt(op->getRHS()->IgnoreParenCasts(), system); - Variable >* var = static_cast >*>(left); - - std::vector args; - args.push_back(&system.constant(-infinity >())); - args.push_back(right); - if (system[*var] != NULL) - args.push_back(system[*var]); - system[*var] = &system.maxExpression(args);*/ - +Result fromAssignment(const BinaryOperator* op) { const Expr* left = op->getLHS()->IgnoreParenCasts(); if (left->getStmtClass() == Stmt::DeclRefExprClass) { std::string name = static_cast(left)->getNameInfo().getAsString(); - Result expr = fromStmt(op->getRHS()->IgnoreParenCasts(), system); - llvm::errs() << name << " = <{ "; + 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->first) << " = " << toString(it->second); + llvm::errs() << " + "; + llvm::errs() << toString(it->second) << "*" << toString(it->first); } - llvm::errs() << " }, " << toString(expr.second) << ">\n"; + llvm::errs() << " + " << toString(expr.second) << "\n"; return expr; } return Result(); } -Result fromStmt(const Stmt* stmt, EqnSys& system) { +Result fromStmt(const Stmt* stmt) { if (!stmt) return Result(); + //stmt->dump(); switch (stmt->getStmtClass()) { case Stmt::IntegerLiteralClass: - return fromInteger(static_cast(stmt), system); + return fromInteger(static_cast(stmt)); case Stmt::DeclRefExprClass: - return fromDeclExpr(static_cast(stmt), system); + return fromDeclExpr(static_cast(stmt)); case Stmt::UnaryOperatorClass: - return fromUnary(static_cast(stmt), system); + return fromUnary(static_cast(stmt)); case Stmt::DeclStmtClass: - return fromDeclStmt(static_cast(stmt), system); + return fromDeclStmt(static_cast(stmt)); case Stmt::BinaryOperatorClass: - { - const BinaryOperator* binop = static_cast(stmt); - if (binop->isAssignmentOp()) - return fromAssignment(binop, system); - else - return fromBinary(binop, system); - } + return fromBinary(static_cast(stmt)); + } + const Expr* expr = dyn_cast(stmt); + if (expr) { + const Expr* expr2 = expr->IgnoreParenCasts(); + if (expr != expr2) + return fromStmt(expr2); } + llvm::errs() << "we shouldn't get here...\n"; return Result(); } -void runOnBlock(std::string id, const CFGBlock* block, EqnSys& system) { +Condition fromComparison(const BinaryOperator* op) { + if (op->isRelationalOp()) { + const Expr* left = op->getLHS()->IgnoreParenCasts(); + const Expr* right = op->getRHS()->IgnoreParenCasts(); + + Condition cond; + std::string name; + int64_t value; + if (left->getStmtClass() == Stmt::DeclRefExprClass) { + if (right->getStmtClass() == Stmt::IntegerLiteralClass) { + name = static_cast(left)->getNameInfo().getAsString(); + value = *static_cast(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(); + } + } else if (right->getStmtClass() == Stmt::DeclRefExprClass) { + if (left->getStmtClass() == Stmt::IntegerLiteralClass) { + name = static_cast(right)->getNameInfo().getAsString(); + value = *static_cast(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(); + } + } + return Condition(); + } + return Condition(); +} + +std::map seen_blocks; +EqnVar* runOnBlock(const CFGBlock* block, EqnSys& system) { + if (seen_blocks.find(block) != seen_blocks.end()) + return seen_blocks.find(block)->second; + + std::string id = toString(block->getBlockID()); + unsigned int counter = 0; + + // detemine equations for this block + LinearEquation eqn; + EqnVar* var; + Result current; + + var = &system.variable(id); for (CFGBlock::const_iterator it = block->begin(), ei = block->end(); it != ei; ++it) { const CFGStmt* cfg_stmt = it->getAs(); - Result expr = fromStmt(cfg_stmt->getStmt(), system); - /*llvm::errs() << "<{ "; - 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->first) << " = " << toString(it->second); + const Stmt* stmt = cfg_stmt->getStmt(); + + std::string name = ""; + Result expr; + if (stmt->getStmtClass() == Stmt::BinaryOperatorClass) { + const BinaryOperator* binop = static_cast(stmt); + if (binop->isAssignmentOp()) { + const Expr* left = binop->getLHS()->IgnoreParenCasts(); + const Expr* right = binop->getRHS()->IgnoreParenCasts(); + if (left->getStmtClass() == Stmt::DeclRefExprClass) { + name = static_cast(left)->getNameInfo().getAsString(); + expr = fromStmt(right); + } + } + } else if (stmt->getStmtClass() == Stmt::DeclStmtClass) { + stmt->dump(); + const DeclStmt* decl_stmt = static_cast(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(*jt); + name = decl->getNameAsString(); + expr = fromStmt(decl->getInit()); + if (jt+1 != 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"; + } + } } - llvm::errs() << "}, " << toString(expr.second) << ">\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()); + } + + if (newBlock) { + EqnVar* lastVar = var; + var = &system.variable(id + "-" + toString(++counter)); + + // the linear expression + std::vector args; + args.push_back(lastVar); + EqnExpr* expr = &system.expression(new LinearOperator(eqn), args); + + // the max expression + std::vector maxArgs; + maxArgs.push_back(&system.constant(-infinity())); + maxArgs.push_back(expr); + system[*var] = &system.maxExpression(args); + eqn = LinearEquation(); + } + + eqn[name] = expr; + expr.first = expr.first; + expr.second = -expr.second; + eqn["-"+name] = expr; } - fromStmt(block->getTerminatorCondition(), system); - /*if (terminator.getStmt() != NULL) { - if (terminator.getStmt()->getStmtClass() == Stmt::IfStmtClass) { - const IfStmt* if_stmt = static_cast(terminator.getStmt()); - llvm::errs() << "If: \n"; - if_stmt->dump(); + EqnVar* lastVar = var; + var = &system.variable(id + "-" + toString(++counter)); + + // the linear expression + std::vector args; + args.push_back(lastVar); + EqnExpr* expr = &system.expression(new LinearOperator(eqn), args); + + // the max expression + std::vector maxArgs; + maxArgs.push_back(&system.constant(-infinity())); + 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 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((*it)->getTerminatorCondition()); + std::vector args; + args.push_back(&system.constant(fromComparison(binop))); + args.push_back(runOnBlock(*it, system)); + preArgs.push_back(&system.expression(new Minimum(), args)); } else { - llvm::errs() << "\n"; - terminator.getStmt()->dump(); + preArgs.push_back(runOnBlock(*it, system)); } - }*/ - return; // TODO: return a generated expression + } + EqnVar* preVar = &system.variable(id); + if (preArgs.empty()) + preArgs.push_back(&system.constant(infinity())); + system[*preVar] = &system.maxExpression(preArgs); + + // return the final value we used + return var; } void IntervalAnalysis::runOnAllBlocks() { @@ -324,16 +659,16 @@ void IntervalAnalysis::runOnAllBlocks() { todo.pop_front(); continue; } - llvm::errs() << (void*)block << "\n"; + llvm::errs() << block->getBlockID() << "\n"; seen.insert(block); todo.pop_front(); - runOnBlock(toString(block), block, system); + runOnBlock(block, system); llvm::errs() << "-> "; for (CFGBlock::const_succ_iterator it = block->succ_begin(), ei = block->succ_end(); it != ei; it++ ) { - llvm::errs() << (void*) *it << ", "; + llvm::errs() << (*it)->getBlockID() << ", "; todo.push_back(*it); } llvm::errs() << "\n\n"; @@ -344,12 +679,12 @@ void IntervalAnalysis::runOnAllBlocks() { llvm::errs() << toString(system) << "\n"; system.indexMaxExpressions(); - DynamicMaxStrategy > strategy(system); - DynamicVariableAssignment > rho(system, strategy); + DynamicMaxStrategy strategy(system); + DynamicVariableAssignment rho(system, strategy); strategy.setRho(rho); for (unsigned int i = 0, size = system.variableCount(); i < size; ++i) { - Variable >& var = system.variable(i); + Variable& var = system.variable(i); llvm::errs() << toString(var.name()) << " = " << toString(rho[var]) << "\n"; } -- cgit v1.2.3