GCC Middle and Back End API Reference
uninit_analysis Class Reference

#include <gimple-predicate-analysis.h>

Collaboration diagram for uninit_analysis:

Data Structures

struct  func_t
 

Public Member Functions

 uninit_analysis (func_t &eval)
 
 uninit_analysis (const uninit_analysis &rhs)=delete
 
uninit_analysisoperator= (const uninit_analysis &)=delete
 
bool is_use_guarded (gimple *, basic_block, gphi *, unsigned)
 

Private Member Functions

bool is_use_guarded (gimple *, basic_block, gphi *, unsigned, hash_set< gphi * > *)
 
bool prune_phi_opnds (gphi *, unsigned, gphi *, tree, tree_code, hash_set< gphi * > *, bitmap *)
 
bool overlap (gphi *, unsigned, hash_set< gphi * > *, const predicate &)
 
void collect_phi_def_edges (gphi *, basic_block, vec< edge > *, hash_set< gimple * > *)
 
bool init_from_phi_def (gphi *)
 
bool init_use_preds (predicate &, basic_block, basic_block)
 

Private Attributes

predicate m_phi_def_preds
 
func_tm_eval
 

Detailed Description

Represents a complex Boolean predicate expression.   

Constructor & Destructor Documentation

◆ uninit_analysis() [1/2]

uninit_analysis::uninit_analysis ( func_t & eval)
inline

◆ uninit_analysis() [2/2]

uninit_analysis::uninit_analysis ( const uninit_analysis & rhs)
delete

Member Function Documentation

◆ collect_phi_def_edges()

void uninit_analysis::collect_phi_def_edges ( gphi * phi,
basic_block cd_root,
vec< edge > * edges,
hash_set< gimple * > * visited )
private
Recursively compute the set PHI's incoming edges with "uninteresting"
operands of a phi chain, i.e., those for which EVAL returns false.
CD_ROOT is the control dependence root from which edges are collected
up the CFG nodes that it's dominated by.  *EDGES holds the result, and
VISITED is used for detecting cycles.   

References as_a(), CDI_DOMINATORS, collect_phi_def_edges(), DEBUG_PREDICATE_ANALYZER, dominated_by_p(), dump_file, dump_flags, gimple_bb(), gimple_phi_arg_def(), gimple_phi_arg_edge(), gimple_phi_num_args(), i, basic_block_def::index, m_eval, MASK_TEST_BIT, uninit_analysis::func_t::phi_arg_set(), print_gimple_stmt(), SSA_NAME_DEF_STMT, TDF_DETAILS, TREE_CODE, and visited.

Referenced by collect_phi_def_edges(), and init_from_phi_def().

◆ init_from_phi_def()

bool uninit_analysis::init_from_phi_def ( gphi * phi)
private
For each use edge of PHI, compute all control dependence chains
and convert those to the composite predicates in M_PREDS.
Return true if a nonempty predicate has been obtained.   

References CDI_DOMINATORS, cfun, collect_phi_def_edges(), compute_control_dep_chain(), dfs_mark_dominating_region(), EDGE_COUNT, gcc_assert, get_immediate_dominator(), gimple_bb(), i, predicate::init_from_control_deps(), predicate::is_empty(), m_phi_def_preds, MAX_NUM_CHAINS, MIN, n_basic_blocks_for_fn, and vNULL.

Referenced by is_use_guarded().

◆ init_use_preds()

bool uninit_analysis::init_use_preds ( predicate & use_preds,
basic_block def_bb,
basic_block use_bb )
private
Initialize USE_PREDS with the predicates of the control dependence chains
between the basic block DEF_BB that defines a variable of interst and
USE_BB that uses the variable, respectively.   

References CDI_DOMINATORS, CDI_POST_DOMINATORS, cfun, compute_control_dep_chain(), DEBUG_PREDICATE_ANALYZER, dfs_mark_dominating_region(), dominated_by_p(), dump_file, gcc_assert, get_immediate_dominator(), basic_block_def::index, predicate::init_from_control_deps(), predicate::is_empty(), MAX_NUM_CHAINS, MIN, n_basic_blocks_for_fn, simple_control_dep_chain(), single_pred_p(), and single_succ_p().

Referenced by is_use_guarded().

◆ is_use_guarded() [1/2]

bool uninit_analysis::is_use_guarded ( gimple * stmt,
basic_block use_bb,
gphi * phi,
unsigned opnds )
Public interface to the above.  

References is_use_guarded(), and visited.

Referenced by find_uninit_use(), is_use_guarded(), and prune_phi_opnds().

◆ is_use_guarded() [2/2]

bool uninit_analysis::is_use_guarded ( gimple * use_stmt,
basic_block use_bb,
gphi * phi,
unsigned opnds,
hash_set< gphi * > * visited )
private
Compute the predicates that guard the use USE_STMT and check if
the incoming paths that have an empty (or possibly empty) definition
can be pruned.  Return true if it can be determined that the use of
PHI's def in USE_STMT is guarded by a predicate set that does not
overlap with the predicate sets of all runtime paths that do not
have a definition.

Return false if the use is not guarded or if it cannot be determined.
USE_BB is the bb of the use (for phi operand use, the bb is not the bb
of the phi stmt, but the source bb of the operand edge).

