Re: PA casesi questions

[John Wehle <john at feith dot com>]

To add a little context ... the value range propgation pass that I'm
currently shaking out the bugs is capable of determining the min. and
max. values for the index into a jump table.  I.e.:

  if (a < 0)
    return;

  if (a > 4)
    return;

  /* At this point "a" is >= 0 and <= 4.  */

  switch (a)
    {
    case 0: ... ; break;
    case 1: ... ; break;
    ...
    case 9: ... ; break;
    default: break;
    }

It uses that information to truncate the jump table when it determines
that the last entries will never be used.  It works by parsing the RTL
in order to determine what register is the index into the table.

> > (jump_insn 108 8 120 (set (pc)
> >         (if_then_else (gtu (reg/v:SI 94)
> >                 (const_int 9 [0x9]))
> >             (label_ref 113)
> >             (pc))) 47 {bleu+1} (nil)
> >     (nil))
> > 
> > (note 120 108 109 [bb 1] NOTE_INSN_BASIC_BLOCK)
> > 
> > (jump_insn 109 120 110 (set (pc)
> >         (plus:SI (mem:SI (plus:SI (pc)
> >                     (reg/v:SI 94)) 0)
> >             (label_ref 110))) 284 {casesi0} (nil)
> >     (nil))
> > 
> > (code_label 110 109 111 15 "" "" [num uses: 1])
> > 
> > (jump_insn 111 110 112 (addr_vec:DI[ 
> >             (label_ref:SI 13)
> >             (label_ref:SI 21)
> > ...
> > 
> > which doesn't look right.  Specifically:
> > 
> >   1) Jump_insn 109 looks like it does a jump relative to code_label 110,
> >      however an addr_vec is being used, not an addr_diff_vec.  Should
> >      CASE_VECTOR_PC_RELATIVE be defined in pa.h and ASM_OUTPUT_ADDR_VEC_ELT
> >      omitted?
> Not an issue.  Switches in PA-land turn into an indirect branch (insn 108)
> which jumps to a direct branch to the ultimate destination (insn 111).

From a RTL correctness standpoint it doesn't make sense (to me at least).
The RTL says that a value in the table at PC is added to label_ref 110
and the sum stored in PC.  Since JUMP_TABLES_IN_TEXT_SECTION is set this
means that PC = PC + MEM (PC + index), however the table is an addr_vec
which means that MEM (PC + index) is an absolute address.  It seems to
me that PC = PC + MEM (PC + index) requires MEM (PC + index) represent
a relative address in order to be valid RTL.  This comment:

/* This is how to output an element of a case-vector that is relative.
   This must be defined correctly as it is used when generating PIC code.

   I believe it safe to use the same definition as ASM_OUTPUT_ADDR_VEC_ELT
   on the PA since ASM_OUTPUT_ADDR_VEC_ELT uses pc-relative jump instructions
   rather than a table of absolute addresses.  */

from pa.h says that pc-relative jump instructions are used.  Doesn't this
also suggest CASE_VECTOR_PC_RELATIVE be define and ASM_OUTPUT_ADDR_VEC_ELT
be omitted?  Or should the RTL be changed to PC = MEM (PC + index) if it
isn't desirable to change the ADDR_VEC to a ADDR_DIFF_VEC?

> >   2) The addr_vec is DImode, jump_insn 109 references the memory in SImode,
> >      and judging by jump_insn 108 register 94 is an index into a QImode
> >      jump table.  Should the casesi jump (assuming that TARGET_BIG_SWITCH
> >      isn't set) read:
> > 
> >      (set (pc) (plus:SI (sign_extend:SI (mem:QI (plus:SI (pc)
> >                     (reg/v:SI 94)) 0))
> >             (label_ref 110)))
> > 
> >      and CASE_VECTOR_MODE changed appropriately?
> No, the code as it stands is correct.
> 
> The mode of the ADDR_VEC/ADDR_DIFF_VEC indicates the size (in bytes) of each
> item in the jump vector.  Since each entry in the jump vector corresponds to
> exactly 2 instructions (8 bytes) the mode of the ADDR_DIFF should be DImode.

Thanks for clarifying what the jump tables actully looks like.  The RTL
in jump_insn 108 establishes that register 94 is <= 9.  The RTL in jump_insn
109 is ... (mem:SI (plus:SI (pc) (reg/v:SI 94))).  Let's assume that
register 94 is 1, jump_insn 109 is then going to add the value
(mem:SI (plus:SI (pc) (1))) to label_ref 110 which is incorrect if the
entries are eight bytes in size.  I'm thinking that in this case the RTL
should look like ... (mem:SI (plus:SI (pc) (mult:SI (reg/v:SI 94)
                                                    (const_int 8))))

My code looks for variations of:

   (set (pc) (plus:SI (mem:SI (label_ref)
                              (register / expression))
                      (pc)))

Once register / expression is determined (by parsing the RTL) it's current
min. and max. values are divided by size of the ADDR_VEC/ADDR_DIFF_VEC
mode in order to determine the first and last entries of the
ADDR_VEC/ADDR_DIFF_VEC which will be used.  Entries at the end of
ADDR_VEC/ADDR_DIFF_VEC which will never be used are then deleted.

I'm open to better ways of analyzing the RTL in order to determine the min.
and max. values of the jump table index.

-- John
-------------------------------------------------------------------------
|   Feith Systems  |   Voice: 1-215-646-8000  |  Email: john@feith.com  |
|    John Wehle    |     Fax: 1-215-540-5495  |                         |
-------------------------------------------------------------------------