Lines Matching defs:loop
77 #include "loop-unroll.h"
91 1. Build a data-dependence graph (DDG) for each loop.
92 2. Use the DDG to order the insns of a loop (not in topological order
95 3. Compute MII: a lower bound on the number of cycles to schedule the loop.
96 4. Use the ordering to perform list-scheduling of the loop:
97 1. Set II = MII. We will try to schedule the loop within II cycles.
108 5. If we succeeded in scheduling the loop within II cycles, we now
109 generate prolog and epilog, decrease the counter of the loop, and
115 decoupled from the rest of the loop and (2) whose loop count can
119 constant number of iterations less than the original loop. So the
121 its own iv, not otherwise used in the loop (at-least for now), which
122 initializes a register before the loop to the number of iterations.
123 Currently SMS relies on the do-loop pattern to recognize such loops,
125 using a certain 'count' register and (2) the loop count can be
126 adjusted by modifying this register prior to the loop.
249 static void generate_prolog_epilog (partial_schedule_ptr, struct loop *,
352 the original (unscheduled) loop. Return the first instruction
353 in the loop that was associated with ps_rtl_insn (PS, ID).
374 /* Given HEAD and TAIL which are the first and last insns in a loop;
375 return the register which controls the loop. Return zero if it has
376 more than one occurrence in the loop besides the control part or the
377 do-loop pattern is not of the form we expect. */
401 /* Check that the COUNT_REG has no other occurrences in the loop
700 Breaking intra-loop register anti-dependences:
701 Each intra-loop register anti-dependence implies a cross-iteration true
755 thus we do not except to encounter them in the loop
911 the insns of the loop kernel. */
1156 the loop. */
1177 generate_prolog_epilog (partial_schedule_ptr ps, struct loop *loop,
1184 /* Generate the prolog, inserting its insns on the loop-entry edge. */
1190 adjust the loop count by STAGE_COUNT. If loop count is constant
1208 e = loop_preheader_edge (loop);
1215 /* Generate the epilog, inserting its insns on the loop-exit edge. */
1222 gcc_assert (single_exit (loop));
1223 e = single_exit (loop);
1234 mark_loop_unsched (struct loop *loop)
1237 basic_block *bbs = get_loop_body (loop);
1239 for (i = 0; i < loop->num_nodes; i++)
1245 /* Return true if all the BBs of the loop are empty except the
1246 loop header. */
1248 loop_single_full_bb_p (struct loop *loop)
1251 basic_block *bbs = get_loop_body (loop);
1253 for (i = 0; i < loop->num_nodes ; i++)
1258 if (bbs[i] == loop->header)
1295 /* A simple loop from SMS point of view; it is a loop that is composed of
1297 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
1298 && (EDGE_COUNT (loop->latch->preds) == 1) \
1299 && (EDGE_COUNT (loop->latch->succs) == 1))
1301 /* Return true if the loop is in its canonical form and false if not.
1304 loop_canon_p (struct loop *loop)
1307 if (loop->inner || !loop_outer (loop))
1310 fprintf (dump_file, "SMS loop inner or !loop_outer\n");
1314 if (!single_exit (loop))
1318 rtx_insn *insn = BB_END (loop->header);
1320 fprintf (dump_file, "SMS loop many exits");
1327 if (! SIMPLE_SMS_LOOP_P (loop) && ! loop_single_full_bb_p (loop))
1331 rtx_insn *insn = BB_END (loop->header);
1333 fprintf (dump_file, "SMS loop many BBs.");
1343 /* If there are more than one entry for the loop,
1347 canon_loop (struct loop *loop)
1358 if (loop->latch == loop->header
1359 || EDGE_COUNT (loop->latch->succs) > 1)
1361 FOR_EACH_EDGE (e, i, loop->header->preds)
1362 if (e->src == loop->latch)
1381 /* Probability in % that the sms-ed loop rolls enough so that optimized
1399 struct loop *loop;
1428 /* Allocate memory to hold the DDG array one entry for each loop.
1429 We use loop->num as index into this array. */
1439 indexed by the loop index. */
1440 FOR_EACH_LOOP (loop, 0)
1456 rtx_insn *insn = BB_END (loop->header);
1458 fprintf (dump_file, "SMS loop num: %d", loop->num);
1463 if (! loop_canon_p (loop))
1466 if (! loop_single_full_bb_p (loop))
1473 bb = loop->header;
1476 latch_edge = loop_latch_edge (loop);
1477 gcc_assert (single_exit (loop));
1478 if (single_exit (loop)->count)
1479 trip_count = latch_edge->count / single_exit (loop)->count;
1484 && (latch_edge->count < single_exit (loop)->count * SMS_LOOP_AVERAGE_COUNT_THRESHOLD))
1489 fprintf (dump_file, "\nSMS single-bb-loop\n");
1492 fprintf (dump_file, "SMS loop-count ");
1520 that do-loop recognizes.
1541 fprintf (dump_file, "SMS loop-with-call\n");
1543 fprintf (dump_file, "SMS loop-with-barrier\n");
1546 fprintf (dump_file, "SMS loop-with-not-single-set\n");
1548 fprintf (dump_file, "SMS loop with subreg in lhs\n");
1566 g_arr[loop->num] = g;
1578 FOR_EACH_LOOP (loop, 0)
1587 if (! (g = g_arr[loop->num]))
1592 rtx_insn *insn = BB_END (loop->header);
1594 fprintf (dump_file, "SMS loop num: %d", loop->num);
1601 get_ebb_head_tail (loop->header, loop->header, &head, &tail);
1603 latch_edge = loop_latch_edge (loop);
1604 gcc_assert (single_exit (loop));
1605 if (single_exit (loop)->count)
1606 trip_count = latch_edge->count / single_exit (loop)->count;
1611 fprintf (dump_file, "\nSMS single-bb-loop\n");
1614 fprintf (dump_file, "SMS loop-count ");
1630 /* In case of th loop have doloop register it gets special
1637 pre_header = loop_preheader_edge (loop)->src;
1706 " loop-count=", stage_count);
1749 canon_loop (loop);
1759 /* case the BCT count is not known , Do loop-versioning */
1768 loop_version (loop, comp_rtx, &condition_bb,
1773 /* Set new iteration count of loop kernel. */
1778 /* Now apply the scheduled kernel to the RTL of the loop. */
1781 /* Mark this loop as software pipelined so the later
1784 mark_loop_unsched (loop);
1793 generate_prolog_epilog (ps, loop, count_reg, count_init);
1812 Input: 'O' an ordered list of insns of a loop.
1813 Output: A scheduling of the loop - kernel, prolog, and epilogue.
1896 noticed that there are several cases in which we fail to SMS the loop
3347 /* Revisit later and optimize this into a single loop. */
3411 /* Collect loop information to be used in SMS. */