unswitch_predicate Struct Reference

Collaboration diagram for unswitch_predicate:

Public Member Functions
	unswitch_predicate (tree cond, tree lhs_, int edge_index_, edge e, const int_range_max &edge_range)
	unswitch_predicate (gcond *stmt)
void	copy_merged_ranges ()

Data Fields
tree	condition
tree	lhs
int_range_max	true_range = {}
int_range_max	false_range = {}
int_range_max	merged_true_range = {}
int_range_max	merged_false_range = {}
int	edge_index
profile_count	count
bool	switch_p
unsigned	num

Static Public Attributes
static vec< unswitch_predicate * > *	predicates

Detailed Description

Loop unswitching.
   Copyright (C) 2004-2024 Free Software Foundation, Inc.

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.cc ensures that all the suitable conditions are in this
shape.   

Loop unswitching algorithm for innermost loops works in the following steps:

1) Number of instructions is estimated for each BB that belongs to a loop.
2) Unswitching candidates are found for gcond and gswitch statements
   (note that an unswitching predicate for a gswitch actually corresponds
    to a non-default edge so it can contain multiple cases).
3) The so called unswitch predicates are stored in a cache where the
   gimple_uid of the last stmt in a basic-block is an index to the cache.
4) We consider one by one the unswitching candidates and calculate BBs that
   will be reachable in the unswitch version.
5) A selected predicate is chosen and we simplify the CFG (dead edges) in
   both versions of the loop.  We utilize both Ranger for condition
   simplification and also symbol equivalence.  The folded if conditions
   are replaced with true/false values, while for gswitch we mark the
   corresponding edges with a pass-defined unreachable flag.
6) Every time we unswitch a loop, we save unswitch_predicate to a vector
   together with information if true or false edge was taken.  Doing that
   we have a so called PREDICATE_PATH that is utilized for simplification
   of the cloned loop.
7) The process is repeated until we reach a growth threshold or all
   unswitching opportunities are taken.   

A tuple that holds a GENERIC condition and value range for an unswitching
predicate.   

Constructor & Destructor Documentation

unswitch_predicate() [1/2]

unswitch_predicate::unswitch_predicate ( tree cond, tree lhs_, int edge_index_, edge e, const int_range_max & edge_range )

inline

References count, false_range, gcc_assert, irange::invert(), lhs, num, predicates, irange::supports_p(), TREE_TYPE, true_range, vrange::undefined_p(), and vrange::varying_p().

unswitch_predicate() [2/2]

unswitch_predicate::unswitch_predicate ( gcond * stmt )

inline

References boolean_type_node, build2(), CONSTANT_CLASS_P, count, edge_index, EDGE_SUCC, false_range, gimple_bb(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), lhs, profile_count::max(), num, predicates, range_false(), range_true(), irange::set(), irange::set_varying(), irange::supports_p(), wi::to_wide(), TREE_TYPE, and true_range.

Member Function Documentation

copy_merged_ranges()

void unswitch_predicate::copy_merged_ranges ( )

inline

References false_range, merged_false_range, merged_true_range, and true_range.

Field Documentation

condition

tree unswitch_predicate::condition

count

profile_count unswitch_predicate::count

Referenced by find_unswitching_predicates_for_bb(), unswitch_predicate(), and unswitch_predicate().

edge_index

int unswitch_predicate::edge_index

Referenced by unswitch_predicate().

false_range

int_range_max unswitch_predicate::false_range = {}

Referenced by copy_merged_ranges(), unswitch_predicate(), and unswitch_predicate().

lhs

tree unswitch_predicate::lhs

Referenced by unswitch_predicate(), and unswitch_predicate().

merged_false_range

int_range_max unswitch_predicate::merged_false_range = {}

Referenced by copy_merged_ranges().

merged_true_range

int_range_max unswitch_predicate::merged_true_range = {}

Referenced by copy_merged_ranges().

num

unsigned unswitch_predicate::num

Referenced by unswitch_predicate(), and unswitch_predicate().

predicates

vec< unswitch_predicate * > * unswitch_predicate::predicates

static

Referenced by tree_ssa_unswitch_loops(), unswitch_predicate(), and unswitch_predicate().

switch_p

bool unswitch_predicate::switch_p

true_range

int_range_max unswitch_predicate::true_range = {}

Referenced by copy_merged_ranges(), unswitch_predicate(), and unswitch_predicate().

---

The documentation for this struct was generated from the following file:

• tree-ssa-loop-unswitch.cc