From a2f6018f329c3629795c2006ba6684b083c19fcb Mon Sep 17 00:00:00 2001 From: Jeff Law Date: Mon, 19 Oct 2015 10:24:00 -0600 Subject: [PATCH] [PATCH] Don't allow FSM threader to create irreducible loops unless it eliminates a multi-way branch * tree-ssa-threadupdate.c (valid_jump_thread_path): Reject paths that create irreducible loops unless the path elimiantes a multiway branch. From-SVN: r228974 --- gcc/ChangeLog | 6 ++++++ gcc/tree-ssa-threadupdate.c | 30 ++++++++++++++++++++++++++---- 2 files changed, 32 insertions(+), 4 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 89a42c1..ff3d3fc 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,9 @@ +2015-10-19 Jeff Law + + * tree-ssa-threadupdate.c (valid_jump_thread_path): Reject paths + that create irreducible loops unless the path elimiantes a multiway + branch. + 2015-10-19 Richard Biener PR tree-optimization/67975 diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c index 5632a88..8e3437a 100644 --- a/gcc/tree-ssa-threadupdate.c +++ b/gcc/tree-ssa-threadupdate.c @@ -2553,11 +2553,31 @@ static bool valid_jump_thread_path (vec *path) { unsigned len = path->length (); + bool multiway_branch = false; - /* Check that the path is connected. */ + /* Check that the path is connected and see if there's a multi-way + branch on the path. */ for (unsigned int j = 0; j < len - 1; j++) - if ((*path)[j]->e->dest != (*path)[j+1]->e->src) - return false; + { + if ((*path)[j]->e->dest != (*path)[j+1]->e->src) + return false; + gimple *last = last_stmt ((*path)[j]->e->dest); + multiway_branch |= (last && gimple_code (last) == GIMPLE_SWITCH); + } + + /* If we are trying to thread the loop latch to a block that does + not dominate the loop latch, then that will create an irreducible + loop. We avoid that unless the jump thread has a multi-way + branch, in which case we have deemed it worth losing other + loop optimizations later if we can eliminate the multi-way branch. */ + edge e = (*path)[0]->e; + struct loop *loop = e->dest->loop_father; + if (!multiway_branch + && loop->latch + && loop_latch_edge (loop) == e + && (determine_bb_domination_status (loop, path->last ()->e->dest) + == DOMST_NONDOMINATING)) + return false; return true; } @@ -2650,7 +2670,9 @@ thread_through_all_blocks (bool may_peel_loop_headers) if (bitmap_bit_p (threaded_blocks, entry->src->index) /* Verify that the jump thread path is still valid: a previous jump-thread may have changed the CFG, and - invalidated the current path. */ + invalidated the current path or the requested jump + thread might create irreducible loops which should + generally be avoided. */ || !valid_jump_thread_path (path)) { /* Remove invalid FSM jump-thread paths. */ -- 2.7.4