From: Lishin <[email protected]>
Track whole-local initialization across BIR control-flow branches.
When a local is moved on only some paths, mark its Drop as conditional.
Keep the existing backend handling for straight-line CFGs and add tests
for static, dead and conditional Drops.
gcc/rust/ChangeLog:
* checks/errors/borrowck/rust-bir-drop-analysis.cc
(struct BlockInitializationState): New struct.
(is_straight_line): New function.
(set_initialized): Likewise.
(set_uninitialized): Likewise.
(merge_state): Likewise.
(update_state_for_statement): Likewise.
(classify_drop): Likewise.
(compute_entry_states): Likewise.
(record_drop_for_straight_line_backend): Likewise.
(annotate_drop_statements): Likewise.
(DropAnalysis::analyze): Propagate initialization state across the
CFG and classify Drop statements.
* checks/errors/borrowck/rust-bir-drop-analysis.h: Update class
comment.
gcc/testsuite/ChangeLog:
* rust/borrowck/drop_analysis_conditional_move.rs: New test.
Signed-off-by: Lishin <[email protected]>
---
This change was merged into the gccrs repository and is posted here for
upstream visibility and potential drive-by review, as requested by GCC
release managers.
Each commit email contains a link to its details on github from where you can
find the Pull-Request and associated discussions.
Commit on github:
https://github.com/Rust-GCC/gccrs/commit/00a99e715512791f52ad68522e38d149c6373310
The commit has NOT been mentioned in any issue.
The commit has been mentioned in the following pull-request(s):
- https://github.com/Rust-GCC/gccrs/pull/4777
.../errors/borrowck/rust-bir-drop-analysis.cc | 391 +++++++++++++-----
.../errors/borrowck/rust-bir-drop-analysis.h | 2 +-
.../drop_analysis_conditional_move.rs | 46 +++
3 files changed, 340 insertions(+), 99 deletions(-)
create mode 100644
gcc/testsuite/rust/borrowck/drop_analysis_conditional_move.rs
diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-drop-analysis.cc
b/gcc/rust/checks/errors/borrowck/rust-bir-drop-analysis.cc
index 09301d86e..2bdf5e5e4 100644
--- a/gcc/rust/checks/errors/borrowck/rust-bir-drop-analysis.cc
+++ b/gcc/rust/checks/errors/borrowck/rust-bir-drop-analysis.cc
@@ -20,145 +20,340 @@
#include "rust-bir.h"
#include "rust-hir-map.h"
-#include <unordered_set>
-
namespace Rust {
namespace BIR {
-
namespace {
-struct BasicBlockIdHash
+struct BlockInitializationState
{
- size_t operator() (BasicBlockId id) const
- {
- return std::hash<uint32_t> () (id.value);
- }
-};
+ explicit BlockInitializationState (size_t place_count)
+ : maybe_initialized (place_count, false),
+ maybe_uninitialized (place_count, false), reachable (false)
+ {}
-} // namespace
+ std::vector<bool> maybe_initialized;
+ std::vector<bool> maybe_uninitialized;
-DropAnalysis &
-DropAnalysis::get ()
+ // Whether this block is reached or not.
+ bool reachable;
+};
+
+static bool
+is_straight_line (const Function &function)
{
- static DropAnalysis instance;
- return instance;
+ std::set<BasicBlockId> visited;
+ BasicBlockId current = ENTRY_BASIC_BLOCK;
+
+ while (current != INVALID_BB)
+ {
+ // Revisiting a block means that the CFG contains a cycle.
+ if (!visited.insert (current).second)
+ return false;
+
+ const BasicBlock &block = function.basic_blocks[current];
+
+ if (block.successors.empty ())
+ return true;
+
+ if (block.successors.size () != 1)
+ return false;
+
+ current = block.successors.front ();
+ }
+
+ return true;
}
-void
-DropAnalysis::clear ()
+static void
+set_initialized (BlockInitializationState &state, PlaceId place)
{
- definitely_dead.clear ();
+ state.maybe_initialized[place.value] = true;
+ state.maybe_uninitialized[place.value] = false;
}
-bool
-DropAnalysis::is_definitely_dead (HirId id) const
+static void
+set_uninitialized (BlockInitializationState &state, PlaceId place)
{
- return definitely_dead.find (id) != definitely_dead.end ();
+ state.maybe_initialized[place.value] = false;
+ state.maybe_uninitialized[place.value] = true;
}
-void
-DropAnalysis::analyze (Function &function)
+// This function combines states from incoming blocks.
+// Take conditional move as example,
+//
+// BB0
+// initialize x
+// / |
+// v v
+// BB1 BB2
+// move x no change
+// \ /
+// v v
+// BB3
+// Drop(x)
+// BB1 -> BB3
+// (BB1): maybe_initialized(x) = false
+// (BB1): maybe_uninitialized(x) = true
+//
+// (BB3): maybe_initialized(x) = true || (BB1): maybe_initialized(x) -> true
+// (BB3): maybe_uninitialized(x) = false || (BB1): maybe_uninitialized(x) ->
+// true
+static bool
+merge_state (BlockInitializationState &into,
+ const BlockInitializationState &from)
{
- std::vector<BasicBlockId> block_order;
- std::unordered_set<BasicBlockId, BasicBlockIdHash> visited;
+ bool changed = false;
- BasicBlockId current = ENTRY_BASIC_BLOCK;
+ if (!into.reachable)
+ {
+ into = from;
+ return !changed;
+ }
- while (current != INVALID_BB)
+ for (size_t i = 0; i < into.maybe_initialized.size (); i++)
{
- // A repeated block indicates a cycle in straight-line control flow.
- if (!visited.insert (current).second)
- return;
+ bool maybe_initialized
+ = into.maybe_initialized[i] || from.maybe_initialized[i];
- block_order.push_back (current);
+ bool maybe_uninitialized
+ = into.maybe_uninitialized[i] || from.maybe_uninitialized[i];
- const BasicBlock &block = function.basic_blocks[current];
+ changed |= maybe_initialized != into.maybe_initialized[i];
+ changed |= maybe_uninitialized != into.maybe_uninitialized[i];
- if (block.successors.empty ())
- break;
+ into.maybe_initialized[i] = maybe_initialized;
+ into.maybe_uninitialized[i] = maybe_uninitialized;
+ }
- if (block.successors.size () != 1)
- return;
+ return changed;
+}
- current = block.successors.front ();
+static void
+update_state_for_statement (Function &function, Statement &statement,
+ BlockInitializationState &state)
+{
+ PlaceId place = statement.get_place ();
+
+ switch (statement.get_kind ())
+ {
+ case Statement::Kind::STORAGE_LIVE:
+ set_uninitialized (state, place);
+ break;
+
+ case Statement::Kind::ASSIGNMENT:
+ {
+ PlaceId lhs = place;
+ AbstractExpr &expr = statement.get_expr ();
+
+ if (expr.get_kind () == ExprKind::ASSIGNMENT)
+ {
+ PlaceId rhs = static_cast<Assignment &> (expr).get_rhs ();
+ const Place &rhs_place = function.place_db[rhs];
+
+ if (rhs_place.kind == Place::VARIABLE
+ && rhs_place.should_be_moved ())
+ set_uninitialized (state, rhs);
+ }
+
+ set_initialized (state, lhs);
+ break;
+ }
+
+ case Statement::Kind::DROP:
+ case Statement::Kind::STORAGE_DEAD:
+ set_uninitialized (state, place);
+ break;
+
+ case Statement::Kind::SWITCH:
+ case Statement::Kind::RETURN:
+ case Statement::Kind::GOTO:
+ case Statement::Kind::USER_TYPE_ASCRIPTION:
+ case Statement::Kind::FAKE_READ:
+ break;
}
+}
+
+static Statement::DropStyle
+classify_drop (const BlockInitializationState &state, PlaceId place)
+{
+ bool maybe_initialized = state.maybe_initialized[place.value];
+ bool maybe_uninitialized = state.maybe_uninitialized[place.value];
+
+ if (!maybe_initialized)
+ return Statement::DropStyle::DEAD;
+
+ if (!maybe_uninitialized)
+ return Statement::DropStyle::STATIC;
+
+ return Statement::DropStyle::CONDITIONAL;
+}
+
+// Compute the initialization state at the entry of every reachable block.
+static std::vector<BlockInitializationState>
+compute_entry_states (Function &function)
+{
+ size_t place_count = function.place_db.size ();
+ size_t block_count = function.basic_blocks.size ();
+
+ std::vector<BlockInitializationState> entry_states;
+ entry_states.reserve (block_count);
+
+ for (size_t i = 0; i < block_count; i++)
+ entry_states.emplace_back (place_count);
+
+ BlockInitializationState &entry_state =
entry_states[ENTRY_BASIC_BLOCK.value];
- std::vector<bool> initialized (function.place_db.size (), false);
+ entry_state.reachable = true;
+
+ // All places start uninitialized, except function arguments.
+ for (size_t i = 0; i < place_count; i++)
+ entry_state.maybe_uninitialized[i] = true;
for (PlaceId argument : function.arguments)
- initialized[argument.value] = true;
+ set_initialized (entry_state, argument);
+
+ std::vector<BasicBlockId> worklist;
+ std::vector<bool> queued (block_count, false);
- for (BasicBlockId block_id : block_order)
+ worklist.push_back (ENTRY_BASIC_BLOCK);
+ queued[ENTRY_BASIC_BLOCK.value] = true;
+
+ // Propagate block states until the last block.
+ while (!worklist.empty ())
{
+ BasicBlockId block_id = worklist.back ();
+ worklist.pop_back ();
+ queued[block_id.value] = false;
+
+ BlockInitializationState state = entry_states[block_id.value];
BasicBlock &block = function.basic_blocks[block_id];
for (Statement &statement : block.statements)
+ update_state_for_statement (function, statement, state);
+
+ for (BasicBlockId successor : block.successors)
{
- PlaceId place = statement.get_place ();
+ bool state_changed
+ = merge_state (entry_states[successor.value], state);
+
+ if (state_changed && !queued[successor.value])
+ {
+ worklist.push_back (successor);
+ queued[successor.value] = true;
+ }
+ }
+ }
+ return entry_states;
+}
+
+static void
+record_drop_for_straight_line_backend (const Function &function, PlaceId place,
+ Statement::DropStyle drop_style,
+ std::set<HirId> &dead_drop_hir_ids,
+ std::set<HirId> &non_dead_drop_hir_ids)
+{
+ const Place &dropped_place = function.place_db[place];
+
+ if (dropped_place.kind != Place::VARIABLE)
+ return;
+
+ auto hir_id = Analysis::Mappings::get ().lookup_node_to_hir (
+ static_cast<NodeId> (dropped_place.variable_or_field_index));
- switch (statement.get_kind ())
+ if (!hir_id.has_value ())
+ return;
+
+ if (drop_style == Statement::DropStyle::DEAD)
+ dead_drop_hir_ids.insert (hir_id.value ());
+ else
+ non_dead_drop_hir_ids.insert (hir_id.value ());
+}
+
+// Walk each reachable block forward from its stable entry state and classify
+// its Drop statements.
+static void
+annotate_drop_statements (
+ Function &function, const std::vector<BlockInitializationState>
&entry_states,
+ bool record_straight_line_backend_drops, std::set<HirId> &dead_drop_hir_ids,
+ std::set<HirId> &non_dead_drop_hir_ids)
+{
+ const size_t block_count = function.basic_blocks.size ();
+
+ for (size_t i = 0; i < block_count; i++)
+ {
+ BlockInitializationState state = entry_states[i];
+
+ if (!state.reachable)
+ continue;
+
+ BasicBlockId block_id = {static_cast<uint32_t> (i)};
+ BasicBlock &block = function.basic_blocks[block_id];
+
+ for (Statement &statement : block.statements)
+ {
+ // A Drop is classified using the state before it executes.
+ if (statement.get_kind () == Statement::Kind::DROP)
{
- case Statement::Kind::STORAGE_LIVE:
- initialized[place.value] = false;
- break;
-
- case Statement::Kind::ASSIGNMENT:
- {
- PlaceId lhs = place;
- AbstractExpr &expr = statement.get_expr ();
-
- if (expr.get_kind () == ExprKind::ASSIGNMENT)
- {
- PlaceId rhs = static_cast<Assignment &> (expr).get_rhs ();
- const Place &rhs_place = function.place_db[rhs];
-
- if (rhs_place.kind == Place::VARIABLE
- && rhs_place.should_be_moved ())
- initialized[rhs.value] = false;
- }
-
- initialized[lhs.value] = true;
- break;
- }
-
- case Statement::Kind::DROP:
- statement.set_drop_style (initialized[place.value]
- ? Statement::DropStyle::STATIC
- : Statement::DropStyle::DEAD);
-
- if (statement.get_drop_style () == Statement::DropStyle::DEAD)
- {
- const Place &dropped_place = function.place_db[place];
-
- if (dropped_place.kind == Place::VARIABLE)
- {
- auto hir_id
- = Analysis::Mappings::get ().lookup_node_to_hir (
- static_cast<NodeId> (
- dropped_place.variable_or_field_index));
-
- if (hir_id.has_value ())
- definitely_dead.insert (hir_id.value ());
- }
- }
-
- initialized[place.value] = false;
- break;
-
- case Statement::Kind::STORAGE_DEAD:
- initialized[place.value] = false;
- break;
-
- case Statement::Kind::SWITCH:
- case Statement::Kind::RETURN:
- case Statement::Kind::GOTO:
- case Statement::Kind::USER_TYPE_ASCRIPTION:
- case Statement::Kind::FAKE_READ:
- break;
+ PlaceId place = statement.get_place ();
+ Statement::DropStyle drop_style = classify_drop (state, place);
+
+ statement.set_drop_style (drop_style);
+
+ if (record_straight_line_backend_drops)
+ record_drop_for_straight_line_backend (function, place,
+ drop_style,
+ dead_drop_hir_ids,
+ non_dead_drop_hir_ids);
}
+
+ // Update the state for the following statement.
+ update_state_for_statement (function, statement, state);
}
}
}
+} // namespace
+
+DropAnalysis &
+DropAnalysis::get ()
+{
+ static DropAnalysis instance;
+ return instance;
+}
+
+void
+DropAnalysis::clear ()
+{
+ definitely_dead.clear ();
+}
+
+bool
+DropAnalysis::is_definitely_dead (HirId id) const
+{
+ return definitely_dead.find (id) != definitely_dead.end ();
+}
+
+void
+DropAnalysis::analyze (Function &function)
+{
+ std::vector<BlockInitializationState> entry_states
+ = compute_entry_states (function);
+
+ // Keep the existing backend handling for straight-line CFGs.
+ const bool record_straight_line_backend_drops = is_straight_line (function);
+
+ std::set<HirId> dead_drop_hir_ids;
+ std::set<HirId> non_dead_drop_hir_ids;
+
+ annotate_drop_statements (function, entry_states,
+ record_straight_line_backend_drops,
+ dead_drop_hir_ids, non_dead_drop_hir_ids);
+
+ // A local is definitely dead only when all of its Drops are dead.
+ for (HirId hir_id : dead_drop_hir_ids)
+ if (non_dead_drop_hir_ids.find (hir_id) == non_dead_drop_hir_ids.end ())
+ definitely_dead.insert (hir_id);
+}
+
} // namespace BIR
} // namespace Rust
diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-drop-analysis.h
b/gcc/rust/checks/errors/borrowck/rust-bir-drop-analysis.h
index 2a52c1355..17a175e08 100644
--- a/gcc/rust/checks/errors/borrowck/rust-bir-drop-analysis.h
+++ b/gcc/rust/checks/errors/borrowck/rust-bir-drop-analysis.h
@@ -28,7 +28,7 @@ namespace BIR {
Classifies scheduled whole-local BIR Drop statements according to
whether their place is initialized at the drop point.
- This initial implementation only handles straight-line control flow.
+ This analysis tracks initialization state across the BIR control-flow graph.
*/
class DropAnalysis
{
diff --git a/gcc/testsuite/rust/borrowck/drop_analysis_conditional_move.rs
b/gcc/testsuite/rust/borrowck/drop_analysis_conditional_move.rs
new file mode 100644
index 000000000..0f58de44c
--- /dev/null
+++ b/gcc/testsuite/rust/borrowck/drop_analysis_conditional_move.rs
@@ -0,0 +1,46 @@
+// { dg-additional-options "-frust-compile-until=compilation
-frust-borrowcheck -frust-dump-bir" }
+// { dg-final { scan-file
bir_dump/drop_analysis_conditional_move.conditional_move.bir.dump
"Drop\\(_3\\): Conditional" } }
+// { dg-final { scan-file
bir_dump/drop_analysis_conditional_move.static_after_join.bir.dump
"Drop\\(_3\\): Static" } }
+// { dg-final { scan-file
bir_dump/drop_analysis_conditional_move.dead_after_join.bir.dump "Drop\\(_3\\):
Dead" } }
+
+#![feature(no_core)]
+#![no_core]
+
+fn conditional_move(condition: bool) {
+ struct A {
+ i: i32,
+ }
+
+ let x = A { i: 1 };
+
+ if condition {
+ let y = x;
+ }
+}
+
+
+fn static_after_join(condition: bool) {
+ struct A {
+ i: i32,
+ }
+
+ let x = A { i: 1 };
+
+ if condition {
+ let y = 1;
+ }
+}
+
+fn dead_after_join(condition: bool) {
+ struct A {
+ i: i32,
+ }
+
+ let x = A { i: 1 };
+
+ if condition {
+ let y = x;
+ } else {
+ let z = x;
+ }
+}
\ No newline at end of file
base-commit: 0fd9c68665c73458385978ac698b7d0b644c7d87
--
2.55.0
