+ if (get_irn_link(node) == PRED_SEARCH)
+ set_irn_link(node, NULL);
+}
+
+/**
+ * Create a link for blocks, that have Phi, Load or Store nodes for scalar_replacement.
+ *
+ * @param node A Phi, Load or Store node, that block muss get a link.
+ * @param env Contains information about scalars number and mode.
+ * @parm repairs A set, that contains all blocks, that have a link, and all Phis, that
+ * have copies to repair.
+ */
+static void block_link(ir_node *node, env_t *env, set *repairs)
+{
+ repairs_t key, *value;
+ ir_node *nods_block ;
+ int i;
+ nods_block = get_nodes_block(node);
+ /* If the block of the node have no link. */
+ if (get_irn_link(nods_block) == NULL) {
+ DDMN(nods_block);
+ key.irn = nods_block;
+ value = set_insert(repairs, &key, sizeof(key), HASH_PTR(key.irn));
+ value->link = obstack_alloc(&env->obst, sizeof(ir_node *) * env->nvals);
+ /* The block of the node be inserted in the set repairs, because it have yet a link.
+ The link is a array with size equal to number of scalars.*/
+ for (i = 0; i < env->nvals; i++)
+ /* First all links member be set to NULL. */
+ value->link[i] = NULL;
+ set_irn_link(nods_block, value->link);
+ }
+}
+
+/**
+ * Handle Phis, that get the memory edge of Loads or Stors, that were been scalar replaced or
+ * will be scalar replaced.
+ *
+ * @param phi A Phi node, that muss have mode_M.
+ * @param env Contains information about scalars number and mode.
+ * @parm repairs A set that contains all blocks having a link and all Phis that
+ * have copies to repair.
+ */
+static void phi_handling(ir_node *phi, env_t *env, set *repairs)
+{
+ ir_node *phi_block, **link;
+ repairs_t key, *value;
+ int rem;
+ int p = 0, i, phi_preds;
+ ir_node **in;
+
+ key.irn = phi;
+ value = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
+
+ /* Test if the phi have been handled. */
+ if (value != NULL)
+ return;
+
+ rem = get_optimize();
+
+ phi_block = get_nodes_block(phi);
+ phi_preds = get_Phi_n_preds(phi);
+
+ /* Test if the Phi have predecessors, that were been or will be scalar replaced. */
+ for (i = 0; i < phi_preds; i++){
+ ir_node *pred = get_Phi_pred(phi, i);
+ ir_node *pred_block = get_nodes_block(pred);
+
+ key.irn = pred_block;
+ value = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
+
+ if (value != NULL)
+ p++;
+ }
+ /* Phis from the loop head muss be handled.*/
+ if (get_irn_link(phi) == LOOP_HEAD_PHI)
+ p++;
+
+ /* If the Phi node have such predecessor(s), be inserted in the repairs set, else is nothing to do
+ and exit "phi_handling".*/
+ if (p) {
+ key.irn = phi;
+ value = set_insert(repairs, &key, sizeof(key), HASH_PTR(key.irn));
+ }
+ else
+ return;
+
+ //DDMN(phi);
+ if (get_irn_link(phi_block) == NULL)
+ block_link(phi, env, repairs);
+
+ link = get_irn_link(phi_block);
+
+ key.irn = phi_block;
+ value = set_find(repairs, &key, sizeof(key), HASH_PTR(phi_block));
+
+ in = alloca(phi_preds * sizeof(*in));
+
+ /* We will build some Phi nodes. Beware, as they have all Unknown predecessors, CSE
+ * would combine them into one. To prevent this, we must deactivate Optimizations here
+ */
+ for (p = 0; p < env->nvals; ++p) {
+
+ for (i = 0; i < phi_preds; ++i)
+ in[i] = new_Unknown(env->modes[p]);
+
+ set_optimize(0);
+ value->link[p] = new_r_Phi(current_ir_graph, get_nodes_block(phi), phi_preds, in, env->modes[p]);
+ set_optimize(rem);
+ }
+}
+
+/**
+ * Handle Loads, that were been scalar replaced or
+ * will be scalar replaced.
+ *
+ * @param load A load node.
+ * @param env Contains information about scalars number and mode.
+ * @parm repairs A set, that contains all blocks, that have a link, and all Phis, that
+ * have copies to repair.
+ */
+static void load_handling(ir_node *load, env_t *env, set *repairs)
+{
+ repairs_t key, *value;
+ ir_node *load_ptr, *load_mem, *nods_block;
+ unsigned i;
+
+ nods_block = get_nodes_block(load);
+ load_ptr = get_Load_ptr(load);
+ load_mem = get_Load_mem(load);
+ // DDMN(load);
+ /* The pointer predecessor of Load muss be a Sel node. */
+ if (get_irn_op(load_ptr) == op_Sel) {
+ /* If the link field of sel's entity is set to "ADDRESS_TAKEN", that means this value
+ can't be scalar replaced. It is nothing to do and load_handling() must be exited. */
+ if (get_entity_link(get_Sel_entity(load_ptr)) == ADDRESS_TAKEN)
+ return;
+
+ key.irn = nods_block;
+ value = set_find(repairs, &key, sizeof(key), HASH_PTR(nods_block));
+
+ /* Load's pointer predecessor's link field contains the position in the block's link, where
+ must be searched the predecessor of this Load. */
+ i = (unsigned)get_irn_link(load_ptr);
+
+ /* If the link of Load's block doesn't contains at position "i" a node or isn't calculated,
+ than pred_search() must be called .*/
+ if (value == NULL) {
+ block_link(load, env, repairs);
+ key.irn = nods_block;
+ value = set_find(repairs, &key, sizeof(key), HASH_PTR(nods_block));
+ pred_search(load, value, repairs, i, 0);
+ } else if (value->link[i] == NULL)
+ pred_search(load, value, repairs, i, 0);
+
+ /* If after the pred_search() call the link of Load's block at position "i" is equal to NULL,
+ that means the loaded value wasn't initialized and the load predecessor is set to Unknown */
+ if (value->link[i] == NULL)
+ value->link[i] = new_Unknown(env->modes[i]);
+
+ /* The Load node can be turned into a tuple now. This tuple will be optimized later. */
+ turn_into_tuple(load, pn_Load_max);
+ set_Tuple_pred(load, pn_Load_M, load_mem);
+ set_Tuple_pred(load, pn_Load_res, value->link[i]);
+ set_Tuple_pred(load, pn_Load_X_except, new_Bad());
+ }
+}
+
+/**
+ * A walker along the memory edge. Load and Phi nodes muss be found for optimization
+ *
+ * @param node A node from the graph.
+ * @param env Contains information about scalars number and mode.
+ * @parm repairs A set, that contains all blocks, that have a link, and all Phis, that
+ * have copies to repair.
+*/
+static void memory_edge_walk2(ir_node *node, env_t *env, set *repairs)
+{
+ int i, p, n = get_irn_arity(node);
+ repairs_t key, *value, *value_block;
+ ir_node *phi_pred;
+ DDMN(node);
+
+ for (i = 0; i < n; i++) {
+ ir_node *pred = get_irn_n(node, i);
+
+ if((get_irn_op(pred) == op_Proj &&
+ get_irn_mode(pred) == mode_M) ||
+ get_irn_mode(pred) == mode_T ||
+ is_memop(pred) ||
+ get_irn_op(pred) == op_Call ||
+ get_irn_op(pred) == op_Alloc)
+ memory_edge_walk2(pred, env, repairs);
+
+ if(get_irn_op(pred) == op_Phi &&
+ get_irn_mode(pred) == mode_M &&
+ get_irn_link(pred) != NODE_VISITED){
+ set_irn_link(pred, NODE_VISITED);
+ memory_edge_walk2(pred, env, repairs);
+ }
+ }
+
+ if (get_irn_op(node) == op_Load)
+ load_handling(node, env, repairs);
+
+ if (get_irn_op(node) == op_Phi && get_irn_mode(node) == mode_M){
+ key.irn = node;
+ value = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
+ /* If the phi is in the set " repairs ", then must be handled.*/
+ if (value != NULL){
+ // DDMN(node);
+ key.irn = get_nodes_block(node);
+ value_block = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
+ n = get_irn_arity(node);
+ /* All predecessors of a Phi node muss be found.*/
+ for(i = 0; i < env->nvals; i ++)
+ for(p = 0; p < n; p ++){
+ phi_pred = get_Phi_pred(value->irn, p);
+ pred_search(phi_pred, value_block, repairs, i, p);
+ }
+ }
+ }
+ /* Reset the links, that have been used by the walk.*/
+ if (get_irn_link(node) == NODE_VISITED)
+ set_irn_link(node, NULL);
+}
+
+/**
+ * A walker along the memory edge in a loop.The walker walk from the node to the loop head.
+ * Load and Phi nodes muss be found for optimisation
+ *
+ * @param *node A node from the graph.
+ * @param *env Contains information about scalars number and mode.
+ * @parm *repairs A set, that contains all blocks, that have a link, and all Phis, that
+ * have copies to repair.
+*/
+static void loop_walk(ir_node *node, env_t *env, set *repairs)
+{
+ int i, p, n = get_irn_arity(node);
+ repairs_t key, *value, *value_block;
+ ir_node *phi_pred;
+ DDMN(node);
+
+ /* Test if the loop head have been achieved. */
+ if (has_backedges(get_nodes_block(node)))
+ return;
+
+ for (i = 0; i < n; i++) {
+ ir_node *pred = get_irn_n(node, i);
+
+ if((get_irn_op(pred) == op_Proj &&
+ get_irn_mode(pred) == mode_M) ||
+ get_irn_mode(pred) == mode_T ||
+ is_memop(pred) ||
+ get_irn_op(pred) == op_Call ||
+ get_irn_op(pred) == op_Alloc)
+ loop_walk(pred, env, repairs);
+
+ if(get_irn_op(pred) == op_Phi &&
+ get_irn_mode(pred) == mode_M &&
+ get_irn_link(pred) != LOOP_WALK) {
+ set_irn_link(pred, LOOP_WALK);
+ loop_walk(pred, env, repairs);
+ }
+ }
+
+ if (get_irn_op(node) == op_Load)
+ load_handling(node, env, repairs);
+
+ if (get_irn_op(node) == op_Phi && get_irn_mode(node) == mode_M){
+ key.irn = node;
+ value = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
+ /* If the phi is in the set " repairs ", then muss be handled.*/
+ if(value != NULL){
+ DDMN(node);
+ key.irn = get_nodes_block(node);
+ value_block = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
+ n = get_irn_arity(node);
+ /* All predecessors of a Phi node muss be found.*/
+ for(i = 0; i < env->nvals; i ++)
+ for(p = 0; p < n; p ++){
+ phi_pred = get_Phi_pred(value->irn, p);
+ pred_search(phi_pred, value_block, repairs, i, p);
+ }
+ }
+ }
+ /* Reset the links, that have beeb used by the walk.*/
+ if(get_irn_link(node) == LOOP_WALK)
+ set_irn_link(node, NULL);
+}
+
+/**
+ * Handle Stores that were been scalar replaced or
+ * will be scalar replaced.
+ *
+ * @param load A store node.
+ * @param env Contains information about scalars number and mode.
+ * @parm repairs A set, that contains all blocks, that have a link, and all Phis, that
+ * have copies to repair.
+ */
+static void store_handling(ir_node *store, env_t *env, set *repairs)
+{
+ repairs_t key, *value;
+ ir_node *nods_block, *store_mem, *store_ptr, *store_value, *phi;
+ ir_loop *store_l;
+
+ store_ptr = get_Store_ptr(store);
+
+ /* The pointer predecessor of Store must be a Sel node.*/
+ if (get_irn_op(store_ptr) == op_Sel) {
+ /* If the link field of a Store's is set to "ADDRESS_TAKEN", that mean this value
+ can't be scalar replaced. It's nothing to do and store_handling() must be exit.*/
+ if (get_entity_link(get_Sel_entity(store_ptr)) == ADDRESS_TAKEN)
+ return;
+
+ /* If the Store node is in a loop, than the loop head of the Store
+ * must be handled, if this was not already done. */
+ store_l = get_irn_loop(store);
+ if (store_l != NULL) {
+ phi = get_loop_node(store_l, 0);
+ if (get_irn_op(phi) != op_Block) {
+ key.irn = get_nodes_block(phi);
+ value = set_find(repairs, &key, sizeof(key), HASH_PTR(key.irn));
+ if (value == NULL) {
+ set_irn_link(phi, LOOP_HEAD_PHI);
+ block_link(phi, env, repairs);
+ phi_handling(phi, env, repairs);
+ }
+ }
+ }
+
+ DDMN(store);
+ nods_block = get_nodes_block(store);
+
+ key.irn = nods_block;
+ value = set_find(repairs, &key, sizeof(key), HASH_PTR(nods_block));
+
+ store_mem = get_Store_mem(store);
+ store_value = get_Store_value(store);
+
+ if (store_l != NULL)
+ loop_walk(store, env, repairs);
+ else
+ memory_edge_walk2(store, env, repairs);
+ /* Store's pointer predecessor's link field contains the position in the block's link, where
+ must be saved the value predecessor of this store. */
+ value->link[(unsigned)get_irn_link(store_ptr)] = store_value;
+
+ /* The store node can be turned into a tuple now. This tuple will be optimized later. */
+ turn_into_tuple(store, pn_Store_max);
+ set_Tuple_pred(store, pn_Store_M, store_mem);
+ set_Tuple_pred(store, pn_Store_X_except, new_Bad());
+ }
+}
+
+/**
+ * A walker along the memory edge. Stores, Phis and their blocks as well Load's blocks must be found for optimization
+ *
+ * @param node A node from the graph.
+ * @param env Contains information about scalars number and mode.
+ * @parm repairs A set, that contains all blocks, that have a link, and all Phis, that
+ * have copies to repair.
+*/
+static void memory_edge_walk(ir_node *node, env_t *env, set *repairs)
+{
+ int i, n = get_irn_arity(node);
+ ir_op *op;
+
+ DDMN(node);
+
+ set_irn_link(get_nodes_block(node), NULL);
+
+ for (i = n - 1; i >= 0; --i) {
+ ir_node *pred = get_irn_n(node, i);
+ ir_op *op = get_irn_op(pred);
+
+ if ((op == op_Proj &&
+ get_irn_mode(pred) == mode_M) ||
+ op == op_Load ||
+ op == op_Store ||
+ op == op_Call ||
+ op == op_Alloc)
+ memory_edge_walk(pred, env, repairs);
+
+ if (op == op_Phi &&
+ get_irn_mode(pred) == mode_M &&
+ get_irn_link(pred) != NODE_VISITED) {
+ set_irn_link(pred, NODE_VISITED);
+ memory_edge_walk(pred, env, repairs);
+ }
+ }
+
+ op = get_irn_op(node);
+ if (op == op_Store || op == op_Load)
+ block_link(node, env, repairs);
+
+ if (op == op_Phi && get_irn_mode(node) == mode_M)
+ phi_handling(node, env, repairs);
+
+ if (op == op_Store)
+ store_handling(node, env, repairs);
+
+ /* Reset the links, that have been used by the walk.*/
+ if (get_irn_link(node) == NODE_VISITED)
+ set_irn_link(node, NULL);
+}
+
+/**
+ * Make scalar replacement.
+ *
+ * @param envals The number of scalars.
+ * @parm repairs A set, that contains all blocks, that have a link, and all Phis, that
+ * have copies to repair.
+ * @param modes A flexible array, containing all the modes of
+ * the value numbers.
+ */
+static void do_scalar_replacements(int nvals, set * repairs, ir_mode **modes)
+{
+ ir_node *end_block = get_irg_end_block(current_ir_graph);
+ int i;
+ int n = get_Block_n_cfgpreds(end_block);
+ env_t env;
+
+ obstack_init(&env.obst);
+ env.nvals = nvals;
+ env.modes = modes;
+
+ /* Search for scalars.*/
+ for (i = 0; i < n; ++i) {
+ ir_node *pred = get_Block_cfgpred(end_block, i);
+ if (get_irn_op(pred) != op_Block)
+ memory_edge_walk(pred, &env, repairs);
+ }
+
+ /* Search for predecessors of scalars.*/
+ for (i = 0; i < n; ++i) {
+ ir_node *pred = get_Block_cfgpred(end_block, i);
+ if (get_irn_op(pred) != op_Block)
+ memory_edge_walk2(pred, &env, repairs);
+ }
+ obstack_free(&env.obst, NULL);
+}