https://gcc.gnu.org/g:7bc7c6ef5e9c840e6e24a1e714dc48051d93f002
commit r17-4288-g7bc7c6ef5e9c840e6e24a1e714dc48051d93f002 Author: Lishin <[email protected]> Date: Sun Aug 9 17:54:54 2026 +0000 gccrs: Handle conditional moves in BIR drop analysis 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]> Diff: --- .../errors/borrowck/rust-bir-drop-analysis.cc | 391 +++++++++++++++------ .../errors/borrowck/rust-bir-drop-analysis.h | 2 +- .../borrowck/drop_analysis_conditional_move.rs | 46 +++ 3 files changed, 340 insertions(+), 99 deletions(-) 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 09301d86eb62..2bdf5e5e4dd6 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 2a52c13550e6..17a175e08d6f 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 000000000000..0f58de44c1bb --- /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
