Add GIMPLE switch support to loop unswitching

This patch adds support to unswitch loops with switch statements
based on invariant index.  It furthermore reworks the cost model
to allow an overall budget of statements to be created per original
loop by all unswitching opportunities in the loop.  Compared to
the original all unswitching opportunities in a loop are
pre-evaluated before the first transform which will allow future
changes to select the most profitable candidates first.

To efficiently support switch statements the pass now uses
ranger to simplify switch statements and conditions in loop
copies based on ranges extracted from the recorded set of
predicates unswitched.

gcc/ChangeLog:

	* dbgcnt.def (DEBUG_COUNTER): Add loop_unswitch counter.
	* params.opt (max-unswitch-level): Remove.
	* doc/invoke.texi (max-unswitch-level): Likewise.
	* tree-cfg.cc (gimple_lv_add_condition_to_bb): Support not
	gimplified expressions.
	* tree-ssa-loop-unswitch.cc (struct unswitch_predicate): New.
	(tree_may_unswitch_on): Rename to ...
	(find_unswitching_predicates_for_bb): ... this and handle
	switch statements.
	(get_predicates_for_bb): Likewise.
	(set_predicates_for_bb): Likewise.
	(init_loop_unswitch_info): Likewise.
	(tree_ssa_unswitch_loops): Prepare stuff before calling
	tree_unswitch_single_loop.
	(tree_unswitch_single_loop): Rework the function using
	pre-computed predicates and with a per original loop cost model.
	(merge_last): New.
	(add_predicate_to_path): Likewise.
	(find_range_for_lhs): Likewise.
	(simplify_using_entry_checks): Rename to ...
	(evaluate_control_stmt_using_entry_checks): ... this, handle
	switch statements and improve simplifications using ranger.
	(simplify_loop_version): Rework using
	evaluate_control_stmt_using_entry_checks.
	(evaluate_bbs): New.
	(evaluate_loop_insns_for_predicate): Likewise.
	(tree_unswitch_loop): Adjust to allow switch statements and
	pass in the edge to unswitch.
	(clean_up_after_unswitching): New.
	(pass_tree_unswitch::execute): Pass down fun.

gcc/testsuite/ChangeLog:

	* gcc.dg/loop-unswitch-7.c: New test.
	* gcc.dg/loop-unswitch-8.c: New test.
	* gcc.dg/loop-unswitch-9.c: New test.
	* gcc.dg/loop-unswitch-10.c: New test.
	* gcc.dg/loop-unswitch-11.c: New test.
	* gcc.dg/loop-unswitch-12.c: New test.
	* gcc.dg/loop-unswitch-13.c: New test.
	* gcc.dg/loop-unswitch-14.c: New test.
	* gcc.dg/loop-unswitch-15.c: New test.
	* gcc.dg/loop-unswitch-16.c: New test.
	* gcc.dg/loop-unswitch-17.c: New test.
	* gcc.dg/torture/20220518-1.c: New test.
	* gcc.dg/torture/20220518-2.c: New test.
	* gcc.dg/torture/20220525-1.c: New test.
	* gcc.dg/alias-10.c: Adjust.
	* gcc.dg/tree-ssa/loop-6.c: Likewise.
	* gcc.dg/loop-unswitch-1.c: Likewise.

Co-authored-by: Richard Biener  <rguenther@suse.de>

1 files changed, 0 insertions, 3 deletions

diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index a2f85f0..12f834f 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -14204,9 +14204,6 @@ The maximum depth of a loop nest suitable for complete peeling.
 @item max-unswitch-insns
 The maximum number of insns of an unswitched loop.
 
-@item max-unswitch-level
-The maximum number of branches unswitched in a single loop.
-
 @item lim-expensive
 The minimum cost of an expensive expression in the loop invariant motion.