GCC Middle and Back End API Reference
stmt.c File Reference

Data Structures

struct  case_node

Typedefs

typedef struct case_node case_node
typedef struct case_nodecase_node_ptr

Functions

basic_block label_to_block_fn (struct function *, tree)
static int n_occurrences (int, const char *)
static bool tree_conflicts_with_clobbers_p (tree, HARD_REG_SET *)
static bool check_operand_nalternatives (tree, tree)
static bool check_unique_operand_names (tree, tree, tree)
static char * resolve_operand_name_1 (char *, tree, tree, tree)
static void expand_null_return_1 (void)
static void expand_value_return (rtx)
static void balance_case_nodes (case_node_ptr *, case_node_ptr)
static int node_has_low_bound (case_node_ptr, tree)
static int node_has_high_bound (case_node_ptr, tree)
static int node_is_bounded (case_node_ptr, tree)
static void emit_case_nodes (rtx, case_node_ptr, rtx, int, tree)
rtx label_rtx ()
rtx force_label_rtx ()
void emit_jump ()
void expand_computed_goto ()
void expand_label ()
void expand_goto ()
static int n_occurrences ()
static void expand_asm_loc ()
bool parse_output_constraint (const char **constraint_p, int operand_num, int ninputs, int noutputs, bool *allows_mem, bool *allows_reg, bool *is_inout)
bool parse_input_constraint (const char **constraint_p, int input_num, int ninputs, int noutputs, int ninout, const char *const *constraints, bool *allows_mem, bool *allows_reg)
static tree decl_overlaps_hard_reg_set_p (tree *declp, int *walk_subtrees, void *data)
tree tree_overlaps_hard_reg_set ()
static bool tree_conflicts_with_clobbers_p ()
static void expand_asm_operands (tree string, tree outputs, tree inputs, tree clobbers, tree labels, int vol, location_t locus)
void expand_asm_stmt ()
static bool check_operand_nalternatives ()
static bool check_unique_operand_names ()
tree resolve_asm_operand_names ()
static char * resolve_operand_name_1 ()
void expand_null_return ()
void expand_naked_return ()
static void expand_value_return ()
void expand_return ()
rtx expand_stack_save ()
void expand_stack_restore ()
static void do_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label, int unsignedp, int prob)
static struct case_nodeadd_case_node (struct case_node *head, tree low, tree high, tree label, int prob, alloc_pool case_node_pool)
static void dump_case_nodes (FILE *f, struct case_node *root, int indent_step, int indent_level)
static unsigned int case_values_threshold ()
static bool expand_switch_as_decision_tree_p (tree range, unsigned int uniq, unsigned int count)
static void emit_case_decision_tree (tree index_expr, tree index_type, struct case_node *case_list, rtx default_label, int default_prob)
static int get_outgoing_edge_probs ()
static int conditional_probability ()
static void emit_case_dispatch_table (tree index_expr, tree index_type, struct case_node *case_list, rtx default_label, tree minval, tree maxval, tree range, basic_block stmt_bb)
static void reset_out_edges_aux ()
static void compute_cases_per_edge ()
void expand_case ()
void expand_sjlj_dispatch_table (rtx dispatch_index, vec< tree > dispatch_table)
static void balance_case_nodes ()
static int node_has_low_bound ()
static int node_has_high_bound ()
static int node_is_bounded ()

Typedef Documentation

typedef struct case_node case_node
typedef struct case_node* case_node_ptr

Function Documentation

static struct case_node* add_case_node ( struct case_node head,
tree  low,
tree  high,
tree  label,
int  prob,
alloc_pool  case_node_pool 
)
staticread
Do the insertion of a case label into case_list.  The labels are
   fed to us in descending order from the sorted vector of case labels used
   in the tree part of the middle end.  So the list we construct is
   sorted in ascending order.
   
   LABEL is the case label to be inserted. LOW and HIGH are the bounds
   against which the index is compared to jump to LABEL and PROB is the
   estimated probability LABEL is reached from the switch statement.   

References case_node::code_label, case_node::high, case_node::left, case_node::low, case_node::parent, pool_alloc(), case_node::prob, prob, case_node::right, and case_node::subtree_prob.