OPNDS is a bitmap with a bit set for each PHI operand of interest.

THIS->M_PREDS contains the (memoized) defining predicate chains of
a PHI.  If THIS->M_PREDS is empty, the PHI's defining predicate
chains are computed and stored into THIS->M_PREDS as needed.

VISITED_PHIS is a pointer set of phis being visited.   

References DEBUG_PREDICATE_ANALYZER, dump_file, gimple_bb(), init_from_phi_def(), init_use_preds(), predicate::is_empty(), predicate::is_false(), predicate::is_true(), m_phi_def_preds, predicate::normalize(), overlap(), predicate::simplify(), predicate::superset_of(), and visited.

◆ operator=()

uninit_analysis & uninit_analysis::operator= ( const uninit_analysis & )
delete

◆ overlap()

bool uninit_analysis::overlap ( gphi * phi,
unsigned opnds,
hash_set< gphi * > * visited,
const predicate & use_preds )
private
Determine if the predicate set of the use does not overlap with that
of the interesting paths.  The most common senario of guarded use is
in Example 1:
  Example 1:
        if (some_cond)
        {
           x = ...;   // set x to valid
           flag = true;
        }

         ... some code ...

        if (flag)
           use (x);   // use when x is valid

  The real world examples are usually more complicated, but similar
  and usually result from inlining:

      bool init_func (int * x)
      {
          if (some_cond)
        return false;
          *x  =  ...;   // set *x to valid
          return true;
      }

      void foo (..)
      {
          int x;

          if (!init_func (&x))
        return;

          .. some_code ...
          use (x);      // use when x is valid
      }

  Another possible use scenario is in the following trivial example:

  Example 2:
       if (n > 0)
          x = 1;
       ...
       if (n > 0)
         {
           if (m < 2)
         ... = x;
         }

  Predicate analysis needs to compute the composite predicate:

    1) 'x' use predicate: (n > 0) .AND. (m < 2)
    2) 'x' default value  (non-def) predicate: .NOT. (n > 0)
    (the predicate chain for phi operand defs can be computed
    starting from a bb that is control equivalent to the phi's
    bb and is dominating the operand def.)

    and check overlapping:
       (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
     <==> false

  This implementation provides a framework that can handle different
  scenarios.  (Note that many simple cases are handled properly without
  the predicate analysis if jump threading eliminates the merge point
  thus makes path-sensitive analysis unnecessary.)

  PHI is the phi node whose incoming (undefined) paths need to be
  pruned, and OPNDS is the bitmap holding interesting operand
  positions.  VISITED is the pointer set of phi stmts being
  checked.   

References as_a(), BITMAP_FREE, predicate::chain(), find_var_cmp_const(), i, NULL, NULL_TREE, prune_phi_opnds(), and visited.

Referenced by is_use_guarded().

◆ prune_phi_opnds()

bool uninit_analysis::prune_phi_opnds ( gphi * phi,
unsigned opnds,
gphi * flag_def,
tree boundary_cst,
tree_code cmp_code,
hash_set< gphi * > * visited_phis,
bitmap * visited_flag_phis )
private
Return true if all interesting opnds are pruned, false otherwise.
PHI is the phi node with interesting operands, OPNDS is the bitmap
of the interesting operand positions, FLAG_DEF is the statement
defining the flag guarding the use of the PHI output, BOUNDARY_CST
is the const value used in the predicate associated with the flag,
CMP_CODE is the comparison code used in the predicate, VISITED_PHIS
is the pointer set of phis visited, and VISITED_FLAG_PHIS is
the pointer to the pointer set of flag definitions that are also
phis.

Example scenario:

BB1:
  flag_1 = phi <0, 1>                   // (1)
  var_1  = phi <undef, some_val>


BB2:
  flag_2 = phi <0,   flag_1, flag_1>            // (2)
  var_2  = phi <undef, var_1, var_1>
  if (flag_2 == 1)
    goto BB3;

BB3:
  use of var_2                          // (3)

Because some flag arg in (1) is not constant, if we do not look into
the flag phis recursively, it is conservatively treated as unknown and
var_1 is thought to flow into use at (3).  Since var_1 is potentially
uninitialized a false warning will be emitted.
Checking recursively into (1), the compiler can find out that only
some_val (which is defined) can flow into (3) which is OK.   

References BITMAP_ALLOC, bitmap_bit_p, bitmap_clear_bit(), bitmap_set_bit, dyn_cast(), gimple_bb(), gimple_phi_arg_def(), gimple_phi_arg_edge(), gimple_phi_num_args(), gimple_phi_result(), i, is_gimple_constant(), is_use_guarded(), is_value_included_in(), m_eval, MASK_EMPTY, MASK_TEST_BIT, uninit_analysis::func_t::max_phi_args, MIN, NULL, uninit_analysis::func_t::phi_arg_set(), prune_phi_opnds(), SSA_NAME_DEF_STMT, SSA_NAME_VERSION, and TREE_CODE.

Referenced by overlap(), and prune_phi_opnds().

Field Documentation

◆ m_eval

func_t& uninit_analysis::m_eval
private

◆ m_phi_def_preds

predicate uninit_analysis::m_phi_def_preds
private

The documentation for this class was generated from the following files: