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"
72 /* convenience macro for iterating over every phi node of the given block */
73 #define for_each_phi(block, phi) \
74 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 the 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 */
89 //loop_entry_t loop_entry_list;
91 /* Store complex values in the nodes link */
92 typedef struct link_node_state_t {
94 unsigned temp:1; /* < Node is temporarily copied, to resolve cycles */
97 ir_node *link; /*< temporary links for ssa creation */
98 ir_node **ins; /* ins for phi nodes, during rewiring of blocks */
102 loop_entry_t *loop_entries; /* loop entries (from below) in the node graph */
103 //int loop_entries_n;
104 loop_entry_t *head_entries; /* loop entries (from below) in the node graph */
106 //loop_entry_t *backedges; /* backedges exclusively from the current loop */
107 //loop_entry_t *alien_backedges; /* The head can be head of several loops. */
108 //loop_entry_t *head_edges; /* The head can be head of several loops. */
110 ir_node *loop_cf_head = NULL; /* loop exit in the node graph */
111 unsigned loop_cf_head_valid = 1; /* a loop may/must have one head, otherwise invalid */
113 unsigned has_sto; /* If we store inside the loop we might
114 * have disambiguation problems */
116 //void arrdump(ir_node **arr)
119 // for (i=0; i<ARR_LEN(arr); i++)
121 // printf("inarr: %ld is block %d \n", (arr[i]->node_nr), is_Block(arr[i]));
126 * Returns the state of the given node.
128 link_node_state_t *get_lstate(ir_node *n)
130 return ((link_node_state_t *)n->link);
134 * Returns the link inside of the nodes state which is pointing to its copy
135 * most of the time during loop peeling.
137 ir_node *get_copy(ir_node *n)
139 return ((link_node_state_t *)n->link)->copy;
143 * Sets the nodes copy information
145 void set_copy(ir_node *n, ir_node *copy)
147 ((link_node_state_t *)n->link)->copy = copy;
151 * Returns true if the node or block is in cur_loop.
153 unsigned is_in_loop(ir_node *node)
155 // if (is_Block(node)) {
156 // if (node->loop == cur_loop) {
157 // printf(" INLOOP %ld \n", node->node_nr);
159 // return (node->loop == cur_loop);
161 // if ( get_nodes_block(node)->loop == cur_loop ) {
162 // printf(" INLOOP %ld \n", node->node_nr);
164 // return ( get_nodes_block(node)->loop == cur_loop );
166 if (is_Block(node)) {
167 return (node->loop == cur_loop);
169 return ( get_nodes_block(node)->loop == cur_loop );
173 unsigned is_in_head(ir_node *node)
175 if (is_Block(node)) {
176 return (node == loop_cf_head);
178 return ( get_nodes_block(node) == loop_cf_head );
183 * Returns if the given be is an alien edge
185 unsigned is_alien_edge(ir_node *n, int i)
187 return( !is_in_loop( get_irn_n( n, i ) ) );
190 static void add_pred(ir_node* node, ir_node* x)
197 // printf("NONODE\n");
199 //printf("addpred %ld pred %ld \n", node->node_nr, x->node_nr);
201 // WHY limit it to blocks and phi?
202 assert(is_Block(node) || is_Phi(node));
204 n = get_irn_arity(node);
205 NEW_ARR_A(ir_node*, ins, n + 1);
206 for (i = 0; i < n; i++)
207 ins[i] = get_irn_n(node, i);
209 set_irn_in(node, n + 1, ins);
212 void block_phi_walker(ir_node *n, void *env)
214 const ir_edge_t *edge;
221 /* generate phi list for every block */
222 n->attr.block.phis = NULL;
224 foreach_out_edge(n, edge) {
225 ir_node *src = get_edge_src_irn(edge);
228 //printf("%ld has phi %ld \n", block->node_nr, src->node_nr);
229 add_Block_phi(n, src);
235 * Calls func() for every block in the given loop.
237 void for_each_loop_block(ir_loop *loop, irg_walk_func *func, void *env)
240 elements = get_loop_n_elements(loop);
242 for(e=0; e<elements; e++)
244 loop_element elem = get_loop_element(loop, e);
245 if (is_ir_node(elem.kind) && is_Block(elem.node) )
247 //printf(" foreach LOOPBLOCK %ld \n", elem.node->node_nr);
248 func(elem.node, env);
254 * collects the blocks backedges and creates the phi list for every block
256 void collect_backedges(ir_node *block, void *env)
260 //printf("LOOP BLOCK %ld\n", block->node_nr);
262 /* collect backedges */
263 if (has_backedges(block))
266 int arity = get_irn_arity(block);
268 for(i = 0; i < arity; ++i) {
269 ir_node *pred = get_irn_n(block, i);
275 //ARR_APP1(loop_entry_t, head_edges, be);
277 if (is_backedge(block, i) )
279 if ( is_in_loop(pred) ) {
280 //printf("be: %ld --> %ld \n", block->node_nr, pred->node_nr);
281 //ARR_APP1(loop_entry_t, backedges, be);
285 // //printf("alien be: %ld --> %ld \n", block->node_nr, pred->node_nr);
286 // ARR_APP1(loop_entry_t, alien_backedges, be);
290 // if ( !is_in_loop(pred) ) {
291 // ARR_APP1(loop_entry_t, head_edges, be);
299 * Walks through all loop nodes.
301 unsigned loop_walker_rec(ir_node *node,
302 irg_walk_func_abortable *pre,
303 irg_walk_func_abortable *post, void * env)
308 ir_graph *irg = current_ir_graph;
310 /* RETURN if we walked out of the loop*/
311 if (!is_in_loop(node))
316 unsigned stop = pre(node, env);
321 set_irn_visited(node, irg->visited);
323 if (node->op != op_Block) {
324 ir_node *pred = get_irn_n(node, -1);
325 if (pred->visited < irg->visited)
327 stop = loop_walker_rec(pred, pre, post, env);
333 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
334 ir_node *pred = get_irn_n(node, i);
335 if (pred->visited < irg->visited)
337 stop = loop_walker_rec(pred, pre, post, env);
344 return post(node, env);
349 * Walks through loop nodes.
350 * The entries of the loop (all edges pointing into the loop) have to be given.
352 unsigned loop_walker(loop_entry_t *entries,
353 irg_walk_func_abortable *pre, irg_walk_func_abortable *post, void * env)
358 for (i=0; !stop && i<ARR_LEN(entries); i++)
364 pred = get_irn_n( entry.node , entry.pred_irn_n);
366 stop = loop_walker_rec( pred, pre, post, env);
374 void find_loop_entries_walk(ir_node *node, void *env)
376 unsigned node_in_loop, pred_in_loop;
380 arity = get_irn_arity(node);
381 for (i = 0; i < arity; i++) {
382 ir_node *pred = get_irn_n(node, i);
384 pred_in_loop = is_in_loop(pred);
385 node_in_loop = is_in_loop(node);
387 //Find the loops head/the blocks with cfpred outside of the loop
388 if (is_Block(node) && node_in_loop
389 && !pred_in_loop && loop_cf_head_valid)
391 ir_node *cfgpred = get_Block_cfgpred(node, i);
393 if ( !is_in_loop(cfgpred) )
395 // another head? We do not touch this.
397 if (loop_cf_head && loop_cf_head != node)
399 loop_cf_head_valid = 0;
408 if ( pred_in_loop && !node_in_loop )
410 /* we walked right into the loop. */
413 entry.pred_irn_n = i;
416 // printf("inloop: %ld --> inloop %ld (@ %d) \n",
417 // node->node_nr, pred->node_nr, i);
419 ARR_APP1(loop_entry_t, loop_entries, entry);
425 // * Finds invariant nodes and marks them as invariant.
428 //unsigned get_invariants(ir_node *node, void *env)
430 // unsigned invar = 1;
433 // if (is_Store(node))
436 // /* RETURN and abort walker */
440 // int arity = get_irn_arity(node);
442 // /* RETURN, no preds to visit */
443 // if (arity == 0) return 0;
445 // if (is_Load(node))
447 // assert(arity>=2 && "expected load to have edge nr 1 (address)");
449 // ir_node *pred = get_irn_n(node, 1);
450 // if (!is_in_loop(pred) /* Everything outside the loop is considered invariant */
451 // || is_Const(pred) /* This is not true, but we also want the quasi-invariants. */
452 // || is_SymConst(pred)
453 // || get_lstate(node)->invariant)
455 // //printf("## CONSTLOAD: %ld \n", node->node_nr);
456 // get_lstate(node)->invariant = 1;
459 // get_lstate(node)->invariant = 0;
466 // /* find loop variant preds */
467 // for(i = 0; i < arity; ++i)
469 // ir_node *pred = get_irn_n(node, i);
471 // if ( !(!is_in_loop(pred) /* outside loop is loop invariant */
472 // || is_Const(pred) /* constants */
473 // || is_SymConst(pred) /* SymConst, if no Store */
474 // || get_lstate(node)->invariant /* pred is marked as invariant */
482 // printf("const: %ld \n", node->node_nr);
483 // get_lstate(node)->invariant = 1;
485 // get_lstate(node)->invariant = 0;
488 //// if (!is_nodes_block_marked(pred)) {
489 //// //printf("pred outloop: %ld, pred %ld (const)\n", node->node_nr, pred->node_nr);
490 //// } else if (is_Const(pred) || is_SymConst(pred)) // || is_Phi(pred)) {
491 //// //printf("predconst: %ld, pred %ld CONST\n", node->node_nr, pred->node_nr);
492 //// } else if (pred->link == MARKED_CONST) {
493 //// //printf("predmarked: %ld, pred %ld const\n", node->node_nr, pred->node_nr);
502 //void phifix(ir_node *node, ir_node *newpred)
504 // ir_node *phi=get_Block_phis(node);
507 // int pa = get_irn_arity(phi);
508 // int ba = get_irn_arity(node);
514 // printf("!!!!!!!!!! block has %d, phi had %d\n", ba, pa );
515 // add_pred(phi, newpred);
517 // printf("!!!!!!!!!! block has %d, phi has now %d\n", ba, pa );
519 // phi=get_Phi_next(phi);
523 static ir_node *ssa_second_def;
524 static ir_node *ssa_second_def_block;
529 static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode,
538 /* This is needed because we create bads sometimes */
542 /* the other defs can't be marked for cases where a user of the original
543 * value is in the same block as the alternative definition.
544 * In this case we mustn't use the alternative definition.
545 * So we keep a flag that indicated wether we walked at least 1 block
546 * away and may use the alternative definition */
547 if (block == ssa_second_def_block && !first) {
548 return ssa_second_def;
551 /* already processed this block? */
552 if (irn_visited(block)) {
553 ir_node *value = get_lstate(block)->link;
557 irg = get_irn_irg(block);
558 assert(block != get_irg_start_block(irg));
560 /* a Block with only 1 predecessor needs no Phi */
561 n_cfgpreds = get_Block_n_cfgpreds(block);
562 if (n_cfgpreds == 1) {
563 ir_node *pred_block = get_Block_cfgpred_block(block, 0);
564 ir_node *value = search_def_and_create_phis(pred_block, mode, 0);
566 get_lstate(block)->link = value;
567 //set_irn_link(block, value);
568 mark_irn_visited(block);
572 /* create a new Phi */
573 NEW_ARR_A(ir_node*, in, n_cfgpreds);
574 for(i = 0; i < n_cfgpreds; ++i)
575 in[i] = new_Unknown(mode);
577 phi = new_r_Phi(block, n_cfgpreds, in, mode);
578 //set_irn_link(block, phi);
579 get_lstate(block)->link = phi;
580 mark_irn_visited(block);
582 /* set Phi predecessors */
583 for(i = 0; i < n_cfgpreds; ++i) {
584 ir_node *pred_block = get_Block_cfgpred_block(block, i);
585 ir_node *pred_val = search_def_and_create_phis(pred_block, mode, 0);
587 set_irn_n(phi, i, pred_val);
593 * Given a set of values this function constructs SSA-form for the users of the
594 * first value (the users are determined through the out-edges of the value).
595 * Uses the irn_visited flags. Works without using the dominance tree.
597 static void construct_ssa(ir_node *orig_block, ir_node *orig_val,
598 ir_node *second_block, ir_node *second_val)
602 const ir_edge_t *edge;
603 const ir_edge_t *next;
605 /* no need to do anything */
606 if (orig_val == second_val)
609 irg = get_irn_irg(orig_val);
610 inc_irg_visited(irg);
612 mode = get_irn_mode(orig_val);
613 get_lstate(orig_block)->link = orig_val;
614 //set_irn_link(orig_block, orig_val);
615 mark_irn_visited(orig_block);
617 ssa_second_def_block = second_block;
618 ssa_second_def = second_val;
620 /* Only fix the users of the first, i.e. the original node */
621 foreach_out_edge_safe(orig_val, edge, next) {
622 ir_node *user = get_edge_src_irn(edge);
623 int j = get_edge_src_pos(edge);
624 ir_node *user_block = get_nodes_block(user);
631 //DB((dbg, LEVEL_3, ">>> Fixing user %+F (pred %d == %+F)\n", user, j, get_irn_n(user, j)));
634 ir_node *pred_block = get_Block_cfgpred_block(user_block, j);
635 newval = search_def_and_create_phis(pred_block, mode, 1);
637 newval = search_def_and_create_phis(user_block, mode, 1);
640 /* don't fix newly created Phis from the SSA construction */
641 if (newval != user) {
642 //DB((dbg, LEVEL_4, ">>>> Setting input %d of %+F to %+F\n", j, user, newval));
643 set_irn_n(user, j, newval);
651 * Rewires the heads after peeling. This results in a tail-controlled loop.
653 void fix_head(ir_node *loophead)
655 int headarity = get_irn_arity(loophead);
657 ir_node **loopheadnins;
658 ir_node **peelheadnins;
660 ir_node *peelhead = get_copy(loophead);
665 * the loopheads new preds are:
666 * its own backedge(s) and the former backedge(s) of the peeled code
668 int lhead_arity = 2 * backedges_n; //ARR_LEN(backedges);
669 int phead_arity = headarity - backedges_n; //ARR_LEN(backedges);
671 /** We assume the worst case, in which every head entry
672 * origins from the same node. +1 for a null terminated list.
674 //int tchead_arity = ARR_LEN(head_entries) + ( headarity - backedges_n) + 1 ;
676 NEW_ARR_A(ir_node *, loopheadnins, lhead_arity );
677 NEW_ARR_A(ir_node *, peelheadnins, phead_arity );
679 phi = get_Block_phis(loophead);
681 NEW_ARR_A(ir_node *, get_lstate(phi)->ins, lhead_arity);
682 phi=get_Phi_next(phi);
685 phi = get_Block_phis(peelhead);
688 NEW_ARR_A(ir_node *, get_lstate(phi)->ins, phead_arity);
689 phi=get_Phi_next(phi);
692 for (i = 0; i < headarity; i++)
695 ir_node *orgjmp = get_irn_n(loophead, i);
696 ir_node *copyjmp = get_copy(orgjmp);
699 * Rewire the head blocks ins and their phi ins.
700 * Requires blocks phi list.
702 * 1. Alien bes origin from the peeled head (new head of the whole loop)
703 * 2. Loops own bes must be kept/copied to the loophead.
704 * 3. All other edges origin from the peeled head (new head of the loop)
708 //printf("head i %d\n", i);
710 if (is_backedge(loophead, i))
712 if (is_alien_edge(loophead, i)) {
713 peelheadnins[pheadin_c] = orgjmp; /* alien bes go to the peeled head */
714 //set_backedge(peelhead, pheadin_c);
716 // alien bes origin at the peeled head
717 for_each_phi(peelhead, phi)
719 //printf("alienbe phi %ld @ %d -> %ld\n", phi->node_nr, i, get_irn_n(phi, i)->node_nr);
720 get_lstate( phi )->ins[pheadin_c] = get_irn_n(phi, i);
722 //printf("alienbe %ld @ %d -> add to peelhead orgjump %ld\n", peelhead->node_nr, i, orgjmp->node_nr);
725 loopheadnins[lheadin_c] = orgjmp; /* keep/copy the loops own bes */
726 //set_backedge(loophead, lheadin_c);
728 for_each_phi(loophead, phi) {
729 //printf("normalbe phi %ld @ %d -> %ld\n", phi->node_nr, i, get_irn_n(phi, i)->node_nr);
730 get_lstate( phi )->ins[lheadin_c] = get_irn_n(phi, i);
732 //printf("normalbe %ld @ %d -> add to loophead orgjump %ld\n", loophead->node_nr, i, orgjmp->node_nr);
735 loopheadnins[lheadin_c] = copyjmp; /* former bes of the peeled code origin now from the loophead */
736 //set_not_backedge(loophead, lheadin_c);
738 /* get_irn_n( get_copy_of(phi), i) <!=> get_copy_of(get_irn_n( phi, i))
739 * Order is crucial! Preds outside of the loop are non existent, like Const.
741 for_each_phi(loophead, phi) {
742 //printf("normalbe phi %ld @ %d -> %ld\n", phi->node_nr, i, get_irn_n( get_copy_of(phi), i)->node_nr);
743 get_lstate( phi )->ins[lheadin_c] = get_irn_n( get_copy(phi), i) ;
745 //printf("normalbe %ld @ %d -> add to loophead copyjump %ld\n", loophead->node_nr, i, copyjmp->node_nr);
749 peelheadnins[pheadin_c] = orgjmp;
750 //set_not_backedge(peelhead, pheadin_c);
752 for_each_phi(peelhead, phi) {
753 //printf("edge phi %ld @ %d -> %ld\n", phi->node_nr, i, get_irn_n( phi, i)->node_nr);
754 get_lstate( phi )->ins[pheadin_c] = get_irn_n(phi, i);
756 //printf("edge %ld @ %d -> add to peelhead orgjump %ld\n", peelhead->node_nr, i, orgjmp->node_nr);
761 // printf("pheadin %d arr %d lheadin %d arr %d \n",
762 // pheadin_c, ARR_LEN(peelheadnins),
763 // lheadin_c, ARR_LEN(loopheadnins));
765 assert(pheadin_c == ARR_LEN(peelheadnins) &&
766 lheadin_c == ARR_LEN(loopheadnins) &&
767 "the number of head elements does not match the predefined one");
769 set_irn_in(loophead, ARR_LEN(loopheadnins), loopheadnins);
770 set_irn_in(peelhead, ARR_LEN(peelheadnins), peelheadnins);
772 for_each_phi(loophead, phi) {
773 ir_node **ins = get_lstate( phi )->ins;
774 set_irn_in(phi, lhead_arity, ins);
777 for_each_phi(peelhead, phi) {
778 ir_node **ins = get_lstate( phi )->ins;
779 set_irn_in(phi, phead_arity, ins);
783 ir_node *rawcopy_node(ir_node *node)
786 link_node_state_t *cpstate;
788 cp = exact_copy(node);
790 cpstate = XMALLOCZ(link_node_state_t);
793 cp->loop = NULL; /* the copy does not belong to the loop */
794 set_irn_visited(cp, current_ir_graph->visited);
799 * Peels the loop by copying the contents. Graph needs some rewiring after that.
801 void peel_walk(ir_node *node)
807 ir_graph *irg = current_ir_graph;
811 link_node_state_t *nodestate = get_lstate(node);
814 * break condition and cycle resolver, creating temporary node copies
816 if (node->visited >= irg->visited)
818 if (!nodestate->cloned && !nodestate->temp)
820 /** temporary clone this node
821 * because we were here before and would walk into a cycle
828 //printf(" ----- WALK %ld ----- \n", node->node_nr);
833 set_irn_visited(node, irg->visited);
835 if ( !is_Block(node) ) {
836 ir_node *pred = get_irn_n(node, -1);
837 if (is_in_loop(pred))
841 arity = get_irn_arity(node);
843 NEW_ARR_A(ir_node *, cpin, arity);
846 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
847 ir_node *pred = get_irn_n(node, i);
849 /* collect head entries */
850 if ( is_in_head(pred) && !is_in_head(node) )
854 entry.pred_irn_n = i;
855 ARR_APP1(loop_entry_t, head_entries, entry);
858 if (is_in_loop(pred))
861 cpin[i] = get_copy(pred); //get_lstate(pred)->link;
862 //printf("copy of %ld gets in %ld", node->node_nr, cpin[i]->node_nr);
866 //printf("copy of %ld gets in %ld \n", node->node_nr, cpin[i]->node_nr);
870 * copy node / finalize temp node
872 if (!nodestate->temp) {
873 // if (!is_Const(node) && !is_SymConst(node)) {
874 cp = rawcopy_node(node);
878 // printf("CONST FINAL: %ld -F> %ld \n", node->node_nr, cp->node_nr);
879 // nodestate->link = cp;
882 /* temporary copy is existent but without correct ins */
883 cp = get_copy(node); // nodestate->link;
884 //printf("FINALIZE: %ld \n", cp->node_nr);
887 // special treatment for the head/condition: we need 3 heads for a tail-controlled and peeled loop
888 if (is_in_head(node)) {
889 // head/condition for the tail-controlled loop
890 // These copies are linked to the copies
896 ir_node *cpblock = get_copy(get_nodes_block(node));
898 /* set the block of the copy to the copied block */
899 //printf(" PRE NODE %ld BLOCK %ld \n", cp->node_nr, get_nodes_block(cp)->node_nr);
900 set_nodes_block(cp, cpblock );
901 //printf(" POST NODE %ld BLOCK %ld \n", cp->node_nr, get_nodes_block(cp)->node_nr);
903 /* fix the phi information in attr.phis (does not add the phi node to the block) */
906 add_Block_phi(cpblock, cp);
907 //printf("PHI-BLOCK block %ld got its phi %ld\n", cpblock->node_nr, cp->node_nr);
911 /* macroblock info is not copied */
912 set_Block_MacroBlock(cp, cp);
916 // for(i=0; i<ARR_LEN(cpin); i++)
917 // printf(" cpin of %ld (cp %ld): %ld \n ", node->node_nr, cp->node_nr, cpin[i]->node_nr);
919 set_irn_in(cp, ARR_LEN(cpin), cpin);
921 // for(i=0; i< ARR_LEN(cpin); i++)
923 // printf("ins %ld: %ld \n", cp->node_nr, cpin[i]->node_nr);
927 // if (!nodestate->temp)
929 // nodestate->link = cp;
930 // cpstate = XMALLOCZ(link_node_state_t);
931 // cp->link = cpstate;
933 // /* temporary copy is existent but without correct ins */
934 // cp = nodestate->link;
939 nodestate->cloned = 1;
942 //void chklink (ir_node *n, void * e)
944 // ir_node *link = n->link;
945 // link_node_state_t *l = (link_node_state_t *)link;
947 // printf("n %ld\n", n->node_nr);
948 // printf("l p %ld\n", l->link);
950 // printf("l %ld\n", l->link->node_nr);
955 * Loop peeling, and fix the cf for the loop entry nodes, which have now more preds
960 ir_node **entry_buffer;
964 NEW_ARR_A(ir_node *, entry_buffer, ARR_LEN(loop_entries));
966 for(i = 0; i < ARR_LEN(loop_entries); i++)
968 loop_entry_t entry = loop_entries[i];
969 ir_node *node = entry.node;
970 ir_node *pred = get_irn_n(entry.node, entry.pred_irn_n);
972 if (is_Block(node)) {
973 /* node is block and the given pred points inside the loop */
978 // leave keepalives out
979 if (is_End(node) && (is_Block(pred) || is_Phi(pred)) ) {
980 //add_End_keepalive(get_irg_end(current_ir_graph), get_copy_of(pred) );
982 cppred = get_copy(pred);
983 //printf("fix block entry %ld to cp %ld\n", node->node_nr, cppred->node_nr);
984 add_pred( node, cppred );
985 //printf("fix block entry %ld to cp %ld\n", node->node_nr, cppred->node_nr);
988 //add_End_keepalive(get_irg_end(current_ir_graph), get_copy_of(pred) );
991 //phifix(node, cppred);
993 /* node is somewhere in the graph, outside of the loop */
999 // no ssa for keepalives
1000 if (is_End(node) && (is_Block(pred) || is_Phi(pred)) ) {
1001 //add_End_keepalive(get_irg_end(current_ir_graph), get_copy_of(pred) );
1003 //printf("fix entry %ld to %ld\n", node->node_nr, pred->node_nr);
1004 entry_buffer[entry_c++] = pred;
1007 //add_End_keepalive(get_irg_end(current_ir_graph), get_copy_of(pred) );
1009 // cannot construct_ssa here, because it needs another walker
1014 //irg_walk_graph(current_ir_graph, chklink, NULL, NULL);
1016 fix_head(loop_cf_head);
1018 //printf (" FIXHEAD DONE :D \n");
1022 /* Generate phis for values from peeled code and original loop */
1023 for(i = 0; entry_i < entry_c; i++)
1025 loop_entry_t entry = loop_entries[i];
1026 ir_node *node = entry.node;
1031 ir_node *phi=get_Block_phis(node);
1035 add_pred(phi, entry_buffer[entry_i++]);
1036 phi=get_Phi_next(phi);
1041 ir_node *cppred, *block, *cpblock, *pred;
1044 * pred = get_irn_n(entry.node, entry.pred_irn_n);
1045 * does not work, because we could have changed the nodes preds in construct_ssa
1048 pred = entry_buffer[entry_i++];
1050 //printf("pred %ld\n", pred->node_nr);
1051 cppred = get_copy(pred);
1052 //printf("cppred %ld\n", cppred->node_nr);
1053 block = get_nodes_block(pred);
1054 //printf("block %ld\n", block->node_nr);
1055 cpblock = get_nodes_block(cppred);
1056 //printf("cpblock %ld\n", cpblock->node_nr);
1059 //dump_ir_block_graph(current_ir_graph, "vorher");
1060 construct_ssa(block, pred, cpblock, cppred);
1061 //add_End_keepalive(get_irg_end(current_ir_graph), cppred);
1064 //add_pred(get_irg_end(current_ir_graph), cppred);
1065 //dump_ir_block_graph(current_ir_graph, "nachher");
1071 void alloc_linkstructs(ir_node *node, void *env)
1074 link_node_state_t *state = XMALLOCZ(link_node_state_t);
1075 node->link = (void *)state;
1078 void free_linkstructs(ir_node *node, void *env)
1081 xfree( (link_node_state_t*) node->link);
1084 void decision_maker(void)
1086 //inc_irg_visited(current_ir_graph);
1087 //loop_walker( loop_entries, NULL, get_invariants, NULL );
1090 inc_irg_visited(current_ir_graph);
1091 irg_walk_graph(current_ir_graph, alloc_linkstructs, NULL, NULL);
1093 inc_irg_visited(current_ir_graph);
1096 inc_irg_visited(current_ir_graph);
1097 irg_walk_graph(current_ir_graph, free_linkstructs, NULL, NULL);
1102 * TODO use list , not arr_F
1104 void analyze_loop(ir_loop *loop)
1106 /* Init new for every loop */
1107 loop_cf_head = NULL;
1108 loop_cf_head_valid = 1;
1109 //loop_entries_n = 0;
1116 //backedges = NEW_ARR_F(loop_entry_t, 0);
1117 //alien_backedges = NEW_ARR_F(loop_entry_t, 0);
1118 //head_edges = NEW_ARR_F(loop_entry_t, 0);
1120 loop_entries = NEW_ARR_F(loop_entry_t, 0);
1121 head_entries = NEW_ARR_F(loop_entry_t, 0);
1123 inc_irg_visited( current_ir_graph );
1124 irg_walk_graph( current_ir_graph, block_phi_walker, NULL, NULL );
1126 /* Collect all backedges */
1127 for_each_loop_block(loop, collect_backedges, NULL );
1129 /* Find loop entries walk, find head */
1130 inc_irg_visited( current_ir_graph );
1131 irg_walk_graph( current_ir_graph, find_loop_entries_walk, NULL, NULL );
1133 /* RETURN if there is no valid head */
1134 if (!loop_cf_head || !loop_cf_head_valid)
1136 //DBG printf("NOTE: There is no valid loop head. Nothing done.\n");
1142 // TODO free all link states... or better put them on functionstack
1145 DEL_ARR_F(loop_entries);
1146 DEL_ARR_F(head_entries);
1147 //DEL_ARR_F(backedges);
1148 //DEL_ARR_F(alien_backedges);
1149 //DEL_ARR_F(head_edges);
1151 //dump_ir_block_graph(current_ir_graph, "-lu1");
1155 * Find most inner loops and send them to analyze_loop
1157 void analyze_inner_loop(ir_loop *loop)
1159 /* descend into sons */
1160 int sons = get_loop_n_sons(loop);
1162 //printf("found %d loops \n", sons);
1166 //printf("analyze loop %ld\n", loop->loop_nr);
1172 for(s=0; s<sons; s++)
1174 //printf("descend into loop son %ld\n", get_loop_son(loop, s)->loop_nr);
1175 analyze_inner_loop( get_loop_son(loop, s) );
1180 void loop_optimization(ir_graph *irg)
1182 //printf(" --- loop unroll start --- \n");
1184 //irg_walk_graph(irg, phicheck, NULL, NULL);
1188 assure_cf_loop(irg);
1190 loop = get_irg_loop(irg);
1191 int sons = get_loop_n_sons(loop);
1192 //printf("FOUND %d LOOPS \n", sons);
1194 for (nr=0; nr<sons; nr++)
1196 analyze_inner_loop( get_loop_son(loop, nr) );
1200 //printf(" --- loop unroll done --- \n");
1203 //struct loop_unroll_pass_t {
1204 // ir_graph_pass_t pass;
1208 * Wrapper to run loop_unroll() as a ir_prog pass.
1210 //static int loop_unroll_wrapper(ir_graph *irg, void *context) {
1213 // loop_unroll(irg);
1218 //ir_graph_pass_t *loop_unroll_pass(const char *name)
1220 // struct loop_unroll_pass_t *pass =
1221 // XMALLOCZ(struct loop_unroll_pass_t);
1223 // return def_graph_pass_constructor(
1224 // &pass->pass, name ? name : "loop_unroll",
1225 // loop_unroll_wrapper);
1229 void firm_init_loopunroll(void) {
1230 FIRM_DBG_REGISTER(dbg, "firm.opt.loopunroll");