[PATCH] Fix PR52808

[PATCH] Fix PR52808

[Richard Guenther]

This fixes LTO profiledbootstrap.  tracer tail-duplicates loop
headers; that is not profitable and it makes loops have multiple
entries which inhibits further optimization.  The following
patch cures that.

LTO profiledbootstrapped on x86_64-unknown-linux-gnu, regular
testing in progress.

Richard.

2012-04-04  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/52808
	* tracer.c (tail_duplicate): Do not tail-duplicate loop header
	blocks.
	* Makefile.in (tracer.o): Depend on $(CFGLOOP_H).

Index: gcc/tracer.c
===================================================================
*** gcc/tracer.c	(revision 186134)
--- gcc/tracer.c	(working copy)
***************
*** 52,57 ****
--- 52,58 ----
  #include "tree-pass.h"
  #include "tree-flow.h"
  #include "tree-inline.h"
+ #include "cfgloop.h"
  
  static int count_insns (basic_block);
  static bool ignore_bb_p (const_basic_block);
*************** tail_duplicate (void)
*** 307,313 ****
  	    }
  	  traced_insns += bb2->frequency * counts [bb2->index];
  	  if (EDGE_COUNT (bb2->preds) > 1
! 	      && can_duplicate_block_p (bb2))
  	    {
  	      edge e;
  	      basic_block copy;
--- 308,320 ----
  	    }
  	  traced_insns += bb2->frequency * counts [bb2->index];
  	  if (EDGE_COUNT (bb2->preds) > 1
! 	      && can_duplicate_block_p (bb2)
! 	      /* We have the tendency to duplicate the loop header
! 	         of all do { } while loops.  Do not do that - it is
! 		 not profitable and it might create a loop with multiple
! 		 entries or at least rotate the loop.  */
! 	      && (!current_loops
! 		  || bb2->loop_father->header != bb2))
  	    {
  	      edge e;
  	      basic_block copy;
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in	(revision 186134)
+++ gcc/Makefile.in	(working copy)
@@ -3391,7 +3391,7 @@ bb-reorder.o : bb-reorder.c $(CONFIG_H)
 tracer.o : tracer.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
    $(TREE_H) $(BASIC_BLOCK_H) hard-reg-set.h output.h $(CFGLAYOUT_H) \
    $(FLAGS_H) $(TIMEVAR_H) $(PARAMS_H) $(COVERAGE_H) $(FIBHEAP_H) \
-   $(TREE_PASS_H) $(TREE_FLOW_H) $(TREE_INLINE_H)
+   $(TREE_PASS_H) $(TREE_FLOW_H) $(TREE_INLINE_H) $(CFGLOOP_H)
 cfglayout.o : cfglayout.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    $(RTL_H) $(TREE_H) insn-config.h $(BASIC_BLOCK_H) hard-reg-set.h output.h \
    $(FUNCTION_H) $(CFGLAYOUT_H) $(CFGLOOP_H) $(TARGET_H) gt-cfglayout.h \

[PATCH] Fix PR52808

[Richard Guenther]

The following patch fixes PR52808 - the issue is as in the
duplicate_block fixme comment - if we are destroying a loop
by means of adding another entry we have to do that.  Thus
tracer needs to cleanup the cfg after it finished (a good idea
anyway).  And jump threading needs to tell cfg manipulation it
behaves well when threading a loop latch edge.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.

Richard.

2012-04-03  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/52808
	* tracer.c (tail_duplicate): Return whether we have duplicated
	any block.
	(tracer): If we have duplicated any block, cleanup the CFG.
	* cfghooks.c (duplicate_block): If we duplicated a loop
	header but not its loop, destroy the loop because it now has
	multiple entries.
	* tree-ssa-threadupdate.c (thread_through_loop_header): Tell
	the cfg manipulation routines we are not creating a multiple
	entry loop.

	* gcc.dg/pr52808.c: New testcase.

Index: gcc/tracer.c
===================================================================
--- gcc/tracer.c	(revision 186066)
+++ gcc/tracer.c	(working copy)
@@ -59,7 +59,6 @@ static bool better_p (const_edge, const_
 static edge find_best_successor (basic_block);
 static edge find_best_predecessor (basic_block);
 static int find_trace (basic_block, basic_block *);
-static void tail_duplicate (void);
 
 /* Minimal outgoing edge probability considered for superblock formation.  */
 static int probability_cutoff;
@@ -224,7 +223,7 @@ find_trace (basic_block bb, basic_block
 /* Look for basic blocks in frequency order, construct traces and tail duplicate
    if profitable.  */
 
-static void
+static bool
 tail_duplicate (void)
 {
   fibnode_t *blocks = XCNEWVEC (fibnode_t, last_basic_block);
@@ -236,6 +235,7 @@ tail_duplicate (void)
   gcov_type cover_insns;
   int max_dup_insns;
   basic_block bb;
+  bool changed = false;
 
   /* Create an oversized sbitmap to reduce the chance that we need to
      resize it.  */
@@ -332,6 +332,7 @@ tail_duplicate (void)
 			 bb2->index, copy->index, copy->frequency);
 
 	      bb2 = copy;
+	      changed = true;
 	    }
 	  mark_bb_seen (bb2);
 	  bb = bb2;
@@ -353,6 +354,8 @@ tail_duplicate (void)
   free (trace);
   free (counts);
   fibheap_delete (heap);
+
+  return changed;
 }
 
 /* Main entry point to this file.  */
@@ -360,6 +363,8 @@ tail_duplicate (void)
 static unsigned int
 tracer (void)
 {
+  bool changed;
+
   gcc_assert (current_ir_type () == IR_GIMPLE);
 
   if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
@@ -370,15 +375,14 @@ tracer (void)
     dump_flow_info (dump_file, dump_flags);
 
   /* Trace formation is done on the fly inside tail_duplicate */
-  tail_duplicate ();
+  changed = tail_duplicate ();
+  if (changed)
+    free_dominance_info (CDI_DOMINATORS);
 
-  /* FIXME: We really only need to do this when we know tail duplication
-            has altered the CFG. */
-  free_dominance_info (CDI_DOMINATORS);
   if (dump_file)
     dump_flow_info (dump_file, dump_flags);
 
-  return 0;
+  return changed ? TODO_cleanup_cfg : 0;
 }
 \f
 static bool
Index: gcc/cfghooks.c
===================================================================
--- gcc/cfghooks.c	(revision 186066)
+++ gcc/cfghooks.c	(working copy)
@@ -1009,18 +1009,28 @@ duplicate_block (basic_block bb, edge e,
     {
       struct loop *cloop = bb->loop_father;
       struct loop *copy = get_loop_copy (cloop);
-      add_bb_to_loop (new_bb, copy ? copy : cloop);
-      /* If we copied the loop latch block but not the loop, adjust
-	 loop state.
-	 ???  If we copied the loop header block but not the loop
-	 we might either have created a loop copy or a loop with
-	 multiple entries.  In both cases we probably have to
-	 ditch the loops and arrange for a fixup.  */
+      /* If we copied the loop header block but not the loop
+	 we have created a loop with multiple entries.  Ditch the loop,
+	 add the new block to the outer loop and arrange for a fixup.  */
       if (!copy
-	  && cloop->latch == bb)
+	  && cloop->header == bb)
 	{
+	  add_bb_to_loop (new_bb, loop_outer (cloop));
+	  cloop->header = NULL;
 	  cloop->latch = NULL;
-	  loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
+	  loops_state_set (LOOPS_NEED_FIXUP);
+	}
+      else
+	{
+	  add_bb_to_loop (new_bb, copy ? copy : cloop);
+	  /* If we copied the loop latch block but not the loop, adjust
+	     loop state.  */
+	  if (!copy
+	      && cloop->latch == bb)
+	    {
+	      cloop->latch = NULL;
+	      loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
+	    }
 	}
     }
 
Index: gcc/testsuite/gcc.dg/pr52808.c
===================================================================
--- gcc/testsuite/gcc.dg/pr52808.c	(revision 0)
+++ gcc/testsuite/gcc.dg/pr52808.c	(revision 0)
@@ -0,0 +1,12 @@
+/* { dg-do compile } */
+/* { dg-options "-O -ftracer" } */
+
+int **fn1 () __attribute__ ((__const__));
+int main ()
+{
+  int i;
+  i = 0;
+  for (;; i++)
+    if (*fn1 ()[i] && !'a' <= 0 && i <= 'z' || *fn1 ()[0] && 'a' <= 'z')
+      return;
+}
Index: gcc/tree-ssa-threadupdate.c
===================================================================
*** gcc/tree-ssa-threadupdate.c	(revision 186100)
--- gcc/tree-ssa-threadupdate.c	(working copy)
*************** thread_through_loop_header (struct loop
*** 1004,1011 ****
        basic_block *bblocks;
        unsigned nblocks, i;
  
!       /* First handle the case latch edge is redirected.  */
        loop->latch = thread_single_edge (latch);
        gcc_assert (single_succ (loop->latch) == tgt_bb);
        loop->header = tgt_bb;
  
--- 1004,1015 ----
        basic_block *bblocks;
        unsigned nblocks, i;
  
!       /* First handle the case latch edge is redirected.  We are copying
!          the loop header but not creating a multiple entry loop.  Make the
! 	 cfg manipulation code aware of that fact.  */
!       set_loop_copy (loop, loop);
        loop->latch = thread_single_edge (latch);
+       set_loop_copy (loop, NULL);
        gcc_assert (single_succ (loop->latch) == tgt_bb);
        loop->header = tgt_bb;