Skip to content

Commit 8221feb

Browse files
fitzgenfitzgen
committed
Use b-trees based on bumpalo arenas
Alternative to the other PR. Numbers don't look great? ``` $ cargo run --release -- benchmark -e ~/scratch/bumpalo-arena.so -e ~/scratch/main.so -m perf-counters --stop-after compilation --processes 10 --iterations-per-process 20 --engine-flags="--disable-parallel-compilation --disable-cache" -- benchmarks/spidermonkey/benchmark.wasm benchmarks/bz2/benchmark.wasm benchmarks/pulldown-cmark/benchmark.wasm compilation :: cache-misses :: benchmarks/bz2/benchmark.wasm Δ = 2154.84 ± 788.55 (confidence = 99%) main.so is 1.02x to 1.05x faster than bumpalo-arena.so! [62141 66843.37 75776] bumpalo-arena.so [59523 64688.53 81781] main.so compilation :: cache-accesses :: benchmarks/pulldown-cmark/benchmark.wasm Δ = 8595.08 ± 5795.64 (confidence = 99%) bumpalo-arena.so is 1.01x to 1.03x faster than main.so! [401717 437779.00 545867] bumpalo-arena.so [410908 446374.08 536809] main.so compilation :: cache-accesses :: benchmarks/bz2/benchmark.wasm Δ = 2342.34 ± 2055.41 (confidence = 99%) bumpalo-arena.so is 1.00x to 1.03x faster than main.so! [133753 143249.76 180756] bumpalo-arena.so [135428 145592.10 203005] main.so compilation :: instructions-retired :: benchmarks/pulldown-cmark/benchmark.wasm Δ = 35306.54 ± 32172.66 (confidence = 99%) bumpalo-arena.so is 1.00x to 1.01x faster than main.so! [8801940 8900728.23 9461825] bumpalo-arena.so [8831762 8936034.78 9485351] main.so compilation :: instructions-retired :: benchmarks/spidermonkey/benchmark.wasm Δ = 382102.42 ± 81779.69 (confidence = 99%) bumpalo-arena.so is 1.00x to 1.00x faster than main.so! [208106667 209068806.32 210101434] bumpalo-arena.so [208492210 209450908.75 210448369] main.so compilation :: cpu-cycles :: benchmarks/bz2/benchmark.wasm No difference in performance. [2441143 2659275.73 4199423] bumpalo-arena.so [2392678 2608641.54 5347877] main.so compilation :: cpu-cycles :: benchmarks/pulldown-cmark/benchmark.wasm No difference in performance. [7014995 8113396.99 13667438] bumpalo-arena.so [7371875 7996085.34 13293046] main.so compilation :: cache-misses :: benchmarks/pulldown-cmark/benchmark.wasm No difference in performance. [131096 167836.79 217530] bumpalo-arena.so [128340 169539.35 282605] main.so compilation :: cache-accesses :: benchmarks/spidermonkey/benchmark.wasm No difference in performance. [8780974 9800932.96 10522183] bumpalo-arena.so [8758505 9771531.34 10590536] main.so compilation :: cpu-cycles :: benchmarks/spidermonkey/benchmark.wasm No difference in performance. [185218977 194521807.51 238636300] bumpalo-arena.so [181686455 194998321.78 258060749] main.so compilation :: cache-misses :: benchmarks/spidermonkey/benchmark.wasm No difference in performance. [4330008 4990485.00 5498381] bumpalo-arena.so [4192710 4978995.85 5666416] main.so compilation :: instructions-retired :: benchmarks/bz2/benchmark.wasm No difference in performance. [2361496 2431407.85 3123724] bumpalo-arena.so [2362101 2429567.66 3057998] main.so ```
1 parent 227a9fd commit 8221feb

File tree

11 files changed

+39
-29
lines changed

11 files changed

+39
-29
lines changed

‎Cargo.toml‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,7 @@ description = "Backtracking register allocator inspired from IonMonkey"
1111
repository = "https://github.com/bytecodealliance/regalloc2"
1212

1313
[dependencies]
14+
arena-btree = { git = "https://github.com/bytecodealliance/arena-btree.git", branch = "bumpalo-based-arenas" }
1415
log = { version = "0.4.8", default-features = false }
1516
smallvec = "1.6.1"
1617
fxhash = "0.2.1"

‎src/ion/data_structures.rs‎

Lines changed: 19 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -21,11 +21,14 @@ use crate::{
2121
RegClass, VReg,
2222
};
2323
use fxhash::FxHashSet;
24+
use arena_btree::BTreeMap;
2425
use smallvec::SmallVec;
2526
use std::cmp::Ordering;
26-
use std::collections::{BTreeMap, HashMap, HashSet};
27+
use std::collections::{HashMap, HashSet};
2728
use std::fmt::Debug;
2829