Referenced by expand_case(), and expand_sjlj_dispatch_table().

static void balance_case_nodes ( case_node_ptr ,
case_node_ptr   
)
static
static void balance_case_nodes ( )
static
Take an ordered list of case nodes
   and transform them into a near optimal binary tree,
   on the assumption that any target code selection value is as
   likely as any other.

   The transformation is performed by splitting the ordered
   list into two equal sections plus a pivot.  The parts are
   then attached to the pivot as left and right branches.  Each
   branch is then transformed recursively.   

References balance_case_nodes(), case_node::high, case_node::left, case_node::low, case_node::parent, case_node::prob, case_node::right, case_node::subtree_prob, and tree_int_cst_equal().

static unsigned int case_values_threshold ( )
static
Return the smallest number of different values for which it is best to use a
   jump-table instead of a tree of conditional branches.   

References targetm.

Referenced by expand_switch_as_decision_tree_p().

static bool check_operand_nalternatives ( tree  ,
tree   
)
static

Referenced by expand_asm_operands().

static bool check_operand_nalternatives ( )
static
A subroutine of expand_asm_operands.  Check that all operands have
   the same number of alternatives.  Return true if so.   

References error(), and n_occurrences.

static bool check_unique_operand_names ( tree  ,
tree  ,
tree   
)
static
static bool check_unique_operand_names ( )
static
A subroutine of expand_asm_operands.  Check that all operand names
   are unique.  Return true if so.  We rely on the fact that these names
   are identifiers, and so have been canonicalized by get_identifier,
   so all we need are pointer comparisons.   

References error(), failure, and simple_cst_equal().

static void compute_cases_per_edge ( )
inlinestatic
Compute the number of case labels that correspond to each outgoing edge of
   STMT. Record this information in the aux field of the edge.   

References edge_def::aux, cfun, find_edge(), gimple_bb(), gimple_switch_label(), gimple_switch_num_labels(), label_to_block_fn(), and reset_out_edges_aux().

Referenced by expand_case().

static int conditional_probability ( )
inlinestatic
Computes the conditional probability of jumping to a target if the branch
   instruction is executed.
   TARGET_PROB is the estimated probability of jumping to a target relative
   to some basic block BB.
   BASE_PROB is the probability of reaching the branch instruction relative
   to the same basic block BB.   

Referenced by emit_case_dispatch_table(), and emit_case_nodes().

static tree decl_overlaps_hard_reg_set_p ( tree declp,
int *  walk_subtrees,
void *  data 
)
static
Return DECL iff there's an overlap between *REGS and DECL, where DECL
   can be an asm-declared register.  Called via walk_tree.   

References overlaps_hard_reg_set_p().

Referenced by tree_overlaps_hard_reg_set().

static void do_jump_if_equal ( enum machine_mode  mode,
rtx  op0,
rtx  op1,
rtx  label,
int  unsignedp,
int  prob 
)
static
Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. PROB
   is the probability of jumping to LABEL.   

References do_compare_rtx_and_jump().

Referenced by emit_case_nodes(), and expand_sjlj_dispatch_table().

static void dump_case_nodes ( FILE *  f,
struct case_node root,
int  indent_step,
int  indent_level 
)
static
Dump ROOT, a list or tree of case nodes, to file.   

References case_node::high, HOST_WIDE_INT, HOST_WIDE_INT_PRINT_DEC, case_node::left, case_node::low, case_node::right, and tree_low_cst().

Referenced by emit_case_decision_tree().

static void emit_case_decision_tree ( tree  index_expr,
tree  index_type,
struct case_node case_list,
rtx  default_label,
int  default_prob 
)
static
Generate a decision tree, switching on INDEX_EXPR and jumping to
   one of the labels in CASE_LIST or to the DEFAULT_LABEL.
   DEFAULT_PROB is the estimated probability that it jumps to
   DEFAULT_LABEL.
   
   We generate a binary decision tree to select the appropriate target
   code.  This is done as follows:

     If the index is a short or char that we do not have
     an insn to handle comparisons directly, convert it to
     a full integer now, rather than letting each comparison
     generate the conversion.

     Load the index into a register.

     The list of cases is rearranged into a binary tree,
     nearly optimal assuming equal probability for each case.

     The tree is transformed into RTL, eliminating redundant
     test conditions at the same time.

     If program flow could reach the end of the decision tree
     an unconditional jump to the default code is emitted.

   The above process is unaware of the CFG.  The caller has to fix up
   the CFG itself.  This is done in cfgexpand.c.   

