Chris Lattner | 82ac87c | 2002-05-13 22:19:50 +0000 | [diff] [blame] | 1 | Date: Sun, 12 May 2002 17:12:53 -0500 (CDT) |
| 2 | From: Chris Lattner <sabre@nondot.org> |
| 3 | To: "Vikram S. Adve" <vadve@cs.uiuc.edu> |
| 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 propogation), because they aren't actually sparse anymore, |
| 21 | they have to traverse basic blocks to remove constant propogated |
| 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 |