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