1 // Implementation of function-related RTL SSA functions -*- C++ -*-
2 // Copyright (C) 2020-2023 Free Software Foundation, Inc.
4 // This file is part of GCC.
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
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
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/>.
20 #define INCLUDE_ALGORITHM
21 #define INCLUDE_FUNCTIONAL
24 #include "coretypes.h"
29 #include "rtl-ssa/internals.h"
30 #include "rtl-ssa/internals.inl"
32 using namespace rtl_ssa
;
34 function_info::function_info (function
*fn
)
35 : m_fn (fn
), m_clobbered_by_calls ()
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
,
41 obstack_specify_allocation (&m_temp_obstack
, OBSTACK_CHUNK_SIZE
,
42 obstack_alignment
, obstack_chunk_alloc
,
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);
49 init_function_data ();
50 process_all_blocks ();
54 function_info::~function_info ()
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
);
60 obstack_free (&m_temp_obstack
, nullptr);
61 obstack_free (&m_obstack
, nullptr);
64 // See the comment above the declaration.
66 function_info::print (pretty_printer
*pp
) const
68 pp_string (pp
, "Function: ");
69 pp_string (pp
, function_name (m_fn
));
70 for (ebb_info
*ebb
: ebbs ())
73 pp_newline_and_indent (pp
, 0);
78 // Initialize all member variables in preparation for (re)building
79 // SSA form from scratch.
81 function_info::init_function_data ()
83 m_next_artificial_uid
= -1;
85 m_num_regs
= max_reg_num ();
86 m_defs
.safe_grow_cleared (m_num_regs
+ 1);
87 m_bbs
.safe_grow_cleared (last_basic_block_for_fn (m_fn
));
90 m_first_insn
= nullptr;
91 m_last_insn
= nullptr;
92 m_last_nondebug_insn
= nullptr;
93 m_free_phis
= nullptr;
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:
100 // - if we think all inputs to P have the same value, ASSUMED_VALUES[ID]
103 // - otherwise, ASSUMED_VALUES[ID] is P.
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.
110 function_info::simplify_phi_setup (phi_info
*phi
, set_info
**assumed_values
,
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 ())
122 set_info
*def
= input
->def ();
124 if (auto *input_phi
= safe_dyn_cast
<phi_info
*> (def
))
126 // Ignore backedges for now.
127 unsigned int input_phi_uid
= input_phi
->uid ();
128 if (phi_uid
<= input_phi_uid
)
131 def
= assumed_values
[input_phi_uid
];
134 // Compare this definition with previous ones.
138 is_first_input
= false;
140 else if (new_value
!= def
)
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.
146 phi_mode
= combine_modes (phi_mode
, def
->mode ());
148 if (phi
->mode () != phi_mode
)
149 phi
->set_mode (phi_mode
);
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
;
156 // See whether any assumptions for earlier phis are now invalid.
157 simplify_phi_propagate (phi
, assumed_values
, nullptr, worklist
);
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.
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.
170 function_info::simplify_phi_propagate (phi_info
*phi
,
171 set_info
**assumed_values
,
172 bitmap curr_worklist
,
173 bitmap next_worklist
)
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 ())
181 phi_info
*user_phi
= use
->phi ();
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
);
192 // If this is a phi we should be looking at, see whether it needs
194 unsigned int user_phi_uid
= user_phi
->uid ();
195 if (user_phi_uid
< phi_uid
|| curr_worklist
)
197 bool needs_update
= false;
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 (user_phi_mode
, phi_mode
);
202 if (user_phi_mode
!= new_mode
)
204 user_phi
->set_mode (new_mode
);
208 // If USER_PHI optimistically assumed an incorrect value,
210 if (assumed_values
[user_phi_uid
] != user_phi
211 && assumed_values
[user_phi_uid
] != phi_value
)
213 assumed_values
[user_phi_uid
] = user_phi
;
219 if (user_phi_uid
< phi_uid
)
220 bitmap_set_bit (next_worklist
, user_phi_uid
);
222 bitmap_set_bit (curr_worklist
, user_phi_uid
);
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.
231 function_info::simplify_phis ()
233 auto temps
= temp_watermark ();
235 // See the comment above simplify_phi_setup for details about this array.
236 auto *assumed_values
= XOBNEWVEC (&m_temp_obstack
, set_info
*,
239 // An array of all phis, indexed by uid.
240 auto *phis
= XOBNEWVEC (&m_temp_obstack
, phi_info
*, m_next_phi_uid
);
242 // Which phi uids are actually in use.
243 auto_sbitmap
valid_phi_uids (m_next_phi_uid
);
244 bitmap_clear (valid_phi_uids
);
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
;
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 ())
256 bitmap_set_bit (valid_phi_uids
, phi
->uid ());
257 phis
[phi
->uid ()] = phi
;
258 simplify_phi_setup (phi
, assumed_values
, curr_worklist
);
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 (curr_worklist
))
269 unsigned int uid
= bitmap_first_set_bit (curr_worklist
);
270 bitmap_clear_bit (curr_worklist
, uid
);
271 simplify_phi_propagate (phis
[uid
], assumed_values
,
272 curr_worklist
, next_worklist
);
274 while (!bitmap_empty_p (curr_worklist
));
275 std::swap (next_worklist
, curr_worklist
);
278 // Make sure that assumed_values is a transitive closure. This ensures
279 // that each use_info is only updated once.
281 for (unsigned int i
= 0; i
< m_next_phi_uid
; ++i
)
282 if (bitmap_bit_p (valid_phi_uids
, i
))
283 if (auto *new_phi
= safe_dyn_cast
<phi_info
*> (assumed_values
[i
]))
284 gcc_assert (assumed_values
[new_phi
->uid ()] == new_phi
);
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 (valid_phi_uids
, i
) && phis
[i
] != assumed_values
[i
])
289 replace_phi (phis
[i
], assumed_values
[i
]);
292 // Print a description of FUNCTION to PP.
294 rtl_ssa::pp_function (pretty_printer
*pp
, const function_info
*function
)
296 function
->print (pp
);
299 // Print a description of FUNCTION to FILE.
301 dump (FILE *file
, const function_info
*function
)
303 dump_using (file
, pp_function
, function
);
306 // Debug interface to the dump routine above.
307 void debug (const function_info
*x
) { dump (stderr
, x
); }