User:Realazthat/Projects wishlist/LLVM/Strategic optimizations

From Rosetta Code

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 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