References balance_case_nodes(), ceil_log2(), convert_to_mode(), copy_to_reg(), do_pending_stack_adjust(), dump_case_nodes(), dump_file, dump_flags, emit_case_nodes(), emit_jump(), expand_normal(), have_insn_for(), and set_reg_attrs_for_decl_rtl().

Referenced by expand_case().

static void emit_case_dispatch_table ( tree  index_expr,
tree  index_type,
struct case_node case_list,
rtx  default_label,
tree  minval,
tree  maxval,
tree  range,
basic_block  stmt_bb 
)
static
Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
   one of the labels in CASE_LIST or to the DEFAULT_LABEL.
   MINVAL, MAXVAL, and RANGE are the extrema and range of the case
   labels in CASE_LIST. STMT_BB is the basic block containing the statement.

   First, a jump insn is emitted.  First we try "casesi".  If that
   fails, try "tablejump".   A target *must* have one of them (or both).

   Then, a table with the target labels is emitted.

   The process is unaware of the CFG.  The caller has to fix up
   the CFG itself.  This is done in cfgexpand.c.   

References build_int_cst(), case_node::code_label, compare_tree_int(), conditional_probability(), emit_barrier(), emit_jump_table_data(), emit_label(), gen_label_rtx(), gen_rtvec_v(), get_outgoing_edge_probs(), case_node::high, HOST_WIDE_INT, label_rtx(), case_node::low, memset(), optimize_insn_for_speed_p(), edge_def::probability, case_node::right, basic_block_def::succs, tree_low_cst(), try_casesi(), and try_tablejump().

Referenced by expand_case(), and expand_sjlj_dispatch_table().

static void emit_case_nodes ( rtx  index,
case_node_ptr  node,
rtx  default_label,
int  default_prob,
tree  index_type 
)
static
Emit step-by-step code to select a case for the value of INDEX.
   The thus generated decision tree follows the form of the
   case-node binary tree NODE, whose nodes represent test conditions.
   INDEX_TYPE is the type of the index of the switch.

   Care is taken to prune redundant tests from the decision tree
   by detecting any boundary conditions already checked by
   emitted rtx.  (See node_has_high_bound, node_has_low_bound
   and node_is_bounded, above.)

   Where the test conditions can be shown to be redundant we emit
   an unconditional jump to the target code.  As a further
   optimization, the subordinates of a tree node are examined to
   check for bounded nodes.  In this case conditional and/or
   unconditional jumps as a result of the boundary check for the
   current node are arranged to target the subordinates associated
   code for out of bound conditions on the current node.

   We can assume that when control reaches the code generated here,
   the index value has already been compared with the parents
   of this node, and determined to be on the same side of each parent
   as this node is.  Thus, if this node tests for the value 51,
   and a parent tested for 52, we don't need to consider
   the possibility of a value greater than 51.  If another parent
   tests for the value 50, then this node need not test anything.   

References case_node::code_label, conditional_probability(), convert_modes(), curr_insn_location(), do_jump_if_equal(), emit_cmp_and_jump_insns(), emit_jump(), expand_expr(), expand_label(), EXPAND_NORMAL, expand_normal(), expand_simple_binop(), case_node::high, label_rtx(), case_node::left, case_node::low, node_has_high_bound(), node_has_low_bound(), node_is_bounded(), OPTAB_WIDEN, case_node::prob, prob, case_node::right, case_node::subtree_prob, tree_int_cst_equal(), lang_hooks_for_types::type_for_mode, and lang_hooks::types.

Referenced by emit_case_decision_tree().

void emit_jump ( )
Add an unconditional jump to LABEL as the next sequential instruction.   

References do_pending_stack_adjust(), emit_barrier(), and emit_jump_insn().

