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