1 /* Code to analyze doloop loops in order for targets to perform late 2 optimizations converting doloops to other forms of hardware loops. 3 Copyright (C) 2011-2013 Free Software Foundation, Inc. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 /* We need to keep a vector of loops */ 22 typedef struct hwloop_info_d *hwloop_info; 23 24 /* Information about a loop we have found (or are in the process of 25 finding). */ 26 struct GTY (()) hwloop_info_d 27 { 28 /* loop number, for dumps */ 29 int loop_no; 30 31 /* Next loop in the graph. */ 32 hwloop_info next; 33 34 /* Vector of blocks only within the loop, including those within 35 inner loops. */ 36 vec<basic_block> blocks; 37 38 /* Same information in a bitmap. */ 39 bitmap block_bitmap; 40 41 /* Vector of inner loops within this loop. Includes loops of every 42 nesting level. */ 43 vec<hwloop_info> loops; 44 45 /* All edges that jump into the loop. */ 46 vec<edge, va_gc> *incoming; 47 48 /* The ports currently using this infrastructure can typically 49 handle two cases: all incoming edges have the same destination 50 block, or all incoming edges have the same source block. These 51 two members are set to the common source or destination we found, 52 or NULL if different blocks were found. If both are NULL the 53 loop can't be optimized. */ 54 basic_block incoming_src; 55 basic_block incoming_dest; 56 57 /* First block in the loop. This is the one branched to by the loop_end 58 insn. */ 59 basic_block head; 60 61 /* Last block in the loop (the one with the loop_end insn). */ 62 basic_block tail; 63 64 /* The successor block of the loop. This is the one the loop_end insn 65 falls into. */ 66 basic_block successor; 67 68 /* The last instruction in the tail. */ 69 rtx last_insn; 70 71 /* The loop_end insn. */ 72 rtx loop_end; 73 74 /* The iteration register. */ 75 rtx iter_reg; 76 77 /* The new label placed at the beginning of the loop. */ 78 rtx start_label; 79 80 /* The new label placed at the end of the loop. */ 81 rtx end_label; 82 83 /* The length of the loop. */ 84 int length; 85 86 /* The nesting depth of the loop. Innermost loops are given a depth 87 of 1. Only successfully optimized doloops are counted; if an inner 88 loop was marked as bad, it does not increase the depth of its parent 89 loop. 90 This value is valid when the target's optimize function is called. */ 91 int depth; 92 93 /* True if we can't optimize this loop. */ 94 bool bad; 95 96 /* True if we have visited this loop during the optimization phase. */ 97 bool visited; 98 99 /* The following values are collected before calling the target's optimize 100 function and are not valid earlier. */ 101 102 /* Record information about control flow: whether the loop has calls 103 or asm statements, whether it has edges that jump out of the loop, 104 or edges that jump within the loop. */ 105 bool has_call; 106 bool has_asm; 107 bool jumps_within; 108 bool jumps_outof; 109 110 /* True if there is an instruction other than the doloop_end which uses the 111 iteration register. */ 112 bool iter_reg_used; 113 /* True if the iteration register lives past the doloop instruction. */ 114 bool iter_reg_used_outside; 115 116 /* Hard registers set at any point in the loop, except for the loop counter 117 register's set in the doloop_end instruction. */ 118 HARD_REG_SET regs_set_in_loop; 119 }; 120 121 /* A set of hooks to be defined by a target that wants to use the reorg_loops 122 functionality. 123 124 reorg_loops is intended to handle cases where special hardware loop 125 setup instructions are required before the loop, for example to set 126 up loop counter registers that are not exposed to the register 127 allocator, or to inform the hardware about loop bounds. 128 129 reorg_loops performs analysis to discover loop_end patterns created 130 by the earlier loop-doloop pass, and sets up a hwloop_info 131 structure for each such insn it finds. It then tries to discover 132 the basic blocks containing the loop by tracking the lifetime of 133 the iteration register. 134 135 If a valid loop can't be found, the FAIL function is called; 136 otherwise the OPT function is called for each loop, visiting 137 innermost loops first and ascending. */ 138 struct hw_doloop_hooks 139 { 140 /* Examine INSN. If it is a suitable doloop_end pattern, return the 141 iteration register, which should be a single hard register. 142 Otherwise, return NULL_RTX. */ 143 rtx (*end_pattern_reg) (rtx insn); 144 /* Optimize LOOP. The target should perform any additional analysis 145 (e.g. checking that the loop isn't too long), and then perform 146 its transformations. Return true if successful, false if the 147 loop should be marked bad. If it returns false, the FAIL 148 function is called. */ 149 bool (*opt) (hwloop_info loop); 150 /* Handle a loop that was marked bad for any reason. This could be 151 used to split the doloop_end pattern. */ 152 void (*fail) (hwloop_info loop); 153 }; 154 155 extern void reorg_loops (bool, struct hw_doloop_hooks *); 156