Line data Source code
1 : // Copyright (C) 2020-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 : #ifndef RUST_BIR_BUILDER_INTERNAL_H
20 : #define RUST_BIR_BUILDER_INTERNAL_H
21 :
22 : #include "rust-bir-place.h"
23 : #include "rust-hir-expr.h"
24 : #include "rust-hir-item.h"
25 : #include "rust-hir-type-check.h"
26 : #include "rust-hir-visitor.h"
27 : #include "rust-bir.h"
28 : #include "rust-bir-free-region.h"
29 : #include "rust-immutable-name-resolution-context.h"
30 : #include "options.h"
31 :
32 : namespace Rust {
33 :
34 : namespace TyTy {
35 :
36 : using Variance = VarianceAnalysis::Variance;
37 :
38 : class RenumberCtx
39 : {
40 : Polonius::Origin next_region = 0;
41 :
42 : public:
43 : Polonius::Origin get_next_region () { return next_region++; }
44 : };
45 :
46 : } // namespace TyTy
47 :
48 : namespace BIR {
49 :
50 : /** Holds the context of BIR building so that it can be shared/passed between
51 : * different builders. */
52 : struct BuilderContext
53 : {
54 : struct LoopAndLabelCtx
55 : {
56 : bool is_loop; // Loop or labelled block
57 : NodeId label; // UNKNOWN_NODEID if no label (loop)
58 : PlaceId label_var; // For break with value.
59 : BasicBlockId break_bb;
60 : BasicBlockId continue_bb; // Only valid for loops
61 : ScopeId continue_scope;
62 : // Break scope is the parent of the `continue_scope`.
63 :
64 0 : LoopAndLabelCtx (bool is_loop = false, NodeId label = UNKNOWN_NODEID,
65 : PlaceId label_var = INVALID_PLACE,
66 : BasicBlockId break_bb = INVALID_BB,
67 : BasicBlockId continue_bb = INVALID_BB,
68 : ScopeId continue_scope = INVALID_SCOPE)
69 0 : : is_loop (is_loop), label (label), label_var (label_var),
70 0 : break_bb (break_bb), continue_bb (continue_bb),
71 0 : continue_scope (continue_scope)
72 : {}
73 : };
74 :
75 : // External context.
76 : Resolver::TypeCheckContext &tyctx;
77 : const Resolver2_0::NameResolutionContext &resolver;
78 :
79 : // BIR output
80 : BasicBlocks basic_blocks;
81 : BasicBlockId current_bb = ENTRY_BASIC_BLOCK;
82 :
83 : /**
84 : * Allocation and lookup of places (variables, temporaries, paths, and
85 : * constants)
86 : */
87 : PlaceDB place_db;
88 : RegionBinder region_binder{place_db.expose_next_free_region ()};
89 :
90 : // Used for cleaner dump.
91 : std::vector<PlaceId> arguments;
92 : /**
93 : * Since labels can be used to return values, we need to reserve a place for
94 : * them. This map associates labels with their respective places.
95 : */
96 : std::unordered_map<NodeId, PlaceId> label_place_map;
97 :
98 : /** Context for current situation (loop, label, etc.) */
99 : std::vector<LoopAndLabelCtx> loop_and_label_stack;
100 :
101 : FreeRegions fn_free_regions{{}};
102 :
103 : public:
104 36 : BuilderContext ()
105 36 : : tyctx (*Resolver::TypeCheckContext::get ()),
106 36 : resolver (Resolver2_0::ImmutableNameResolutionContext::get ().resolver ())
107 : {
108 36 : basic_blocks.emplace_back (); // StartBB
109 36 : }
110 :
111 166 : BasicBlock &get_current_bb () { return basic_blocks[current_bb]; }
112 :
113 : const LoopAndLabelCtx &lookup_label (NodeId label)
114 : {
115 : auto label_match = [label] (const LoopAndLabelCtx &info) {
116 : return info.label != UNKNOWN_NODEID && info.label == label;
117 : };
118 :
119 : auto found = std::find_if (loop_and_label_stack.rbegin (),
120 : loop_and_label_stack.rend (), label_match);
121 : rust_assert (found != loop_and_label_stack.rend ());
122 : return *found;
123 : }
124 : };
125 :
126 : /** Common infrastructure for building BIR from HIR. */
127 : class AbstractBuilder
128 : {
129 : protected:
130 : BuilderContext &ctx;
131 :
132 : /**
133 : * This emulates the return value of the visitor, to be able to use the
134 : * current visitor infrastructure, where the return value is forced to be
135 : * void.
136 : */
137 : PlaceId translated = INVALID_PLACE;
138 :
139 : protected:
140 42 : explicit AbstractBuilder (BuilderContext &ctx) : ctx (ctx) {}
141 :
142 121 : PlaceId declare_variable (const Analysis::NodeMapping &node,
143 : bool user_type_annotation = false)
144 : {
145 121 : return declare_variable (node, lookup_type (node.get_hirid ()),
146 121 : user_type_annotation);
147 : }
148 :
149 121 : PlaceId declare_variable (const Analysis::NodeMapping &node,
150 : TyTy::BaseType *ty,
151 : bool user_type_annotation = false)
152 : {
153 121 : const NodeId nodeid = node.get_nodeid ();
154 :
155 : // In debug mode, check that the variable is not already declared.
156 121 : rust_assert (ctx.place_db.lookup_variable (nodeid) == INVALID_PLACE);
157 :
158 121 : auto place_id = ctx.place_db.add_variable (nodeid, ty);
159 :
160 121 : if (ctx.place_db.get_current_scope_id () != INVALID_SCOPE)
161 121 : push_storage_live (place_id);
162 :
163 121 : if (user_type_annotation)
164 0 : push_user_type_ascription (place_id, ty);
165 :
166 121 : return place_id;
167 : }
168 :
169 46 : void push_new_scope () { ctx.place_db.push_new_scope (); }
170 :
171 44 : void pop_scope ()
172 : {
173 44 : auto &scope = ctx.place_db.get_current_scope ();
174 88 : if (ctx.place_db.get_current_scope_id () != INVALID_SCOPE)
175 : {
176 44 : std::for_each (scope.locals.rbegin (), scope.locals.rend (),
177 139 : [&] (PlaceId place) { push_storage_dead (place); });
178 : }
179 44 : ctx.place_db.pop_scope ();
180 44 : }
181 :
182 : bool intersection_empty (std::vector<PlaceId> &a, std::vector<PlaceId> &b)
183 : {
184 : for (auto &place : a)
185 : {
186 : if (std::find (b.begin (), b.end (), place) != b.end ())
187 : return false;
188 : }
189 : return true;
190 : }
191 :
192 2 : void unwind_until (ScopeId final_scope)
193 : {
194 2 : auto current_scope_id = ctx.place_db.get_current_scope_id ();
195 6 : while (current_scope_id != final_scope)
196 : {
197 4 : auto &scope = ctx.place_db.get_scope (current_scope_id);
198 :
199 : // TODO: Perform stable toposort based on `borrowed_by`.
200 :
201 4 : std::for_each (scope.locals.rbegin (), scope.locals.rend (),
202 6 : [&] (PlaceId place) { push_storage_dead (place); });
203 4 : current_scope_id = scope.parent;
204 : }
205 2 : }
206 :
207 54 : FreeRegions bind_regions (std::vector<TyTy::Region> regions,
208 : FreeRegions parent_free_regions)
209 : {
210 54 : FreeRegions free_regions;
211 75 : for (auto ®ion : regions)
212 : {
213 21 : if (region.is_early_bound ())
214 : {
215 18 : free_regions.push_back (parent_free_regions[region.get_index ()]);
216 : }
217 3 : else if (region.is_static ())
218 : {
219 1 : free_regions.push_back (STATIC_FREE_REGION);
220 : }
221 2 : else if (region.is_anonymous ())
222 : {
223 2 : free_regions.push_back (ctx.place_db.get_next_free_region ());
224 : }
225 0 : else if (region.is_named ())
226 : {
227 0 : rust_unreachable (); // FIXME
228 : }
229 : else
230 : {
231 0 : rust_sorry_at (UNKNOWN_LOCATION, "Unimplemented");
232 0 : rust_unreachable ();
233 : }
234 : }
235 54 : return free_regions;
236 : }
237 :
238 : protected: // Helpers to add BIR statements
239 185 : void push_assignment (PlaceId lhs, AbstractExpr *rhs, location_t location)
240 : {
241 185 : ctx.get_current_bb ().statements.push_back (
242 185 : Statement::make_assignment (lhs, rhs, location));
243 185 : translated = lhs;
244 185 : }
245 :
246 99 : void push_assignment (PlaceId lhs, PlaceId rhs, location_t location)
247 : {
248 99 : push_assignment (lhs, new Assignment (rhs), location);
249 99 : }
250 :
251 38 : void push_tmp_assignment (AbstractExpr *rhs, TyTy::BaseType *tyty,
252 : location_t location)
253 : {
254 38 : PlaceId tmp = ctx.place_db.add_temporary (tyty);
255 38 : push_storage_live (tmp);
256 38 : push_assignment (tmp, rhs, location);
257 38 : }
258 :
259 14 : void push_tmp_assignment (PlaceId rhs, location_t location)
260 : {
261 14 : push_tmp_assignment (new Assignment (rhs), ctx.place_db[rhs].tyty,
262 : location);
263 14 : }
264 :
265 7 : void push_switch (PlaceId switch_val, location_t location,
266 : std::initializer_list<BasicBlockId> destinations = {})
267 : {
268 7 : auto copy = move_place (switch_val, location);
269 7 : ctx.get_current_bb ().statements.push_back (Statement::make_switch (copy));
270 7 : ctx.get_current_bb ().successors.insert (
271 7 : ctx.get_current_bb ().successors.end (), destinations);
272 7 : }
273 :
274 8 : void push_goto (BasicBlockId bb)
275 : {
276 8 : ctx.get_current_bb ().statements.push_back (Statement::make_goto ());
277 8 : if (bb != INVALID_BB) // INVALID_BB means the goto will be resolved later.
278 0 : ctx.get_current_bb ().successors.push_back (bb);
279 8 : }
280 :
281 159 : void push_storage_live (PlaceId place)
282 : {
283 159 : ctx.get_current_bb ().statements.push_back (
284 159 : Statement::make_storage_live (place));
285 159 : }
286 :
287 145 : void push_storage_dead (PlaceId place)
288 : {
289 145 : ctx.get_current_bb ().statements.push_back (
290 145 : Statement::make_storage_dead (place));
291 145 : }
292 :
293 0 : void push_user_type_ascription (PlaceId place, TyTy::BaseType *ty)
294 : {
295 0 : ctx.get_current_bb ().statements.push_back (
296 0 : Statement::make_user_type_ascription (place, ty));
297 0 : }
298 :
299 90 : void push_fake_read (PlaceId place)
300 : {
301 90 : ctx.get_current_bb ().statements.push_back (
302 90 : Statement::make_fake_read (place));
303 90 : }
304 :
305 38 : void push_return (location_t location)
306 : {
307 38 : ctx.get_current_bb ().statements.push_back (
308 38 : Statement::make_return (location));
309 38 : }
310 :
311 13 : PlaceId borrow_place (PlaceId place_id, TyTy::BaseType *ty,
312 : location_t location)
313 : {
314 13 : auto mutability = ty->as<const TyTy::ReferenceType> ()->mutability ();
315 13 : auto loan = ctx.place_db.add_loan ({mutability, place_id, location});
316 13 : push_tmp_assignment (
317 : new BorrowExpr (place_id, loan,
318 13 : ctx.place_db.get_next_free_region ().value),
319 : ty, location);
320 13 : return translated;
321 : }
322 :
323 29 : PlaceId move_place (PlaceId arg, location_t location)
324 : {
325 29 : auto &place = ctx.place_db[arg];
326 :
327 29 : if (place.is_constant ())
328 4 : return arg;
329 :
330 25 : if (place.tyty->is<TyTy::ReferenceType> ())
331 13 : return reborrow_place (arg, location);
332 :
333 12 : if (place.is_rvalue ())
334 3 : return arg;
335 :
336 9 : push_tmp_assignment (arg, location);
337 9 : return translated;
338 : }
339 :
340 13 : PlaceId reborrow_place (PlaceId arg, location_t location)
341 : {
342 13 : auto ty = ctx.place_db[arg].tyty->as<TyTy::ReferenceType> ();
343 13 : return borrow_place (ctx.place_db.lookup_or_add_path (Place::DEREF,
344 : ty->get_base (), arg),
345 13 : ty, location);
346 : }
347 :
348 : template <typename T>
349 17 : void move_all (T &args, std::vector<location_t> locations)
350 : {
351 17 : rust_assert (args.size () == locations.size ());
352 17 : std::transform (args.begin (), args.end (), locations.begin (),
353 17 : args.begin (), [this] (PlaceId arg, location_t location) {
354 17 : return move_place (arg, location);
355 : });
356 17 : }
357 :
358 : protected: // CFG helpers
359 28 : BasicBlockId new_bb ()
360 : {
361 28 : ctx.basic_blocks.emplace_back ();
362 28 : return {ctx.basic_blocks.size () - 1};
363 : }
364 :
365 11 : BasicBlockId start_new_consecutive_bb ()
366 : {
367 11 : BasicBlockId bb = new_bb ();
368 11 : if (!ctx.get_current_bb ().is_terminated ())
369 : {
370 0 : push_goto (bb);
371 : }
372 : else
373 : {
374 11 : add_jump_to (bb);
375 : }
376 11 : ctx.current_bb = bb;
377 11 : return bb;
378 : }
379 :
380 33 : void add_jump (BasicBlockId from, BasicBlockId to)
381 : {
382 15 : ctx.basic_blocks[from].successors.emplace_back (to);
383 : }
384 :
385 11 : void add_jump_to (BasicBlockId bb) { add_jump (ctx.current_bb, bb); }
386 :
387 : protected: // HIR resolution helpers
388 : template <typename T>
389 292 : WARN_UNUSED_RESULT TyTy::BaseType *lookup_type (T &hir_node) const
390 : {
391 292 : return lookup_type (hir_node.get_mappings ().get_hirid ());
392 : }
393 :
394 413 : WARN_UNUSED_RESULT TyTy::BaseType *lookup_type (HirId hirid) const
395 : {
396 413 : TyTy::BaseType *type = nullptr;
397 413 : bool ok = ctx.tyctx.lookup_type (hirid, &type);
398 413 : rust_assert (ok);
399 413 : rust_assert (type != nullptr);
400 413 : return type;
401 : }
402 :
403 0 : template <typename T> NodeId resolve_label (T &expr)
404 : {
405 0 : auto res = ctx.resolver.lookup (expr.get_mappings ().get_nodeid ());
406 0 : rust_assert (res.has_value ());
407 0 : return res.value ();
408 : }
409 :
410 2 : template <typename T> PlaceId resolve_variable (T &variable)
411 : {
412 2 : auto res = ctx.resolver.lookup (variable.get_mappings ().get_nodeid ());
413 2 : rust_assert (res.has_value ());
414 2 : return ctx.place_db.lookup_variable (res.value ());
415 : }
416 :
417 : template <typename T>
418 108 : PlaceId resolve_variable_or_fn (T &variable, TyTy::BaseType *ty)
419 : {
420 108 : ty = (ty) ? ty : lookup_type (variable);
421 :
422 : // Unlike variables,
423 : // functions do not have to be declared in PlaceDB before use.
424 108 : if (ty->is<TyTy::FnType> ())
425 11 : return ctx.place_db.get_constant (ty);
426 :
427 97 : auto res = ctx.resolver.lookup (variable.get_mappings ().get_nodeid ());
428 97 : rust_assert (res.has_value ());
429 97 : return ctx.place_db.lookup_or_add_variable (res.value (), ty);
430 : }
431 :
432 : protected: // Implicit conversions.
433 : /**
434 : * Performs implicit coercions on the `translated` place defined for a
435 : * coercion site.
436 : *
437 : * Reference: https://doc.rust-lang.org/reference/type-coercions.html
438 : *
439 : * The only coercion relevant to BIR is the autoderef. All other coercions
440 : * will be taken in account because the type is extracted from each node and
441 : * not derived from operations in HIR/BIR. The borrowck does not care about
442 : * type transitions. Lifetimes are not coerced, rather new are created with
443 : * defined bounds to the original ones.
444 : */
445 17 : void coercion_site (PlaceId &place, TyTy::BaseType *expected_ty)
446 : {
447 51 : auto count_ref_levels = [] (TyTy::BaseType *ty) {
448 34 : size_t count = 0;
449 58 : while (auto r = ty->try_as<TyTy::ReferenceType> ())
450 : {
451 24 : ty = r->get_base ();
452 24 : count++;
453 24 : }
454 34 : return count;
455 : };
456 :
457 17 : auto actual_ty = ctx.place_db[place].tyty;
458 :
459 17 : auto deref_count
460 17 : = count_ref_levels (actual_ty) - count_ref_levels (expected_ty);
461 :
462 17 : for (size_t i = 0; i < deref_count; ++i)
463 : {
464 0 : actual_ty = actual_ty->as<TyTy::ReferenceType> ()->get_base ();
465 0 : place
466 0 : = ctx.place_db.lookup_or_add_path (Place::DEREF, actual_ty, place);
467 : }
468 17 : }
469 :
470 : /** Dereferences the `translated` place until it is at most one reference
471 : * and return the base type. */
472 5 : TyTy::BaseType *autoderef (PlaceId &place)
473 : {
474 5 : auto ty = ctx.place_db[place].tyty;
475 6 : while (auto ref_ty = ty->try_as<TyTy::ReferenceType> ())
476 : {
477 1 : ty = ref_ty->get_base ();
478 1 : place = ctx.place_db.lookup_or_add_path (Place::DEREF, ty, place);
479 1 : }
480 5 : return ty;
481 : }
482 :
483 : void autoref ()
484 : {
485 : if (ctx.place_db[translated].tyty->get_kind () != TyTy::REF)
486 : {
487 : // FIXME: not sure how to fetch correct location for this
488 : // this function is unused yet, so can ignore for now
489 : auto ty = ctx.place_db[translated].tyty;
490 : translated
491 : = borrow_place (translated,
492 : new TyTy::ReferenceType (ty->get_ref (),
493 : TyTy::TyVar (ty->get_ref ()),
494 : Mutability::Imm),
495 : UNKNOWN_LOCATION);
496 : }
497 : }
498 : };
499 :
500 : class AbstractExprBuilder : public AbstractBuilder,
501 : public HIR::HIRExpressionVisitor
502 : {
503 : protected:
504 : /**
505 : * Optional place for the result of the evaluated expression.
506 : * Valid if value is not `INVALID_PLACE`.
507 : * Used when return place must be created by caller (return for if-else).
508 : */
509 : PlaceId expr_return_place = INVALID_PLACE;
510 :
511 : protected:
512 40 : explicit AbstractExprBuilder (BuilderContext &ctx,
513 : PlaceId expr_return_place = INVALID_PLACE)
514 40 : : AbstractBuilder (ctx), expr_return_place (expr_return_place)
515 : {}
516 :
517 : /**
518 : * Wrapper that provides return value based API inside a visitor which has
519 : * to use global state to pass the data around.
520 : * @param dst_place Place to assign the produced value to, optionally
521 : * allocated by the caller.
522 : * */
523 276 : PlaceId visit_expr (HIR::Expr &expr, PlaceId dst_place = INVALID_PLACE)
524 : {
525 : // Save to support proper recursion.
526 276 : auto saved = expr_return_place;
527 276 : expr_return_place = dst_place;
528 276 : translated = INVALID_PLACE;
529 271 : expr.accept_vis (*this);
530 276 : expr_return_place = saved;
531 276 : auto result = translated;
532 276 : translated = INVALID_PLACE;
533 271 : return result;
534 : }
535 :
536 : /**
537 : * Create a return value of a subexpression, which produces an expression.
538 : * Use `return_place` for subexpression that only produce a place (look it
539 : * up) to avoid needless assignments.
540 : *
541 : * @param can_panic mark that expression can panic to insert jump to
542 : * cleanup.
543 : */
544 59 : void return_expr (AbstractExpr *expr, TyTy::BaseType *ty, location_t location,
545 : bool can_panic = false)
546 : {
547 59 : if (expr_return_place != INVALID_PLACE)
548 : {
549 48 : push_assignment (expr_return_place, expr, location);
550 : }
551 : else
552 : {
553 11 : push_tmp_assignment (expr, ty, location);
554 : }
555 :
556 59 : if (can_panic)
557 : {
558 11 : start_new_consecutive_bb ();
559 : }
560 :
561 59 : if (ty->is<TyTy::ReferenceType> ()
562 59 : || ctx.place_db[translated].is_constant ())
563 : {
564 43 : push_fake_read (translated);
565 : }
566 59 : }
567 :
568 : /** Mark place to be a result of processed subexpression. */
569 174 : void return_place (PlaceId place, location_t location, bool can_panic = false)
570 : {
571 174 : if (expr_return_place != INVALID_PLACE)
572 : {
573 : // Return place is already allocated, no need to defer assignment.
574 64 : push_assignment (expr_return_place, place, location);
575 : }
576 : else
577 : {
578 110 : translated = place;
579 : }
580 :
581 174 : if (can_panic)
582 : {
583 0 : start_new_consecutive_bb ();
584 : }
585 :
586 174 : if (ctx.place_db[place].is_constant ())
587 : {
588 47 : push_fake_read (translated);
589 : }
590 174 : }
591 :
592 : /** Explicitly return a unit value. Expression produces no value. */
593 4 : void return_unit (HIR::Expr &expr)
594 : {
595 4 : translated = ctx.place_db.get_constant (lookup_type (expr));
596 4 : }
597 :
598 42 : PlaceId return_borrowed (PlaceId place_id, TyTy::BaseType *ty,
599 : location_t location)
600 : {
601 : // TODO: deduplicate with borrow_place
602 42 : auto loan = ctx.place_db.add_loan (
603 42 : {ty->as<const TyTy::ReferenceType> ()->mutability (), place_id,
604 : location});
605 42 : return_expr (new BorrowExpr (place_id, loan,
606 42 : ctx.place_db.get_next_free_region ().value),
607 : ty, location);
608 42 : return translated;
609 : }
610 :
611 17 : PlaceId take_or_create_return_place (TyTy::BaseType *type)
612 : {
613 17 : PlaceId result = INVALID_PLACE;
614 17 : if (expr_return_place != INVALID_PLACE)
615 : {
616 17 : result = expr_return_place;
617 17 : expr_return_place = INVALID_PLACE;
618 : }
619 : else
620 : {
621 0 : result = ctx.place_db.add_temporary (type);
622 0 : push_storage_live (result);
623 : }
624 17 : return result;
625 : }
626 : };
627 :
628 : /**
629 : * Helper to convert a pointer to an optional. Maps nullptr to nullopt.
630 : * Optionals are mainly used here to provide monadic operations (map) over
631 : * possibly null pointers.
632 : */
633 : template <typename T>
634 : tl::optional<T>
635 : optional_from_ptr (T ptr)
636 : {
637 : if (ptr != nullptr)
638 : return {ptr};
639 : else
640 : return tl::nullopt;
641 : }
642 :
643 : } // namespace BIR
644 : } // namespace Rust
645 :
646 : #endif // RUST_BIR_BUILDER_INTERNAL_H
|
