From 5da257fd4f00f94b37628c24ce1ef2f208bff065 Mon Sep 17 00:00:00 2001 From: Andreas Zwinkau Date: Tue, 22 Feb 2011 10:24:27 +0000 Subject: [PATCH] Fix beabi call sorting Difference of idx for Calls with no order relation is stable, but may lead to circular dependencies. Fixed by looking at the heights first. Fixes backend/transform_loop.c (with -O0) [r28436] --- ir/be/beabi.c | 12 +++++++++++- 1 file changed, 11 insertions(+), 1 deletion(-) diff --git a/ir/be/beabi.c b/ir/be/beabi.c index e5eb80f5b..3348a695e 100644 --- a/ir/be/beabi.c +++ b/ir/be/beabi.c @@ -979,6 +979,7 @@ static int cmp_call_dependency(const void *c1, const void *c2) { ir_node *n1 = *(ir_node **) c1; ir_node *n2 = *(ir_node **) c2; + unsigned h1, h2; /* Classical qsort() comparison function behavior: @@ -993,7 +994,16 @@ static int cmp_call_dependency(const void *c1, const void *c2) return 1; /* The nodes have no depth order, but we need a total order because qsort() - * is not stable. */ + * is not stable. + * + * Additionally, we need to respect transitive dependencies. Consider a + * Call a depending on Call b and an independent Call c. + * We MUST NOT order c > a and b > c. */ + h1 = get_irn_height(ir_heights, n1); + h2 = get_irn_height(ir_heights, n2); + if (h1 < h2) return -1; + if (h1 > h2) return 1; + /* Same height, so use a random (but stable) order */ return get_irn_idx(n1) - get_irn_idx(n2); } -- 2.20.1