This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Fwd: [dataflow]: PATCH: fix grammar error, clean whitespace, add more comments
- From: Kenneth Zadeck <zadeck at naturalbridge dot com>
- To: Seongbae Park <seongbae dot park at gmail dot com>
- Cc: Daniel Berlin <dberlin at dberlin dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Thu, 11 Jan 2007 01:30:11 -0500
- Subject: Re: Fwd: [dataflow]: PATCH: fix grammar error, clean whitespace, add more comments
- References: <ab3a61990701101258j4c4fe813wa776edd422d103ab@mail.gmail.com> <ab3a61990701102227h60becce2i4d2816b7ae87c243@mail.gmail.com>
Seongbae Park wrote:
> Forgot to send to you guys directly.
>
> Seongbae
>
fine by me.
Kenny
> ---------- Forwarded message ----------
> From: Seongbae Park <seongbae.park@gmail.com>
> Date: Jan 10, 2007 12:58 PM
> Subject: [dataflow]: PATCH: fix grammar error, clean whitespace, add
> more comments
> To: gcc-patches <gcc-patches@gcc.gnu.org>
>
>
> This is mostly more comments and fixes for grammar/spelling erorrs
> and whitespace cleanup. Bootstrapped and reg-tested on i686.
> OK?
>
> 2007-01-10 Seongbae Park <seongbae.park@gmail.com>
> * df-core.c (df_worklist_propagate_backward,
> df_worklist_dataflow)): More comments.
> (df_iterative_dataflow): Whitespace fixup.
> * cfganal.c (inverted_post_order_compute):
> More comments and rename a local variable DEST to PRED.
> (df_find_deadend): More comments. Use gcc_unreachable().
>
> --
> #pragma ident "Seongbae Park, compiler, http://seongbae.blogspot.com"
>
>
>
>
> ------------------------------------------------------------------------
>
> Index: df-core.c
> ===================================================================
> --- df-core.c (revision 120635)
> +++ df-core.c (working copy)
> @@ -998,7 +998,10 @@ df_worklist_propagate_backward (struct d
> Worklist algorithm works better than iterative algorithm
> for CFGs with no nested loops.
> In practice, the measurement shows worklist algorithm beats
> - iterative algorithm by some margin overall. */
> + iterative algorithm by some margin overall.
> + Note that this is slightly different from the traditional textbook worklist solver,
> + in that the worklist is effectively sorted by the reverse postorder.
> + For CFGs with no nested loops, this is optimal. */
>
> void
> df_worklist_dataflow (struct dataflow *dataflow,
> @@ -1019,17 +1022,18 @@ df_worklist_dataflow (struct dataflow *d
> /* BBINDEX_TO_POSTORDER maps the bb->index to the reverse postorder. */
> bbindex_to_postorder = (unsigned int *)xmalloc (last_basic_block * sizeof (unsigned int));
>
> - /* Initialize the array to an out-of-bound value. */
> + /* Initialize the array to an out-of-bound value. */
> for (i = 0; i < last_basic_block; i++)
> bbindex_to_postorder[i] = last_basic_block;
>
> + /* Initialize the considered map. */
> sbitmap_zero (considered);
> -
> EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, index, bi)
> {
> SET_BIT (considered, index);
> }
>
> + /* Initialize the mapping of block index to postorder. */
> for (i = 0; i < n_blocks; i++)
> {
> bbindex_to_postorder[blocks_in_postorder[i]] = i;
> @@ -1095,13 +1099,12 @@ df_iterative_dataflow (struct dataflow *
> {
> idx = blocks_in_postorder[i];
> SET_BIT (pending, idx);
> - };
> + }
>
> dataflow->problem->init_fun (blocks_to_consider);
>
> while (1)
> {
> -
> /* For forward problems, you want to pass in reverse postorder
> and for backward problems you want postorder. This has been
> shown to be as good as you can do by several people, the
> Index: cfganal.c
> ===================================================================
> --- cfganal.c (revision 120635)
> +++ cfganal.c (working copy)
> @@ -744,32 +744,24 @@ post_order_compute (int *post_order, boo
>
>
> /* Helper routine for inverted_post_order_compute.
> - BB has to belong to an region of CFG
> - unreachable by inverted traversal of the CFG from the exit.
> + BB has to belong to a region of CFG
> + unreachable by inverted traversal from the exit.
> i.e. there's no control flow path from ENTRY to EXIT
> that contains this BB.
> This can happen in two cases - if there's an infinite loop
> or if there's a block that has no successor
> (call to a function with no return).
> - Other part of the RTL passes deal with this by
> - calling connect_infinite_loops_to_exit () or
> - add_noreturn_fake_exit_edges (),
> - but this function is used for the dataflow computation
> - which might be used by a pass that requires
> - not to change the CFG. Hence, we deal with
> - the infinite loop/no return cases by identifying
> - a unique basic block that can reach all blocks
> - in the region when traversed in inverted CFG.
> - This function returns a basic block that satisfies:
> - 1) the block has no successor
> - or
> - 2) the block that is at the bottom of the infinite loop
> - in a DFS search.
> -
> - It's guaranteed that all blocks in the region
> - that BB belongs to are reachable
> - by an inverted traversal on the returned basic block.
> - */
> + Some RTL passes deal with this condition by
> + calling connect_infinite_loops_to_exit () and/or
> + add_noreturn_fake_exit_edges ().
> + However, those methods involve modifying the CFG itself
> + which may not be desirable.
> + Hence, we deal with the infinite loop/no return cases
> + by identifying a unique basic block that can reach all blocks
> + in such a region by inverted traversal.
> + This function returns a basic block that guarantees
> + that all blocks in the region are reachable
> + by starting an inverted traversal from the returned block. */
>
> static basic_block
> dfs_find_deadend (basic_block bb)
> @@ -790,27 +782,25 @@ dfs_find_deadend (basic_block bb)
> bb = EDGE_SUCC (bb, 0)->dest;
> }
>
> - sbitmap_free (visited);
> - return NULL;
> + gcc_unreachable ();
> }
>
>
> -/* Compute reverse top sort order with the inverted CFG
> +/* Compute the reverse top sort order of the inverted CFG
> i.e. starting from the exit block and following the edges backward
> - (from successors to predecessors.
> - This is mainly used for getting the reverse post-order
> - for forward dataflow problems.
> + (from successors to predecessors).
> + This ordering can be used for forward dataflow problems among others.
>
> This function assumes that all blocks in the CFG are reachable
> - from the entry (but not necessarily from EXIT by traversal of inverted CFG).
> + from the ENTRY (but not necessarily from EXIT).
>
> - The problematic condition occurs when there's an infinite loop
> - or a non-exit block with no successor in the CFG,
> - which means a simple inverted traversal starting from the exit
> - can't assign the order for all reachable blocks.
> - To solve this problem, we first start with the exit block
> - and do the usual traversal from the exit.
> - If there are any block left that's not visited by this method,
> + If there's an infinite loop,
> + a simple inverted traversal starting from the blocks
> + with no successors can't visit all blocks.
> + To solve this problem, we first do inverted traversal
> + starting from the blocks with no successor.
> + And if there's any block left that's not visited by the regular
> + inverted traversal from EXIT,
> those blocks are in such problematic region.
> Among those, we find one block that has
> any visited predecessor (which is an entry into such a region),
> @@ -856,31 +846,30 @@ inverted_post_order_compute (int *post_o
> while (sp)
> {
> edge_iterator ei;
> - basic_block src;
> - basic_block dest;
> + basic_block pred;
>
> /* Look at the edge on the top of the stack. */
> ei = stack[sp - 1];
> - src = ei_edge (ei)->dest;
> - dest = ei_edge (ei)->src;
> + bb = ei_edge (ei)->dest;
> + pred = ei_edge (ei)->src;
>
> - /* Check if the edge destination has been visited yet. */
> - if (! TEST_BIT (visited, dest->index))
> + /* Check if the predecessor has been visited yet. */
> + if (! TEST_BIT (visited, pred->index))
> {
> /* Mark that we have visited the destination. */
> - SET_BIT (visited, dest->index);
> + SET_BIT (visited, pred->index);
>
> - if (EDGE_COUNT (dest->preds) > 0)
> - /* Since the DEST node has been visited for the first
> - time, check its successors. */
> - stack[sp++] = ei_start (dest->preds);
> + if (EDGE_COUNT (pred->preds) > 0)
> + /* Since the predecessor node has been visited for the first
> + time, check its predecessors. */
> + stack[sp++] = ei_start (pred->preds);
> else
> - post_order[post_order_num++] = dest->index;
> + post_order[post_order_num++] = pred->index;
> }
> else
> {
> - if (src != EXIT_BLOCK_PTR && ei_one_before_end_p (ei))
> - post_order[post_order_num++] = src->index;
> + if (bb != EXIT_BLOCK_PTR && ei_one_before_end_p (ei))
> + post_order[post_order_num++] = bb->index;
>
> if (!ei_one_before_end_p (ei))
> ei_next (&stack[sp - 1]);
> @@ -889,9 +878,9 @@ inverted_post_order_compute (int *post_o
> }
> }
>
> - /* Detect inifinite loop and activate the kludge.
> - Note that this loop doesn't check EXIT_BLOCK itself.
> - It is always added after the outer do-while loop below. */
> + /* Detect any inifinite loop and activate the kludge.
> + Note that this doesn't check EXIT_BLOCK itself
> + since EXIT_BLOCK is always added after the outer do-while loop. */
> FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
> if (!TEST_BIT (visited, bb->index))
> {
> @@ -903,7 +892,6 @@ inverted_post_order_compute (int *post_o
> edge e;
> basic_block visited_pred = NULL;
>
> -
> /* Find an already visited predecessor. */
> FOR_EACH_EDGE (e, ei, bb->preds)
> {
>