| Date: Sun, 12 May 2002 17:12:53 -0500 (CDT) |
| From: Chris Lattner <sabre@nondot.org> |
| To: "Vikram S. Adve" <vadve@cs.uiuc.edu> |
| Subject: LLVM change |
| |
| There is a fairly fundemental change that I would like to make to the LLVM |
| infrastructure, but I'd like to know if you see any drawbacks that I |
| don't... |
| |
| Basically right now at the basic block level, each basic block contains an |
| instruction list (returned by getInstList()) that is a ValueHolder of |
| instructions. To iterate over instructions, we must actually iterate over |
| the instlist, and access the instructions through the instlist. |
| |
| To add or remove an instruction from a basic block, we need to get an |
| iterator to an instruction, which, given just an Instruction*, requires a |
| linear search of the basic block the instruction is contained in... just |
| to insert an instruction before another instruction, or to delete an |
| instruction! This complicates algorithms that should be very simple (like |
| simple constant propagation), because they aren't actually sparse anymore, |
| they have to traverse basic blocks to remove constant propogated |
| instructions. |
| |
| Additionally, adding or removing instructions to a basic block |
| _invalidates all iterators_ pointing into that block, which is really |
| irritating. |
| |
| To fix these problems (and others), I would like to make the ordering of |
| the instructions be represented with a doubly linked list in the |
| instructions themselves, instead of an external data structure. This is |
| how many other representations do it, and frankly I can't remember why I |
| originally implemented it the way I did. |
| |
| Long term, all of the code that depends on the nasty features in the |
| instruction list (which can be found by grep'ing for getInstList()) will |
| be changed to do nice local transformations. In the short term, I'll |
| change the representation, but preserve the interface (including |
| getInstList()) so that all of the code doesn't have to change. |
| |
| Iteration over the instructions in a basic block remains the simple: |
| for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) ... |
| |
| But we will also support: |
| for (Instruction *I = BB->front(); I; I = I->getNext()) ... |
| |
| After converting instructions over, I'll convert basic blocks and |
| functions to have a similar interface. |
| |
| The only negative aspect of this change that I see is that it increases |
| the amount of memory consumed by one pointer per instruction. Given the |
| benefits, I think this is a very reasonable tradeoff. |
| |
| What do you think? |
| |
| -Chris |