cselib.c File Reference
Include dependency graph for cselib.c:
Data Structures | |
| struct | elt_list |
| struct | expand_value_data |
| struct | cselib_hasher |
| struct | cselib_record_autoinc_data |
Function Documentation
|
static |
|
static |
ADDR_ELT is a value that is used as address. MEM_ELT is the value that contains the data at this address. X is a MEM that represents the value. Update the two value structures to represent this situation.
Avoid duplicates.
References bitmap_bit_p(), cfa_base_preserved_regno, dump_file, dump_flags, elt_loc_list::loc, and expand_value_data::regs_active.
|
static |
If x is a PLUS or an autoinc operation, expand the operation, storing the offset, if any, in *OFF.
| void cselib_add_permanent_equiv | ( | ) |
Make ELT and X's VALUE equivalent to each other at INSN.
| void cselib_clear_table | ( | void | ) |
Remove all entries from the hash table. Also used during initialization.
Referenced by fp_setter_insn().
| bool cselib_dummy_expand_value_rtx_cb | ( | rtx | orig, |
| bitmap | regs_active, | ||
| int | max_depth, | ||
| cselib_expand_callback | cb, | ||
| void * | data | ||
| ) |
Similar to cselib_expand_value_rtx_cb, but no rtxs are actually copied or simplified. Useful to find out whether cselib_expand_value_rtx_cb would return NULL or non-NULL, without allocating new rtx.
References expand_value_data::callback, expand_value_data::callback_arg, and expand_value_data::regs_active.
| rtx cselib_expand_value_rtx | ( | ) |
Forward substitute and expand an expression out to its roots. This is the opposite of common subexpression. Because local value numbering is such a weak optimization, the expanded expression is pretty much unique (not from a pointer equals point of view but from a tree shape point of view. This function returns NULL if the expansion fails. The expansion will fail if there is no value number for one of the operands or if one of the operands has been overwritten between the current insn and the beginning of the basic block. For instance x has no expansion in: r1 <- r1 + 3 x <- r1 + 8 REGS_ACTIVE is a scratch bitmap that should be clear when passing in. It is clear on return.
|
static |
Internal implementation of cselib_expand_value_rtx and cselib_expand_value_rtx_cb.
For the context of dse, if we end up expand into a huge tree, we
will not have a useful address, so we might as well just give up
quickly. The only thing that we are not willing to do (this
is requirement of dse and if others potential uses
need this function we should add a parm to control
it) is that we will not substitute the
STACK_POINTER_REGNUM, FRAME_POINTER or the
HARD_FRAME_POINTER.
These expansions confuses the code that notices that
stores into the frame go dead at the end of the
function and that the frame is not effected by calls
to subroutines. If you allow the
STACK_POINTER_REGNUM substitution, then dse will
think that parameter pushing also goes dead which is
wrong. If you allow the FRAME_POINTER or the
HARD_FRAME_POINTER then you lose the opportunity to
make the frame assumptions. SCRATCH must be shared because they represent distinct values.
Copy the various flags, fields, and other information. We assume
that all fields need copying, and then clear the fields that should
not be copied. That is the sensible default behavior, and forces
us to explicitly document why we are *not* copying a flag. These are left unchanged.
If an operand has been simplified into CONST_INT, which doesn't
have a mode and the mode isn't derivable from whole rtx's mode,
try simplify_*_operation first with mode from original's operand
and as a fallback wrap CONST_INT into gen_rtx_CONST. These expressions can derive operand modes from the whole rtx's mode.
Referenced by expand_loc().
| rtx cselib_expand_value_rtx_cb | ( | rtx | orig, |
| bitmap | regs_active, | ||
| int | max_depth, | ||
| cselib_expand_callback | cb, | ||
| void * | data | ||
| ) |
Same as cselib_expand_value_rtx, but using a callback to try to resolve some expressions. The CB function should return ORIG if it can't or does not want to deal with a certain RTX. Any other return value, including NULL, will be used as the expansion for VALUE, without any further changes.
Referenced by loc_exp_insert_dep().
|
static |
Search for X, whose hashcode is HASH, in CSELIB_HASH_TABLE, INSERTing if requested. When X is part of the address of a MEM, MEMMODE should specify the mode of the MEM. While searching the table, MEMMODE is held in FIND_SLOT_MEMMODE, so that autoinc RTXs in X can be resolved.
References elt_loc_list::next, references_value_p(), and unchain_one_elt_loc_list().
| void cselib_finish | ( | void | ) |
Called when the current user is done with cselib.
Referenced by chain_to_prev_insn_p().
| unsigned int cselib_get_next_uid | ( | void | ) |
Return the number of the next value that will be generated.
Referenced by emit_notes_for_changes().
|
static |
|
static |
Hash an rtx. Return 0 if we couldn't hash the rtx.
For registers and memory locations, we look up their cselib_val structure
and return its VALUE element.
Possible reasons for return 0 are: the object is volatile, or we couldn't
find a register or memory location in the table and CREATE is zero. If
CREATE is nonzero, table elts are created for regs and mem.
N.B. this hash function returns the same hash value for RTXes that
differ only in the order of operands, thus it is suitable for comparisons
that take commutativity into account.
If we wanted to also support associative rules, we'd have to use a different
strategy to avoid returning spurious 0, e.g. return ~(~0U >> 1) .
MEMMODE indicates the mode of an enclosing MEM, and it's only
used to compute autoinc values.
We used to have a MODE argument for hashing for CONST_INTs, but that
didn't make sense, since it caused spurious hash differences between
(set (reg:SI 1) (const_int))
(plus:SI (reg:SI 2) (reg:SI 1))
and
(plus:SI (reg:SI 2) (const_int))
If the mode is important in any context, it must be checked specifically
in a comparison anyway, since relying on hash differences is unsafe. ENTRY_VALUEs are function invariant, thus try to avoid
recursing on argument if ENTRY_VALUE is one of the
forms emitted by expand_debug_expr, otherwise
ENTRY_VALUE hash would depend on the current value
in some register or memory. This is like the general case, except that it only counts
the integers representing the constant. Assume there is only one rtx object for any given label.
We don't hash on the address of the CODE_LABEL to avoid bootstrap
differences and differences between each stage's debugging dumps. Don't hash on the symbol's address to avoid bootstrap differences.
Different hash values may cause expressions to be recorded in
different orders and thus different registers to be used in the
final assembler. This also avoids differences in the dump files
between various stages. We can't compute these without knowing the MEM mode.
Adjust the hash so that (mem:MEMMODE (pre_* (reg))) hashes
like (mem:MEMMODE (plus (reg) (const_int I))). unused
| bool cselib_have_permanent_equivalences | ( | void | ) |
Return TRUE if any permanent equivalences have been recorded since the table was last initialized.
| void cselib_init | ( | ) |
Initialize cselib for one pass. The caller must also call init_alias_analysis.
(mem:BLK (scratch)) is a special mechanism to conflict with everything,
see canon_true_dependence. This is only created once. We preserve reg_values to allow expensive clearing of the whole thing.
Reallocate it however if it happens to be too large. Some space for newly emit instructions so we don't end up
reallocating in between passes.
Referenced by chain_to_prev_insn_p().
|
static |
|
static |
Invalidate any locations in the table which are changed because of a store to MEM_RTX. If this is called because of a non-const call instruction, MEM_RTX is (mem:BLK const0_rtx).
MEMs may occur in locations only at the top level; below
that every MEM or REG is substituted by its VALUE. This one overlaps.
We must have a mapping from this MEM's address to the
value (E). Remove that, too. Record canonicalized elt.
References cselib_val_struct::locs, new_elt_list(), new_elt_loc_list(), and cselib_val_struct::val_rtx.
|
static |
|
static |
Invalidate any entries in reg_values that overlap REGNO. This is called if REGNO is changing. MODE is the mode of the assignment to REGNO, which is used to determine how many hard registers are being changed. If MODE is VOIDmode, then only REGNO is being changed; this is used when invalidating call clobbered registers across a call.
If we see pseudos after reload, something is _wrong_.
Determine the range of registers that must be invalidated. For
pseudos, only REGNO is affected. For hard regs, we must take MODE
into account, and we must also invalidate lower register numbers
if they contain values that overlap REGNO. Go through all known values for this reg; if it overlaps the range
we're invalidating, remove the value. We have an overlap.
Maintain the invariant that the first entry of
REG_VALUES, if present, must be the value used to set
the register, or NULL. This is also nice because
then we won't push the same regno onto user_regs
multiple times. Now, we clear the mapping from value to reg. It must exist, so
this code will crash intentionally if it doesn't.
References cselib_val_struct::addr_list, canon_anti_dependence(), canonical_cselib_val(), cselib_lookup(), elt_list::next, elt_loc_list::next, unchain_one_elt_list(), and unchain_one_elt_loc_list().
| void cselib_invalidate_rtx | ( | ) |
Invalidate DEST, which is being assigned to or clobbered.
A wrapper for cselib_invalidate_rtx to be called via note_stores.
| cselib_val* cselib_lookup | ( | rtx | x, |
| enum machine_mode | mode, | ||
| int | create, | ||
| enum machine_mode | memmode | ||
| ) |
Wrapper for cselib_lookup_1, that logs the lookup result and maintains invariants related with debug insns.
??? Should we return NULL if we're not to create an entry, the
found loc is a debug loc and cselib_current_insn is not DEBUG?
If so, we should also avoid converting val to non-DEBUG; probably
easiest setting cselib_current_insn to NULL before the call
above.
Referenced by add_stores(), cselib_invalidate_regno(), cselib_reg_set_mode(), dataflow_set_destroy(), debug_ilist(), and vt_stack_adjustments().
|
static |
Look up the rtl expression X in our tables and return the value it has. If CREATE is zero, we return NULL if we don't know the value. Otherwise, we create a new one if possible, using mode MODE if X doesn't have a mode (i.e. because it's a constant). When X is part of an address, MEMMODE should be the mode of the enclosing MEM if we're tracking autoinc expressions.
Maintain the invariant that the first entry of
REG_VALUES, if present, must be the value used to set the
register, or NULL. During var-tracking, try harder to find equivalences
for SUBREGs. If a setter sets say a DImode register
and user uses that register only in SImode, add a lowpart
subreg location. Can't even create if hashing is not possible.
We have to fill the slot before calling cselib_subst_to_values:
the hash table is inconsistent until we do so, and
cselib_subst_to_values will need to do lookups.
| cselib_val* cselib_lookup_from_insn | ( | rtx | x, |
| enum machine_mode | mode, | ||
| int | create, | ||
| enum machine_mode | memmode, | ||
| rtx | insn | ||
| ) |
Wrapper for cselib_lookup, that indicates X is in INSN.
Referenced by sched_analyze_2().
|
static |
|
static |
Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx. If CREATE, make a new one if we haven't seen it before.
Look up the value for the address.
Find a value that describes a value of our mode at that address.
References dump_file, elt_loc_list::loc, and print_inline_rtx().
| void cselib_preserve_cfa_base_value | ( | ) |
Arrange for a REG value to be assumed constant through the whole function, never invalidated and preserved across cselib_reset_table calls.
| void cselib_preserve_only_values | ( | void | ) |
Clean all non-constant expressions in the hash table, but retain their values.
| void cselib_preserve_value | ( | ) |
Arrange for a value to not be removed from the hash table even if it becomes useless.
References cselib_val_struct::val_rtx.
Referenced by same_variable_part_p().
| bool cselib_preserved_value_p | ( | ) |
Test whether a value is preserved.
Referenced by add_stores().
| void cselib_process_insn | ( | ) |
Record the effects of INSN.
Forget everything at a CODE_LABEL, a volatile insn, or a setjmp.
If this is a call instruction, forget anything stored in a
call clobbered register, or, if this is not a const call, in
memory. Since it is not clear how cselib is going to be used, be
conservative here and treat looping pure or const functions
as if they were regular functions. Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
after we have processed the insn. Flush evertything on setjmp.
On setter of the hard frame pointer if frame_pointer_needed,
invalidate stack_pointer_rtx, so that sp and {,h}fp based
VALUEs are distinct. remove_useless_values is linear in the hash table size. Avoid
quadratic behavior for very large hashtables with very few
useless elements.
References cselib_val_struct::addr_list, elt_list::elt, elt_loc_list::loc, cselib_val_struct::locs, elt_list::next, elt_loc_list::next, cselib_val_struct::next_containing_mem, print_inline_rtx(), elt_loc_list::setting_insn, and cselib_val_struct::val_rtx.
Referenced by record_entry_value(), and reload_cse_regs_1().
|
static |
Callback for for_each_inc_dec. Records in ARG the SETs implied by autoinc RTXs: SRC plus SRCOFF if non-NULL is stored in DEST.
|
static |
|
static |
Record the result of a SET instruction. DEST is being set; the source contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT describes its address.
The register should have been invalidated.
|
static |
|
static |
Record the effects of any sets and autoincs in INSN.
Find all sets.
Look through the PARALLEL and record the values being
set, if possible. Also handle any CLOBBERs. Look up the values that are read. Do this before invalidating the
locations that are written. A STRICT_LOW_PART can be ignored; we'll record the equivalence for
the low part after invalidating any knowledge about larger modes. We don't know how to record anything but REG or MEM.
Invalidate all locations written by this insn. Note that the elts we
looked up in the previous loop aren't affected, just some of their
locations may go away. If this is an asm, look for duplicate sets. This can happen when the
user uses the same value as an output multiple times. This is valid
if the outputs are not actually used thereafter. Treat this case as
if the value isn't actually set. We do this by smashing the destination
to pc_rtx, so that we won't record the value later. Now enter the equivalences in our tables.
References find_reg_note(), and modified_in_p().
| enum machine_mode cselib_reg_set_mode | ( | ) |
Return the mode in which a register was last set. If X is not a register, return its mode. If the mode in which the register was set is not known, or the value was already clobbered, return VOIDmode.
References cselib_lookup().
| void cselib_reset_table | ( | ) |
Remove all entries from the hash table, arranging for the next value to be numbered NUM.
Referenced by unchain_one_elt_list().
| void cselib_set_value_sp_based | ( | ) |
Arrange for a value to be marked as based on stack pointer for find_base_term purposes.
| bool cselib_sp_based_value_p | ( | ) |
Test whether a value is based on stack pointer for find_base_term purposes.
Referenced by rtx_equal_for_memref_p().
| rtx cselib_subst_to_values | ( | ) |
Walk rtx X and replace all occurrences of REG and MEM subexpressions with VALUE expressions. This way, it becomes independent of changes to registers and memory. X isn't actually modified; if modifications are needed, new rtl is allocated. However, the return value can share rtl with X. If X is within a MEM, MEMMODE must be the mode of the MEM.
This used to happen for autoincrements, but we deal with them
properly now. Remove the if stmt for the next release. Assign a value that doesn't match any other.
| rtx cselib_subst_to_values_from_insn | ( | ) |
Wrapper for cselib_subst_to_values, that indicates X is in INSN.
| int discard_useless_locs | ( | ) |
For all locations found in X, delete locations that reference useless values (i.e. values without any location). Called through htab_traverse.
References canonical_cselib_val(), dummy_val, first_containing_mem, cselib_val_struct::locs, n_useless_debug_values, cselib_val_struct::next_containing_mem, and hash_table< Descriptor, Allocator >::traverse().
| int discard_useless_values | ( | ) |
If X is a value with no locations, remove it from the hashtable.
| void dump_cselib_table | ( | ) |
Dump to OUT everything in the CSELIB table.
Referenced by record_entry_value().
| int dump_cselib_val | ( | ) |
Dump the cselib_val *X to FILE *OUT.
|
static |
Search through the possible substitutions in P. We prefer a non reg substitution because this allows us to expand the tree further. If we find, just a reg, take the lowest regno. There may be several non-reg results, we just take the first one because they will all expand to the same place.
Return these right away to avoid returning stack pointer based
expressions for frame pointer and vice versa, which is something
that would confuse DSE. See the comment in cselib_expand_value_rtx_1
for more details. Avoid infinite recursion trying to expand a reg into a
the same reg. Avoid infinite recursion and do not try to expand the
value.
References expand_value_data::callback, expand_value_data::callback_arg, cselib_expand_value_rtx_1(), expand_value_data::dummy, and expand_value_data::regs_active.
| bool fp_setter_insn | ( | ) |
Return true if INSN in the prologue initializes hard_frame_pointer_rtx.
Don't return true for frame pointer restores in the epilogue.
References cfa_base_preserved_regno, cselib_any_perm_equivs, cselib_clear_table(), cselib_discard_hook, cselib_preserve_constants, hash_table< Descriptor, Allocator >::dispose(), free(), and free_alloc_pool().
|
static |
Return TRUE if V is a constant, a function invariant or a VALUE equivalence; FALSE otherwise.
Keep VALUE equivalences around.
Although a debug expr may be bound to different expressions,
we can preserve it as if it was constant, to get unification
and proper merging within var-tracking. (plus (value V) (const_int C)) is invariant iff V is invariant.
References hash_table< Descriptor, Allocator >::clear_slot().
|
static |
|
inlinestatic |
Create a new value structure for VALUE and initialize it. The mode of the value is MODE.
We use an alloc pool to allocate this RTL construct because it
accounts for about 8% of the overall memory usage. We know
precisely when we can have VALUE RTXen (when cselib is active)
so we don't need to put them in garbage collected memory.
??? Why should a VALUE be an RTX in the first place?
|
staticread |
Referenced by cselib_invalidate_mem().
|
staticread |
Allocate a struct elt_list and fill in its two elements with the arguments.
|
static |
Referenced by cselib_invalidate_mem().
|
inlinestatic |
Allocate a struct elt_loc_list with LOC and prepend it to VAL's loc list.
If we're creating the first loc in a debug insn context, we've
just created a debug value. Count it. Reverse the insertion.
Bring all locs from LOC to VAL.
Adjust values that have LOC as canonical so that VAL
becomes their canonical. Bring in addr_list into canonical node.
Add VAL to the containing_mem list after LOC. LOC will
be removed when we notice it doesn't contain any
MEMs. Chain LOC back to VAL.
| int preserve_constants_and_equivs | ( | ) |
Remove from hash table all VALUEs except constants, function invariants and VALUE equivalences.
References cselib_any_perm_equivs, and hash_table< Descriptor, Allocator >::empty().
|
inlinestatic |
|
inlinestatic |
Promote loc L to a nondebug cselib_current_insn if L is marked as originating from a debug insn, maintaining the debug values count.
References elt_loc_list::next, and pool_free().
| int references_value_p | ( | ) |
Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we only return true for values which point to a cselib_val whose value element has been set to zero, which implies the cselib_val will be removed.
Referenced by cselib_find_slot().
|
static |
Clean out useless values (i.e. those which no longer have locations associated with them) from the hash table.
First pass: eliminate locations that reference the value. That in
turn can make more values useless. Second pass: actually remove the values.
References cfa_base_preserved_regno, cselib_preserve_constants, elt_loc_list::loc, and cselib_val_struct::locs.
|
static |
Return nonzero if we can prove that X and Y contain the same value, taking our gathered information into account. MEMMODE holds the mode of the enclosing MEM, if any, as required to deal with autoinc addressing modes. If X and Y are not (known to be) part of addresses, MEMMODE should be VOIDmode.
Avoid infinite recursion. We know we have the canonical
value, so we can just skip any values in the equivalence
list. Don't recurse if nothing changed.
These won't be handled correctly by the code below.
ENTRY_VALUEs are function invariant, it is thus undesirable to
use rtx_equal_for_cselib_1 to compare the operands. We have to compare any autoinc operations in the addresses
using this MEM's mode. Two vectors must have the same length.
And the corresponding elements must match.
These are just backpointers, so they don't matter.
It is believed that rtx's at this level will never
contain anything but integers and other rtx's,
except for within LABEL_REFs and SYMBOL_REFs.
| int rtx_equal_for_cselib_p | ( | ) |
Return nonzero if we can prove that X and Y contain the same value, taking our gathered information into account.
|
static |
Referenced by cselib_invalidate_regno().
|
inlinestatic |
The elt_list at *PL is no longer needed. Unchain it and free its storage.
References cselib_reset_table().
|
static |
Referenced by cselib_find_slot(), and cselib_invalidate_regno().
|
static |
Likewise for elt_loc_lists.
References elt_loc_list::loc, and cselib_val_struct::locs.
|
static |
|
static |
Likewise for cselib_vals. This also frees the addr_list associated with V.
|
static |
We need to pass down the mode of constants through the hash table functions. For that purpose, wrap them in a CONST of the appropriate mode.
Variable Documentation
|
static |
We pass this to cselib_invalidate_mem to invalidate all of memory for a non-const call instruction.
|
static |
Referenced by add_mem_for_addr(), fp_setter_insn(), and remove_useless_values().
|
static |
If non-NULL, value of the eliminated arg_pointer_rtx or frame_pointer_rtx that is constant through the whole function and should never be eliminated.
|
static |
Referenced by fp_setter_insn(), and preserve_constants_and_equivs().
|
static |
This is a global so we don't have to pass this through every function. It is used in new_elt_loc_list to set SETTING_INSN.
| void(* cselib_discard_hook)(cselib_val *) |
If nonnull, cselib will call this function before freeing useless VALUEs. A VALUE is deemed useless if its "locs" field is null.
Referenced by fp_setter_insn().
|
static |
A table that enables us to look up elts by their value.
|
static |
The number of registers we had when the varrays were last resized.
|
static |
Referenced by fp_setter_insn(), and remove_useless_values().
|
static |
| void(* cselib_record_sets_hook)(rtx insn, struct cselib_set *sets, int n_sets) |
If nonnull, cselib will call this function before recording sets or even clobbering outputs of INSN. All the recorded sets will be represented in the array sets[n_sets]. new_val_min can be used to tell whether values present in sets are introduced by this instruction.
|
static |
|
static |
Used as stop element of the containing_mem list so we can check presence in the list by checking the next pointer.
Referenced by discard_useless_locs().
|
static |
|
static |
|
static |
See the documentation of cselib_find_slot below.
|
static |
Used to list all values that contain memory reference. May or may not contain the useless values - the list is compacted each time memory is invalidated.
Referenced by discard_useless_locs().
|
static |
The largest number of hard regs used by any entry added to the REG_VALUES table. Cleared on each cselib_clear_table() invocation.
|
static |
Count values whose locs have been taken exclusively from debug insns for the entire life of the value.
|
static |
|
static |
Referenced by discard_useless_locs().
|
static |
Count values without known locations, or with only locations that wouldn't have been known except for debug insns. Whenever this grows too big, we remove these useless values from the table. Counting values with only debug values is a bit tricky. We don't want to increment n_useless_values when we create a value for a debug insn, for this would get n_useless_values out of sync, but we want increment it if all locs in the list that were ever referenced in nondebug insns are removed from the list. In the general case, once we do that, we'd have to stop accepting nondebug expressions in the loc list, to avoid having two values equivalent that, without debug insns, would have been made into separate values. However, because debug insns never introduce equivalences themselves (no assignments), the only means for growing loc lists is through nondebug assignments. If the locs also happen to be referenced in debug insns, it will work just fine. A consequence of this is that there's at most one debug-only loc in each loc list. If we keep it in the first entry, testing whether we have a debug-only loc list takes O(1). Furthermore, since any additional entry in a loc list containing a debug loc would have to come from an assignment (nondebug) that references both the initial debug loc and the newly-equivalent loc, the initial debug loc would be promoted to a nondebug loc, and the loc list would not contain debug locs any more. So the only case we have to be careful with in order to keep n_useless_values in sync between debug and nondebug compilations is to avoid incrementing n_useless_values when removing the single loc from a value that turns out to not appear outside debug values. We increment n_useless_debug_values instead, and leave such values alone until, for other reasons, we garbage-collect useless values.
|
static |
The unique id that the next create value will take.
|
static |
This table maps from register number to values. It does not contain pointers to cselib_val structures, but rather elt_lists. The purpose is to be able to refer to the same register in different modes. The first element of the list defines the mode in which the register was set; if the mode is unknown or the value is no longer valid in that mode, ELT will be NULL for the first element.
|
static |
|
static |
Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used in cselib_clear_table() for fast emptying.
Referenced by saved_hard_reg_compare_func().
|
static |
|
static |
Set by discard_useless_locs if it deleted the last location of any value.
