| 1 |
Date: Sun, 12 May 2002 17:12:53 -0500 (CDT) |
| 2 |
From: Chris Lattner <[email protected]> |
| 3 |
To: "Vikram S. Adve" <[email protected]> |
| 4 |
Subject: LLVM change |
| 5 |
|
| 6 |
There is a fairly fundemental change that I would like to make to the LLVM |
| 7 |
infrastructure, but I'd like to know if you see any drawbacks that I |
| 8 |
don't... |
| 9 |
|
| 10 |
Basically right now at the basic block level, each basic block contains an |
| 11 |
instruction list (returned by getInstList()) that is a ValueHolder of |
| 12 |
instructions. To iterate over instructions, we must actually iterate over |
| 13 |
the instlist, and access the instructions through the instlist. |
| 14 |
|
| 15 |
To add or remove an instruction from a basic block, we need to get an |
| 16 |
iterator to an instruction, which, given just an Instruction*, requires a |
| 17 |
linear search of the basic block the instruction is contained in... just |
| 18 |
to insert an instruction before another instruction, or to delete an |
| 19 |
instruction! This complicates algorithms that should be very simple (like |
| 20 |
simple constant propagation), because they aren't actually sparse anymore, |
| 21 |
they have to traverse basic blocks to remove constant propagated |
| 22 |
instructions. |
| 23 |
|
| 24 |
Additionally, adding or removing instructions to a basic block |
| 25 |
_invalidates all iterators_ pointing into that block, which is really |
| 26 |
irritating. |
| 27 |
|
| 28 |
To fix these problems (and others), I would like to make the ordering of |
| 29 |
the instructions be represented with a doubly linked list in the |
| 30 |
instructions themselves, instead of an external data structure. This is |
| 31 |
how many other representations do it, and frankly I can't remember why I |
| 32 |
originally implemented it the way I did. |
| 33 |
|
| 34 |
Long term, all of the code that depends on the nasty features in the |
| 35 |
instruction list (which can be found by grep'ing for getInstList()) will |
| 36 |
be changed to do nice local transformations. In the short term, I'll |
| 37 |
change the representation, but preserve the interface (including |
| 38 |
getInstList()) so that all of the code doesn't have to change. |
| 39 |
|
| 40 |
Iteration over the instructions in a basic block remains the simple: |
| 41 |
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) ... |
| 42 |
|
| 43 |
But we will also support: |
| 44 |
for (Instruction *I = BB->front(); I; I = I->getNext()) ... |
| 45 |
|
| 46 |
After converting instructions over, I'll convert basic blocks and |
| 47 |
functions to have a similar interface. |
| 48 |
|
| 49 |
The only negative aspect of this change that I see is that it increases |
| 50 |
the amount of memory consumed by one pointer per instruction. Given the |
| 51 |
benefits, I think this is a very reasonable tradeoff. |
| 52 |
|
| 53 |
What do you think? |
| 54 |
|
| 55 |
-Chris |