Reapply "[dataflow] use true/false literals in formulas, rather than variables"

This reverts commit 3353f7dd3d91c9b2b6a15ba9229bee53e0cb8196.

Fixed test bug (unspecified order of arg evaluation)

Revert "[dataflow] use true/false literals in formulas, rather than variables"

This reverts commit 36bd5bd888f193b70abf43a09bb4fc04cd2a2ff1.

This change is causing a test failure on several build b

Revert "[dataflow] use true/false literals in formulas, rather than variables"

This reverts commit 36bd5bd888f193b70abf43a09bb4fc04cd2a2ff1.

This change is causing a test failure on several build bots:
- https://lab.llvm.org/buildbot/#/builders/139/builds/50255
- https://lab.llvm.org/buildbot/#/builders/216/builds/27735
- https://lab.llvm.org/buildbot/#/builders/247/builds/9334

show more ...

[dataflow] use true/false literals in formulas, rather than variables

And simplify formulas containing true/false
It's unclear to me how useful this is, it does make formulas more
conveniently self-

[dataflow] use true/false literals in formulas, rather than variables

And simplify formulas containing true/false
It's unclear to me how useful this is, it does make formulas more
conveniently self-contained now (we can usefully print them without
carrying around the "true/false" labels)

(while here, simplify !!X to X, too)

Differential Revision: https://reviews.llvm.org/D153485

show more ...

