*/
# include "ircons.h"
-# include "array.h"
+# include "common.h"
+# include "irvrfy.h"
+# include "irop.h"
# include "iropt.h"
+# include "irgmod.h"
+# include "array.h"
/* memset belongs to string.h */
# include "string.h"
+# include "irnode.h"
+#if USE_EXPICIT_PHI_IN_STACK
+/* A stack needed for the automatic Phi node construction in constructor
+ Phi_in. */
+struct Phi_in_stack {
+ ir_node **stack;
+ int pos;
+};
+#endif
+
+/*********************************************** */
+/** privat interfaces, for professional use only */
+
+/* Constructs a Block with a fixed number of predecessors.*/
-/* irnode constructor */
-/* create a new irnode in irg, with an op, mode, arity and */
-/* some incoming irnodes */
-/* this constructor is used in every specified irnode constructor */
inline ir_node *
-new_ir_node (ir_graph *irg, ir_node *block, ir_op *op, ir_mode *mode,
- int arity, ir_node **in)
+new_r_Block (ir_graph *irg, int arity, ir_node **in)
{
ir_node *res;
- int node_size = offsetof (ir_node, attr) + op->attr_size;
- res = (ir_node *) obstack_alloc (irg->obst, node_size);
+ res = new_ir_node (current_ir_graph, NULL, op_Block, mode_R, arity, in);
- res->kind = k_ir_node;
- res->op = op;
- res->mode = mode;
- res->visit = 0;
- res->link = NULL;
- if (arity < 0) {
- res->in = NEW_ARR_F (ir_node *, 1);
- } else {
- res->in = NEW_ARR_D (ir_node *, irg->obst, (arity+1));
- memcpy (&res->in[1], in, sizeof (ir_node *) * arity);
- }
- res->in[0] = block;
+ irn_vrfy (res);
return res;
}
+ir_node *
+new_r_Start (ir_graph *irg, ir_node *block)
+{
+ ir_node *res;
+ res = new_ir_node (irg, block, op_Start, mode_T, 0, NULL);
+ irn_vrfy (res);
+ return res;
+}
-/*********************************************** */
-/** privat interfaces, for professional use only */
+ir_node *
+new_r_End (ir_graph *irg, ir_node *block)
+{
+ ir_node *res;
+
+ res = new_ir_node (irg, block, op_End, mode_X, -1, NULL);
+
+ irn_vrfy (res);
+ return res;
+}
/* Creates a Phi node with 0 predecessors */
inline ir_node *
/* GL I'm not sure whether we should optimize this guy. *
res = optimize (res); ??? */
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
res = new_ir_node (irg, block, op_Phi, mode, arity, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
return res;
}
-
void free_to_Phi_in_stack(ir_node *phi) {
assert(get_irn_opcode(phi) == iro_Phi);
assert (res->kind == k_ir_node);
assert (res->op == op_Phi);
res->mode = mode;
- res->visit = 0;
+ res->visited = 0;
res->link = NULL;
assert (arity >= 0);
/* ???!!! How to free the old in array?? */
#endif
-
/* Creates a Phi node with a given, fixed array **in of predecessors.
If the Phi node is unnecessary, as the same value reaches the block
through all control flow paths, it is eliminated and the value
#else
res = known = new_ir_node (irg, block, op_Phi, mode, ins, in);
#endif
- /* The in-array can contain NULLs. These were returned by get_r_value_internal
- if it reached the same block/definition on a second path.
+ /* The in-array can contain NULLs. These were returned by
+ get_r_value_internal if it reached the same block/definition on a
+ second path.
The NULLs are replaced by the node itself to simplify the test in the
next loop. */
for (i=0; i < ins; ++i)
res = known;
} else {
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
}
/* return the pointer to the Phi node. This node might be deallocated! */
res = new_ir_node (irg, block, op_Const, mode, 0, NULL);
res->attr.con = con;
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
#if 0
res = local_optimize_newby (res);
ir_node *res;
res = new_ir_node (irg, block, op_Id, mode, 1, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
ir_node *
-new_r_Proj (ir_graph *irg, ir_node *block, ir_node *arg, ir_mode *mode, long proj)
+new_r_Proj (ir_graph *irg, ir_node *block, ir_node *arg, ir_mode *mode,
+ long proj)
{
ir_node *in[1] = {arg};
ir_node *res;
res = new_ir_node (irg, block, op_Proj, mode, 1, in);
res->attr.proj = proj;
+
+ assert(res);
+ assert(get_Proj_pred(res));
+ assert(get_nodes_Block(get_Proj_pred(res)));
+
res = optimize (res);
- ir_vrfy (res);
+
+ irn_vrfy (res);
return res;
}
ir_node *res;
res = new_ir_node (irg, block, op_Conv, mode, 1, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
res = new_ir_node (irg, block, op_Tuple, mode_T, arity, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
ir_node *res;
res = new_ir_node (irg, block, op_Add, mode, 2, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
ir_node *res;
res = new_ir_node (irg, block, op_Sub, mode, 2, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
ir_node *res;
res = new_ir_node (irg, block, op_Minus, mode, 1, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
ir_node *res;
res = new_ir_node (irg, block, op_Mul, mode, 2, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
{
ir_node *in[3] = {memop, op1, op2};
ir_node *res;
- res = new_ir_node (irg, block, op_Quot, mode_T, 2, in);
+ res = new_ir_node (irg, block, op_Quot, mode_T, 3, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
{
ir_node *in[3] = {memop, op1, op2};
ir_node *res;
- res = new_ir_node (irg, block, op_DivMod, mode_T, 2, in);
+ res = new_ir_node (irg, block, op_DivMod, mode_T, 3, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
{
ir_node *in[3] = {memop, op1, op2};
ir_node *res;
- res = new_ir_node (irg, block, op_Div, mode_T, 2, in);
+ res = new_ir_node (irg, block, op_Div, mode_T, 3, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
{
ir_node *in[3] = {memop, op1, op2};
ir_node *res;
- res = new_ir_node (irg, block, op_Mod, mode_T, 2, in);
+ res = new_ir_node (irg, block, op_Mod, mode_T, 3, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
ir_node *res;
res = new_ir_node (irg, block, op_And, mode, 2, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
ir_node *res;
res = new_ir_node (irg, block, op_Or, mode, 2, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
ir_node *res;
res = new_ir_node (irg, block, op_Eor, mode, 2, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
ir_node *res;
res = new_ir_node (irg, block, op_Not, mode, 1, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
ir_node *res;
res = new_ir_node (irg, block, op_Shl, mode, 2, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
ir_node *res;
res = new_ir_node (irg, block, op_Shr, mode, 2, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
ir_node *res;
res = new_ir_node (irg, block, op_Shrs, mode, 2, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
ir_node *res;
res = new_ir_node (irg, block, op_Rot, mode, 2, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
ir_node *res;
res = new_ir_node (irg, block, op_Abs, mode, 1, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
ir_node *res;
res = new_ir_node (irg, block, op_Cmp, mode_T, 2, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
ir_node *res;
res = new_ir_node (irg, block, op_Jmp, mode_X, 0, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
ir_node *res;
res = new_ir_node (irg, block, op_Cond, mode_T, 1, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
set_Call_type(res, type);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
int r_arity;
r_arity = arity+1;
-
NEW_ARR_A (ir_node *, r_in, r_arity);
-
r_in[0] = store;
-
memcpy (&r_in[1], in, sizeof (ir_node *) * arity);
-
res = new_ir_node (irg, block, op_Return, mode_X, r_arity, r_in);
-
res = optimize (res);
-
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
res = new_ir_node (irg, block, op_Raise, mode_X, 2, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
res = new_ir_node (irg, block, op_Load, mode_T, 2, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
res = new_ir_node (irg, block, op_Store, mode_T, 3, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
res->attr.a.type = alloc_type;
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
res->attr.f = free_type;
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
res->attr.s.ent = ent;
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
res->attr.i.tori.typ = (type *)value;
}
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
res = new_ir_node (irg, block, op_Sync, mode_M, arity, in);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
-
ir_node *
-new_r_Bad (ir_node *block)
+new_r_Bad ()
{
return current_ir_graph->bad;
}
op_Start, mode_T, 0, NULL);
res = optimize (res);
- ir_vrfy (res);
+ irn_vrfy (res);
return res;
}
-
ir_node *
new_End (void)
{
op_End, mode_X, -1, NULL);
res = optimize (res);
- ir_vrfy (res);
- return res;
+ irn_vrfy (res);
+ return res;
}
ir_node *
res = new_ir_node (current_ir_graph, NULL, op_Block, mode_R, -1, NULL);
current_ir_graph->current_block = res;
res->attr.block.matured = 0;
- set_Block_block_visit(res, 0);
+ set_Block_block_visited(res, 0);
- // res = optimize (res); /* GL: only optimize if mature!!!! */
- ir_vrfy (res);
+ /* forget this optimization. use this only if mature !!!!
+ res = optimize (res); */
+ irn_vrfy (res);
/** create a new dynamic array, which stores all parameters in irnodes */
/** using the same obstack as the whole irgraph */
return res;
}
+inline ir_node *
+get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
+
+/** This function computes the predecessors for a real Phi node, and then
+ allocates and returns this node. The routine called to allocate the
+ node might optimize it away and return a real value, or even a pointer
+ to a deallocated Phi node on top of the obstack!
+ This function is called with an in-array of proper size. **/
+static inline ir_node *
+phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
+{
+ ir_node *prevBlock, *res;
+ int i;
+
+ /* This loop goes to all predecessor blocks of the block the Phi node is in
+ and there finds the operands of the Phi node by calling
+ get_r_value_internal. */
+ for (i = 1; i <= ins; ++i) {
+ assert (block->in[i]);
+ prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
+ assert (prevBlock);
+ nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
+ }
+
+ /* After collecting all predecessors into the array nin a new Phi node
+ with these predecessors is created. This constructor contains an
+ optimization: If all predecessors of the Phi node are identical it
+ returns the only operand instead of a new Phi node. If the value
+ passes two different control flow edges without being defined, and
+ this is the second path treated, a pointer to the node that will be
+ allocated for the first path (recurstion) is returned. We already
+ know the address of this node, as it is the next node to be allocated
+ and will be placed on top of the obstack. (The obstack is a _stack_!) */
+ res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
+
+ /* Now we now the value "pos" and can enter it in the array with
+ all known local variables. Attention: this might be a pointer to
+ a node, that later will be allocated!!! See new_r_Phi_in.
+ If this is called in mature, after some set_value in the same block,
+ the proper value must not be overwritten:
+ The call order
+ get_value (makes Phi0, put's it into graph_arr)
+ set_value (overwrites Phi0 in graph_arr)
+ mature_block (upgrades Phi0, puts it again into graph_arr, overwriting
+ the proper value.)
+ fails. */
+ if (!block->attr.block.graph_arr[pos]) {
+ block->attr.block.graph_arr[pos] = res;
+ } else {
+ // printf(" value already computed by %s\n",
+ // id_to_str(block->attr.block.graph_arr[pos]->op->name));
+ }
+
+ return res;
+}
+
+/* This function returns the last definition of a variable. In case
+ this variable was last defined in a previous block, Phi nodes are
+ inserted. If the part of the firm graph containing the definition
+ is not yet constructed, a dummy Phi node is returned. */
+inline ir_node *
+get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
+{
+ ir_node *res;
+ /* There are 4 cases to treat.
+
+ 1. The block is not mature and we visit it the first time. We can not
+ create a proper Phi node, therefore a Phi0, i.e., a Phi without
+ predecessors is returned. This node is added to the linked list (field
+ "link") of the containing block to be completed when this block is
+ matured. (Comlpletion will add a new Phi and turn the Phi0 into a Id
+ node.)
+
+ 2. The value is already known in this block, graph_arr[pos] is set and we
+ visit the block the first time. We can return the value without
+ creating any new nodes.
+
+ 3. The block is mature and we visit it the first time. A Phi node needs
+ to be created (phi_merge). If the Phi is not needed, as all it's
+ operands are the same value reaching the block through different
+ paths, it's optimizes away and the value itself is returned.
+
+ 4. The block is mature, and we visit it the second time. Now two
+ subcases are possible:
+ * The value was computed completely the last time we were here.
+ This is the case if there is no loop. We can return the proper value.
+ * The recursion that visited this node and set the flag did not
+ return yet. We are computing a value in a loop and need to
+ break the recursion without knowing the result yet.
+ There is no simple check for the second subcase. Therefore we check
+ for a second visit and treat all such cases as the second subcase.
+ Anyways, the basic situation is the same: we reached a block
+ on two paths without finding a definition of the value: No Phi
+ nodes are needed on both paths.
+ We return this information "Two paths, no Phi needed" by a very tricky
+ implementation that relies on the fact that an obstack is a stack and
+ will return a node with the same address on different allocations.
+ Look also at phi_merge and get_r_phi_in to understand this.
+ */
+
+ /* case 4 -- already visited. */
+ if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) return NULL;
+
+ /* visited the first time */
+ set_irn_visited(block, get_irg_visited(current_ir_graph));
+
+ /* Get the local valid value */
+ res = block->attr.block.graph_arr[pos];
+
+ /* case 2 -- If the value is actually computed, return it. */
+ if (res) { return res;};
+
+ if (block->attr.block.matured) { /* case 3 */
+
+ /* The Phi has the same amount of ins as the corresponding block. */
+ int ins = get_irn_arity(block);
+ ir_node **nin;
+ NEW_ARR_A (ir_node *, nin, ins);
+
+ /* Phi merge collects the predecessors and then creates a node. */
+ res = phi_merge (block, pos, mode, nin, ins);
+
+ } else { /* case 1 */
+ /* The block is not mature, we don't know how many in's are needed. A Phi
+ with zero predecessors is created. Such a Phi node is called Phi0
+ node. (There is also an obsolete Phi0 opcode.) The Phi0 is then added
+ to the list of Phi0 nodes in this block to be matured by mature_block
+ later.
+ The Phi0 has to remember the pos of it's internal value. If the real
+ Phi is computed, pos is used to update the array with the local
+ values. */
+
+ res = new_r_Phi0 (current_ir_graph, block, mode);
+ res->attr.phi0_pos = pos;
+ res->link = block->link;
+ block->link = res;
+ }
+
+ /* If we get here, the frontend missed a use-before-definition error */
+ if (!res) {
+ /* Error Message */
+ printf("Error: no value set\n");
+ assert (mode->code >= irm_f && mode->code <= irm_p);
+ res = new_r_Const (current_ir_graph, block, mode,
+ tarval_mode_null[mode->code]);
+ }
+
+ /* The local valid value is available now. */
+ block->attr.block.graph_arr[pos] = res;
+
+ return res;
+}
+
+/** Finalize a Block node, when all control flows are known. */
+/** Acceptable parameters are only Block nodes. */
+void
+mature_block (ir_node *block)
+{
+
+ int ins;
+ ir_node *n, **nin;
+ ir_node *next;
+
+ assert (get_irn_opcode(block) == iro_Block);
+
+ if (!get_Block_matured(block)) {
+
+ /* turn the dynamic in-array into a static one. */
+ ins = ARR_LEN (block->in)-1;
+ NEW_ARR_A (ir_node *, nin, ins);
+
+ /* Traverse a chain of Phi nodes attached to this block and mature
+ these, too. **/
+ for (n = block->link; n; n=next) {
+ inc_irg_visited(current_ir_graph);
+ next = n->link;
+ exchange (n, phi_merge (block, n->attr.phi0_pos, n->mode, nin, ins));
+ }
+
+ block->attr.block.matured = 1;
+
+ block = optimize_in_place(block);
+ irn_vrfy(block);
+ }
+
+}
ir_node *
new_Phi (int arity, ir_node **in, ir_mode *mode)
store, callee, arity, in, type);
}
-/* make M parameter in call explicit:
-new_Return (ir_node* store, int arity, ir_node **in) */
ir_node *
new_Return (ir_node* store, int arity, ir_node **in)
{
return current_ir_graph->bad;
}
-#if 0
-/************************/
-/* ir block constructor */
+/*************************************************************************/
+/* Comfortable interface with automatic Phi node construction. */
+/* (Uses also constructors of ?? interface, except new_Block. */
+/* add an adge to a jmp node */
+void
+add_in_edge (ir_node *block, ir_node *jmp)
+{
+ if (block->attr.block.matured) {
+ printf("Error: Block already matured!\n");
+ }
+ else {
+ assert (jmp != NULL);
+ ARR_APP1 (ir_node *, block->in, jmp);
+ }
+}
+
+/* changing the current block */
+void
+switch_block (ir_node *target)
+{
+ current_ir_graph->current_block = target;
+}
-/* GL: what's this good for? */
+/****************************/
+/* parameter administration */
-typedef struct ir_block {
- char closed;
- char matured;
- /* -1 = error, 0 = OK */
-} ir_block;
+/* get a value from the parameter array from the current block by its index */
+ir_node *
+get_value (int pos, ir_mode *mode)
+{
+ inc_irg_visited(current_ir_graph);
+ return get_r_value_internal (current_ir_graph->current_block, pos + 1, mode);
+}
-ir_block *
-new_ir_Block(void)
+/* set a value at position pos in the parameter array from the current block */
+inline void
+set_value (int pos, ir_node *value)
{
- ir_block *res;
+ current_ir_graph->current_block->attr.block.graph_arr[pos + 1] = value;
+}
- res->closed = -1;
- res->matured = -1;
+/* get the current store */
+inline ir_node *
+get_store (void)
+{
+ /* GL: one could call get_value instead */
+ inc_irg_visited(current_ir_graph);
+ return get_r_value_internal (current_ir_graph->current_block, 0, mode_M);
+}
- return res;
+/* set the current store */
+inline void
+set_store (ir_node *store)
+{
+ /* GL: one could call set_value instead */
+ current_ir_graph->current_block->attr.block.graph_arr[0] = store;
}
-#endif
+/*************************************************************************/
/* initialize */
/* call once for each run of the library */
projects / libfirm / blobdiff