]>
Commit | Line | Data |
---|---|---|
90e88fd3 | 1 | /* Gimple range GORI functions. |
99dee823 | 2 | Copyright (C) 2017-2021 Free Software Foundation, Inc. |
90e88fd3 AM |
3 | Contributed by Andrew MacLeod <amacleod@redhat.com> |
4 | and Aldy Hernandez <aldyh@redhat.com>. | |
5 | ||
6 | This file is part of GCC. | |
7 | ||
8 | GCC is free software; you can redistribute it and/or modify | |
9 | it under the terms of the GNU General Public License as published by | |
10 | the Free Software Foundation; either version 3, or (at your option) | |
11 | any later version. | |
12 | ||
13 | GCC is distributed in the hope that it will be useful, | |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | GNU General Public License for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
19 | along with GCC; see the file COPYING3. If not see | |
20 | <http://www.gnu.org/licenses/>. */ | |
21 | ||
22 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
25 | #include "backend.h" | |
26 | #include "tree.h" | |
27 | #include "gimple.h" | |
28 | #include "ssa.h" | |
29 | #include "gimple-pretty-print.h" | |
30 | #include "gimple-range.h" | |
31 | ||
4c85ff75 AM |
32 | // Calculate what we can determine of the range of this unary |
33 | // statement's operand if the lhs of the expression has the range | |
34 | // LHS_RANGE. Return false if nothing can be determined. | |
35 | ||
36 | bool | |
37 | gimple_range_calc_op1 (irange &r, const gimple *stmt, const irange &lhs_range) | |
38 | { | |
39 | gcc_checking_assert (gimple_num_ops (stmt) < 3); | |
004afb98 | 40 | // Give up on empty ranges. |
4c85ff75 | 41 | if (lhs_range.undefined_p ()) |
004afb98 AM |
42 | return false; |
43 | ||
4c85ff75 AM |
44 | // Unary operations require the type of the first operand in the |
45 | // second range position. | |
004afb98 | 46 | tree type = TREE_TYPE (gimple_range_operand1 (stmt)); |
4c85ff75 AM |
47 | int_range<2> type_range (type); |
48 | return gimple_range_handler (stmt)->op1_range (r, type, lhs_range, | |
49 | type_range); | |
50 | } | |
51 | ||
52 | // Calculate what we can determine of the range of this statement's | |
53 | // first operand if the lhs of the expression has the range LHS_RANGE | |
54 | // and the second operand has the range OP2_RANGE. Return false if | |
55 | // nothing can be determined. | |
56 | ||
57 | bool | |
58 | gimple_range_calc_op1 (irange &r, const gimple *stmt, | |
59 | const irange &lhs_range, const irange &op2_range) | |
60 | { | |
004afb98 AM |
61 | // Give up on empty ranges. |
62 | if (lhs_range.undefined_p ()) | |
63 | return false; | |
64 | ||
4c85ff75 AM |
65 | // Unary operation are allowed to pass a range in for second operand |
66 | // as there are often additional restrictions beyond the type which | |
67 | // can be imposed. See operator_cast::op1_range(). | |
68 | tree type = TREE_TYPE (gimple_range_operand1 (stmt)); | |
004afb98 AM |
69 | // If op2 is undefined, solve as if it is varying. |
70 | if (op2_range.undefined_p ()) | |
4c85ff75 | 71 | { |
004afb98 AM |
72 | // This is sometimes invoked on single operand stmts. |
73 | if (gimple_num_ops (stmt) < 3) | |
74 | return false; | |
75 | int_range<2> trange (TREE_TYPE (gimple_range_operand2 (stmt))); | |
76 | return gimple_range_handler (stmt)->op1_range (r, type, lhs_range, | |
77 | trange); | |
4c85ff75 AM |
78 | } |
79 | return gimple_range_handler (stmt)->op1_range (r, type, lhs_range, | |
80 | op2_range); | |
81 | } | |
82 | ||
83 | // Calculate what we can determine of the range of this statement's | |
84 | // second operand if the lhs of the expression has the range LHS_RANGE | |
85 | // and the first operand has the range OP1_RANGE. Return false if | |
86 | // nothing can be determined. | |
87 | ||
88 | bool | |
89 | gimple_range_calc_op2 (irange &r, const gimple *stmt, | |
90 | const irange &lhs_range, const irange &op1_range) | |
91 | { | |
004afb98 AM |
92 | // Give up on empty ranges. |
93 | if (lhs_range.undefined_p ()) | |
94 | return false; | |
95 | ||
4c85ff75 | 96 | tree type = TREE_TYPE (gimple_range_operand2 (stmt)); |
004afb98 AM |
97 | // If op1 is undefined, solve as if it is varying. |
98 | if (op1_range.undefined_p ()) | |
4c85ff75 | 99 | { |
004afb98 AM |
100 | int_range<2> trange (TREE_TYPE (gimple_range_operand1 (stmt))); |
101 | return gimple_range_handler (stmt)->op2_range (r, type, lhs_range, | |
102 | trange); | |
4c85ff75 AM |
103 | } |
104 | return gimple_range_handler (stmt)->op2_range (r, type, lhs_range, | |
105 | op1_range); | |
106 | } | |
107 | ||
329d2f0d AM |
108 | // Return TRUE if GS is a logical && or || expression. |
109 | ||
110 | static inline bool | |
111 | is_gimple_logical_p (const gimple *gs) | |
112 | { | |
113 | // Look for boolean and/or condition. | |
114 | if (is_gimple_assign (gs)) | |
115 | switch (gimple_expr_code (gs)) | |
116 | { | |
117 | case TRUTH_AND_EXPR: | |
118 | case TRUTH_OR_EXPR: | |
119 | return true; | |
120 | ||
121 | case BIT_AND_EXPR: | |
122 | case BIT_IOR_EXPR: | |
123 | // Bitwise operations on single bits are logical too. | |
124 | if (types_compatible_p (TREE_TYPE (gimple_assign_rhs1 (gs)), | |
125 | boolean_type_node)) | |
126 | return true; | |
127 | break; | |
128 | ||
129 | default: | |
130 | break; | |
131 | } | |
132 | return false; | |
133 | } | |
90e88fd3 | 134 | |
c2164470 | 135 | /* RANGE_DEF_CHAIN is used to determine which SSA names in a block can |
90e88fd3 AM |
136 | have range information calculated for them, and what the |
137 | dependencies on each other are. | |
138 | ||
139 | Information for a basic block is calculated once and stored. It is | |
140 | only calculated the first time a query is made, so if no queries | |
141 | are made, there is little overhead. | |
142 | ||
143 | The def_chain bitmap is indexed by SSA_NAME_VERSION. Bits are set | |
144 | within this bitmap to indicate SSA names that are defined in the | |
145 | SAME block and used to calculate this SSA name. | |
146 | ||
147 | ||
148 | <bb 2> : | |
149 | _1 = x_4(D) + -2; | |
150 | _2 = _1 * 4; | |
151 | j_7 = foo (); | |
152 | q_5 = _2 + 3; | |
153 | if (q_5 <= 13) | |
154 | ||
155 | _1 : x_4(D) | |
156 | _2 : 1 x_4(D) | |
157 | q_5 : _1 _2 x_4(D) | |
158 | ||
159 | This dump indicates the bits set in the def_chain vector. | |
160 | as well as demonstrates the def_chain bits for the related ssa_names. | |
161 | ||
162 | Checking the chain for _2 indicates that _1 and x_4 are used in | |
163 | its evaluation. | |
164 | ||
165 | Def chains also only include statements which are valid gimple | |
166 | so a def chain will only span statements for which the range | |
167 | engine implements operations for. */ | |
168 | ||
169 | ||
90e88fd3 AM |
170 | // Construct a range_def_chain. |
171 | ||
172 | range_def_chain::range_def_chain () | |
173 | { | |
c2164470 | 174 | bitmap_obstack_initialize (&m_bitmaps); |
90e88fd3 AM |
175 | m_def_chain.create (0); |
176 | m_def_chain.safe_grow_cleared (num_ssa_names); | |
329d2f0d | 177 | m_logical_depth = 0; |
90e88fd3 AM |
178 | } |
179 | ||
180 | // Destruct a range_def_chain. | |
181 | ||
182 | range_def_chain::~range_def_chain () | |
183 | { | |
90e88fd3 | 184 | m_def_chain.release (); |
c2164470 | 185 | bitmap_obstack_release (&m_bitmaps); |
90e88fd3 AM |
186 | } |
187 | ||
188 | // Return true if NAME is in the def chain of DEF. If BB is provided, | |
189 | // only return true if the defining statement of DEF is in BB. | |
190 | ||
191 | bool | |
192 | range_def_chain::in_chain_p (tree name, tree def) | |
193 | { | |
194 | gcc_checking_assert (gimple_range_ssa_p (def)); | |
195 | gcc_checking_assert (gimple_range_ssa_p (name)); | |
196 | ||
197 | // Get the defintion chain for DEF. | |
198 | bitmap chain = get_def_chain (def); | |
199 | ||
200 | if (chain == NULL) | |
201 | return false; | |
202 | return bitmap_bit_p (chain, SSA_NAME_VERSION (name)); | |
203 | } | |
204 | ||
c2164470 AM |
205 | // Add either IMP or the import list B to the import set of DATA. |
206 | ||
207 | void | |
208 | range_def_chain::set_import (struct rdc &data, tree imp, bitmap b) | |
209 | { | |
210 | // If there are no imports, just return | |
211 | if (imp == NULL_TREE && !b) | |
212 | return; | |
213 | if (!data.m_import) | |
214 | data.m_import = BITMAP_ALLOC (&m_bitmaps); | |
215 | if (imp != NULL_TREE) | |
216 | bitmap_set_bit (data.m_import, SSA_NAME_VERSION (imp)); | |
217 | else | |
218 | bitmap_ior_into (data.m_import, b); | |
219 | } | |
220 | ||
221 | // Return the import list for NAME. | |
222 | ||
223 | bitmap | |
224 | range_def_chain::get_imports (tree name) | |
225 | { | |
226 | if (!has_def_chain (name)) | |
227 | get_def_chain (name); | |
228 | bitmap i = m_def_chain[SSA_NAME_VERSION (name)].m_import; | |
c2164470 AM |
229 | return i; |
230 | } | |
231 | ||
232 | // Return true if IMPORT is an import to NAMEs def chain. | |
233 | ||
234 | bool | |
235 | range_def_chain::chain_import_p (tree name, tree import) | |
236 | { | |
237 | bitmap b = get_imports (name); | |
238 | if (b) | |
239 | return bitmap_bit_p (b, SSA_NAME_VERSION (import)); | |
240 | return false; | |
241 | } | |
242 | ||
90e88fd3 AM |
243 | // Build def_chains for NAME if it is in BB. Copy the def chain into RESULT. |
244 | ||
245 | void | |
c2164470 | 246 | range_def_chain::register_dependency (tree name, tree dep, basic_block bb) |
90e88fd3 | 247 | { |
c2164470 AM |
248 | if (!gimple_range_ssa_p (dep)) |
249 | return; | |
250 | ||
251 | unsigned v = SSA_NAME_VERSION (name); | |
7f0cfeb1 BE |
252 | if (v >= m_def_chain.length ()) |
253 | m_def_chain.safe_grow_cleared (num_ssa_names + 1); | |
c2164470 AM |
254 | struct rdc &src = m_def_chain[v]; |
255 | gimple *def_stmt = SSA_NAME_DEF_STMT (dep); | |
256 | unsigned dep_v = SSA_NAME_VERSION (dep); | |
90e88fd3 | 257 | bitmap b; |
c2164470 AM |
258 | |
259 | // Set the direct dependency cache entries. | |
260 | if (!src.ssa1) | |
261 | src.ssa1 = dep; | |
262 | else if (!src.ssa2 && src.ssa1 != dep) | |
263 | src.ssa2 = dep; | |
264 | ||
265 | // Don't calculate imports or export/dep chains if BB is not provided. | |
266 | // This is usually the case for when the temporal cache wants the direct | |
267 | // dependencies of a stmt. | |
268 | if (!bb) | |
269 | return; | |
270 | ||
271 | if (!src.bm) | |
272 | src.bm = BITMAP_ALLOC (&m_bitmaps); | |
273 | ||
90e88fd3 | 274 | // Add this operand into the result. |
c2164470 | 275 | bitmap_set_bit (src.bm, dep_v); |
90e88fd3 AM |
276 | |
277 | if (gimple_bb (def_stmt) == bb && !is_a<gphi *>(def_stmt)) | |
278 | { | |
279 | // Get the def chain for the operand. | |
c2164470 | 280 | b = get_def_chain (dep); |
90e88fd3 AM |
281 | // If there was one, copy it into result. |
282 | if (b) | |
c2164470 AM |
283 | bitmap_ior_into (src.bm, b); |
284 | // And copy the import list. | |
285 | set_import (src, NULL_TREE, get_imports (dep)); | |
90e88fd3 | 286 | } |
c2164470 AM |
287 | else |
288 | // Originated outside the block, so it is an import. | |
289 | set_import (src, dep, NULL); | |
290 | } | |
291 | ||
292 | bool | |
293 | range_def_chain::def_chain_in_bitmap_p (tree name, bitmap b) | |
294 | { | |
295 | bitmap a = get_def_chain (name); | |
296 | if (a && b) | |
297 | return bitmap_intersect_p (a, b); | |
298 | return false; | |
299 | } | |
300 | ||
301 | void | |
302 | range_def_chain::add_def_chain_to_bitmap (bitmap b, tree name) | |
303 | { | |
304 | bitmap r = get_def_chain (name); | |
305 | if (r) | |
306 | bitmap_ior_into (b, r); | |
90e88fd3 AM |
307 | } |
308 | ||
c2164470 | 309 | |
90e88fd3 AM |
310 | // Return TRUE if NAME has been processed for a def_chain. |
311 | ||
312 | inline bool | |
313 | range_def_chain::has_def_chain (tree name) | |
314 | { | |
315 | // Ensure there is an entry in the internal vector. | |
316 | unsigned v = SSA_NAME_VERSION (name); | |
317 | if (v >= m_def_chain.length ()) | |
318 | m_def_chain.safe_grow_cleared (num_ssa_names + 1); | |
c2164470 | 319 | return (m_def_chain[v].ssa1 != 0); |
90e88fd3 AM |
320 | } |
321 | ||
c2164470 AM |
322 | |
323 | ||
90e88fd3 AM |
324 | // Calculate the def chain for NAME and all of its dependent |
325 | // operands. Only using names in the same BB. Return the bitmap of | |
326 | // all names in the m_def_chain. This only works for supported range | |
327 | // statements. | |
328 | ||
329 | bitmap | |
330 | range_def_chain::get_def_chain (tree name) | |
331 | { | |
332 | tree ssa1, ssa2, ssa3; | |
333 | unsigned v = SSA_NAME_VERSION (name); | |
329d2f0d | 334 | bool is_logical = false; |
90e88fd3 AM |
335 | |
336 | // If it has already been processed, just return the cached value. | |
337 | if (has_def_chain (name)) | |
c2164470 | 338 | return m_def_chain[v].bm; |
90e88fd3 AM |
339 | |
340 | // No definition chain for default defs. | |
341 | if (SSA_NAME_IS_DEFAULT_DEF (name)) | |
c2164470 AM |
342 | { |
343 | // A Default def is always an import. | |
344 | set_import (m_def_chain[v], name, NULL); | |
345 | return NULL; | |
346 | } | |
90e88fd3 AM |
347 | |
348 | gimple *stmt = SSA_NAME_DEF_STMT (name); | |
349 | if (gimple_range_handler (stmt)) | |
350 | { | |
329d2f0d AM |
351 | is_logical = is_gimple_logical_p (stmt); |
352 | // Terminate the def chains if we see too many cascading logical stmts. | |
353 | if (is_logical) | |
354 | { | |
355 | if (m_logical_depth == param_ranger_logical_depth) | |
356 | return NULL; | |
357 | m_logical_depth++; | |
358 | } | |
359 | ||
90e88fd3 AM |
360 | ssa1 = gimple_range_ssa_p (gimple_range_operand1 (stmt)); |
361 | ssa2 = gimple_range_ssa_p (gimple_range_operand2 (stmt)); | |
362 | ssa3 = NULL_TREE; | |
363 | } | |
364 | else if (is_a<gassign *> (stmt) | |
365 | && gimple_assign_rhs_code (stmt) == COND_EXPR) | |
366 | { | |
367 | gassign *st = as_a<gassign *> (stmt); | |
368 | ssa1 = gimple_range_ssa_p (gimple_assign_rhs1 (st)); | |
369 | ssa2 = gimple_range_ssa_p (gimple_assign_rhs2 (st)); | |
370 | ssa3 = gimple_range_ssa_p (gimple_assign_rhs3 (st)); | |
371 | } | |
372 | else | |
c2164470 AM |
373 | { |
374 | // Stmts not understood are always imports. | |
375 | set_import (m_def_chain[v], name, NULL); | |
376 | return NULL; | |
377 | } | |
90e88fd3 | 378 | |
c2164470 AM |
379 | register_dependency (name, ssa1, gimple_bb (stmt)); |
380 | register_dependency (name, ssa2, gimple_bb (stmt)); | |
381 | register_dependency (name, ssa3, gimple_bb (stmt)); | |
382 | // Stmts with no understandable operands are also imports. | |
383 | if (!ssa1 && !ssa2 & !ssa3) | |
384 | set_import (m_def_chain[v], name, NULL); | |
90e88fd3 | 385 | |
329d2f0d AM |
386 | if (is_logical) |
387 | m_logical_depth--; | |
388 | ||
c2164470 | 389 | return m_def_chain[v].bm; |
90e88fd3 AM |
390 | } |
391 | ||
c2164470 AM |
392 | // Dump what we know for basic block BB to file F. |
393 | ||
394 | void | |
395 | range_def_chain::dump (FILE *f, basic_block bb, const char *prefix) | |
396 | { | |
397 | unsigned x, y; | |
398 | bitmap_iterator bi; | |
399 | ||
400 | // Dump the def chain for each SSA_NAME defined in BB. | |
401 | for (x = 1; x < num_ssa_names; x++) | |
402 | { | |
403 | tree name = ssa_name (x); | |
404 | if (!name) | |
405 | continue; | |
406 | gimple *stmt = SSA_NAME_DEF_STMT (name); | |
407 | if (!stmt || (bb && gimple_bb (stmt) != bb)) | |
408 | continue; | |
409 | bitmap chain = (has_def_chain (name) ? get_def_chain (name) : NULL); | |
410 | if (chain && !bitmap_empty_p (chain)) | |
411 | { | |
412 | fprintf (f, prefix); | |
413 | print_generic_expr (f, name, TDF_SLIM); | |
414 | fprintf (f, " : "); | |
415 | ||
416 | bitmap imports = get_imports (name); | |
417 | EXECUTE_IF_SET_IN_BITMAP (chain, 0, y, bi) | |
418 | { | |
419 | print_generic_expr (f, ssa_name (y), TDF_SLIM); | |
420 | if (imports && bitmap_bit_p (imports, y)) | |
421 | fprintf (f, "(I)"); | |
422 | fprintf (f, " "); | |
423 | } | |
424 | fprintf (f, "\n"); | |
425 | } | |
426 | } | |
427 | } | |
428 | ||
429 | ||
90e88fd3 AM |
430 | // ------------------------------------------------------------------- |
431 | ||
432 | /* GORI_MAP is used to accumulate what SSA names in a block can | |
433 | generate range information, and provides tools for the block ranger | |
434 | to enable it to efficiently calculate these ranges. | |
435 | ||
436 | GORI stands for "Generates Outgoing Range Information." | |
437 | ||
438 | It utilizes the range_def_chain class to contruct def_chains. | |
439 | Information for a basic block is calculated once and stored. It is | |
440 | only calculated the first time a query is made. If no queries are | |
441 | made, there is little overhead. | |
442 | ||
443 | one bitmap is maintained for each basic block: | |
444 | m_outgoing : a set bit indicates a range can be generated for a name. | |
445 | ||
446 | Generally speaking, the m_outgoing vector is the union of the | |
447 | entire def_chain of all SSA names used in the last statement of the | |
448 | block which generate ranges. */ | |
449 | ||
90e88fd3 AM |
450 | |
451 | // Initialize a gori-map structure. | |
452 | ||
453 | gori_map::gori_map () | |
454 | { | |
455 | m_outgoing.create (0); | |
456 | m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun)); | |
c2164470 AM |
457 | m_incoming.create (0); |
458 | m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun)); | |
2dd1f944 | 459 | m_maybe_variant = BITMAP_ALLOC (&m_bitmaps); |
90e88fd3 AM |
460 | } |
461 | ||
462 | // Free any memory the GORI map allocated. | |
463 | ||
464 | gori_map::~gori_map () | |
465 | { | |
c2164470 | 466 | m_incoming.release (); |
90e88fd3 AM |
467 | m_outgoing.release (); |
468 | } | |
469 | ||
470 | // Return the bitmap vector of all export from BB. Calculate if necessary. | |
471 | ||
472 | bitmap | |
473 | gori_map::exports (basic_block bb) | |
474 | { | |
c2164470 | 475 | if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index]) |
90e88fd3 AM |
476 | calculate_gori (bb); |
477 | return m_outgoing[bb->index]; | |
478 | } | |
479 | ||
c2164470 AM |
480 | // Return the bitmap vector of all imports to BB. Calculate if necessary. |
481 | ||
482 | bitmap | |
483 | gori_map::imports (basic_block bb) | |
484 | { | |
485 | if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index]) | |
486 | calculate_gori (bb); | |
487 | return m_incoming[bb->index]; | |
488 | } | |
489 | ||
90e88fd3 AM |
490 | // Return true if NAME is can have ranges generated for it from basic |
491 | // block BB. | |
492 | ||
493 | bool | |
494 | gori_map::is_export_p (tree name, basic_block bb) | |
495 | { | |
7f359556 AM |
496 | // If no BB is specified, test if it is exported anywhere in the IL. |
497 | if (!bb) | |
2dd1f944 | 498 | return bitmap_bit_p (m_maybe_variant, SSA_NAME_VERSION (name)); |
90e88fd3 AM |
499 | return bitmap_bit_p (exports (bb), SSA_NAME_VERSION (name)); |
500 | } | |
501 | ||
2dd1f944 AM |
502 | // Clear the m_maybe_variant bit so ranges will not be tracked for NAME. |
503 | ||
504 | void | |
505 | gori_map::set_range_invariant (tree name) | |
506 | { | |
507 | bitmap_clear_bit (m_maybe_variant, SSA_NAME_VERSION (name)); | |
508 | } | |
509 | ||
c2164470 | 510 | // Return true if NAME is an import to block BB. |
90e88fd3 AM |
511 | |
512 | bool | |
c2164470 | 513 | gori_map::is_import_p (tree name, basic_block bb) |
90e88fd3 | 514 | { |
c2164470 AM |
515 | // If no BB is specified, test if it is exported anywhere in the IL. |
516 | return bitmap_bit_p (imports (bb), SSA_NAME_VERSION (name)); | |
90e88fd3 AM |
517 | } |
518 | ||
519 | // If NAME is non-NULL and defined in block BB, calculate the def | |
520 | // chain and add it to m_outgoing. | |
521 | ||
522 | void | |
523 | gori_map::maybe_add_gori (tree name, basic_block bb) | |
524 | { | |
525 | if (name) | |
526 | { | |
c2164470 AM |
527 | // Check if there is a def chain, regardless of the block. |
528 | add_def_chain_to_bitmap (m_outgoing[bb->index], name); | |
529 | // Check for any imports. | |
530 | bitmap imp = get_imports (name); | |
531 | // If there were imports, add them so we can recompute | |
532 | if (imp) | |
533 | bitmap_ior_into (m_incoming[bb->index], imp); | |
534 | // This name is always an import. | |
535 | if (gimple_bb (SSA_NAME_DEF_STMT (name)) != bb) | |
536 | bitmap_set_bit (m_incoming[bb->index], SSA_NAME_VERSION (name)); | |
537 | ||
90e88fd3 AM |
538 | // Def chain doesn't include itself, and even if there isn't a |
539 | // def chain, this name should be added to exports. | |
540 | bitmap_set_bit (m_outgoing[bb->index], SSA_NAME_VERSION (name)); | |
541 | } | |
542 | } | |
543 | ||
544 | // Calculate all the required information for BB. | |
545 | ||
546 | void | |
547 | gori_map::calculate_gori (basic_block bb) | |
548 | { | |
549 | tree name; | |
550 | if (bb->index >= (signed int)m_outgoing.length ()) | |
c2164470 AM |
551 | { |
552 | m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun)); | |
553 | m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun)); | |
554 | } | |
90e88fd3 AM |
555 | gcc_checking_assert (m_outgoing[bb->index] == NULL); |
556 | m_outgoing[bb->index] = BITMAP_ALLOC (&m_bitmaps); | |
c2164470 | 557 | m_incoming[bb->index] = BITMAP_ALLOC (&m_bitmaps); |
90e88fd3 AM |
558 | |
559 | // If this block's last statement may generate range informaiton, go | |
560 | // calculate it. | |
561 | gimple *stmt = gimple_outgoing_range_stmt_p (bb); | |
562 | if (!stmt) | |
563 | return; | |
564 | if (is_a<gcond *> (stmt)) | |
565 | { | |
566 | gcond *gc = as_a<gcond *>(stmt); | |
567 | name = gimple_range_ssa_p (gimple_cond_lhs (gc)); | |
568 | maybe_add_gori (name, gimple_bb (stmt)); | |
569 | ||
570 | name = gimple_range_ssa_p (gimple_cond_rhs (gc)); | |
571 | maybe_add_gori (name, gimple_bb (stmt)); | |
572 | } | |
573 | else | |
574 | { | |
3ca950c3 AM |
575 | // Do not process switches if they are too large. |
576 | if (EDGE_COUNT (bb->succs) > (unsigned)param_evrp_switch_limit) | |
577 | return; | |
90e88fd3 AM |
578 | gswitch *gs = as_a<gswitch *>(stmt); |
579 | name = gimple_range_ssa_p (gimple_switch_index (gs)); | |
580 | maybe_add_gori (name, gimple_bb (stmt)); | |
581 | } | |
7f359556 | 582 | // Add this bitmap to the aggregate list of all outgoing names. |
2dd1f944 | 583 | bitmap_ior_into (m_maybe_variant, m_outgoing[bb->index]); |
90e88fd3 AM |
584 | } |
585 | ||
586 | // Dump the table information for BB to file F. | |
587 | ||
588 | void | |
c2164470 | 589 | gori_map::dump (FILE *f, basic_block bb, bool verbose) |
90e88fd3 | 590 | { |
90e88fd3 | 591 | // BB was not processed. |
c2164470 | 592 | if (!m_outgoing[bb->index] || bitmap_empty_p (m_outgoing[bb->index])) |
90e88fd3 AM |
593 | return; |
594 | ||
c2164470 AM |
595 | tree name; |
596 | ||
597 | bitmap imp = imports (bb); | |
598 | if (!bitmap_empty_p (imp)) | |
90e88fd3 | 599 | { |
c2164470 AM |
600 | if (verbose) |
601 | fprintf (f, "bb<%u> Imports: ",bb->index); | |
602 | else | |
603 | fprintf (f, "Imports: "); | |
604 | FOR_EACH_GORI_IMPORT_NAME (*this, bb, name) | |
605 | { | |
90e88fd3 | 606 | print_generic_expr (f, name, TDF_SLIM); |
c2164470 | 607 | fprintf (f, " "); |
90e88fd3 | 608 | } |
c2164470 | 609 | fputc ('\n', f); |
90e88fd3 AM |
610 | } |
611 | ||
c2164470 AM |
612 | if (verbose) |
613 | fprintf (f, "bb<%u> Exports: ",bb->index); | |
614 | else | |
615 | fprintf (f, "Exports: "); | |
616 | // Dump the export vector. | |
617 | FOR_EACH_GORI_EXPORT_NAME (*this, bb, name) | |
90e88fd3 | 618 | { |
c2164470 | 619 | print_generic_expr (f, name, TDF_SLIM); |
90e88fd3 AM |
620 | fprintf (f, " "); |
621 | } | |
c2164470 | 622 | fputc ('\n', f); |
90e88fd3 | 623 | |
c2164470 | 624 | range_def_chain::dump (f, bb, " "); |
90e88fd3 AM |
625 | } |
626 | ||
627 | // Dump the entire GORI map structure to file F. | |
628 | ||
629 | void | |
630 | gori_map::dump (FILE *f) | |
631 | { | |
632 | basic_block bb; | |
633 | FOR_EACH_BB_FN (bb, cfun) | |
c2164470 | 634 | dump (f, bb); |
90e88fd3 AM |
635 | } |
636 | ||
637 | DEBUG_FUNCTION void | |
638 | debug (gori_map &g) | |
639 | { | |
640 | g.dump (stderr); | |
641 | } | |
642 | ||
643 | // ------------------------------------------------------------------- | |
644 | ||
645 | // Construct a gori_compute object. | |
646 | ||
3ca950c3 AM |
647 | gori_compute::gori_compute (int not_executable_flag) |
648 | : outgoing (param_evrp_switch_limit), tracer ("GORI ") | |
90e88fd3 | 649 | { |
053e1d64 | 650 | m_not_executable_flag = not_executable_flag; |
90e88fd3 AM |
651 | // Create a boolean_type true and false range. |
652 | m_bool_zero = int_range<2> (boolean_false_node, boolean_false_node); | |
653 | m_bool_one = int_range<2> (boolean_true_node, boolean_true_node); | |
9cb114fd | 654 | if (dump_file && (param_ranger_debug & RANGER_DEBUG_GORI)) |
4759e1e0 | 655 | tracer.enable_trace (); |
90e88fd3 AM |
656 | } |
657 | ||
90e88fd3 AM |
658 | // Given the switch S, return an evaluation in R for NAME when the lhs |
659 | // evaluates to LHS. Returning false means the name being looked for | |
660 | // was not resolvable. | |
661 | ||
662 | bool | |
663 | gori_compute::compute_operand_range_switch (irange &r, gswitch *s, | |
664 | const irange &lhs, | |
47ea02bb | 665 | tree name, fur_source &src) |
90e88fd3 AM |
666 | { |
667 | tree op1 = gimple_switch_index (s); | |
668 | ||
669 | // If name matches, the range is simply the range from the edge. | |
670 | // Empty ranges are viral as they are on a path which isn't | |
671 | // executable. | |
672 | if (op1 == name || lhs.undefined_p ()) | |
673 | { | |
674 | r = lhs; | |
675 | return true; | |
676 | } | |
677 | ||
678 | // If op1 is in the defintion chain, pass lhs back. | |
28ceee1b | 679 | if (gimple_range_ssa_p (op1) && in_chain_p (name, op1)) |
47ea02bb | 680 | return compute_operand_range (r, SSA_NAME_DEF_STMT (op1), lhs, name, src); |
90e88fd3 AM |
681 | |
682 | return false; | |
683 | } | |
684 | ||
90e88fd3 AM |
685 | |
686 | // Return an evaluation for NAME as it would appear in STMT when the | |
687 | // statement's lhs evaluates to LHS. If successful, return TRUE and | |
688 | // store the evaluation in R, otherwise return FALSE. | |
689 | ||
690 | bool | |
691 | gori_compute::compute_operand_range (irange &r, gimple *stmt, | |
47ea02bb AM |
692 | const irange &lhs, tree name, |
693 | fur_source &src) | |
90e88fd3 | 694 | { |
47ea02bb AM |
695 | // If the lhs doesn't tell us anything, neither will unwinding further. |
696 | if (lhs.varying_p ()) | |
697 | return false; | |
698 | ||
90e88fd3 AM |
699 | // Empty ranges are viral as they are on an unexecutable path. |
700 | if (lhs.undefined_p ()) | |
701 | { | |
702 | r.set_undefined (); | |
703 | return true; | |
704 | } | |
705 | if (is_a<gswitch *> (stmt)) | |
47ea02bb AM |
706 | return compute_operand_range_switch (r, as_a<gswitch *> (stmt), lhs, name, |
707 | src); | |
90e88fd3 AM |
708 | if (!gimple_range_handler (stmt)) |
709 | return false; | |
710 | ||
711 | tree op1 = gimple_range_ssa_p (gimple_range_operand1 (stmt)); | |
712 | tree op2 = gimple_range_ssa_p (gimple_range_operand2 (stmt)); | |
713 | ||
47ea02bb AM |
714 | // Handle end of lookup first. |
715 | if (op1 == name) | |
716 | return compute_operand1_range (r, stmt, lhs, name, src); | |
717 | if (op2 == name) | |
718 | return compute_operand2_range (r, stmt, lhs, name, src); | |
90e88fd3 AM |
719 | |
720 | // NAME is not in this stmt, but one of the names in it ought to be | |
721 | // derived from it. | |
28ceee1b AM |
722 | bool op1_in_chain = op1 && in_chain_p (name, op1); |
723 | bool op2_in_chain = op2 && in_chain_p (name, op2); | |
47ea02bb AM |
724 | |
725 | // If neither operand is derived, then this stmt tells us nothing. | |
726 | if (!op1_in_chain && !op2_in_chain) | |
727 | return false; | |
728 | ||
4759e1e0 | 729 | bool res; |
47ea02bb AM |
730 | // Process logicals as they have special handling. |
731 | if (is_gimple_logical_p (stmt)) | |
732 | { | |
4759e1e0 AM |
733 | unsigned idx; |
734 | if ((idx = tracer.header ("compute_operand "))) | |
735 | { | |
736 | print_generic_expr (dump_file, name, TDF_SLIM); | |
737 | fprintf (dump_file, " with LHS = "); | |
738 | lhs.dump (dump_file); | |
739 | fprintf (dump_file, " at stmt "); | |
740 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
741 | } | |
742 | ||
47ea02bb AM |
743 | int_range_max op1_trange, op1_frange; |
744 | int_range_max op2_trange, op2_frange; | |
745 | compute_logical_operands (op1_trange, op1_frange, stmt, lhs, | |
746 | name, src, op1, op1_in_chain); | |
747 | compute_logical_operands (op2_trange, op2_frange, stmt, lhs, | |
748 | name, src, op2, op2_in_chain); | |
4759e1e0 AM |
749 | res = logical_combine (r, gimple_expr_code (stmt), lhs, |
750 | op1_trange, op1_frange, op2_trange, op2_frange); | |
751 | if (idx) | |
752 | tracer.trailer (idx, "compute_operand", res, name, r); | |
47ea02bb | 753 | } |
47ea02bb | 754 | // Follow the appropriate operands now. |
4759e1e0 AM |
755 | else if (op1_in_chain && op2_in_chain) |
756 | res = compute_operand1_and_operand2_range (r, stmt, lhs, name, src); | |
757 | else if (op1_in_chain) | |
758 | res = compute_operand1_range (r, stmt, lhs, name, src); | |
759 | else if (op2_in_chain) | |
760 | res = compute_operand2_range (r, stmt, lhs, name, src); | |
761 | else | |
762 | gcc_unreachable (); | |
90e88fd3 AM |
763 | |
764 | // If neither operand is derived, this statement tells us nothing. | |
4759e1e0 | 765 | return res; |
90e88fd3 AM |
766 | } |
767 | ||
47ea02bb | 768 | |
90e88fd3 AM |
769 | // Return TRUE if range R is either a true or false compatible range. |
770 | ||
771 | static bool | |
772 | range_is_either_true_or_false (const irange &r) | |
773 | { | |
774 | if (r.undefined_p ()) | |
775 | return false; | |
776 | ||
777 | // This is complicated by the fact that Ada has multi-bit booleans, | |
778 | // so true can be ~[0, 0] (i.e. [1,MAX]). | |
779 | tree type = r.type (); | |
6e02de94 | 780 | gcc_checking_assert (range_compatible_p (type, boolean_type_node)); |
90e88fd3 AM |
781 | return (r.singleton_p () || !r.contains_p (build_zero_cst (type))); |
782 | } | |
783 | ||
90e88fd3 AM |
784 | // Evaluate a binary logical expression by combining the true and |
785 | // false ranges for each of the operands based on the result value in | |
786 | // the LHS. | |
787 | ||
788 | bool | |
789 | gori_compute::logical_combine (irange &r, enum tree_code code, | |
790 | const irange &lhs, | |
47ea02bb AM |
791 | const irange &op1_true, const irange &op1_false, |
792 | const irange &op2_true, const irange &op2_false) | |
90e88fd3 | 793 | { |
47ea02bb AM |
794 | if (op1_true.varying_p () && op1_false.varying_p () |
795 | && op2_true.varying_p () && op2_false.varying_p ()) | |
90e88fd3 AM |
796 | return false; |
797 | ||
4759e1e0 AM |
798 | unsigned idx; |
799 | if ((idx = tracer.header ("logical_combine"))) | |
800 | { | |
801 | switch (code) | |
802 | { | |
803 | case TRUTH_OR_EXPR: | |
804 | case BIT_IOR_EXPR: | |
805 | fprintf (dump_file, " || "); | |
806 | break; | |
807 | case TRUTH_AND_EXPR: | |
808 | case BIT_AND_EXPR: | |
809 | fprintf (dump_file, " && "); | |
810 | break; | |
811 | default: | |
812 | break; | |
813 | } | |
814 | fprintf (dump_file, " with LHS = "); | |
815 | lhs.dump (dump_file); | |
816 | fputc ('\n', dump_file); | |
817 | ||
818 | tracer.print (idx, "op1_true = "); | |
819 | op1_true.dump (dump_file); | |
820 | fprintf (dump_file, " op1_false = "); | |
821 | op1_false.dump (dump_file); | |
822 | fputc ('\n', dump_file); | |
823 | tracer.print (idx, "op2_true = "); | |
824 | op2_true.dump (dump_file); | |
825 | fprintf (dump_file, " op2_false = "); | |
826 | op2_false.dump (dump_file); | |
827 | fputc ('\n', dump_file); | |
828 | } | |
829 | ||
90e88fd3 AM |
830 | // This is not a simple fold of a logical expression, rather it |
831 | // determines ranges which flow through the logical expression. | |
832 | // | |
833 | // Assuming x_8 is an unsigned char, and relational statements: | |
834 | // b_1 = x_8 < 20 | |
835 | // b_2 = x_8 > 5 | |
836 | // consider the logical expression and branch: | |
837 | // c_2 = b_1 && b_2 | |
838 | // if (c_2) | |
839 | // | |
840 | // To determine the range of x_8 on either edge of the branch, one | |
841 | // must first determine what the range of x_8 is when the boolean | |
842 | // values of b_1 and b_2 are both true and false. | |
843 | // b_1 TRUE x_8 = [0, 19] | |
844 | // b_1 FALSE x_8 = [20, 255] | |
845 | // b_2 TRUE x_8 = [6, 255] | |
846 | // b_2 FALSE x_8 = [0,5]. | |
847 | // | |
848 | // These ranges are then combined based on the expected outcome of | |
849 | // the branch. The range on the TRUE side of the branch must satisfy | |
850 | // b_1 == true && b_2 == true | |
851 | // | |
852 | // In terms of x_8, that means both x_8 == [0, 19] and x_8 = [6, 255] | |
853 | // must be true. The range of x_8 on the true side must be the | |
854 | // intersection of both ranges since both must be true. Thus the | |
855 | // range of x_8 on the true side is [6, 19]. | |
856 | // | |
857 | // To determine the ranges on the FALSE side, all 3 combinations of | |
858 | // failing ranges must be considered, and combined as any of them | |
859 | // can cause the false result. | |
860 | // | |
861 | // If the LHS can be TRUE or FALSE, then evaluate both a TRUE and | |
862 | // FALSE results and combine them. If we fell back to VARYING any | |
863 | // range restrictions that have been discovered up to this point | |
864 | // would be lost. | |
865 | if (!range_is_either_true_or_false (lhs)) | |
866 | { | |
4759e1e0 | 867 | bool res; |
90e88fd3 | 868 | int_range_max r1; |
47ea02bb AM |
869 | if (logical_combine (r1, code, m_bool_zero, op1_true, op1_false, |
870 | op2_true, op2_false) | |
871 | && logical_combine (r, code, m_bool_one, op1_true, op1_false, | |
872 | op2_true, op2_false)) | |
90e88fd3 AM |
873 | { |
874 | r.union_ (r1); | |
4759e1e0 | 875 | res = true; |
90e88fd3 | 876 | } |
4759e1e0 AM |
877 | else |
878 | res = false; | |
879 | if (idx) | |
880 | tracer.trailer (idx, "logical_combine", res, NULL_TREE, r); | |
90e88fd3 AM |
881 | } |
882 | ||
883 | switch (code) | |
884 | { | |
885 | // A logical AND combines ranges from 2 boolean conditions. | |
886 | // c_2 = b_1 && b_2 | |
887 | case TRUTH_AND_EXPR: | |
888 | case BIT_AND_EXPR: | |
889 | if (!lhs.zero_p ()) | |
890 | { | |
891 | // The TRUE side is the intersection of the the 2 true ranges. | |
47ea02bb AM |
892 | r = op1_true; |
893 | r.intersect (op2_true); | |
90e88fd3 AM |
894 | } |
895 | else | |
896 | { | |
897 | // The FALSE side is the union of the other 3 cases. | |
47ea02bb AM |
898 | int_range_max ff (op1_false); |
899 | ff.intersect (op2_false); | |
900 | int_range_max tf (op1_true); | |
901 | tf.intersect (op2_false); | |
902 | int_range_max ft (op1_false); | |
903 | ft.intersect (op2_true); | |
90e88fd3 AM |
904 | r = ff; |
905 | r.union_ (tf); | |
906 | r.union_ (ft); | |
907 | } | |
908 | break; | |
909 | // A logical OR combines ranges from 2 boolean conditons. | |
910 | // c_2 = b_1 || b_2 | |
911 | case TRUTH_OR_EXPR: | |
912 | case BIT_IOR_EXPR: | |
913 | if (lhs.zero_p ()) | |
914 | { | |
915 | // An OR operation will only take the FALSE path if both | |
7d26a337 AM |
916 | // operands are false simlulateously, which means they should |
917 | // be intersected. !(x || y) == !x && !y | |
47ea02bb AM |
918 | r = op1_false; |
919 | r.intersect (op2_false); | |
90e88fd3 AM |
920 | } |
921 | else | |
922 | { | |
923 | // The TRUE side of an OR operation will be the union of | |
924 | // the other three combinations. | |
47ea02bb AM |
925 | int_range_max tt (op1_true); |
926 | tt.intersect (op2_true); | |
927 | int_range_max tf (op1_true); | |
928 | tf.intersect (op2_false); | |
929 | int_range_max ft (op1_false); | |
930 | ft.intersect (op2_true); | |
90e88fd3 AM |
931 | r = tt; |
932 | r.union_ (tf); | |
933 | r.union_ (ft); | |
934 | } | |
935 | break; | |
936 | default: | |
937 | gcc_unreachable (); | |
938 | } | |
939 | ||
4759e1e0 AM |
940 | if (idx) |
941 | tracer.trailer (idx, "logical_combine", true, NULL_TREE, r); | |
90e88fd3 AM |
942 | return true; |
943 | } | |
944 | ||
90e88fd3 AM |
945 | |
946 | // Given a logical STMT, calculate true and false ranges for each | |
947 | // potential path of NAME, assuming NAME came through the OP chain if | |
948 | // OP_IN_CHAIN is true. | |
949 | ||
950 | void | |
47ea02bb AM |
951 | gori_compute::compute_logical_operands (irange &true_range, irange &false_range, |
952 | gimple *stmt, | |
953 | const irange &lhs, | |
954 | tree name, fur_source &src, | |
955 | tree op, bool op_in_chain) | |
90e88fd3 | 956 | { |
7d26a337 | 957 | gimple *src_stmt = gimple_range_ssa_p (op) ? SSA_NAME_DEF_STMT (op) : NULL; |
47ea02bb | 958 | if (!op_in_chain || !src_stmt || chain_import_p (gimple_get_lhs (stmt), op)) |
90e88fd3 | 959 | { |
7d26a337 AM |
960 | // If op is not in the def chain, or defined in this block, |
961 | // use its known value on entry to the block. | |
47ea02bb AM |
962 | src.get_operand (true_range, name); |
963 | false_range = true_range; | |
4759e1e0 AM |
964 | unsigned idx; |
965 | if ((idx = tracer.header ("logical_operand"))) | |
966 | { | |
967 | print_generic_expr (dump_file, op, TDF_SLIM); | |
968 | fprintf (dump_file, " not in computation chain. Queried.\n"); | |
969 | tracer.trailer (idx, "logical_operand", true, NULL_TREE, true_range); | |
970 | } | |
90e88fd3 AM |
971 | return; |
972 | } | |
90e88fd3 | 973 | |
47ea02bb AM |
974 | enum tree_code code = gimple_expr_code (stmt); |
975 | // Optimize [0 = x | y], since neither operand can ever be non-zero. | |
976 | if ((code == BIT_IOR_EXPR || code == TRUTH_OR_EXPR) && lhs.zero_p ()) | |
977 | { | |
978 | if (!compute_operand_range (false_range, src_stmt, m_bool_zero, name, | |
979 | src)) | |
980 | src.get_operand (false_range, name); | |
981 | true_range = false_range; | |
982 | return; | |
983 | } | |
90e88fd3 | 984 | |
47ea02bb AM |
985 | // Optimize [1 = x & y], since neither operand can ever be zero. |
986 | if ((code == BIT_AND_EXPR || code == TRUTH_AND_EXPR) && lhs == m_bool_one) | |
987 | { | |
988 | if (!compute_operand_range (true_range, src_stmt, m_bool_one, name, src)) | |
989 | src.get_operand (true_range, name); | |
990 | false_range = true_range; | |
991 | return; | |
992 | } | |
90e88fd3 | 993 | |
47ea02bb AM |
994 | // Calculate ranges for true and false on both sides, since the false |
995 | // path is not always a simple inversion of the true side. | |
996 | if (!compute_operand_range (true_range, src_stmt, m_bool_one, name, src)) | |
997 | src.get_operand (true_range, name); | |
998 | if (!compute_operand_range (false_range, src_stmt, m_bool_zero, name, src)) | |
999 | src.get_operand (false_range, name); | |
90e88fd3 AM |
1000 | } |
1001 | ||
1002 | // Calculate a range for NAME from the operand 1 position of STMT | |
1003 | // assuming the result of the statement is LHS. Return the range in | |
1004 | // R, or false if no range could be calculated. | |
1005 | ||
1006 | bool | |
1007 | gori_compute::compute_operand1_range (irange &r, gimple *stmt, | |
47ea02bb AM |
1008 | const irange &lhs, tree name, |
1009 | fur_source &src) | |
90e88fd3 AM |
1010 | { |
1011 | int_range_max op1_range, op2_range; | |
1012 | tree op1 = gimple_range_operand1 (stmt); | |
1013 | tree op2 = gimple_range_operand2 (stmt); | |
1014 | ||
47ea02bb AM |
1015 | // Fetch the known range for op1 in this block. |
1016 | src.get_operand (op1_range, op1); | |
90e88fd3 | 1017 | |
47ea02bb | 1018 | // Now range-op calcuate and put that result in r. |
90e88fd3 AM |
1019 | if (op2) |
1020 | { | |
47ea02bb | 1021 | src.get_operand (op2_range, op2); |
90e88fd3 AM |
1022 | if (!gimple_range_calc_op1 (r, stmt, lhs, op2_range)) |
1023 | return false; | |
1024 | } | |
1025 | else | |
1026 | { | |
1027 | // We pass op1_range to the unary operation. Nomally it's a | |
1028 | // hidden range_for_type parameter, but sometimes having the | |
1029 | // actual range can result in better information. | |
1030 | if (!gimple_range_calc_op1 (r, stmt, lhs, op1_range)) | |
1031 | return false; | |
1032 | } | |
1033 | ||
4759e1e0 AM |
1034 | unsigned idx; |
1035 | if ((idx = tracer.header ("compute op 1 ("))) | |
1036 | { | |
1037 | print_generic_expr (dump_file, op1, TDF_SLIM); | |
1038 | fprintf (dump_file, ") at "); | |
1039 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
1040 | tracer.print (idx, "LHS ="); | |
1041 | lhs.dump (dump_file); | |
1042 | if (op2 && TREE_CODE (op2) == SSA_NAME) | |
1043 | { | |
1044 | fprintf (dump_file, ", "); | |
1045 | print_generic_expr (dump_file, op2, TDF_SLIM); | |
1046 | fprintf (dump_file, " = "); | |
1047 | op2_range.dump (dump_file); | |
1048 | } | |
1049 | fprintf (dump_file, "\n"); | |
1050 | tracer.print (idx, "Computes "); | |
1051 | print_generic_expr (dump_file, op1, TDF_SLIM); | |
1052 | fprintf (dump_file, " = "); | |
1053 | r.dump (dump_file); | |
1054 | fprintf (dump_file, " intersect Known range : "); | |
1055 | op1_range.dump (dump_file); | |
1056 | fputc ('\n', dump_file); | |
1057 | } | |
47ea02bb AM |
1058 | // Intersect the calculated result with the known result and return if done. |
1059 | if (op1 == name) | |
1060 | { | |
1061 | r.intersect (op1_range); | |
4759e1e0 AM |
1062 | if (idx) |
1063 | tracer.trailer (idx, "produces ", true, name, r); | |
47ea02bb AM |
1064 | return true; |
1065 | } | |
1066 | // If the calculation continues, we're using op1_range as the new LHS. | |
90e88fd3 AM |
1067 | op1_range.intersect (r); |
1068 | ||
4759e1e0 AM |
1069 | if (idx) |
1070 | tracer.trailer (idx, "produces ", true, op1, op1_range); | |
90e88fd3 | 1071 | gimple *src_stmt = SSA_NAME_DEF_STMT (op1); |
47ea02bb AM |
1072 | gcc_checking_assert (src_stmt); |
1073 | ||
90e88fd3 | 1074 | // Then feed this range back as the LHS of the defining statement. |
47ea02bb | 1075 | return compute_operand_range (r, src_stmt, op1_range, name, src); |
90e88fd3 AM |
1076 | } |
1077 | ||
1078 | ||
1079 | // Calculate a range for NAME from the operand 2 position of S | |
1080 | // assuming the result of the statement is LHS. Return the range in | |
1081 | // R, or false if no range could be calculated. | |
1082 | ||
1083 | bool | |
1084 | gori_compute::compute_operand2_range (irange &r, gimple *stmt, | |
47ea02bb AM |
1085 | const irange &lhs, tree name, |
1086 | fur_source &src) | |
90e88fd3 AM |
1087 | { |
1088 | int_range_max op1_range, op2_range; | |
1089 | tree op1 = gimple_range_operand1 (stmt); | |
1090 | tree op2 = gimple_range_operand2 (stmt); | |
1091 | ||
47ea02bb AM |
1092 | src.get_operand (op1_range, op1); |
1093 | src.get_operand (op2_range, op2); | |
90e88fd3 AM |
1094 | |
1095 | // Intersect with range for op2 based on lhs and op1. | |
46f4a397 AM |
1096 | if (!gimple_range_calc_op2 (r, stmt, lhs, op1_range)) |
1097 | return false; | |
90e88fd3 | 1098 | |
4759e1e0 AM |
1099 | unsigned idx; |
1100 | if ((idx = tracer.header ("compute op 2 ("))) | |
1101 | { | |
1102 | print_generic_expr (dump_file, op2, TDF_SLIM); | |
1103 | fprintf (dump_file, ") at "); | |
1104 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
1105 | tracer.print (idx, "LHS = "); | |
1106 | lhs.dump (dump_file); | |
1107 | if (TREE_CODE (op1) == SSA_NAME) | |
1108 | { | |
1109 | fprintf (dump_file, ", "); | |
1110 | print_generic_expr (dump_file, op1, TDF_SLIM); | |
1111 | fprintf (dump_file, " = "); | |
1112 | op1_range.dump (dump_file); | |
1113 | } | |
1114 | fprintf (dump_file, "\n"); | |
1115 | tracer.print (idx, "Computes "); | |
1116 | print_generic_expr (dump_file, op2, TDF_SLIM); | |
1117 | fprintf (dump_file, " = "); | |
1118 | r.dump (dump_file); | |
1119 | fprintf (dump_file, " intersect Known range : "); | |
1120 | op2_range.dump (dump_file); | |
1121 | fputc ('\n', dump_file); | |
1122 | } | |
47ea02bb AM |
1123 | // Intersect the calculated result with the known result and return if done. |
1124 | if (op2 == name) | |
90e88fd3 | 1125 | { |
47ea02bb | 1126 | r.intersect (op2_range); |
4759e1e0 AM |
1127 | if (idx) |
1128 | tracer.trailer (idx, " produces ", true, NULL_TREE, r); | |
47ea02bb | 1129 | return true; |
90e88fd3 | 1130 | } |
47ea02bb AM |
1131 | // If the calculation continues, we're using op2_range as the new LHS. |
1132 | op2_range.intersect (r); | |
1133 | ||
4759e1e0 AM |
1134 | if (idx) |
1135 | tracer.trailer (idx, " produces ", true, op2, op2_range); | |
47ea02bb AM |
1136 | gimple *src_stmt = SSA_NAME_DEF_STMT (op2); |
1137 | gcc_checking_assert (src_stmt); | |
1138 | // gcc_checking_assert (!is_import_p (op2, find.bb)); | |
1139 | ||
90e88fd3 | 1140 | // Then feed this range back as the LHS of the defining statement. |
47ea02bb | 1141 | return compute_operand_range (r, src_stmt, op2_range, name, src); |
90e88fd3 AM |
1142 | } |
1143 | ||
1144 | // Calculate a range for NAME from both operand positions of S | |
1145 | // assuming the result of the statement is LHS. Return the range in | |
1146 | // R, or false if no range could be calculated. | |
1147 | ||
1148 | bool | |
47ea02bb AM |
1149 | gori_compute::compute_operand1_and_operand2_range (irange &r, |
1150 | gimple *stmt, | |
1151 | const irange &lhs, | |
1152 | tree name, | |
1153 | fur_source &src) | |
90e88fd3 AM |
1154 | { |
1155 | int_range_max op_range; | |
1156 | ||
1157 | // Calculate a good a range for op2. Since op1 == op2, this will | |
1158 | // have already included whatever the actual range of name is. | |
47ea02bb | 1159 | if (!compute_operand2_range (op_range, stmt, lhs, name, src)) |
90e88fd3 AM |
1160 | return false; |
1161 | ||
1162 | // Now get the range thru op1. | |
47ea02bb | 1163 | if (!compute_operand1_range (r, stmt, lhs, name, src)) |
90e88fd3 AM |
1164 | return false; |
1165 | ||
47ea02bb AM |
1166 | // Both operands have to be simultaneously true, so perform an intersection. |
1167 | r.intersect (op_range); | |
90e88fd3 AM |
1168 | return true; |
1169 | } | |
786188e8 | 1170 | // Return TRUE if a range can be calculated or recomputed for NAME on edge E. |
90e88fd3 AM |
1171 | |
1172 | bool | |
7f359556 | 1173 | gori_compute::has_edge_range_p (tree name, edge e) |
90e88fd3 | 1174 | { |
786188e8 AM |
1175 | // Check if NAME is an export or can be recomputed. |
1176 | if (e) | |
1177 | return is_export_p (name, e->src) || may_recompute_p (name, e); | |
90e88fd3 | 1178 | |
786188e8 AM |
1179 | // If no edge is specified, check if NAME can have a range calculated |
1180 | // on any edge. | |
1181 | return is_export_p (name) || may_recompute_p (name); | |
2dd1f944 AM |
1182 | } |
1183 | ||
90e88fd3 AM |
1184 | // Dump what is known to GORI computes to listing file F. |
1185 | ||
1186 | void | |
1187 | gori_compute::dump (FILE *f) | |
1188 | { | |
28ceee1b | 1189 | gori_map::dump (f); |
90e88fd3 AM |
1190 | } |
1191 | ||
786188e8 AM |
1192 | // Return TRUE if NAME can be recomputed on edge E. If any direct dependant |
1193 | // is exported on edge E, it may change the computed value of NAME. | |
1194 | ||
1195 | bool | |
1196 | gori_compute::may_recompute_p (tree name, edge e) | |
1197 | { | |
1198 | tree dep1 = depend1 (name); | |
1199 | tree dep2 = depend2 (name); | |
1200 | ||
1201 | // If the first dependency is not set, there is no recompuation. | |
1202 | if (!dep1) | |
1203 | return false; | |
1204 | ||
1205 | // Don't recalculate PHIs or statements with side_effects. | |
1206 | gimple *s = SSA_NAME_DEF_STMT (name); | |
1207 | if (is_a<gphi *> (s) || gimple_has_side_effects (s)) | |
1208 | return false; | |
1209 | ||
1210 | // If edge is specified, check if NAME can be recalculated on that edge. | |
1211 | if (e) | |
1212 | return ((is_export_p (dep1, e->src)) | |
1213 | || (dep2 && is_export_p (dep2, e->src))); | |
1214 | ||
1215 | return (is_export_p (dep1)) || (dep2 && is_export_p (dep2)); | |
1216 | } | |
1217 | ||
90e88fd3 AM |
1218 | // Calculate a range on edge E and return it in R. Try to evaluate a |
1219 | // range for NAME on this edge. Return FALSE if this is either not a | |
1220 | // control edge or NAME is not defined by this edge. | |
1221 | ||
1222 | bool | |
47ea02bb AM |
1223 | gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name, |
1224 | range_query &q) | |
90e88fd3 AM |
1225 | { |
1226 | int_range_max lhs; | |
4759e1e0 | 1227 | unsigned idx; |
90e88fd3 | 1228 | |
053e1d64 | 1229 | if ((e->flags & m_not_executable_flag)) |
73cf73af AM |
1230 | { |
1231 | r.set_undefined (); | |
1232 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1233 | fprintf (dump_file, "Outgoing edge %d->%d unexecutable.\n", | |
1234 | e->src->index, e->dest->index); | |
1235 | return true; | |
1236 | } | |
1237 | ||
90e88fd3 AM |
1238 | gcc_checking_assert (gimple_range_ssa_p (name)); |
1239 | // Determine if there is an outgoing edge. | |
1240 | gimple *stmt = outgoing.edge_range_p (lhs, e); | |
1241 | if (!stmt) | |
1242 | return false; | |
1243 | ||
87f9ac93 | 1244 | fur_stmt src (stmt, &q); |
90e88fd3 | 1245 | // If NAME can be calculated on the edge, use that. |
28ceee1b | 1246 | if (is_export_p (name, e->src)) |
6e02de94 | 1247 | { |
4759e1e0 AM |
1248 | bool res; |
1249 | if ((idx = tracer.header ("outgoing_edge"))) | |
1250 | { | |
1251 | fprintf (dump_file, " for "); | |
1252 | print_generic_expr (dump_file, name, TDF_SLIM); | |
1253 | fprintf (dump_file, " on edge %d->%d\n", | |
1254 | e->src->index, e->dest->index); | |
1255 | } | |
1256 | if ((res = compute_operand_range (r, stmt, lhs, name, src))) | |
6e02de94 AM |
1257 | { |
1258 | // Sometimes compatible types get interchanged. See PR97360. | |
1259 | // Make sure we are returning the type of the thing we asked for. | |
1260 | if (!r.undefined_p () && r.type () != TREE_TYPE (name)) | |
1261 | { | |
1262 | gcc_checking_assert (range_compatible_p (r.type (), | |
1263 | TREE_TYPE (name))); | |
1264 | range_cast (r, TREE_TYPE (name)); | |
1265 | } | |
6e02de94 | 1266 | } |
4759e1e0 AM |
1267 | if (idx) |
1268 | tracer.trailer (idx, "outgoing_edge", res, name, r); | |
1269 | return res; | |
6e02de94 | 1270 | } |
786188e8 AM |
1271 | // If NAME isn't exported, check if it can be recomputed. |
1272 | else if (may_recompute_p (name, e)) | |
1273 | { | |
1274 | gimple *def_stmt = SSA_NAME_DEF_STMT (name); | |
1275 | ||
4759e1e0 | 1276 | if ((idx = tracer.header ("recomputation"))) |
786188e8 | 1277 | { |
4759e1e0 | 1278 | fprintf (dump_file, " attempt on edge %d->%d for ", |
786188e8 | 1279 | e->src->index, e->dest->index); |
4759e1e0 | 1280 | print_gimple_stmt (dump_file, def_stmt, 0, TDF_SLIM); |
786188e8 | 1281 | } |
8cbaa093 | 1282 | // Simply calculate DEF_STMT on edge E using the range query Q. |
786188e8 | 1283 | fold_range (r, def_stmt, e, &q); |
4759e1e0 AM |
1284 | if (idx) |
1285 | tracer.trailer (idx, "recomputation", true, name, r); | |
786188e8 AM |
1286 | return true; |
1287 | } | |
90e88fd3 AM |
1288 | return false; |
1289 | } | |
1290 | ||
c2164470 AM |
1291 | |
1292 | // ------------------------------------------------------------------------ | |
1293 | // GORI iterator. Although we have bitmap iterators, don't expose that it | |
1294 | // is currently a bitmap. Use an export iterator to hide future changes. | |
1295 | ||
1296 | // Construct a basic iterator over an export bitmap. | |
1297 | ||
1298 | gori_export_iterator::gori_export_iterator (bitmap b) | |
1299 | { | |
1300 | bm = b; | |
1301 | if (b) | |
1302 | bmp_iter_set_init (&bi, b, 1, &y); | |
1303 | } | |
1304 | ||
1305 | ||
1306 | // Move to the next export bitmap spot. | |
1307 | ||
1308 | void | |
1309 | gori_export_iterator::next () | |
1310 | { | |
1311 | bmp_iter_next (&bi, &y); | |
1312 | } | |
1313 | ||
1314 | ||
1315 | // Fetch the name of the next export in the export list. Return NULL if | |
1316 | // iteration is done. | |
1317 | ||
1318 | tree | |
1319 | gori_export_iterator::get_name () | |
1320 | { | |
1321 | if (!bm) | |
1322 | return NULL_TREE; | |
1323 | ||
1324 | while (bmp_iter_set (&bi, &y)) | |
1325 | { | |
1326 | tree t = ssa_name (y); | |
1327 | if (t) | |
1328 | return t; | |
1329 | next (); | |
1330 | } | |
1331 | return NULL_TREE; | |
1332 | } |