+ ir_opcode opcode = get_irn_opcode(node);
+ ir_node *pred, *blk, *pred_blk;
+ ldst_info_t *ldst_info;
+ walk_env_t *wenv = env;
+
+ if (opcode == iro_Proj) {
+ pred = get_Proj_pred(node);
+ opcode = get_irn_opcode(pred);
+
+ if (opcode == iro_Load || opcode == iro_Store || opcode == iro_Call) {
+ ldst_info = get_ldst_info(pred, &wenv->obst);
+
+ wenv->changes |= update_projs(ldst_info, node);
+
+ /*
+ * Place the Proj's to the same block as the
+ * predecessor Load. This is always ok and prevents
+ * "non-SSA" form after optimizations if the Proj
+ * is in a wrong block.
+ */
+ blk = get_nodes_block(node);
+ pred_blk = get_nodes_block(pred);
+ if (blk != pred_blk) {
+ wenv->changes |= DF_CHANGED;
+ set_nodes_block(node, pred_blk);
+ }
+ }
+ } else if (opcode == iro_Block) {
+ int i;
+
+ for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
+ ir_node *pred_block, *proj;
+ block_info_t *bl_info;
+ int is_exc = 0;
+
+ pred = proj = get_Block_cfgpred(node, i);
+
+ if (is_Proj(proj)) {
+ pred = get_Proj_pred(proj);
+ is_exc = get_Proj_proj(proj) == pn_Generic_X_except;
+ }
+
+ /* ignore Bad predecessors, they will be removed later */
+ if (is_Bad(pred))
+ continue;
+
+ pred_block = get_nodes_block(pred);
+ bl_info = get_block_info(pred_block, &wenv->obst);
+
+ if (is_fragile_op(pred) && is_exc)
+ bl_info->flags |= BLOCK_HAS_EXC;
+ else if (is_irn_forking(pred))
+ bl_info->flags |= BLOCK_HAS_COND;
+
+ opcode = get_irn_opcode(pred);
+ if (is_exc && (opcode == iro_Load || opcode == iro_Store || opcode == iro_Call)) {
+ ldst_info = get_ldst_info(pred, &wenv->obst);
+
+ wenv->changes |= update_exc(ldst_info, node, i);
+ }
+ }
+ }
+} /* collect_nodes */
+
+/**
+ * Returns an entity if the address ptr points to a constant one.
+ *
+ * @param ptr the address
+ *
+ * @return an entity or NULL
+ */
+static ir_entity *find_constant_entity(ir_node *ptr)
+{
+ for (;;) {
+ if (is_SymConst(ptr) && get_SymConst_kind(ptr) == symconst_addr_ent) {
+ ir_entity *ent = get_SymConst_entity(ptr);
+ if (variability_constant == get_entity_variability(ent))
+ return ent;
+ return NULL;
+ } else if (is_Sel(ptr)) {
+ ir_entity *ent = get_Sel_entity(ptr);
+ ir_type *tp = get_entity_owner(ent);
+
+ /* Do not fiddle with polymorphism. */
+ if (is_Class_type(get_entity_owner(ent)) &&
+ ((get_entity_n_overwrites(ent) != 0) ||
+ (get_entity_n_overwrittenby(ent) != 0) ) )
+ return NULL;
+
+ if (is_Array_type(tp)) {
+ /* check bounds */
+ int i, n;
+
+ for (i = 0, n = get_Sel_n_indexs(ptr); i < n; ++i) {
+ ir_node *bound;
+ tarval *tlower, *tupper;
+ ir_node *index = get_Sel_index(ptr, i);
+ tarval *tv = computed_value(index);
+
+ /* check if the index is constant */
+ if (tv == tarval_bad)
+ return NULL;
+
+ bound = get_array_lower_bound(tp, i);
+ tlower = computed_value(bound);
+ bound = get_array_upper_bound(tp, i);
+ tupper = computed_value(bound);
+
+ if (tlower == tarval_bad || tupper == tarval_bad)
+ return NULL;
+
+ if (tarval_cmp(tv, tlower) & pn_Cmp_Lt)
+ return NULL;
+ if (tarval_cmp(tupper, tv) & pn_Cmp_Lt)
+ return NULL;
+
+ /* ok, bounds check finished */
+ }
+ }
+
+ if (variability_constant == get_entity_variability(ent))
+ return ent;
+
+ /* try next */
+ ptr = get_Sel_ptr(ptr);
+ } else if (is_Add(ptr)) {
+ ir_node *l = get_Add_left(ptr);
+ ir_node *r = get_Add_right(ptr);
+
+ if (get_irn_mode(l) == get_irn_mode(ptr) && is_Const(r))
+ ptr = l;
+ else if (get_irn_mode(r) == get_irn_mode(ptr) && is_Const(l))
+ ptr = r;
+ else
+ return NULL;
+
+ /* for now, we support only one addition, reassoc should fold all others */
+ if (! is_SymConst(ptr) && !is_Sel(ptr))
+ return NULL;
+ } else if (is_Sub(ptr)) {
+ ir_node *l = get_Sub_left(ptr);
+ ir_node *r = get_Sub_right(ptr);
+
+ if (get_irn_mode(l) == get_irn_mode(ptr) && is_Const(r))
+ ptr = l;
+ else
+ return NULL;
+ /* for now, we support only one substraction, reassoc should fold all others */
+ if (! is_SymConst(ptr) && !is_Sel(ptr))
+ return NULL;
+ } else
+ return NULL;
+ }
+} /* find_constant_entity */
+
+/**
+ * Return the Selection index of a Sel node from dimension n
+ */
+static long get_Sel_array_index_long(ir_node *n, int dim) {
+ ir_node *index = get_Sel_index(n, dim);
+ assert(is_Const(index));
+ return get_tarval_long(get_Const_tarval(index));
+} /* get_Sel_array_index_long */
+
+/**
+ * Returns the accessed component graph path for an
+ * node computing an address.
+ *
+ * @param ptr the node computing the address
+ * @param depth current depth in steps upward from the root
+ * of the address
+ */
+static compound_graph_path *rec_get_accessed_path(ir_node *ptr, int depth) {
+ compound_graph_path *res = NULL;
+ ir_entity *root, *field, *ent;
+ int path_len, pos, idx;
+ tarval *tv;
+ ir_type *tp;
+
+ if (is_SymConst(ptr)) {
+ /* a SymConst. If the depth is 0, this is an access to a global
+ * entity and we don't need a component path, else we know
+ * at least it's length.
+ */
+ assert(get_SymConst_kind(ptr) == symconst_addr_ent);
+ root = get_SymConst_entity(ptr);
+ res = (depth == 0) ? NULL : new_compound_graph_path(get_entity_type(root), depth);
+ } else if (is_Sel(ptr)) {
+ /* it's a Sel, go up until we find the root */
+ res = rec_get_accessed_path(get_Sel_ptr(ptr), depth+1);
+ if (res == NULL)
+ return NULL;
+
+ /* fill up the step in the path at the current position */
+ field = get_Sel_entity(ptr);
+ path_len = get_compound_graph_path_length(res);
+ pos = path_len - depth - 1;
+ set_compound_graph_path_node(res, pos, field);
+
+ if (is_Array_type(get_entity_owner(field))) {
+ assert(get_Sel_n_indexs(ptr) == 1 && "multi dim arrays not implemented");
+ set_compound_graph_path_array_index(res, pos, get_Sel_array_index_long(ptr, 0));
+ }
+ } else if (is_Add(ptr)) {
+ ir_node *l = get_Add_left(ptr);
+ ir_node *r = get_Add_right(ptr);
+ ir_mode *mode = get_irn_mode(ptr);
+ tarval *tmp;
+
+ if (is_Const(r) && get_irn_mode(l) == mode) {
+ ptr = l;
+ tv = get_Const_tarval(r);
+ } else {
+ ptr = r;
+ tv = get_Const_tarval(l);
+ }
+ptr_arith:
+ mode = get_tarval_mode(tv);
+ tmp = tv;
+
+ /* ptr must be a Sel or a SymConst, this was checked in find_constant_entity() */
+ if (is_Sel(ptr)) {
+ field = get_Sel_entity(ptr);
+ } else {
+ field = get_SymConst_entity(ptr);
+ }
+ idx = 0;
+ for (ent = field;;) {
+ unsigned size;
+ tarval *sz, *tv_index, *tlower, *tupper;
+ ir_node *bound;
+
+ tp = get_entity_type(ent);
+ if (! is_Array_type(tp))
+ break;
+ ent = get_array_element_entity(tp);
+ size = get_type_size_bytes(get_entity_type(ent));
+ sz = new_tarval_from_long(size, mode);
+
+ tv_index = tarval_div(tmp, sz);
+ tmp = tarval_mod(tmp, sz);
+
+ if (tv_index == tarval_bad || tmp == tarval_bad)
+ return NULL;
+
+ assert(get_array_n_dimensions(tp) == 1 && "multiarrays not implemented");
+ bound = get_array_lower_bound(tp, 0);
+ tlower = computed_value(bound);
+ bound = get_array_upper_bound(tp, 0);
+ tupper = computed_value(bound);
+
+ if (tlower == tarval_bad || tupper == tarval_bad)
+ return NULL;
+
+ if (tarval_cmp(tv_index, tlower) & pn_Cmp_Lt)
+ return NULL;
+ if (tarval_cmp(tupper, tv_index) & pn_Cmp_Lt)
+ return NULL;
+
+ /* ok, bounds check finished */
+ ++idx;
+ }
+ if (! tarval_is_null(tmp)) {
+ /* access to some struct/union member */
+ return NULL;
+ }
+
+ /* should be at least ONE array */
+ if (idx == 0)
+ return NULL;
+
+ res = rec_get_accessed_path(ptr, depth + idx);
+ if (res == NULL)
+ return NULL;
+
+ path_len = get_compound_graph_path_length(res);
+ pos = path_len - depth - idx;
+
+ for (ent = field;;) {
+ unsigned size;
+ tarval *sz, *tv_index;
+ long index;
+
+ tp = get_entity_type(ent);
+ if (! is_Array_type(tp))
+ break;
+ ent = get_array_element_entity(tp);
+ set_compound_graph_path_node(res, pos, ent);
+
+ size = get_type_size_bytes(get_entity_type(ent));
+ sz = new_tarval_from_long(size, mode);
+
+ tv_index = tarval_div(tv, sz);
+ tv = tarval_mod(tv, sz);
+
+ /* worked above, should work again */
+ assert(tv_index != tarval_bad && tv != tarval_bad);
+
+ /* bounds already checked above */
+ index = get_tarval_long(tv_index);
+ set_compound_graph_path_array_index(res, pos, index);
+ ++pos;
+ }
+ } else if (is_Sub(ptr)) {
+ ir_node *l = get_Sub_left(ptr);
+ ir_node *r = get_Sub_right(ptr);
+
+ ptr = l;
+ tv = get_Const_tarval(r);
+ tv = tarval_neg(tv);
+ goto ptr_arith;
+ }
+ return res;
+} /* rec_get_accessed_path */
+
+/**
+ * Returns an access path or NULL. The access path is only
+ * valid, if the graph is in phase_high and _no_ address computation is used.
+ */
+static compound_graph_path *get_accessed_path(ir_node *ptr) {
+ compound_graph_path *gr = rec_get_accessed_path(ptr, 0);
+ return gr;
+} /* get_accessed_path */
+
+typedef struct path_entry {
+ ir_entity *ent;
+ struct path_entry *next;
+ long index;
+} path_entry;
+
+static ir_node *rec_find_compound_ent_value(ir_node *ptr, path_entry *next) {
+ path_entry entry, *p;
+ ir_entity *ent, *field;
+ ir_initializer_t *initializer;
+ tarval *tv;
+ ir_type *tp;
+ unsigned n;
+
+ entry.next = next;
+ if (is_SymConst(ptr)) {
+ /* found the root */
+ ent = get_SymConst_entity(ptr);
+ initializer = get_entity_initializer(ent);
+ for (p = next; p != NULL;) {
+ if (initializer->kind != IR_INITIALIZER_COMPOUND)
+ return NULL;
+ n = get_initializer_compound_n_entries(initializer);
+ tp = get_entity_type(ent);
+
+ if (is_Array_type(tp)) {
+ ent = get_array_element_entity(tp);
+ if (ent != p->ent) {
+ /* a missing [0] */
+ if (0 >= n)
+ return NULL;
+ initializer = get_initializer_compound_value(initializer, 0);
+ continue;
+ }
+ }
+ if (p->index >= (int) n)
+ return NULL;
+ initializer = get_initializer_compound_value(initializer, p->index);
+
+ ent = p->ent;
+ p = p->next;
+ }
+ tp = get_entity_type(ent);
+ while (is_Array_type(tp)) {
+ ent = get_array_element_entity(tp);
+ tp = get_entity_type(ent);
+ /* a missing [0] */
+ n = get_initializer_compound_n_entries(initializer);
+ if (0 >= n)
+ return NULL;
+ initializer = get_initializer_compound_value(initializer, 0);
+ }
+
+ switch (initializer->kind) {
+ case IR_INITIALIZER_CONST:
+ return get_initializer_const_value(initializer);
+ case IR_INITIALIZER_TARVAL:
+ case IR_INITIALIZER_NULL:
+ default:
+ return NULL;
+ }
+ } else if (is_Sel(ptr)) {
+ entry.ent = field = get_Sel_entity(ptr);
+ tp = get_entity_owner(field);
+ if (is_Array_type(tp)) {
+ assert(get_Sel_n_indexs(ptr) == 1 && "multi dim arrays not implemented");
+ entry.index = get_Sel_array_index_long(ptr, 0) - get_array_lower_bound_int(tp, 0);
+ } else {
+ int i, n_members = get_compound_n_members(tp);
+ for (i = 0; i < n_members; ++i) {
+ if (get_compound_member(tp, i) == field)
+ break;
+ }
+ if (i >= n_members) {
+ /* not found: should NOT happen */
+ return NULL;
+ }
+ entry.index = i;
+ }
+ return rec_find_compound_ent_value(get_Sel_ptr(ptr), &entry);
+ } else if (is_Add(ptr)) {
+ ir_node *l = get_Add_left(ptr);
+ ir_node *r = get_Add_right(ptr);
+ ir_mode *mode;
+ unsigned pos;
+
+ if (is_Const(r)) {
+ ptr = l;
+ tv = get_Const_tarval(r);
+ } else {
+ ptr = r;
+ tv = get_Const_tarval(l);
+ }
+ptr_arith:
+ mode = get_tarval_mode(tv);
+
+ /* ptr must be a Sel or a SymConst, this was checked in find_constant_entity() */
+ if (is_Sel(ptr)) {
+ field = get_Sel_entity(ptr);
+ } else {
+ field = get_SymConst_entity(ptr);
+ }
+
+ /* count needed entries */
+ pos = 0;
+ for (ent = field;;) {
+ tp = get_entity_type(ent);
+ if (! is_Array_type(tp))
+ break;
+ ent = get_array_element_entity(tp);
+ ++pos;
+ }
+ /* should be at least ONE entry */
+ if (pos == 0)
+ return NULL;
+
+ /* allocate the right number of entries */
+ NEW_ARR_A(path_entry, p, pos);