Just like `TInstruction` is cached to prevent re-numbering its tuples in
every IR query, I think `TOperand` should be cached too. I tested it on
the small comdb2 snapshot, where it only saves one second of work when
running a second IR query, but the savings should grow when snapshots
are larger and when there are more IR queries in a suite. Tuple
numbering is mildly quadratic, so it should be good to avoid repeating
it.
Adding these annotations adds three cached stages to the existing four
cached stages of the IR. The new cached stages are small and do not
appear to repeat any work from the other stages, so I see no advantage
to merging them with the existing stages.
The previous version of the test used `0 = 1;` to test an lvalue-typed
`ErrorExpr`, but the extractor replaced the whole assignment expression
with `ErrorExpr` instead of just the LHS. This variation of the test
only leads to an `ErrorExpr` for the part of the syntax that's supposed
to be an lvalue-typed expression, so that's an improvement.
Unfortunately it still doesn't demonstrate that we can `Store` into an
address computed by an `ErrorExpr`.
This doesn't fix the underlying problem that for some reason there are
cycles in the operand graph on our snapshots of the Linux kernel, but it
ensures that the cycles don't lead to non-termination of
`ConstantAnalysis` and `ValueNumbering`.
The `ValueNumbering` library is supposed to propagate value numberings
through a `CopyInstruction` only when it's _congruent_, meaning it must
have exact overlap with its source. A `CopyInstruction` can be a
`LoadInstruction`, a `StoreInstruction`, or a `CopyValueInstruction`.
The latter is also a `UnaryInstruction`, and the value numbering rule
for `UnaryInstruction` applied to it as well.
This meant that value numbering would propagate even through a
non-congruent `CopyValueInstruction`. That's semantically wrong but
probably only an issue in very rare circumstances, and it should get
corrected when we change the definition of `getUnary` to require
congruence.
What's worse is the performance implications. It meant that the value
numbering IPA witness could take two different paths through every
`CopyValueInstruction`. If multiple `CopyValueInstruction`s were
chained, this would lead to an exponential number of variable numbers
for the same `Instruction`, and we would run out of time and space
while performing value numbering.
This fixes the performance of `ValueNumbering.qll` on
https://github.com/asterisk/asterisk, although this project might also
require a separate change for fixing an infinite loop in the IR constant
analysis.
Before this change, `delete` and `delete[]` expressions had no control
flow after them, which caused the reachability analysis to remove all
code after a delete expression. This commit adds placeholder support for
delete expression by translating them to `NoOp` instructions so their
presence doesn't cause large chunks of the program to be removed.
This changes all the getters on `Instruction` to use `getDef` instead of
`getAnyDef`, with the result that these getters now only have a result
if the definition is exact.
This is a backwards-INCOMPATIBLE change.
These are the hand-written changes that complete the automatic changes
from the previous commit.
- Add deprecated compatibility wrappers for the renamed predicates.
- Add a new `Operand.getDef` predicate.
- Clarify the QLDoc for all these predicates.
This renames `getDefinitionInstruction` to `getAnyDef`, reflecting that
it includes definitions without exact overlap. It renames
`getUseInstruction` to `getUse` for consistency.
perl -p -i -e 's/\bgetUseInstruction\b/getUse/g; s/\bgetDefinitionInstruction\b/getAnyDef/g' \
cpp/ql/src/semmle/code/cpp/ir/**/*.ql* \
cpp/ql/test/**/*.ql* \
cpp/ql/src/semmle/code/cpp/rangeanalysis/**/*.ql*
The predicates `getter` and `setter` in `StructLikeClass.qll` were very
slow on some snapshots. On https://github.com/dotnet/coreclr they had
this performance:
StructLikeClass::getter#fff#antijoin_rhs ........... 3m55s
Variable::Variable::getAnAssignedValue_dispred#bb .. 3m36s
StructLikeClass::setter#fff#antijoin_rhs ........... 20.5s
The `getAnAssignedValue_dispred` predicate in the middle was slow due to
magic propagated from `setter`.
With this commit, performance is instead:
StructLikeClass::getter#fff#antijoin_rhs ........... 497ms
Variable::Variable::getAnAssignedValue_dispred#ff .. 617ms
StructLikeClass::setter#fff#antijoin_rhs ........... 158ms
Instead of hand-optimizing the QL for performance, I simplified `setter`
and `getter` to require slightly stronger conditions. Previously, a
function was only considered a setter if it had no writes to other
fields on the same class. That requirement is now relaxed by dropping
the "on the same class" part. I made the corresponding change for what
defines a getter. I think that still captures the spirit of what getters
and setters are.
I also changed the double-negation with `exists` into a `forall`.
The `sameBaseType` predicate was fundamentally quadratic, and this blew
up on large C++ code bases. Replacing it with calls to `Type.stripType`
fixes performance and does not affect the qltests. It looks like
`sameBaseType` was used purely an ad hoc heuristic, so I'm not worried
about the slight semantic difference between `sameBaseType` and
`stripType`.
