View source for User:Realazthat/Projects wishlist/LLVM/Strategic optimizations

Strategic optimizations are those that change the overall way a function does its duty; ie. it changes the algorithm entirely, changing control flow and complexity, both time and/or memory.

The only way I know of currently that a strategic optimization can take place is either by:
* Dead code elimination
* Constant folding/evaluation
* Memoization/tail call optimization
* [[wp:Superoptimization]]
*: Combinations of instructions are tested for functional equivalence
** Takes forever
** Better way would be to find a way to iterator over set of all possible equivalent algorithms, in a decidable (subset) language, and test their complexity
** Some other pruning approaches
*** On a random combination, execute the algorithm for tiny inputs, most won't match
*** Choose the instructions as a graph of possible paths, make sure not to lose any bits of information that would be necessary for the output
*** Use a SMT solver to simulate a [[wp:Machine_that_always_halts|halting turing machine]] (decider)
**** Assert that there is no input to the decider that has the same output as the function (also translated to SMT for the decider)
**** Ask for a counter example
**** Additionally, if complexity can be auto-computed (due to the loops being finite), assert that there is no algorithm with a lower complexity
**** Additionally, when calculating the complexity, add weights to different instructions to be used as constants, and keep the constants and lower order nomials in the complexity calculation to determine a winning overall algorithm


Other approaches:
* Recognize problems in their complexity class (eg. in P, or in NP), and use reductions to reduce the complexity to the easiest problem

== Recommended research ==
* "term graph rewriting"
* "strong normalization property"
** http://www.cs.st-andrews.ac.uk/~eb/writings/thesis.ps.gz
** http://www.cs.st-andrews.ac.uk/~eb/