+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)