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