summaryrefslogtreecommitdiff
path: root/clang/include
diff options
context:
space:
mode:
Diffstat (limited to 'clang/include')
-rw-r--r--clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp99
-rw-r--r--clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp77
2 files changed, 134 insertions, 42 deletions
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp
index 57dcdeb..f4026dd 100644
--- a/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp
@@ -10,6 +10,9 @@ template<typename Domain>
struct MaxStrategy {
virtual ~MaxStrategy() { }
virtual unsigned int get(const MaxExpression<Domain>& e) const = 0;
+ virtual unsigned int get(const MaxExpression<Domain>& e) {
+ return const_cast<const MaxStrategy*>(this)->get(e);
+ }
};
unsigned int stack_depth = 1;
@@ -38,20 +41,38 @@ struct DynamicMaxStrategy : public MaxStrategy<Domain> {
_influence(system.maxExpressionCount(),
IdSet<MaxExpression<Domain> >(system.maxExpressionCount())),
_var_influence(system.variableCount(),
- IdSet<MaxExpression<Domain> >(system.maxExpressionCount()))
+ IdSet<MaxExpression<Domain> >(system.maxExpressionCount())),
+ _frozen(false)
{}
+ void freeze() {
+ _frozen = true;
+ }
+
+ void thaw() {
+ _frozen = false;
+ }
+
+ bool is_frozen() {
+ return _frozen;
+ }
+
void setRho(DynamicVariableAssignment<Domain>& rho) {
_rho = &rho;
}
unsigned int get(const MaxExpression<Domain>& e) const {
- solve(e);
return _values[e];
}
- void invalidate(const Variable<Domain>& v) const {
- solver_log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl;
+ unsigned int get(const MaxExpression<Domain>& e) {
+ if (!_frozen)
+ solve(e);
+ return _values[e];
+ }
+
+ void invalidate(const Variable<Domain>& v) {
+ log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl;
_stable.filter(_var_influence[v]);
IdSet<MaxExpression<Domain> > infl = _var_influence[v];
@@ -67,10 +88,10 @@ struct DynamicMaxStrategy : public MaxStrategy<Domain> {
}
private:
- void solve(const MaxExpression<Domain>& x) const {
+ void solve(const MaxExpression<Domain>& x) {
if (!_stable.contains(x)) {
_stable.insert(x);
- solver_log::strategy << indent() << "Stabilise " << x << std::endl;
+ log::strategy << indent() << "Stabilise " << x << std::endl;
stack_depth++;
unsigned int val = x.bestStrategy(DependencyAssignment(*this, *_rho, x),
@@ -78,7 +99,7 @@ private:
stack_depth--;
if (val != _values[x]) {
- solver_log::strategy << x << " => " << *x.arguments()[val] << std::endl;
+ log::strategy << x << " => " << *x.arguments()[val] << std::endl;
IdSet<MaxExpression<Domain> > oldInfluence = _influence[x];
_influence[x].clear();
@@ -96,15 +117,17 @@ private:
solve(_system.maxExpression(*it));
}
} else {
- solver_log::strategy << indent() << x << " did not change" << std::endl;
+ log::strategy << indent() << x << " did not change: "
+ << x << " => " << *x.arguments()[val] << std::endl;
}
} else {
- solver_log::strategy << indent() << x << " is stable" << std::endl;
+ log::strategy << indent() << x << " is stable: "
+ << x << " => " << *x.arguments()[_values[x]] << std::endl;
}
}
struct DependencyAssignment : public VariableAssignment<Domain>{
- DependencyAssignment(const DynamicMaxStrategy& strat,
+ DependencyAssignment(DynamicMaxStrategy& strat,
VariableAssignment<Domain>& rho,
const MaxExpression<Domain>& expr)
: _strat(strat),
@@ -116,13 +139,13 @@ private:
return _rho[var];
}
private:
- const DynamicMaxStrategy& _strat;
+ DynamicMaxStrategy& _strat;
VariableAssignment<Domain>& _rho;
const MaxExpression<Domain>& _expr;
};
struct DependencyStrategy : public MaxStrategy<Domain> {
- DependencyStrategy(const DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr)
+ DependencyStrategy(DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr)
: _strat(strat),
_expr(expr) {
}
@@ -134,19 +157,57 @@ private:
return _strat._values[e];
}
private:
- const DynamicMaxStrategy& _strat;
+ DynamicMaxStrategy& _strat;
const MaxExpression<Domain>& _expr;
};
-private:
+private:
const EquationSystem<Domain>& _system;
- mutable DynamicVariableAssignment<Domain>* _rho;
- mutable IdMap<MaxExpression<Domain>,unsigned int> _values;
- mutable IdSet<MaxExpression<Domain> > _stable;
- mutable IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain> > > _influence;
- mutable IdMap<Variable<Domain>,IdSet<MaxExpression<Domain> > > _var_influence;
+ DynamicVariableAssignment<Domain>* _rho;
+ IdMap<MaxExpression<Domain>,unsigned int> _values;
+ IdSet<MaxExpression<Domain> > _stable;
+ IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain> > > _influence;
+ IdMap<Variable<Domain>,IdSet<MaxExpression<Domain> > > _var_influence;
+ bool _frozen;
};
+
+template<typename T>
+IdMap<Variable<T>,T> solve_for(const EquationSystem<T>& system) {
+ IdMap<Variable<T>,T> result(system.variableCount(), infinity<T>());
+
+ DynamicMaxStrategy<T> strategy(system);
+ DynamicVariableAssignment<T> rho(system, strategy, -infinity<T>());
+ strategy.setRho(rho);
+
+ bool changed;
+ do {
+ changed = false;
+
+ // improve strategy
+ rho.freeze();
+ strategy.thaw();
+ for (unsigned int i = 0; i < system.variableCount(); ++i) {
+ strategy.get(*system[system.variable(i)]);
+ }
+
+ // iterate fixpoint
+ strategy.freeze();
+ rho.thaw();
+ for (unsigned int i = 0; i < system.variableCount(); ++i) {
+ Variable<T>& var = system.variable(i);
+ T val = rho[var];
+ if (result[var] != val) {
+ result[var] = val;
+ changed = true;
+ }
+ }
+ } while(changed);
+
+ return result;
+}
+
+
/*template<typename Domain>
std::ostream& operator<<(std::ostream& cout, const MaxStrategy<Domain>& strat) {
strat.print(cout);
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp
index ba5f650..2a63756 100644
--- a/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp
@@ -8,6 +8,9 @@ template<typename Domain>
struct VariableAssignment {
virtual ~VariableAssignment() { }
virtual const Domain& operator[](const Variable<Domain>&) const = 0;
+ virtual const Domain& operator[](const Variable<Domain>& x) {
+ return (*const_cast<const VariableAssignment*>(this))[x];
+ }
};
#include "EquationSystem.hpp"
@@ -19,46 +22,71 @@ template<typename Domain>
struct DynamicVariableAssignment : public VariableAssignment<Domain> {
DynamicVariableAssignment(
const EquationSystem<Domain>& system,
- const DynamicMaxStrategy<Domain>& strat
+ DynamicMaxStrategy<Domain>& strat,
+ const Domain& value=infinity<Domain>()
) : _system(system),
_strategy(strat),
- _values(system.variableCount(), infinity<Domain>()),
+ _values(system.variableCount(), value),
_stable(system.variableCount()),
_influence(system.variableCount(),
- IdSet<Variable<Domain> >(system.variableCount()))
+ IdSet<Variable<Domain> >(system.variableCount())),
+ _frozen(false)
{ }
+ void freeze() {
+ _frozen = true;
+ }
+
+ void thaw() {
+ _frozen = false;
+ }
+
+ bool is_frozen() {
+ return _frozen;
+ }
+
const Domain& operator[](const Variable<Domain>& var) const {
- solve(var);
return _values[var];
}
- void invalidate(const Variable<Domain>& x) const {
- solver_log::fixpoint << indent() << "Invalidating " << x << std::endl;
+ const Domain& operator[](const Variable<Domain>& var) {
+ if (!_frozen)
+ solve(var);
+ return _values[var];
+ }
+
+ void invalidate(const Variable<Domain>& x) {
+ log::fixpoint << indent() << "Invalidating " << x << std::endl;
if (_stable.contains(x)) {
_stable.remove(x);
_values[x] = infinity<Domain>();
-
- solve(x);
+
+ IdSet<Variable<Domain> > infl = _influence[x];
+ _influence[x].clear();
+ for (typename IdSet<Variable<Domain> >::iterator
+ it = infl.begin(),
+ ei = infl.end();
+ it != ei;
+ ++it) {
+ invalidate(_system.variable(*it));
+ }
}
}
private:
- void solve(const Variable<Domain>& x) const {
+ void solve(const Variable<Domain>& x) {
if (!_stable.contains(x)) {
_stable.insert(x);
- solver_log::fixpoint << indent() << "Stabilise " << x << std::endl;
+ log::fixpoint << indent() << "Stabilise " << x << std::endl;
stack_depth++;
- if (!_system[x])
- return;
- Domain val = _system[x]->evalWithStrat(DependencyAssignment(*this, x),
- _strategy);
+ Domain val = _system[x]->eval(DependencyAssignment(*this, x),
+ _strategy);
stack_depth--;
if (val != _values[x]) {
- solver_log::fixpoint << x << " = " << val << std::endl;
+ log::fixpoint << x << " = " << val << std::endl;
IdSet<Variable<Domain> > oldInfluence = _influence[x];
_influence[x].clear();
@@ -74,15 +102,17 @@ private:
solve(_system.variable(*it));
}
} else {
- solver_log::fixpoint << indent() << x << " did not change" << std::endl;
+ log::fixpoint << indent() << x << " did not change: "
+ << x << " = " << val << std::endl;
}
} else {
- solver_log::fixpoint << indent() << x << " is stable" << std::endl;
+ log::fixpoint << indent() << x << " is stable: "
+ << x << " = " << _values[x] << std::endl;
}
}
struct DependencyAssignment : public VariableAssignment<Domain> {
- DependencyAssignment(const DynamicVariableAssignment& assignment, const Variable<Domain>& var)
+ DependencyAssignment(DynamicVariableAssignment& assignment, const Variable<Domain>& var)
: _assignment(assignment), _var(var) { }
const Domain& operator[](const Variable<Domain>& x) const {
const Domain& result = _assignment[x];
@@ -90,15 +120,16 @@ private:
return result;
}
private:
- const DynamicVariableAssignment& _assignment;
+ DynamicVariableAssignment& _assignment;
const Variable<Domain>& _var;
};
const EquationSystem<Domain>& _system;
- const DynamicMaxStrategy<Domain>& _strategy;
- mutable IdMap<Variable<Domain>, Domain> _values;
- mutable IdSet<Variable<Domain> > _stable;
- mutable IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence;
+ DynamicMaxStrategy<Domain>& _strategy;
+ IdMap<Variable<Domain>, Domain> _values;
+ IdSet<Variable<Domain> > _stable;
+ IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence;
+ bool _frozen;
};
#endif
generated by cgit v1.2.3 (git 2.46.2) at 2024-12-26 20:19:25 +0000