The previous commit had the side effect that `IRVariable`s were created
for all `Functions`, including those that did not have IR. This commit
restricts all `TIRVariable` constructors to functions that have IR.
This doesn't make it much faster, but it reduces the debug output
volume. It also simplifies the code.
I've found this change necessary when I compute the full IR on a
Wireshark snapshot in QL4E. Without it, Eclipse runs out of memory
because the console log is too large.
The new predicate `isOrphan` gets inlined into
`ignoreExprAndDescendants`, whose performance improves from
TranslatedElement::ignoreExprAndDescendants#f .. 23.4s (executed 9 times)
to
TranslatedElement::ignoreExprAndDescendants#f ... 4.3s (executed 9 times)
This dramatic improvement is not only due to eliminating a type check in
the recursive case. Removing the type check from the other base cases
also enabled them to get better join orders.
The previous reccomentation changed the behaviour of the code.
A user following the advice might have broken her/his code:
With call-by-value, the original parameter is not changed.
With a call-by-reference, however, it may be changed. To be sure,
nothing breaks by blindly following the advice, suggest to pass a
const reference.
The `SSAConstruction.getNewIRVariable` was very slow on Wireshark. This
was probably because it couldn't join on multiple columns
simultaneously. Instead of improving the join, I observed that the
`TIRVariable` type was the same between all three IR stages except for a
few occurrences of `FunctionIR` that could easily be changed to
`Function`. By sharing `TIRVariable` between all the stages, we avoid
recomputing it and translating it between every stage, turning the slow
`getNewIRVariable` predicate into a no-op.
This change means that later stages of the IR can't introduce new
variables, but that was already the case because
`config/identical-files.json` forced all three `IRVariable.qll` files to
be identical.
This predicate computed a local CP between all defs and uses of the same
virtual variable in a basic block. This wasn't a problem in
`unaliased_ssa`, but it became a huge problem in `aliased_ssa`, probably
because many variables can be modelled with a single virtual variable
there.
Before this commit, evaluation of `aliased_ssa`'s
`variableLiveOnEntryToBlock#ff#antijoin_rhs` on Wireshark took 80
_minutes_. After this commit, that predicate and its immediate
dependencies take around 5 _seconds_.
This relation was almost 40x the size it needed to be on Wireshark
because it lacked a restriction on the `tag` parameter. To implement
that restriction efficiently, I had to split the relation in two to
dictate the join order.
With the fix, `getInstruction` now computes the same as
`getInstructionTranslatedElementAndTag`, so the latter could be
simplified.
I made a corresponding change to `TranslatedElement.getTempVariable` for
the sake of consistency.
A part of `SSAConstruction.getInstructionOperandDefinition` was more
expensive than it had to be. On a ChakraCore snapshot, this changes the
tuple counts from
3020569 ~2% {3} r40 = JOIN OperandTag::TUnmodeledUseOperand#f WITH Instruction::Instruction::getFunction_dispred#ff CARTESIAN PRODUCT OUTPUT FIELDS {Instruction::Instruction::getFunction_dispred#ff.<0>,OperandTag::TUnmodeledUseOperand#f.<0>,Instruction::Instruction::getFunction_dispred#ff.<1>}
62405 ~0% {3} r41 = JOIN r40 WITH Instruction::UnmodeledUseInstruction#class#fffffff ON r40.<0>=Instruction::UnmodeledUseInstruction#class#fffffff.<0> OUTPUT FIELDS {r40.<2>,r40.<1>,r40.<0>}
2868421 ~1% {3} r42 = JOIN r41 WITH Instruction::Instruction::getFunction_dispred#ff_10#join_rhs ON r41.<0>=Instruction::Instruction::getFunction_dispred#ff_10#join_rhs.<0> OUTPUT FIELDS {Instruction::Instruction::getFunction_dispred#ff_10#join_rhs.<1>,r41.<1>,r41.<2>}
62405 ~0% {3} r43 = JOIN r42 WITH Instruction::UnmodeledDefinitionInstruction#class#fffffff ON r42.<0>=Instruction::UnmodeledDefinitionInstruction#class#fffffff.<0> OUTPUT FIELDS {r42.<2>,r42.<1>,r42.<0>}
to
(0s) Starting to evaluate predicate SSAConstruction::Cached::getUnmodeledUseInstruction#ff
(0s) Tuple counts:
62405 ~0% {2} r1 = JOIN Instruction::UnmodeledUseInstruction#class#fffffff WITH Instruction::Instruction::getFunction_dispred#ff ON Instruction::UnmodeledUseInstruction#class#fffffff.<0>=Instruction::Instruction::getFunction_dispred#ff.<0> OUTPUT FIELDS {Instruction::Instruction::getFunction_dispred#ff.<1>,Instruction::Instruction::getFunction_dispred#ff.<0>}
return r1
...
75716 ~0% {3} r40 = JOIN OperandTag::TUnmodeledUseOperand#f WITH FunctionIR::FunctionIR::getUnmodeledDefinitionInstruction#ff CARTESIAN PRODUCT OUTPUT FIELDS {FunctionIR::FunctionIR::getUnmodeledDefinitionInstruction#ff.<0>,OperandTag::TUnmodeledUseOperand#f.<0>,FunctionIR::FunctionIR::getUnmodeledDefinitionInstruction#ff.<1>}
62405 ~0% {3} r41 = JOIN r40 WITH FunctionIR::FunctionIR::getUnmodeledUseInstruction#ff ON r40.<0>=FunctionIR::FunctionIR::getUnmodeledUseInstruction#ff.<0> OUTPUT FIELDS {FunctionIR::FunctionIR::getUnmodeledUseInstruction#ff.<1>,r40.<1>,r40.<2>}
Now that we have `Expr.getParentWithConversions`, we can implement
`TranslatedElement.getRealParent` simpler. This implementation also
avoids recursion.
In theory this query will produce no results on C++ code; in practice, I
suspect the "cpp" suite is often run on code compiled as C, so it is
likely to be worth running anyways.
