Replace llvm::iplist<Instruction> with TaggedList<Instruction> in IRFunction

[stoklund]

I want to introduce a new linked list data structure, TaggedList. This is an intrusive doubly linked list like llvm::iplist with the following differences:

• Each node has a uint32_t tag member. These tags are maintained online in a strictly increasing order. This means that the relative position of elements in the list can be determined in (fast) constant time, even while inserting and removing elements from the list.
• The list has a constant time size() operation, maintained as a member in the TaggedList class. This is needed for the online tag maintenance algorithm.
• Splicing is a linear time operation because the new elements need to be tagged correctly. This is already the case for our specialization of transferNodesFromList().
• The tag also makes it possible to detect when an end() iterator is dereferenced or incremented.

I have implemented a prototype of TaggedList based on the Two simplified algorithms for maintaining order in a list paper in order to run benchmarks. List insertions are O(log N) with excellent constant factors.

We already have class LiveIntervalsInstructionNumbering in IROptimizer.cpp. This change makes that class redundant by providing the same functionality while also allowing online instruction insertions.

The online instruction ordering is needed to implement advanced memory allocation and scheduling in backends.

Preemptively Answered Questions:

• No, we can't extend llvm::iplist with this functionality because a) iplist::size() is linear time, and b) despite using 27 template classes for configuration and specialization, iplist doesn't offer the hooks needed.
• No, we can't implement this as a hack in IRFunction because a) we need the constant time size() operator, and b) IRFunction::getInstrs() exposes the list implementation, and we can't prevent users from modifying the list and invalidating our side tables.

[stoklund]

The average time to insert an element in a list as measured on my MacBook Pro:

• 256 nodes: 11 ns.
• 256 K nodes: 125 ns.
• 256 M nodes: 1597 ns.

The constant factor steps up around 256 K nodes which corresponds to the size of my last level cache. Each list node is 24 bytes in my benchmark program.

For comparison, I've measured untagged list insertions at ~7 ns. Note that this is a very difficult operation to time, though. The time taken is usually dominated by what else is going on in the program.

[SplitInfinity]

@stoklund

This sounds interesting. Is this a good issue for a beginner to work on?

[stoklund]

Is this a good issue for a beginner to work on?

Yes for a Glow beginner, no for a C++ beginner ;-)

I already have a prototype where I worked out a lot of the implementation details of the retagging algorithm. Maybe I should get that in shape so I can submit it as a WIP PR.

[SplitInfinity]

@stoklund

I can take over if you post whatever you have. Perhaps there is value for me in polishing up your existing code.

[stoklund]

@SplitInfinity Are you still working on this?

[SplitInfinity]

@stoklund

No, I'll put it back up for grabs.