/*
- * 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 "irpass.h"
#include "tv_t.h"
#include "irtools.h"
+#include "firmstat_t.h"
#include "irprintf.h"
#include "irdump.h"
return a->op->ops.node_cmp_attr(a, b);
return 0;
-} /* cmp_irn_opcode */
+}
#ifdef CHECK_PARTITIONS
/**
assert(node->flagged == 0);
assert(node->part == T);
}
-} /* check_partition */
+}
/**
* check that all leader nodes in the partition have the same opcode.
assert(cmp_irn_opcode(repr, irn) == 0);
}
}
-} /* check_opcode */
+}
static void check_all_partitions(environment_t *env)
{
(void) ofs;
(void) Z;
#endif
-} /* ido_check_list */
+}
/**
* Check a local list.
static void check_list(const node_t *list, const partition_t *Z)
{
do_check_list(list, offsetof(node_t, next), Z);
-} /* check_list */
+}
#else
#define check_partition(T)
}
}
DB((dbg, LEVEL_2, "\n}\n"));
-} /* dump_partition */
+}
/**
* Dumps a list.
DB((dbg, LEVEL_3, "\n}\n"));
#undef GET_LINK
-} /* do_dump_list */
+}
/**
* Dumps a race list.
static void dump_race_list(const char *msg, const node_t *list)
{
do_dump_list(msg, list, offsetof(node_t, race_next));
-} /* dump_race_list */
+}
/**
* Dumps a local list.
static void dump_list(const char *msg, const node_t *list)
{
do_dump_list(msg, list, offsetof(node_t, next));
-} /* dump_list */
+}
/**
* Dump all partitions.
DB((dbg, LEVEL_2, "All partitions\n===============\n"));
for (P = env->dbg_list; P != NULL; P = P->dbg_next)
dump_partition("", P);
-} /* dump_all_partitions */
+}
/**
* Sump a split list.
split = ',';
}
DB((dbg, LEVEL_2, "\n}\n"));
-} /* dump_split_list */
+}
/**
* Dump partition and type for a node.
ir_fprintf(F, "info2 : \"partition %u type %+F\"\n", node->part->nr, node->type);
return 1;
-} /* dump_partition_hook */
+}
#else
#define dump_partition(msg, part)
return;
}
panic("wrong translation from %+F to %+F on node %+F", old_type, node->type, node->node);
-} /* verify_type */
+}
#else
#define verify_type(old_type, node)
(void) size;
return e1->id != e2->id;
-} /* listmap_cmp_ptr */
+}
/**
* Initializes a listmap.
{
map->map = new_set(listmap_cmp_ptr, 16);
map->values = NULL;
-} /* listmap_init */
+}
/**
* Terminates a listmap.
static void listmap_term(listmap_t *map)
{
del_set(map->map);
-} /* listmap_term */
+}
/**
* Return the associated listmap entry for a given id.
map->values = entry;
}
return entry;
-} /* listmap_find */
+}
/**
* Calculate the hash value for an opcode map entry.
else if (code == iro_Proj)
hash += (unsigned)get_Proj_proj(n);
return hash;
-} /* opcode_hash */
+}
/**
* Compare two entries in the opcode map.
(void) size;
return cmp_irn_opcode(o1->irn, o2->irn);
-} /* cmp_opcode */
+}
/**
* Compare two Def-Use edges for input position.
/* no overrun, because range is [-1, MAXINT] */
return ea->pos - eb->pos;
-} /* cmp_def_use_edge */
+}
/**
* We need the Def-Use edges sorted.
qsort(irn->o.out->edges, n_outs, sizeof(irn->o.out->edges[0]),
cmp_def_use_edge);
node->max_user_input = n_outs > 0 ? irn->o.out->edges[n_outs-1].pos : -1;
-} /* sort_irn_outs */
+}
/**
* Return the type of a node.
static inline lattice_elem_t get_node_type(const ir_node *irn)
{
return get_irn_node(irn)->type;
-} /* get_node_type */
+}
/**
* Return the tarval of a node.
if (is_tarval(type.tv))
return type.tv;
return tarval_bottom;
-} /* get_node_type */
+}
/**
* Add a partition to the worklist.
X->wl_next = env->worklist;
X->on_worklist = 1;
env->worklist = X;
-} /* add_to_worklist */
+}
/**
* Create a new empty partition.
#endif
return part;
-} /* new_partition */
+}
/**
* Get the first node from a partition.
static inline node_t *get_first_node(const partition_t *X)
{
return list_entry(X->Leader.next, node_t, node_list);
-} /* get_first_node */
+}
/**
* Return the type of a partition (assuming partition is non-empty and
{
const node_t *first = get_first_node(X);
return first->type;
-} /* get_partition_type */
+}
/**
* Creates a partition node for the given IR-node and place it
++part->n_leader;
return node;
-} /* create_partition_node */
+}
/**
* Pre-Walker, initialize all Nodes' type to U or top and place
if (is_Block(irn)) {
set_Block_phis(irn, NULL);
}
-} /* create_initial_partitions */
+}
/**
* Post-Walker, collect all Block-Phi lists, set Cond.
ir_node *block = get_nodes_block(irn);
add_Block_phi(block, irn);
}
-} /* init_block_phis */
+}
/**
* Add a node to the entry.partition.touched set and
check_list(part->touched, part);
}
-} /* add_to_touched */
+}
/**
* Place a node on the cprop list.
add_to_cprop(p, env);
}
}
-} /* add_to_cprop */
+}
/**
* Update the worklist: If Z is on worklist then add Z' to worklist.
} else {
add_to_worklist(Z, env);
}
-} /* update_worklist */
+}
/**
* Make all inputs to x no longer be F.def_use edges.
}
}
}
-} /* move_edges_to_leader */
+}
/**
* Split a partition that has NO followers by a local list.
update_worklist(Z, Z_prime, env);
return Z_prime;
-} /* split_no_followers */
+}
/**
* Make the Follower -> Leader transition for a node.
list_del(&n->node_list);
list_add_tail(&n->node_list, &n->part->Leader);
++n->part->n_leader;
-} /* follower_to_leader */
+}
/**
* The environment for one race step.
break;
}
return 1;
-} /* is_real_follower */
+}
/**
* Do one step in the race.
env->index = 0;
}
return 1;
-} /* step */
+}
/**
* Clear the flags from a list and check for
n->flagged = 0;
}
return res;
-} /* clear_flags */
+}
/**
* Split a partition by a local list using the race.
}
return X_prime;
-} /* split */
+}
/**
* Returns non-zero if the i'th input of a Phi node is live.
}
/* else it's the control input, always live */
return 1;
-} /* is_live_input */
+}
/**
* Return non-zero if a type is a constant.
if (type.tv != tarval_bottom && type.tv != tarval_top)
return 1;
return 0;
-} /* is_constant_type */
+}
/**
* Check whether a type is neither Top or a constant.
return 0;
}
return 1;
-} /* type_is_neither_top_nor_const */
+}
/**
* Collect nodes to the touched list.
}
}
}
-} /* collect_touched */
+}
/**
* Collect commutative nodes to the touched list.
}
}
}
-} /* collect_commutative_touched */
+}
/**
* Split the partitions if caused by the first entry on the worklist.
assert(n_touched <= Z->n_leader);
}
}
-} /* cause_splits */
+}
/**
* Implements split_by_what(): Split a partition by characteristics given
listmap_term(&map);
return *P;
-} /* split_by_what */
+}
/** lambda n.(n.type) */
static void *lambda_type(const node_t *node, environment_t *env)
{
(void)env;
return node->type.tv;
-} /* lambda_type */
+}
/** lambda n.(n.opcode) */
static void *lambda_opcode(const node_t *node, environment_t *env)
entry = set_insert(opcode_key_t, env->opcode2id_map, &key, sizeof(key), opcode_hash(&key));
return entry;
-} /* lambda_opcode */
+}
/** lambda n.(n[i].partition) */
static void *lambda_partition(const node_t *node, environment_t *env)
pred = i == -1 ? get_irn_n(skipped, i) : get_irn_n(node->node, i);
p = get_irn_node(pred);
return p->part;
-} /* lambda_partition */
+}
/** lambda n.(n[i].partition) for commutative nodes */
static void *lambda_commutative_partition(const node_t *node, environment_t *env)
return p->part;
}
-} /* lambda_commutative_partition */
+}
/**
* Returns true if a type is a constant (and NOT Top
if (is_tarval(type.tv))
return tarval_is_constant(type.tv);
return is_entity(type.sym.entity_p);
-} /* is_con */
+}
/**
* Implements split_by().
}
}
} while (P != NULL);
-} /* split_by */
+}
/**
* (Re-)compute the type for a given node.
node->type.tv = tarval_reachable;
else
node->type.tv = computed_value(irn);
-} /* default_compute */
+}
/**
* (Re-)compute the type for a Block node.
int i;
ir_node *block = node->node;
- if (block == get_irg_start_block(current_ir_graph) || get_Block_entity(block) != NULL) {
+ ir_graph *const irg = get_Block_irg(block);
+ if (block == get_irg_start_block(irg) || get_Block_entity(block) != NULL) {
/* start block and labelled blocks are always reachable */
node->type.tv = tarval_reachable;
return;
}
}
node->type.tv = tarval_top;
-} /* compute_Block */
+}
/**
* (Re-)compute the type for a Bad node.
{
/* Bad nodes ALWAYS compute Top */
node->type.tv = tarval_top;
-} /* compute_Bad */
+}
/**
* (Re-)compute the type for an Unknown node.
* (jump threading for instance) might replace them by Phib's...
*/
node->type.tv = tarval_UNKNOWN;
-} /* compute_Unknown */
+}
/**
* (Re-)compute the type for a Jmp node.
node_t *block = get_irn_node(get_nodes_block(node->node));
node->type = block->type;
-} /* compute_Jmp */
+}
/**
* (Re-)compute the type for the Return node.
* This is already checked in compute(). so we can return
* Reachable here. */
node->type.tv = tarval_reachable;
-} /* compute_Return */
+}
/**
* (Re-)compute the type for the End node.
{
/* the End node is NOT dead of course */
node->type.tv = tarval_reachable;
-} /* compute_End */
+}
/**
* (Re-)compute the type for a Call.
* predecessors.
*/
node->type.tv = tarval_bottom;
-} /* compute_Call */
+}
/**
* (Re-)compute the type for a SymConst node.
default:
node->type.tv = computed_value(irn);
}
-} /* compute_SymConst */
+}
/**
* (Re-)compute the type for a Phi node.
/* else nothing, constants are the same */
}
node->type = type;
-} /* compute_Phi */
+}
/**
* (Re-)compute the type for an Add. Special case: one nodes is a Zero Const.
}
node->type.tv = tarval_bottom;
}
-} /* compute_Add */
+}
/**
* (Re-)compute the type for a Sub. Special case: both nodes are congruent.
} else {
node->type.tv = tarval_bottom;
}
-} /* compute_Sub */
+}
/**
* (Re-)compute the type for an Eor. Special case: both nodes are congruent.
} else {
node->type.tv = tarval_bottom;
}
-} /* compute_Eor */
+}
/**
* (Re-)compute the type for Cmp.
}
}
}
-} /* compute_Proj_Cond */
+}
static void compute_Proj_Switch(node_t *node, ir_node *switchn)
{
}
default_compute(node);
-} /* compute_Proj */
+}
/**
* (Re-)compute the type for a Confirm.
}
/* a Confirm is a copy OR a Const */
node->type = pred->type;
-} /* compute_Confirm */
+}
/**
* (Re-)compute the type for a given node.
func = (compute_func)node->node->op->ops.generic;
if (func != NULL)
func(node);
-} /* compute */
+}
/*
* Identity functions: Note that one might think that identity() is just a
* tarval_top, is in the TOP partition and should NOT being split! */
assert(n_part != NULL);
return n_part;
-} /* identity_Phi */
+}
/**
* Calculates the Identity for commutative 0 neutral nodes.
if (b->type.tv == zero)
return a;
return node;
-} /* identity_comm_zero_binop */
+}
/**
* Calculates the Identity for Shift nodes.
if (b->type.tv == zero)
return get_irn_node(get_binop_left(op));
return node;
-} /* identity_shift */
+}
/**
* Calculates the Identity for Mul nodes.
if (b->type.tv == one)
return a;
return node;
-} /* identity_Mul */
+}
/**
* Calculates the Identity for Sub nodes.
if (b->type.tv == get_mode_null(mode))
return get_irn_node(get_Sub_left(sub));
return node;
-} /* identity_Sub */
+}
/**
* Calculates the Identity for And nodes.
if (b->type.tv == neutral)
return a;
return node;
-} /* identity_And */
+}
/**
* Calculates the Identity for Confirm nodes.
/* a Confirm is always a Copy */
return get_irn_node(get_Confirm_value(confirm));
-} /* identity_Confirm */
+}
/**
* Calculates the Identity for Mux nodes.
return t;
/* for now, the 1-input identity is not supported */
-#if 0
- sel = get_irn_node(get_Mux_sel(mux));
-
- /* Mux sel input is mode_b, so it is always a tarval */
- if (sel->type.tv == tarval_b_true)
- return t;
- if (sel->type.tv == tarval_b_false)
- return f;
-#endif
return node;
-} /* identity_Mux */
+}
/**
* Calculates the Identity for nodes.
default:
return node;
}
-} /* identity */
+}
/**
* Node follower is a (new) follower of leader, segregate Leader
break;
}
}
-} /* segregate_def_use_chain_1 */
+}
/**
* Node follower is a (new) follower segregate its Leader
segregate_def_use_chain_1(follower, pred);
}
-} /* segregate_def_use_chain */
+}
/**
* Propagate constant evaluation.
}
split_by(Y, env);
}
-} /* propagate */
+}
/**
* Get the leader for a given node from its congruence class.
return get_first_node(part)->node;
}
return node->node;
-} /* get_leader */
+}
/**
* Returns non-zero if a mode_T node has only one reachable output.
}
}
return 1;
-} /* only_one_reachable_proj */
+}
/**
* Return non-zero if the control flow predecessor node pred
return only_one_reachable_proj(pred);
}
return 0;
-} /* can_exchange */
+}
/**
* Block Post-Walker, apply the analysis results on control flow by
}
}
- if (block == get_irg_end_block(current_ir_graph)) {
+ ir_graph *const irg = get_Block_irg(block);
+ if (block == get_irg_end_block(irg)) {
/* Analysis found out that the end block is unreachable,
* hence we remove all its control flow predecessors. */
set_irn_in(block, 0, NULL);
}
set_irn_in(block, k, in_X);
env->modified = 1;
-} /* apply_cf */
+}
/**
* Exchange a node by its leader.
}
}
exchange(irn, leader);
-} /* exchange_leader */
+}
/**
* Check, if all users of a mode_M node are dead. Use
}
/* all users are unreachable */
return 1;
-} /* all_user_are_dead */
+}
/**
* Walker: Find reachable mode_M nodes that have only
DB((dbg, LEVEL_1, "%+F must be kept\n", irn));
ARR_APP1(ir_node *, env->kept_memory, irn);
}
-} /* find_kept_memory */
+}
/**
* Post-Walker, apply the analysis results;
}
}
}
-} /* apply_result */
+}
/**
* Fix the keep-alives by deleting unreachable ones.
set_End_keepalives(end, j, in);
env->modified = 1;
}
-} /* apply_end */
+}
#define SET(code) op_##code->ops.generic = (op_func)compute_##code
SET(Return);
SET(End);
SET(Call);
-} /* set_compute_functions */
+}
/**
* Add memory keeps.
}
}
ir_nodeset_destroy(&set);
-} /* add_memory_keeps */
+}
void combo(ir_graph *irg)
{
dump_all_partitions(&env);
check_all_partitions(&env);
-#if 0
- dump_ir_block_graph(irg, "-partition");
-#endif
-
/* apply the result */
/* check, which nodes must be kept */
current_ir_graph = rem;
confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE);
-} /* combo */
+}
/* Creates an ir_graph pass for combo. */
ir_graph_pass_t *combo_pass(const char *name)
{
return def_graph_pass(name ? name : "combo", combo);
-} /* combo_pass */
+}
projects / libfirm / blobdiff