summaryrefslogtreecommitdiff
path: root/clang/include/clang
diff options
context:
space:
mode:
Diffstat (limited to 'clang/include/clang')
-rw-r--r--clang/include/clang/Analysis/Analyses/IntervalSolver/Complete.hpp8
-rw-r--r--clang/include/clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp12
-rw-r--r--clang/include/clang/Analysis/Analyses/IntervalSolver/Log.hpp6
-rw-r--r--clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp82
-rw-r--r--clang/include/clang/Analysis/Analyses/IntervalSolver/Operator.hpp82
-rw-r--r--clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp34
6 files changed, 143 insertions, 81 deletions
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/Complete.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/Complete.hpp
index 664d71f..73c8f23 100644
--- a/clang/include/clang/Analysis/Analyses/IntervalSolver/Complete.hpp
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/Complete.hpp
@@ -4,9 +4,15 @@
#include <cassert>
#include <ostream>
#include <istream>
+#include <limits>
template<typename T>
-T infinity() { }
+T infinity();
+
+template<>
+double infinity() {
+ return std::numeric_limits<double>::infinity();
+}
template<typename T>
struct Complete {
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp
index 5ee5405..3342cc7 100644
--- a/clang/include/clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp
@@ -76,14 +76,9 @@ struct EquationSystem {
}
Constant<Domain>& constant(const Domain& value) {
- if (_constants.find(value) == _constants.end()) {
- Constant<Domain>* constant = new Constant<Domain>(value);
- _expressions.insert(constant);
- _constants[value] = constant;
- return *constant;
- } else {
- return *_constants[value];
- }
+ Constant<Domain>* constant = new Constant<Domain>(value);
+ _expressions.insert(constant);
+ return *constant;
}
MaxExpression<Domain>* operator[](const Variable<Domain>& var) const {
@@ -132,7 +127,6 @@ struct EquationSystem {
private:
std::set<Operator<Domain>*> _operators;
std::set<Expression<Domain>*> _expressions;
- std::map<Domain,Constant<Domain>*> _constants;
std::vector<Variable<Domain>*> _variables;
std::map<std::string, Variable<Domain>*> _variable_names;
IdMap<MaxExpression<Domain>, Variable<Domain>*>* _expr_to_var;
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/Log.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/Log.hpp
index 90ab7e5..7502ac8 100644
--- a/clang/include/clang/Analysis/Analyses/IntervalSolver/Log.hpp
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/Log.hpp
@@ -1,17 +1,13 @@
#ifndef LOG_HPP
#define LOG_HPP
-// could not be hackier, but C++ is annoying
-#define protected public
-#include <streambuf>
-#undef protected
-
#include <string>
#include <iostream>
#include <map>
#include <cstdio>
namespace solver_log {
+
struct Logger : public std::ostream {
Logger(std::streambuf* buffer, const std::string& name)
: std::ostream(NULL) { }
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp
index 9ae7394..da05dd8 100644
--- a/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp
@@ -39,22 +39,13 @@ struct DynamicMaxStrategy : public MaxStrategy<Domain> {
_values(system.maxExpressionCount(), 0),
_stable(system.maxExpressionCount()),
_influence(system.maxExpressionCount(),
- IdSet<MaxExpression<Domain> >(system.maxExpressionCount())),
- _changed(false)
+ IdSet<MaxExpression<Domain> >(system.maxExpressionCount()))
{}
void setRho(DynamicVariableAssignment<Domain>& rho) {
_rho = &rho;
}
- void hasChanged(bool c) {
- _changed = c;
- }
-
- bool hasChanged() const {
- return _changed;
- }
-
unsigned int get(const MaxExpression<Domain>& e) const {
solver_log::strategy << indent() << "Look up " << e << std::endl;
return _values[e];
@@ -66,19 +57,6 @@ struct DynamicMaxStrategy : public MaxStrategy<Domain> {
return _values[e];
}
- void invalidate(const Variable<Domain>& v) {
- solver_log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl;
-
- IdSet<MaxExpression<Domain> > infl = _influence[*_system[v]];
- for (typename IdSet<MaxExpression<Domain> >::iterator
- it = infl.begin(),
- end = infl.end();
- it != end;
- ++it) {
- invalidate(_system.maxExpression(*it));
- }
- }
-
void invalidate(const MaxExpression<Domain>& v) {
if (_stable.contains(v)) {
solver_log::strategy << indent() << "Invalidating " << v << std::endl;
@@ -111,20 +89,18 @@ private:
if (val != _values[x]) {
solver_log::strategy << x << " => " << *x.arguments()[val] << std::endl;
- IdSet<MaxExpression<Domain> > oldInfluence = _influence[x];
- //_influence[x].clear();
_values[x] = val;
- _changed = true;
_rho->invalidate(*_system.varFromExpr(x));
//_rho->stabilise();
- _stable.filter(oldInfluence);
-
+ IdSet<MaxExpression<Domain> > infl = _influence[x];
+ _stable.filter(infl);
+
for (typename IdSet<MaxExpression<Domain> >::iterator
- it = oldInfluence.begin(),
- end = oldInfluence.end();
+ it = infl.begin(),
+ end = infl.end();
it != end;
++it) {
solve(_system.maxExpression(*it));
@@ -141,7 +117,7 @@ private:
struct DependencyAssignment : public VariableAssignment<Domain>{
DependencyAssignment(DynamicMaxStrategy& strat,
- VariableAssignment<Domain>& rho,
+ DynamicVariableAssignment<Domain>& rho,
const MaxExpression<Domain>& expr)
: _strat(strat),
_rho(rho),
@@ -149,14 +125,25 @@ private:
_current(strat._system.variableCount()) {
}
const Domain operator[](const Variable<Domain>& var) {
- // solve the strategy for this variable, too
- _strat.solve(*_strat._system[var]);
+ // force evaluation to get touched variables
+ Domain value = _rho[var];
+
_strat._influence[*_strat._system[var]].insert(_expr);
- return _rho[var];
+
+ // invalidate touched variables
+ IdSet<Variable<Domain> > changed = _rho.get_changed();
+ for (typename IdSet<Variable<Domain> >::iterator
+ it = changed.begin(),
+ ei = changed.end();
+ it != ei;
+ ++it) {
+ _strat.invalidate(*_strat._system[_strat._system.variable(*it)]);
+ }
+ return value;
}
private:
DynamicMaxStrategy& _strat;
- VariableAssignment<Domain>& _rho;
+ DynamicVariableAssignment<Domain>& _rho;
const MaxExpression<Domain>& _expr;
IdSet<Variable<Domain> > _current;
};
@@ -186,7 +173,6 @@ private:
IdMap<MaxExpression<Domain>,unsigned int> _values;
IdSet<MaxExpression<Domain> > _stable;
IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain> > > _influence;
- bool _changed;
};
@@ -200,28 +186,12 @@ struct Solver {
}
Domain solve(Variable<Domain>& var) {
- MaxExpression<Domain>& rhs = *_system[var];
-
- // _rho automatically keeps up to date with changes made to the
- // strategy, so you don't need to stabilise it
-
+ MaxExpression<Domain>& rhs = *_system[var];
+ // this will automatically work sufficiently to get the final
+ // strategy for this variable's RHS
_strategy.get(rhs);
-
- /*
- do {
- _strategy.hasChanged(false);
-
- solver_log::debug << "Stabilise assignment (toplevel)" << std::endl;
- _rho.stabilise();
-
- solver_log::debug << "Improve strategy (toplevel)" << std::endl;
- // improve strategy
- _strategy.get(rhs);
- solver_log::debug << (_strategy.hasChanged() ? "Strategy has changed - loop again" : "Strategy has not changed - terminate") << std::endl;
- } while (_strategy.hasChanged());
- */
-
+ // this will automatically solve for the value of the RHS, if required
return _rho[var];
}
private:
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/Operator.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/Operator.hpp
index 64ef096..0b08866 100644
--- a/clang/include/clang/Analysis/Analyses/IntervalSolver/Operator.hpp
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/Operator.hpp
@@ -135,6 +135,88 @@ struct Guard : public Operator<Domain> {
}
};
+#include "MCFSimplex.h"
+
+template<typename Domain>
+struct MinCostFlow : public Operator<Domain> {
+ MinCostFlow(const std::vector<Domain>& supplies, const std::vector<std::pair<int,int> > arcs)
+ : _supplies(supplies), _arcs(arcs), _solver(0,0) {
+ MCFClass::FNumber* deficits = new MCFClass::FNumber[supplies.size()];
+ MCFClass::Index* starts = new MCFClass::Index[arcs.size()];
+ MCFClass::Index* ends = new MCFClass::Index[arcs.size()];
+
+ for (int i = 0, size = supplies.size(); i < size; ++i) {
+ deficits[i] = -supplies[i].template as<MCFClass::FNumber>();
+ }
+ for (int i = 0, size = arcs.size(); i < size; ++i) {
+ starts[i] = arcs[i].first;
+ ends[i] = arcs[i].second;
+ }
+
+ _solver.LoadNet(supplies.size(), arcs.size(), // max nodes/arcs
+ supplies.size(), arcs.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;
+ }
+ Domain eval (const std::vector<Domain>& costs) const {
+ assert(costs.size() == _arcs.size());
+ if (costs.size() == 0)
+ return 0;
+ for (int i = 0, size = costs.size(); i < size; ++i) {
+ _solver.ChgCost(i, costs[i].template as<MCFClass::CNumber>());
+ }
+ _solver.SolveMCF();
+ if (_solver.MCFGetStatus() == MCFClass::kUnfeasible){
+ return -infinity<Domain>();
+ } else if (_solver.MCFGetFO() == MCFClass::Inf<MCFClass::FONumber>()) {
+ return infinity<Domain>();
+ } else if (_solver.MCFGetFO() == -MCFClass::Inf<MCFClass::FONumber>()) {
+ return -infinity<Domain>();
+ } else {
+ return _solver.MCFGetFO();
+ }
+ }
+ void print(std::ostream& cout) const {
+ std::string supplyString = "[";
+ for (int i = 0, size = _supplies.size(); i < size; ++i) {
+ if (i > 0)
+ supplyString += ",";
+ std::stringstream stream;
+ stream << _supplies[i];
+ supplyString += stream.str();
+ }
+ supplyString += ']';
+
+ std::string arcString = "[";
+ for (int i = 0, size = _arcs.size(); i < size; ++i) {
+ if (i > 0)
+ arcString += ",";
+ {
+ std::stringstream stream;
+ stream << _arcs[i].first;
+ arcString += stream.str() + ":";
+ }
+ {
+ std::stringstream stream;
+ stream << _arcs[i].second;
+ arcString += stream.str();
+ }
+ }
+ arcString += ']';
+
+ cout << "MCF<" << supplyString << "," << arcString << ">";
+ }
+private:
+ std::vector<Domain> _supplies;
+ std::vector<std::pair<int,int> > _arcs;
+ mutable MCFSimplex _solver;
+};
+
/*#include "TemplateConstraintMatrix.hpp"
template<typename Domain>
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp
index 746e5ef..4c4519a 100644
--- a/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp
@@ -24,9 +24,11 @@ struct DynamicVariableAssignment : public VariableAssignment<Domain> {
) : _system(system),
_strategy(strat),
_values(system.variableCount(), value),
+ _old_values(system.variableCount(), value),
_unstable(system.variableCount()),
_influence(system.variableCount(),
- IdSet<Variable<Domain> >(system.variableCount()))
+ IdSet<Variable<Domain> >(system.variableCount())),
+ _touched(system.variableCount())
{ }
const Domain operator[](const Variable<Domain>& var) {
@@ -34,18 +36,13 @@ struct DynamicVariableAssignment : public VariableAssignment<Domain> {
return _values[var];
}
- /*void stabilise() {
- if (!_unstable.empty()) {
- Variable<Domain>& var = _system.variable(*_unstable.begin());
- solve(var);
- }
- }*/
-
void invalidate(const Variable<Domain>& x) {
if (!_unstable.contains(x)) {
solver_log::fixpoint << indent() << "Invalidating " << x << std::endl;
_unstable.insert(x);
+ _touched.insert(x);
+ _old_values[x] = _values[x];
_values[x] = infinity<Domain>();
IdSet<Variable<Domain> > infl = _influence[x];
@@ -61,6 +58,23 @@ struct DynamicVariableAssignment : public VariableAssignment<Domain> {
}
}
+ IdSet<Variable<Domain> > get_changed() {
+ IdSet<Variable<Domain> > changed;
+ for (typename IdSet<Variable<Domain> >::iterator
+ it = _touched.begin(),
+ ei = _touched.end();
+ it != ei;
+ ++it) {
+ Variable<Domain>& var = _system.variable(*it);
+ if (!_unstable.contains(var) && _old_values[var] != _values[var]) {
+ changed.insert(var);
+ _touched.remove(var);
+ }
+ }
+ //_touched.clear();
+ return changed;
+ }
+
private:
void solve(const Variable<Domain>& x) {
@@ -79,8 +93,6 @@ private:
if (val != _values[x]) {
solver_log::fixpoint << x << " = " << val << std::endl;
- _strategy.invalidate(x);
-
IdSet<Variable<Domain> > oldInfluence = _influence[x];
_influence[x].clear();
_values[x] = val;
@@ -118,8 +130,10 @@ private:
const EquationSystem<Domain>& _system;
DynamicMaxStrategy<Domain>& _strategy;
IdMap<Variable<Domain>, Domain> _values;
+ IdMap<Variable<Domain>, Domain> _old_values;
IdSet<Variable<Domain> > _unstable;
IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence;
+ IdSet<Variable<Domain> > _touched;
};
#endif
generated by cgit v1.2.3 (git 2.46.2) at 2024-12-25 06:56:43 +0000