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