[llvm-dev] ilist/iplist are broken (maybe I'll fix them?)

[escha via llvm-dev]

> On Oct 8, 2015, at 11:00 AM, Justin Bogner via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> "Duncan P. N. Exon Smith" <dexonsmith at apple.com> writes:
>> I don't feel totally comfortable just going ahead and fixing this
>> without buy-in, since it'll touch some things.  Here's my basic plan:
>> 
>>  - Fix `getNextNode()` and `getPrevNode()` by taking in the parent list
>>    and checking against `end()` instead of checking for `nullptr`.
>>  - Change the lists to be normal circular linked lists (possibly I'll
>>    stick an "is-sentinel" bit in the prev pointer in asserts builds so
>>    we can have assertions instead of infinite loops).  I'll layer our
>>    weird partial ownership semantics on top to keep this part NFC.
>>  - Re-layer the external state hooks so that they're on top of the
>>    basic list instead of inside of it (so that someone in the future
>>    can understand the code with far less studying).
>> 
>> Anyone want to back me on this before I dive in?  Even better, did I
>> miss something fundamental?
> 
> +1
> 
> Other than having to update pretty well the entire code base, I don't
> see any drawbacks to replacing ilist/iplist with something sane. The
> current thing is complicated, tries to do too many things (and not many
> of them well), and broken in several ways. In addition to the UB and
> re-capitation you mention, I've also heard of issues using the reverse
> iterators.

Specifically, I discovered (the hard and painful way) last night that if you reverse-iterator over a MachineBasicBlock, removing/moving instructions as you go — even pre-incrementing the iterator at the start of the loop isn’t enough to prevent the list from being corrupted in unexpected ways. A regular iterator, used backwards (-- instead of ++) works correctly, nothing else different.

—escha