Mercurial > hg > CbC > CbC_gcc

comparison gcc/cfgloopanal.c @ 55:77e2b8dfacca gcc-4.4.5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update it from 4.4.3 to 4.5.0
author ryoma <e075725@ie.u-ryukyu.ac.jp>
date Fri, 12 Feb 2010 23:39:51 +0900
parents a06113de4d67
children f6334be47118
comparison
equal deleted inserted replaced
52:c156f1bd5cd9 55:77e2b8dfacca
50 return false; 50 return false;
51 51
52 return true; 52 return true;
53 } 53 }
54 54
55 /* Marks the edge E in graph G irreducible if it connects two vertices in the
56 same scc. */
57
58 static void
59 check_irred (struct graph *g, struct graph_edge *e)
60 {
61 edge real = (edge) e->data;
62
63 /* All edges should lead from a component with higher number to the
64 one with lower one. */
65 gcc_assert (g->vertices[e->src].component >= g->vertices[e->dest].component);
66
67 if (g->vertices[e->src].component != g->vertices[e->dest].component)
68 return;
69
70 real->flags |= EDGE_IRREDUCIBLE_LOOP;
71 if (flow_bb_inside_loop_p (real->src->loop_father, real->dest))
72 real->src->flags |= BB_IRREDUCIBLE_LOOP;
73 }
74
75 /* Marks blocks and edges that are part of non-recognized loops; i.e. we 55 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
76 throw away all latch edges and mark blocks inside any remaining cycle. 56 throw away all latch edges and mark blocks inside any remaining cycle.
77 Everything is a bit complicated due to fact we do not want to do this 57 Everything is a bit complicated due to fact we do not want to do this
78 for parts of cycles that only "pass" through some loop -- i.e. for 58 for parts of cycles that only "pass" through some loop -- i.e. for
79 each cycle, we want to mark blocks that belong directly to innermost 59 each cycle, we want to mark blocks that belong directly to innermost
82 LOOPS is the loop tree. */ 62 LOOPS is the loop tree. */
83 63
84 #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block) 64 #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block)
85 #define BB_REPR(BB) ((BB)->index + 1) 65 #define BB_REPR(BB) ((BB)->index + 1)
86 66
87 void 67 bool
88 mark_irreducible_loops (void) 68 mark_irreducible_loops (void)
89 { 69 {
90 basic_block act; 70 basic_block act;
71 struct graph_edge *ge;
91 edge e; 72 edge e;
92 edge_iterator ei; 73 edge_iterator ei;
93 int src, dest; 74 int src, dest;
94 unsigned depth; 75 unsigned depth;
95 struct graph *g; 76 struct graph *g;
96 int num = number_of_loops (); 77 int num = number_of_loops ();
97 struct loop *cloop; 78 struct loop *cloop;
79 bool irred_loop_found = false;
80 int i;
98 81
99 gcc_assert (current_loops != NULL); 82 gcc_assert (current_loops != NULL);
100 83
101 /* Reset the flags. */ 84 /* Reset the flags. */
102 FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 85 FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
152 135
153 /* Find the strongly connected components. */ 136 /* Find the strongly connected components. */
154 graphds_scc (g, NULL); 137 graphds_scc (g, NULL);
155 138
156 /* Mark the irreducible loops. */ 139 /* Mark the irreducible loops. */
157 for_each_edge (g, check_irred); 140 for (i = 0; i < g->n_vertices; i++)
141 for (ge = g->vertices[i].succ; ge; ge = ge->succ_next)
142 {
143 edge real = (edge) ge->data;
144 /* edge E in graph G is irreducible if it connects two vertices in the
145 same scc. */
146
147 /* All edges should lead from a component with higher number to the
148 one with lower one. */
149 gcc_assert (g->vertices[ge->src].component >= g->vertices[ge->dest].component);
150
151 if (g->vertices[ge->src].component != g->vertices[ge->dest].component)
152 continue;
153
154 real->flags |= EDGE_IRREDUCIBLE_LOOP;
155 irred_loop_found = true;
156 if (flow_bb_inside_loop_p (real->src->loop_father, real->dest))
157 real->src->flags |= BB_IRREDUCIBLE_LOOP;
158 }
158 159
159 free_graph (g); 160 free_graph (g);
160 161
161 loops_state_set (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS); 162 loops_state_set (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
163 return irred_loop_found;
162 } 164 }
163 165
164 /* Counts number of insns inside LOOP. */ 166 /* Counts number of insns inside LOOP. */
165 int 167 int
166 num_loop_insns (const struct loop *loop) 168 num_loop_insns (const struct loop *loop)
171 173
172 bbs = get_loop_body (loop); 174 bbs = get_loop_body (loop);
173 for (i = 0; i < loop->num_nodes; i++) 175 for (i = 0; i < loop->num_nodes; i++)
174 { 176 {
175 bb = bbs[i]; 177 bb = bbs[i];
176 ninsns++; 178 FOR_BB_INSNS (bb, insn)
177 for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn)) 179 if (NONDEBUG_INSN_P (insn))
178 if (INSN_P (insn))
179 ninsns++; 180 ninsns++;
180 } 181 }
181 free(bbs); 182 free (bbs);
183
184 if (!ninsns)
185 ninsns = 1; /* To avoid division by zero. */
182 186
183 return ninsns; 187 return ninsns;
184 } 188 }
185 189
186 /* Counts number of insns executed on average per iteration LOOP. */ 190 /* Counts number of insns executed on average per iteration LOOP. */
195 bbs = get_loop_body (loop); 199 bbs = get_loop_body (loop);
196 for (i = 0; i < loop->num_nodes; i++) 200 for (i = 0; i < loop->num_nodes; i++)
197 { 201 {
198 bb = bbs[i]; 202 bb = bbs[i];
199 203
200 binsns = 1; 204 binsns = 0;
201 for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn)) 205 FOR_BB_INSNS (bb, insn)
202 if (INSN_P (insn)) 206 if (NONDEBUG_INSN_P (insn))
203 binsns++; 207 binsns++;
204 208
205 ratio = loop->header->frequency == 0 209 ratio = loop->header->frequency == 0
206 ? BB_FREQ_MAX 210 ? BB_FREQ_MAX
207 : (bb->frequency * BB_FREQ_MAX) / loop->header->frequency; 211 : (bb->frequency * BB_FREQ_MAX) / loop->header->frequency;
208 ninsns += binsns * ratio; 212 ninsns += binsns * ratio;
209 } 213 }
210 free(bbs); 214 free (bbs);
211 215
212 ninsns /= BB_FREQ_MAX; 216 ninsns /= BB_FREQ_MAX;
213 if (!ninsns) 217 if (!ninsns)
214 ninsns = 1; /* To avoid division by zero. */ 218 ninsns = 1; /* To avoid division by zero. */
215 219