sgatev accepted this revision. sgatev added inline comments.
================ Comment at: clang/unittests/Analysis/FlowSensitive/MultiVarConstantPropagationTest.cpp:171-173 + Vars[Var] = (E->EvaluateAsInt(R, Context) && R.Val.isInt()) + ? ValueLattice(R.Val.getInt().getExtValue()) + : ValueLattice::top(); ---------------- ymandel wrote: > sgatev wrote: > > I think this makes the transfer function non-monotonic. Concretely, > > `Vars[var]` can be `top` and the right-hand side can be something else. The > > transfer function must be monotonic to guarantee termination. Perhaps this > > should be `Vars[Var].join(...)`? > Keep in mind that CP analysis is not looking at a variable's value *over the > course of program*, but only *at each program point*. If we wanted to know > whether a variable could be replaced entirely with a constant, then we'd need > the former, in which case you'd be right that join would be correct here. > > To the more general point: monotonic means something more subtle. > Specifically, it doesn't relate inputs to outputs, but input-output pairs to > each other. Specifically, for monotinically increasing functions `f`: > ``` > if a <= b then f(a) <= f(b) > ``` > In this case, no matter the inputs to f, the output is a constant (the value > of the expression at that point or `top`), which trivially satisfies the > requirement `f(a) <= f(b)`. > > Intuitively, transfer functions model program behavior, so indeed it would be > odd to enforce that `x <= f(x)`. Assignment is a good example -- at that > program point, we know *exactly* the value of the variable, no matter what it > held before. > > Agreed about the distinction in the type of analysis. What I meant is that `ConstantPropagationAnalysis::transfer` isn't monotonic because it could happen that `transfer(top, ...) = 1` and `transfer(1, ...) = top`. However, I think this isn't important. What's important is that `transferBlock` is monotonic which I think is the case for `ConstantPropagationAnalysis`. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D116370/new/ https://reviews.llvm.org/D116370 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
