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