Attacking quadratic behaviors associated with SWITCH_EXPR

[Kazu Hirata]

Hi,

Some operations dealing with SWITCH_EXPR are known to be expensive.

Let me start out with a list of common operations with SWITCH_EXPR
along with their costs.

Let n is the the number of case labels in a SWITCH_EXPR.  Here are
summary of "given A, find B" operations related to SWITCH_EXPR.

INTEGER_CST -> CASE_LABEL_EXPR
  O(log n).  Implemented in find_case_label_for_value.

CASE_LABEL_EXPR -> LABEL_DECL
  O(1).  This is a primitive operation.

CASE_LABEL_EXPR -> basic_block (via LABEL_DECL)
  O(1).  Implemented in label_to_block.

CASE_LABEL_EXPR -> edge (via LABEL_DECL and basic_block)
  O(n).  Performed in find_taken_edge_switch_expr.
  Implemented as label_to_block, followed by find_edge

edge -> CASE_LABEL_EXPR
  O(n).  Performed in tree_redirect_edge_and_branch.

Functions dealing with SWITCH_EXPR often scan the entires set of case
labels, so if those functions perform one of the last two operations
above, we easily get O(n^2) behavior.

======================================================================

First, I am thinking about improving "CASE_LABEL_EXPR -> edge" as
follows.

1. add "edge e;" to stmt_ann_d

2. allocate stmt_ann for each CASE_LABEL_EXPR

3. stop using CASE_LABEL of CASE_LABEL_EXPR after CFG is created.  In
   fact, we should probably put null in CASE_LABEL so that people
   won't mistakenly use it.

Then we should be able to do

  stmt_ann (switch_stmt)->e

to get an edge equivalent to find_edge (label_to_block (CASE_LABEL ()))
in constant time.  Now the obvious concern is memory consumption
arising from having edge for every statement with stmt_ann.  I need
come clever ideas here.  Maybe a hash table mapping CASE_LABEL_EXPR to
edge?

======================================================================

Second, I am thinking about improving "edge -> CASE_LABEL_EXPR" as
follows.

1. Have exactly one CASE_LABEL_EXPR per edge by doing something like
   this

   case 6 ... 8, 16 ... 20: goto <L5>;

   This means that we goto <L5> if a value given to the SWITCH_EXPR is
   between 6 and 8 or 16 and 20.

2. Create a sorted array of single ranges like 6...8, so that
   "INTEGER_CST -> CASE_LABEL_EXPR" can continue to use a binary
   search.

3. Put the sorted array in the SWITCH_EXPR.  As a result, the
   SWITCH_EXPR would have a sorted array of ranges *and* an array of
   CASE_LABEL_EXPRs.

4. Put a pointer in edge to point back to CASE_LABEL_EXPR.

Then we should be able to do "edge -> CASE_LABEL_EXPR" in constant
time.

======================================================================

I think it's easier to address "CASE_LABEL_EXPR -> edge", and that
should probably be done first.

By the way, here is a message from Steven Bosscher on the same
subject.

http://gcc.gnu.org/ml/gcc/2004-09/msg01141.html

Kazu Hirata