static void expand_asm_loc ( )
static
Generate RTL for an asm statement (explicit assembler code).
   STRING is a STRING_CST node containing the assembler code text,
   or an ADDR_EXPR containing a STRING_CST.  VOL nonzero means the
   insn is volatile; don't optimize it.   

References emit_insn().

Referenced by expand_asm_stmt().

static void expand_asm_operands ( tree  string,
tree  outputs,
tree  inputs,
tree  clobbers,
tree  labels,
int  vol,
location_t  locus 
)
static
Generate RTL for an asm statement with arguments.
   STRING is the instruction template.
   OUTPUTS is a list of output arguments (lvalues); INPUTS a list of inputs.
   Each output or input has an expression in the TREE_VALUE and
   a tree list in TREE_PURPOSE which in turn contains a constraint
   name in TREE_VALUE (or NULL_TREE) and a constraint string
   in TREE_PURPOSE.
   CLOBBERS is a list of STRING_CST nodes each naming a hard register
   that is clobbered by this insn.

   Not all kinds of lvalue that may appear in OUTPUTS can be stored directly.
   Some elements of OUTPUTS may be replaced with trees representing temporary
   values.  The caller should copy those temporary values to the originally
   specified lvalues.

   VOL nonzero means the insn is volatile; don't optimize it.   

References asm_operand_ok(), assign_temp(), buffer, check_operand_nalternatives(), constraints, decode_reg_name_and_count(), do_pending_stack_adjust(), emit_insn(), emit_jump_insn(), emit_move_insn(), empty_string, error(), expand_expr(), EXPAND_INITIALIZER, EXPAND_MEMORY, EXPAND_NORMAL, EXPAND_WRITE, force_reg(), free_temp_slots(), gen_reg_rtx(), gen_rtx_MEM(), gen_rtx_REG(), generating_concat_p, internal_error(), label_rtx(), list_length(), make_tree(), mark_addressable(), parse_input_constraint(), parse_output_constraint(), reg_overlap_mentioned_p(), resolve_asm_operand_names(), rtvec_alloc(), set_reg_attrs_for_decl_rtl(), targetm, tree_conflicts_with_clobbers_p(), type(), validize_mem(), and warning().

Referenced by expand_asm_stmt().

void expand_case ( )
void expand_computed_goto ( )
Emit code to jump to the address
   specified by the pointer expression EXP.   

References do_pending_stack_adjust(), emit_indirect_jump(), and expand_normal().

Referenced by expand_gimple_stmt_1().

void expand_goto ( )
Generate RTL code for a `goto' statement with target label LABEL.
   LABEL should be a LABEL_DECL tree node that was or will later be
   defined with `expand_label'.   

References current_function_decl, decl_function_context(), emit_jump(), and label_rtx().

Referenced by expand_gimple_stmt_1().

void expand_label ( )
Handle goto statements and the labels that they can go to.   
Specify the location in the RTL code of a label LABEL,
   which is a LABEL_DECL tree node.

   This is used for the kind of label that the user can jump to with a
   goto statement, and for alternatives of a switch or case statement.
   RTL labels generated for loops and conditionals don't go through here;
   they are generated directly at the RTL level, by other functions below.

   Note that this has nothing to do with defining label *names*.
   Languages vary in how they do that and what that even means.   

References do_pending_stack_adjust(), emit_label(), expand_builtin_setjmp_receiver(), label_rtx(), and maybe_set_first_label_num().

Referenced by emit_case_nodes(), and expand_gimple_stmt_1().

void expand_naked_return ( void  )
Generate RTL to return directly from the current function.
   (That is, we bypass any return value.)   

References clear_pending_stack_adjust(), do_pending_stack_adjust(), emit_jump(), and gen_label_rtx().

Referenced by expand_builtin_return().

void expand_null_return ( void  )
Generate RTL to return from the current function, with no value.
   (That is, we do not do anything about returning any value.)   

References clobber_return_register(), and expand_null_return_1().

Referenced by expand_gimple_stmt_1(), and expand_return().

static void expand_null_return_1 ( )
static
Output a return with no value.   

References clear_pending_stack_adjust(), do_pending_stack_adjust(), and emit_jump().

