sgatev marked an inline comment as done.
sgatev added inline comments.
================
Comment at: clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp:49
+ // in tests.
+ std::set<const CFGBlock *> Preds;
Preds.insert(Block.pred_begin(), Block.pred_end());
----------------
xazax.hun wrote:
> sgatev wrote:
> > xazax.hun wrote:
> > > sgatev wrote:
> > > > xazax.hun wrote:
> > > > > xazax.hun wrote:
> > > > > > Are we sure that the memory addresses of CFGBlocks are stable
> > > > > > enough for a deterministic order? Alternatively, we could use the
> > > > > > block ids for the ordering.
> > > > > Also, could you describe where the flakiness is originated from?
> > > > > Naively, I'd expect that the order in which we process the
> > > > > predecessors should not change the results of the analysis.
> > > > You're right, using block ids for ordering is better. I updated the
> > > > code.
> > > >
> > > > > Also, could you describe where the flakiness is originated from?
> > > >
> > > > Say we have a block `B1` with predecessors `B2` and `B3`. Let the
> > > > environment of `B2` after evaluating all of its statements is `B2Env =
> > > > { Expr1 -> Loc1 }` and the environment of `B3` after evaluating all of
> > > > its statement is `B3Env = { Expr2 -> Loc2 }` where `ExprX -> LocX`
> > > > refers to a particular mapping of storage locations to expressions.
> > > >
> > > > What we want for the input environment of `B1` is `{}` because `B2Env`
> > > > and `B3Env` do not contain common assignments of storage locations to
> > > > expressions. What we got before this patch is either `B2Env.join(B3Env)
> > > > = { Expr1 -> Loc1 }` or `B3Env.join(B2Env) = { Expr2 -> Loc2 }`.
> > > >
> > > > Without deterministic ordering of predecessors the test that I'm
> > > > introducing in this patch is flaky.
> > > > What we got before this patch is either B2Env.join(B3Env) = { Expr1 ->
> > > > Loc1 } or B3Env.join(B2Env) = { Expr2 -> Loc2 }.
> > >
> > > I think I'm still missing something. With this patch, wouldn't both
> > > B2Env.join(B3Env) and B3Env.join(B2Env) produce the empty environment? If
> > > that is the case, do we still care about a deterministic order?
> > >
> > >
> > >
> > That's right. With the patch in `DataflowEnvironment.cpp` the particular
> > order of predecessors doesn't affect the result. However, one of the
> > properties that I'm looking for in tests is being able to remove
> > functionality from the code and have the tests that exercise this
> > functionality fail. This won't necessarily be the case here if the order
> > wasn't deterministic. I don't have a strong preference so please let me
> > know if you have concerns about it. I should also note that we expect all
> > of this to be removed once temporary destructors are handled better in the
> > CFG.
> Strictly speaking, making this deterministic is not a requirement, it should
> not have any observable effect for the end user. On the other hand, we could
> think of this non-determinism as a feature. A well behaved analysis should
> produce the same answer regardless of the order in which we process the
> nodes. (This requirement follows from the algebraic properties of the join
> operation.) So in the future I would even anticipate a feature that
> deliberately randomize the order to ensure that the clients are well behaved.
>
> I think eliminating this non-determinism could potentially mask bugs in the
> future and also it requires extra code. I think I prefer the original version
> until we see some evidence that determinism is desired.
Sure. Reverted that part.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D117754/new/
https://reviews.llvm.org/D117754
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
