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