#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "tm_p.h"
#include "basic-block.h"
#include "gimple.h"
#include "gimple-ssa.h"
#include "tree-cfg.h"
#include "tree-phinodes.h"
#include "ssa-iterators.h"
#include "tree-ssa-loop-niter.h"
#include "tree-ssa-loop.h"
#include "tree-into-ssa.h"
#include "cfgloop.h"
#include "params.h"
#include "tree-pass.h"
#include "tree-inline.h"

Include dependency graph for tree-ssa-loop-unswitch.c:

Functions
static struct loop *	tree_unswitch_loop (struct loop *, basic_block, tree)
static bool	tree_unswitch_single_loop (struct loop *, int)
static tree	tree_may_unswitch_on (basic_block, struct loop *)
unsigned int	tree_ssa_unswitch_loops ()
static tree	tree_may_unswitch_on ()
static tree	simplify_using_entry_checks ()
static bool	tree_unswitch_single_loop ()
static unsigned int	tree_ssa_loop_unswitch ()
static bool	gate_tree_ssa_loop_unswitch ()
gimple_opt_pass *	make_pass_tree_unswitch ()

Function Documentation

static bool gate_tree_ssa_loop_unswitch ( )

static

gimple_opt_pass* make_pass_tree_unswitch ( )

static tree simplify_using_entry_checks ( )

static

Simplifies COND using checks in front of the entry of the LOOP. Just very simplish (sufficient to prevent us from duplicating loop in unswitching unnecessarily).

Referenced by tree_unswitch_single_loop().

static tree tree_may_unswitch_on	(	basic_block	,
		struct loop *
	)

static

Referenced by tree_unswitch_single_loop().

static tree tree_may_unswitch_on ( )

static

Checks whether we can unswitch LOOP on condition at end of BB – one of its basic blocks (for what it means see comments below).

 BB must end in a simple conditional jump.

 To keep the things simple, we do not directly remove the conditions,
 but just replace tests with 0 != 0 resp. 1 != 0.  Prevent the infinite
 loop where we would unswitch again on such a condition.

 Condition must be invariant.

static unsigned int tree_ssa_loop_unswitch ( )

static

Loop unswitching pass.

unsigned int tree_ssa_unswitch_loops ( )

Main entry point. Perform loop unswitching on all suitable loops.

 Go through inner loops (only original ones).

     Do not unswitch in cold regions.

     The loop should not be too large, to limit code growth.

     If the loop is not expected to iterate, there is no need
     for unswitching.

References dump_file, dump_flags, eni_size_weights, estimated_loop_iterations_int(), loop::num, optimize_loop_for_size_p(), PARAM_VALUE, TDF_DETAILS, tree_num_loop_insns(), and tree_unswitch_single_loop().

static struct loop * tree_unswitch_loop	(	struct loop *	loop,
		basic_block	unswitch_on,
		tree	cond
	)

staticread

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see http://www.gnu.org/licenses/. This file implements the loop unswitching, i.e. transformation of loops like

while (A) { if (inv) B;

X;

if (!inv) C; }

where inv is the loop invariant, into

if (inv) { while (A) { B; X; } } else { while (A) { X; C; } }

Inv is considered invariant iff the values it compares are both invariant; tree-ssa-loop-im.c ensures that all the suitable conditions are in this shape.

Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support unswitching of innermost loops. COND is the condition determining which loop is entered – the new loop is entered if COND is true. Returns NULL if impossible, new loop otherwise.

Some sanity checking.

static bool tree_unswitch_single_loop	(	struct loop *	,
		int
	)

static

Referenced by tree_ssa_unswitch_loops().

static bool tree_unswitch_single_loop ( )

static

Unswitch single LOOP. NUM is number of unswitchings done; we do not allow it to grow too much, it is too easy to create example on that the code would grow exponentially.

     Find a bb to unswitch on.

         Remove false path.

         Remove true path.

     Do not unswitch too much.

     In nested tree_unswitch_single_loop first optimize all conditions
     using entry checks, then discover still reachable blocks in the
     loop and find the condition only among those still reachable bbs.

     When called recursively, first do a quick discovery
     of reachable bbs after the above changes and only
     consider conditions in still reachable bbs.

     Start with marking header.

     Iterate: find everything reachable from what we've already seen
     within the same innermost loop.  Don't look through false edges
     if condition is always true or true edges if condition is
     always false.

     Find a bb to unswitch on.

 Unswitch the loop on this condition.

 Update the SSA form after unswitching.

 Invoke itself on modified loops.

References boolean_true_node, changed, dump_file, dump_flags, gimple_cond_set_condition_from_tree(), integer_nonzerop(), integer_zerop(), last_stmt(), loop::num_nodes, PARAM_VALUE, simplify_using_entry_checks(), TDF_DETAILS, tree_may_unswitch_on(), and update_stmt().

Functions

Function Documentation