[dataflow] Parse formulas from text (#66424)

My immediate use for this is not in checked-in code, but rather the
ability to plug printed flow conditions (from analysis logs) back into
sat solver u

[dataflow] Parse formulas from text (#66424)

My immediate use for this is not in checked-in code, but rather the
ability to plug printed flow conditions (from analysis logs) back into
sat solver unittests to reproduce slowness.

It does allow simplifying some of the existing solver tests, though.

show more ...

Reland "[dataflow] Add dedicated representation of boolean formulas"

This reverts commit 7a72ce98224be76d9328e65eee472381f7c8e7fe.

Test problems were due to unspecified order of function arg evalua

Reland "[dataflow] Add dedicated representation of boolean formulas"

This reverts commit 7a72ce98224be76d9328e65eee472381f7c8e7fe.

Test problems were due to unspecified order of function arg evaluation.

Reland "[dataflow] Replace most BoolValue subclasses with references to Formula (and AtomicBoolValue => Atom and BoolValue => Formula where appropriate)"

This properly frees the Value hierarchy from managing boolean formulas.

We still distinguish AtomicBoolValue; this type is used in client code.
However we expect to convert such uses to BoolValue (where the
distinction is not needed) or Atom (where atomic identity is intended),
and then fold AtomicBoolValue into FormulaBoolValue.

We also distinguish TopBoolValue; this has distinct rules for
widen/join/equivalence, and top-ness is not represented in Formula.
It'd be nice to find a cleaner representation (e.g. the absence of a
formula), but no immediate plans.

For now, BoolValues with the same Formula are deduplicated. This doesn't
seem desirable, as Values are mutable by their creators (properties).
We can probably drop this for FormulaBoolValue immediately (not in this
patch, to isolate changes). For AtomicBoolValue we first need to update
clients to stop using value pointers for atom identity.

The data structures around flow conditions are updated:
- flow condition tokens are Atom, rather than AtomicBoolValue*
- conditions are Formula, rather than BoolValue
Most APIs were changed directly, some with many clients had a
new version added and the existing one deprecated.

The factories for BoolValues in Environment keep their existing
signatures for now (e.g. makeOr(BoolValue, BoolValue) => BoolValue)
and are not deprecated. These have very many clients and finding the
most ergonomic API & migration path still needs some thought.

Differential Revision: https://reviews.llvm.org/D153469

show more ...

Revert "Reland "[dataflow] Add dedicated representation of boolean formulas" and followups

These changes are OK, but they break downstream stuff that needs more time to adapt :-(

This reverts commi

Revert "Reland "[dataflow] Add dedicated representation of boolean formulas" and followups

These changes are OK, but they break downstream stuff that needs more time to adapt :-(

This reverts commit 71579569f4399d3cf6bc618dcd449b5388d749cc.
This reverts commit 5e4ad816bf100b0325ed45ab1cfea18deb3ab3d1.
This reverts commit 1c3ac8dfa16c42a631968aadd0396cfe7f7778e0.

show more ...

[dataflow] use true/false literals in formulas, rather than variables

And simplify formulas containing true/false
It's unclear to me how useful this is, it does make formulas more
conveniently self-

[dataflow] use true/false literals in formulas, rather than variables

And simplify formulas containing true/false
It's unclear to me how useful this is, it does make formulas more
conveniently self-contained now (we can usefully print them without
carrying around the "true/false" labels)

(while here, simplify !!X to X, too)

Differential Revision: https://reviews.llvm.org/D153485

show more ...

[dataflow] Replace most BoolValue subclasses with references to Formula (and AtomicBoolValue => Atom and BoolValue => Formula where appropriate)

This properly frees the Value hierarchy from managing

[dataflow] Replace most BoolValue subclasses with references to Formula (and AtomicBoolValue => Atom and BoolValue => Formula where appropriate)

This properly frees the Value hierarchy from managing boolean formulas.

We still distinguish AtomicBoolValue; this type is used in client code.
However we expect to convert such uses to BoolValue (where the
distinction is not needed) or Atom (where atomic identity is intended),
and then fold AtomicBoolValue into FormulaBoolValue.

We also distinguish TopBoolValue; this has distinct rules for
widen/join/equivalence, and top-ness is not represented in Formula.
It'd be nice to find a cleaner representation (e.g. the absence of a
formula), but no immediate plans.

For now, BoolValues with the same Formula are deduplicated. This doesn't
seem desirable, as Values are mutable by their creators (properties).
We can probably drop this for FormulaBoolValue immediately (not in this
patch, to isolate changes). For AtomicBoolValue we first need to update
clients to stop using value pointers for atom identity.

The data structures around flow conditions are updated:
- flow condition tokens are Atom, rather than AtomicBoolValue*
- conditions are Formula, rather than BoolValue
Most APIs were changed directly, some with many clients had a
new version added and the existing one deprecated.

The factories for BoolValues in Environment keep their existing
signatures for now (e.g. makeOr(BoolValue, BoolValue) => BoolValue)
and are not deprecated. These have very many clients and finding the
most ergonomic API & migration path still needs some thought.

Differential Revision: https://reviews.llvm.org/D153469

show more ...

Reland "[dataflow] Add dedicated representation of boolean formulas"

This reverts commit 7a72ce98224be76d9328e65eee472381f7c8e7fe.

Test problems were due to unspecified order of function arg evalua

Reland "[dataflow] Add dedicated representation of boolean formulas"

This reverts commit 7a72ce98224be76d9328e65eee472381f7c8e7fe.

Test problems were due to unspecified order of function arg evaluation.

show more ...

Revert "[dataflow] Add dedicated representation of boolean formulas"

This reverts commit 2fd614efc1bb9c27f1bc6c3096c60a7fe121e274.

Commit caused failures on the following two build bots:
http://4

Revert "[dataflow] Add dedicated representation of boolean formulas"

This reverts commit 2fd614efc1bb9c27f1bc6c3096c60a7fe121e274.

Commit caused failures on the following two build bots:
http://45.33.8.238/win/80815/step_7.txt
https://lab.llvm.org/buildbot/#/builders/139/builds/44269

show more ...

[dataflow] Add dedicated representation of boolean formulas

This is the first step in untangling the two current jobs of BoolValue.

=== Desired end-state: ===

- BoolValue will model C++ booleans e

[dataflow] Add dedicated representation of boolean formulas

This is the first step in untangling the two current jobs of BoolValue.

=== Desired end-state: ===

- BoolValue will model C++ booleans e.g. held in StorageLocations.
this includes describing uncertainty (e.g. "top" is a Value concern)
- Formula describes analysis-level assertions in terms of SAT atoms.

These can still be linked together: a BoolValue may have a corresponding
SAT atom which is constrained by formulas.

=== Done in this patch: ===

BoolValue is left intact, Formula is just the input type to the
SAT solver, and we build formulas as needed to invoke the solver.

=== Incidental changes to debug string printing: ===

- variables renamed from B0 etc to V0 etc
B0 collides with the names of basic blocks, which is confusing when
debugging flow conditions.
- debug printing of formulas (Formula and Atom) uses operator<<
rather than debugString(), so works with gtest.
Therefore moved out of DebugSupport.h
- Did the same to Solver::Result, and some helper changes to SolverTest,
so that we get useful messages on unit test failures
- formulas are now printed as infix expressions on one line, rather than
wrapped/indented S-exprs. My experience is that this is easier to scan
FCs for small examples, and large ones are unreadable either way.
- most of the several debugString() functions for constraints/results
are unused, so removed them rather than updating tests.
Inlined the one that was actually used into its callsite.

Differential Revision: https://reviews.llvm.org/D153366

show more ...

[dataflow] Extract arena for Value/StorageLocation out of DataflowAnalysisContext

DataflowAnalysisContext has a few too many responsibilities, this narrows them.

It also allows the Arena to be shar

[dataflow] Extract arena for Value/StorageLocation out of DataflowAnalysisContext

DataflowAnalysisContext has a few too many responsibilities, this narrows them.

It also allows the Arena to be shared with analysis steps, which need to create
Values, without exposing the whole DACtx API (flow conditions etc).
This means Environment no longer needs to proxy all these methods.
(For now it still does, because there are many callsites to update, and maybe
if we separate bool formulas from values we can avoid churning them twice)

In future, if we untangle the concepts of Values from boolean formulas/atoms,
Arena would also be responsible for creating formulas and managing atom IDs.

Differential Revision: https://reviews.llvm.org/D148554

show more ...