/*
- * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
- *
* This file is part of libFirm.
- *
- * This file may be distributed and/or modified under the terms of the
- * GNU General Public License version 2 as published by the Free Software
- * Foundation and appearing in the file LICENSE.GPL included in the
- * packaging of this file.
- *
- * Licensees holding valid libFirm Professional Edition licenses may use
- * this file in accordance with the libFirm Commercial License.
- * Agreement provided with the Software.
- *
- * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
- * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE.
+ * Copyright (C) 2012 University of Karlsruhe.
*/
/**
#include "irtools.h"
#include "irloop_t.h"
#include "array.h"
-#include "firmstat.h"
+#include "firmstat_t.h"
#include "error.h"
#include "irpass_t.h"
(void) size;
return l1->src != l2->src;
-} /* LFTR_cmp */
+}
/**
* Find a LFTR edge.
key.src = src;
- return (LFTR_edge*)set_find(env->lftr_edges, &key, sizeof(key), hash_ptr(src));
-} /* LFTR_find */
+ return set_find(LFTR_edge, env->lftr_edges, &key, sizeof(key), hash_ptr(src));
+}
/**
* Add a LFTR edge.
* There might be more than one edge here. This is rather bad
* because we currently store only one.
*/
- set_insert(env->lftr_edges, &key, sizeof(key), hash_ptr(src));
-} /* LFTR_add */
+ (void)set_insert(LFTR_edge, env->lftr_edges, &key, sizeof(key), hash_ptr(src));
+}
/**
* Gets the node_entry of a node.
set_irn_link(irn, e);
}
return e;
-} /* get_irn_ne */
+}
/**
* Gets the scc from an induction variable.
{
node_entry *e = get_irn_ne(iv, env);
return e->pscc;
-} /* get_iv_scc */
+}
/**
* Check if irn is an IV.
static ir_node *is_iv(ir_node *irn, iv_env *env)
{
return get_irn_ne(irn, env)->header;
-} /* is_iv */
+}
/**
* Check if irn is a region constant.
ir_node *block = get_nodes_block(irn);
return (block != header_block) && block_dominates(block, header_block);
-} /* is_rc */
+}
/**
* Set compare function for the quad set.
(void) size;
return c1->code != c2->code || c1->op1 != c2->op1 || c1->op2 != c2->op2;
-} /* quad_cmp */
+}
/**
* Check if an reduced operation was already calculated.
key.op1 = op1;
key.op2 = op2;
- entry = (quadruple_t*)set_find(env->quad_map, &key, sizeof(key),
- (code * 9) ^ hash_ptr(op1) ^hash_ptr(op2));
+ entry = set_find(quadruple_t, env->quad_map, &key, sizeof(key), (code * 9) ^ hash_ptr(op1) ^ hash_ptr(op2));
if (entry)
return entry->res;
return NULL;
-} /* search */
+}
/**
* Add an reduced operation.
key.op2 = op2;
key.res = result;
- set_insert(env->quad_map, &key, sizeof(key),
- (code * 9) ^ hash_ptr(op1) ^hash_ptr(op2));
-} /* add */
+ (void)set_insert(quadruple_t, env->quad_map, &key, sizeof(key), (code * 9) ^ hash_ptr(op1) ^ hash_ptr(op2));
+}
/**
* Find a location where to place a bin-op whose operands are in
return block2;
assert(block_dominates(block2, block1));
return block1;
-} /* find_location */
+}
/**
* Create a node that executes an op1 code op1 operation.
panic("Unsupported opcode");
}
return result;
-} /* do_apply */
+}
/**
* The Apply operation.
}
}
return result;
-} /* apply */
+}
/**
* The Reduce operation.
get_irn_opname(orig), rc));
}
return result;
-} /* reduce */
+}
/**
* Update the scc for a newly created IV.
} while (! waitq_empty(wq));
del_waitq(wq);
DB((dbg, LEVEL_2, "\n"));
-} /* update_scc */
+}
/**
* The Replace operation. We found a node representing iv (+,-,*) rc
return 1;
}
return 0;
-} /* replace */
-
-#if 0
-/**
- * check if a given node is a mul with 2, 4, 8
- */
-static int is_x86_shift_const(ir_node *mul)
-{
- ir_node *rc;
-
- if (! is_Mul(mul))
- return 0;
-
- /* normalization put constants on the right side */
- rc = get_Mul_right(mul);
- if (is_Const(rc)) {
- ir_tarval *tv = get_Const_tarval(rc);
-
- if (tarval_is_long(tv)) {
- long value = get_tarval_long(tv);
-
- if (value == 2 || value == 4 || value == 8) {
- /* do not reduce multiplications by 2, 4, 8 */
- return 1;
- }
- }
- }
- return 0;
-} /* is_x86_shift_const */
-#endif
+}
/**
* Check if an IV represents a counter with constant limits.
pscc->incr = get_Const_tarval(have_incr);
pscc->code = code;
return code != iro_Bad;
-} /* is_counter_iv */
+}
/**
* Check the users of an induction variable for register pressure.
scc *pscc = e->pscc;
for (irn = pscc->head; irn != NULL; irn = e->next) {
- const ir_edge_t *edge;
-
foreach_out_edge(irn, edge) {
ir_node *user = get_edge_src_irn(edge);
node_entry *ne = get_irn_ne(user, env);
* to do a linear function test replacement, so go on.
*/
return 1;
-} /* check_users_for_reg_pressure */
+}
/**
* Check if a node can be replaced (+, -, *).
break;
}
return 0;
-} /* check_replace */
+}
/**
* Check which SCC's are induction variables.
next = e->next;
switch (get_irn_opcode(irn)) {
- case iro_Add:
case iro_Sub:
+ only_phi = 0;
+ {
+ ir_node *left = get_Sub_left(irn);
+ node_entry *left_entry = get_irn_ne(left, env);
+ ir_node *right = get_Sub_right(irn);
+ node_entry *right_entry = get_irn_ne(right, env);
+
+ if (left_entry->pscc != e->pscc ||
+ (right_entry->pscc != e->pscc && !is_rc(right, header))) {
+ /*
+ * Not an induction variable.
+ * Region constant are only allowed on right hand side.
+ */
+ goto fail;
+ }
+ }
+ break;
+
+ case iro_Add:
only_phi = 0;
/* fall through */
case iro_Phi:
next = e->next;
e->header = NULL;
}
-} /* classify_iv */
+}
/**
* Process an SCC for the operator strength reduction.
} else {
classify_iv(pscc, env);
}
-} /* process_scc */
+}
/**
* If an SCC is a Phi only cycle, remove it.
exchange(irn, out_rc);
}
++env->replaced;
-} /* remove_phi_cycle */
+}
/**
* Process a SCC for the Phi cycle remove.
if (e->next != NULL)
remove_phi_cycle(pscc, env);
-} /* process_phi_only_scc */
+}
/**
env->stack[env->tos++] = n;
e = get_irn_ne(n, env);
e->in_stack = 1;
-} /* push */
+}
/**
* Pop a node from the stack.
e->in_stack = 0;
return n;
-} /* pop */
+}
/**
* Do Tarjan's SCC algorithm and drive OSR.
env->process_scc(pscc, env);
}
}
-} /* dfs */
+}
/**
* Do the DFS by starting at the End node of a graph.
}
ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
-} /* do_dfs */
+}
/**
* Post-block-walker: assign the post-order number.
node_entry *e = get_irn_ne(block, env);
e->POnum = env->POnum++;
-} /* assign_po */
+}
/**
* Apply one LFTR edge operation.
return new_r_Const(irg, tv);
}
return do_apply(e->code, NULL, rc, e->rc, get_irn_mode(e->dst));
-} /* applyOneEdge */
+}
/**
* Applies the operations represented by the LFTR edges to a
DB((dbg, LEVEL_3, "\n"));
*pIV = iv;
return rc;
-} /* applyEdges */
+}
/**
* Walker, finds Cmp(iv, rc) or Cmp(rc, iv)
set_Cmp_right(cmp, nright);
++env->lftr_replaced;
}
-} /* do_lftr */
+}
/**
* do linear function test replacement.
static void lftr(ir_graph *irg, iv_env *env)
{
irg_walk_graph(irg, NULL, do_lftr, env);
-} /* lftr */
-
-/**
- * Pre-walker: set all node links to NULL and fix the
- * block of Proj nodes.
- */
-static void clear_and_fix(ir_node *irn, void *env)
-{
- (void)env;
-
- set_irn_link(irn, NULL);
-
- if (is_Proj(irn)) {
- ir_node *pred = get_Proj_pred(irn);
- ir_node *pred_block = get_nodes_block(pred);
-
- if (get_nodes_block(irn) != pred_block) {
- set_nodes_block(irn, pred_block);
- }
- }
-} /* clear_and_fix */
-
+}
/* Remove any Phi cycles with only one real input. */
void remove_phi_cycles(ir_graph *irg)
{
iv_env env;
+ assure_irg_properties(irg,
+ IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE
+ | IR_GRAPH_PROPERTY_CONSISTENT_OUTS
+ | IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES);
+
FIRM_DBG_REGISTER(dbg, "firm.opt.remove_phi");
DB((dbg, LEVEL_1, "Doing Phi cycle removement for %+F\n", irg));
* the same block as their predecessors.
* This can improve the placement of new nodes.
*/
- irg_walk_graph(irg, NULL, clear_and_fix, NULL);
-
- /* we need outs for calculating the post order */
- assure_irg_outs(irg);
+ irg_walk_graph(irg, NULL, firm_clear_link, NULL);
/* calculate the post order number for blocks. */
irg_out_block_walk(get_irg_start_block(irg), NULL, assign_po, &env);
ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
if (env.replaced) {
- DB((dbg, LEVEL_1, "remove_phi_cycles: %u Cycles removed\n\n", env.replaced));
+ DB((dbg, LEVEL_1, "remove_phi_cycles: %u Cycles removed\n\n",
+ env.replaced));
}
DEL_ARR_F(env.stack);
obstack_free(&env.obst, NULL);
-} /* remove_phi_cycles */
+
+ confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_CONTROL_FLOW);
+}
ir_graph_pass_t *remove_phi_cycles_pass(const char *name)
{
return def_graph_pass(name ? name : "remove_phi_cycles", remove_phi_cycles);
-} /* remove_phi_cycles_pass */
+}
/**
* Post-walker: fix Add and Sub nodes that where results of I<->P conversions.
}
}
}
-} /* fix_adds_and_subs */
+}
/* Performs Operator Strength Reduction for the passed graph. */
void opt_osr(ir_graph *irg, unsigned flags)
FIRM_DBG_REGISTER(dbg, "firm.opt.osr");
+ assure_irg_properties(irg,
+ IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE
+ | IR_GRAPH_PROPERTY_CONSISTENT_OUTS
+ | IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES);
+
DB((dbg, LEVEL_1, "Doing Operator Strength Reduction for %+F\n", irg));
obstack_init(&env.obst);
* the same block as its predecessors.
* This can improve the placement of new nodes.
*/
- irg_walk_graph(irg, NULL, clear_and_fix, NULL);
+ irg_walk_graph(irg, NULL, firm_clear_link, NULL);
- /* we need dominance */
- assure_doms(irg);
-
- assure_edges(irg);
-
- /* calculate the post order number for blocks by walking the out edges. */
- assure_irg_outs(irg);
irg_block_edges_walk(get_irg_start_block(irg), NULL, assign_po, &env);
/* calculate the SCC's and drive OSR. */
DEL_ARR_F(env.stack);
obstack_free(&env.obst, NULL);
- edges_deactivate(irg);
+ confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE);
}
typedef struct pass_t {
pass_t *pass = (pass_t*)context;
opt_osr(irg, pass->flags);
return 0;
-} /* pass_wrapper */
+}
ir_graph_pass_t *opt_osr_pass(const char *name, unsigned flags)
{
pass->flags = flags;
return def_graph_pass_constructor(
&pass->pass, name ? name : "osr", pass_wrapper);
-} /* opt_osr_pass */
+}
projects / libfirm / blobdiff