Referenced by expand_null_return(), and expand_value_return().

void expand_return ( )
Generate RTL to evaluate the expression RETVAL and return it
   from the current function.   

References assign_temp(), build_qualified_type(), copy_blkmode_to_reg(), current_function_decl, expand_expr(), EXPAND_NORMAL, expand_normal(), expand_null_return(), expand_value_return(), force_not_mem(), and TYPE_QUAL_CONST.

Referenced by expand_gimple_stmt_1().

void expand_sjlj_dispatch_table ( rtx  dispatch_index,
vec< tree dispatch_table 
)
Expand the dispatch to a short decrement chain if there are few cases
   to dispatch to.  Likewise if neither casesi nor tablejump is available,
   or if flag_jump_tables is set.  Otherwise, expand as a casesi or a
   tablejump.  The index mode is always the mode of integer_type_node.
   Trap if no case matches the index.

   DISPATCH_INDEX is the index expression to switch on.  It should be a
   memory or register operand.
   
   DISPATCH_TABLE is a set of case labels.  The set should be sorted in
   ascending order, be contiguous, starting with value 0, and contain only
   single-valued case labels.   

References add_case_node(), build_int_cst(), copy_to_mode_reg(), create_alloc_pool(), do_jump_if_equal(), do_pending_stack_adjust(), emit_case_dispatch_table(), emit_label(), expand_builtin_trap(), force_expand_binop(), free_alloc_pool(), free_temp_slots(), gen_label_rtx(), get_last_insn(), label_rtx(), case_node::low, make_tree(), OPTAB_DIRECT, and reorder_insns().

Referenced by sjlj_emit_dispatch_table().

void expand_stack_restore ( )
Emit code to restore the current value of stack.   

References emit_stack_restore(), expand_normal(), fixup_args_size_notes(), get_last_insn(), and SAVE_BLOCK.

Referenced by expand_builtin().

rtx expand_stack_save ( void  )
Emit code to save the current value of stack.   

References do_pending_stack_adjust(), emit_stack_save(), and SAVE_BLOCK.

Referenced by expand_builtin().

static bool expand_switch_as_decision_tree_p ( tree  range,
unsigned int  uniq,
unsigned int  count 
)
static
Return true if a switch should be expanded as a decision tree.
   RANGE is the difference between highest and lowest case.
   UNIQ is number of unique case node targets, not counting the default case.
   COUNT is the number of comparisons needed, not counting the default case.   

References case_values_threshold(), compare_tree_int(), host_integerp(), and optimize_insn_for_size_p().

Referenced by expand_case().

static void expand_value_return ( rtx  )
static

Referenced by expand_return().

static void expand_value_return ( )
static
Generate RTL to return from the current function, with value VAL.   

References convert_modes(), current_function_decl, emit_group_load(), emit_move_insn(), expand_null_return_1(), int_size_in_bytes(), and promote_function_mode().

rtx force_label_rtx ( )
As above, but also put it on the forced-reference list of the
   function that contains it.   

References decl_function_context(), and label_rtx().

static int get_outgoing_edge_probs ( )
static
Return the sum of probabilities of outgoing edges of basic block BB.   

References edge_def::probability, and basic_block_def::succs.

Referenced by emit_case_dispatch_table().

rtx label_rtx ( )
Return the rtx-label that corresponds to a LABEL_DECL,
   creating it if necessary.   

References gen_label_rtx().

basic_block label_to_block_fn ( struct function ,
tree   
)
static int n_occurrences ( int  ,
const char *   
)
static
static int n_occurrences ( )
static
Return the number of times character C occurs in string S.   
static int node_has_high_bound ( case_node_ptr  ,
tree   
)
static

Referenced by emit_case_nodes(), and node_is_bounded().

static int node_has_high_bound ( )
static
Search the parent sections of the case node tree
   to see if a test for the upper bound of NODE would be redundant.
   INDEX_TYPE is the type of the index expression.

   The instructions to generate the case decision tree are
   output in the same order as nodes are processed so it is
   known that if a parent node checks the range of the current
   node plus one that the current node is bounded at its upper
   span.  Thus the test would be redundant.   

