@@ -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});
@@ -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;
}
};
@@ -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
@@ -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
@@ -105,12 +105,30 @@ struct Place
{}
};
+using ScopeId = uint32_t;
+
+static constexpr ScopeId INVALID_SCOPE = std::numeric_limits<ScopeId>::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<ScopeId> children;
+ std::vector<PlaceId> locals;
+};
+
/** Allocated places and keeps track of paths. */
class PlaceDB
{
+private:
// Possible optimizations: separate variables to speedup lookup.
std::vector<Place> places;
std::unordered_map<TyTy::BaseType *, PlaceId> constants_lookup;
+ std::vector<Scope> 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<Scope> &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)