Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 1 | SUMMARY |
| 2 | ------- |
| 3 | |
| 4 | We met to discuss the LLVM instruction format and bytecode representation: |
| 5 | |
| 6 | ISSUES RESOLVED |
| 7 | --------------- |
| 8 | |
| 9 | 1. We decided that we shall use a flat namespace to represent our |
| 10 | variables in SSA form, as opposed to having a two dimensional namespace |
| 11 | of the original variable and the SSA instance subscript. |
| 12 | |
| 13 | ARGUMENT AGAINST: |
| 14 | * A two dimensional namespace would be valuable when doing alias |
| 15 | analysis because the extra information can help limit the scope of |
| 16 | analysis. |
| 17 | |
| 18 | ARGUMENT FOR: |
| 19 | * Including this information would require that all users of the LLVM |
| 20 | bytecode would have to parse and handle it. This would slow down the |
| 21 | common case and inflate the instruction representation with another |
| 22 | infinite variable space. |
| 23 | |
| 24 | REASONING: |
| 25 | * It was decided that because original variable sources could be |
| 26 | reconstructed from SSA form in linear time, that it would be an |
| 27 | unjustified expense for the common case to include the extra |
| 28 | information for one optimization. Alias analysis itself is typically |
| 29 | greater than linear in asymptotic complexity, so this extra analaysis |
| 30 | would not affect the runtime of the optimization in a significant |
| 31 | way. Additionally, this would be an unlikely optimization to do at |
| 32 | runtime. |
| 33 | |
| 34 | |
| 35 | IDEAS TO CONSIDER |
| 36 | ----------------- |
| 37 | |
| 38 | 1. Including dominator information in the LLVM bytecode |
| 39 | representation. This is one example of an analysis result that may be |
| 40 | packaged with the bytecodes themselves. As a conceptual implementation |
| 41 | idea, we could include an immediate dominator number for each basic block |
| 42 | in the LLVM bytecode program. Basic blocks could be numbered according |
| 43 | to the order of occurance in the bytecode representation. |
| 44 | |
| 45 | 2. Including loop header and body information. This would facilitate |
| 46 | detection of intervals and natural loops. |
| 47 | |
| 48 | UNRESOLVED ISSUES |
| 49 | ----------------- |
| 50 | |
| 51 | 1. Will oSUIF provide enough of an infrastructure to support the research |
| 52 | that we will be doing? We know that it has less than stellar |
| 53 | performance, but hope that this will be of little importance for our |
| 54 | static compiler. This could affect us if we decided to do some IP |
| 55 | research. Also we do not yet understand the level of exception support |
| 56 | currently implemented. |
| 57 | |
| 58 | 2. Should we consider the requirements of a direct hardware implementation |
| 59 | of the LLVM when we design it? If so, several design issues should |
| 60 | have their priorities shifted. The other option is to focus on a |
| 61 | software layer interpreting the LLVM in all cases. |
| 62 | |
| 63 | 3. Should we use some form of packetized format to improve forward |
| 64 | compatibility? For example, we could design the system to encode a |
| 65 | packet type and length field before analysis information, to allow a |
| 66 | runtime to skip information that it didn't understand in a bytecode |
| 67 | stream. The obvious benefit would be for compatibility, the drawback |
| 68 | is that it would tend to splinter that 'standard' LLVM definition. |
| 69 | |
| 70 | 4. Should we use fixed length instructions or variable length |
| 71 | instructions? Fetching variable length instructions is expensive (for |
| 72 | either hardware or software based LLVM runtimes), but we have several |
| 73 | 'infinite' spaces that instructions operate in (SSA register numbers, |
| 74 | type spaces, or packet length [if packets were implemented]). Several |
| 75 | 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 numbers |
| 78 | while keeping small number small. |
| 79 | C. Use something similar to Huffman encoding, so that the most common |
| 80 | numbers are the smallest. |
| 81 | |
| 82 | -Chris |
| 83 | |