From de18440f92465be93f0248a7071834baa1ec748d Mon Sep 17 00:00:00 2001 From: Jakub Dupak Date: Fri, 2 Feb 2024 14:38:59 +0100 Subject: [PATCH] borrowck: BIR: scope handling gcc/rust/ChangeLog: * checks/errors/borrowck/rust-bir-builder-expr-stmt.cc (ExprStmtBuilder::setup_loop): Loop handling. (ExprStmtBuilder::visit): Handle scopes. * checks/errors/borrowck/rust-bir-builder-internal.h (struct BuilderContext): Handle scopes. * checks/errors/borrowck/rust-bir-dump.cc (Dump::go): Dump scopes. (Dump::visit): Add scopes dump. (Dump::indent): Add indentation logic. (Dump::visit_scope): Dump scope. * checks/errors/borrowck/rust-bir-dump.h: Dump methods. * checks/errors/borrowck/rust-bir-place.h (std::numeric_limits::max): Scope constants. (struct Scope): Scope representation. (class PlaceDB): Scope tracking. Signed-off-by: Jakub Dupak --- .../borrowck/rust-bir-builder-expr-stmt.cc | 32 +++++--- .../borrowck/rust-bir-builder-internal.h | 82 +++++++++++++++++-- .../checks/errors/borrowck/rust-bir-dump.cc | 52 ++++++++---- .../checks/errors/borrowck/rust-bir-dump.h | 3 + .../checks/errors/borrowck/rust-bir-place.h | 56 ++++++++++++- 5 files changed, 188 insertions(+), 37 deletions(-) diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-builder-expr-stmt.cc b/gcc/rust/checks/errors/borrowck/rust-bir-builder-expr-stmt.cc index ea8107b1fb76..89352d84f6b8 100644 --- a/gcc/rust/checks/errors/borrowck/rust-bir-builder-expr-stmt.cc +++ b/gcc/rust/checks/errors/borrowck/rust-bir-builder-expr-stmt.cc @@ -37,9 +37,17 @@ ExprStmtBuilder::setup_loop (HIR::BaseLoopExpr &expr) PlaceId label_var = take_or_create_return_place (lookup_type (expr)); BasicBlockId continue_bb = new_bb (); + push_goto (continue_bb); + ctx.current_bb = continue_bb; + // falseUnwind + start_new_consecutive_bb (); + BasicBlockId break_bb = new_bb (); - ctx.loop_and_label_stack.push_back ( - {true, label, label_var, break_bb, continue_bb}); + // We are still outside the loop block; + ScopeId continue_scope = ctx.place_db.get_current_scope_id () + 1; + ctx.loop_and_label_stack.emplace_back (true, label, label_var, break_bb, + continue_bb, continue_scope); + return ctx.loop_and_label_stack.back (); } @@ -289,13 +297,16 @@ ExprStmtBuilder::visit (HIR::FieldAccessExpr &expr) void ExprStmtBuilder::visit (HIR::BlockExpr &block) { + push_new_scope (); + if (block.has_label ()) { NodeId label = block.get_label ().get_lifetime ().get_mappings ().get_nodeid (); PlaceId label_var = take_or_create_return_place (lookup_type (block)); - ctx.loop_and_label_stack.push_back ( - {false, label, label_var, new_bb (), INVALID_BB}); + ctx.loop_and_label_stack.emplace_back ( + false, label, label_var, new_bb (), INVALID_BB, + ctx.place_db.get_current_scope_id ()); } // Eliminates dead code after break, continue, return. @@ -333,6 +344,8 @@ ExprStmtBuilder::visit (HIR::BlockExpr &block) take_or_create_return_place ( lookup_type (*block.get_final_expr ())))); } + + pop_scope (); } void @@ -340,6 +353,8 @@ ExprStmtBuilder::visit (HIR::ContinueExpr &cont) { LoopAndLabelCtx info = cont.has_label () ? get_label_ctx (cont.get_label ()) : get_unnamed_loop_ctx (); + start_new_consecutive_bb (); + unwind_until (info.continue_bb); push_goto (info.continue_bb); // No code allowed after continue. Handled in BlockExpr. } @@ -352,6 +367,8 @@ ExprStmtBuilder::visit (HIR::BreakExpr &brk) if (brk.has_break_expr ()) push_assignment (info.label_var, visit_expr (*brk.get_expr ())); + start_new_consecutive_bb (); + unwind_until (ctx.place_db.get_scope (info.continue_scope).parent); push_goto (info.break_bb); // No code allowed after continue. Handled in BlockExpr. } @@ -406,6 +423,7 @@ ExprStmtBuilder::visit (HIR::ReturnExpr &ret) { push_assignment (RETURN_VALUE_PLACE, visit_expr (*ret.get_expr ())); } + unwind_until (ROOT_SCOPE); ctx.get_current_bb ().statements.emplace_back (Statement::Kind::RETURN); } @@ -420,9 +438,6 @@ ExprStmtBuilder::visit (HIR::LoopExpr &expr) { auto loop = setup_loop (expr); - push_goto (loop.continue_bb); - - ctx.current_bb = loop.continue_bb; (void) visit_expr (*expr.get_loop_block ()); if (!ctx.get_current_bb ().is_terminated ()) push_goto (loop.continue_bb); @@ -435,9 +450,6 @@ ExprStmtBuilder::visit (HIR::WhileLoopExpr &expr) { auto loop = setup_loop (expr); - push_goto (loop.continue_bb); - - ctx.current_bb = loop.continue_bb; auto cond_val = visit_expr (*expr.get_predicate_expr ()); auto body_bb = new_bb (); push_switch (cond_val, {body_bb, loop.break_bb}); diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-builder-internal.h b/gcc/rust/checks/errors/borrowck/rust-bir-builder-internal.h index eef0f916408a..55f00aa50ac9 100644 --- a/gcc/rust/checks/errors/borrowck/rust-bir-builder-internal.h +++ b/gcc/rust/checks/errors/borrowck/rust-bir-builder-internal.h @@ -66,13 +66,17 @@ struct BuilderContext PlaceId label_var; // For break with value. BasicBlockId break_bb; BasicBlockId continue_bb; // Only valid for loops + ScopeId continue_scope; + // Break scope is the parent of the `continue_scope`. LoopAndLabelCtx (bool is_loop = false, NodeId label = UNKNOWN_NODEID, PlaceId label_var = INVALID_PLACE, BasicBlockId break_bb = INVALID_BB, - BasicBlockId continue_bb = INVALID_BB) + BasicBlockId continue_bb = INVALID_BB, + ScopeId continue_scope = INVALID_SCOPE) : is_loop (is_loop), label (label), label_var (label_var), - break_bb (break_bb), continue_bb (continue_bb) + break_bb (break_bb), continue_bb (continue_bb), + continue_scope (continue_scope) {} }; @@ -174,7 +178,37 @@ protected: // In debug mode, check that the variable is not already declared. rust_assert (ctx.place_db.lookup_variable (nodeid) == INVALID_PLACE); - return ctx.place_db.add_variable (nodeid, ty); + auto place = ctx.place_db.add_variable (nodeid, ty); + + if (ctx.place_db.get_current_scope_id () != 0) + push_storage_live (place); + + return place; + } + + void push_new_scope () { ctx.place_db.push_new_scope (); } + + void pop_scope () + { + auto &scope = ctx.place_db.get_current_scope (); + if (ctx.place_db.get_current_scope_id () != 0) + { + std::for_each (scope.locals.rbegin (), scope.locals.rend (), + [&] (PlaceId place) { push_storage_dead (place); }); + } + ctx.place_db.pop_scope (); + } + + void unwind_until (ScopeId final_scope) + { + auto current_scope_id = ctx.place_db.get_current_scope_id (); + while (current_scope_id != final_scope) + { + auto &scope = ctx.place_db.get_scope (current_scope_id); + std::for_each (scope.locals.rbegin (), scope.locals.rend (), + [&] (PlaceId place) { push_storage_dead (place); }); + current_scope_id = scope.parent; + } } protected: // Helpers to add BIR statements @@ -192,6 +226,7 @@ protected: // Helpers to add BIR statements void push_tmp_assignment (AbstractExpr *rhs, TyTy::BaseType *tyty) { PlaceId tmp = ctx.place_db.add_temporary (tyty); + push_storage_live (tmp); push_assignment (tmp, rhs); } @@ -212,6 +247,18 @@ protected: // Helpers to add BIR statements ctx.get_current_bb ().successors.push_back (bb); } + void push_storage_live (PlaceId place) + { + ctx.get_current_bb ().statements.emplace_back ( + Statement::Kind::STORAGE_LIVE, place); + } + + void push_storage_dead (PlaceId place) + { + ctx.get_current_bb ().statements.emplace_back ( + Statement::Kind::STORAGE_DEAD, place); + } + PlaceId declare_rvalue (PlaceId place) { ctx.place_db[place].is_rvalue = true; @@ -228,7 +275,10 @@ protected: // Helpers to add BIR statements { auto copy = ctx.place_db.into_rvalue (arg); if (copy != arg) - push_assignment (copy, arg); + { + push_storage_live (copy); + push_assignment (copy, arg); + } return copy; } @@ -248,7 +298,14 @@ protected: // CFG helpers BasicBlockId start_new_consecutive_bb () { BasicBlockId bb = new_bb (); - ctx.get_current_bb ().successors.emplace_back (bb); + if (!ctx.get_current_bb ().is_terminated ()) + { + push_goto (bb); + } + else + { + add_jump_to (bb); + } ctx.current_bb = bb; return bb; } @@ -456,10 +513,17 @@ protected: PlaceId take_or_create_return_place (TyTy::BaseType *type) { - auto result = (expr_return_place != INVALID_PLACE) - ? expr_return_place - : ctx.place_db.add_temporary (type); - expr_return_place = INVALID_PLACE; + PlaceId result = INVALID_PLACE; + if (expr_return_place != INVALID_PLACE) + { + result = expr_return_place; + expr_return_place = INVALID_PLACE; + } + else + { + result = ctx.place_db.add_temporary (type); + push_storage_live (result); + } return result; } }; diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-dump.cc b/gcc/rust/checks/errors/borrowck/rust-bir-dump.cc index 3684ad7b8895..4dea27e30383 100644 --- a/gcc/rust/checks/errors/borrowck/rust-bir-dump.cc +++ b/gcc/rust/checks/errors/borrowck/rust-bir-dump.cc @@ -120,19 +120,7 @@ Dump::go (bool enable_simplify_cfg) << " {\n"; // Print locals declaration. - for (PlaceId id = FIRST_VARIABLE_PLACE; id < func.place_db.size (); ++id) - { - const Place &place = func.place_db[id]; - if (place.kind == Place::VARIABLE || place.kind == Place::TEMPORARY) - { - if (std::find (func.arguments.begin (), func.arguments.end (), id) - != func.arguments.end ()) - continue; - stream << indentation << "let _"; - stream << place_map[id] << ": " - << get_tyty_name (func.place_db[id].tyty) << ";\n"; - } - } + visit_scope (0); // Print BBs. for (statement_bb = 0; statement_bb < func.basic_blocks.size (); @@ -200,12 +188,12 @@ Dump::visit (Statement &stmt) break; case Statement::Kind::STORAGE_DEAD: stream << "StorageDead("; - visit_move_place (stmt.get_place ()); + visit_place (stmt.get_place ()); stream << ")"; break; case Statement::Kind::STORAGE_LIVE: stream << "StorageLive("; - visit_move_place (stmt.get_place ()); + visit_place (stmt.get_place ()); stream << ")"; break; } @@ -333,11 +321,45 @@ Dump::visit (Operator<2> &expr) visit_move_place (expr.get_operand<1> ()); stream << ")"; } + void Dump::visit (Assignment &expr) { visit_move_place (expr.get_rhs ()); } +std::ostream & +Dump::indent (size_t depth) +{ + for (size_t i = 0; i < depth; ++i) + stream << indentation; + return stream; +} + +void +Dump::visit_scope (ScopeId id, size_t depth) +{ + auto scope = func.place_db.get_scope (id); + if (scope.locals.empty () && scope.children.empty ()) + return; + + if (id > 1) + { + indent (depth) << "scope " << id - 1 << " {\n"; + } + for (auto &local : scope.locals) + { + indent (depth + 1) << "let _"; + stream << place_map[local] << ": " + << get_tyty_name (func.place_db[local].tyty) << ";\n"; + } + for (auto &child : scope.children) + { + visit_scope (child, (id >= 1) ? depth + 1 : depth); + } + if (id > 1) + indent (depth) << "}\n"; +} + } // namespace BIR } // namespace Rust diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-dump.h b/gcc/rust/checks/errors/borrowck/rust-bir-dump.h index 7ee94d749e3d..cc3f9cdc7386 100644 --- a/gcc/rust/checks/errors/borrowck/rust-bir-dump.h +++ b/gcc/rust/checks/errors/borrowck/rust-bir-dump.h @@ -59,6 +59,9 @@ protected: void visit (Operator<1> &expr) override; void visit (Operator<2> &expr) override; void visit (Assignment &expr) override; + void visit_scope (ScopeId id, size_t depth = 1); + + std::ostream &indent (size_t depth); }; } // namespace BIR diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-place.h b/gcc/rust/checks/errors/borrowck/rust-bir-place.h index e62ec3557ad4..61e90d58d263 100644 --- a/gcc/rust/checks/errors/borrowck/rust-bir-place.h +++ b/gcc/rust/checks/errors/borrowck/rust-bir-place.h @@ -105,12 +105,30 @@ struct Place {} }; +using ScopeId = uint32_t; + +static constexpr ScopeId INVALID_SCOPE = std::numeric_limits::max (); +/** Arguments and return value are in the root scope. */ +static constexpr ScopeId ROOT_SCOPE = 0; +/** Top-level local variables are in the top-level scope. */ +static constexpr ScopeId TOP_LEVEL_SCOPE = 1; + +struct Scope +{ + ScopeId parent = INVALID_SCOPE; + std::vector children; + std::vector locals; +}; + /** Allocated places and keeps track of paths. */ class PlaceDB { +private: // Possible optimizations: separate variables to speedup lookup. std::vector places; std::unordered_map constants_lookup; + std::vector scopes; + ScopeId current_scope = 0; public: PlaceDB () @@ -118,6 +136,8 @@ public: // Reserved index for invalid place. places.push_back ( {Place::INVALID, 0, {}, false, false, NO_LIFETIME, nullptr}); + + scopes.emplace_back (); // Root scope. } Place &operator[] (PlaceId id) { return places.at (id); } @@ -125,6 +145,30 @@ public: size_t size () const { return places.size (); } + ScopeId get_current_scope_id () const { return current_scope; } + + const std::vector &get_scopes () const { return scopes; } + + const Scope &get_current_scope () const { return scopes[current_scope]; } + + const Scope &get_scope (ScopeId id) const { return scopes[id]; } + + ScopeId push_new_scope () + { + ScopeId new_scope = scopes.size (); + scopes.emplace_back (); + scopes[new_scope].parent = current_scope; + scopes[current_scope].children.push_back (new_scope); + current_scope = new_scope; + return new_scope; + } + + ScopeId pop_scope () + { + current_scope = scopes[current_scope].parent; + return current_scope; + } + PlaceId add_place (Place place, PlaceId last_sibling = 0) { places.push_back (place); @@ -137,6 +181,12 @@ public: { places[last_sibling].path.next_sibling = new_place; } + + if (place.kind == Place::VARIABLE || place.kind == Place::TEMPORARY) + { + scopes[current_scope].locals.push_back (new_place); + } + return new_place; } @@ -166,9 +216,9 @@ public: current = places[current].path.next_sibling; } } - return add_place ( - {kind, id, {parent, 0, 0}, is_type_copy (tyty), false, NO_LIFETIME, tyty}, - current); + return add_place ({kind, id, Place::Path{parent, 0, 0}, is_type_copy (tyty), + false, NO_LIFETIME, tyty}, + current); } PlaceId add_temporary (TyTy::BaseType *tyty) -- 2.43.5