re PR c++/84691 (internal compiler error: in poplevel_class, at cp/name-lookup.c...
[official-gcc.git] / gcc / sese.c
blob5e76a7e033a0526d5105e0385057ddb39b4e1ee9
1 /* Single entry single exit control flow regions.
2 Copyright (C) 2008-2018 Free Software Foundation, Inc.
3 Contributed by Jan Sjodin <jan.sjodin@amd.com> and
4 Sebastian Pop <sebastian.pop@amd.com>.
6 This file is part of GCC.
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.
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.
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/>. */
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 "cfghooks.h"
29 #include "tree-pass.h"
30 #include "ssa.h"
31 #include "tree-pretty-print.h"
32 #include "fold-const.h"
33 #include "gimplify.h"
34 #include "gimple-iterator.h"
35 #include "gimple-pretty-print.h"
36 #include "gimplify-me.h"
37 #include "tree-cfg.h"
38 #include "tree-ssa-loop.h"
39 #include "tree-into-ssa.h"
40 #include "cfgloop.h"
41 #include "tree-data-ref.h"
42 #include "tree-scalar-evolution.h"
43 #include "tree-ssa-propagate.h"
44 #include "cfganal.h"
45 #include "sese.h"
47 /* For a USE in BB, if BB is outside REGION, mark the USE in the
48 LIVEOUTS set. */
50 static void
51 sese_build_liveouts_use (sese_info_p region, bitmap liveouts, basic_block bb,
52 tree use)
54 gcc_assert (!bb_in_sese_p (bb, region->region));
55 if (TREE_CODE (use) != SSA_NAME)
56 return;
58 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
60 if (!def_bb || !bb_in_sese_p (def_bb, region->region))
61 return;
63 unsigned ver = SSA_NAME_VERSION (use);
64 bitmap_set_bit (liveouts, ver);
67 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
68 used in BB that is outside of the REGION. */
70 static void
71 sese_build_liveouts_bb (sese_info_p region, basic_block bb)
73 ssa_op_iter iter;
74 use_operand_p use_p;
76 for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
77 gsi_next (&bsi))
78 FOR_EACH_PHI_ARG (use_p, bsi.phi (), iter, SSA_OP_USE)
79 sese_build_liveouts_use (region, region->liveout,
80 bb, USE_FROM_PTR (use_p));
82 for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
83 gsi_next (&bsi))
85 gimple *stmt = gsi_stmt (bsi);
87 bitmap liveouts = region->liveout;
88 if (is_gimple_debug (stmt))
89 liveouts = region->debug_liveout;
91 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
92 sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
96 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
97 are not marked as liveouts. */
99 static void
100 sese_reset_debug_liveouts (sese_info_p region)
102 bitmap_iterator bi;
103 unsigned i;
104 EXECUTE_IF_AND_COMPL_IN_BITMAP (region->debug_liveout, region->liveout,
105 0, i, bi)
107 tree name = ssa_name (i);
108 auto_vec<gimple *, 4> stmts;
109 gimple *use_stmt;
110 imm_use_iterator use_iter;
111 FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name)
113 if (! is_gimple_debug (use_stmt)
114 || bb_in_sese_p (gimple_bb (use_stmt), region->region))
115 continue;
116 stmts.safe_push (use_stmt);
118 while (!stmts.is_empty ())
120 gimple *stmt = stmts.pop ();
121 gimple_debug_bind_reset_value (stmt);
122 update_stmt (stmt);
127 /* Build the LIVEOUTS of REGION: the set of variables defined inside
128 and used outside the REGION. */
130 void
131 sese_build_liveouts (sese_info_p region)
133 basic_block bb;
135 gcc_assert (region->liveout == NULL
136 && region->debug_liveout == NULL);
138 region->liveout = BITMAP_ALLOC (NULL);
139 region->debug_liveout = BITMAP_ALLOC (NULL);
141 /* FIXME: We could start iterating form the successor of sese. */
142 FOR_EACH_BB_FN (bb, cfun)
143 if (!bb_in_sese_p (bb, region->region))
144 sese_build_liveouts_bb (region, bb);
147 /* Builds a new SESE region from edges ENTRY and EXIT. */
149 sese_info_p
150 new_sese_info (edge entry, edge exit)
152 sese_info_p region = XNEW (struct sese_info_t);
154 region->region.entry = entry;
155 region->region.exit = exit;
156 region->liveout = NULL;
157 region->debug_liveout = NULL;
158 region->params.create (3);
159 region->rename_map = new hash_map <tree, tree>;
160 region->bbs.create (3);
162 return region;
165 /* Deletes REGION. */
167 void
168 free_sese_info (sese_info_p region)
170 region->params.release ();
171 BITMAP_FREE (region->liveout);
172 BITMAP_FREE (region->debug_liveout);
174 delete region->rename_map;
175 region->rename_map = NULL;
176 region->bbs.release ();
178 XDELETE (region);
181 /* Add exit phis for USE on EXIT. */
183 static void
184 sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
186 gphi *phi = create_phi_node (NULL_TREE, exit);
187 create_new_def_for (use, phi, gimple_phi_result_ptr (phi));
188 add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION);
189 add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
190 update_stmt (phi);
193 /* Insert in the block BB phi nodes for variables defined in REGION
194 and used outside the REGION. The code generation moves REGION in
195 the else clause of an "if (1)" and generates code in the then
196 clause that is at this point empty:
198 | if (1)
199 | empty;
200 | else
201 | REGION;
204 void
205 sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb,
206 edge false_e, edge true_e)
208 if (MAY_HAVE_DEBUG_BIND_STMTS)
209 sese_reset_debug_liveouts (region);
211 unsigned i;
212 bitmap_iterator bi;
213 EXECUTE_IF_SET_IN_BITMAP (region->liveout, 0, i, bi)
214 if (!virtual_operand_p (ssa_name (i)))
215 sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
218 /* Returns the outermost loop in SCOP that contains BB. */
220 struct loop *
221 outermost_loop_in_sese_1 (sese_l &region, basic_block bb)
223 struct loop *nest;
225 nest = bb->loop_father;
226 while (loop_outer (nest)
227 && loop_in_sese_p (loop_outer (nest), region))
228 nest = loop_outer (nest);
230 return nest;
233 /* Same as outermost_loop_in_sese_1, returns the outermost loop
234 containing BB in REGION, but makes sure that the returned loop
235 belongs to the REGION, and so this returns the first loop in the
236 REGION when the loop containing BB does not belong to REGION. */
238 loop_p
239 outermost_loop_in_sese (sese_l &region, basic_block bb)
241 loop_p nest = outermost_loop_in_sese_1 (region, bb);
243 if (loop_in_sese_p (nest, region))
244 return nest;
246 /* When the basic block BB does not belong to a loop in the region,
247 return the first loop in the region. */
248 nest = nest->inner;
249 while (nest)
250 if (loop_in_sese_p (nest, region))
251 break;
252 else
253 nest = nest->next;
255 gcc_assert (nest);
256 return nest;
259 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
261 edge
262 get_true_edge_from_guard_bb (basic_block bb)
264 edge e;
265 edge_iterator ei;
267 FOR_EACH_EDGE (e, ei, bb->succs)
268 if (e->flags & EDGE_TRUE_VALUE)
269 return e;
271 gcc_unreachable ();
272 return NULL;
275 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
277 edge
278 get_false_edge_from_guard_bb (basic_block bb)
280 edge e;
281 edge_iterator ei;
283 FOR_EACH_EDGE (e, ei, bb->succs)
284 if (!(e->flags & EDGE_TRUE_VALUE))
285 return e;
287 gcc_unreachable ();
288 return NULL;
291 /* Moves REGION in a condition expression:
292 | if (1)
294 | else
295 | REGION;
298 ifsese
299 move_sese_in_condition (sese_info_p region)
301 basic_block region_entry_dest = region->region.entry->dest;
302 basic_block pred_block = split_edge (region->region.entry);
303 basic_block merge_block = split_edge (region->region.exit);
305 edge true_edge = make_edge (pred_block, merge_block, EDGE_TRUE_VALUE);
306 edge false_edge = find_edge (pred_block, region_entry_dest);
307 false_edge->flags &= ~EDGE_FALLTHRU;
308 false_edge->flags |= EDGE_FALSE_VALUE;
309 gimple_stmt_iterator gsi = gsi_last_bb (pred_block);
310 gcond *cond = gimple_build_cond (NE_EXPR, integer_one_node, integer_zero_node,
311 NULL_TREE, NULL_TREE);
312 gsi_insert_after (&gsi, cond, GSI_CONTINUE_LINKING);
313 if (dom_info_available_p (CDI_DOMINATORS))
314 set_immediate_dominator (CDI_DOMINATORS, merge_block, pred_block);
316 ifsese if_region = XNEW (ifsese_s);
317 if_region->region = XCNEW (sese_info_t);
318 if_region->true_region = XCNEW (sese_info_t);
319 if_region->false_region = XCNEW (sese_info_t);
320 if_region->region->region.entry = single_pred_edge (pred_block);
321 if_region->region->region.exit = single_succ_edge (merge_block);
322 if_region->false_region->region.entry = false_edge;
323 if_region->false_region->region.exit = region->region.exit;
324 if_region->true_region->region.entry = true_edge;
325 if_region->true_region->region.exit
326 = single_succ_edge (split_edge (true_edge));
328 region->region = if_region->false_region->region;
330 return if_region;
333 /* Replaces the condition of the IF_REGION with CONDITION:
334 | if (CONDITION)
335 | true_region;
336 | else
337 | false_region;
340 void
341 set_ifsese_condition (ifsese if_region, tree condition)
343 sese_info_p region = if_region->region;
344 edge entry = region->region.entry;
345 basic_block bb = entry->dest;
346 gimple *last = last_stmt (bb);
347 gimple_stmt_iterator gsi = gsi_last_bb (bb);
348 gcond *cond_stmt;
350 gcc_assert (gimple_code (last) == GIMPLE_COND);
352 gsi_remove (&gsi, true);
353 gsi = gsi_last_bb (bb);
354 condition = force_gimple_operand_gsi (&gsi, condition, true, NULL,
355 false, GSI_NEW_STMT);
356 cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE);
357 gsi = gsi_last_bb (bb);
358 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
361 /* Return true when T is defined outside REGION or when no definitions are
362 variant in REGION. When HAS_VDEFS is a valid pointer, sets HAS_VDEFS to true
363 when T depends on memory that may change in REGION. */
365 bool
366 invariant_in_sese_p_rec (tree t, const sese_l &region, bool *has_vdefs)
368 if (!defined_in_sese_p (t, region))
369 return true;
371 gimple *stmt = SSA_NAME_DEF_STMT (t);
373 if (gimple_code (stmt) == GIMPLE_PHI
374 || gimple_code (stmt) == GIMPLE_CALL)
375 return false;
377 /* VDEF is variant when it is in the region. */
378 if (gimple_vdef (stmt))
380 if (has_vdefs)
381 *has_vdefs = true;
382 return false;
385 /* A VUSE may or may not be variant following the VDEFs. */
386 if (tree vuse = gimple_vuse (stmt))
387 return invariant_in_sese_p_rec (vuse, region, has_vdefs);
389 ssa_op_iter iter;
390 use_operand_p use_p;
391 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
393 tree use = USE_FROM_PTR (use_p);
395 if (!defined_in_sese_p (use, region))
396 continue;
398 if (!invariant_in_sese_p_rec (use, region, has_vdefs))
399 return false;
402 return true;
405 /* Return true when DEF can be analyzed in REGION by the scalar
406 evolution analyzer. */
408 bool
409 scev_analyzable_p (tree def, sese_l &region)
411 loop_p loop;
412 tree scev;
413 tree type = TREE_TYPE (def);
415 /* When Graphite generates code for a scev, the code generator
416 expresses the scev in function of a single induction variable.
417 This is unsafe for floating point computations, as it may replace
418 a floating point sum reduction with a multiplication. The
419 following test returns false for non integer types to avoid such
420 problems. */
421 if (!INTEGRAL_TYPE_P (type)
422 && !POINTER_TYPE_P (type))
423 return false;
425 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
426 scev = scalar_evolution_in_region (region, loop, def);
428 return (!chrec_contains_undetermined (scev)
429 && (TREE_CODE (scev) != SSA_NAME
430 || !defined_in_sese_p (scev, region))
431 && scev_is_linear_expression (scev)
432 && (! loop
433 || ! loop_in_sese_p (loop, region)
434 || ! chrec_contains_symbols_defined_in_loop (scev, loop->num)));
437 /* Returns the scalar evolution of T in REGION. Every variable that
438 is not defined in the REGION is considered a parameter. */
440 tree
441 scalar_evolution_in_region (const sese_l &region, loop_p loop, tree t)
443 /* SCOP parameters. */
444 if (TREE_CODE (t) == SSA_NAME
445 && !defined_in_sese_p (t, region))
446 return t;
448 if (!loop_in_sese_p (loop, region))
449 loop = NULL;
451 return instantiate_scev (region.entry, loop,
452 analyze_scalar_evolution (loop, t));
455 /* Return true if BB is empty, contains only DEBUG_INSNs. */
457 bool
458 sese_trivially_empty_bb_p (basic_block bb)
460 gimple_stmt_iterator gsi;
462 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
463 if (!is_gimple_debug (gsi_stmt (gsi))
464 && gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
465 return false;
467 return true;
470 /* Pretty print edge E to FILE. */
472 void
473 print_edge (FILE *file, const_edge e)
475 fprintf (file, "edge (bb_%d, bb_%d)", e->src->index, e->dest->index);
478 /* Pretty print sese S to FILE. */
480 void
481 print_sese (FILE *file, const sese_l &s)
483 fprintf (file, "(entry_"); print_edge (file, s.entry);
484 fprintf (file, ", exit_"); print_edge (file, s.exit);
485 fprintf (file, ")\n");
488 /* Pretty print edge E to STDERR. */
490 DEBUG_FUNCTION void
491 debug_edge (const_edge e)
493 print_edge (stderr, e);
496 /* Pretty print sese S to STDERR. */
498 DEBUG_FUNCTION void
499 debug_sese (const sese_l &s)
501 print_sese (stderr, s);