Line data Source code
1 : // Copyright (C) 2026 Free Software Foundation, Inc.
2 :
3 : // This file is part of GCC.
4 :
5 : // GCC is free software; you can redistribute it and/or modify it under
6 : // the terms of the GNU General Public License as published by the Free
7 : // Software Foundation; either version 3, or (at your option) any later
8 : // version.
9 :
10 : // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
11 : // WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 : // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 : // for more details.
14 :
15 : // You should have received a copy of the GNU General Public License
16 : // along with GCC; see the file COPYING3. If not see
17 : // <http://www.gnu.org/licenses/>.
18 :
19 : #include "rust-bir-drop-analysis.h"
20 : #include "rust-bir.h"
21 : #include "rust-diagnostics.h"
22 : #include "rust-hir-map.h"
23 :
24 : namespace Rust {
25 : namespace BIR {
26 : namespace {
27 :
28 344 : struct BlockInitializationState
29 : {
30 114 : explicit BlockInitializationState (size_t place_count)
31 114 : : maybe_initialized (place_count, false),
32 114 : maybe_uninitialized (place_count, false), reachable (false)
33 114 : {}
34 :
35 : std::vector<bool> maybe_initialized;
36 : std::vector<bool> maybe_uninitialized;
37 :
38 : // Whether this block is reached or not.
39 : bool reachable;
40 : };
41 :
42 : struct DropAnalysisResults
43 : {
44 : std::unordered_set<HirId> dead_drop_hir_ids;
45 : std::unordered_set<HirId> static_drop_hir_ids;
46 : std::unordered_set<HirId> conditional_drop_hir_ids;
47 : std::unordered_map<HirId, HirId> move_sources;
48 : };
49 :
50 : static void
51 591 : set_initialized (BlockInitializationState &state, PlaceId place)
52 : {
53 591 : state.maybe_initialized[place.value] = true;
54 591 : state.maybe_uninitialized[place.value] = false;
55 591 : }
56 :
57 : static void
58 1449 : set_uninitialized (BlockInitializationState &state, PlaceId place)
59 : {
60 1449 : state.maybe_initialized[place.value] = false;
61 1449 : state.maybe_uninitialized[place.value] = true;
62 1449 : }
63 :
64 : // This function combines states from incoming blocks.
65 : // Take conditional move as example,
66 : //
67 : // BB0
68 : // initialize x
69 : // / |
70 : // v v
71 : // BB1 BB2
72 : // move x no change
73 : // \ /
74 : // v v
75 : // BB3
76 : // Drop(x)
77 : // BB1 -> BB3
78 : // (BB1): maybe_initialized(x) = false
79 : // (BB1): maybe_uninitialized(x) = true
80 : //
81 : // (BB3): maybe_initialized(x) = true || (BB1): maybe_initialized(x) -> true
82 : // (BB3): maybe_uninitialized(x) = false || (BB1): maybe_uninitialized(x) ->
83 : // true
84 : static bool
85 69 : merge_state (BlockInitializationState &into,
86 : const BlockInitializationState &from)
87 : {
88 69 : bool changed = false;
89 :
90 69 : if (!into.reachable)
91 : {
92 56 : into = from;
93 56 : return !changed;
94 : }
95 :
96 160 : for (size_t i = 0; i < into.maybe_initialized.size (); i++)
97 : {
98 147 : bool maybe_initialized
99 147 : = into.maybe_initialized[i] || from.maybe_initialized[i];
100 :
101 147 : bool maybe_uninitialized
102 147 : = into.maybe_uninitialized[i] || from.maybe_uninitialized[i];
103 :
104 147 : changed |= maybe_initialized != into.maybe_initialized[i];
105 147 : changed |= maybe_uninitialized != into.maybe_uninitialized[i];
106 :
107 147 : into.maybe_initialized[i] = maybe_initialized;
108 147 : into.maybe_uninitialized[i] = maybe_uninitialized;
109 : }
110 :
111 : return changed;
112 : }
113 :
114 : static void
115 2398 : update_state_for_statement (Function &function, Statement &statement,
116 : BlockInitializationState &state)
117 : {
118 2398 : PlaceId place = statement.get_place ();
119 :
120 2398 : switch (statement.get_kind ())
121 : {
122 430 : case Statement::Kind::STORAGE_LIVE:
123 430 : set_uninitialized (state, place);
124 430 : break;
125 :
126 563 : case Statement::Kind::ASSIGNMENT:
127 563 : {
128 563 : PlaceId lhs = place;
129 563 : AbstractExpr &expr = statement.get_expr ();
130 :
131 563 : if (expr.get_kind () == ExprKind::ASSIGNMENT)
132 : {
133 350 : PlaceId rhs = static_cast<Assignment &> (expr).get_rhs ();
134 350 : const Place &rhs_place = function.place_db[rhs];
135 :
136 350 : if (rhs_place.kind == Place::VARIABLE
137 494 : && rhs_place.should_be_moved ())
138 74 : set_uninitialized (state, rhs);
139 : }
140 :
141 563 : set_initialized (state, lhs);
142 563 : break;
143 : }
144 :
145 945 : case Statement::Kind::DROP:
146 945 : case Statement::Kind::STORAGE_DEAD:
147 945 : set_uninitialized (state, place);
148 945 : break;
149 :
150 : case Statement::Kind::SWITCH:
151 : case Statement::Kind::RETURN:
152 : case Statement::Kind::GOTO:
153 : case Statement::Kind::USER_TYPE_ASCRIPTION:
154 : case Statement::Kind::FAKE_READ:
155 : break;
156 : }
157 2398 : }
158 :
159 : static Statement::DropStyle
160 246 : classify_drop (const BlockInitializationState &state, PlaceId place)
161 : {
162 246 : bool maybe_initialized = state.maybe_initialized[place.value];
163 246 : bool maybe_uninitialized = state.maybe_uninitialized[place.value];
164 :
165 246 : if (!maybe_initialized)
166 : return Statement::DropStyle::DEAD;
167 :
168 218 : if (!maybe_uninitialized)
169 214 : return Statement::DropStyle::STATIC;
170 :
171 : return Statement::DropStyle::CONDITIONAL;
172 : }
173 :
174 : // Compute the initialization state at the entry of every reachable block.
175 : static std::vector<BlockInitializationState>
176 57 : compute_entry_states (Function &function)
177 : {
178 57 : size_t place_count = function.place_db.size ();
179 57 : size_t block_count = function.basic_blocks.size ();
180 :
181 57 : std::vector<BlockInitializationState> entry_states;
182 57 : entry_states.reserve (block_count);
183 :
184 228 : for (size_t i = 0; i < block_count; i++)
185 114 : entry_states.emplace_back (place_count);
186 :
187 57 : BlockInitializationState &entry_state = entry_states[ENTRY_BASIC_BLOCK.value];
188 :
189 57 : entry_state.reachable = true;
190 :
191 : // All places start uninitialized, except function arguments.
192 584 : for (size_t i = 0; i < place_count; i++)
193 527 : entry_state.maybe_uninitialized[i] = true;
194 :
195 85 : for (PlaceId argument : function.arguments)
196 28 : set_initialized (entry_state, argument);
197 :
198 57 : std::vector<BasicBlockId> worklist;
199 57 : std::vector<bool> queued (block_count, false);
200 :
201 57 : worklist.push_back (ENTRY_BASIC_BLOCK);
202 57 : queued[ENTRY_BASIC_BLOCK.value] = true;
203 :
204 : // Propagate block states until the last block.
205 173 : while (!worklist.empty ())
206 : {
207 116 : BasicBlockId block_id = worklist.back ();
208 116 : worklist.pop_back ();
209 116 : queued[block_id.value] = false;
210 :
211 116 : BlockInitializationState state = entry_states[block_id.value];
212 116 : BasicBlock &block = function.basic_blocks[block_id];
213 :
214 1332 : for (Statement &statement : block.statements)
215 1216 : update_state_for_statement (function, statement, state);
216 :
217 185 : for (BasicBlockId successor : block.successors)
218 : {
219 69 : bool state_changed
220 69 : = merge_state (entry_states[successor.value], state);
221 :
222 69 : if (state_changed && !queued[successor.value])
223 : {
224 59 : worklist.push_back (successor);
225 59 : queued[successor.value] = true;
226 : }
227 : }
228 116 : }
229 57 : return entry_states;
230 57 : }
231 :
232 : static void
233 246 : record_drop_for_backend (const Function &function, PlaceId place,
234 : Statement::DropStyle drop_style,
235 : DropAnalysisResults &results)
236 : {
237 246 : const Place &dropped_place = function.place_db[place];
238 :
239 246 : if (dropped_place.kind != Place::VARIABLE)
240 78 : return;
241 :
242 168 : auto hir_id = Analysis::Mappings::get ().lookup_node_to_hir (
243 168 : static_cast<NodeId> (dropped_place.variable_or_field_index));
244 :
245 168 : if (!hir_id.has_value ())
246 : return;
247 :
248 168 : switch (drop_style)
249 : {
250 : case Statement::DropStyle::UNCLASSIFIED:
251 : break;
252 :
253 28 : case Statement::DropStyle::DEAD:
254 28 : results.dead_drop_hir_ids.insert (hir_id.value ());
255 28 : break;
256 :
257 136 : case Statement::DropStyle::STATIC:
258 136 : results.static_drop_hir_ids.insert (hir_id.value ());
259 136 : break;
260 :
261 4 : case Statement::DropStyle::CONDITIONAL:
262 4 : results.conditional_drop_hir_ids.insert (hir_id.value ());
263 4 : break;
264 : }
265 : }
266 :
267 : // Walk each reachable block forward from its stable entry state and classify
268 : // its Drop statements.
269 : static void
270 57 : annotate_drop_statements (
271 : Function &function, const std::vector<BlockInitializationState> &entry_states,
272 : DropAnalysisResults &results)
273 : {
274 57 : const size_t block_count = function.basic_blocks.size ();
275 :
276 171 : for (size_t i = 0; i < block_count; i++)
277 : {
278 114 : BlockInitializationState state = entry_states[i];
279 :
280 114 : if (!state.reachable)
281 1 : continue;
282 :
283 113 : BasicBlockId block_id = {static_cast<uint32_t> (i)};
284 113 : BasicBlock &block = function.basic_blocks[block_id];
285 :
286 1295 : for (Statement &statement : block.statements)
287 : {
288 1182 : const auto &move_site = statement.get_move_site ();
289 1182 : if (statement.get_kind () == Statement::Kind::ASSIGNMENT
290 1182 : && move_site.has_value ())
291 : {
292 55 : AbstractExpr &expr = statement.get_expr ();
293 55 : if (expr.get_kind () == ExprKind::ASSIGNMENT)
294 : {
295 55 : PlaceId rhs = static_cast<Assignment &> (expr).get_rhs ();
296 55 : const Place &rhs_place = function.place_db[rhs];
297 55 : if (rhs_place.kind == Place::VARIABLE
298 55 : && rhs_place.should_be_moved ())
299 : {
300 35 : auto hirid
301 35 : = Analysis::Mappings::get ().lookup_node_to_hir (
302 : static_cast<NodeId> (
303 35 : rhs_place.variable_or_field_index));
304 35 : if (hirid.has_value ())
305 : {
306 35 : auto move_source
307 35 : = results.move_sources.find (move_site.value ());
308 35 : if (move_source != results.move_sources.end ()
309 2 : && move_source->second != hirid.value ())
310 2 : rust_sorry_at (statement.get_location (),
311 : "moving multiple IDs within the "
312 : "same location is not "
313 : "yet supported");
314 : else
315 33 : results.move_sources.emplace (move_site.value (),
316 : hirid.value ());
317 : }
318 : }
319 : }
320 : }
321 :
322 : // A Drop is classified using the state before it executes.
323 1182 : if (statement.get_kind () == Statement::Kind::DROP)
324 : {
325 246 : PlaceId place = statement.get_place ();
326 246 : Statement::DropStyle drop_style = classify_drop (state, place);
327 :
328 246 : statement.set_drop_style (drop_style);
329 :
330 246 : record_drop_for_backend (function, place, drop_style, results);
331 : }
332 :
333 : // Update the state for the following statement.
334 1182 : update_state_for_statement (function, statement, state);
335 : }
336 114 : }
337 57 : }
338 :
339 : } // namespace
340 :
341 : DropAnalysis &
342 11985 : DropAnalysis::get ()
343 : {
344 15092 : static DropAnalysis instance;
345 11985 : return instance;
346 : }
347 :
348 : void
349 17 : DropAnalysis::clear ()
350 : {
351 17 : definitely_dead.clear ();
352 17 : conditionally_dropped.clear ();
353 17 : move_sources.clear ();
354 17 : }
355 :
356 : bool
357 63 : DropAnalysis::is_definitely_dead (HirId id) const
358 : {
359 63 : return definitely_dead.find (id) != definitely_dead.end ();
360 : }
361 :
362 : bool
363 55 : DropAnalysis::needs_drop_flag (HirId id) const
364 : {
365 55 : return conditionally_dropped.find (id) != conditionally_dropped.end ();
366 : }
367 :
368 : bool
369 11793 : DropAnalysis::lookup_move_source (HirId move_site, HirId *source) const
370 : {
371 11793 : auto it = move_sources.find (move_site);
372 11793 : if (it == move_sources.end ())
373 : return false;
374 :
375 5 : *source = it->second;
376 5 : return true;
377 : }
378 :
379 : void
380 57 : DropAnalysis::analyze (Function &function)
381 : {
382 57 : std::vector<BlockInitializationState> entry_states
383 57 : = compute_entry_states (function);
384 :
385 57 : DropAnalysisResults results;
386 57 : annotate_drop_statements (function, entry_states, results);
387 :
388 : // A local is definitely dead only when all of its Drops are dead.
389 85 : for (HirId hir_id : results.dead_drop_hir_ids)
390 28 : if (results.static_drop_hir_ids.find (hir_id)
391 28 : == results.static_drop_hir_ids.end ()
392 28 : && results.conditional_drop_hir_ids.find (hir_id)
393 56 : == results.conditional_drop_hir_ids.end ())
394 28 : definitely_dead.insert (hir_id);
395 :
396 57 : conditionally_dropped.insert (results.conditional_drop_hir_ids.begin (),
397 : results.conditional_drop_hir_ids.end ());
398 57 : move_sources.insert (results.move_sources.begin (),
399 : results.move_sources.end ());
400 57 : }
401 :
402 : } // namespace BIR
403 : } // namespace Rust
|
