Path to speed up flow_loop_tree_node_add
Michael Hayes
m.hayes@elec.canterbury.ac.nz
Fri Feb 11 20:08:00 GMT 2000
This patch avoids the quadratic worst case performance of the previous
algorithm. OK to commit?
Michael.
2000-02-12 Michael Hayes <m.hayes@elec.canterbury.ac.nz>
* flow.c (flow_loop_tree_node_add): Use better algorithm by passing
previously inserted node instead of root node. Caller changed.
Index: flow.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/flow.c,v
retrieving revision 1.219
diff -c -3 -p -r1.219 flow.c
*** flow.c 2000/02/10 16:45:22 1.219
--- flow.c 2000/02/12 03:49:36
*************** flow_loop_pre_header_find (header, dom)
*** 6716,6756 ****
}
! /* Add LOOP to the loop hierarchy tree so that it is a sibling or a
! descendant of ROOT. */
static void
! flow_loop_tree_node_add (root, loop)
! struct loop *root;
struct loop *loop;
{
- struct loop *outer;
! if (! loop)
! return;
! for (outer = root; outer; outer = outer->next)
{
! if (flow_loop_nested_p (outer, loop))
{
! if (outer->inner)
! {
! /* Add LOOP as a sibling or descendent of OUTER->INNER. */
! flow_loop_tree_node_add (outer->inner, loop);
! }
! else
! {
! /* Add LOOP as child of OUTER. */
! outer->inner = loop;
! loop->outer = outer;
! loop->next = NULL;
! }
return;
}
}
! /* Add LOOP as a sibling of ROOT. */
! loop->next = root->next;
! root->next = loop;
! loop->outer = root->outer;
}
--- 6715,6749 ----
}
! /* Add LOOP to the loop hierarchy tree where PREVLOOP was the loop
! previously added. The insertion algorithm assumes that the loops
! are added in the order found by a depth first search of the CFG. */
static void
! flow_loop_tree_node_add (prevloop, loop)
! struct loop *prevloop;
struct loop *loop;
{
! if (flow_loop_nested_p (prevloop, loop))
! {
! prevloop->inner = loop;
! loop->outer = prevloop;
! return;
! }
! while (prevloop->outer)
{
! if (flow_loop_nested_p (prevloop->outer, loop))
{
! prevloop->next = loop;
! loop->outer = prevloop->outer;
return;
}
+ prevloop = prevloop->outer;
}
!
! prevloop->next = loop;
! loop->outer = NULL;
}
*************** flow_loops_tree_build (loops)
*** 6774,6780 ****
/* Add the remaining loops to the tree. */
for (i = 1; i < num_loops; i++)
! flow_loop_tree_node_add (loops->tree, &loops->array[i]);
}
--- 6767,6773 ----
/* Add the remaining loops to the tree. */
for (i = 1; i < num_loops; i++)
! flow_loop_tree_node_add (&loops->array[i - 1], &loops->array[i]);
}
More information about the Gcc-patches
mailing list