- 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.
We are looking for SET (REG N) (ANY_EXTEND (REG N)).
First, make sure we can get all the reaching definitions.
Second, make sure the reaching definitions don't feed another and
different extension. FIXME: this obviously can be improved. Then add the candidate to the list and insert the reaching definitions
into the definition map.
References dump_file, and print_rtl_single().
|
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.
If cand->insn has been already modified, update cand->mode to a wider
mode if possible, or punt. Go through the defs vector and try to merge all the definitions
in this vector. Now go through the conditional copies vector and try to merge all
the copies in this vector. Commit the changes here if possible
FIXME: It's an all-or-nothing scenario. Even if only one definition
cannot be merged, we entirely give up. In the future, we should allow
extensions to be partially eliminated along those paths where the
definitions could be merged. Changes need not be cancelled explicitly as apply_change_group
does it. Print list of definitions in the dump_file for debug
purposes. This extension cannot be deleted. Cancel any changes that have been made so far.
References merge_def_and_ext(), and ext_state::modified_list.
Referenced by find_removable_extensions().
|
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.
Merge constants by directly moving the constant into the register under
some conditions. Recall that RTL constants are sign-extended. Zero-extend the negative constant by masking out the bits outside
the source mode. This is mostly due to a call insn that should not be optimized.
Here is a sequence of two extensions. Try to merge them.
Only IF_THEN_ELSE of phi-type copies are combined. Otherwise,
in general, IF_THEN_ELSE should not be combined. This is the normal case.
This change is a part of a group of changes. Hence,
validate_change will not try to commit the change.
References ext_cand::code, and gen_int_mode().
|
static |
This is the main function that checks the insn stream for redundant extensions and tries to remove them if possible.
Construct DU chain to get all reaching definitions of each
extension instruction. Try to combine the extension with the definition.
Delete all useless extensions here in one sweep.
References timevar_pop(), and timevar_push().
Traverse the instruction stream looking for extensions and return the list of candidates.
References combine_reaching_defs(), dump_file, ext_cand::expr, ext_cand::insn, ext_state::modified, and print_rtl_single().
|
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.
Problem getting some definition for this instruction.
|
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 EXT_MODIFIED_NONE, EXT_MODIFIED_SEXT, and EXT_MODIFIED_ZEXT.
|
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.
Initialize the work list.
Perform transitive closure for conditional copies.
Push it onto the copy list first.
Now perform the transitive closure.
| rtl_opt_pass* make_pass_ree | ( | ) |
|
static |
Merge the DEF_INSN with an extension. Calls combine_set_extension on the SET pattern.
PARALLEL with multiple SETs.
It is not a PARALLEL or a SET, what could it be ?
If def_insn is already scheduled to be deleted, don't attempt
to modify it.
Referenced by combine_reaching_defs().
|
static |
Find and remove redundant extensions.
|
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.
If the conditional move already has the right or wider mode,
there is nothing to do.
|
static |
1.8.1.1