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]

[PATCH] Fix PR41101


This fixes PR41101 - another case where the maximal set is being computed
as too small.  The fix is to no longer explicitly compute it but instead
take it as containing all expressions.  This means we have to defer
all blocks where we didn't visit at least one successor.

Bootstrapped and tested on x86_64-unknown-linux-gnu, ok for trunk
and the 4.4 branch?

It exposes PR41316 which is being worked on.

Thanks,
Richard.

2009-09-09  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/41101
	* tree-ssa-pre.c (maximal_set): Remove.
	(compute_antic_aux): Treat the maximal set as implicitly all ones.
	Defer all blocks we didn't visit at least one successor.
	(add_to_exp_gen): Do not add to the maximal set.
	(make_values_for_phi): Likewise.
	(compute_avail): Likewise.
	(init_pre): Do not allocate the maximal set.
	(execute_pre): Do not dump it.

	* gcc.c-torture/compile/pr41101.c: New testcase.

Index: gcc/tree-ssa-pre.c
===================================================================
*** gcc/tree-ssa-pre.c.orig	2009-09-09 11:36:20.000000000 +0200
--- gcc/tree-ssa-pre.c	2009-09-09 11:37:06.000000000 +0200
*************** typedef struct bb_bitmap_sets
*** 401,410 ****
  #define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred
  
  
- /* Maximal set of values, used to initialize the ANTIC problem, which
-    is an intersection problem.  */
- static bitmap_set_t maximal_set;
- 
  /* Basic block list in postorder.  */
  static int *postorder;
  
--- 401,406 ----
*************** compute_antic_aux (basic_block block, bo
*** 2201,2249 ****
      {
        VEC(basic_block, heap) * worklist;
        size_t i;
!       basic_block bprime, first;
  
        worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
        FOR_EACH_EDGE (e, ei, block->succs)
- 	VEC_quick_push (basic_block, worklist, e->dest);
-       first = VEC_index (basic_block, worklist, 0);
- 
-       if (phi_nodes (first))
  	{
! 	  bitmap_set_t from = ANTIC_IN (first);
  
! 	  if (!BB_VISITED (first))
! 	    from = maximal_set;
! 	  phi_translate_set (ANTIC_OUT, from, block, first);
  	}
        else
! 	{
! 	  if (!BB_VISITED (first))
! 	    bitmap_set_copy (ANTIC_OUT, maximal_set);
! 	  else
! 	    bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first));
! 	}
  
!       for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++)
  	{
  	  if (phi_nodes (bprime))
  	    {
  	      bitmap_set_t tmp = bitmap_set_new ();
! 	      bitmap_set_t from = ANTIC_IN (bprime);
! 
! 	      if (!BB_VISITED (bprime))
! 		from = maximal_set;
! 	      phi_translate_set (tmp, from, block, bprime);
  	      bitmap_set_and (ANTIC_OUT, tmp);
  	      bitmap_set_free (tmp);
  	    }
  	  else
! 	    {
! 	      if (!BB_VISITED (bprime))
! 		bitmap_set_and (ANTIC_OUT, maximal_set);
! 	      else
! 		bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
! 	    }
  	}
        VEC_free (basic_block, heap, worklist);
      }
--- 2197,2241 ----
      {
        VEC(basic_block, heap) * worklist;
        size_t i;
!       basic_block bprime, first = NULL;
  
        worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
        FOR_EACH_EDGE (e, ei, block->succs)
  	{
! 	  if (!first
! 	      && BB_VISITED (e->dest))
! 	    first = e->dest;
! 	  else if (BB_VISITED (e->dest))
! 	    VEC_quick_push (basic_block, worklist, e->dest);
! 	}
  
!       /* Of multiple successors we have to have visited one already.  */
!       if (!first)
! 	{
! 	  SET_BIT (changed_blocks, block->index);
! 	  BB_VISITED (block) = 0;
! 	  BB_DEFERRED (block) = 1;
! 	  changed = true;
! 	  VEC_free (basic_block, heap, worklist);
! 	  goto maybe_dump_sets;
  	}
+ 
+       if (phi_nodes (first))
+ 	phi_translate_set (ANTIC_OUT, ANTIC_IN (first), block, first);
        else
! 	bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first));
  
