X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Fircons.c;h=5b8e16f06881834eb4011df54ecb84ebc4634e6b;hb=5f8ddee6b08c8040c0a304a347d65045c1141d52;hp=4d075708d39b0ab77fe229edfac785cc478b2350;hpb=e11e9811dbd6dd71d1aa93fd7de821ed422b6393;p=libfirm diff --git a/ir/ir/ircons.c b/ir/ir/ircons.c index 4d075708d..5b8e16f06 100644 --- a/ir/ir/ircons.c +++ b/ir/ir/ircons.c @@ -4,219 +4,89 @@ ** Authors: Martin Trapp, Christian Schaefer ** ** ircons.c: basic and more detailed irnode constructors -** store, block and parameter administration , +** store, block and parameter administration. ** Adapted to extended FIRM nodes (exceptions...) and commented ** by Goetz Lindenmaier */ +# include "irgraph_t.h" +# include "irnode_t.h" +# include "irmode_t.h" # 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" -/* 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) -{ - ir_node *res; - int node_size = offsetof (ir_node, attr) + op->attr_size; - - res = (ir_node *) obstack_alloc (irg->obst, node_size); - - 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; - return res; -} - - - +#if USE_EXPICIT_PHI_IN_STACK +/* A stack needed for the automatic Phi node construction in constructor + Phi_in. Redefinition in irgraph.c!! */ +struct Phi_in_stack { + ir_node **stack; + int pos; +}; +typedef struct Phi_in_stack Phi_in_stack; +#endif /*********************************************** */ /** privat interfaces, for professional use only */ -/* Creates a Phi node with 0 predecessors */ +/* Constructs a Block with a fixed number of predecessors. + Does not set current_block. Can not be used with automatic + Phi node construction. */ inline ir_node * -new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode) +new_r_Block (ir_graph *irg, int arity, ir_node **in) { ir_node *res; - res = new_ir_node (irg, block, op_Phi, mode, 0, NULL); + res = new_ir_node (irg, NULL, op_Block, mode_R, arity, in); + set_Block_matured(res, 1); + set_Block_block_visited(res, 0); - /* GL I'm not sure whether we should optimize this guy. * - res = optimize (res); ??? */ - ir_vrfy (res); + irn_vrfy (res); return res; } -/* Creates a Phi node with all predecessors. Calling this constructor - is only allowed if the corresponding block is mature. */ ir_node * -new_r_Phi (ir_graph *irg, ir_node *block, int arity, ir_node **in, ir_mode *mode) +new_r_Start (ir_graph *irg, ir_node *block) { ir_node *res; - assert( get_Block_matured(block) ); - assert( get_irn_arity(block) == arity ); - - res = new_ir_node (irg, block, op_Phi, mode, arity, in); - - res = optimize (res); - ir_vrfy (res); - return res; -} - -/* This is a stack used for allocating and deallocating nodes in - new_r_Phi_in. The original implementation used the obstack - to model this stack, now it is explicit. This reduces side effects. -*/ -#if USE_EXPICIT_PHI_IN_STACK -Phi_in_stack * -new_Phi_in_stack() { - Phi_in_stack *res; - - res = (Phi_in_stack *) malloc ( sizeof (Phi_in_stack)); - - res->stack = NEW_ARR_F (ir_node *, 1); - res->pos = 0; + res = new_ir_node (irg, block, op_Start, mode_T, 0, NULL); + irn_vrfy (res); return res; } - -void free_to_Phi_in_stack(ir_node *phi) { - assert(get_irn_opcode(phi) == iro_Phi); - - if (ARR_LEN(current_ir_graph->Phi_in_stack->stack) == - current_ir_graph->Phi_in_stack->pos) - ARR_APP1 (ir_node *, current_ir_graph->Phi_in_stack->stack, phi); - else - current_ir_graph->Phi_in_stack->stack[current_ir_graph->Phi_in_stack->pos] = phi; - - (current_ir_graph->Phi_in_stack->pos)++; -} - ir_node * -alloc_or_pop_from_Phi_in_stack(ir_graph *irg, ir_node *block, ir_mode *mode, - int arity, ir_node **in) { +new_r_End (ir_graph *irg, ir_node *block) +{ ir_node *res; - ir_node **stack = current_ir_graph->Phi_in_stack->stack; - int pos = current_ir_graph->Phi_in_stack->pos; + res = new_ir_node (irg, block, op_End, mode_X, -1, NULL); - if (pos == 0) { - /* We need to allocate a new node */ - res = new_ir_node (irg, block, op_Phi, mode, arity, in); - } else { - /* reuse the old node and initialize it again. */ - res = stack[pos-1]; - - assert (res->kind == k_ir_node); - assert (res->op == op_Phi); - res->mode = mode; - res->visit = 0; - res->link = NULL; - assert (arity >= 0); - /* ???!!! How to free the old in array?? */ - res->in = NEW_ARR_D (ir_node *, irg->obst, (arity+1)); - res->in[0] = block; - memcpy (&res->in[1], in, sizeof (ir_node *) * arity); - - (current_ir_graph->Phi_in_stack->pos)--; - } + irn_vrfy (res); return res; } -#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 - returned directly. This constructor is only intended for use in - the automatic Phi node generation triggered by get_value or mature. - The implementation is quite tricky and depends on the fact, that - the nodes are allocated on a stack: - The in array contains predecessors and NULLs. The NULLs appear, - if get_r_value_internal, that computed the predecessors, reached - the same block on two paths. In this case the same value reaches - this block on both paths, there is no definition in between. We need - not allocate a Phi where these path's merge, but we have to communicate - this fact to the caller. This happens by returning a pointer to the - node the caller _will_ allocate. (Yes, we predict the address. We can - do so because the nodes are allocated on the obstack.) The caller then - finds a pointer to itself and, when this routine is called again, - eliminates itself. - */ -inline ir_node * -new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode, - ir_node **in, int ins) +/* Creates a Phi node with all predecessors. Calling this constructor + is only allowed if the corresponding block is mature. */ +ir_node * +new_r_Phi (ir_graph *irg, ir_node *block, int arity, ir_node **in, ir_mode *mode) { - int i; - ir_node *res, *known; - - /* allocate a new node on the obstack. - This can return a node to which some of the pointers in the in-array - already point. - Attention: the constructor copies the in array, i.e., the later changes - to the array in this routine do not affect the constructed node! If - the in array contains NULLs, there will be missing predecessors in the - returned node. - Is this a possible internal state of the Phi node generation? */ -#if USE_EXPICIT_PHI_IN_STACK - res = known = alloc_or_pop_from_Phi_in_stack(irg, block, mode, ins, in); -#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 NULLs are replaced by the node itself to simplify the test in the - next loop. */ - for (i=0; i < ins; ++i) - if (in[i] == NULL) in[i] = res; - - /* This loop checks whether the Phi has more than one predecessor. - If so, it is a real Phi node and we break the loop. Else the - Phi node merges the same definition on several paths and therefore - is not needed. */ - for (i=0; i < ins; ++i) - { - if (in[i]==res || in[i]==known) continue; + ir_node *res; - if (known==res) - known = in[i]; - else - break; - } + assert( get_Block_matured(block) ); + assert( get_irn_arity(block) == arity ); - /* i==ins: there is at most one predecessor, we don't need a phi node. */ - if (i==ins) { -#if USE_EXPICIT_PHI_IN_STACK - free_to_Phi_in_stack(res); -#else - obstack_free (current_ir_graph->obst, res); -#endif - res = known; - } else { - res = optimize (res); - ir_vrfy (res); - } + res = new_ir_node (irg, block, op_Phi, mode, arity, in); - /* return the pointer to the Phi node. This node might be deallocated! */ + res = optimize (res); + irn_vrfy (res); return res; } @@ -227,7 +97,7 @@ new_r_Const (ir_graph *irg, ir_node *block, ir_mode *mode, tarval *con) 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); @@ -243,19 +113,26 @@ new_r_Id (ir_graph *irg, ir_node *block, ir_node *val, ir_mode *mode) 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; } @@ -267,7 +144,7 @@ new_r_Conv (ir_graph *irg, ir_node *block, ir_node *op, ir_mode *mode) 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; } @@ -279,7 +156,7 @@ new_r_Tuple (ir_graph *irg, ir_node *block, int arity, ir_node **in) res = new_ir_node (irg, block, op_Tuple, mode_T, arity, in); res = optimize (res); - ir_vrfy (res); + irn_vrfy (res); return res; } @@ -291,7 +168,7 @@ new_r_Add (ir_graph *irg, ir_node *block, 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; } @@ -303,7 +180,7 @@ new_r_Sub (ir_graph *irg, ir_node *block, 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; } @@ -315,7 +192,7 @@ new_r_Minus (ir_graph *irg, ir_node *block, 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; } @@ -327,7 +204,7 @@ new_r_Mul (ir_graph *irg, ir_node *block, 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; } @@ -337,9 +214,9 @@ new_r_Quot (ir_graph *irg, ir_node *block, { 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; } @@ -349,9 +226,9 @@ new_r_DivMod (ir_graph *irg, ir_node *block, { 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; } @@ -361,9 +238,9 @@ new_r_Div (ir_graph *irg, ir_node *block, { 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; } @@ -373,9 +250,9 @@ new_r_Mod (ir_graph *irg, ir_node *block, { 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; } @@ -387,7 +264,7 @@ new_r_And (ir_graph *irg, ir_node *block, 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; } @@ -399,7 +276,7 @@ new_r_Or (ir_graph *irg, ir_node *block, 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; } @@ -411,7 +288,7 @@ new_r_Eor (ir_graph *irg, ir_node *block, 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; } @@ -423,7 +300,7 @@ new_r_Not (ir_graph *irg, ir_node *block, 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; } @@ -435,7 +312,7 @@ new_r_Shl (ir_graph *irg, ir_node *block, 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; } @@ -447,7 +324,7 @@ new_r_Shr (ir_graph *irg, ir_node *block, 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; } @@ -459,7 +336,7 @@ new_r_Shrs (ir_graph *irg, ir_node *block, 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; } @@ -471,7 +348,7 @@ new_r_Rot (ir_graph *irg, ir_node *block, 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; } @@ -483,7 +360,7 @@ new_r_Abs (ir_graph *irg, ir_node *block, 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; } @@ -495,7 +372,7 @@ new_r_Cmp (ir_graph *irg, ir_node *block, 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; } @@ -506,7 +383,7 @@ new_r_Jmp (ir_graph *irg, ir_node *block) 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; } @@ -517,7 +394,7 @@ new_r_Cond (ir_graph *irg, ir_node *block, ir_node *c) 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; } @@ -539,7 +416,7 @@ new_r_Call (ir_graph *irg, ir_node *block, ir_node *store, set_Call_type(res, type); res = optimize (res); - ir_vrfy (res); + irn_vrfy (res); return res; } @@ -552,18 +429,12 @@ new_r_Return (ir_graph *irg, ir_node *block, 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; } @@ -575,7 +446,7 @@ new_r_Raise (ir_graph *irg, ir_node *block, ir_node *store, ir_node *obj) res = new_ir_node (irg, block, op_Raise, mode_X, 2, in); res = optimize (res); - ir_vrfy (res); + irn_vrfy (res); return res; } @@ -588,7 +459,7 @@ new_r_Load (ir_graph *irg, ir_node *block, res = new_ir_node (irg, block, op_Load, mode_T, 2, in); res = optimize (res); - ir_vrfy (res); + irn_vrfy (res); return res; } @@ -601,7 +472,7 @@ new_r_Store (ir_graph *irg, ir_node *block, res = new_ir_node (irg, block, op_Store, mode_T, 3, in); res = optimize (res); - ir_vrfy (res); + irn_vrfy (res); return res; } @@ -617,7 +488,7 @@ new_r_Alloc (ir_graph *irg, ir_node *block, ir_node *store, res->attr.a.type = alloc_type; res = optimize (res); - ir_vrfy (res); + irn_vrfy (res); return res; } @@ -632,7 +503,7 @@ new_r_Free (ir_graph *irg, ir_node *block, ir_node *store, res->attr.f = free_type; res = optimize (res); - ir_vrfy (res); + irn_vrfy (res); return res; } @@ -655,17 +526,22 @@ new_r_Sel (ir_graph *irg, ir_node *block, ir_node *store, ir_node *objptr, res->attr.s.ent = ent; res = optimize (res); - ir_vrfy (res); + irn_vrfy (res); return res; } inline ir_node * -new_r_SymConst (ir_graph *irg, ir_node *block, type_or_id *value, +new_r_SymConst (ir_graph *irg, ir_node *block, type_or_id_p value, symconst_kind symkind) { ir_node *in[0] = {}; ir_node *res; - res = new_ir_node (irg, block, op_SymConst, mode_I, 0, in); + ir_mode *mode; + if (symkind == linkage_ptr_info) + mode = mode_p; + else + mode = mode_I; + res = new_ir_node (irg, block, op_SymConst, mode, 0, in); res->attr.i.num = symkind; if (symkind == linkage_ptr_info) { @@ -677,7 +553,7 @@ new_r_SymConst (ir_graph *irg, ir_node *block, type_or_id *value, res->attr.i.tori.typ = (type *)value; } res = optimize (res); - ir_vrfy (res); + irn_vrfy (res); return res; } @@ -689,13 +565,12 @@ new_r_Sync (ir_graph *irg, ir_node *block, int arity, ir_node **in) 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; } @@ -713,11 +588,10 @@ new_Start (void) op_Start, mode_T, 0, NULL); res = optimize (res); - ir_vrfy (res); + irn_vrfy (res); return res; } - ir_node * new_End (void) { @@ -727,35 +601,643 @@ new_End (void) op_End, mode_X, -1, NULL); res = optimize (res); - ir_vrfy (res); - return res; + irn_vrfy (res); + return res; } +#if 1 +/* Constructs a Block with a fixed number of predecessors. + Does set current_block. Can be used with automatic Phi + node construction. */ ir_node * -new_Block (void) +new_Block (int arity, ir_node **in) { ir_node *res; - res = new_ir_node (current_ir_graph, NULL, op_Block, mode_R, -1, NULL); + res = new_r_Block (current_ir_graph, arity, in); current_ir_graph->current_block = res; - res->attr.block.matured = 0; - set_Block_block_visit(res, 0); - // res = optimize (res); /* GL: only optimize if mature!!!! */ - ir_vrfy (res); - - /** create a new dynamic array, which stores all parameters in irnodes */ - /** using the same obstack as the whole irgraph */ + /* Create and initialize array for Phi-node construction. */ res->attr.block.graph_arr = NEW_ARR_D (ir_node *, current_ir_graph->obst, - current_ir_graph->params); + current_ir_graph->n_loc); + memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->n_loc); - /** initialize the parameter array */ - memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->params); + res = optimize (res); + irn_vrfy (res); return res; } +#else +ir_node * +new_Block (void) +{ + return new_immBlock(); +} +#endif +/*************************************************************************/ +/* Methods necessary for automatic Phi node creation */ +/* + ir_node *phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins) + ir_node *get_r_value_internal (ir_node *block, int pos, ir_mode *mode); + ir_node *new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode) + ir_node *new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode, ir_node **in, int ins) + + Call Graph: ( A ---> B == A "calls" B) + + get_value mature_block + | | + | | + | | + | ---> phi_merge + | / / \ + | / / \ + \|/ / |/_ \ + get_r_value_internal | + | | + | | + \|/ \|/ + new_r_Phi0 new_r_Phi_in + +*****************************************************************************/ + +/* Creates a Phi node with 0 predecessors */ +inline ir_node * +new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode) +{ + ir_node *res; + res = new_ir_node (irg, block, op_Phi, mode, 0, NULL); + irn_vrfy (res); + return res; +} + +/* There are two implementations of the Phi node construction. The first + is faster, but does not work for blocks with more than 2 predecessors. + The second works always but is slower and causes more unnecessary Phi + nodes. + Select the implementations by the following preprocessor flag set in + common/common.h: */ +#if USE_FAST_PHI_CONSTRUCTION + +/* This is a stack used for allocating and deallocating nodes in + new_r_Phi_in. The original implementation used the obstack + to model this stack, now it is explicit. This reduces side effects. +*/ +#if USE_EXPICIT_PHI_IN_STACK +Phi_in_stack * +new_Phi_in_stack() { + Phi_in_stack *res; + + res = (Phi_in_stack *) malloc ( sizeof (Phi_in_stack)); + + res->stack = NEW_ARR_F (ir_node *, 1); + res->pos = 0; + + return res; +} + +void free_to_Phi_in_stack(ir_node *phi) { + assert(get_irn_opcode(phi) == iro_Phi); + + if (ARR_LEN(current_ir_graph->Phi_in_stack->stack) == + current_ir_graph->Phi_in_stack->pos) + ARR_APP1 (ir_node *, current_ir_graph->Phi_in_stack->stack, phi); + else + current_ir_graph->Phi_in_stack->stack[current_ir_graph->Phi_in_stack->pos] = phi; + + (current_ir_graph->Phi_in_stack->pos)++; +} + +ir_node * +alloc_or_pop_from_Phi_in_stack(ir_graph *irg, ir_node *block, ir_mode *mode, + int arity, ir_node **in) { + ir_node *res; + ir_node **stack = current_ir_graph->Phi_in_stack->stack; + int pos = current_ir_graph->Phi_in_stack->pos; + + + if (pos == 0) { + /* We need to allocate a new node */ + res = new_ir_node (irg, block, op_Phi, mode, arity, in); + } else { + /* reuse the old node and initialize it again. */ + res = stack[pos-1]; + + assert (res->kind == k_ir_node); + assert (res->op == op_Phi); + res->mode = mode; + res->visited = 0; + res->link = NULL; + assert (arity >= 0); + /* ???!!! How to free the old in array?? */ + res->in = NEW_ARR_D (ir_node *, irg->obst, (arity+1)); + res->in[0] = block; + memcpy (&res->in[1], in, sizeof (ir_node *) * arity); + + (current_ir_graph->Phi_in_stack->pos)--; + } + return res; +} +#endif /* USE_EXPICIT_PHI_IN_STACK */ + +/* 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 + returned directly. This constructor is only intended for use in + the automatic Phi node generation triggered by get_value or mature. + The implementation is quite tricky and depends on the fact, that + the nodes are allocated on a stack: + The in array contains predecessors and NULLs. The NULLs appear, + if get_r_value_internal, that computed the predecessors, reached + the same block on two paths. In this case the same value reaches + this block on both paths, there is no definition in between. We need + not allocate a Phi where these path's merge, but we have to communicate + this fact to the caller. This happens by returning a pointer to the + node the caller _will_ allocate. (Yes, we predict the address. We can + do so because the nodes are allocated on the obstack.) The caller then + finds a pointer to itself and, when this routine is called again, + eliminates itself. + */ +inline ir_node * +new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode, + ir_node **in, int ins) +{ + int i; + ir_node *res, *known; + + /* allocate a new node on the obstack. + This can return a node to which some of the pointers in the in-array + already point. + Attention: the constructor copies the in array, i.e., the later changes + to the array in this routine do not affect the constructed node! If + the in array contains NULLs, there will be missing predecessors in the + returned node. + Is this a possible internal state of the Phi node generation? */ +#if USE_EXPICIT_PHI_IN_STACK + res = known = alloc_or_pop_from_Phi_in_stack(irg, block, mode, ins, in); +#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 NULLs are replaced by the node itself to simplify the test in the + next loop. */ + for (i=0; i < ins; ++i) + if (in[i] == NULL) in[i] = res; + + /* This loop checks whether the Phi has more than one predecessor. + If so, it is a real Phi node and we break the loop. Else the + Phi node merges the same definition on several paths and therefore + is not needed. */ + for (i=0; i < ins; ++i) + { + if (in[i]==res || in[i]==known) continue; + + if (known==res) + known = in[i]; + else + break; + } + + /* i==ins: there is at most one predecessor, we don't need a phi node. */ + if (i==ins) { +#if USE_EXPICIT_PHI_IN_STACK + free_to_Phi_in_stack(res); +#else + obstack_free (current_ir_graph->obst, res); +#endif + res = known; + } else { + res = optimize (res); + irn_vrfy (res); + } + + /* return the pointer to the Phi node. This node might be deallocated! */ + 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 (recursion) 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 for "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 an 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 optimized 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. + @@@ strange case. Straight forward we would create a Phi before + starting the computation of it's predecessors. In this case we will find + a Phi here in any case. The problem is that this implementation only + creates a Phi after computing the predecessors, so that it is hard to + compute self references of this Phi. @@@ + 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 new_r_phi_in to understand this. + @@@ Unfortunately this does not work, see testprogram three_cfpred_example. + + */ + + /* 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. Use of undefined variable. Initializing + to zero.\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; +} + +#else /* if 0 */ + +/** This is the simple algorithm. If first generates a Phi0, then + it starts the recursion. This causes an Id at the entry of + every block that has no definition of the value! **/ + +#if USE_EXPICIT_PHI_IN_STACK +/* Just a dummy */ +Phi_in_stack * new_Phi_in_stack() { return NULL; } +#endif + +inline ir_node * +new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode, + ir_node **in, int ins) +{ + int i; + ir_node *res, *known; + + /* Allocate a new node on the obstack. The allocation copies the in + array. */ + res = new_ir_node (irg, block, op_Phi, mode, ins, in); + + /* This loop checks whether the Phi has more than one predecessor. + If so, it is a real Phi node and we break the loop. Else the + Phi node merges the same definition on several paths and therefore + is not needed. Don't consider Bad nodes! */ + known = res; + for (i=0; i < ins; ++i) + { + if (in[i]==res || in[i]==known || is_Bad(in[i])) continue; + + if (known==res) + known = in[i]; + else + break; + } + + /* i==ins: there is at most one predecessor, we don't need a phi node. */ + if (i==ins) { + if (res != known) { + obstack_free (current_ir_graph->obst, res); + res = known; + } else { + /* A undefined value, e.g., in unreachable code. */ + res = new_Bad(); + } + } else { + res = optimize (res); + irn_vrfy (res); + } + + return res; +} + +inline ir_node * +get_r_value_internal (ir_node *block, int pos, ir_mode *mode); + +/** This function allocates a dummy Phi node to break recursions, + computes the predecessors for the 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. + 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, *phi0; + int i; + + + /* If this block has no value at pos create a Phi0 and remember it + in graph_arr to break recursions. */ + phi0 = NULL; + if (!block->attr.block.graph_arr[pos]) { + /* Even if all variables are defined before use, it can happen that + we get to the start block, if a cond has been replaced by a tuple + (bad, jmp). As the start has a self referencing control flow edge, + we get a self referencing Id, which is hard to optimize away. We avoid + this by defining the value as a Bad node. * + if (block == get_irg_start_block(current_ir_graph)) { + block->attr.block.graph_arr[pos] = new_Bad(); + return new_Bad(); + } else */ { + phi0 = new_r_Phi0(current_ir_graph, block, mode); + block->attr.block.graph_arr[pos] = phi0; + } + } + + /* 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]); + if (is_Bad(block->in[i])) { + /* In case a Cond has been optimized we would get right to the start block + with an invalid definition. */ + nin[i-1] = new_Bad(); + continue; + } + prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */ + assert (prevBlock); + if (!is_Bad(prevBlock)) { + nin[i-1] = get_r_value_internal (prevBlock, pos, mode); + } else { + nin[i-1] = new_Bad(); + } + } + + /* 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. */ + res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins); + + /* In case we allocated a Phi0 node at the beginning of this procedure, + we need to exchange this Phi0 with the real Phi. */ + if (phi0) { + exchange(phi0, res); + block->attr.block.graph_arr[pos] = res; + } + + 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 an 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 optimized 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. This case only happens if we visited + the same block with phi_merge before, which inserted a Phi0. + So we return the Phi0. + */ + + /* case 4 -- already visited. */ + if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) { + /* As phi_merge allocates a Phi0 this value is always defined. Here + is the critical difference of the two algorithms. */ + assert(block->attr.block.graph_arr[pos]); + return block->attr.block.graph_arr[pos]; + } + + /* 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. 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. Use of undefined variable. Initializing + to zero.\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; +} + +#endif /* USE_FAST_PHI_CONSTRUCTION */ + +/****************************************************************************/ + +/** 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; + + /* Now, as the block is a finished firm node, we can optimize it. + Since other nodes have been allocated since the block was created + we can not free the node on the obstack. Therefore we have to call + optimize_in_place. + Unfortunately the optimization does not change a lot, as all allocated + nodes refer to the unoptimized node. */ + block = optimize_in_place(block); + irn_vrfy(block); + } +} ir_node * new_Phi (int arity, ir_node **in, ir_mode *mode) @@ -946,8 +1428,6 @@ new_Call (ir_node *store, ir_node *callee, int arity, ir_node **in, 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) { @@ -1008,7 +1488,7 @@ new_Sel (ir_node *store, ir_node *objptr, int n_index, ir_node **index, entity * } ir_node * -new_SymConst (type_or_id *value, symconst_kind kind) +new_SymConst (type_or_id_p value, symconst_kind kind) { return new_r_SymConst (current_ir_graph, current_ir_graph->current_block, value, kind); @@ -1028,30 +1508,89 @@ new_Bad (void) 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. */ +/*************************************************************************/ -/* GL: what's this good for? */ +/** Block construction **/ +/* immature Block without predecessors */ +ir_node *new_immBlock (void) { + ir_node *res; -typedef struct ir_block { - char closed; - char matured; - /* -1 = error, 0 = OK */ -} ir_block; + /* creates a new dynamic in-array as length of in is -1 */ + 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_visited(res, 0); -ir_block * -new_ir_Block(void) -{ - ir_block *res; + /* Create and initialize array for Phi-node construction. */ + res->attr.block.graph_arr = NEW_ARR_D (ir_node *, current_ir_graph->obst, + current_ir_graph->n_loc); + memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->n_loc); - res->closed = -1; - res->matured = -1; + /* Immature block may not be optimized! */ + irn_vrfy (res); return res; } -#endif +/* add an adge to a jmp/control flow 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; +} + +/****************************/ +/* parameter administration */ + +/* 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); +} + +/* set a value at position pos in the parameter array from the current block */ +inline void +set_value (int pos, ir_node *value) +{ + current_ir_graph->current_block->attr.block.graph_arr[pos + 1] = value; +} + +/* 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); +} + +/* 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; +} + +/*************************************************************************/ /* initialize */ /* call once for each run of the library */