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: Non-dominating loop bounds in tree-ssa-loop-niter 2/4


On Wed, 31 Oct 2012, Jan Hubicka wrote:

> > 
> > visited is a poor name for a map ...
> Hmm, visited_with_priority?

Just block_priority?

Richard.

> Thanks,
> Honza
> > 
> > Otherwise looks ok.
> > 
> > Thanks,
> > Richard.
> > 
> > > +
> > > +  /* Perform shortest path discovery loop->header ... loop->latch.
> > > +
> > > +     The "distance" is given by the smallest loop bound of basic block
> > > +     present in the path and we look for path with largest smallest bound
> > > +     on it.
> > > +
> > > +     To avoid the need for fibonaci heap on double ints we simply compress
> > > +     double ints into indexes to BOUNDS array and then represent the queue
> > > +     as arrays of queues for every index.
> > > +     Index of VEC_length (BOUNDS) means that the execution of given BB has
> > > +     no bounds determined.
> > > +
> > > +     VISITED is a pointer map translating basic block into smallest index
> > > +     it was inserted into the priority queue with.  */
> > > +  latch_index = -1;
> > > +
> > > +  /* Start walk in loop header with index set to infinite bound.  */
> > > +  queue_index = VEC_length (double_int, bounds);
> > > +  VEC_safe_grow_cleared (bb_queue, heap, queues, queue_index + 1);
> > > +  VEC_safe_push (basic_block, heap, queue, loop->header);
> > > +  VEC_replace (bb_queue, queues, queue_index, queue);
> > > +  *pointer_map_insert (visited, loop->header) = (void *)queue_index;
> > > +
> > > +  for (; queue_index >= 0; queue_index--)
> > > +    {
> > > +      if (latch_index < queue_index)
> > > +	{
> > > +	  while (VEC_length (basic_block,
> > > +			     VEC_index (bb_queue, queues, queue_index)))
> > > +	    {
> > > +	      basic_block bb;
> > > +	      ptrdiff_t bound_index = queue_index;
> > > +	      void **entry;
> > > +              edge e;
> > > +              edge_iterator ei;
> > > +
> > > +	      queue = VEC_index (bb_queue, queues, queue_index);
> > > +	      bb = VEC_pop (basic_block, queue);
> > > +
> > > +	      /* OK, we later increased BB priority, skip it.  */
> > > +	      if ((ptrdiff_t)*pointer_map_contains (visited, bb) > queue_index)
> > > +		continue;
> > > +
> > > +	      /* See if we can improve the bound.  */
> > > +	      entry = pointer_map_contains (bb_bounds, bb);
> > > +	      if (entry && (ptrdiff_t)*entry < bound_index)
> > > +		bound_index = (ptrdiff_t)*entry;
> > > +
> > > +	      /* Insert succesors into the queue, watch for latch edge
> > > +		 and record greatest index we saw.  */
> > > +	      FOR_EACH_EDGE (e, ei, bb->succs)
> > > +		{
> > > +		  bool insert = false;
> > > +		  void **entry;
> > > +
> > > +		  if (loop_exit_edge_p (loop, e))
> > > +		    continue;
> > > +
> > > +		  if (e == loop_latch_edge (loop)
> > > +		      && latch_index < bound_index)
> > > +		    latch_index = bound_index;
> > > +		  else if (!(entry = pointer_map_contains (visited, e->dest)))
> > > +		    {
> > > +		      insert = true;
> > > +		      *pointer_map_insert (visited, e->dest) = (void *)bound_index;
> > > +		    }
> > > +		  else if ((ptrdiff_t)*entry < bound_index)
> > > +		    {
> > > +		      insert = true;
> > > +		      *entry = (void *)bound_index;
> > > +		    }
> > > +		    
> > > +		  if (insert)
> > > +		    {
> > > +		      bb_queue queue2 = VEC_index (bb_queue, queues, bound_index);
> > > +		      VEC_safe_push (basic_block, heap, queue2, e->dest);
> > > +		      VEC_replace (bb_queue, queues, bound_index, queue2);
> > > +		    }
> > > +		}
> > > +	    }
> > > +	}
> > > +      else
> > > +	VEC_free (basic_block, heap, VEC_index (bb_queue, queues, queue_index));
> > > +    }
> > > +
> > > +  gcc_assert (latch_index >= 0);
> > > +  if (latch_index < VEC_length (double_int, bounds))
> > > +    {
> > > +      if (dump_file && (dump_flags & TDF_DETAILS))
> > > +	{
> > > +	  fprintf (dump_file, "Found better loop bound ");
> > > +	  dump_double_int (dump_file,
> > > +			   VEC_index (double_int, bounds, latch_index), true);
> > > +	  fprintf (dump_file, "\n");
> > > +	}
> > > +      record_niter_bound (loop, VEC_index (double_int, bounds, latch_index),
> > > +			  false, true);
> > > +    }
> > > +
> > > +  VEC_free (bb_queue, heap, queues);
> > > +  pointer_map_destroy (bb_bounds);
> > > +  pointer_map_destroy (visited);
> > > +}
> > > +
> > >  /* See if every path cross the loop goes through a statement that is known
> > >     to not execute at the last iteration. In that case we can decrese iteration
> > >     count by 1.  */
> > > @@ -3102,6 +3330,8 @@ estimate_numbers_of_iterations_loop (str
> > >  
> > >    infer_loop_bounds_from_undefined (loop);
> > >  
> > > +  discover_iteration_bound_by_body_walk (loop);
> > > +
> > >    maybe_lower_iteration_bound (loop);
> > >  
> > >    /* If we have a measured profile, use it to estimate the number of
> > > Index: testsuite/gcc.dg/tree-ssa/loop-38.c
> > > ===================================================================
> > > --- testsuite/gcc.dg/tree-ssa/loop-38.c	(revision 0)
> > > +++ testsuite/gcc.dg/tree-ssa/loop-38.c	(revision 0)
> > > @@ -0,0 +1,18 @@
> > > +/* { dg-do compile } */
> > > +/* { dg-options "-O2 -fdump-tree-cunrolli-details" } */
> > > +int a[10];
> > > +int b[11];
> > > +t(int n)
> > > +{
> > > +   int i;
> > > +   int sum = 0;
> > > +   for (i=0;i<n;i++)
> > > +     if (q())
> > > +	sum+=a[i];
> > > +     else
> > > +	sum+=b[i];
> > > +  return sum;
> > > +}
> > > +/* { dg-final { scan-tree-dump "Found better loop bound 11" "cunrolli" } } */
> > > +/* { dg-final { scan-tree-dump "Loop 1 iterates at most 11 times" "cunrolli" } } */
> > > +/* { dg-final { cleanup-tree-dump "cunrolli" } } */
> > > 
> > > 
> > 
> > -- 
> > Richard Biener <rguenther@suse.de>
> > SUSE / SUSE Labs
> > SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
> > GF: Jeff Hawn, Jennifer Guild, Felix Imend
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend


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