docs/HistoricalNotes/2003-06-26-Reoptimizer2.txt

   1 Thu Jun 26 14:43:04 CDT 2003
   2
   3 Information about BinInterface
   4 ------------------------------
   5
   6 Take in a set of instructions with some particular register
   7 allocation. It allows you to add, modify, or delete some instructions,
   8 in SSA form (kind of like LLVM's MachineInstrs.) Then re-allocate
   9 registers. It assumes that the transformations you are doing are safe.
  10 It does not update the mapping information or the LLVM representation
  11 for the modified trace (so it would not, for instance, support
  12 multiple optimization passes; passes have to be aware of and update
  13 manually the mapping information.)
  14
  15 The way you use it is you take the original code and provide it to
  16 BinInterface; then you do optimizations to it, then you put it in the
  17 trace cache.
  18
  19 The BinInterface tries to find live-outs for traces so that it can do
  20 register allocation on just the trace, and stitch the trace back into
  21 the original code. It has to preserve the live-ins and live-outs when
  22 it does its register allocation.  (On exits from the trace we have
  23 epilogues that copy live-outs back into the right registers, but
  24 live-ins have to be in the right registers.)
  25
  26
  27 Limitations of BinInterface
  28 ---------------------------
  29
  30 It does copy insertions for PHIs, which it infers from the machine
  31 code. The mapping info inserted by LLC is not sufficient to determine
  32 the PHIs.
  33
  34 It does not handle integer or floating-point condition codes and it
  35 does not handle floating-point register allocation.
  36
  37 It is not aggressively able to use lots of registers.
  38
  39 There is a problem with alloca: we cannot find our spill space for
  40 spilling registers, normally allocated on the stack, if the trace
  41 follows an alloca(). What might be an acceptable solution would be to
  42 disable trace generation on functions that have variable-sized
  43 alloca()s. Variable-sized allocas in the trace would also probably
  44 screw things up.
  45
  46 Because of the FP and alloca limitations, the BinInterface is
  47 completely disabled right now.
  48
  49
  50 Demo
  51 ----
  52
  53 This is a demo of the Ball & Larus version that does NOT use 2-level
  54 profiling.
  55
  56 1. Compile program with llvm-gcc.
  57 2. Run opt -lowerswitch -paths -emitfuncs on the bytecode.
  58    -lowerswitch change switch statements to branches
  59    -paths       Ball & Larus path-profiling algorithm
  60    -emitfuncs   emit the table of functions
  61 3. Run llc to generate SPARC assembly code for the result of step 2.
  62 4. Use g++ to link the (instrumented) assembly code.
  63
  64 We use a script to do all this:
  65 ------------------------------------------------------------------------------
  66 #!/bin/sh
  67 llvm-gcc $1.c -o $1
  68 opt -lowerswitch -paths -emitfuncs $1.bc > $1.run.bc
  69 llc -f $1.run.bc
  70 LIBS=$HOME/llvm_sparc/lib/Debug
  71 GXX=/usr/dcs/software/evaluation/bin/g++
  72 $GXX -g -L $LIBS $1.run.s -o $1.run.llc \
  73 $LIBS/tracecache.o \
  74 $LIBS/mapinfo.o \
  75 $LIBS/trigger.o \
  76 $LIBS/profpaths.o \
  77 $LIBS/bininterface.o \
  78 $LIBS/support.o \
  79 $LIBS/vmcore.o \
  80 $LIBS/transformutils.o \
  81 $LIBS/bcreader.o \
  82 -lscalaropts -lscalaropts -lanalysis \
  83 -lmalloc -lcpc -lm -ldl
  84 ------------------------------------------------------------------------------
  85
  86 5. Run the resulting binary.  You will see output from BinInterface
  87 (described below) intermixed with the output from the program.
  88
  89
  90 Output from BinInterface
  91 ------------------------
  92
  93 BinInterface's debugging code prints out the following stuff in order:
  94
  95 1. Initial code provided to BinInterface with original register
  96 allocation.
  97
  98 2. Section 0 is the trace prolog, consisting mainly of live-ins and
  99 register saves which will be restored in epilogs.
 100
 101 3. Section 1 is the trace itself, in SSA form used by BinInterface,
 102 along with the PHIs that are inserted.
 103 PHIs are followed by the copies that implement them.
 104 Each branch (i.e., out of the trace) is annotated with the
 105 section number that represents the epilog it branches to.
 106
 107 4. All the other sections starting with Section 2 are trace epilogs.
 108 Every branch from the trace has to go to some epilog.
 109
 110 5. After the last section is the register allocation output.