[PATCH,RFC] CSE path following on basic blocks

Steven Bosscher stevenb.gcc@gmail.com
Tue Nov 28 12:39:00 GMT 2006


On 11/28/06, Eric Botcazou <ebotcazou@libertysurf.fr> wrote:
> !   /* There is a previous path.  Make sure it started with FIRST_BB.  */
> !   if (path_size)
> !     gcc_assert (data->path[0].bb = first_bb);
>
> Not sure what you're trying to do here.  Or maybe an annoying typo?

If there is a path in data, then we're going to discover a new path
starting with
data->path[0].bb.  But Passing first_bb may be unnecessary.


> !       /* Otherwise, path_size must be equal to or greater than 2, because
> !        a previous path exists that is at least two basic blocks long.  */
> !       gcc_assert (path_size >= 2);
>
> I'm generally for assertions, but this one is useless as the 0 and 1 cases are
> short-circuited just above.

Yes.  Left-over from testing.  I sometimes ended up with path_size < 0
due to a bug.  I'll remove this in the final patch submission.

> It seems to me that cse_find_path is a nop if flag_cse_follow_jumps is not set
> so it should not be invoked in this case, only cse_prescan_path should be.

Well, that depends on what we want to do with flag_cse_follow_jumps,
because as you noticed, in the current patch...:

> But aren't you fundamentally altering the meaning of flag_cse_follow_jumps
> here?  The current CSE works on extended basic blocks independently of
> whether flag_cse_follow_jumps is set.

Correct.

I'm not sure if we want to do this, though.  We could follow the
fallthrough path even if flag_cse_follow_jumps is not set (which is
indeed what CSE currently does). Or we could make CSE purely a local
(i.e. intra basic block) pass if flag_cse_follow_jumps is not set.
Personally, I don't think it matters much, but making it purely local
is slightly easier and a lot more consistent.


> ! #if ENABLE_CHECKING
> !                 /* We should only see blocks here that we have not
> !                    visited yet.  */
> !                 gcc_assert (!TEST_BIT (cse_visited_basic_blocks, bb->index));
> ! #endif
>
> Is that really true with a DFS traversal?

Yes. If you see a block twice in a DFS, you've traversed a back-edge.


>          do
>            {
>              prev = PREV_INSN (prev);
>            }
> !         while (prev != bb_head);
>
> Convoluted way to write "prev = bb_head;" :-)

Heh.  Thanks for catching that one :-)  That's what you get when you
blindly do search and replace.


> *************** cse_insn (rtx insn, rtx libcall_insn)
> *** 5599,5606 ****
>             This section previously turned the REG_EQUIV into a REG_EQUAL
>             note.  We cannot do that because REG_EQUIV may provide an
>             uninitialized stack slot when REG_PARM_STACK_SPACE is used.  */
> !
> !         if (prev != 0 && NONJUMP_INSN_P (prev)
>              && GET_CODE (PATTERN (prev)) == SET
>              && SET_DEST (PATTERN (prev)) == SET_SRC (sets[0].rtl)
>              && ! find_reg_note (prev, REG_EQUIV, NULL_RTX))
> --- 5609,5616 ----
>             This section previously turned the REG_EQUIV into a REG_EQUAL
>             note.  We cannot do that because REG_EQUIV may provide an
>             uninitialized stack slot when REG_PARM_STACK_SPACE is used.  */
> !         gcc_assert (prev);
> !         if (NONJUMP_INSN_P (prev)
>              && GET_CODE (PATTERN (prev)) == SET
>              && SET_DEST (PATTERN (prev)) == SET_SRC (sets[0].rtl)
>              && ! find_reg_note (prev, REG_EQUIV, NULL_RTX))
>
> Please explain.

Well, we know that prev == bb_head, and a basic block with a NULL
bb_head can't occur.  The rest is just what the code was before.


> *************** cse_insn (rtx insn, rtx libcall_insn)
> *** 5647,5652 ****
> --- 5652,5659 ----
>    prev_insn_cc0_mode = this_insn_cc0_mode;
>    prev_insn = insn;
>  #endif
> +
> +   return;
>  }
>
> Rather clever attempt to grow the size of the patch. :-)

Actually, without this you get a warning about a label at the end of a
compound statement on CC0-targets.  I found that out the hard way.


> !         /* Get a reasonable extimate for the maximum number of qty's
> !            needed for this path.  For this, we take the number of sets
> !            and multiply that by MAX_RECOG_OPERANDS.
> !            The old CSE path following code would use MIN(2*nsets,500)
> !            but now that we know exactly how many insns (and hence sets)
> !            we will see in the path, it seemed like a good idea to just
> !            use max_qty = 2 * nsets.  Interestingly, we end up writing
> !            past the end of qty_table with that value for max_qty.  In
> !            other words, this was a latent bug in cse.c present since
> !            at least 1992.
> !            Oh well, we just take a bigger max_qty now to play safe.  */
> !         max_qty = ebb_data.nsets * MAX_RECOG_OPERANDS;
> !         cse_basic_block_start = ebb_data.low_cuid;
> !         cse_basic_block_end = ebb_data.high_cuid;
>
> Firstly it's MAX(2*nsets,500), not MIN, in the old code.

Yes.  Typo.

>  Secondly, "a
> reasonable estimate" sounds a little worrying and the old code really
> thinks it computes an upper bound.  If that's not true, we should try to
> identify the problem instead of papering over it.

The old code does think it computes an upper bound, but if you remove
the 500 from CSE as it is on the trunk, it will also ICE, usually on
small functions (e.g. I had a test case with max_qty == 3, and we
allocated 6 qtys).  I don't know where the extra qty's come from yet.

Yes, that should be fixed.

No, I will not do this for the current patch (but I will look into it
later because I need to fix this anyway if I'm going to save/restore
the hash table at the end of each basic block).


> >         (rest_of_handle_cse): Initialize cfglayout mode.  Verify that
> >         the CFG is incrementally updated and correct after cse_main.
> >         Don't call delete_trivially_dead_insns, let cfgcleanup do that.
> >         (rest_of_handle_cse2): Verify the CFG here, too, after cse_main.
>
> Why the dissymmetry between rest_of_handle_cse and rest_of_handle_cse2?

Just testing.  I wanted to make sure CSE works in cfglayout and cfgrtl
mode, and so I just ended up making different changes to the two
passes.

> ! #ifdef ENABLE_CHECKING
> !   if (purge_all_dead_edges ())
> !     gcc_unreachable ();
> ! #endif
>
> Could you add a comment (especially in rest_of_handle_cse2)?

OK.
It should also be gcc_assert (!purge_all_dead_edges ()) as you pointed
out last weekend.


Thanks for looking at the patch!

Gr.
Steven



More information about the Gcc-patches mailing list