30+
pub use arena_btree::Arena;
31+
2932
/// A range from `from` (inclusive) to `to` (exclusive).
3033
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
3134
pub struct CodeRange {
@@ -288,8 +291,8 @@ pub struct VRegData {
288291
}
289292

290293
#[derive(Clone, Debug)]
291-
pub struct PRegData {
292-
pub allocations: LiveRangeSet,
294+
pub struct PRegData<'arena> {
295+
pub allocations: LiveRangeSet<'arena>,
293296
pub is_stack: bool,
294297
}
295298

@@ -362,8 +365,9 @@ impl BlockparamIn {
362365
}
363366
}
364367

365-
#[derive(Clone, Debug)]
366-
pub struct Env<'a, F: Function> {
368+
pub struct Env<'a, 'arena, F: Function> {
369+
pub arena: &'arena Arena<LiveRangeKey, LiveRangeIndex>,
370+
367371
pub func: &'a F,
368372
pub env: &'a MachineEnv,
369373
pub cfginfo: CFGInfo,
@@ -376,13 +380,13 @@ pub struct Env<'a, F: Function> {
376380
pub bundles: Vec<LiveBundle>,
377381
pub spillsets: Vec<SpillSet>,
378382
pub vregs: Vec<VRegData>,
379-
pub pregs: Vec<PRegData>,
383+
pub pregs: Vec<PRegData<'arena>>,
380384
pub allocation_queue: PrioQueue,
381385
pub safepoints: Vec<Inst>, // Sorted list of safepoint insts.
382386
pub safepoints_per_vreg: HashMap<usize, HashSet<Inst>>,
383387

384388
pub spilled_bundles: Vec<LiveBundleIndex>,
385-
pub spillslots: Vec<SpillSlotData>,
389+
pub spillslots: Vec<SpillSlotData<'arena>>,
386390
pub slots_by_size: Vec<SpillSlotList>,
387391

388392
pub extra_spillslots_by_class: [SmallVec<[Allocation; 2]>; 2],
@@ -437,7 +441,7 @@ pub struct Env<'a, F: Function> {
437441
pub conflict_set: FxHashSet<LiveBundleIndex>,
438442
}
439443

