The number of candidate bounds during the main `SimpleRangeAnalysis`
recursion was in principle always exponential in the size of the
program, but in practice it did not get out of hand when only `+` and
`-` operations were supported. Now that `*` is also supported, the range
analysis started timing out on the SinaMostafanejad/OpenRDM project. The
problematic expressions in that project are of the form
a*x*x*x + b*x*x + c*x + d
where most of the variables involved are recursive definitions and are
therefore likely to have a large number of candidate bounds.
The fix here is to identify those few binary operations that are most
likely to cause an explosion in the number of bounds and apply widening
to them. Previously, widening was only applied at definitions.
This stops some cases of `-0.0` from propagating through the range
analysis, fixing a false positive on arvidn/libtorrent.
There seems to be no need for a corresponding change in the caller of
`getDefLowerBoundsImpl` since that predicate only contains computations
that cannot introduce negative zero.
The range analysis wasn't producing useful bounds for `AssignOperation`s
(`+=`, `-=`) unless their RHS involved a variable. This is because a
shortcut was made in the `analyzableDef` predicate, which used to
specify that an analyzable definition was one for which we'd specified
the dependencies. But we can't distinguish between having _no
dependencies_ and having _no specification of the dependencies_.
The fix is to be more explicit about which definitions are analyzable.
To avoid too much repetition I'm still calling out to `analyzableExpr`
in the new code.
The pretty-printing of a QL `float` didn't include enough digits to tell
whether a large number had accurate bounds. The `toString` value of a
float appears to be more precise.
When the extractor can't prove that control flow will never reach the end of a non-`void`-returning function without reaching an explicit `return` statement, it inserts an implicit `return` without an operand. If control actually reaches this point, the behavior is undefined.
We were previously generating invalid IR for these implicit `return` statements, because the lack of an operand meant that there was no definition of the return value variable along that path. Instead, I've changed the IR generation to emit an `Unreached` instruction for the implicit `return`. This ensures that we don't create a control flow edge from the end of the body to the function epilogue.
The change to the range analysis test avoids having that test depend on the previous bad IR behavior, while still preserving the original spirit of the test.
Added a new `StaticLocalVariable` class, which made several other pieces of the original change a bit cleaner.
Fixed test failures due to a mistake in the original `CFG.qll` change.
Added a test case for static local variables with constructors.
Removed the `Uninitialized` instruction from the initialization of a static local, because all objects with static storage duration are zero-initialized at startup.
Fixed expectations for `SignAnalysis.ql` to reflect that a bad result is now fixed.
Previously, the `Load` would be associated with the `CrementOperation`
rather than its operand, which gave surprising results when mapping
taint sinks back to `Expr`.
The changes in `raw_ir.expected` are to add `Copy` operations on the
`x++` in code like `y = x++`. This is now needed because the result that
`x++` would otherwise have (the Load) no longer belongs to the `++`
expression. Copies are inserted to ensure that all expressions are
associated with an `Instruction` result.
The changes in `*aliased_ssa_ir.expected` appear to be just wobble.
