8000 Generalize small dominators optimization by tmiasko · Pull Request #116454 · rust-lang/rust · GitHub
[go: up one dir, main page]
Skip to content

Generalize small dominators optimization #116454

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 6 commits into from
Oct 8, 2023
Merged

Generalize small dominators optimization #116454

Changes from 1 commit
Commits
Show all changes
6 commits
Select commit Hold shift + click to select a range
a8ec7dd
Test immediate dominators using public API
tmiasko Oct 5, 2023
ba694e3
Remove redundant Dominators::start_node field
tmiasko Oct 5, 2023
0528d37
Optimize dominators for small path graphs
tmiasko Oct 5, 2023
6c348b7
Remove small dominators optimization from SsaLocals
tmiasko Oct 5, 2023
4357482
Move DefLocation from rustc_codegen_ssa to rustc_middle
tmiasko Oct 5, 2023
eaafb25
Replace LocationExtended with DefLocation in SsaLocals
tmiasko Oct 5, 2023
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Replace LocationExtended with DefLocation in SsaLocals
  • Loading branch information
@tmiasko
tmiasko committed Oct 5, 2023
commit eaafb256f8e729338603476ab1e54b804efead91
38 changes: 11 additions & 27 deletions compiler/rustc_mir_transform/src/ssa.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -15,7 +15,7 @@ use rustc_middle::mir::*;

pub struct SsaLocals {
/// Assignments to each local. This defines whether the local is SSA.
assignments: IndexVec<Local, Set1<LocationExtended>>,
assignments: IndexVec<Local, Set1<DefLocation>>,
/// We visit the body in reverse postorder, to ensure each local is assigned before it is used.
/// We remember the order in which we saw the assignments to compute the SSA values in a single
/// pass.
Expand All @@ -38,7 +38,7 @@ impl SsaLocals {
let mut visitor = SsaVisitor { assignments, assignment_order, dominators, direct_uses };

for local in body.args_iter() {
visitor.assignments[local] = Set1::One(LocationExtended::Arg);
visitor.assignments[local] = Set1::One(DefLocation::Argument);
}

// For SSA assignments, a RPO visit will see the assignment before it sees any use.
Expand Down Expand Up @@ -94,14 +94,7 @@ impl SsaLocals {
location: Location,
) -> bool {
match self.assignments[local] {
Set1::One(LocationExtended::Arg) => true,
Set1::One(LocationExtended::Plain(ass)) => {
if ass.block == location.block {
ass.statement_index < location.statement_index
} else {
dominators.dominates(ass.block, location.block)
}
}
Set1::One(def) => def.dominates(location, dominators),
_ => false,
}
}
Expand All @@ -111,7 +104,7 @@ impl SsaLocals {
body: &'a Body<'tcx>,
) -> impl Iterator<Item = (Local, &'a Rvalue<'tcx>, Location)> + 'a {
self.assignment_order.iter().filter_map(|&local| {
if let Set1::One(LocationExtended::Plain(loc)) = self.assignments[local] {
if let Set1::One(DefLocation::Body(loc)) = self.assignments[local] {
// `loc` must point to a direct assignment to `local`.
let Either::Left(stmt) = body.stmt_at(loc) else { bug!() };
let Some((target, rvalue)) = stmt.kind.as_assign() else { bug!() };
Expand All @@ -129,7 +122,7 @@ impl SsaLocals {
mut f: impl FnMut(Local, &mut Rvalue<'tcx>, Location),
) {
for &local in &self.assignment_order {
if let Set1::One(LocationExtended::Plain(loc)) = self.assignments[local] {
if let Set1::One(DefLocation::Body(loc)) = self.assignments[local] {
// `loc` must point to a direct assignment to `local`.
let bbs = basic_blocks.as_mut_preserves_cfg();
let bb = &mut bbs[loc.block];
Expand Down Expand Up @@ -187,15 +180,9 @@ impl SsaLocals {
}
}

#[derive(Copy, Clone, Debug, PartialEq, Eq)]
enum LocationExtended {
Plain(Location),
Arg,
}

struct SsaVisitor<'a> {
dominators: &'a Dominators<BasicBlock>,
assignments: IndexVec<Local, Set1<LocationExtended>>,
assignments: IndexVec<Local, Set1<DefLocation>>,
assignment_order: Vec<Local>,
direct_uses: IndexVec<Local, u32>,
}
Expand All @@ -205,10 +192,7 @@ impl SsaVisitor<'_> {
let set = &mut self.assignments[local];
let assign_dominates = match *set {
Set1::Empty | Set1::Many => false,
Set1::One(LocationExtended::Arg) => true,
Set1::One(LocationExtended::Plain(assign)) => {
assign.successor_within_block().dominates(loc, self.dominators)
}
Set1::One(def) => def.dominates(loc, self.dominators),
};
// We are visiting a use that is not dominated by an assignment.
// Either there is a cycle involved, or we are reading for uninitialized local.
Expand Down Expand Up @@ -262,7 +246,7 @@ impl<'tcx> Visitor<'tcx> for SsaVisitor<'_> {

fn visit_assign(&mut self, place: &Place<'tcx>, rvalue: &Rvalue<'tcx>, loc: Location) {
if let Some(local) = place.as_local() {
self.assignments[local].insert(LocationExtended::Plain(loc));
self.assignments[local].insert(DefLocation::Body(loc));
if let Set1::One(_) = self.assignments[local] {
// Only record if SSA-like, to avoid growing the vector needlessly.
self.assignment_order.push(local);
Expand Down Expand Up @@ -338,7 +322,7 @@ fn compute_copy_classes(ssa: &mut SsaLocals, body: &Body<'_>) {
#[derive(Debug)]
pub(crate) struct StorageLiveLocals {
/// Set of "StorageLive" statements for each local.
storage_live: IndexVec<Local, Set1<LocationExtended>>,
storage_live: IndexVec<Local, Set1<DefLocation>>,
}

impl StorageLiveLocals {
Expand All @@ -348,13 +332,13 @@ impl StorageLiveLocals {
) -> StorageLiveLocals {
let mut storage_live = IndexVec::from_elem(Set1::Empty, &body.local_decls);
for local in always_storage_live_locals.iter() {
storage_live[local] = Set1::One(LocationExtended::Arg);
storage_live[local] = Set1::One(DefLocation::Argument);
}
for (block, bbdata) in body.basic_blocks.iter_enumerated() {
for (statement_index, statement) in bbdata.statements.iter().enumerate() {
if let StatementKind::StorageLive(local) = statement.kind {
storage_live[local]
.insert(LocationExtended::Plain(Location { block, statement_index }));
.insert(DefLocation::Body(Location { block, statement_index }));
}
}
}
Expand Down
0