#include "config.h"#include "system.h"#include "coretypes.h"#include "tm.h"#include "rtl.h"#include "tree.h"#include "tm_p.h"#include "flags.h"#include "regs.h"#include "hard-reg-set.h"#include "basic-block.h"#include "insn-config.h"#include "function.h"#include "expr.h"#include "insn-attr.h"#include "recog.h"#include "diagnostic-core.h"#include "target.h"#include "optabs.h"#include "insn-codes.h"#include "rtlhooks-def.h"#include "params.h"#include "tree-pass.h"#include "df.h"#include "cgraph.h"
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 |
Typedef Documentation
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.
Enumeration Type Documentation
| enum ext_modified_kind |
Function Documentation
|
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, gen_int_mode(), GET_MODE, GET_MODE_MASK, INTVAL, and SET_DEST.
|
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, INSN_UID, 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.
Variable Documentation
|
static |
