1// Implementation of function-related RTL SSA functions -*- C++ -*-
2// Copyright (C) 2020-2024 Free Software Foundation, Inc.
3//
4// This file is part of GCC.
5//
6// GCC is free software; you can redistribute it and/or modify it under
7// the terms of the GNU General Public License as published by the Free
8// Software Foundation; either version 3, or (at your option) any later
9// version.
10//
11// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12// WARRANTY; without even the implied warranty of MERCHANTABILITY or
13// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14// for more details.
15//
16// You should have received a copy of the GNU General Public License
17// along with GCC; see the file COPYING3. If not see
18// <http://www.gnu.org/licenses/>.
19
20#define INCLUDE_ALGORITHM
21#define INCLUDE_FUNCTIONAL
22#include "config.h"
23#include "system.h"
24#include "coretypes.h"
25#include "backend.h"
26#include "rtl.h"
27#include "df.h"
28#include "rtl-ssa.h"
29#include "rtl-ssa/internals.h"
30#include "rtl-ssa/internals.inl"
31
32using namespace rtl_ssa;
33
34function_info::function_info (function *fn)
35 : m_fn (fn), m_clobbered_by_calls ()
36{
37 // Force the alignment to be obstack_alignment. Everything else is normal.
38 obstack_specify_allocation (&m_obstack, OBSTACK_CHUNK_SIZE,
39 obstack_alignment, obstack_chunk_alloc,
40 obstack_chunk_free);
41 obstack_specify_allocation (&m_temp_obstack, OBSTACK_CHUNK_SIZE,
42 obstack_alignment, obstack_chunk_alloc,
43 obstack_chunk_free);
44
45 // Record the start of the obstacks.
46 m_obstack_start = XOBNEWVAR (&m_obstack, char, 0);
47 m_temp_obstack_start = XOBNEWVAR (&m_temp_obstack, char, 0);
48
49 init_function_data ();
50 process_all_blocks ();
51 simplify_phis ();
52}
53
54function_info::~function_info ()
55{
56 // Anything using the temporary obstack should free it afterwards,
57 // preferably via temp_watermark ().
58 gcc_assert (XOBNEWVAR (&m_temp_obstack, char, 0) == m_temp_obstack_start);
59
60 obstack_free (&m_temp_obstack, nullptr);
61 obstack_free (&m_obstack, nullptr);
62}
63
64// See the comment above the declaration.
65void
66function_info::print (pretty_printer *pp) const
67{
68 pp_string (pp, "Function: ");
69 pp_string (pp, function_name (m_fn));
70 for (ebb_info *ebb : ebbs ())
71 {
72 pp_newline (pp);
73 pp_newline_and_indent (pp, 0);
74 pp_ebb (pp, ebb);
75 }
76}
77
78// Initialize all member variables in preparation for (re)building
79// SSA form from scratch.
80void
81function_info::init_function_data ()
82{
83 m_next_artificial_uid = -1;
84 m_next_phi_uid = 0;
85 m_num_regs = max_reg_num ();
86 m_defs.safe_grow_cleared (len: m_num_regs + 1);
87 m_bbs.safe_grow_cleared (last_basic_block_for_fn (m_fn));
88 m_first_bb = nullptr;
89 m_last_bb = nullptr;
90 m_first_insn = nullptr;
91 m_last_insn = nullptr;
92 m_last_nondebug_insn = nullptr;
93 m_free_phis = nullptr;
94}
95
96// The initial phase of the phi simplification process. The cumulative
97// effect of the initial phase is to set up ASSUMED_VALUES such that,
98// for a phi P with uid ID:
99//
100// - if we think all inputs to P have the same value, ASSUMED_VALUES[ID]
101// is that value
102//
103// - otherwise, ASSUMED_VALUES[ID] is P.
104//
105// This has already been done for phis with a lower uid than PHI,
106// initially making optimistic assumptions about backedge inputs.
107// Now do the same for PHI. If this might invalidate any assumptions
108// made for earlier phis, add the uids of those phis to WORKLIST.
109void
110function_info::simplify_phi_setup (phi_info *phi, set_info **assumed_values,
111 bitmap worklist)
112{
113 // If all non-backedge inputs have the same value, set NEW_VALUE
114 // to that value. Otherwise set NEW_VALUE to PHI, to indicate
115 // that PHI cannot be simplified.
116 unsigned int phi_uid = phi->uid ();
117 bool is_first_input = true;
118 set_info *new_value = nullptr;
119 machine_mode phi_mode = phi->mode ();
120 for (use_info *input : phi->inputs ())
121 {
122 set_info *def = input->def ();
123
124 if (auto *input_phi = safe_dyn_cast<phi_info *> (p: def))
125 {
126 // Ignore backedges for now.
127 unsigned int input_phi_uid = input_phi->uid ();
128 if (phi_uid <= input_phi_uid)
129 continue;
130
131 def = assumed_values[input_phi_uid];
132 }
133
134 // Compare this definition with previous ones.
135 if (is_first_input)
136 {
137 new_value = def;
138 is_first_input = false;
139 }
140 else if (new_value != def)
141 new_value = phi;
142
143 // If the input has a known mode (i.e. not BLKmode), make sure
144 // that the phi's mode is at least as large.
145 if (def)
146 phi_mode = combine_modes (mode1: phi_mode, mode2: def->mode ());
147 }
148 if (phi->mode () != phi_mode)
149 phi->set_mode (phi_mode);
150
151 // Since we use a reverse postorder traversal, no phi can consist
152 // entirely of backedges.
153 gcc_checking_assert (!is_first_input);
154 assumed_values[phi_uid] = new_value;
155
156 // See whether any assumptions for earlier phis are now invalid.
157 simplify_phi_propagate (phi, assumed_values, nullptr, worklist);
158}
159
160// The propagation phase of the phi simplification process, with
161// ASSUMED_VALUES as described above simplify_phi_setup. Iteratively
162// update the phis that use PHI based on PHI's entry in ASSUMED_VALUES.
163// If CURR_WORKLIST is null, consider only phi uses with a lower uid
164// than PHI, otherwise consider all phi uses.
165//
166// If a phi with a higher uid than PHI needs updating, add its uid to
167// CURR_WORKLIST; if a phi with a lower uid than PHI needs updating,
168// add its uid to NEXT_WORKLIST.
169void
170function_info::simplify_phi_propagate (phi_info *phi,
171 set_info **assumed_values,
172 bitmap curr_worklist,
173 bitmap next_worklist)
174{
175 // Go through each phi user of PHI to see whether it needs updating.
176 unsigned int phi_uid = phi->uid ();
177 machine_mode phi_mode = phi->mode ();
178 set_info *phi_value = assumed_values[phi_uid];
179 for (use_info *use : phi->phi_uses ())
180 {
181 phi_info *user_phi = use->phi ();
182
183 // Propagate the phi's new mode to all phi users. Insn uses should
184 // not be updated, since their modes reflect a property of the insns
185 // rather than the phi.
186 if (use->mode () != phi_mode)
187 use->set_mode (phi_mode);
188
189 if (user_phi == phi)
190 continue;
191
192 // If this is a phi we should be looking at, see whether it needs
193 // an update.
194 unsigned int user_phi_uid = user_phi->uid ();
195 if (user_phi_uid < phi_uid || curr_worklist)
196 {
197 bool needs_update = false;
198
199 // Make sure that USER_PHI's mode is at least as big as PHI_MODE.
200 machine_mode user_phi_mode = user_phi->mode ();
201 machine_mode new_mode = combine_modes (mode1: user_phi_mode, mode2: phi_mode);
202 if (user_phi_mode != new_mode)
203 {
204 user_phi->set_mode (new_mode);
205 needs_update = true;
206 }
207
208 // If USER_PHI optimistically assumed an incorrect value,
209 // adjust it now.
210 if (assumed_values[user_phi_uid] != user_phi
211 && assumed_values[user_phi_uid] != phi_value)
212 {
213 assumed_values[user_phi_uid] = user_phi;
214 needs_update = true;
215 }
216
217 if (needs_update)
218 {
219 if (user_phi_uid < phi_uid)
220 bitmap_set_bit (next_worklist, user_phi_uid);
221 else
222 bitmap_set_bit (curr_worklist, user_phi_uid);
223 }
224 }
225 }
226}
227
228// Update the modes of all phis so that they are at least as big as
229// all inputs. Remove any non-degenerate phis whose inputs are all equal.
230void
231function_info::simplify_phis ()
232{
233 auto temps = temp_watermark ();
234
235 // See the comment above simplify_phi_setup for details about this array.
236 auto *assumed_values = XOBNEWVEC (&m_temp_obstack, set_info *,
237 m_next_phi_uid);
238
239 // An array of all phis, indexed by uid.
240 auto *phis = XOBNEWVEC (&m_temp_obstack, phi_info *, m_next_phi_uid);
241
242 // Which phi uids are actually in use.
243 auto_sbitmap valid_phi_uids (m_next_phi_uid);
244 bitmap_clear (valid_phi_uids);
245
246 // Bitmaps used for the main double-queue propagation phase.
247 auto_bitmap worklist1;
248 auto_bitmap worklist2;
249 bitmap curr_worklist = worklist1;
250 bitmap next_worklist = worklist2;
251
252 // Perform the set-up phase; see simplify_phi_setup for details.
253 for (ebb_info *ebb : ebbs ())
254 for (phi_info *phi : ebb->phis ())
255 {
256 bitmap_set_bit (map: valid_phi_uids, bitno: phi->uid ());
257 phis[phi->uid ()] = phi;
258 simplify_phi_setup (phi, assumed_values, worklist: curr_worklist);
259 }
260
261 // Iteratively process any phis that need updating; see
262 // simplify_phi_propagate for details. Using a double queue
263 // should reduce the number of times that any given phi node
264 // needs to be revisited.
265 while (!bitmap_empty_p (map: curr_worklist))
266 {
267 do
268 {
269 unsigned int uid = bitmap_first_set_bit (curr_worklist);
270 bitmap_clear_bit (curr_worklist, uid);
271 simplify_phi_propagate (phi: phis[uid], assumed_values,
272 curr_worklist, next_worklist);
273 }
274 while (!bitmap_empty_p (map: curr_worklist));
275 std::swap (a&: next_worklist, b&: curr_worklist);
276 }
277
278 // Make sure that assumed_values is a transitive closure. This ensures
279 // that each use_info is only updated once.
280 if (flag_checking)
281 for (unsigned int i = 0; i < m_next_phi_uid; ++i)
282 if (bitmap_bit_p (map: valid_phi_uids, bitno: i))
283 if (auto *new_phi = safe_dyn_cast<phi_info *> (p: assumed_values[i]))
284 gcc_assert (assumed_values[new_phi->uid ()] == new_phi);
285
286 // Update any phis that turned out to be equivalent to a single input.
287 for (unsigned int i = 0; i < m_next_phi_uid; ++i)
288 if (bitmap_bit_p (map: valid_phi_uids, bitno: i) && phis[i] != assumed_values[i])
289 replace_phi (phis[i], assumed_values[i]);
290}
291
292// Print a description of FUNCTION to PP.
293void
294rtl_ssa::pp_function (pretty_printer *pp, const function_info *function)
295{
296 function->print (pp);
297}
298
299// Print a description of FUNCTION to FILE.
300void
301dump (FILE *file, const function_info *function)
302{
303 dump_using (file, printer: pp_function, args: function);
304}
305
306// Debug interface to the dump routine above.
307void debug (const function_info *x) { dump (stderr, function: x); }
308

source code of gcc/rtl-ssa/functions.cc