!       for (i = 0; VEC_iterate (basic_block, worklist, i, bprime); i++)
  	{
  	  if (phi_nodes (bprime))
  	    {
  	      bitmap_set_t tmp = bitmap_set_new ();
! 	      phi_translate_set (tmp, ANTIC_IN (bprime), block, bprime);
  	      bitmap_set_and (ANTIC_OUT, tmp);
  	      bitmap_set_free (tmp);
  	    }
  	  else
! 	    bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
  	}
        VEC_free (basic_block, heap, worklist);
      }
*************** add_to_exp_gen (basic_block block, tree
*** 3711,3717 ****
  	return;
        result = get_or_alloc_expr_for_name (op);
        bitmap_value_insert_into_set (EXP_GEN (block), result);
-       bitmap_value_insert_into_set (maximal_set, result);
      }
  }
  
--- 3703,3708 ----
*************** make_values_for_phi (gimple phi, basic_b
*** 3740,3746 ****
  		{
  		  e = get_or_alloc_expr_for_name (arg);
  		  add_to_value (get_expr_value_id (e), e);
- 		  bitmap_value_insert_into_set (maximal_set, e);
  		}
  	    }
  	}
--- 3731,3736 ----
*************** compute_avail (void)
*** 3781,3790 ****
        e = get_or_alloc_expr_for_name (name);
        add_to_value (get_expr_value_id (e), e);
        if (!in_fre)
! 	{
! 	  bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e);
! 	  bitmap_value_insert_into_set (maximal_set, e);
! 	}
        bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), e);
      }
  
--- 3771,3777 ----
        e = get_or_alloc_expr_for_name (name);
        add_to_value (get_expr_value_id (e), e);
        if (!in_fre)
! 	bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e);
        bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), e);
      }
  
*************** compute_avail (void)
*** 3888,3898 ****
  		get_or_alloc_expression_id (result);
  		add_to_value (get_expr_value_id (result), result);
  		if (!in_fre)
! 		  {
! 		    bitmap_value_insert_into_set (EXP_GEN (block),
! 						  result);
! 		    bitmap_value_insert_into_set (maximal_set, result);
! 		  }
  		continue;
  	      }
  
--- 3875,3881 ----
  		get_or_alloc_expression_id (result);
  		add_to_value (get_expr_value_id (result), result);
  		if (!in_fre)
! 		  bitmap_value_insert_into_set (EXP_GEN (block), result);
  		continue;
  	      }
  
*************** compute_avail (void)
*** 3974,3983 ****
  		get_or_alloc_expression_id (result);
  		add_to_value (get_expr_value_id (result), result);
  		if (!in_fre)
! 		  {
! 		    bitmap_value_insert_into_set (EXP_GEN (block), result);
! 		    bitmap_value_insert_into_set (maximal_set, result);
! 		  }
  
  		continue;
  	      }
--- 3957,3963 ----
  		get_or_alloc_expression_id (result);
  		add_to_value (get_expr_value_id (result), result);
  		if (!in_fre)
! 		  bitmap_value_insert_into_set (EXP_GEN (block), result);
  
  		continue;
  	      }
*************** init_pre (bool do_fre)
*** 4515,4521 ****
        TMP_GEN (bb) = bitmap_set_new ();
        AVAIL_OUT (bb) = bitmap_set_new ();
      }
-   maximal_set = in_fre ? NULL : bitmap_set_new ();
  
    need_eh_cleanup = BITMAP_ALLOC (NULL);
  }
--- 4495,4500 ----
*************** execute_pre (bool do_fre ATTRIBUTE_UNUSE
*** 4601,4608 ****
  	  print_bitmap_set (dump_file, TMP_GEN (bb), "tmp_gen", bb->index);
  	  print_bitmap_set (dump_file, AVAIL_OUT (bb), "avail_out", bb->index);
  	}
- 
-       print_bitmap_set (dump_file, maximal_set, "maximal", 0);
      }
  
    /* Insert can get quite slow on an incredibly large number of basic
--- 4580,4585 ----
Index: gcc/testsuite/gcc.c-torture/compile/pr41101.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.c-torture/compile/pr41101.c	2009-09-09 11:36:27.000000000 +0200
***************
*** 0 ****
--- 1,19 ----
+ int func(int);
+ 
+ void
+ bug(int* x, int* y, unsigned long int N)
+ {
+   unsigned long int i;
+   int* t;
+ 
+   while (1)
+     {
+       for (i=1; i<=N; i++)
+ 	{
+ 	  y[i] = func(x[i] - x[1]);
+ 	  if (y[i])
+ 	    return;
+ 	}
+       t=x; x=y; y=t;
+     }
+ }


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