This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Fwd: [dataflow]: PATCH: fix grammar error, clean whitespace, add more comments


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)
>                    {
>   


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]