| 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. |