* @author Christian Helmer
* @brief loop inversion and loop unrolling
*
- * @version $Id$
*/
#include "config.h"
#include "beutil.h"
#include "irpass.h"
#include "irdom.h"
-#include "opt_manage.h"
#include <math.h>
#include "irbackedge_t.h"
-#include "irphase_t.h"
+#include "irnodemap.h"
#include "irloop_t.h"
-
-DEBUG_ONLY(static firm_dbg_module_t *dbg);
+DEBUG_ONLY(static firm_dbg_module_t *dbg;)
/**
* Convenience macro for iterating over every phi node of the given block.
/* Number of unrolls to perform */
static int unroll_nr;
/* Phase is used to keep copies of nodes. */
-static ir_phase *phase;
+static ir_nodemap map;
+static struct obstack obst;
/* Loop operations. */
typedef enum loop_op_t {
/* Find the loops head/the blocks with cfpred outside of the loop */
if (is_Block(node)) {
- const ir_edge_t *edge;
unsigned outs_n = 0;
/* Count innerloop branches */
{
ir_graph *irg;
ir_mode *mode;
- const ir_edge_t *edge;
- const ir_edge_t *next;
assert(orig_block && orig_val && second_block && second_val &&
"no parameter of construct_ssa may be NULL");
ssa_second_def = second_val;
/* Only fix the users of the first, i.e. the original node */
- foreach_out_edge_safe(orig_val, edge, next) {
+ foreach_out_edge_safe(orig_val, edge) {
ir_node *user = get_edge_src_irn(edge);
int j = get_edge_src_pos(edge);
ir_node *user_block = get_nodes_block(user);
unrolling_node_info *info;
assert(nr != 0 && "0 reserved");
- info = (unrolling_node_info *)phase_get_irn_data(phase, n);
+ info = ir_nodemap_get(unrolling_node_info, &map, n);
if (! info) {
- ir_node **arr;
+ ir_node **const arr = NEW_ARR_DZ(ir_node*, &obst, unroll_nr);
- info = XMALLOCZ(unrolling_node_info);
- arr = NEW_ARR_F(ir_node *, unroll_nr);
+ info = OALLOCZ(&obst, unrolling_node_info);
info->copies = arr;
- memset(info->copies, 0, (unroll_nr) * sizeof(ir_node *));
-
- phase_set_irn_data(phase, n, info);
+ ir_nodemap_insert(&map, n, info);
}
/* Original node */
info->copies[0] = n;
static ir_node *get_unroll_copy(ir_node *n, int nr)
{
ir_node *cp;
- unrolling_node_info *info = (unrolling_node_info *)phase_get_irn_data(phase, n);
+ unrolling_node_info *info = ir_nodemap_get(unrolling_node_info, &map, n);
if (! info)
return NULL;
/* Sets copy cp of node n. */
static void set_inversion_copy(ir_node *n, ir_node *cp)
{
- phase_set_irn_data(phase, n, cp);
+ ir_nodemap_insert(&map, n, cp);
}
/* Getter of copy of n for inversion */
static ir_node *get_inversion_copy(ir_node *n)
{
- ir_node *cp = (ir_node *)phase_get_irn_data(phase, n);
+ ir_node *cp = ir_nodemap_get(ir_node, &map, n);
return cp;
}
set_backedge(n, i);
}
}
+ free(ins);
+ free(bes);
}
/* Extends a block by a copy of its pred at pos,
{
ir_node *new_in;
ir_node *phi;
- ir_node *pred;
assert(is_Block(block));
/* Extend block by copy of definition at pos */
- pred = get_irn_n(block, pos);
+ ir_node *const pred = get_Block_cfgpred(block, pos);
new_in = get_inversion_copy(pred);
DB((dbg, LEVEL_5, "Extend block %N by %N cp of %N\n", block, new_in, pred));
extend_irn(block, new_in, false);
/* Returns the number of blocks backedges. With or without alien bes. */
static int get_backedge_n(ir_node *block, bool with_alien)
{
- int i;
- int be_n = 0;
- int arity = get_irn_arity(block);
-
- assert(is_Block(block));
-
- for (i = 0; i < arity; ++i) {
- ir_node *pred = get_irn_n(block, i);
+ int be_n = 0;
+ int const arity = get_Block_n_cfgpreds(block);
+ for (int i = 0; i < arity; ++i) {
+ ir_node *const pred = get_Block_cfgpred(block, i);
if (is_backedge(block, i) && (with_alien || is_in_loop(pred)))
++be_n;
}
int arity;
ir_node *cp;
ir_node **cpin;
- ir_graph *irg = current_ir_graph;
/**
* break condition and cycle resolver, creating temporary node copies
*/
- if (get_irn_visited(node) >= get_irg_visited(irg)) {
+ if (irn_visited(node)) {
/* Here we rely on nodestate's copy being initialized with NULL */
DB((dbg, LEVEL_5, "copy_walk: We have already visited %N\n", node));
if (get_inversion_copy(node) == NULL) {
for(i = 0; i < blocks; ++i) {
ir_node *block = cc_blocks[i];
- int a;
- int arity = get_irn_arity(block);
/* Head is an exception. */
if (block == loop_head)
continue;
- for(a = 0; a < arity; ++a) {
- if (! is_nodes_block_marked(get_irn_n(block, a))) {
+ int const arity = get_Block_n_cfgpreds(block);
+ for (int a = 0; a < arity; ++a) {
+ if (!is_nodes_block_marked(get_Block_cfgpred(block, a))) {
set_Block_mark(block, 0);
--inversion_blocks_in_cc;
DB((dbg, LEVEL_5, "Removed %N from cc (blocks in cc %d)\n",
*/
static void find_condition_chain(ir_node *block)
{
- const ir_edge_t *edge;
bool mark = false;
bool has_be = false;
bool jmp_only = true;
inversion_blocks_in_cc = 0;
/* Use phase to keep copy of nodes from the condition chain. */
- phase = new_phase(irg, phase_irn_init_default);
+ ir_nodemap_init(&map, irg);
+ obstack_init(&obst);
/* Search for condition chains and temporarily save the blocks in an array. */
cc_blocks = NEW_ARR_F(ir_node *, 0);
DEL_ARR_F(cur_head_outs);
/* Duplicated blocks changed doms */
- set_irg_doms_inconsistent(irg);
- set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);
+ clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE
+ | IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO);
++stats.inverted;
}
/* free */
- phase_free(phase);
+ obstack_free(&obst, NULL);
+ ir_nodemap_destroy(&map);
DEL_ARR_F(cond_chain_entries);
DEL_ARR_F(head_df_loop);
if (!is_Cmp(cmp))
return NULL;
- DB((dbg, LEVEL_5, "projection is %s\n", get_relation_string(get_Proj_proj(projx))));
+ DB((dbg, LEVEL_5, "projection is %s\n", get_relation_string(get_Cmp_relation(cmp))));
switch(get_Proj_proj(projx)) {
case pn_Cond_false:
}
/* Use phase to keep copy of nodes from the condition chain. */
- phase = new_phase(current_ir_graph, phase_irn_init_default);
+ ir_nodemap_init(&map, current_ir_graph);
+ obstack_init(&obst);
/* Copies the loop */
copy_loop(loop_entries, unroll_nr - 1);
else
++stats.invariant_unroll;
- set_irg_doms_inconsistent(current_ir_graph);
+ clear_irg_properties(current_ir_graph, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
DEL_ARR_F(loop_entries);
+ obstack_free(&obst, NULL);
+ ir_nodemap_destroy(&map);
}
}
/* Reset loop info */
memset(&loop_info, 0, sizeof(loop_info_t));
- DB((dbg, LEVEL_1, " >>>> current loop includes node %N <<<\n",
- get_loop_node(loop, 0)));
+ DB((dbg, LEVEL_1, " >>>> current loop %ld <<<\n",
+ get_loop_loop_nr(loop)));
/* Collect loop informations: head, node counts. */
irg_walk_graph(irg, get_loop_info, NULL, NULL);
default:
panic("Loop optimization not implemented.");
}
- DB((dbg, LEVEL_1, " <<<< end of loop with node %N >>>>\n",
- get_loop_node(loop, 0)));
+ DB((dbg, LEVEL_1, " <<<< end of loop with node %ld >>>>\n",
+ get_loop_loop_nr(loop)));
}
/* Find innermost loops and add them to loops. */
static void find_innermost_loop(ir_loop *loop)
{
- /* descend into sons */
- size_t sons = get_loop_n_sons(loop);
-
- if (sons == 0) {
- ARR_APP1(ir_loop *, loops, loop);
- } else {
- size_t s;
- for (s = 0; s < sons; ++s) {
- find_innermost_loop(get_loop_son(loop, s));
+ bool had_sons = false;
+ size_t n_elements = get_loop_n_elements(loop);
+ size_t e;
+
+ for (e = 0; e < n_elements; ++e) {
+ loop_element element = get_loop_element(loop, e);
+ if (*element.kind == k_ir_loop) {
+ find_innermost_loop(element.son);
+ had_sons = true;
}
}
+
+ if (!had_sons) {
+ ARR_APP1(ir_loop*, loops, loop);
+ }
}
static void set_loop_params(void)
void loop_optimization(ir_graph *irg)
{
ir_loop *loop;
- size_t sons, nr;
- size_t i;
+ size_t i;
+ size_t n_elements;
+
+ assure_irg_properties(irg,
+ IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES
+ | IR_GRAPH_PROPERTY_CONSISTENT_OUTS
+ | IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO);
set_loop_params();
collect_phiprojs(irg);
loop = get_irg_loop(irg);
- sons = get_loop_n_sons(loop);
loops = NEW_ARR_F(ir_loop *, 0);
/* List all inner loops */
- for (nr = 0; nr < sons; ++nr) {
- find_innermost_loop(get_loop_son(loop, nr));
+ n_elements = get_loop_n_elements(loop);
+ for (i = 0; i < n_elements; ++i) {
+ loop_element element = get_loop_element(loop, i);
+ if (*element.kind != k_ir_loop)
+ continue;
+ find_innermost_loop(element.son);
}
/* Set all links to NULL */
DEL_ARR_F(loops);
ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
+
+ confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE);
}
-static ir_graph_state_t perform_loop_unrolling(ir_graph *irg)
+void do_loop_unrolling(ir_graph *irg)
{
loop_op = loop_op_unrolling;
loop_optimization(irg);
- return 0;
}
-static ir_graph_state_t perform_loop_inversion(ir_graph *irg)
+void do_loop_inversion(ir_graph *irg)
{
loop_op = loop_op_inversion;
loop_optimization(irg);
- return 0;
}
-static ir_graph_state_t perform_loop_peeling(ir_graph *irg)
+void do_loop_peeling(ir_graph *irg)
{
loop_op = loop_op_peeling;
loop_optimization(irg);
- return 0;
}
-optdesc_t opt_unroll_loops = {
- "unroll-loops",
- IR_GRAPH_STATE_CONSISTENT_OUT_EDGES | IR_GRAPH_STATE_CONSISTENT_OUTS | IR_GRAPH_STATE_CONSISTENT_LOOPINFO,
- perform_loop_unrolling,
-};
-
-optdesc_t opt_invert_loops = {
- "invert-loops",
- IR_GRAPH_STATE_CONSISTENT_OUT_EDGES | IR_GRAPH_STATE_CONSISTENT_OUTS | IR_GRAPH_STATE_CONSISTENT_LOOPINFO,
- perform_loop_inversion,
-};
-
-optdesc_t opt_peel_loops = {
- "peel-loops",
- IR_GRAPH_STATE_CONSISTENT_OUT_EDGES | IR_GRAPH_STATE_CONSISTENT_OUTS | IR_GRAPH_STATE_CONSISTENT_LOOPINFO,
- perform_loop_peeling,
-};
-
-void do_loop_unrolling(ir_graph *irg)
-{ perform_irg_optimization(irg, &opt_unroll_loops); }
-
-void do_loop_inversion(ir_graph *irg)
-{ perform_irg_optimization(irg, &opt_invert_loops); }
-
-void do_loop_peeling(ir_graph *irg)
-{ perform_irg_optimization(irg, &opt_peel_loops); }
-
ir_graph_pass_t *loop_inversion_pass(const char *name)
{
return def_graph_pass(name ? name : "loop_inversion", do_loop_inversion);
projects / libfirm / blobdiff