Attacking quadratic behaviors associated with SWITCH_EXPR
Kazu Hirata
kazu@cs.umass.edu
Sat Oct 23 13:00:00 GMT 2004
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
More information about the Gcc
mailing list