84 lines · plain
1SUMMARY2-------3 4We met to discuss the LLVM instruction format and bytecode representation:5 6ISSUES RESOLVED7---------------8 91. We decided that we shall use a flat namespace to represent our 10 variables in SSA form, as opposed to having a two dimensional namespace11 of the original variable and the SSA instance subscript.12 13ARGUMENT AGAINST:14 * A two dimensional namespace would be valuable when doing alias 15 analysis because the extra information can help limit the scope of16 analysis.17 18ARGUMENT FOR:19 * Including this information would require that all users of the LLVM20 bytecode would have to parse and handle it. This would slow down the21 common case and inflate the instruction representation with another22 infinite variable space.23 24REASONING:25 * It was decided that because original variable sources could be26 reconstructed from SSA form in linear time, that it would be an27 unjustified expense for the common case to include the extra28 information for one optimization. Alias analysis itself is typically29 greater than linear in asymptotic complexity, so this extra analaysis30 would not affect the runtime of the optimization in a significant31 way. Additionally, this would be an unlikely optimization to do at32 runtime.33 34 35IDEAS TO CONSIDER36-----------------37 381. Including dominator information in the LLVM bytecode39 representation. This is one example of an analysis result that may be40 packaged with the bytecodes themselves. As a conceptual implementation 41 idea, we could include an immediate dominator number for each basic block42 in the LLVM bytecode program. Basic blocks could be numbered according43 to the order of occurrence in the bytecode representation.44 452. Including loop header and body information. This would facilitate46 detection of intervals and natural loops.47 48UNRESOLVED ISSUES 49----------------- 50 511. Will oSUIF provide enough of an infrastructure to support the research52 that we will be doing? We know that it has less than stellar53 performance, but hope that this will be of little importance for our54 static compiler. This could affect us if we decided to do some IP55 research. Also we do not yet understand the level of exception support56 currently implemented.57 582. Should we consider the requirements of a direct hardware implementation59 of the LLVM when we design it? If so, several design issues should60 have their priorities shifted. The other option is to focus on a61 software layer interpreting the LLVM in all cases.62 633. Should we use some form of packetized format to improve forward64 compatibility? For example, we could design the system to encode a65 packet type and length field before analysis information, to allow a66 runtime to skip information that it didn't understand in a bytecode67 stream. The obvious benefit would be for compatibility, the drawback68 is that it would tend to splinter that 'standard' LLVM definition.69 704. Should we use fixed length instructions or variable length71 instructions? Fetching variable length instructions is expensive (for72 either hardware or software based LLVM runtimes), but we have several73 'infinite' spaces that instructions operate in (SSA register numbers,74 type spaces, or packet length [if packets were implemented]). Several75 options were mentioned including: 76 A. Using 16 or 32 bit numbers, which would be 'big enough'77 B. A scheme similar to how UTF-8 works, to encode infinite numbers78 while keeping small number small.79 C. Use something similar to Huffman encoding, so that the most common80 numbers are the smallest.81 82-Chris83 84