- Generated by
1.8.1.1
|
GCC Middle and Back End API Reference
|
Data Structures | |
| struct | ext_cand |
| struct | ext_modified |
| struct | ext_state |
Typedefs | |
| typedef struct ext_cand | ext_cand |
| typedef struct ext_state | ext_state |
Enumerations | |
| enum | ext_modified_kind { EXT_MODIFIED_NONE, EXT_MODIFIED_ZEXT, EXT_MODIFIED_SEXT } |
Functions | |
| static bool | combine_set_extension () |
| static bool | transform_ifelse () |
| static struct df_link * | get_defs () |
| static bool | is_cond_copy_insn () |
| static bool | make_defs_and_copies_lists (rtx extend_insn, const_rtx set_pat, ext_state *state) |
| static bool | merge_def_and_ext () |
| static bool | combine_reaching_defs () |
| static void | add_removable_extension (const_rtx expr, rtx insn, vec< ext_cand > *insn_list, unsigned *def_map) |
| static vec< ext_cand > | find_removable_extensions () |
| static void | find_and_remove_re () |
| static unsigned int | rest_of_handle_ree () |
| static bool | gate_handle_ree () |
| rtl_opt_pass * | make_pass_ree () |
Variables | |
| static int | max_insn_uid |
@verbatim Redundant Extension Elimination pass for the GNU compiler.
Copyright (C) 2010-2013 Free Software Foundation, Inc. Contributed by Ilya Enkovich (ilya.enkovich@intel.com)
Based on the Redundant Zero-extension elimination pass contributed by Sriraman Tallam (tmsriram@google.com) and Silvius Rus (rus@google.com).
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/.
Problem Description :
--------------------
This pass is intended to remove redundant extension instructions.
Such instructions appear for different reasons. We expect some of
them due to implicit zero-extension in 64-bit registers after writing
to their lower 32-bit half (e.g. for the x86-64 architecture).
Another possible reason is a type cast which follows a load (for
instance a register restore) and which can be combined into a single
instruction, and for which earlier local passes, e.g. the combiner,
weren't able to optimize.
How does this pass work ?
--------------------------
This pass is run after register allocation. Hence, all registers that
this pass deals with are hard registers. This pass first looks for an
extension instruction that could possibly be redundant. Such extension
instructions show up in RTL with the pattern :
(set (reg:<SWI248> x) (any_extend:<SWI248> (reg:<SWI124> x))),
where x can be any hard register.
Now, this pass tries to eliminate this instruction by merging the
extension with the definitions of register x. For instance, if
one of the definitions of register x was :
(set (reg:SI x) (plus:SI (reg:SI z1) (reg:SI z2))),
followed by extension :
(set (reg:DI x) (zero_extend:DI (reg:SI x)))
then the combination converts this into :
(set (reg:DI x) (zero_extend:DI (plus:SI (reg:SI z1) (reg:SI z2)))).
If all the merged definitions are recognizable assembly instructions,
the extension is effectively eliminated.
For example, for the x86-64 architecture, implicit zero-extensions
are captured with appropriate patterns in the i386.md file. Hence,
these merged definition can be matched to a single assembly instruction.
The original extension instruction is then deleted if all the
definitions can be merged.
However, there are cases where the definition instruction cannot be
merged with an extension. Examples are CALL instructions. In such
cases, the original extension is not redundant and this pass does
not delete it.
Handling conditional moves :
----------------------------
Architectures like x86-64 support conditional moves whose semantics for
extension differ from the other instructions. For instance, the
instruction *cmov ebx, eax*
zero-extends eax onto rax only when the move from ebx to eax happens.
Otherwise, eax may not be zero-extended. Consider conditional moves as
RTL instructions of the form
(set (reg:SI x) (if_then_else (cond) (reg:SI y) (reg:SI z))).
This pass tries to merge an extension with a conditional move by
actually merging the definitions of y and z with an extension and then
converting the conditional move into :
(set (reg:DI x) (if_then_else (cond) (reg:DI y) (reg:DI z))).
Since registers y and z are extended, register x will also be extended
after the conditional move. Note that this step has to be done
transitively since the definition of a conditional copy can be
another conditional copy.
Motivating Example I :
---------------------
For this program :
**********************************************
bad_code.c
int mask[1000];
int foo(unsigned x)
{
if (x < 10)
x = x * 45;
else
x = x * 78;
return mask[x];
}
**********************************************
$ gcc -O2 bad_code.c
........
400315: b8 4e 00 00 00 mov $0x4e,%eax
40031a: 0f af f8 imul %eax,%edi
40031d: 89 ff mov %edi,%edi - useless extension
40031f: 8b 04 bd 60 19 40 00 mov 0x401960(,%rdi,4),%eax
400326: c3 retq
......
400330: ba 2d 00 00 00 mov $0x2d,%edx
400335: 0f af fa imul %edx,%edi
400338: 89 ff mov %edi,%edi - useless extension
40033a: 8b 04 bd 60 19 40 00 mov 0x401960(,%rdi,4),%eax
400341: c3 retq
$ gcc -O2 -free bad_code.c
......
400315: 6b ff 4e imul $0x4e,%edi,%edi
400318: 8b 04 bd 40 19 40 00 mov 0x401940(,%rdi,4),%eax
40031f: c3 retq
400320: 6b ff 2d imul $0x2d,%edi,%edi
400323: 8b 04 bd 40 19 40 00 mov 0x401940(,%rdi,4),%eax
40032a: c3 retq
Motivating Example II :
---------------------
Here is an example with a conditional move.
For this program :
**********************************************
unsigned long long foo(unsigned x , unsigned y)
{
unsigned z;
if (x > 100)
z = x + y;
else
z = x - y;
return (unsigned long long)(z);
}
$ gcc -O2 bad_code.c
............
400360: 8d 14 3e lea (%rsi,%rdi,1),%edx
400363: 89 f8 mov %edi,%eax
400365: 29 f0 sub %esi,%eax
400367: 83 ff 65 cmp $0x65,%edi
40036a: 0f 43 c2 cmovae %edx,%eax
40036d: 89 c0 mov %eax,%eax - useless extension
40036f: c3 retq
$ gcc -O2 -free bad_code.c
.............
400360: 89 fa mov %edi,%edx
400362: 8d 04 3e lea (%rsi,%rdi,1),%eax
400365: 29 f2 sub %esi,%edx
400367: 83 ff 65 cmp $0x65,%edi
40036a: 89 d6 mov %edx,%esi
40036c: 48 0f 42 c6 cmovb %rsi,%rax
400370: c3 retq
Motivating Example III :
---------------------
Here is an example with a type cast.
For this program :
**********************************************
void test(int size, unsigned char *in, unsigned char *out)
{
int i;
unsigned char xr, xg, xy=0;
for (i = 0; i < size; i++) {
xr = *in++;
xg = *in++;
xy = (unsigned char) ((19595*xr + 38470*xg) >> 16);
*out++ = xy;
}
}
$ gcc -O2 bad_code.c
............
10: 0f b6 0e movzbl (%rsi),%ecx
13: 0f b6 46 01 movzbl 0x1(%rsi),%eax
17: 48 83 c6 02 add $0x2,%rsi
1b: 0f b6 c9 movzbl %cl,%ecx - useless extension
1e: 0f b6 c0 movzbl %al,%eax - useless extension
21: 69 c9 8b 4c 00 00 imul $0x4c8b,%ecx,%ecx
27: 69 c0 46 96 00 00 imul $0x9646,%eax,%eax
$ gcc -O2 -free bad_code.c
.............
10: 0f b6 0e movzbl (%rsi),%ecx
13: 0f b6 46 01 movzbl 0x1(%rsi),%eax
17: 48 83 c6 02 add $0x2,%rsi
1b: 69 c9 8b 4c 00 00 imul $0x4c8b,%ecx,%ecx
21: 69 c0 46 96 00 00 imul $0x9646,%eax,%eax
Usefulness :
----------
The original redundant zero-extension elimination pass reported reduction
of the dynamic instruction count of a compression benchmark by 2.8% and
improvement of its run time by about 1%.
The additional performance gain with the enhanced pass is mostly expected
on in-order architectures where redundancy cannot be compensated by out of
order execution. Measurements showed up to 10% performance gain (reduced
run time) on EEMBC 2.0 benchmarks on Atom processor with geomean performance
gain 1%. This structure represents a candidate for elimination.
| enum ext_modified_kind |
|
static |
Add an extension pattern that could be eliminated.
References ext_cand::code, defs, dump_file, get_defs(), df_link::next, print_rtl_single(), df_link::ref, and SET.
Referenced by find_removable_extensions().
|
static |
This function goes through all reaching defs of the source of the candidate for elimination (CAND) and tries to combine the extension with the definition instruction. The changes are made as a group so that even if one definition cannot be merged, all reaching definitions end up not being merged. When a conditional copy is encountered, merging is attempted transitively on its definitions. It returns true upon success and false upon failure.
References apply_change_group(), cancel_changes(), ext_cand::code, ext_state::copies_list, ext_state::defs_list, dump_file, EXT_MODIFIED_NONE, EXT_MODIFIED_SEXT, EXT_MODIFIED_ZEXT, ext_cand::insn, make_defs_and_copies_lists(), merge_def_and_ext(), ext_cand::mode, ext_state::modified, ext_state::modified_list, print_rtl_single(), and transform_ifelse().
Referenced by find_and_remove_re().
|
static |
Given a insn (CURR_INSN), an extension candidate for removal (CAND) and a pointer to the SET rtx (ORIG_SET) that needs to be modified, this code modifies the SET rtx to a new SET rtx that extends the right hand expression into a register on the left hand side. Note that multiple assumptions are made about the nature of the set that needs to be true for this to work and is called from merge_def_and_ext. Original : (set (reg a) (expression)) Transform : (set (reg a) (any_extend (expression))) Special Cases : If the expression is a constant or another extension, then directly assign it to the register.
References ext_cand::code, dump_file, gen_rtx_REG(), HOST_BITS_PER_WIDE_INT, ext_cand::mode, print_rtl_single(), simplify_rtx(), and validate_change().
Referenced by merge_def_and_ext().
|
static |
This is the main function that checks the insn stream for redundant extensions and tries to remove them if possible.
References combine_reaching_defs(), ext_state::copies_list, curr_insn, ext_state::defs_list, delete_insn(), df_analyze(), df_chain_add_problem(), DF_DEFER_INSN_RESCAN, DF_DU_CHAIN, DF_RD_PRUNE_DEAD_DEFS, df_set_flags(), DF_UD_CHAIN, dump_file, ext_cand::expr, find_removable_extensions(), get_max_uid(), ext_cand::insn, max_insn_uid, ext_state::modified, ext_state::modified_list, print_rtl_single(), and ext_state::work_list.
Referenced by rest_of_handle_ree().
Traverse the instruction stream looking for extensions and return the list of candidates.
References add_removable_extension(), max_insn_uid, and vNULL.
Referenced by find_and_remove_re().
|
static |
Run REE pass when flag_ree is set at optimization level > 0.
|
staticread |
Get all the reaching definitions of an instruction. The definitions are desired for REG used in INSN. Return the definition list or NULL if a definition is missing. If DEST is non-NULL, additionally push the INSN of the definitions onto DEST.
References df_link::next, and df_link::ref.
Referenced by add_removable_extension(), and make_defs_and_copies_lists().
|
static |
Return true if INSN is
(SET (reg REGNO (def_reg)) (if_then_else (cond) (REG x1) (REG x2)))
and store x1 and x2 in REG_1 and REG_2.
References SET.
Referenced by make_defs_and_copies_lists().
|
static |
Reaching Definitions of the extended register could be conditional copies or regular definitions. This function separates the two types into two lists, STATE->DEFS_LIST and STATE->COPIES_LIST. This is necessary because, if a reaching definition is a conditional copy, merging the extension with this definition is wrong. Conditional copies are merged by transitively merging their definitions. The defs_list is populated with all the reaching definitions of the extension instruction (EXTEND_INSN) which must be merged with an extension. The copies_list contains all the conditional moves that will later be extended into a wider mode conditional move if all the merges are successful. The function returns false upon failure, true upon success.
References ext_state::copies_list, ext_state::defs_list, get_defs(), is_cond_copy_insn(), max_insn_uid, and ext_state::work_list.
Referenced by combine_reaching_defs().
| rtl_opt_pass* make_pass_ree | ( | ) |
|
static |
Merge the DEF_INSN with an extension. Calls combine_set_extension on the SET pattern.
References ext_cand::code, combine_set_extension(), deleted, ext_cand::expr, EXT_MODIFIED_NONE, EXT_MODIFIED_SEXT, EXT_MODIFIED_ZEXT, ext_cand::mode, ext_state::modified, and SET.
Referenced by combine_reaching_defs().
|
static |
Find and remove redundant extensions.
References find_and_remove_re(), timevar_pop(), and timevar_push().
|
static |
Treat if_then_else insns, where the operands of both branches are registers, as copies. For instance, Original : (set (reg:SI a) (if_then_else (cond) (reg:SI b) (reg:SI c))) Transformed : (set (reg:DI a) (if_then_else (cond) (reg:DI b) (reg:DI c))) DEF_INSN is the if_then_else insn.
References dump_file, gen_rtx_REG(), ext_cand::mode, print_rtl_single(), SET, and validate_change().
Referenced by combine_reaching_defs().
|
static |
Referenced by find_and_remove_re(), find_removable_extensions(), and make_defs_and_copies_lists().
1.8.1.1