>
> visited is a poor name for a map ...
Hmm, visited_with_priority?
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 <[email protected]>
> SUSE / SUSE Labs
> SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
> GF: Jeff Hawn, Jennifer Guild, Felix Imend
