+static void do_load_store_optimize(ir_node *n, void *env) {
+ walk_env_t *wenv = env;
+
+ switch (get_irn_opcode(n)) {
+
+ case iro_Load:
+ wenv->changes |= optimize_load(n);
+ break;
+
+ case iro_Store:
+ wenv->changes |= optimize_store(n);
+ break;
+
+ case iro_Phi:
+ wenv->changes |= optimize_phi(n, wenv);
+ break;
+
+ default:
+ ;
+ }
+} /* do_load_store_optimize */
+
+/** A scc. */
+typedef struct scc {
+ ir_node *head; /**< the head of the list */
+} scc;
+
+/** A node entry. */
+typedef struct node_entry {
+ unsigned DFSnum; /**< the DFS number of this node */
+ unsigned low; /**< the low number of this node */
+ ir_node *header; /**< the header of this node */
+ int in_stack; /**< flag, set if the node is on the stack */
+ ir_node *next; /**< link to the next node the the same scc */
+ scc *pscc; /**< the scc of this node */
+ unsigned POnum; /**< the post order number for blocks */
+} node_entry;
+
+/** A loop entry. */
+typedef struct loop_env {
+ ir_phase ph; /**< the phase object */
+ ir_node **stack; /**< the node stack */
+ int tos; /**< tos index */
+ unsigned nextDFSnum; /**< the current DFS number */
+ unsigned POnum; /**< current post order number */
+
+ unsigned changes; /**< a bitmask of graph changes */
+} loop_env;
+
+/**
+* Gets the node_entry of a node
+*/
+static node_entry *get_irn_ne(ir_node *irn, loop_env *env) {
+ ir_phase *ph = &env->ph;
+ node_entry *e = phase_get_irn_data(&env->ph, irn);
+
+ if (! e) {
+ e = phase_alloc(ph, sizeof(*e));
+ memset(e, 0, sizeof(*e));
+ phase_set_irn_data(ph, irn, e);
+ }
+ return e;
+} /* get_irn_ne */
+
+/**
+ * Push a node onto the stack.
+ *
+ * @param env the loop environment
+ * @param n the node to push
+ */
+static void push(loop_env *env, ir_node *n) {
+ node_entry *e;
+
+ if (env->tos == ARR_LEN(env->stack)) {
+ int nlen = ARR_LEN(env->stack) * 2;
+ ARR_RESIZE(ir_node *, env->stack, nlen);
+ }
+ env->stack[env->tos++] = n;
+ e = get_irn_ne(n, env);
+ e->in_stack = 1;
+} /* push */
+
+/**
+ * pop a node from the stack
+ *
+ * @param env the loop environment
+ *
+ * @return The topmost node
+ */
+static ir_node *pop(loop_env *env) {
+ ir_node *n = env->stack[--env->tos];
+ node_entry *e = get_irn_ne(n, env);
+
+ e->in_stack = 0;
+ return n;
+} /* pop */
+
+/**
+ * Check if irn is a region constant.
+ * The block or irn must strictly dominate the header block.
+ *
+ * @param irn the node to check
+ * @param header_block the header block of the induction variable
+ */
+static int is_rc(ir_node *irn, ir_node *header_block) {
+ ir_node *block = get_nodes_block(irn);
+
+ return (block != header_block) && block_dominates(block, header_block);
+} /* is_rc */
+
+typedef struct phi_entry phi_entry;
+struct phi_entry {
+ ir_node *phi; /**< A phi with a region const memory. */
+ int pos; /**< The position of the region const memory */
+ ir_node *load; /**< the newly created load for this phi */
+ phi_entry *next;
+};
+
+/**
+ * Move loops out of loops if possible.
+ *
+ * @param pscc the loop described by an SCC
+ * @param env the loop environment
+ */
+static void move_loads_out_of_loops(scc *pscc, loop_env *env) {
+ ir_node *phi, *load, *next, *other, *next_other;
+ ir_entity *ent;
+ int j;
+ phi_entry *phi_list = NULL;
+
+ /* collect all outer memories */
+ for (phi = pscc->head; phi != NULL; phi = next) {
+ node_entry *ne = get_irn_ne(phi, env);
+ next = ne->next;
+
+ /* check all memory Phi's */
+ if (! is_Phi(phi))
+ continue;
+
+ assert(get_irn_mode(phi) == mode_M && "DFS geturn non-memory Phi");
+
+ for (j = get_irn_arity(phi) - 1; j >= 0; --j) {
+ ir_node *pred = get_irn_n(phi, j);
+ node_entry *pe = get_irn_ne(pred, env);
+
+ if (pe->pscc != ne->pscc) {
+ /* not in the same SCC, is region const */
+ phi_entry *pe = phase_alloc(&env->ph, sizeof(*pe));
+
+ pe->phi = phi;
+ pe->pos = j;
+ pe->next = phi_list;
+ phi_list = pe;
+ }
+ }
+ }
+ /* no Phis no fun */
+ assert(phi_list != NULL && "DFS found a loop without Phi");
+
+ for (load = pscc->head; load; load = next) {
+ ir_mode *load_mode;
+ node_entry *ne = get_irn_ne(load, env);
+ next = ne->next;
+
+ if (is_Load(load)) {
+ ldst_info_t *info = get_irn_link(load);
+ ir_node *ptr = get_Load_ptr(load);
+
+ /* for now, we cannot handle Loads with exceptions */
+ if (info->projs[pn_Load_res] == NULL || info->projs[pn_Load_X_regular] != NULL || info->projs[pn_Load_X_except] != NULL)
+ continue;
+
+ /* for now, we can only handle Load(Global) */
+ if (! is_Global(ptr))
+ continue;
+ ent = get_Global_entity(ptr);
+ load_mode = get_Load_mode(load);
+ for (other = pscc->head; other != NULL; other = next_other) {
+ node_entry *ne = get_irn_ne(other, env);
+ next_other = ne->next;
+
+ if (is_Store(other)) {
+ ir_alias_relation rel = get_alias_relation(
+ current_ir_graph,
+ get_Store_ptr(other),
+ get_irn_mode(get_Store_value(other)),
+ ptr, load_mode);
+ /* if the might be an alias, we cannot pass this Store */
+ if (rel != ir_no_alias)
+ break;
+ }
+ /* only pure Calls are allowed here, so ignore them */
+ }
+ if (other == NULL) {
+ ldst_info_t *ninfo;
+ phi_entry *pe;
+ dbg_info *db;
+
+ /* for now, we cannot handle more than one input */
+ if (phi_list->next != NULL)
+ return;
+
+ /* yep, no aliasing Store found, Load can be moved */
+ DB((dbg, LEVEL_1, " Found a Load that could be moved: %+F\n", load));
+
+ db = get_irn_dbg_info(load);
+ for (pe = phi_list; pe != NULL; pe = pe->next) {
+ int pos = pe->pos;
+ ir_node *phi = pe->phi;
+ ir_node *blk = get_nodes_block(phi);
+ ir_node *pred = get_Block_cfgpred_block(blk, pos);
+ ir_node *irn, *mem;
+
+ pe->load = irn = new_rd_Load(db, current_ir_graph, pred, get_Phi_pred(phi, pos), ptr, load_mode);
+ ninfo = get_ldst_info(irn, phase_obst(&env->ph));
+
+ ninfo->projs[pn_Load_M] = mem = new_r_Proj(current_ir_graph, pred, irn, mode_M, pn_Load_M);
+ set_Phi_pred(phi, pos, mem);
+
+ ninfo->projs[pn_Load_res] = new_r_Proj(current_ir_graph, pred, irn, load_mode, pn_Load_res);
+
+ DB((dbg, LEVEL_1, " Created %+F in %+F\n", irn, pred));
+ }
+
+ /* now kill the old Load */
+ exchange(info->projs[pn_Load_M], get_Load_mem(load));
+ exchange(info->projs[pn_Load_res], ninfo->projs[pn_Load_res]);
+
+ env->changes |= DF_CHANGED;
+ }
+ }
+ }
+} /* move_loads_out_of_loops */
+
+/**
+ * Process a loop SCC.
+ *
+ * @param pscc the SCC
+ * @param env the loop environment
+ */
+static void process_loop(scc *pscc, loop_env *env) {
+ ir_node *irn, *next, *header = NULL;
+ node_entry *b, *h = NULL;
+ int j, only_phi, num_outside, process = 0;
+ ir_node *out_rc;
+
+ /* find the header block for this scc */
+ for (irn = pscc->head; irn; irn = next) {
+ node_entry *e = get_irn_ne(irn, env);
+ ir_node *block = get_nodes_block(irn);
+
+ next = e->next;
+ b = get_irn_ne(block, env);
+
+ if (header) {
+ if (h->POnum < b->POnum) {
+ header = block;
+ h = b;
+ }
+ }
+ else {
+ header = block;
+ h = b;
+ }
+ }
+
+ /* check if this scc contains only Phi, Loads or Stores nodes */
+ only_phi = 1;
+ num_outside = 0;
+ out_rc = NULL;
+ for (irn = pscc->head; irn; irn = next) {
+ node_entry *e = get_irn_ne(irn, env);
+
+ next = e->next;
+ switch (get_irn_opcode(irn)) {
+ case iro_Call:
+ if (is_Call_pure(irn)) {
+ /* pure calls can be treated like loads */
+ only_phi = 0;
+ break;
+ }
+ /* non-pure calls must be handle like may-alias Stores */
+ goto fail;
+ case iro_CopyB:
+ /* cannot handle CopyB yet */
+ goto fail;
+ case iro_Load:
+ process = 1;
+ if (get_Load_volatility(irn) == volatility_is_volatile) {
+ /* cannot handle loops with volatile Loads */
+ goto fail;
+ }
+ only_phi = 0;
+ break;
+ case iro_Store:
+ if (get_Store_volatility(irn) == volatility_is_volatile) {
+ /* cannot handle loops with volatile Stores */
+ goto fail;
+ }
+ only_phi = 0;
+ break;
+ default:
+ only_phi = 0;
+ break;
+ case iro_Phi:
+ for (j = get_irn_arity(irn) - 1; j >= 0; --j) {
+ ir_node *pred = get_irn_n(irn, j);
+ node_entry *pe = get_irn_ne(pred, env);
+
+ if (pe->pscc != e->pscc) {
+ /* not in the same SCC, must be a region const */
+ if (! is_rc(pred, header)) {
+ /* not a memory loop */
+ goto fail;
+ }
+ if (! out_rc) {
+ out_rc = pred;
+ ++num_outside;
+ } else if (out_rc != pred) {
+ ++num_outside;
+ }
+ }
+ }
+ break;
+ }
+ }
+ if (! process)
+ goto fail;
+
+ /* found a memory loop */
+ DB((dbg, LEVEL_2, " Found a memory loop:\n "));
+ if (only_phi && num_outside == 1) {
+ /* a phi cycle with only one real predecessor can be collapsed */
+ DB((dbg, LEVEL_2, " Found an USELESS Phi cycle:\n "));
+
+ for (irn = pscc->head; irn; irn = next) {
+ node_entry *e = get_irn_ne(irn, env);
+ next = e->next;
+ e->header = NULL;
+ exchange(irn, out_rc);
+ }
+ env->changes |= DF_CHANGED;
+ return;
+ }
+
+ /* set the header for every node in this scc */
+ for (irn = pscc->head; irn; irn = next) {
+ node_entry *e = get_irn_ne(irn, env);
+ e->header = header;
+ next = e->next;
+ DB((dbg, LEVEL_2, " %+F,", irn));
+ }
+ DB((dbg, LEVEL_2, "\n"));
+
+ move_loads_out_of_loops(pscc, env);
+
+fail:
+ ;
+} /* process_loop */
+
+/**
+ * Process a SCC.
+ *
+ * @param pscc the SCC
+ * @param env the loop environment
+ */
+static void process_scc(scc *pscc, loop_env *env) {
+ ir_node *head = pscc->head;
+ node_entry *e = get_irn_ne(head, env);
+
+#ifdef DEBUG_libfirm
+ {
+ ir_node *irn, *next;
+
+ DB((dbg, LEVEL_4, " SCC at %p:\n ", pscc));
+ for (irn = pscc->head; irn; irn = next) {
+ node_entry *e = get_irn_ne(irn, env);
+
+ next = e->next;
+
+ DB((dbg, LEVEL_4, " %+F,", irn));
+ }
+ DB((dbg, LEVEL_4, "\n"));
+ }
+#endif
+
+ if (e->next != NULL) {
+ /* this SCC has more than one member */
+ process_loop(pscc, env);
+ }
+} /* process_scc */
+
+/**
+ * Do Tarjan's SCC algorithm and drive load/store optimization.
+ *
+ * @param irn start at this node
+ * @param env the loop environment
+ */
+static void dfs(ir_node *irn, loop_env *env)