diff options
author | Chris Lattner <sabre@nondot.org> | 2002-05-13 22:19:50 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2002-05-13 22:19:50 +0000 |
commit | 82ac87cc215897c3ab682ffbfd958a4098d7337f (patch) | |
tree | 54373f97bd6fe1dcf97c86b0a74fcd34960ac82a /docs/HistoricalNotes/2002-05-12-InstListChange.txt | |
parent | 2172db04e7feeb7e0d841e0350824f1991db4625 (diff) | |
download | external_llvm-82ac87cc215897c3ab682ffbfd958a4098d7337f.zip external_llvm-82ac87cc215897c3ab682ffbfd958a4098d7337f.tar.gz external_llvm-82ac87cc215897c3ab682ffbfd958a4098d7337f.tar.bz2 |
New file
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2618 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'docs/HistoricalNotes/2002-05-12-InstListChange.txt')
-rw-r--r-- | docs/HistoricalNotes/2002-05-12-InstListChange.txt | 55 |
1 files changed, 55 insertions, 0 deletions
diff --git a/docs/HistoricalNotes/2002-05-12-InstListChange.txt b/docs/HistoricalNotes/2002-05-12-InstListChange.txt new file mode 100644 index 0000000..004edb0 --- /dev/null +++ b/docs/HistoricalNotes/2002-05-12-InstListChange.txt @@ -0,0 +1,55 @@ +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 propogation), 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 |