From 1e907d883191571b5c374fd1c3b2f6c1fe11da83 Mon Sep 17 00:00:00 2001 From: "Zancanaro; Carlo" Date: Thu, 8 Nov 2012 19:37:59 +1100 Subject: A few fixes to the MCF solver, and equation stuff General work on the equation systems. Trying to get them to generate correctly with the MCF stuff. It's harder than it seems! --- clang/lib/Analysis/Interval.cpp | 163 +++++++++++++++++++++++++++++++++------- 1 file changed, 136 insertions(+), 27 deletions(-) (limited to 'clang/lib/Analysis/Interval.cpp') diff --git a/clang/lib/Analysis/Interval.cpp b/clang/lib/Analysis/Interval.cpp index 7096d75..e643f5e 100644 --- a/clang/lib/Analysis/Interval.cpp +++ b/clang/lib/Analysis/Interval.cpp @@ -8,6 +8,8 @@ #include "clang/Analysis/Analyses/IntervalSolver/Complete.hpp" #include "clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp" #include "clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp" + +#include "MCFSimplex.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/DenseMap.h" @@ -41,6 +43,11 @@ 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::pair >*, V>& v) { + cout << "(" << v.first->name() << ", " << v.second << ")"; + return cout; +} template std::ostream& operator<<(std::ostream& cout, const std::vector& v) { @@ -485,6 +492,86 @@ Condition fromComparison(const BinaryOperator* op, bool negate) { return cond; } + +struct MinCostFlow : public Operator { + MinCostFlow(const std::vector >& supplies) + : solver(0, 0) { + assert(supplies.size() % 2 == 0); + + if (supplies.size() == 0) + return; + + MCFClass::FNumber* deficits = new MCFClass::FNumber[supplies.size()]; + MCFClass::Index* starts = new MCFClass::Index[supplies.size()]; + MCFClass::Index* ends = new MCFClass::Index[supplies.size()]; + + for (int i = 0, size = supplies.size(); i < size; i += 2) { + deficits[i] = -supplies[i].second.as(); + deficits[i+1] = -supplies[i+1].second.as(); + + starts[i] = i+1; + ends[i] = i+2; + + starts[i+1] = i+2; + ends[i+1] = i+1; + + printableSupply.push_back(supplies[i].second); + printableSupply.push_back(supplies[i+1].second); + } + + solver.LoadNet(supplies.size(), supplies.size(), // max nodes/arcs + supplies.size(), supplies.size(), // current nodes/arcs + NULL, NULL, // arcs have inf cap, zero cost (to begin) + deficits, // deficits for each node + starts, ends); // start/end of each edge + + delete[] deficits; + delete[] starts; + delete[] ends; + } + + ZBar eval(const std::vector& args) const { + if (args.size() == 0) + return 0; + for (int i = 0, size = args.size(); i < size; ++i) { + //if (args[i] == infinity()) { + // if (!solver.IsClosedArc(i)) + // solver.CloseArc(i); + //} else { + // if (solver.IsClosedArc(i)) + // solver.OpenArc(i); + solver.ChgCost(i, args[i].as()); + //} + } + std::cerr << "MCF" << this << "<" << printableSupply << ">(" << args << ")" << " = "; + solver.SolveMCF(); + if (solver.MCFGetStatus() == MCFClass::kUnfeasible){ + std::cerr << -infinity() << std::endl; + return -infinity(); + } else { + if (solver.MCFGetFO() == MCFClass::Inf()) { + std::cerr << infinity() << std::endl; + return infinity(); + } else if (solver.MCFGetFO() == -MCFClass::Inf()) { + std::cerr << -infinity() << std::endl; + return -infinity(); + } else { + ZBar result = solver.MCFGetFO(); + std::cerr << result << std::endl; + return result; + } + } + } + + virtual void print(std::ostream& cout) const { + cout << "MCF" << this << "<" << printableSupply << ">"; + } + + mutable MCFSimplex solver; + std::vector printableSupply; +}; + + /* Blocks */ typedef std::map Counters; @@ -551,28 +638,41 @@ void runOnBlock(const CFGBlock* block, EqnSys& system, BlockVars& block_vars) { 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 additionArgs; - additionArgs.push_back(expression); - - if (it->second == 1) { - additionArgs.push_back(vars[it->first]); - } else { - std::vector multiplicationArgs; - multiplicationArgs.push_back(vars[it->first]); - multiplicationArgs.push_back(&system.constant(it->second)); - additionArgs.push_back(&system.expression(new Multiplication(), multiplicationArgs)); - } - expression = &system.expression(new Addition(), additionArgs); + EqnExpr* expression; + + if (result.first.size() > 0) { + // set up the min-cost stuff + std::vector minCostArgs; + std::vector > varCosts; + 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"); + + EqnVar& var = *vars[it->first]; + EqnVar& negVar = *vars[negate_string(it->first)]; + + varCosts.push_back(std::pair(&var, it->second)); + varCosts.push_back(std::pair(&negVar, -it->second)); + + minCostArgs.push_back(&var); + minCostArgs.push_back(&negVar); + } + EqnExpr* minCostExpr = &system.expression(new MinCostFlow(varCosts), minCostArgs); + + // add the constant factor to the min-cost bit + std::vector additionArgs; + additionArgs.push_back(&system.constant(result.second)); + additionArgs.push_back(minCostExpr); + expression = &system.expression(new Addition(), additionArgs); + } else { + expression = &system.constant(result.second); } - + + // max(-inf, expr), so strategy iteration will work std::vector maxArgs; maxArgs.push_back(&system.constant(-infinity())); maxArgs.push_back(expression); @@ -612,6 +712,7 @@ void runOnBlock(const CFGBlock* block, EqnSys& system, BlockVars& block_vars) { EqnExpr* expr = NULL; if (val == -infinity()) { // don't do anything here: min(-inf, x) = -inf (for all x) + expr = &system.constant(-infinity()); } else if (val == infinity()) { // no need to have a min here: min(inf, x) = x (for all x) expr = jt->second; @@ -623,7 +724,9 @@ void runOnBlock(const CFGBlock* block, EqnSys& system, BlockVars& block_vars) { expr = &system.expression(new Minimum(), minArgs); } - if (expr) { + system[*var]->arguments().push_back(expr); + + /*if (expr) { std::set ignore; for (VarMap::iterator variables = vars.begin(), @@ -638,10 +741,13 @@ void runOnBlock(const CFGBlock* block, EqnSys& system, BlockVars& block_vars) { for (int negate = 0; negate < 2; ++negate) { std::string var_name = negate ? negate_string(variables->first) : variables->first; if (cond[var_name] == infinity()) { + // min(x, inf) = x plusArgs.push_back(vars[var_name]); } else if (cond[var_name] == -infinity()) { + // min(x, -inf) = -inf plusArgs.push_back(&system.constant(-infinity())); } else { + // min(x, y) = ? std::vector minArgs; minArgs.push_back(vars[var_name]); minArgs.push_back(&system.constant(cond[var_name])); @@ -656,7 +762,7 @@ void runOnBlock(const CFGBlock* block, EqnSys& system, BlockVars& block_vars) { expr = &system.expression(new Guard(), guard_args); } system[*var]->arguments().push_back(expr); - } + }*/ } } } @@ -683,6 +789,7 @@ void IntervalAnalysis::runOnAllBlocks(const Decl& decl) { BlockVars block_vars; std::vector infArg; + infArg.push_back(&system.constant(-infinity())); // left-most argument has to be -infinity infArg.push_back(&system.constant(infinity())); std::set& function_arguments = block_vars[&cfg->getEntry()]; std::string block_id = toString(cfg->getEntry().getBlockID()); @@ -690,11 +797,13 @@ void IntervalAnalysis::runOnAllBlocks(const Decl& decl) { for (unsigned int i = func->getNumParams(); i > 0; i--) { std::string name = func->getParamDecl(i-1)->getNameAsString(); - function_arguments.insert(name); // add it to the first block's vars - function_arguments.insert(negate_string(name)); // add it to the first block's vars - - system[system.variable(name + '-' + block_id + "-pre")] = &system.maxExpression(infArg); // set the vars to infinity in the system here - system[system.variable(negate_string(name) + '-' + block_id + "-pre")] = &system.maxExpression(infArg); // set the vars to infinity in the system here + // add the variables to the first block + function_arguments.insert(name); + function_arguments.insert(negate_string(name)); + + // set the vars to infinity (unconstrained) + system[system.variable(name + '-' + block_id + "-pre")] = &system.maxExpression(infArg); + system[system.variable(negate_string(name) + '-' + block_id + "-pre")] = &system.maxExpression(infArg); } } -- cgit v1.2.3