#include "config.h"#include "system.h"#include "coretypes.h"#include "tm.h"#include "diagnostic-core.h"#include "sparseset.h"#include "rtl.h"#include "tm_p.h"#include "insn-config.h"#include "recog.h"#include "flags.h"#include "obstack.h"#include "basic-block.h"#include "df.h"#include "target.h"#include "cfgloop.h"#include "tree-pass.h"#include "domwalk.h"#include "emit-rtl.h"
Data Structures | |
| class | single_def_use_dom_walker |
Macros | |
| #define | DF_MD_GEN_FLAGS (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER) |
Enumerations | |
| enum | { PR_CAN_APPEAR = 1, PR_HANDLE_MEM = 2, PR_OPTIMIZE_FOR_SPEED = 4 } |
Variables | |
| static int | num_changes |
| static vec< df_ref > | use_def_ref |
| static vec< df_ref > | reg_defs |
| static vec< df_ref > | reg_defs_stack |
| static bitmap | local_md |
| static bitmap | local_lr |
| static df_ref * | active_defs |
Macro Definition Documentation
| #define DF_MD_GEN_FLAGS (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER) |
Update the reg_defs vector with non-partial definitions in DEF_REC. TOP_FLAG says which artificials uses should be used, when DEF_REC is an artificial def vector. LOCAL_MD is modified as after a df_md_simulate_* function; we do more or less the same processing done there, so we do not use those functions.
Enumeration Type Documentation
| anonymous enum |
Flags for the last parameter of propagate_rtx_1.
- Enumerator:
Function Documentation
|
static |
Check if all uses in DEF_INSN can be used in TARGET_INSN. This would require full computation of available expressions; we check only restricted conditions, see use_killed_between.
If target_insn comes right after def_insn, which is very common for addresses, we can use a quicker test. Ignore debug insns other than target insns for this.
If the insn uses the reg that it defines, the substitution is
invalid. Look at all the uses of DEF_INSN, and see if they are not
killed between DEF_INSN and TARGET_INSN.
|
static |
Build a vector holding the reaching definitions of uses reached by a single dominating definition.
We use the multiple definitions problem to compute our restricted use-def chains.
Walk the dominator tree looking for single reaching definitions dominating the uses. This is similar to how SSA form is built.
|
static |
Do not try to replace constant addresses or addresses of local and argument slots. These MEM expressions are made only once and inserted in many instructions, as well as being used to control symbol table output. It is not safe to clobber them.
There are some uncommon cases where the address is already in a register for some reason, but we cannot take advantage of that because we have no easy way to unshare the MEM. In addition, looking up all stack addresses is costly.
|
static |
Returns a canonical version of X for the address, from the point of view, that all multiplications are represented as MULT instead of the multiply by a power of 2 being represented as ASHIFT.
Every ASHIFT we find has been made by simplify_gen_binary and was not there before, so it is not shared. So we can do this in place.
|
static |
Try to replace USE with SRC (defined in DEF_INSN) and simplify the result.
Do not propagate into PC, CC0, etc.
If def and use are subreg, check if they match.
Check if the def had a subreg, but the use has the whole reg.
Check if the use has a subreg, but the def had the whole reg. Unlike the previous case, the optimization is possible and often useful indeed.
Make sure that we can treat REG as having the same mode as the source of DEF_SET.
Check if the substitution is valid (last, because it's the most expensive check!).
Check if the def is loading something from the constant pool; in this case we would undo optimization such as compress_float_constant. Still, we can set a REG_EQUAL note.
Else try simplifying.
Do not replace an existing REG_EQUAL note if the insn is not
recognized. Either we're already replacing in the note, or we'll
separately try plugging the definition in the note and simplifying.
And only install a REQ_EQUAL note when the destination is a REG
that isn't mentioned in USE_SET, as the note would be invalid
otherwise. We also don't want to install a note if we are merely
propagating a pseudo since verifying that this pseudo isn't dead
is a pain; moreover such a note won't help anything.
|
static |
Try to replace USE with SRC (defined in DEF_INSN) in __asm.
In __asm don't replace if src might need more registers than reg, as that could increase register pressure on the __asm.
|
static |
Given a use USE of an insn, if it has a single reaching definition, try to forward propagate it into that insn. Return true if cfg cleanup will be needed.
Only consider uses that have a single definition.
Do not propagate loop invariant definitions inside the loop.
Check if the use is still present in the insn!
Only try one kind of propagation. If two are possible, we'll do it on the following iterations.
|
static |
If USE is a subreg, see if it can be replaced by a pseudo.
Only consider subregs...
If this is a paradoxical SUBREG...
If this is a paradoxical SUBREG, we have no idea what value the
extra bits would have. However, if the operand is equivalent to
a SUBREG whose operand is the same as our mode, and all the modes
are within a word, we can just use the inner operand because
these SUBREGs just say how to treat the register. If this is a SUBREG of a ZERO_EXTEND or SIGN_EXTEND, and the SUBREG
is the low part of the reg being extended then just use the inner
operand. Don't do this if the ZERO_EXTEND or SIGN_EXTEND insn will
be removed due to it matching a LOAD_EXTEND_OP load from memory,
or due to the operation being a no-op when applied to registers.
For example, if we have:
A: (set (reg:DI X) (sign_extend:DI (reg:SI Y)))
B: (... (subreg:SI (reg:DI X)) ...)
and mode_rep_extended says that Y is already sign-extended,
the backend will typically allow A to be combined with the
definition of Y or, failing that, allow A to be deleted after
reload through register tying. Introducing more uses of Y
prevents both optimisations.
|
static |
For the given single_set INSN, containing SRC known to be a ZERO_EXTEND or SIGN_EXTEND of a register, return true if INSN is redundant due to the register being set by a LOAD_EXTEND_OP load from memory.
|
static |
Go through all the uses. df_uses_create will create new ones at the end, and we'll go through them as well.
Do not forward propagate addresses into loops until after unrolling. CSE did so because it was able to fix its own mess, but we are not.
The outer most loop is not really a loop.
|
static |
Go through all the uses. df_uses_create will create new ones at the end, and we'll go through them as well.
The outer most loop is not really a loop.
|
static |
References gate_fwprop().
|
static |
We do not always want to propagate into loops, so we have to find loops and be careful about them. Avoid CFG modifications so that we don't have to update dominance information afterwards for build_single_def_use_links.
References OPTGROUP_NONE, RTL_PASS, TODO_df_finish, TODO_verify_flow, and TODO_verify_rtl_sharing.
|
static |
Main entry point.
References DF_REF_BB, DF_REF_REG_USE, DF_REF_TYPE, DF_USES_GET, and NULL.
Referenced by fwprop_done().
|
inlinestatic |
Return the only def in USE's use-def chain, or NULL if there is more than one def in the chain.
|
static |
Return true if the register from reference REF is killed between FROM to (but not including) TO.
| rtl_opt_pass* make_pass_rtl_fwprop | ( | ) |
| rtl_opt_pass* make_pass_rtl_fwprop_addr | ( | ) |
|
static |
Do not store anything if "transitioning" from NULL to NULL. But otherwise, push a special entry on the stack to tell the leave_block callback that the entry in reg_defs was NULL.
|
static |
Fill the use_def_ref vector with values for the uses in USE_REC, taking reaching definitions info from LOCAL_MD and REG_DEFS. TOP_FLAG says which artificials uses should be used, when USE_REC is an artificial use vector.
|
static |
Replace all occurrences of OLD in X with NEW and try to simplify the resulting expression (in mode MODE). Return a new expression if it is a constant, otherwise X.
Simplifications where occurrences of NEW collapse to a constant are always accepted. All simplifications are accepted if NEW is a pseudo too. Otherwise, we accept simplifications that have a lower or equal cost.
gen_lowpart_common will not be able to process VOIDmode entities other than CONST_INTs.
|
static |
Replace all occurrences of OLD in *PX with NEW and try to simplify the resulting expression. Replace *PX with a new RTL expression if an occurrence of OLD was found.
This is only a wrapper around simplify-rtx.c: do not add any pattern matching code here. (The sole exception is the handling of LO_SUM, but that is because there is no simplify_gen_* function for LO_SUM).
If unsafe, change MEMs to CLOBBERs or SCRATCHes (to preserve whether they have side effects or not).
If X is OLD_RTX, return NEW_RTX. But not if replacing only within an address, and we are <em>not</em> inside one. If this is an expression, try recursive substitution.
The only case we try to handle is a SUBREG.
There are some addresses that we cannot work on.
Dismiss transformation that we do not want to carry on.
Copy propagations are always ok. Otherwise check the costs.
The only simplification we do attempts to remove references to op0
or make it constant – in both cases, op0's invalidity will not
make the result invalid. (lo_sum (high x) x) -> x
OP1 is likely not a legitimate address, otherwise there would have
been no LO_SUM. We want it to disappear if it is invalid, return
false in that case. No change, no trouble.
The replacement we made so far is valid, if all of the recursive replacements were valid, or we could simplify everything to a constant.
|
static |
Fill the ACTIVE_DEFS array with the use->def link for the registers mentioned in USE_REC. Register the valid entries in ACTIVE_DEFS_CHECK too, for checking purposes.
|
static |
OLD is a memory address. Return whether it is good to use NEW instead, for a memory access in the given MODE.
Copy propagation is always ok.
Prefer the new address if it is less expensive.
If the addresses have equivalent cost, prefer the new address if it has the highest `set_src_cost'. That has the potential of eliminating the most insns without additional costs, and it is the same that cse.c used to do.
|
static |
Try substituting NEW into LOC, which originated from forward propagation of USE's value from DEF_INSN. SET_REG_EQUAL says whether we are substituting the whole SET_SRC, so we can set a REG_EQUAL note if the new insn is not recognized. Return whether the substitution was performed.
forward_propagate_subreg may be operating on an instruction with multiple sets. If so, assume the cost of the new instruction is not greater than the old one.
Can also record a simplified value in a REG_EQUAL note,
making a new one if one does not already exist.
References copy_rtx(), dump_file, and set_unique_reg_note().
|
static |
Update the USE_DEF_REF array for the uses in INSN. Only update note uses if NOTES_ONLY is true.
|
static |
Build the use->def links that we use to update the dataflow info for new uses. Note that building the links is very cheap and if it were done earlier, they could be used to rule out invalid propagations (in addition to what is done in all_uses_available_at). I'm not doing this yet, though.
|
inlinestatic |
Update the USE_DEF_REF array for the given use, using the active definitions in the ACTIVE_DEFS array to match pseudos to their def.
Set up the use-def chain.
|
static |
Check if the given DEF is available in INSN. This would require full computation of available expressions; we check only restricted conditions:
- if DEF is the sole definition of its register, go ahead;
- in the same basic block, we check for no definitions killing the definition of DEF_INSN;
- if USE's basic block has DEF's basic block as the sole predecessor, we check if the definition is killed after DEF_INSN or before TARGET_INSN insn, in their respective basic blocks.
We used to have a def reaching a use that is <em>before</em> the def, with the def not dominating the use even though the use and def are in the same basic block, when a register may be used uninitialized in a loop. This should not happen anymore since we do not use reaching definitions, but still we test for such cases and assume that DEF is not available.
Check if the reg in USE has only one definition. We already know that this definition reaches use, or we wouldn't be here. However, this is invalid for hard registers because if they are live at the beginning of the function it does not mean that we have an uninitialized access.
Check locally if we are in the same basic block.
Finally, if DEF_BB is the sole predecessor of TARGET_BB.
See if USE is killed between DEF_INSN and the last insn in the
basic block containing DEF_INSN. See if USE is killed between TARGET_INSN and the first insn in the
basic block containing TARGET_INSN. Otherwise assume the worst case.
|
static |
for_each_rtx traversal function that returns 1 if BODY points to a non-constant mem.
Variable Documentation
|
static |
|
static |
|
static |
The MD bitmaps are trimmed to include only live registers to cut memory usage on testcases like insn-recog.c. Track live registers in the basic block and do not perform forward propagation if the destination is a dead pseudo occurring in a note.
|
static |
RTL-based forward propagation pass for GNU compiler. Copyright (C) 2005-2013 Free Software Foundation, Inc. Contributed by Paolo Bonzini and Steven Bosscher.
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/. This pass does simple forward propagation and simplification when an operand of an insn can only come from a single def. This pass uses df.c, so it is global. However, we only do limited analysis of available expressions.
1) The pass tries to propagate the source of the def into the use, and checks if the result is independent of the substituted value. For example, the high word of a (zero_extend:DI (reg:SI M)) is always zero, independent of the source register.
In particular, we propagate constants into the use site. Sometimes RTL expansion did not put the constant in the same insn on purpose, to satisfy a predicate, and the result will fail to be recognized; but this happens rarely and in this case we can still create a REG_EQUAL note. For multi-word operations, this
(set (subreg:SI (reg:DI 120) 0) (const_int 0)) (set (subreg:SI (reg:DI 120) 4) (const_int -1)) (set (subreg:SI (reg:DI 122) 0) (ior:SI (subreg:SI (reg:DI 119) 0) (subreg:SI (reg:DI 120) 0))) (set (subreg:SI (reg:DI 122) 4) (ior:SI (subreg:SI (reg:DI 119) 4) (subreg:SI (reg:DI 120) 4)))
can be simplified to the much simpler
(set (subreg:SI (reg:DI 122) 0) (subreg:SI (reg:DI 119))) (set (subreg:SI (reg:DI 122) 4) (const_int -1))
This particular propagation is also effective at putting together complex addressing modes. We are more aggressive inside MEMs, in that all definitions are propagated if the use is in a MEM; if the result is a valid memory address we check address_cost to decide whether the substitution is worthwhile.
2) The pass propagates register copies. This is not as effective as the copy propagation done by CSE's canon_reg, which works by walking the instruction chain, it can help the other transformations.
We should consider removing this optimization, and instead reorder the RTL passes, because GCSE does this transformation too. With some luck, the CSE pass at the end of rest_of_handle_gcse could also go away.
3) The pass looks for paradoxical subregs that are actually unnecessary. Things like this:
(set (reg:QI 120) (subreg:QI (reg:SI 118) 0)) (set (reg:QI 121) (subreg:QI (reg:SI 119) 0)) (set (reg:SI 122) (plus:SI (subreg:SI (reg:QI 120) 0) (subreg:SI (reg:QI 121) 0)))
are very common on machines that can only do word-sized operations. For each use of a paradoxical subreg (subreg:WIDER (reg:NARROW N) 0), if it has a single def and it is (subreg:NARROW (reg:WIDE M) 0), we can replace the paradoxical subreg with simply (reg:WIDE M). The above will simplify this to
(set (reg:QI 120) (subreg:QI (reg:SI 118) 0)) (set (reg:QI 121) (subreg:QI (reg:SI 119) 0)) (set (reg:SI 122) (plus:SI (reg:SI 118) (reg:SI 119)))
where the first two insns are now dead.
We used to use reaching definitions to find which uses have a single reaching definition (sounds obvious...), but this is too complex a problem in nasty testcases like PR33928. Now we use the multiple definitions problem in df-problems.c. The similarity between that problem and SSA form creation is taken further, in that fwprop does a dominator walk to create its chains; however, instead of creating a PHI function where multiple definitions meet I just punt and record only singleton use-def chains, which is all that is needed by fwprop.
