OSDev.org

Boris wrote:I don't think you can have a reference which will work for any language and any target architecture.
If you are looking for something very generic, why don't you look at LLVM work ? http://llvm.org/docs/LangRef.html

Artlav wrote:Some examples of assembler code are fine, but the idea is to document the patterns used.

• for (initial;final;increment){A;}
  -Process initial
  -Remember current position X
  -Process final
  -Emit unresolved conditional jump Y
  -Process A
  -Process increment
  -Emit goto X
  -Store current position to Y

    for (initial;condition;increment) { A; }

    initial;
    if(!condition) goto endloop;
startloop:
    A;
    if(condition) goto startloop;
endloop:

Schol-R-LEA wrote:Also, I would expect highly optimizing compilers to insert an optimization step before converting the high-level AST to the less abstract low-level AST, but most compilers won't (or at least won't use them unless given an option to do very aggressive optimizations) because such techniques are both difficult to write and have considerable time requirements. You would only use them for those few optimizations that rely on knowledge of the specific type of operation in question, such as converting a case (switch) to a jump table.

Schol-R-LEA wrote:Makes sense, I agree. Dead code elimination is something you probably would want more than one pass of, though, with the high-level pass at the start and at the very least a peephole pass at the end. Different optimization strategies may cause dead code to be generated, and while it probably can be avoided in most case, I don't know if it always can be, so a polish pass during the peephole stage might be a good idea.

Mind you, this relates to some of the issues I am having with the design of my AOT/JIT pair, and the data format for relics itself. I want to do at least some high-level optimization in the AOT, preferably quite a few for code in the release-candidate and release states; if nothing else, the I expect the superoptimizer to trigger rebuilds for some code fairly often, so having the optimizations completed ahead of time would avoid cases where the rebuild time and memory usage exceeds what would be saved by specializing rebuilds.

• some optimisations are higher level/generic (constant folding, dead code elimination, common sub-expression elimination, etc) and belong in your AOT compiler (and don't make sense in your JIT)
• some optimisations (register allocation, peephole, branch removal, etc) depend on low level/machine specific information and belong in your JIT (and don't make any sense in the AOT compiler)

Schol-R-LEA wrote:However, a general high-level optimizer risks losing information that could be used by the JIT optimizer, so I don't want to discard the data entirely. I am thinking that I would have to pack the original AST into the relic, and possibly allow it to have more than one pre-optimized AST as well, and let the JIT decide which AST branches it wants to build from. I may even make it possible for the fetch system to request a specific optimization tree rather than have the whole set of ASTs transferred, but determining something so complicated would probably be going past the point of diminishing returns.