Anonymous user
User:Realazthat/Projects wishlist/LLVM/Strategic optimizations: Difference between revisions
User:Realazthat/Projects wishlist/LLVM/Strategic optimizations (view source)
Revision as of 21:41, 18 October 2010
, 13 years agono edit summary
No edit summary |
mNo edit summary |
||
Line 10:
*** 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
| |||