440-
impl<'a, F: Function> Env<'a, F> {
444+
impl<'a, 'arena, F: Function> Env<'a, 'arena, F> {
441445
/// Get the VReg (with bundled RegClass) from a vreg index.
442446
#[inline]
443447
pub fn vreg(&self, index: VRegIndex) -> VReg {
@@ -463,8 +467,8 @@ impl<'a, F: Function> Env<'a, F> {
463467
}
464468

465469
#[derive(Clone, Debug)]
466-
pub struct SpillSlotData {
467-
pub ranges: LiveRangeSet,
470+
pub struct SpillSlotData<'arena> {
471+
pub ranges: LiveRangeSet<'arena>,
468472
pub slots: u32,
469473
pub alloc: Allocation,
470474
}
@@ -501,8 +505,8 @@ pub struct PrioQueueEntry {
501505
}
502506

503507
#[derive(Clone, Debug)]
504-
pub struct LiveRangeSet {
505-
pub btree: BTreeMap<LiveRangeKey, LiveRangeIndex>,
508+
pub struct LiveRangeSet<'arena> {
509+
pub btree: BTreeMap<'arena, LiveRangeKey, LiveRangeIndex>,
506510
}
507511

508512
#[derive(Clone, Copy, Debug)]
@@ -592,10 +596,10 @@ impl PrioQueue {
592596
}
593597
}
594598

595-
impl LiveRangeSet {
596-
pub(crate) fn new() -> Self {
599+
impl<'arena> LiveRangeSet<'arena> {
600+
pub(crate) fn new(arena: &'arena Arena<LiveRangeKey, LiveRangeIndex>) -> Self {
597601
Self {
598-
btree: BTreeMap::new(),
602+
btree: BTreeMap::new(arena),
599603
}
600604
}
601605
}

‎src/ion/dump.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@
33
use super::Env;
44
use crate::{Block, Function, ProgPoint};
55

6-
impl<'a, F: Function> Env<'a, F> {
6+
impl<'a, 'arena, F: Function> Env<'a, 'arena, F> {
77
pub fn dump_state(&self) {
88
trace!("Bundles:");
99
for (i, b) in self.bundles.iter().enumerate() {

‎src/ion/liveranges.rs‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -98,13 +98,13 @@ impl std::ops::Add<SpillWeight> for SpillWeight {
9898
}
9999
}
100100

101-
impl<'a, F: Function> Env<'a, F> {
101+
impl<'a, 'arena, F: Function> Env<'a, 'arena, F> {
102102
pub fn create_pregs_and_vregs(&mut self) {
103103
// Create PRegs from the env.
104104
self.pregs.resize(
105105
PReg::NUM_INDEX,
106106
PRegData {
107-
allocations: LiveRangeSet::new(),
107+
allocations: LiveRangeSet::new(self.arena),
108108
is_stack: false,
109109
},
110110
);

‎src/ion/merge.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -21,7 +21,7 @@ use crate::{
2121
};
2222
use smallvec::smallvec;
2323

24-
impl<'a, F: Function> Env<'a, F> {
24+
impl<'a, 'arena, F: Function> Env<'a, 'arena, F> {
2525
pub fn merge_bundles(&mut self, from: LiveBundleIndex, to: LiveBundleIndex) -> bool {
2626
if from == to {
2727
// Merge bundle into self -- trivial merge.

‎src/ion/mod.rs‎

Lines changed: 7 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,7 @@
1515
1616
use crate::cfg::CFGInfo;
1717
use crate::{Function, MachineEnv, Output, PReg, ProgPoint, RegAllocError, RegClass};
18+
use arena_btree::Arena;
1819
use std::collections::HashMap;
1920

2021
pub(crate) mod data_structures;
@@ -37,15 +38,18 @@ pub(crate) mod moves;
3738
pub(crate) mod spill;
3839
pub(crate) mod stackmap;
3940

40-
impl<'a, F: Function> Env<'a, F> {
41+
impl<'a, 'arena, F: Function> Env<'a, 'arena, F> {
4142
pub(crate) fn new(
4243
func: &'a F,
4344
env: &'a MachineEnv,
45+
arena: &'arena Arena<LiveRangeKey, LiveRangeIndex>,
4446
cfginfo: CFGInfo,
4547
annotations_enabled: bool,
4648
) -> Self {
4749
let n = func.num_insts();
4850
Self {
51+
arena,
52+
4953
func,
5054
env,
5155
cfginfo,
@@ -123,7 +127,8 @@ pub fn run<F: Function>(
123127
) -> Result<Output, RegAllocError> {
124128
let cfginfo = CFGInfo::new(func)?;
125129

126-
let mut env = Env::new(func, mach_env, cfginfo, enable_annotations);
130+
let arena = Arena::new();
131+
let mut env = Env::new(func, mach_env, &arena, cfginfo, enable_annotations);
127132
env.init()?;
128133

129134
env.run()?;

‎src/ion/moves.rs‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -29,7 +29,7 @@ use fxhash::FxHashMap;
2929
use smallvec::{smallvec, SmallVec};
3030
use std::fmt::Debug;
3131

32-
impl<'a, F: Function> Env<'a, F> {
32+
impl<'a, 'arena, F: Function> Env<'a, 'arena, F> {
3333
pub fn is_start_of_block(&self, pos: ProgPoint) -> bool {
3434
let block = self.cfginfo.insn_block[pos.inst().index()];
3535
pos == self.cfginfo.block_entry[block.index()]
@@ -885,8 +885,8 @@ impl<'a, F: Function> Env<'a, F> {
885885
// Redundant-move elimination state tracker.
886886
let mut redundant_moves = RedundantMoveEliminator::default();
887887

888-
fn redundant_move_process_side_effects<'a, F: Function>(
889-
this: &Env<'a, F>,
888+
fn redundant_move_process_side_effects<'a, 'arena, F: Function>(
889+
this: &Env<'a, 'arena, F>,
890890
redundant_moves: &mut RedundantMoveEliminator,
891891
from: ProgPoint,
892892
to: ProgPoint,

‎src/ion/process.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -37,7 +37,7 @@ pub enum AllocRegResult {
3737
ConflictHighCost,
3838
}
3939

40-
impl<'a, F: Function> Env<'a, F> {
40+
impl<'a, 'arena, F: Function> Env<'a, 'arena, F> {
4141
pub fn process_bundles(&mut self) -> Result<(), RegAllocError> {
4242
while let Some((bundle, reg_hint)) = self.allocation_queue.pop() {
4343
self.stats.process_bundle_count += 1;

‎src/ion/requirement.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -104,7 +104,7 @@ impl Requirement {
104104
}
105105
}
106106

107-
impl<'a, F: Function> Env<'a, F> {
107+
impl<'a, 'arena, F: Function> Env<'a, 'arena, F> {
108108
#[inline(always)]
109109
pub fn requirement_from_operand(&self, op: Operand) -> Requirement {
110110
match op.constraint() {

‎src/ion/spill.rs‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,7 @@ use super::{
1919
use crate::{Allocation, Function, SpillSlot};
2020
use smallvec::smallvec;
2121

22-
impl<'a, F: Function> Env<'a, F> {
22+
impl<'a, 'arena, F: Function> Env<'a, 'arena, F> {
2323
pub fn try_allocating_regs_for_spilled_bundles(&mut self) {
2424
trace!("allocating regs for spilled bundles");
2525
for i in 0..self.spilled_bundles.len() {
@@ -163,7 +163,7 @@ impl<'a, F: Function> Env<'a, F> {
163163
// Allocate a new spillslot.
164164
let spillslot = SpillSlotIndex::new(self.spillslots.len());
165165
self.spillslots.push(SpillSlotData {
166-
ranges: LiveRangeSet::new(),
166+
ranges: LiveRangeSet::new(self.arena),
167167
alloc: Allocation::none(),
168168
slots: size as u32,
169169
});

0 commit comments

Comments
 (0)