References build_int_cst(), case_node::high, case_node::low, case_node::parent, case_node::right, tree_int_cst_equal(), and tree_int_cst_lt().

static int node_has_low_bound ( case_node_ptr  ,
tree   
)
static

Referenced by emit_case_nodes(), and node_is_bounded().

static int node_has_low_bound ( )
static
Search the parent sections of the case node tree
   to see if a test for the lower bound of NODE would be redundant.
   INDEX_TYPE is the type of the index expression.

   The instructions to generate the case decision tree are
   output in the same order as nodes are processed so it is
   known that if a parent node checks the range of the current
   node minus one that the current node is bounded at its lower
   span.  Thus the test would be redundant.   

References build_int_cst(), case_node::high, case_node::left, case_node::low, case_node::parent, tree_int_cst_equal(), and tree_int_cst_lt().

static int node_is_bounded ( case_node_ptr  ,
tree   
)
static

Referenced by emit_case_nodes().

static int node_is_bounded ( )
static
Search the parent sections of the
   case node tree to see if both tests for the upper and lower
   bounds of NODE would be redundant.   

References node_has_high_bound(), and node_has_low_bound().

bool parse_input_constraint ( const char **  constraint_p,
int  input_num,
int  ninputs,
int  noutputs,
int  ninout,
const char *const *  constraints,
bool *  allows_mem,
bool *  allows_reg 
)
bool parse_output_constraint ( const char **  constraint_p,
int  operand_num,
int  ninputs,
int  noutputs,
bool *  allows_mem,
bool *  allows_reg,
bool *  is_inout 
)
Parse the output constraint pointed to by *CONSTRAINT_P.  It is the
   OPERAND_NUMth output operand, indexed from zero.  There are NINPUTS
   inputs and NOUTPUTS outputs to this extended-asm.  Upon return,
   *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
   memory operand.  Similarly, *ALLOWS_REG will be TRUE iff the
   constraint allows the use of a register operand.  And, *IS_INOUT
   will be true if the operand is read-write, i.e., if it is used as
   an input as well as an output.  If *CONSTRAINT_P is not in
   canonical form, it will be made canonical.  (Note that `+' will be
   replaced with `=' as part of this process.)

   Returns TRUE if all went well; FALSE if an error occurred.   

References error(), strlen(), and warning().

Referenced by expand_asm_operands(), find_func_aliases(), get_asm_expr_operands(), gimple_regimplify_operands(), gimplify_asm_expr(), walk_gimple_asm(), and walk_stmt_load_store_addr_ops().

static void reset_out_edges_aux ( )
inlinestatic
Reset the aux field of all outgoing edges of basic block BB.   

References edge_def::aux, and basic_block_def::succs.

Referenced by compute_cases_per_edge(), and expand_case().

tree resolve_asm_operand_names ( )
A subroutine of expand_asm_operands.  Resolve the names of the operands
   in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
   STRING and in the constraints to those numbers.   

References buffer, build_string(), check_unique_operand_names(), free(), resolve_operand_name_1(), and strlen().

Referenced by expand_asm_operands().

static char* resolve_operand_name_1 ( char *  ,
tree  ,
tree  ,
tree   
)
static
static char* resolve_operand_name_1 ( )
static
A subroutine of resolve_operand_names.  P points to the '[' for a
   potential named operand of the form [<name>].  In place, replace
   the name and brackets with a number.  Return a pointer to the
   balance of the string after substitution.   

References error(), identifier_to_locale(), and strlen().

static bool tree_conflicts_with_clobbers_p ( tree  ,
HARD_REG_SET  
)
static

Referenced by expand_asm_operands().

static bool tree_conflicts_with_clobbers_p ( )
static
Check for overlap between registers marked in CLOBBERED_REGS and
   anything inappropriate in T.  Emit error and return the register
   variable definition for error, NULL_TREE for ok.   

References error(), and tree_overlaps_hard_reg_set().

tree tree_overlaps_hard_reg_set ( )
If there is an overlap between *REGS and DECL, return the first overlap
   found.   

References decl_overlaps_hard_reg_set_p().

Referenced by tree_conflicts_with_clobbers_p().