2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Loop peeling and unrolling
23 * @author Christian Helmer
34 #include "irgraph_t.h"
35 //#include "irprog_t.h"
37 //#include "iroptimize.h"
44 //#include "array_t.h"
49 //#include "xmalloc.h"
54 #include "irbackedge_t.h"
55 //#include "opt_inline_t.h"
60 //#include "analyze_irg_args.h"
61 #include "iredges_t.h"
62 //#include "irflag_t.h"
63 //#include "irhooks.h"
65 //#include "iropt_dbg.h"
73 /* convenience macro iterating over every phi node of the block */
74 #define for_each_phi(block, phi) \
75 for ( (phi) = get_Block_phis( (block) ); (phi) ; (phi) = get_Phi_next( (phi) ) )
79 /* The loop walker should be possible to abort if nothing can be done anymore */
80 typedef unsigned irg_walk_func_abortable(ir_node *, void *);
82 /* stores pair of node and number for nodes predecessor */
83 typedef struct loop_entry_t {
84 ir_node *node; /* node outside of the loop */
85 int pred_irn_n; /* with pred_irn_n pointing inside loop */
88 /* Store complex values in the nodes link */
89 //TODO optimize. Every node has these values and seldom many otm are used.
90 typedef struct link_node_state_t {
95 ir_node *ssalink; /* we will have to keep the link to the copies, as well as have temporary links for ssa creation */
96 ir_node **ins; /* ins for phi nodes, during rewiring of blocks */
97 // TODO omit ins. can be replaced by new ins and newunknown ins for each
101 loop_entry_t *loop_entries; /* loop entries (from below) in the node graph */
102 loop_entry_t *backedges; /* backedges exclusively from the current loop */
103 loop_entry_t *alien_backedges; /* The head can be head of several loops. */
104 loop_entry_t *head_edges; /* The head can be head of several loops. */
106 ir_node *loop_cf_head = NULL; /* loop exit in the node graph */
107 unsigned loop_cf_head_valid = 1; /* a loop may/must have one head, otherwise invalid */
109 unsigned has_sto = 0; /* If we store inside the loop we might
110 * have disambiguation problems */
112 //void arrdump(ir_node **arr)
115 // for (i=0; i<ARR_LEN(arr); i++)
117 // printf("inarr: %ld is block %d \n", (arr[i]->node_nr), is_Block(arr[i]));
122 * Returns the state of the given node.
124 link_node_state_t *get_lstate(ir_node *n)
126 return ((link_node_state_t *)n->link);
130 * Returns the link inside of the nodes state which is pointing to its copy
131 * most of the time during loop peeling.
133 ir_node *get_copy_of(ir_node *n)
135 return ((link_node_state_t *)n->link)->link;
139 * Returns true if the node or block is in cur_loop.
141 unsigned is_in_loop(ir_node *node)
143 // if (is_Block(node)) {
144 // if (node->loop == cur_loop) {
145 // printf(" INLOOP %ld \n", node->node_nr);
147 // return (node->loop == cur_loop);
149 // if ( get_nodes_block(node)->loop == cur_loop ) {
150 // printf(" INLOOP %ld \n", node->node_nr);
152 // return ( get_nodes_block(node)->loop == cur_loop );
154 if (is_Block(node)) {
155 return (node->loop == cur_loop);
157 return ( get_nodes_block(node)->loop == cur_loop );
162 * Returns if the given be is an alien edge
164 unsigned is_alien_edge(ir_node *n, int i)
166 return( !is_in_loop( get_irn_n( n, i ) ) );
169 static void add_pred(ir_node* node, ir_node* x)
176 // printf("NONODE\n");
178 //printf("addpred %ld pred %ld \n", node->node_nr, x->node_nr);
180 // WHY limit it to blocks and phi?
181 //assert(is_Block(node) || is_Phi(node));
183 n = get_irn_arity(node);
184 NEW_ARR_A(ir_node*, ins, n + 1);
185 for (i = 0; i < n; i++)
186 ins[i] = get_irn_n(node, i);
188 set_irn_in(node, n + 1, ins);
191 void block_phi_walker(ir_node *n, void *env)
193 const ir_edge_t *edge;
200 /* generate phi list for every block */
201 n->attr.block.phis = NULL;
203 foreach_out_edge(n, edge) {
204 ir_node *src = get_edge_src_irn(edge);
207 //printf("%ld has phi %ld \n", block->node_nr, src->node_nr);
208 add_Block_phi(n, src);
214 * Calls func() for every block in the given loop.
216 void for_each_loop_block(ir_loop *loop, irg_walk_func *func, void *env)
219 elements = get_loop_n_elements(loop);
221 for(e=0; e<elements; e++)
223 loop_element elem = get_loop_element(loop, e);
224 if (is_ir_node(elem.kind) && is_Block(elem.node) )
226 //printf(" foreach LOOPBLOCK %ld \n", elem.node->node_nr);
227 func(elem.node, env);
233 * collects the blocks backedges and creates the phi list for every block
235 void collect_backedges(ir_node *block, void *env)
239 printf("LOOP BLOCK %ld\n", block->node_nr);
241 /* collect backedges */
242 if (has_backedges(block))
245 int arity = get_irn_arity(block);
247 for(i = 0; i < arity; ++i) {
248 ir_node *pred = get_irn_n(block, i);
254 ARR_APP1(loop_entry_t, head_edges, be);
256 if (is_backedge(block, i) )
258 if ( is_in_loop(pred) ) {
259 //printf("be: %ld --> %ld \n", block->node_nr, pred->node_nr);
260 ARR_APP1(loop_entry_t, backedges, be);
262 //printf("alien be: %ld --> %ld \n", block->node_nr, pred->node_nr);
263 ARR_APP1(loop_entry_t, alien_backedges, be);
267 // if ( !is_in_loop(pred) ) {
268 // ARR_APP1(loop_entry_t, head_edges, be);
276 * Walks through all loop nodes.
278 unsigned loop_walker_rec(ir_node *node,
279 irg_walk_func_abortable *pre,
280 irg_walk_func_abortable *post, void * env)
285 ir_graph *irg = current_ir_graph;
287 /* RETURN if we walked out of the loop*/
288 if (!is_in_loop(node))
293 unsigned stop = pre(node, env);
298 set_irn_visited(node, irg->visited);
300 if (node->op != op_Block) {
301 ir_node *pred = get_irn_n(node, -1);
302 if (pred->visited < irg->visited)
304 stop = loop_walker_rec(pred, pre, post, env);
310 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
311 ir_node *pred = get_irn_n(node, i);
312 if (pred->visited < irg->visited)
314 stop = loop_walker_rec(pred, pre, post, env);
321 return post(node, env);
326 * Walks through loop nodes.
327 * The entries of the loop (all edges pointing into the loop) have to be given.
329 unsigned loop_walker(loop_entry_t *entries,
330 irg_walk_func_abortable *pre, irg_walk_func_abortable *post, void * env)
335 for (i=0; !stop && i<ARR_LEN(entries); i++)
341 pred = get_irn_n( entry.node , entry.pred_irn_n);
343 stop = loop_walker_rec( pred, pre, post, env);
351 void find_loop_entries_walk(ir_node *node, void *env)
353 unsigned node_in_loop, pred_in_loop;
356 link_node_state_t *state = XMALLOCZ(link_node_state_t);
357 node->link = (void *)state;
360 arity = get_irn_arity(node);
361 for (i = 0; i < arity; i++) {
362 ir_node *pred = get_irn_n(node, i);
364 pred_in_loop = is_in_loop(pred);
365 node_in_loop = is_in_loop(node);
367 //Find the loops head/the blocks with cfpred outside of the loop
368 if (is_Block(node) && node_in_loop
369 && !pred_in_loop && loop_cf_head_valid)
371 ir_node *cfgpred = get_Block_cfgpred(node, i);
373 if ( !is_in_loop(cfgpred) )
375 //another head? We do not touch this.
376 if (loop_cf_head && loop_cf_head != node)
378 loop_cf_head_valid = 0;
387 if ( pred_in_loop && !node_in_loop )
389 /* we walked right into the loop. */
392 entry.pred_irn_n = i;
395 // printf("inloop: %ld --> inloop %ld (@ %d) \n",
396 // node->node_nr, pred->node_nr, i);
398 ARR_APP1(loop_entry_t, loop_entries, entry);
405 // * Finds invariant nodes and marks them as invariant.
408 //unsigned get_invariants(ir_node *node, void *env)
410 // unsigned invar = 1;
413 // if (is_Store(node))
416 // /* RETURN and abort walker */
420 // int arity = get_irn_arity(node);
422 // /* RETURN, no preds to visit */
423 // if (arity == 0) return 0;
425 // if (is_Load(node))
427 // assert(arity>=2 && "expected load to have edge nr 1 (address)");
429 // ir_node *pred = get_irn_n(node, 1);
430 // if (!is_in_loop(pred) /* Everything outside the loop is considered invariant */
431 // || is_Const(pred) /* This is not true, but we also want the quasi-invariants. */
432 // || is_SymConst(pred)
433 // || get_lstate(node)->invariant)
435 // //printf("## CONSTLOAD: %ld \n", node->node_nr);
436 // get_lstate(node)->invariant = 1;
439 // get_lstate(node)->invariant = 0;
446 // /* find loop variant preds */
447 // for(i = 0; i < arity; ++i)
449 // ir_node *pred = get_irn_n(node, i);
451 // if ( !(!is_in_loop(pred) /* outside loop is loop invariant */
452 // || is_Const(pred) /* constants */
453 // || is_SymConst(pred) /* SymConst, if no Store */
454 // || get_lstate(node)->invariant /* pred is marked as invariant */
462 // printf("const: %ld \n", node->node_nr);
463 // get_lstate(node)->invariant = 1;
465 // get_lstate(node)->invariant = 0;
468 //// if (!is_nodes_block_marked(pred)) {
469 //// //printf("pred outloop: %ld, pred %ld (const)\n", node->node_nr, pred->node_nr);
470 //// } else if (is_Const(pred) || is_SymConst(pred)) // || is_Phi(pred)) {
471 //// //printf("predconst: %ld, pred %ld CONST\n", node->node_nr, pred->node_nr);
472 //// } else if (pred->link == MARKED_CONST) {
473 //// //printf("predmarked: %ld, pred %ld const\n", node->node_nr, pred->node_nr);
482 void phifix(ir_node *node, ir_node *newpred)
484 ir_node *phi=get_Block_phis(node);
487 int pa = get_irn_arity(phi);
488 int ba = get_irn_arity(node);
494 printf("!!!!!!!!!! block has %d, phi had %d\n", ba, pa );
495 add_pred(phi, newpred);
497 printf("!!!!!!!!!! block has %d, phi has now %d\n", ba, pa );
499 phi=get_Phi_next(phi);
503 static ir_node *ssa_second_def;
504 static ir_node *ssa_second_def_block;
506 static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode,
515 /* This is needed because we create bads sometimes */
519 /* the other defs can't be marked for cases where a user of the original
520 * value is in the same block as the alternative definition.
521 * In this case we mustn't use the alternative definition.
522 * So we keep a flag that indicated wether we walked at least 1 block
523 * away and may use the alternative definition */
524 if (block == ssa_second_def_block && !first) {
525 return ssa_second_def;
528 /* already processed this block? */
529 if (irn_visited(block)) {
530 ir_node *value = get_lstate(block)->ssalink;
534 irg = get_irn_irg(block);
535 assert(block != get_irg_start_block(irg));
537 /* a Block with only 1 predecessor needs no Phi */
538 n_cfgpreds = get_Block_n_cfgpreds(block);
539 if (n_cfgpreds == 1) {
540 ir_node *pred_block = get_Block_cfgpred_block(block, 0);
541 ir_node *value = search_def_and_create_phis(pred_block, mode, 0);
543 get_lstate(block)->ssalink = value;
544 //set_irn_link(block, value);
545 mark_irn_visited(block);
549 /* create a new Phi */
550 NEW_ARR_A(ir_node*, in, n_cfgpreds);
551 for(i = 0; i < n_cfgpreds; ++i)
552 in[i] = new_Unknown(mode);
554 phi = new_r_Phi(block, n_cfgpreds, in, mode);
555 //set_irn_link(block, phi);
556 get_lstate(block)->ssalink = phi;
557 mark_irn_visited(block);
559 /* set Phi predecessors */
560 for(i = 0; i < n_cfgpreds; ++i) {
561 ir_node *pred_block = get_Block_cfgpred_block(block, i);
562 ir_node *pred_val = search_def_and_create_phis(pred_block, mode, 0);
564 set_irn_n(phi, i, pred_val);
570 * Given a set of values this function constructs SSA-form for the users of the
571 * first value (the users are determined through the out-edges of the value).
572 * Uses the irn_visited flags. Works without using the dominance tree.
574 static void construct_ssa(ir_node *orig_block, ir_node *orig_val,
575 ir_node *second_block, ir_node *second_val)
579 const ir_edge_t *edge;
580 const ir_edge_t *next;
582 /* no need to do anything */
583 if (orig_val == second_val)
586 irg = get_irn_irg(orig_val);
587 inc_irg_visited(irg);
589 mode = get_irn_mode(orig_val);
590 get_lstate(orig_block)->ssalink = orig_val;
591 //set_irn_link(orig_block, orig_val);
592 mark_irn_visited(orig_block);
594 ssa_second_def_block = second_block;
595 ssa_second_def = second_val;
597 /* Only fix the users of the first, i.e. the original node */
598 foreach_out_edge_safe(orig_val, edge, next) {
599 ir_node *user = get_edge_src_irn(edge);
600 int j = get_edge_src_pos(edge);
601 ir_node *user_block = get_nodes_block(user);
608 //DB((dbg, LEVEL_3, ">>> Fixing user %+F (pred %d == %+F)\n", user, j, get_irn_n(user, j)));
611 ir_node *pred_block = get_Block_cfgpred_block(user_block, j);
612 newval = search_def_and_create_phis(pred_block, mode, 1);
614 newval = search_def_and_create_phis(user_block, mode, 1);
617 /* don't fix newly created Phis from the SSA construction */
618 if (newval != user) {
619 //DB((dbg, LEVEL_4, ">>>> Setting input %d of %+F to %+F\n", j, user, newval));
620 set_irn_n(user, j, newval);
628 * Rewires the heads after peeling
630 void fix_head(ir_node *loophead)
632 int headarity = get_irn_arity(loophead);
634 ir_node **loopheadnins;
635 ir_node **peelheadnins;
637 ir_node *peelhead = get_copy_of(loophead);
642 * the loopheads new preds are:
643 * its own backedge(s) and the former backedge(s) of the peeled code
645 int lhead_arity = 2 * ARR_LEN(backedges);
646 int phead_arity = headarity - ARR_LEN(backedges);
648 NEW_ARR_A(ir_node *, loopheadnins, lhead_arity );
649 NEW_ARR_A(ir_node *, peelheadnins, phead_arity );
651 phi = get_Block_phis(loophead);
653 NEW_ARR_A(ir_node *, get_lstate(phi)->ins, lhead_arity);
654 phi=get_Phi_next(phi);
657 phi = get_Block_phis(peelhead);
660 NEW_ARR_A(ir_node *, get_lstate(phi)->ins, phead_arity);
661 phi=get_Phi_next(phi);
664 for (i = 0; i < headarity; i++)
667 ir_node *orgjmp = get_irn_n(loophead, i);
668 ir_node *copyjmp = get_copy_of(orgjmp);
671 * Rewire the head blocks ins and their phi ins.
672 * Requires blocks phi list.
674 * 1. Alien bes origin from the peeled head (new head of the whole loop)
675 * 2. Loops own bes must be kept/copied to the loophead.
676 * 3. All other edges origin from the peeled head (new head of the loop)
680 //printf("head i %d\n", i);
682 if (is_backedge(loophead, i))
684 if (is_alien_edge(loophead, i)) {
685 peelheadnins[pheadin_c] = orgjmp; /* alien bes go to the peeled head */
686 //set_backedge(peelhead, pheadin_c);
688 // alien bes origin at the peeled head
689 for_each_phi(peelhead, phi)
691 //printf("alienbe phi %ld @ %d -> %ld\n", phi->node_nr, i, get_irn_n(phi, i)->node_nr);
692 get_lstate( phi )->ins[pheadin_c] = get_irn_n(phi, i);
694 //printf("alienbe %ld @ %d -> add to peelhead orgjump %ld\n", peelhead->node_nr, i, orgjmp->node_nr);
697 loopheadnins[lheadin_c] = orgjmp; /* keep/copy the loops own bes */
698 //set_backedge(loophead, lheadin_c);
700 for_each_phi(loophead, phi) {
701 //printf("normalbe phi %ld @ %d -> %ld\n", phi->node_nr, i, get_irn_n(phi, i)->node_nr);
702 get_lstate( phi )->ins[lheadin_c] = get_irn_n(phi, i);
704 //printf("normalbe %ld @ %d -> add to loophead orgjump %ld\n", loophead->node_nr, i, orgjmp->node_nr);
707 loopheadnins[lheadin_c] = copyjmp; /* former bes of the peeled code origin now from the loophead */
708 //set_not_backedge(loophead, lheadin_c);
710 /* get_irn_n( get_copy_of(phi), i) <!=> get_copy_of(get_irn_n( phi, i))
711 * Order is crucial! Preds outside of the loop are non existent, like Const.
713 for_each_phi(loophead, phi) {
714 //printf("normalbe phi %ld @ %d -> %ld\n", phi->node_nr, i, get_irn_n( get_copy_of(phi), i)->node_nr);
715 get_lstate( phi )->ins[lheadin_c] = get_irn_n( get_copy_of(phi), i) ;
717 //printf("normalbe %ld @ %d -> add to loophead copyjump %ld\n", loophead->node_nr, i, copyjmp->node_nr);
721 peelheadnins[pheadin_c] = orgjmp;
722 //set_not_backedge(peelhead, pheadin_c);
724 for_each_phi(peelhead, phi) {
725 //printf("edge phi %ld @ %d -> %ld\n", phi->node_nr, i, get_irn_n( phi, i)->node_nr);
726 get_lstate( phi )->ins[pheadin_c] = get_irn_n(phi, i);
728 //printf("edge %ld @ %d -> add to peelhead orgjump %ld\n", peelhead->node_nr, i, orgjmp->node_nr);
733 // printf("pheadin %d arr %d lheadin %d arr %d \n",
734 // pheadin_c, ARR_LEN(peelheadnins),
735 // lheadin_c, ARR_LEN(loopheadnins));
737 assert(pheadin_c == ARR_LEN(peelheadnins) &&
738 lheadin_c == ARR_LEN(loopheadnins) &&
739 "the number of head elements does not match the predefined one");
741 set_irn_in(loophead, ARR_LEN(loopheadnins), loopheadnins);
742 set_irn_in(peelhead, ARR_LEN(peelheadnins), peelheadnins);
744 for_each_phi(loophead, phi) {
745 ir_node **ins = get_lstate( phi )->ins;
746 set_irn_in(phi, lhead_arity, ins);
749 for_each_phi(peelhead, phi) {
750 ir_node **ins = get_lstate( phi )->ins;
751 set_irn_in(phi, phead_arity, ins);
757 * Peels the loop by copying the contents. Graph needs some rewiring after that.
759 void peel_walk(ir_node *node, void *env)
765 ir_graph *irg = current_ir_graph;
766 link_node_state_t *cpstate;
769 link_node_state_t *nodestate = get_lstate(node);
772 * break condition and cycle resolver, creating temporary node copies
774 if (node->visited >= irg->visited)
776 if (!nodestate->cloned && !nodestate->temp)
778 /** temporary clone this node
779 * because we were here before and would walk into a cycle
781 cp = exact_copy(node);
783 //printf("COPY TEMP : %ld -T> %ld \n", node->node_nr, cp->node_nr);
784 nodestate->link = cp;
787 cpstate = XMALLOCZ(link_node_state_t);
790 set_irn_visited(cp, irg->visited);
794 //printf(" ----- WALK %ld ----- \n", node->node_nr);
799 set_irn_visited(node, irg->visited);
801 if ( !is_Block(node) ) {
802 ir_node *pred = get_irn_n(node, -1);
803 if (is_in_loop(pred))
804 peel_walk(pred, NULL);
807 arity = get_irn_arity(node);
809 NEW_ARR_A(ir_node *, cpin, arity);
811 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
812 ir_node *pred = get_irn_n(node, i);
814 if (is_in_loop(pred))
816 peel_walk(pred, NULL);
817 cpin[i] = get_lstate(pred)->link;
818 //printf("copy of %ld gets in %ld", node->node_nr, cpin[i]->node_nr);
823 //printf("copy of %ld gets in %ld \n", node->node_nr, cpin[i]->node_nr);
827 * copy node / finalize temp node
829 if (!nodestate->temp)
831 // if (!is_Const(node) && !is_SymConst(node)) {
832 cp = exact_copy(node);
834 //printf("COPY FINAL: %ld -F> %ld \n", node->node_nr, cp->node_nr);
835 nodestate->link = cp;
836 cpstate = XMALLOCZ(link_node_state_t);
840 set_irn_visited(cp, irg->visited);
844 // printf("CONST FINAL: %ld -F> %ld \n", node->node_nr, cp->node_nr);
845 // nodestate->link = cp;
848 /* temporary copy is existent but without correct ins */
849 cp = nodestate->link;
850 //printf("FINALIZE: %ld \n", cp->node_nr);
854 //add_End_keepalive(get_irg_end(current_ir_graph), cp );
858 ir_node *cpblock = get_copy_of(get_nodes_block(node));
860 /* set the block of the copy to the copied block */
861 //printf(" PRE NODE %ld BLOCK %ld \n", cp->node_nr, get_nodes_block(cp)->node_nr);
862 set_nodes_block(cp, cpblock );
863 //printf(" POST NODE %ld BLOCK %ld \n", cp->node_nr, get_nodes_block(cp)->node_nr);
865 /* fix the phi information in attr.phis (does not add the phi node to the block) */
868 add_Block_phi(cpblock, cp);
869 //printf("PHI-BLOCK block %ld got its phi %ld\n", cpblock->node_nr, cp->node_nr);
873 /* macroblock info is not copied */
874 set_Block_MacroBlock(cp, cp);
878 // for(i=0; i<ARR_LEN(cpin); i++)
879 // printf(" cpin of %ld (cp %ld): %ld \n ", node->node_nr, cp->node_nr, cpin[i]->node_nr);
881 set_irn_in(cp, ARR_LEN(cpin), cpin);
883 // for(i=0; i< ARR_LEN(cpin); i++)
885 // printf("ins %ld: %ld \n", cp->node_nr, cpin[i]->node_nr);
889 // if (!nodestate->temp)
891 // nodestate->link = cp;
892 // cpstate = XMALLOCZ(link_node_state_t);
893 // cp->link = cpstate;
895 // /* temporary copy is existent but without correct ins */
896 // cp = nodestate->link;
901 nodestate->cloned = 1;
904 //void chklink (ir_node *n, void * e)
906 // ir_node *link = n->link;
907 // link_node_state_t *l = (link_node_state_t *)link;
909 // printf("n %ld\n", n->node_nr);
910 // printf("l p %ld\n", l->link);
912 // printf("l %ld\n", l->link->node_nr);
917 * Loop peeling, and fix the cf for the loop entry nodes, which have now more preds
922 ir_node **entry_buffer;
926 NEW_ARR_A(ir_node *, entry_buffer, ARR_LEN(loop_entries));
928 for(i = 0; i < ARR_LEN(loop_entries); i++)
930 loop_entry_t entry = loop_entries[i];
931 ir_node *node = entry.node;
932 ir_node *pred = get_irn_n(entry.node, entry.pred_irn_n);
934 if (is_Block(node)) {
935 /* node is block and the given pred points inside the loop */
940 // leave keepalives out
941 if (is_End(node) && (is_Block(pred) || is_Phi(pred)) ) {
942 //add_End_keepalive(get_irg_end(current_ir_graph), get_copy_of(pred) );
944 cppred = get_copy_of(pred);
945 //printf("fix block entry %ld to cp %ld\n", node->node_nr, cppred->node_nr);
946 add_pred( node, cppred );
947 //printf("fix block entry %ld to cp %ld\n", node->node_nr, cppred->node_nr);
950 //add_End_keepalive(get_irg_end(current_ir_graph), get_copy_of(pred) );
953 //phifix(node, cppred);
955 /* node is somewhere in the graph, outside of the loop */
961 // no ssa for keepalives
962 if (is_End(node) && (is_Block(pred) || is_Phi(pred)) ) {
963 //add_End_keepalive(get_irg_end(current_ir_graph), get_copy_of(pred) );
965 //printf("fix entry %ld to %ld\n", node->node_nr, pred->node_nr);
966 entry_buffer[entry_c++] = pred;
969 //add_End_keepalive(get_irg_end(current_ir_graph), get_copy_of(pred) );
971 // cannot construct_ssa here, because it needs another walker
976 //irg_walk_graph(current_ir_graph, chklink, NULL, NULL);
978 fix_head(loop_cf_head);
980 //printf (" FIXHEAD DONE :D \n");
984 /* Generate phis for values from peeled code and original loop */
985 for(i = 0; entry_i < entry_c; i++)
987 loop_entry_t entry = loop_entries[i];
988 ir_node *node = entry.node;
993 ir_node *phi=get_Block_phis(node);
997 add_pred(phi, entry_buffer[entry_i++]);
998 phi=get_Phi_next(phi);
1003 ir_node *cppred, *block, *cpblock, *pred;
1006 * pred = get_irn_n(entry.node, entry.pred_irn_n);
1007 * does not work, because we could have changed the nodes preds in construct_ssa
1010 pred = entry_buffer[entry_i++];
1012 //printf("pred %ld\n", pred->node_nr);
1013 cppred = get_copy_of(pred);
1014 //printf("cppred %ld\n", cppred->node_nr);
1015 block = get_nodes_block(pred);
1016 //printf("block %ld\n", block->node_nr);
1017 cpblock = get_nodes_block(cppred);
1018 //printf("cpblock %ld\n", cpblock->node_nr);
1021 //dump_ir_block_graph(current_ir_graph, "vorher");
1022 construct_ssa(block, pred, cpblock, cppred);
1023 //add_End_keepalive(get_irg_end(current_ir_graph), cppred);
1026 //add_pred(get_irg_end(current_ir_graph), cppred);
1027 //dump_ir_block_graph(current_ir_graph, "nachher");
1034 void decision_maker(void)
1036 //inc_irg_visited(current_ir_graph);
1037 //loop_walker( loop_entries, NULL, get_invariants, NULL );
1039 inc_irg_visited(current_ir_graph);
1046 * TODO use list , not arr_F
1048 void analyze_loop(ir_loop *loop)
1050 /* Init new for every loop */
1051 loop_cf_head = NULL;
1052 loop_cf_head_valid = 1;
1058 backedges = NEW_ARR_F(loop_entry_t, 0);
1059 alien_backedges = NEW_ARR_F(loop_entry_t, 0);
1060 loop_entries = NEW_ARR_F(loop_entry_t, 0);
1061 head_edges = NEW_ARR_F(loop_entry_t, 0);
1063 inc_irg_visited( current_ir_graph );
1064 irg_walk_graph( current_ir_graph, block_phi_walker, NULL, NULL );
1066 /* Collect all backedges */
1067 for_each_loop_block(loop, collect_backedges, NULL );
1069 /* Find loop entries walk, find head */
1070 inc_irg_visited( current_ir_graph );
1071 irg_walk_graph( current_ir_graph, find_loop_entries_walk, NULL, NULL );
1073 /* RETURN if there is no valid head */
1074 if (!loop_cf_head || !loop_cf_head_valid)
1076 //DBG printf("NOTE: There is no valid loop head. Nothing done.\n");
1082 // TODO free all link states... or better put them on functionstack
1085 DEL_ARR_F(loop_entries);
1086 DEL_ARR_F(backedges);
1087 DEL_ARR_F(alien_backedges);
1088 DEL_ARR_F(head_edges);
1090 //dump_ir_block_graph(current_ir_graph, "-lu1");
1094 * Find most inner loops and send them to analyze_loop
1096 void analyze_inner_loop(ir_loop *loop)
1098 /* descend into sons */
1099 int sons = get_loop_n_sons(loop);
1101 //printf("found %d loops \n", sons);
1105 //printf("analyze loop %ld\n", loop->loop_nr);
1111 for(s=0; s<sons; s++)
1113 //printf("descend into loop son %ld\n", get_loop_son(loop, s)->loop_nr);
1114 analyze_inner_loop( get_loop_son(loop, s) );
1122 //void phicheck(ir_node *node, void * env)
1124 // if (!is_Block(node)) return;
1126 // ir_node *phi=get_Block_phis(node);
1129 // if (!is_Phi(phi))
1131 // printf("NOT PHI %ld\n", phi->node_nr);
1134 // phi=get_Phi_next(phi);
1139 void loop_unroll(ir_graph *irg)
1141 //printf(" --- loop unroll start --- \n");
1143 //irg_walk_graph(irg, phicheck, NULL, NULL);
1147 assure_cf_loop(irg);
1149 loop = get_irg_loop(irg);
1150 int sons = get_loop_n_sons(loop);
1151 //printf("FOUND %d LOOPS \n", sons);
1153 for (nr=0; nr<sons; nr++)
1155 analyze_inner_loop( get_loop_son(loop, nr) );
1159 //printf(" --- loop unroll done --- \n");
1162 struct loop_unroll_pass_t {
1163 ir_graph_pass_t pass;
1167 * Wrapper to run ...() as a ir_prog pass.
1169 static int loop_unroll_wrapper(ir_graph *irg, void *context) {
1177 ir_graph_pass_t *loop_unroll_pass(const char *name)
1179 struct loop_unroll_pass_t *pass =
1180 XMALLOCZ(struct loop_unroll_pass_t);
1182 return def_graph_pass_constructor(
1183 &pass->pass, name ? name : "loop_unroll",
1184 loop_unroll_wrapper);
1188 void firm_init_loopunroll(void) {
1189 FIRM_DBG_REGISTER(dbg, "firm.opt.loopunroll");