Segfault in ilist_node::getPrevNode for nodes with certain custom traits

Is ilist_node::getPrevNode() supposed to work for node types with custom
traits that embed the sentinel? Examples: Instruction, MachineInstr,
BasicBlock, …

Calling getPrevNode on the first node in a such a list segfaults because
"Prev" is 0:

  NodeTy *getPrevNode() {
    NodeTy *Prev = this->getPrev();

    // Check for sentinel.
    if (!Prev->getNext())
      return 0;

    return Prev;
  }

None of the ilist unit tests pass/run when done with similar traits.
They either segfault or run into the sentinel.

Prev could be initialized to the Sentinel in the traits constructor,
which avoids the segfault. But the sentinel check still won't work since
the sentinel is only an ilist_half_node, and its Next value and the list
head have the same memory address.

-Nico

Looking through the history this was indeed implemented (in 2009) to
save a pointer. I'm surprised this issue hasn't come up more often (I
can only find 2 mails regarding this issue, without conclusion).

One solution I tested would be to use a special ilist_half_node in these
cases that represents "Prev" and "isSentinel" with a PointerIntPair,
lift the sentinel check into the list traits and then specialize the
check use the PointerIntPair where applicable (see the attached patch
for a draft).

-Nico

ilist.patch (5.52 KB)