/* Loop invariant motion.
- Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2010
- Free Software Foundation, Inc.
+ Copyright (C) 2003-2013 Free Software Foundation, Inc.
This file is part of GCC.
#include "tm_p.h"
#include "basic-block.h"
#include "gimple-pretty-print.h"
-#include "tree-flow.h"
+#include "gimple.h"
+#include "gimplify.h"
+#include "gimple-iterator.h"
+#include "gimplify-me.h"
+#include "gimple-ssa.h"
+#include "tree-cfg.h"
+#include "tree-phinodes.h"
+#include "ssa-iterators.h"
+#include "stringpool.h"
+#include "tree-ssanames.h"
+#include "tree-ssa-loop-manip.h"
+#include "tree-ssa-loop.h"
+#include "tree-into-ssa.h"
#include "cfgloop.h"
#include "domwalk.h"
#include "params.h"
#include "tree-pass.h"
#include "flags.h"
-#include "hashtab.h"
+#include "hash-table.h"
#include "tree-affine.h"
#include "pointer-set.h"
#include "tree-ssa-propagate.h"
+#include "trans-mem.h"
/* TODO: Support for predicated code motion. I.e.
something;
} */
-/* A type for the list of statements that have to be moved in order to be able
- to hoist an invariant computation. */
-
-struct depend
-{
- gimple stmt;
- struct depend *next;
-};
-
/* The auxiliary data kept for each statement. */
struct lim_aux_data
unsigned cost; /* Cost of the computation performed by the
statement. */
- struct depend *depends; /* List of statements that must be also hoisted
- out of the loop when this statement is
- hoisted; i.e. those that define the operands
- of the statement and are inside of the
- MAX_LOOP loop. */
+ vec<gimple> depends; /* Vector of statements that must be also
+ hoisted out of the loop when this statement
+ is hoisted; i.e. those that define the
+ operands of the statement and are inside of
+ the MAX_LOOP loop. */
};
/* Maps statements to their lim_aux_data. */
gimple stmt; /* The statement in that it occurs. */
} *mem_ref_loc_p;
-DEF_VEC_P(mem_ref_loc_p);
-DEF_VEC_ALLOC_P(mem_ref_loc_p, heap);
-
-/* The list of memory reference locations in a loop. */
-
-typedef struct mem_ref_locs
-{
- VEC (mem_ref_loc_p, heap) *locs;
-} *mem_ref_locs_p;
-
-DEF_VEC_P(mem_ref_locs_p);
-DEF_VEC_ALLOC_P(mem_ref_locs_p, heap);
/* Description of a memory reference. */
typedef struct mem_ref
{
- tree mem; /* The memory itself. */
unsigned id; /* ID assigned to the memory reference
(its index in memory_accesses.refs_list) */
hashval_t hash; /* Its hash value. */
- bitmap stored; /* The set of loops in that this memory location
+
+ /* The memory access itself and associated caching of alias-oracle
+ query meta-data. */
+ ao_ref mem;
+
+ bitmap_head stored; /* The set of loops in that this memory location
is stored to. */
- VEC (mem_ref_locs_p, heap) *accesses_in_loop;
+ vec<vec<mem_ref_loc> > accesses_in_loop;
/* The locations of the accesses. Vector
indexed by the loop number. */
/* The following sets are computed on demand. We keep both set and
its complement, so that we know whether the information was
already computed or not. */
- bitmap indep_loop; /* The set of loops in that the memory
+ bitmap_head indep_loop; /* The set of loops in that the memory
reference is independent, meaning:
If it is stored in the loop, this store
is independent on all other loads and
stores.
If it is only loaded, then it is independent
on all stores in the loop. */
- bitmap dep_loop; /* The complement of INDEP_LOOP. */
-
- bitmap indep_ref; /* The set of memory references on that
- this reference is independent. */
- bitmap dep_ref; /* The complement of INDEP_REF. */
+ bitmap_head dep_loop; /* The complement of INDEP_LOOP. */
} *mem_ref_p;
-DEF_VEC_P(mem_ref_p);
-DEF_VEC_ALLOC_P(mem_ref_p, heap);
+/* We use two bits per loop in the ref->{in,}dep_loop bitmaps, the first
+ to record (in)dependence against stores in the loop and its subloops, the
+ second to record (in)dependence against all references in the loop
+ and its subloops. */
+#define LOOP_DEP_BIT(loopnum, storedp) (2 * (loopnum) + (storedp ? 1 : 0))
+
+/* Mem_ref hashtable helpers. */
+
+struct mem_ref_hasher : typed_noop_remove <mem_ref>
+{
+ typedef mem_ref value_type;
+ typedef tree_node compare_type;
+ static inline hashval_t hash (const value_type *);
+ static inline bool equal (const value_type *, const compare_type *);
+};
+
+/* A hash function for struct mem_ref object OBJ. */
+
+inline hashval_t
+mem_ref_hasher::hash (const value_type *mem)
+{
+ return mem->hash;
+}
+
+/* An equality function for struct mem_ref object MEM1 with
+ memory reference OBJ2. */
-DEF_VEC_P(bitmap);
-DEF_VEC_ALLOC_P(bitmap, heap);
+inline bool
+mem_ref_hasher::equal (const value_type *mem1, const compare_type *obj2)
+{
+ return operand_equal_p (mem1->mem.ref, (const_tree) obj2, 0);
+}
-DEF_VEC_P(htab_t);
-DEF_VEC_ALLOC_P(htab_t, heap);
/* Description of memory accesses in loops. */
static struct
{
/* The hash table of memory references accessed in loops. */
- htab_t refs;
+ hash_table <mem_ref_hasher> refs;
/* The list of memory references. */
- VEC (mem_ref_p, heap) *refs_list;
+ vec<mem_ref_p> refs_list;
/* The set of memory references accessed in each loop. */
- VEC (bitmap, heap) *refs_in_loop;
+ vec<bitmap_head> refs_in_loop;
- /* The set of memory references accessed in each loop, including
- subloops. */
- VEC (bitmap, heap) *all_refs_in_loop;
+ /* The set of memory references stored in each loop. */
+ vec<bitmap_head> refs_stored_in_loop;
- /* The set of memory references stored in each loop, including
- subloops. */
- VEC (bitmap, heap) *all_refs_stored_in_loop;
+ /* The set of memory references stored in each loop, including subloops . */
+ vec<bitmap_head> all_refs_stored_in_loop;
/* Cache for expanding memory addresses. */
struct pointer_map_t *ttae_cache;
#define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
#define SET_ALWAYS_EXECUTED_IN(BB, VAL) ((BB)->aux = (void *) (VAL))
+/* ID of the shared unanalyzable mem. */
+#define UNANALYZABLE_MEM_ID 0
+
/* Whether the reference was analyzable. */
-#define MEM_ANALYZABLE(REF) ((REF)->mem != error_mark_node)
+#define MEM_ANALYZABLE(REF) ((REF)->id != UNANALYZABLE_MEM_ID)
static struct lim_aux_data *
init_lim_data (gimple stmt)
static void
free_lim_aux_data (struct lim_aux_data *data)
{
- struct depend *dep, *next;
-
- for (dep = data->depends; dep; dep = next)
- {
- next = dep->next;
- free (dep);
- }
+ data->depends.release ();
free (data);
}
*p = NULL;
}
-/* Calls CBCK for each index in memory reference ADDR_P. There are two
- kinds situations handled; in each of these cases, the memory reference
- and DATA are passed to the callback:
-
- Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
- pass the pointer to the index to the callback.
-
- Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
- pointer to addr to the callback.
-
- If the callback returns false, the whole search stops and false is returned.
- Otherwise the function returns true after traversing through the whole
- reference *ADDR_P. */
-
-bool
-for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
-{
- tree *nxt, *idx;
-
- for (; ; addr_p = nxt)
- {
- switch (TREE_CODE (*addr_p))
- {
- case SSA_NAME:
- return cbck (*addr_p, addr_p, data);
-
- case MEM_REF:
- nxt = &TREE_OPERAND (*addr_p, 0);
- return cbck (*addr_p, nxt, data);
-
- case BIT_FIELD_REF:
- case VIEW_CONVERT_EXPR:
- case REALPART_EXPR:
- case IMAGPART_EXPR:
- nxt = &TREE_OPERAND (*addr_p, 0);
- break;
-
- case COMPONENT_REF:
- /* If the component has varying offset, it behaves like index
- as well. */
- idx = &TREE_OPERAND (*addr_p, 2);
- if (*idx
- && !cbck (*addr_p, idx, data))
- return false;
-
- nxt = &TREE_OPERAND (*addr_p, 0);
- break;
- case ARRAY_REF:
- case ARRAY_RANGE_REF:
- nxt = &TREE_OPERAND (*addr_p, 0);
- if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
- return false;
- break;
-
- case VAR_DECL:
- case PARM_DECL:
- case STRING_CST:
- case RESULT_DECL:
- case VECTOR_CST:
- case COMPLEX_CST:
- case INTEGER_CST:
- case REAL_CST:
- case FIXED_CST:
- case CONSTRUCTOR:
- return true;
-
- case ADDR_EXPR:
- gcc_assert (is_gimple_min_invariant (*addr_p));
- return true;
-
- case TARGET_MEM_REF:
- idx = &TMR_BASE (*addr_p);
- if (*idx
- && !cbck (*addr_p, idx, data))
- return false;
- idx = &TMR_INDEX (*addr_p);
- if (*idx
- && !cbck (*addr_p, idx, data))
- return false;
- idx = &TMR_INDEX2 (*addr_p);
- if (*idx
- && !cbck (*addr_p, idx, data))
- return false;
- return true;
+/* The possibilities of statement movement. */
+enum move_pos
+ {
+ MOVE_IMPOSSIBLE, /* No movement -- side effect expression. */
+ MOVE_PRESERVE_EXECUTION, /* Must not cause the non-executed statement
+ become executed -- memory accesses, ... */
+ MOVE_POSSIBLE /* Unlimited movement. */
+ };
- default:
- gcc_unreachable ();
- }
- }
-}
/* If it is possible to hoist the statement STMT unconditionally,
returns MOVE_POSSIBLE.
gimple def_stmt = SSA_NAME_DEF_STMT (def);
basic_block def_bb = gimple_bb (def_stmt);
struct loop *max_loop;
- struct depend *dep;
struct lim_aux_data *def_data;
if (!def_bb)
&& def_bb->loop_father == loop)
data->cost += def_data->cost;
- dep = XNEW (struct depend);
- dep->stmt = def_stmt;
- dep->next = data->depends;
- data->depends = dep;
+ data->depends.safe_push (def_stmt);
return true;
}
{
struct loop *aloop;
- if (bitmap_bit_p (ref->stored, loop->num))
+ if (bitmap_bit_p (&ref->stored, loop->num))
return NULL;
for (aloop = outer;
aloop != loop;
aloop = superloop_at_depth (loop, loop_depth (aloop) + 1))
- if (!bitmap_bit_p (ref->stored, aloop->num)
+ if (!bitmap_bit_p (&ref->stored, aloop->num)
&& ref_indep_loop_p (aloop, ref))
return aloop;
gcc_assert (!store);
hash = iterative_hash_expr (*mem, 0);
- ref = (mem_ref_p) htab_find_with_hash (memory_accesses.refs, *mem, hash);
+ ref = memory_accesses.refs.find_with_hash (*mem, hash);
gcc_assert (ref != NULL);
return ref;
set_level (gimple stmt, struct loop *orig_loop, struct loop *level)
{
struct loop *stmt_loop = gimple_bb (stmt)->loop_father;
- struct depend *dep;
struct lim_aux_data *lim_data;
+ gimple dep_stmt;
+ unsigned i;
stmt_loop = find_common_loop (orig_loop, stmt_loop);
lim_data = get_lim_data (stmt);
|| flow_loop_nested_p (lim_data->max_loop, level));
lim_data->tgt_loop = level;
- for (dep = lim_data->depends; dep; dep = dep->next)
- set_level (dep->stmt, orig_loop, level);
+ FOR_EACH_VEC_ELT (lim_data->depends, i, dep_stmt)
+ set_level (dep_stmt, orig_loop, level);
}
/* Determines an outermost loop from that we want to hoist the statement STMT.
return stmt;
}
+/* For each statement determines the outermost loop in that it is invariant,
+ - statements on whose motion it depends and the cost of the computation.
+ - This information is stored to the LIM_DATA structure associated with
+ - each statement. */
+class invariantness_dom_walker : public dom_walker
+{
+public:
+ invariantness_dom_walker (cdi_direction direction)
+ : dom_walker (direction) {}
+
+ virtual void before_dom_children (basic_block);
+};
/* Determine the outermost loops in that statements in basic block BB are
invariant, and record them to the LIM_DATA associated with the statements.
- Callback for walk_dominator_tree. */
+ Callback for dom_walker. */
-static void
-determine_invariantness_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
- basic_block bb)
+void
+invariantness_dom_walker::before_dom_children (basic_block bb)
{
enum move_pos pos;
gimple_stmt_iterator bsi;
}
}
-/* For each statement determines the outermost loop in that it is invariant,
- statements on whose motion it depends and the cost of the computation.
- This information is stored to the LIM_DATA structure associated with
- each statement. */
+class move_computations_dom_walker : public dom_walker
+{
+public:
+ move_computations_dom_walker (cdi_direction direction)
+ : dom_walker (direction), todo_ (0) {}
-static void
-determine_invariantness (void)
+ virtual void before_dom_children (basic_block);
+
+ unsigned int todo_;
+};
+
+/* Return true if CODE is an operation that when operating on signed
+ integer types involves undefined behavior on overflow and the
+ operation can be expressed with unsigned arithmetic. */
+
+static bool
+arith_code_with_undefined_signed_overflow (tree_code code)
+{
+ switch (code)
+ {
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ case MULT_EXPR:
+ case NEGATE_EXPR:
+ case POINTER_PLUS_EXPR:
+ return true;
+ default:
+ return false;
+ }
+}
+
+/* Rewrite STMT, an assignment with a signed integer or pointer arithmetic
+ operation that can be transformed to unsigned arithmetic by converting
+ its operand, carrying out the operation in the corresponding unsigned
+ type and converting the result back to the original type.
+
+ Returns a sequence of statements that replace STMT and also contain
+ a modified form of STMT itself. */
+
+static gimple_seq
+rewrite_to_defined_overflow (gimple stmt)
{
- struct dom_walk_data walk_data;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "rewriting stmt with undefined signed "
+ "overflow ");
+ print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+ }
- memset (&walk_data, 0, sizeof (struct dom_walk_data));
- walk_data.dom_direction = CDI_DOMINATORS;
- walk_data.before_dom_children = determine_invariantness_stmt;
+ tree lhs = gimple_assign_lhs (stmt);
+ tree type = unsigned_type_for (TREE_TYPE (lhs));
+ gimple_seq stmts = NULL;
+ for (unsigned i = 1; i < gimple_num_ops (stmt); ++i)
+ {
+ gimple_seq stmts2 = NULL;
+ gimple_set_op (stmt, i,
+ force_gimple_operand (fold_convert (type,
+ gimple_op (stmt, i)),
+ &stmts2, true, NULL_TREE));
+ gimple_seq_add_seq (&stmts, stmts2);
+ }
+ gimple_assign_set_lhs (stmt, make_ssa_name (type, stmt));
+ if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
+ gimple_assign_set_rhs_code (stmt, PLUS_EXPR);
+ gimple_seq_add_stmt (&stmts, stmt);
+ gimple cvt = gimple_build_assign_with_ops
+ (NOP_EXPR, lhs, gimple_assign_lhs (stmt), NULL_TREE);
+ gimple_seq_add_stmt (&stmts, cvt);
- init_walk_dominator_tree (&walk_data);
- walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
- fini_walk_dominator_tree (&walk_data);
+ return stmts;
}
/* Hoist the statements in basic block BB out of the loops prescribed by
data stored in LIM_DATA structures associated with each statement. Callback
for walk_dominator_tree. */
-static void
-move_computations_stmt (struct dom_walk_data *dw_data,
- basic_block bb)
+void
+move_computations_dom_walker::before_dom_children (basic_block bb)
{
struct loop *level;
gimple_stmt_iterator bsi;
new_stmt = gimple_build_assign_with_ops (TREE_CODE (arg),
gimple_phi_result (stmt),
arg, NULL_TREE);
- SSA_NAME_DEF_STMT (gimple_phi_result (stmt)) = new_stmt;
}
else
{
new_stmt = gimple_build_assign_with_ops (COND_EXPR,
gimple_phi_result (stmt),
t, arg0, arg1);
- SSA_NAME_DEF_STMT (gimple_phi_result (stmt)) = new_stmt;
- *((unsigned int *)(dw_data->global_data)) |= TODO_cleanup_cfg;
+ todo_ |= TODO_cleanup_cfg;
}
gsi_insert_on_edge (loop_preheader_edge (level), new_stmt);
remove_phi_node (&bsi, false);
}
}
gsi_remove (&bsi, false);
- gsi_insert_on_edge (e, stmt);
+ /* In case this is a stmt that is not unconditionally executed
+ when the target loop header is executed and the stmt may
+ invoke undefined integer or pointer overflow rewrite it to
+ unsigned arithmetic. */
+ if (is_gimple_assign (stmt)
+ && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt)))
+ && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (gimple_assign_lhs (stmt)))
+ && arith_code_with_undefined_signed_overflow
+ (gimple_assign_rhs_code (stmt))
+ && (!ALWAYS_EXECUTED_IN (bb)
+ || !(ALWAYS_EXECUTED_IN (bb) == level
+ || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb), level))))
+ gsi_insert_seq_on_edge (e, rewrite_to_defined_overflow (stmt));
+ else
+ gsi_insert_on_edge (e, stmt);
}
}
static unsigned int
move_computations (void)
{
- struct dom_walk_data walk_data;
- unsigned int todo = 0;
-
- memset (&walk_data, 0, sizeof (struct dom_walk_data));
- walk_data.global_data = &todo;
- walk_data.dom_direction = CDI_DOMINATORS;
- walk_data.before_dom_children = move_computations_stmt;
-
- init_walk_dominator_tree (&walk_data);
- walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
- fini_walk_dominator_tree (&walk_data);
+ move_computations_dom_walker walker (CDI_DOMINATORS);
+ walker.walk (cfun->cfg->x_entry_block_ptr);
gsi_commit_edge_inserts ();
if (need_ssa_update_p (cfun))
rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
- return todo;
+ return walker.todo_;
}
/* Checks whether the statement defining variable *INDEX can be hoisted
return true;
}
-/* A hash function for struct mem_ref object OBJ. */
-
-static hashval_t
-memref_hash (const void *obj)
-{
- const struct mem_ref *const mem = (const struct mem_ref *) obj;
-
- return mem->hash;
-}
-
-/* An equality function for struct mem_ref object OBJ1 with
- memory reference OBJ2. */
-
-static int
-memref_eq (const void *obj1, const void *obj2)
-{
- const struct mem_ref *const mem1 = (const struct mem_ref *) obj1;
-
- return operand_equal_p (mem1->mem, (const_tree) obj2, 0);
-}
-
-/* Releases list of memory reference locations ACCS. */
-
-static void
-free_mem_ref_locs (mem_ref_locs_p accs)
-{
- unsigned i;
- mem_ref_loc_p loc;
-
- if (!accs)
- return;
-
- FOR_EACH_VEC_ELT (mem_ref_loc_p, accs->locs, i, loc)
- free (loc);
- VEC_free (mem_ref_loc_p, heap, accs->locs);
- free (accs);
-}
-
/* A function to free the mem_ref object OBJ. */
static void
memref_free (struct mem_ref *mem)
{
unsigned i;
- mem_ref_locs_p accs;
+ vec<mem_ref_loc> *accs;
- FOR_EACH_VEC_ELT (mem_ref_locs_p, mem->accesses_in_loop, i, accs)
- free_mem_ref_locs (accs);
- VEC_free (mem_ref_locs_p, heap, mem->accesses_in_loop);
+ FOR_EACH_VEC_ELT (mem->accesses_in_loop, i, accs)
+ accs->release ();
+ mem->accesses_in_loop.release ();
free (mem);
}
mem_ref_alloc (tree mem, unsigned hash, unsigned id)
{
mem_ref_p ref = XNEW (struct mem_ref);
- ref->mem = mem;
+ ao_ref_init (&ref->mem, mem);
ref->id = id;
ref->hash = hash;
- ref->stored = BITMAP_ALLOC (&lim_bitmap_obstack);
- ref->indep_loop = BITMAP_ALLOC (&lim_bitmap_obstack);
- ref->dep_loop = BITMAP_ALLOC (&lim_bitmap_obstack);
- ref->indep_ref = BITMAP_ALLOC (&lim_bitmap_obstack);
- ref->dep_ref = BITMAP_ALLOC (&lim_bitmap_obstack);
- ref->accesses_in_loop = NULL;
+ bitmap_initialize (&ref->stored, &lim_bitmap_obstack);
+ bitmap_initialize (&ref->indep_loop, &lim_bitmap_obstack);
+ bitmap_initialize (&ref->dep_loop, &lim_bitmap_obstack);
+ ref->accesses_in_loop.create (0);
return ref;
}
-/* Allocates and returns the new list of locations. */
-
-static mem_ref_locs_p
-mem_ref_locs_alloc (void)
-{
- mem_ref_locs_p accs = XNEW (struct mem_ref_locs);
- accs->locs = NULL;
- return accs;
-}
-
/* Records memory reference location *LOC in LOOP to the memory reference
description REF. The reference occurs in statement STMT. */
static void
record_mem_ref_loc (mem_ref_p ref, struct loop *loop, gimple stmt, tree *loc)
{
- mem_ref_loc_p aref = XNEW (struct mem_ref_loc);
- mem_ref_locs_p accs;
- bitmap ril = VEC_index (bitmap, memory_accesses.refs_in_loop, loop->num);
+ mem_ref_loc aref;
- if (VEC_length (mem_ref_locs_p, ref->accesses_in_loop)
+ if (ref->accesses_in_loop.length ()
<= (unsigned) loop->num)
- VEC_safe_grow_cleared (mem_ref_locs_p, heap, ref->accesses_in_loop,
- loop->num + 1);
- accs = VEC_index (mem_ref_locs_p, ref->accesses_in_loop, loop->num);
- if (!accs)
- {
- accs = mem_ref_locs_alloc ();
- VEC_replace (mem_ref_locs_p, ref->accesses_in_loop, loop->num, accs);
- }
-
- aref->stmt = stmt;
- aref->ref = loc;
+ ref->accesses_in_loop.safe_grow_cleared (loop->num + 1);
- VEC_safe_push (mem_ref_loc_p, heap, accs->locs, aref);
- bitmap_set_bit (ril, ref->id);
+ aref.stmt = stmt;
+ aref.ref = loc;
+ ref->accesses_in_loop[loop->num].safe_push (aref);
}
/* Marks reference REF as stored in LOOP. */
static void
mark_ref_stored (mem_ref_p ref, struct loop *loop)
{
- for (;
- loop != current_loops->tree_root
- && !bitmap_bit_p (ref->stored, loop->num);
- loop = loop_outer (loop))
- bitmap_set_bit (ref->stored, loop->num);
+ while (loop != current_loops->tree_root
+ && bitmap_set_bit (&ref->stored, loop->num))
+ loop = loop_outer (loop);
}
/* Gathers memory references in statement STMT in LOOP, storing the
{
tree *mem = NULL;
hashval_t hash;
- PTR *slot;
+ mem_ref **slot;
mem_ref_p ref;
bool is_stored;
unsigned id;
mem = simple_mem_ref_in_stmt (stmt, &is_stored);
if (!mem)
{
- id = VEC_length (mem_ref_p, memory_accesses.refs_list);
- ref = mem_ref_alloc (error_mark_node, 0, id);
- VEC_safe_push (mem_ref_p, heap, memory_accesses.refs_list, ref);
+ /* We use the shared mem_ref for all unanalyzable refs. */
+ id = UNANALYZABLE_MEM_ID;
+ ref = memory_accesses.refs_list[id];
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Unanalyzed memory reference %u: ", id);
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
}
- if (gimple_vdef (stmt))
- mark_ref_stored (ref, loop);
- record_mem_ref_loc (ref, loop, stmt, mem);
- return;
- }
-
- hash = iterative_hash_expr (*mem, 0);
- slot = htab_find_slot_with_hash (memory_accesses.refs, *mem, hash, INSERT);
-
- if (*slot)
- {
- ref = (mem_ref_p) *slot;
- id = ref->id;
+ is_stored = gimple_vdef (stmt);
}
else
{
- id = VEC_length (mem_ref_p, memory_accesses.refs_list);
- ref = mem_ref_alloc (*mem, hash, id);
- VEC_safe_push (mem_ref_p, heap, memory_accesses.refs_list, ref);
- *slot = ref;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
+ hash = iterative_hash_expr (*mem, 0);
+ slot = memory_accesses.refs.find_slot_with_hash (*mem, hash, INSERT);
+ if (*slot)
{
- fprintf (dump_file, "Memory reference %u: ", id);
- print_generic_expr (dump_file, ref->mem, TDF_SLIM);
- fprintf (dump_file, "\n");
+ ref = (mem_ref_p) *slot;
+ id = ref->id;
}
- }
+ else
+ {
+ id = memory_accesses.refs_list.length ();
+ ref = mem_ref_alloc (*mem, hash, id);
+ memory_accesses.refs_list.safe_push (ref);
+ *slot = ref;
- if (is_stored)
- mark_ref_stored (ref, loop);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Memory reference %u: ", id);
+ print_generic_expr (dump_file, ref->mem.ref, TDF_SLIM);
+ fprintf (dump_file, "\n");
+ }
+ }
- record_mem_ref_loc (ref, loop, stmt, mem);
+ record_mem_ref_loc (ref, loop, stmt, mem);
+ }
+ bitmap_set_bit (&memory_accesses.refs_in_loop[loop->num], ref->id);
+ if (is_stored)
+ {
+ bitmap_set_bit (&memory_accesses.refs_stored_in_loop[loop->num], ref->id);
+ mark_ref_stored (ref, loop);
+ }
return;
}
+static unsigned *bb_loop_postorder;
+
+/* qsort sort function to sort blocks after their loop fathers postorder. */
+
+static int
+sort_bbs_in_loop_postorder_cmp (const void *bb1_, const void *bb2_)
+{
+ basic_block bb1 = *(basic_block *)const_cast<void *>(bb1_);
+ basic_block bb2 = *(basic_block *)const_cast<void *>(bb2_);
+ struct loop *loop1 = bb1->loop_father;
+ struct loop *loop2 = bb2->loop_father;
+ if (loop1->num == loop2->num)
+ return 0;
+ return bb_loop_postorder[loop1->num] < bb_loop_postorder[loop2->num] ? -1 : 1;
+}
+
/* Gathers memory references in loops. */
static void
-gather_mem_refs_in_loops (void)
+analyze_memory_references (void)
{
gimple_stmt_iterator bsi;
- basic_block bb;
- struct loop *loop;
- loop_iterator li;
- bitmap lrefs, alrefs, alrefso;
-
+ basic_block bb, *bbs;
+ struct loop *loop, *outer;
+ unsigned i, n;
+
+ /* Initialize bb_loop_postorder with a mapping from loop->num to
+ its postorder index. */
+ i = 0;
+ bb_loop_postorder = XNEWVEC (unsigned, number_of_loops (cfun));
+ FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
+ bb_loop_postorder[loop->num] = i++;
+ /* Collect all basic-blocks in loops and sort them after their
+ loops postorder. */
+ i = 0;
+ bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS);
FOR_EACH_BB (bb)
+ if (bb->loop_father != current_loops->tree_root)
+ bbs[i++] = bb;
+ n = i;
+ qsort (bbs, n, sizeof (basic_block), sort_bbs_in_loop_postorder_cmp);
+ free (bb_loop_postorder);
+
+ /* Visit blocks in loop postorder and assign mem-ref IDs in that order.
+ That results in better locality for all the bitmaps. */
+ for (i = 0; i < n; ++i)
{
- loop = bb->loop_father;
- if (loop == current_loops->tree_root)
- continue;
-
+ basic_block bb = bbs[i];
for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
- gather_mem_refs_stmt (loop, gsi_stmt (bsi));
+ gather_mem_refs_stmt (bb->loop_father, gsi_stmt (bsi));
}
+ free (bbs);
+
/* Propagate the information about accessed memory references up
the loop hierarchy. */
- FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
+ FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
{
- lrefs = VEC_index (bitmap, memory_accesses.refs_in_loop, loop->num);
- alrefs = VEC_index (bitmap, memory_accesses.all_refs_in_loop, loop->num);
- bitmap_ior_into (alrefs, lrefs);
-
- if (loop_outer (loop) == current_loops->tree_root)
+ /* Finalize the overall touched references (including subloops). */
+ bitmap_ior_into (&memory_accesses.all_refs_stored_in_loop[loop->num],
+ &memory_accesses.refs_stored_in_loop[loop->num]);
+
+ /* Propagate the information about accessed memory references up
+ the loop hierarchy. */
+ outer = loop_outer (loop);
+ if (outer == current_loops->tree_root)
continue;
- alrefso = VEC_index (bitmap, memory_accesses.all_refs_in_loop,
- loop_outer (loop)->num);
- bitmap_ior_into (alrefso, alrefs);
- }
-}
-
-/* Create a mapping from virtual operands to references that touch them
- in LOOP. */
-
-static void
-create_vop_ref_mapping_loop (struct loop *loop)
-{
- bitmap refs = VEC_index (bitmap, memory_accesses.refs_in_loop, loop->num);
- struct loop *sloop;
- bitmap_iterator bi;
- unsigned i;
- mem_ref_p ref;
-
- EXECUTE_IF_SET_IN_BITMAP (refs, 0, i, bi)
- {
- ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
- for (sloop = loop; sloop != current_loops->tree_root;
- sloop = loop_outer (sloop))
- if (bitmap_bit_p (ref->stored, loop->num))
- {
- bitmap refs_stored
- = VEC_index (bitmap, memory_accesses.all_refs_stored_in_loop,
- sloop->num);
- bitmap_set_bit (refs_stored, ref->id);
- }
- }
-}
-
-/* For each non-clobbered virtual operand and each loop, record the memory
- references in this loop that touch the operand. */
-
-static void
-create_vop_ref_mapping (void)
-{
- loop_iterator li;
- struct loop *loop;
-
- FOR_EACH_LOOP (li, loop, 0)
- {
- create_vop_ref_mapping_loop (loop);
- }
-}
-
-/* Gathers information about memory accesses in the loops. */
-
-static void
-analyze_memory_references (void)
-{
- unsigned i;
- bitmap empty;
-
- memory_accesses.refs = htab_create (100, memref_hash, memref_eq, NULL);
- memory_accesses.refs_list = NULL;
- memory_accesses.refs_in_loop = VEC_alloc (bitmap, heap,
- number_of_loops ());
- memory_accesses.all_refs_in_loop = VEC_alloc (bitmap, heap,
- number_of_loops ());
- memory_accesses.all_refs_stored_in_loop = VEC_alloc (bitmap, heap,
- number_of_loops ());
-
- for (i = 0; i < number_of_loops (); i++)
- {
- empty = BITMAP_ALLOC (&lim_bitmap_obstack);
- VEC_quick_push (bitmap, memory_accesses.refs_in_loop, empty);
- empty = BITMAP_ALLOC (&lim_bitmap_obstack);
- VEC_quick_push (bitmap, memory_accesses.all_refs_in_loop, empty);
- empty = BITMAP_ALLOC (&lim_bitmap_obstack);
- VEC_quick_push (bitmap, memory_accesses.all_refs_stored_in_loop, empty);
+ bitmap_ior_into (&memory_accesses.all_refs_stored_in_loop[outer->num],
+ &memory_accesses.all_refs_stored_in_loop[loop->num]);
}
-
- memory_accesses.ttae_cache = NULL;
-
- gather_mem_refs_in_loops ();
- create_vop_ref_mapping ();
}
/* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
tree_to_aff_combination_expand. */
static bool
-mem_refs_may_alias_p (tree mem1, tree mem2, struct pointer_map_t **ttae_cache)
+mem_refs_may_alias_p (mem_ref_p mem1, mem_ref_p mem2,
+ struct pointer_map_t **ttae_cache)
{
/* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
object and their offset differ in such a way that the locations cannot
overlap, then they cannot alias. */
- double_int size1, size2;
+ widest_int size1, size2;
aff_tree off1, off2;
/* Perform basic offset and type-based disambiguation. */
- if (!refs_may_alias_p (mem1, mem2))
+ if (!refs_may_alias_p_1 (&mem1->mem, &mem2->mem, true))
return false;
/* The expansion of addresses may be a bit expensive, thus we only do
if (optimize < 2)
return true;
- get_inner_reference_aff (mem1, &off1, &size1);
- get_inner_reference_aff (mem2, &off2, &size2);
+ get_inner_reference_aff (mem1->mem.ref, &off1, &size1);
+ get_inner_reference_aff (mem2->mem.ref, &off2, &size2);
aff_combination_expand (&off1, ttae_cache);
aff_combination_expand (&off2, ttae_cache);
- aff_combination_scale (&off1, double_int_minus_one);
+ aff_combination_scale (&off1, -1);
aff_combination_add (&off2, &off1);
if (aff_comb_cannot_overlap_p (&off2, size1, size2))
return true;
}
-/* Rewrites location LOC by TMP_VAR. */
-
-static void
-rewrite_mem_ref_loc (mem_ref_loc_p loc, tree tmp_var)
-{
- *loc->ref = tmp_var;
- update_stmt (loc->stmt);
-}
+/* Iterates over all locations of REF in LOOP and its subloops calling
+ fn.operator() with the location as argument. When that operator
+ returns true the iteration is stopped and true is returned.
+ Otherwise false is returned. */
-/* Adds all locations of REF in LOOP and its subloops to LOCS. */
-
-static void
-get_all_locs_in_loop (struct loop *loop, mem_ref_p ref,
- VEC (mem_ref_loc_p, heap) **locs)
+template <typename FN>
+static bool
+for_all_locs_in_loop (struct loop *loop, mem_ref_p ref, FN fn)
{
- mem_ref_locs_p accs;
unsigned i;
mem_ref_loc_p loc;
- bitmap refs = VEC_index (bitmap, memory_accesses.all_refs_in_loop,
- loop->num);
struct loop *subloop;
- if (!bitmap_bit_p (refs, ref->id))
- return;
-
- if (VEC_length (mem_ref_locs_p, ref->accesses_in_loop)
- > (unsigned) loop->num)
- {
- accs = VEC_index (mem_ref_locs_p, ref->accesses_in_loop, loop->num);
- if (accs)
- {
- FOR_EACH_VEC_ELT (mem_ref_loc_p, accs->locs, i, loc)
- VEC_safe_push (mem_ref_loc_p, heap, *locs, loc);
- }
- }
+ if (ref->accesses_in_loop.length () > (unsigned) loop->num)
+ FOR_EACH_VEC_ELT (ref->accesses_in_loop[loop->num], i, loc)
+ if (fn (loc))
+ return true;
for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
- get_all_locs_in_loop (subloop, ref, locs);
+ if (for_all_locs_in_loop (subloop, ref, fn))
+ return true;
+
+ return false;
}
-/* Rewrites all references to REF in LOOP by variable TMP_VAR. */
+/* Rewrites location LOC by TMP_VAR. */
-static void
-rewrite_mem_refs (struct loop *loop, mem_ref_p ref, tree tmp_var)
+struct rewrite_mem_ref_loc
{
- unsigned i;
- mem_ref_loc_p loc;
- VEC (mem_ref_loc_p, heap) *locs = NULL;
+ rewrite_mem_ref_loc (tree tmp_var_) : tmp_var (tmp_var_) {}
+ bool operator () (mem_ref_loc_p loc);
+ tree tmp_var;
+};
- get_all_locs_in_loop (loop, ref, &locs);
- FOR_EACH_VEC_ELT (mem_ref_loc_p, locs, i, loc)
- rewrite_mem_ref_loc (loc, tmp_var);
- VEC_free (mem_ref_loc_p, heap, locs);
+bool
+rewrite_mem_ref_loc::operator () (mem_ref_loc_p loc)
+{
+ *loc->ref = tmp_var;
+ update_stmt (loc->stmt);
+ return false;
}
-/* The name and the length of the currently generated variable
- for lsm. */
-#define MAX_LSM_NAME_LENGTH 40
-static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
-static int lsm_tmp_name_length;
-
-/* Adds S to lsm_tmp_name. */
+/* Rewrites all references to REF in LOOP by variable TMP_VAR. */
static void
-lsm_tmp_name_add (const char *s)
+rewrite_mem_refs (struct loop *loop, mem_ref_p ref, tree tmp_var)
{
- int l = strlen (s) + lsm_tmp_name_length;
- if (l > MAX_LSM_NAME_LENGTH)
- return;
-
- strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
- lsm_tmp_name_length = l;
+ for_all_locs_in_loop (loop, ref, rewrite_mem_ref_loc (tmp_var));
}
-/* Stores the name for temporary variable that replaces REF to
- lsm_tmp_name. */
+/* Stores the first reference location in LOCP. */
-static void
-gen_lsm_tmp_name (tree ref)
+struct first_mem_ref_loc_1
{
- const char *name;
-
- switch (TREE_CODE (ref))
- {
- case MEM_REF:
- case TARGET_MEM_REF:
- gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
- lsm_tmp_name_add ("_");
- break;
-
- case ADDR_EXPR:
- gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
- break;
-
- case BIT_FIELD_REF:
- case VIEW_CONVERT_EXPR:
- case ARRAY_RANGE_REF:
- gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
- break;
-
- case REALPART_EXPR:
- gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
- lsm_tmp_name_add ("_RE");
- break;
-
- case IMAGPART_EXPR:
- gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
- lsm_tmp_name_add ("_IM");
- break;
-
- case COMPONENT_REF:
- gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
- lsm_tmp_name_add ("_");
- name = get_name (TREE_OPERAND (ref, 1));
- if (!name)
- name = "F";
- lsm_tmp_name_add (name);
- break;
-
- case ARRAY_REF:
- gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
- lsm_tmp_name_add ("_I");
- break;
-
- case SSA_NAME:
- case VAR_DECL:
- case PARM_DECL:
- name = get_name (ref);
- if (!name)
- name = "D";
- lsm_tmp_name_add (name);
- break;
-
- case STRING_CST:
- lsm_tmp_name_add ("S");
- break;
-
- case RESULT_DECL:
- lsm_tmp_name_add ("R");
- break;
-
- case INTEGER_CST:
- /* Nothing. */
- break;
+ first_mem_ref_loc_1 (mem_ref_loc_p *locp_) : locp (locp_) {}
+ bool operator () (mem_ref_loc_p loc);
+ mem_ref_loc_p *locp;
+};
- default:
- gcc_unreachable ();
- }
+bool
+first_mem_ref_loc_1::operator () (mem_ref_loc_p loc)
+{
+ *locp = loc;
+ return true;
}
-/* Determines name for temporary variable that replaces REF.
- The name is accumulated into the lsm_tmp_name variable.
- N is added to the name of the temporary. */
+/* Returns the first reference location to REF in LOOP. */
-char *
-get_lsm_tmp_name (tree ref, unsigned n)
+static mem_ref_loc_p
+first_mem_ref_loc (struct loop *loop, mem_ref_p ref)
{
- char ns[2];
-
- lsm_tmp_name_length = 0;
- gen_lsm_tmp_name (ref);
- lsm_tmp_name_add ("_lsm");
- if (n < 10)
- {
- ns[0] = '0' + n;
- ns[1] = 0;
- lsm_tmp_name_add (ns);
- }
- return lsm_tmp_name;
+ mem_ref_loc_p locp = NULL;
+ for_all_locs_in_loop (loop, ref, first_mem_ref_loc_1 (&locp));
+ return locp;
}
struct prev_flag_edges {
EDGE_SUCC (new_bb, 0)->flags &= ~EDGE_FALLTHRU;
}
+/* When REF is set on the location, set flag indicating the store. */
+
+struct sm_set_flag_if_changed
+{
+ sm_set_flag_if_changed (tree flag_) : flag (flag_) {}
+ bool operator () (mem_ref_loc_p loc);
+ tree flag;
+};
+
+bool
+sm_set_flag_if_changed::operator () (mem_ref_loc_p loc)
+{
+ /* Only set the flag for writes. */
+ if (is_gimple_assign (loc->stmt)
+ && gimple_assign_lhs_ptr (loc->stmt) == loc->ref)
+ {
+ gimple_stmt_iterator gsi = gsi_for_stmt (loc->stmt);
+ gimple stmt = gimple_build_assign (flag, boolean_true_node);
+ gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
+ }
+ return false;
+}
+
/* Helper function for execute_sm. On every location where REF is
set, set an appropriate flag indicating the store. */
static tree
execute_sm_if_changed_flag_set (struct loop *loop, mem_ref_p ref)
{
- unsigned i;
- mem_ref_loc_p loc;
tree flag;
- VEC (mem_ref_loc_p, heap) *locs = NULL;
- char *str = get_lsm_tmp_name (ref->mem, ~0);
-
- lsm_tmp_name_add ("_flag");
+ char *str = get_lsm_tmp_name (ref->mem.ref, ~0, "_flag");
flag = create_tmp_reg (boolean_type_node, str);
- get_all_locs_in_loop (loop, ref, &locs);
- FOR_EACH_VEC_ELT (mem_ref_loc_p, locs, i, loc)
- {
- gimple_stmt_iterator gsi;
- gimple stmt;
-
- /* Only set the flag for writes. */
- if (is_gimple_assign (loc->stmt)
- && gimple_assign_lhs_ptr (loc->stmt) == loc->ref)
- {
- gsi = gsi_for_stmt (loc->stmt);
- stmt = gimple_build_assign (flag, boolean_true_node);
- gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
- }
- }
- VEC_free (mem_ref_loc_p, heap, locs);
+ for_all_locs_in_loop (loop, ref, sm_set_flag_if_changed (flag));
return flag;
}
to the reference from the temporary variable are emitted to exits. */
static void
-execute_sm (struct loop *loop, VEC (edge, heap) *exits, mem_ref_p ref)
+execute_sm (struct loop *loop, vec<edge> exits, mem_ref_p ref)
{
tree tmp_var, store_flag;
unsigned i;
gimple load;
struct fmt_data fmt_data;
- edge ex, latch_edge;
+ edge ex;
struct lim_aux_data *lim_data;
bool multi_threaded_model_p = false;
+ gimple_stmt_iterator gsi;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Executing store motion of ");
- print_generic_expr (dump_file, ref->mem, 0);
+ print_generic_expr (dump_file, ref->mem.ref, 0);
fprintf (dump_file, " from loop %d\n", loop->num);
}
- tmp_var = create_tmp_reg (TREE_TYPE (ref->mem),
- get_lsm_tmp_name (ref->mem, ~0));
+ tmp_var = create_tmp_reg (TREE_TYPE (ref->mem.ref),
+ get_lsm_tmp_name (ref->mem.ref, ~0));
fmt_data.loop = loop;
fmt_data.orig_loop = loop;
- for_each_index (&ref->mem, force_move_till, &fmt_data);
+ for_each_index (&ref->mem.ref, force_move_till, &fmt_data);
- if (block_in_transaction (loop_preheader_edge (loop)->src)
+ if (bb_in_transaction (loop_preheader_edge (loop)->src)
|| !PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES))
multi_threaded_model_p = true;
rewrite_mem_refs (loop, ref, tmp_var);
- /* Emit the load code into the latch, so that we are sure it will
- be processed after all dependencies. */
- latch_edge = loop_latch_edge (loop);
+ /* Emit the load code on a random exit edge or into the latch if
+ the loop does not exit, so that we are sure it will be processed
+ by move_computations after all dependencies. */
+ gsi = gsi_for_stmt (first_mem_ref_loc (loop, ref)->stmt);
/* FIXME/TODO: For the multi-threaded variant, we could avoid this
load altogether, since the store is predicated by a flag. We
could, do the load only if it was originally in the loop. */
- load = gimple_build_assign (tmp_var, unshare_expr (ref->mem));
+ load = gimple_build_assign (tmp_var, unshare_expr (ref->mem.ref));
lim_data = init_lim_data (load);
lim_data->max_loop = loop;
lim_data->tgt_loop = loop;
- gsi_insert_on_edge (latch_edge, load);
+ gsi_insert_before (&gsi, load, GSI_SAME_STMT);
if (multi_threaded_model_p)
{
lim_data = init_lim_data (load);
lim_data->max_loop = loop;
lim_data->tgt_loop = loop;
- gsi_insert_on_edge (latch_edge, load);
+ gsi_insert_before (&gsi, load, GSI_SAME_STMT);
}
/* Sink the store to every exit from the loop. */
- FOR_EACH_VEC_ELT (edge, exits, i, ex)
+ FOR_EACH_VEC_ELT (exits, i, ex)
if (!multi_threaded_model_p)
{
gimple store;
- store = gimple_build_assign (unshare_expr (ref->mem), tmp_var);
+ store = gimple_build_assign (unshare_expr (ref->mem.ref), tmp_var);
gsi_insert_on_edge (ex, store);
}
else
- execute_sm_if_changed (ex, ref->mem, tmp_var, store_flag);
+ execute_sm_if_changed (ex, ref->mem.ref, tmp_var, store_flag);
}
/* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
static void
hoist_memory_references (struct loop *loop, bitmap mem_refs,
- VEC (edge, heap) *exits)
+ vec<edge> exits)
{
mem_ref_p ref;
unsigned i;
EXECUTE_IF_SET_IN_BITMAP (mem_refs, 0, i, bi)
{
- ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
+ ref = memory_accesses.refs_list[i];
execute_sm (loop, exits, ref);
}
}
-/* Returns true if REF is always accessed in LOOP. If STORED_P is true
- make sure REF is always stored to in LOOP. */
+struct ref_always_accessed
+{
+ ref_always_accessed (struct loop *loop_, tree base_, bool stored_p_)
+ : loop (loop_), base (base_), stored_p (stored_p_) {}
+ bool operator () (mem_ref_loc_p loc);
+ struct loop *loop;
+ tree base;
+ bool stored_p;
+};
-static bool
-ref_always_accessed_p (struct loop *loop, mem_ref_p ref, bool stored_p)
+bool
+ref_always_accessed::operator () (mem_ref_loc_p loc)
{
- VEC (mem_ref_loc_p, heap) *locs = NULL;
- unsigned i;
- mem_ref_loc_p loc;
- bool ret = false;
struct loop *must_exec;
- tree base;
- base = get_base_address (ref->mem);
- if (INDIRECT_REF_P (base)
- || TREE_CODE (base) == MEM_REF)
- base = TREE_OPERAND (base, 0);
+ if (!get_lim_data (loc->stmt))
+ return false;
- get_all_locs_in_loop (loop, ref, &locs);
- FOR_EACH_VEC_ELT (mem_ref_loc_p, locs, i, loc)
+ /* If we require an always executed store make sure the statement
+ stores to the reference. */
+ if (stored_p)
{
- if (!get_lim_data (loc->stmt))
- continue;
+ tree lhs;
+ if (!gimple_get_lhs (loc->stmt))
+ return false;
+ lhs = get_base_address (gimple_get_lhs (loc->stmt));
+ if (!lhs)
+ return false;
+ if (INDIRECT_REF_P (lhs)
+ || TREE_CODE (lhs) == MEM_REF)
+ lhs = TREE_OPERAND (lhs, 0);
+ if (lhs != base)
+ return false;
+ }
- /* If we require an always executed store make sure the statement
- stores to the reference. */
- if (stored_p)
- {
- tree lhs;
- if (!gimple_get_lhs (loc->stmt))
- continue;
- lhs = get_base_address (gimple_get_lhs (loc->stmt));
- if (!lhs)
- continue;
- if (INDIRECT_REF_P (lhs)
- || TREE_CODE (lhs) == MEM_REF)
- lhs = TREE_OPERAND (lhs, 0);
- if (lhs != base)
- continue;
- }
+ must_exec = get_lim_data (loc->stmt)->always_executed_in;
+ if (!must_exec)
+ return false;
- must_exec = get_lim_data (loc->stmt)->always_executed_in;
- if (!must_exec)
- continue;
+ if (must_exec == loop
+ || flow_loop_nested_p (must_exec, loop))
+ return true;
- if (must_exec == loop
- || flow_loop_nested_p (must_exec, loop))
- {
- ret = true;
- break;
- }
- }
- VEC_free (mem_ref_loc_p, heap, locs);
+ return false;
+}
- return ret;
+/* Returns true if REF is always accessed in LOOP. If STORED_P is true
+ make sure REF is always stored to in LOOP. */
+
+static bool
+ref_always_accessed_p (struct loop *loop, mem_ref_p ref, bool stored_p)
+{
+ tree base = ao_ref_base (&ref->mem);
+ if (TREE_CODE (base) == MEM_REF)
+ base = TREE_OPERAND (base, 0);
+
+ return for_all_locs_in_loop (loop, ref,
+ ref_always_accessed (loop, base, stored_p));
}
/* Returns true if REF1 and REF2 are independent. */
static bool
refs_independent_p (mem_ref_p ref1, mem_ref_p ref2)
{
- if (ref1 == ref2
- || bitmap_bit_p (ref1->indep_ref, ref2->id))
+ if (ref1 == ref2)
return true;
- if (bitmap_bit_p (ref1->dep_ref, ref2->id))
- return false;
- if (!MEM_ANALYZABLE (ref1)
- || !MEM_ANALYZABLE (ref2))
- return false;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Querying dependency of refs %u and %u: ",
ref1->id, ref2->id);
- if (mem_refs_may_alias_p (ref1->mem, ref2->mem,
- &memory_accesses.ttae_cache))
+ if (mem_refs_may_alias_p (ref1, ref2, &memory_accesses.ttae_cache))
{
- bitmap_set_bit (ref1->dep_ref, ref2->id);
- bitmap_set_bit (ref2->dep_ref, ref1->id);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "dependent.\n");
return false;
}
else
{
- bitmap_set_bit (ref1->indep_ref, ref2->id);
- bitmap_set_bit (ref2->indep_ref, ref1->id);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "independent.\n");
return true;
}
}
-/* Records the information whether REF is independent in LOOP (according
- to INDEP). */
+/* Mark REF dependent on stores or loads (according to STORED_P) in LOOP
+ and its super-loops. */
static void
-record_indep_loop (struct loop *loop, mem_ref_p ref, bool indep)
+record_dep_loop (struct loop *loop, mem_ref_p ref, bool stored_p)
{
- if (indep)
- bitmap_set_bit (ref->indep_loop, loop->num);
- else
- bitmap_set_bit (ref->dep_loop, loop->num);
+ /* We can propagate dependent-in-loop bits up the loop
+ hierarchy to all outer loops. */
+ while (loop != current_loops->tree_root
+ && bitmap_set_bit (&ref->dep_loop, LOOP_DEP_BIT (loop->num, stored_p)))
+ loop = loop_outer (loop);
}
/* Returns true if REF is independent on all other memory references in
LOOP. */
static bool
-ref_indep_loop_p_1 (struct loop *loop, mem_ref_p ref)
+ref_indep_loop_p_1 (struct loop *loop, mem_ref_p ref, bool stored_p)
{
bitmap refs_to_check;
unsigned i;
bitmap_iterator bi;
- bool ret = true, stored = bitmap_bit_p (ref->stored, loop->num);
mem_ref_p aref;
- if (stored)
- refs_to_check = VEC_index (bitmap,
- memory_accesses.all_refs_in_loop, loop->num);
+ if (stored_p)
+ refs_to_check = &memory_accesses.refs_in_loop[loop->num];
else
- refs_to_check = VEC_index (bitmap,
- memory_accesses.all_refs_stored_in_loop,
- loop->num);
+ refs_to_check = &memory_accesses.refs_stored_in_loop[loop->num];
+
+ if (bitmap_bit_p (refs_to_check, UNANALYZABLE_MEM_ID))
+ return false;
EXECUTE_IF_SET_IN_BITMAP (refs_to_check, 0, i, bi)
{
- aref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
- if (!MEM_ANALYZABLE (aref)
- || !refs_independent_p (ref, aref))
- {
- ret = false;
- record_indep_loop (loop, aref, false);
- break;
- }
+ aref = memory_accesses.refs_list[i];
+ if (!refs_independent_p (ref, aref))
+ return false;
}
- return ret;
+ return true;
}
/* Returns true if REF is independent on all other memory references in
LOOP. Wrapper over ref_indep_loop_p_1, caching its results. */
static bool
-ref_indep_loop_p (struct loop *loop, mem_ref_p ref)
+ref_indep_loop_p_2 (struct loop *loop, mem_ref_p ref, bool stored_p)
{
- bool ret;
+ stored_p |= bitmap_bit_p (&ref->stored, loop->num);
- if (bitmap_bit_p (ref->indep_loop, loop->num))
+ if (bitmap_bit_p (&ref->indep_loop, LOOP_DEP_BIT (loop->num, stored_p)))
return true;
- if (bitmap_bit_p (ref->dep_loop, loop->num))
+ if (bitmap_bit_p (&ref->dep_loop, LOOP_DEP_BIT (loop->num, stored_p)))
return false;
- ret = ref_indep_loop_p_1 (loop, ref);
+ struct loop *inner = loop->inner;
+ while (inner)
+ {
+ if (!ref_indep_loop_p_2 (inner, ref, stored_p))
+ return false;
+ inner = inner->next;
+ }
+
+ bool indep_p = ref_indep_loop_p_1 (loop, ref, stored_p);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Querying dependencies of ref %u in loop %d: %s\n",
- ref->id, loop->num, ret ? "independent" : "dependent");
+ ref->id, loop->num, indep_p ? "independent" : "dependent");
+
+ /* Record the computed result in the cache. */
+ if (indep_p)
+ {
+ if (bitmap_set_bit (&ref->indep_loop, LOOP_DEP_BIT (loop->num, stored_p))
+ && stored_p)
+ {
+ /* If it's independend against all refs then it's independent
+ against stores, too. */
+ bitmap_set_bit (&ref->indep_loop, LOOP_DEP_BIT (loop->num, false));
+ }
+ }
+ else
+ {
+ record_dep_loop (loop, ref, stored_p);
+ if (!stored_p)
+ {
+ /* If it's dependent against stores it's dependent against
+ all refs, too. */
+ record_dep_loop (loop, ref, true);
+ }
+ }
- record_indep_loop (loop, ref, ret);
+ return indep_p;
+}
- return ret;
+/* Returns true if REF is independent on all other memory references in
+ LOOP. */
+
+static bool
+ref_indep_loop_p (struct loop *loop, mem_ref_p ref)
+{
+ gcc_checking_assert (MEM_ANALYZABLE (ref));
+
+ return ref_indep_loop_p_2 (loop, ref, false);
}
/* Returns true if we can perform store motion of REF from LOOP. */
if (!MEM_ANALYZABLE (ref))
return false;
- /* Unless the reference is stored in the loop, there is nothing to do. */
- if (!bitmap_bit_p (ref->stored, loop->num))
- return false;
-
/* It should be movable. */
- if (!is_gimple_reg_type (TREE_TYPE (ref->mem))
- || TREE_THIS_VOLATILE (ref->mem)
- || !for_each_index (&ref->mem, may_move_till, loop))
+ if (!is_gimple_reg_type (TREE_TYPE (ref->mem.ref))
+ || TREE_THIS_VOLATILE (ref->mem.ref)
+ || !for_each_index (&ref->mem.ref, may_move_till, loop))
return false;
/* If it can throw fail, we do not properly update EH info. */
- if (tree_could_throw_p (ref->mem))
+ if (tree_could_throw_p (ref->mem.ref))
return false;
/* If it can trap, it must be always executed in LOOP.
Readonly memory locations may trap when storing to them, but
tree_could_trap_p is a predicate for rvalues, so check that
explicitly. */
- base = get_base_address (ref->mem);
- if ((tree_could_trap_p (ref->mem)
+ base = get_base_address (ref->mem.ref);
+ if ((tree_could_trap_p (ref->mem.ref)
|| (DECL_P (base) && TREE_READONLY (base)))
&& !ref_always_accessed_p (loop, ref, true))
return false;
static void
find_refs_for_sm (struct loop *loop, bitmap sm_executed, bitmap refs_to_sm)
{
- bitmap refs = VEC_index (bitmap, memory_accesses.all_refs_in_loop,
- loop->num);
+ bitmap refs = &memory_accesses.all_refs_stored_in_loop[loop->num];
unsigned i;
bitmap_iterator bi;
mem_ref_p ref;
EXECUTE_IF_AND_COMPL_IN_BITMAP (refs, sm_executed, 0, i, bi)
{
- ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
+ ref = memory_accesses.refs_list[i];
if (can_sm_ref_p (loop, ref))
bitmap_set_bit (refs_to_sm, i);
}
static bool
loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED,
- VEC (edge, heap) *exits)
+ vec<edge> exits)
{
unsigned i;
edge ex;
- FOR_EACH_VEC_ELT (edge, exits, i, ex)
+ FOR_EACH_VEC_ELT (exits, i, ex)
if (ex->flags & (EDGE_ABNORMAL | EDGE_EH))
return false;
static void
store_motion_loop (struct loop *loop, bitmap sm_executed)
{
- VEC (edge, heap) *exits = get_loop_exit_edges (loop);
+ vec<edge> exits = get_loop_exit_edges (loop);
struct loop *subloop;
- bitmap sm_in_loop = BITMAP_ALLOC (NULL);
+ bitmap sm_in_loop = BITMAP_ALLOC (&lim_bitmap_obstack);
if (loop_suitable_for_sm (loop, exits))
{
find_refs_for_sm (loop, sm_executed, sm_in_loop);
hoist_memory_references (loop, sm_in_loop, exits);
}
- VEC_free (edge, heap, exits);
+ exits.release ();
bitmap_ior_into (sm_executed, sm_in_loop);
for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
store_motion (void)
{
struct loop *loop;
- bitmap sm_executed = BITMAP_ALLOC (NULL);
+ bitmap sm_executed = BITMAP_ALLOC (&lim_bitmap_obstack);
for (loop = current_loops->tree_root->inner; loop != NULL; loop = loop->next)
store_motion_loop (loop, sm_executed);
blocks that contain a nonpure call. */
static void
-fill_always_executed_in (struct loop *loop, sbitmap contains_call)
+fill_always_executed_in_1 (struct loop *loop, sbitmap contains_call)
{
basic_block bb = NULL, *bbs, last = NULL;
unsigned i;
if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
last = bb;
- if (TEST_BIT (contains_call, bb->index))
+ if (bitmap_bit_p (contains_call, bb->index))
break;
FOR_EACH_EDGE (e, ei, bb->succs)
}
for (loop = loop->inner; loop; loop = loop->next)
- fill_always_executed_in (loop, contains_call);
+ fill_always_executed_in_1 (loop, contains_call);
}
-/* Compute the global information needed by the loop invariant motion pass. */
+/* Fills ALWAYS_EXECUTED_IN information for basic blocks, i.e.
+ for each such basic block bb records the outermost loop for that execution
+ of its header implies execution of bb. */
static void
-tree_ssa_lim_initialize (void)
+fill_always_executed_in (void)
{
sbitmap contains_call = sbitmap_alloc (last_basic_block);
- gimple_stmt_iterator bsi;
- struct loop *loop;
basic_block bb;
-
- bitmap_obstack_initialize (&lim_bitmap_obstack);
+ struct loop *loop;
bitmap_clear (contains_call);
FOR_EACH_BB (bb)
{
- for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ gimple_stmt_iterator gsi;
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
- if (nonpure_call_p (gsi_stmt (bsi)))
+ if (nonpure_call_p (gsi_stmt (gsi)))
break;
}
- if (!gsi_end_p (bsi))
- SET_BIT (contains_call, bb->index);
+ if (!gsi_end_p (gsi))
+ bitmap_set_bit (contains_call, bb->index);
}
for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
- fill_always_executed_in (loop, contains_call);
+ fill_always_executed_in_1 (loop, contains_call);
sbitmap_free (contains_call);
+}
+
+
+/* Compute the global information needed by the loop invariant motion pass. */
+
+static void
+tree_ssa_lim_initialize (void)
+{
+ unsigned i;
+ bitmap_obstack_initialize (&lim_bitmap_obstack);
lim_aux_data_map = pointer_map_create ();
if (flag_tm)
compute_transaction_bits ();
alloc_aux_for_edges (0);
+
+ memory_accesses.refs.create (100);
+ memory_accesses.refs_list.create (100);
+ /* Allocate a special, unanalyzable mem-ref with ID zero. */
+ memory_accesses.refs_list.quick_push
+ (mem_ref_alloc (error_mark_node, 0, UNANALYZABLE_MEM_ID));
+
+ memory_accesses.refs_in_loop.create (number_of_loops (cfun));
+ memory_accesses.refs_in_loop.quick_grow (number_of_loops (cfun));
+ memory_accesses.refs_stored_in_loop.create (number_of_loops (cfun));
+ memory_accesses.refs_stored_in_loop.quick_grow (number_of_loops (cfun));
+ memory_accesses.all_refs_stored_in_loop.create (number_of_loops (cfun));
+ memory_accesses.all_refs_stored_in_loop.quick_grow (number_of_loops (cfun));
+
+ for (i = 0; i < number_of_loops (cfun); i++)
+ {
+ bitmap_initialize (&memory_accesses.refs_in_loop[i],
+ &lim_bitmap_obstack);
+ bitmap_initialize (&memory_accesses.refs_stored_in_loop[i],
+ &lim_bitmap_obstack);
+ bitmap_initialize (&memory_accesses.all_refs_stored_in_loop[i],
+ &lim_bitmap_obstack);
+ }
+
+ memory_accesses.ttae_cache = NULL;
}
/* Cleans up after the invariant motion pass. */
bitmap_obstack_release (&lim_bitmap_obstack);
pointer_map_destroy (lim_aux_data_map);
- htab_delete (memory_accesses.refs);
+ memory_accesses.refs.dispose ();
- FOR_EACH_VEC_ELT (mem_ref_p, memory_accesses.refs_list, i, ref)
+ FOR_EACH_VEC_ELT (memory_accesses.refs_list, i, ref)
memref_free (ref);
- VEC_free (mem_ref_p, heap, memory_accesses.refs_list);
+ memory_accesses.refs_list.release ();
- VEC_free (bitmap, heap, memory_accesses.refs_in_loop);
- VEC_free (bitmap, heap, memory_accesses.all_refs_in_loop);
- VEC_free (bitmap, heap, memory_accesses.all_refs_stored_in_loop);
+ memory_accesses.refs_in_loop.release ();
+ memory_accesses.refs_stored_in_loop.release ();
+ memory_accesses.all_refs_stored_in_loop.release ();
if (memory_accesses.ttae_cache)
free_affine_expand_cache (&memory_accesses.ttae_cache);
/* Gathers information about memory accesses in the loops. */
analyze_memory_references ();
+ /* Fills ALWAYS_EXECUTED_IN information for basic blocks. */
+ fill_always_executed_in ();
+
/* For each statement determine the outermost loop in that it is
invariant and cost for computing the invariant. */
- determine_invariantness ();
+ invariantness_dom_walker (CDI_DOMINATORS)
+ .walk (cfun->cfg->x_entry_block_ptr);
/* Execute store motion. Force the necessary invariants to be moved
out of the loops as well. */
return todo;
}
+
+/* Loop invariant motion pass. */
+
+static unsigned int
+tree_ssa_loop_im (void)
+{
+ if (number_of_loops (cfun) <= 1)
+ return 0;
+
+ return tree_ssa_lim ();
+}
+
+static bool
+gate_tree_ssa_loop_im (void)
+{
+ return flag_tree_loop_im != 0;
+}
+
+namespace {
+
+const pass_data pass_data_lim =
+{
+ GIMPLE_PASS, /* type */
+ "lim", /* name */
+ OPTGROUP_LOOP, /* optinfo_flags */
+ true, /* has_gate */
+ true, /* has_execute */
+ TV_LIM, /* tv_id */
+ PROP_cfg, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
+};
+
+class pass_lim : public gimple_opt_pass
+{
+public:
+ pass_lim (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_lim, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ opt_pass * clone () { return new pass_lim (m_ctxt); }
+ bool gate () { return gate_tree_ssa_loop_im (); }
+ unsigned int execute () { return tree_ssa_loop_im (); }
+
+}; // class pass_lim
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_lim (gcc::context *ctxt)
+{
+ return new pass_lim (ctxt);
+}
+
+
projects / thirdparty / gcc.git / blobdiff