New cfg code

[Jeffrey A Law <law at cygnus dot com>]

Fun fun fun.

Suppose we have something like this before cse2:

(insn 75 104 77 (set (reg:SI 25)
        (reg:SI 27)) 48 {movsi+2} (nil)
    (expr_list:REG_LABEL (code_label 80 79 81 15 "" [num uses: 2])
        (expr_list:REG_EQUAL (label_ref:SI 80)
            (nil))))

(insn 77 75 78 (set (reg:SI 26)
        (mem/u:SI (plus:SI (mult:SI (reg:SI 24)
                    (const_int 4 [0x4]))
                (reg:SI 25)) 0)) 48 {movsi+2} (nil)
    (nil))

(jump_insn 78 77 79 (parallel[
            (set (pc)
                (reg:SI 26))
            (use (label_ref 80))
        ] ) 364 {tablejump} (nil)
    (nil))

(barrier 79 78 80)

(code_label 80 79 81 15 "" [num uses: 2])

(jump_insn 81 80 82 (addr_vec:SI[
(barrier)
[ ... more insns ... ]
end of function

Then let's assume that we can determine that reg24 is a constant.  And
therefore we can determine the precise target of the tablejump in insn 78.

CSE deletes insn 78, and emits a fresh new jump to the constant target, then
deletes insn 78.  Since insn 78 is followed by a BARRIER, delete_insn will
*not* delete (code_label 80) or (jump_insn 81).

The RTL after this looks like:

(insn 75 104 77 (set (reg:SI 25)
        (reg:SI 27)) 48 {movsi+2} (nil)
    (expr_list:REG_EQUAL (label_ref:SI 80)
        (nil)))

(insn 77 75 111 (set (reg:SI 26)
        (label_ref:SI 16)) 48 {movsi+2} (nil)
    (expr_list:REG_LABEL (code_label 16 10 103 5 "" [num uses: 9])
        (expr_list:REG_EQUAL (label_ref:SI 16)
            (nil))))

(jump_insn 111 77 112 (set (pc)
        (label_ref 16)) -1 (nil)
    (nil))

(barrier 112 111 80)

(code_label 80 112 81 15 "" [num uses: 1])

(jump_insn 81 80 82 (addr_vec:SI[
            (label_ref:SI 16)
            (label_ref:SI 16)
            (label_ref:SI 16)
            (label_ref:SI 16)
            (label_ref:SI 16)
            (label_ref:SI 41)
            (label_ref:SI 16)
        ] ) -1 (nil)

(barrier 82 81 28)

Note carefully that we have a block that is just a label and an jump
table.  Danger, danger, danger.

We eventually get into find_basic_blocks and this code:

        case JUMP_INSN:
          /* A basic block ends at a jump.  */
          if (head == NULL_RTX)
            head = insn;
          else
            {
              /* ??? Make a special check for table jumps.  The way this
                 happens is truely and amazingly gross.  We are about to
                 create a basic block that contains just a code label and
                 an addr*vec jump insn.  Worse, an addr_diff_vec creates
                 its own natural loop.

                 Prevent this bit of brain damage, pasting things together
                 correctly in make_edges.

                 The correct solution involves emitting the table directly
                 on the tablejump instruction as a note, or JUMP_LABEL.  */

              if (GET_CODE (PATTERN (insn)) == ADDR_VEC
                  || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
                {
                  head = end = NULL;
                  n_basic_blocks--;
                  break;
                }

Which as far as I can tell has the effect of leaving the CODE_LABEL and
ADDR_VEC in no-mans land (ie, not in any basic block).

We then find that all the code after the ADDR_VEC is dead, so we delete it.

So now we have something like
[ ... block 0 ... ]
[ ... block 1 ... ]
(code_label 80)
(jump_insn 81 (addr_vec ... ))
(barier)
(bunch-o-notes)
(end of function)

Where the code label and the jump insn are not in any basic block.

This triggers an abort in global.c::make_insn_chain because it checks for
the case where we find real insns after the last known basic block.

One thought would be to try and have CSE kill the ADDR_VEC when it turns
the tablejump into a simple jump.

Another would be to have jump kill the unreachable ADDR_VEC.

Another would be to not special case this stuff in find_basic_blocks_1 and
instead either attach the insns to the previous block via merge_blocks or
delete the block if we determine it is unreachable.

Your thoughts would be appreciated.

Here's the testcase for x86-linux -O2


extern int getch();
extern int class();

int
token()
{
    int state = 1;

    while (1) {
	int c=0;
	c = getch();
	switch (state) {
	case 1: break;
	case 4: break;
	case 5: break;
	case 6: 
            {
	        switch (class(c)) {
	        default: break;
	        }
	    } break;
	case 7:	break;
	}
    }
}