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]

Fix regression on PR46590 (slow compile with -O0)


Hi,

the stack-var conflict generation code needs 13 (out of 34) seconds, with 
-O0 on the second testcase of PR46590.  Most of the time is spent in 
generating the same conflicts again and again at each basic block (the 
time right now is O(nr-of-bbs * N^2) where the number of conflicts is 
O(N^2)).

If we simply remember for which partitions we already generated the lower 
triangular conflict matrix we don't have to do that again, lowering the 
overall time to O(N^2).

This patch does that.  Time for variable expansion now is 0.4 seconds (of 
overall 22).

Regstrapping in progress on x86_64-linux, okay for trunk?


Ciao,
Michael.

	* cfgexpand.c (add_scope_conflicts_1): New old_conflicts argument,
	use it in remembering which conflicts we already created.
	(add_scope_conflicts): Adjust call to above, (de)allocate helper
	bitmap.

Index: cfgexpand.c
===================================================================
*** cfgexpand.c	(revision 183155)
--- cfgexpand.c	(working copy)
*************** visit_conflict (gimple stmt ATTRIBUTE_UN
*** 441,451 ****
  
  /* Helper routine for add_scope_conflicts, calculating the active partitions
     at the end of BB, leaving the result in WORK.  We're called to generate
!    conflicts when FOR_CONFLICT is true, otherwise we're just tracking
!    liveness.  */
  
  static void
! add_scope_conflicts_1 (basic_block bb, bitmap work, bool for_conflict)
  {
    edge e;
    edge_iterator ei;
--- 441,452 ----
  
  /* Helper routine for add_scope_conflicts, calculating the active partitions
     at the end of BB, leaving the result in WORK.  We're called to generate
!    conflicts when OLD_CONFLICTS is non-null, otherwise we're just tracking
!    liveness.  If we generate conflicts then OLD_CONFLICTS stores the bits
!    for which we generated conflicts already.  */
  
  static void
! add_scope_conflicts_1 (basic_block bb, bitmap work, bitmap old_conflicts)
  {
    edge e;
    edge_iterator ei;
*************** add_scope_conflicts_1 (basic_block bb, b
*** 482,488 ****
  	}
        else if (!is_gimple_debug (stmt))
  	{
! 	  if (for_conflict
  	      && visit == visit_op)
  	    {
  	      /* If this is the first real instruction in this BB we need
--- 483,489 ----
  	}
        else if (!is_gimple_debug (stmt))
  	{
! 	  if (old_conflicts
  	      && visit == visit_op)
  	    {
  	      /* If this is the first real instruction in this BB we need
*************** add_scope_conflicts_1 (basic_block bb, b
*** 490,505 ****
  		 Unlike classical liveness for named objects we can't
  		 rely on seeing a def/use of the names we're interested in.
  		 There might merely be indirect loads/stores.  We'd not add any
! 		 conflicts for such partitions.  */
  	      bitmap_iterator bi;
  	      unsigned i;
! 	      EXECUTE_IF_SET_IN_BITMAP (work, 0, i, bi)
  		{
  		  unsigned j;
  		  bitmap_iterator bj;
! 		  EXECUTE_IF_SET_IN_BITMAP (work, i + 1, j, bj)
  		    add_stack_var_conflict (i, j);
  		}
  	      visit = visit_conflict;
  	    }
  	  walk_stmt_load_store_addr_ops (stmt, work, visit, visit, visit);
--- 491,521 ----
  		 Unlike classical liveness for named objects we can't
  		 rely on seeing a def/use of the names we're interested in.
  		 There might merely be indirect loads/stores.  We'd not add any
! 		 conflicts for such partitions.  We know that we generated
! 		 conflicts between all partitions in old_conflicts already,
! 		 so we need to generate only the new ones, avoiding to
! 		 repeatedly pay the O(N^2) cost for each basic block.  */
  	      bitmap_iterator bi;
  	      unsigned i;
! 
! 	      /* First the conflicts between new and old_conflicts members.  */
! 	      EXECUTE_IF_AND_COMPL_IN_BITMAP (work, old_conflicts, 0, i, bi)
  		{
  		  unsigned j;
  		  bitmap_iterator bj;
! 		  EXECUTE_IF_SET_IN_BITMAP (old_conflicts, 0, j, bj)
  		    add_stack_var_conflict (i, j);
  		}
+ 	      /* Then the conflicts between only the new members.  */
+ 	      EXECUTE_IF_AND_COMPL_IN_BITMAP (work, old_conflicts, 0, i, bi)
+ 		{
+ 		  unsigned j;
+ 		  bitmap_iterator bj;
+ 		  EXECUTE_IF_AND_COMPL_IN_BITMAP (work, old_conflicts, 0, j, bj)
+ 		    add_stack_var_conflict (i, j);
+ 		}
+ 	      /* And remember for the next basic block.  */
+ 	      bitmap_ior_into (old_conflicts, work);
  	      visit = visit_conflict;
  	    }
  	  walk_stmt_load_store_addr_ops (stmt, work, visit, visit, visit);
*************** add_scope_conflicts (void)
*** 516,521 ****
--- 532,538 ----
    basic_block bb;
    bool changed;
    bitmap work = BITMAP_ALLOC (NULL);
+   bitmap old_conflicts;
  
    /* We approximate the live range of a stack variable by taking the first
       mention of its name as starting point(s), and by the end-of-scope
*************** add_scope_conflicts (void)
*** 537,551 ****
        FOR_EACH_BB (bb)
  	{
  	  bitmap active = (bitmap)bb->aux;
! 	  add_scope_conflicts_1 (bb, work, false);
  	  if (bitmap_ior_into (active, work))
  	    changed = true;
  	}
      }
  
    FOR_EACH_BB (bb)
!     add_scope_conflicts_1 (bb, work, true);
  
    BITMAP_FREE (work);
    FOR_ALL_BB (bb)
      BITMAP_FREE (bb->aux);
--- 554,571 ----
        FOR_EACH_BB (bb)
  	{
  	  bitmap active = (bitmap)bb->aux;
! 	  add_scope_conflicts_1 (bb, work, NULL);
  	  if (bitmap_ior_into (active, work))
  	    changed = true;
  	}
      }
  
+   old_conflicts = BITMAP_ALLOC (NULL);
+ 
    FOR_EACH_BB (bb)
!     add_scope_conflicts_1 (bb, work, old_conflicts);
  
+   BITMAP_FREE (old_conflicts);
    BITMAP_FREE (work);
    FOR_ALL_BB (bb)
      BITMAP_FREE (bb->aux);


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