• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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