1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
//! Liveness analysis for SSA values.
//!
//! This module computes the live range of all the SSA values in a function and produces a
//! `LiveRange` instance for each.
//!
//!
//! # Liveness consumers
//!
//! The primary consumer of the liveness analysis is the SSA coloring pass which goes through each
//! block and assigns a register to the defined values. This algorithm needs to maintain a set of the
//! currently live values as it is iterating down the instructions in the block. It asks the
//! following questions:
//!
//! - What is the set of live values at the entry to the block?
//! - When moving past a use of a value, is that value still alive in the block, or was that the last
//!   use?
//! - When moving past a branch, which of the live values are still live below the branch?
//!
//! The set of `LiveRange` instances can answer these questions through their `def_local_end` and
//! `livein_local_end` queries. The coloring algorithm visits blocks in a topological order of the
//! dominator tree, so it can compute the set of live values at the beginning of a block by starting
//! from the set of live values at the dominating branch instruction and filtering it with
//! `livein_local_end`. These sets do not need to be stored in the liveness analysis.
//!
//! The secondary consumer of the liveness analysis is the spilling pass which needs to count the
//! number of live values at every program point and insert spill code until the number of
//! registers needed is small enough.
//!
//!
//! # Alternative algorithms
//!
//! A number of different liveness analysis algorithms exist, so it is worthwhile to look at a few
//! alternatives.
//!
//! ## Data-flow equations
//!
//! The classic *live variables analysis* that you will find in all compiler books from the
//! previous century does not depend on SSA form. It is typically implemented by iteratively
//! solving data-flow equations on bit-vectors of variables. The result is a live-out bit-vector of
//! variables for every basic block in the program.
//!
//! This algorithm has some disadvantages that makes us look elsewhere:
//!
//! - Quadratic memory use. We need a bit per variable per basic block in the function.
//! - Dense representation of sparse data. In practice, the majority of SSA values never leave
//!   their basic block, and those that do spa basic blocks rarely span a large number of basic
//!   blocks. This makes the data stored in the bitvectors quite sparse.
//! - Traditionally, the data-flow equations were solved for real program *variables* which does
//!   not include temporaries used in evaluating expressions. We have an SSA form program which
//!   blurs the distinction between temporaries and variables. This makes the quadratic memory
//!   problem worse because there are many more SSA values than there was variables in the original
//!   program, and we don't know a priori which SSA values leave their basic block.
//! - Missing last-use information. For values that are not live-out of a basic block, we would
//!   need to store information about the last use in the block somewhere. LLVM stores this
//!   information as a 'kill bit' on the last use in the IR. Maintaining these kill bits has been a
//!   source of problems for LLVM's register allocator.
//!
//! Data-flow equations can detect when a variable is used uninitialized, and they can handle
//! multiple definitions of the same variable. We don't need this generality since we already have
//! a program in SSA form.
//!
//! ## LLVM's liveness analysis
//!
//! LLVM's register allocator computes liveness per *virtual register*, where a virtual register is
//! a disjoint union of related SSA values that should be assigned to the same physical register.
//! It uses a compact data structure very similar to our `LiveRange`. The important difference is
//! that Cranelift's `LiveRange` only describes a single SSA value, while LLVM's `LiveInterval`
//! describes the live range of a virtual register *and* which one of the related SSA values is
//! live at any given program point.
//!
//! LLVM computes the live range of each virtual register independently by using the use-def chains
//! that are baked into its IR. The algorithm for a single virtual register is:
//!
//! 1. Initialize the live range with a single-instruction snippet of liveness at each def, using
//!    the def-chain. This does not include any phi-values.
//! 2. Go through the virtual register's use chain and perform the following steps at each use:
//! 3. Perform an exhaustive depth-first traversal up the CFG from the use. Look for basic blocks
//!    that already contain some liveness and extend the last live SSA value in the block to be
//!    live-out. Also build a list of new basic blocks where the register needs to be live-in.
//! 4. Iteratively propagate live-out SSA values to the new live-in blocks. This may require new
//!    PHI values to be created when different SSA values can reach the same block.
//!
//! The iterative SSA form reconstruction can be skipped if the depth-first search only encountered
//! one SSA value.
//!
//! This algorithm has some advantages compared to the data-flow equations:
//!
//! - The live ranges of local virtual registers are computed very quickly without ever traversing
//!   the CFG. The memory needed to store these live ranges is independent of the number of basic
//!   blocks in the program.
//! - The time to compute the live range of a global virtual register is proportional to the number
//!   of basic blocks covered. Many virtual registers only cover a few blocks, even in very large
//!   functions.
//! - A single live range can be recomputed after making modifications to the IR. No global
//!   algorithm is necessary. This feature depends on having use-def chains for virtual registers
//!   which Cranelift doesn't.
//!
//! Cranelift uses a very similar data structures and algorithms to LLVM, with the important
//! difference that live ranges are computed per SSA value instead of per virtual register, and the
//! uses in Cranelift IR refers to SSA values instead of virtual registers. This means that
//! Cranelift can skip the last step of reconstructing SSA form for the virtual register uses.
//!
//! ## Fast Liveness Checking for SSA-Form Programs
//!
//! A liveness analysis that is often brought up in the context of SSA-based register allocation
//! was presented at CGO 2008:
//!
//! > Boissinot, B., Hack, S., Grund, D., de Dinechin, B. D., & Rastello, F. (2008). *Fast Liveness
//! Checking for SSA-Form Programs.* CGO.
//!
//! This analysis uses a global pre-computation that only depends on the CFG of the function. It
//! then allows liveness queries for any (value, program point) pair. Each query traverses the use
//! chain of the value and performs lookups in the precomputed bit-vectors.
//!
//! I did not seriously consider this analysis for Cranelift because:
//!
//! - It depends critically on use chains which Cranelift doesn't have.
//! - Popular variables like the `this` pointer in a C++ method can have very large use chains.
//!   Traversing such a long use chain on every liveness lookup has the potential for some nasty
//!   quadratic behavior in unfortunate cases.
//! - It says "fast" in the title, but the paper only claims to be 16% faster than a data-flow
//!   based approach, which isn't that impressive.
//!
//! Nevertheless, the property of only depending in the CFG structure is very useful. If Cranelift
//! gains use chains, this approach would be worth a proper evaluation.
//!
//!
//! # Cranelift's liveness analysis
//!
//! The algorithm implemented in this module is similar to LLVM's with these differences:
//!
//! - The `LiveRange` data structure describes the liveness of a single SSA value, not a virtual
//!   register.
//! - Instructions in Cranelift IR contains references to SSA values, not virtual registers.
//! - All live ranges are computed in one traversal of the program. Cranelift doesn't have use
//!   chains, so it is not possible to compute the live range for a single SSA value independently.
//!
//! The liveness computation visits all instructions in the program. The order is not important for
//! the algorithm to be correct. At each instruction, the used values are examined.
//!
//! - The first time a value is encountered, its live range is constructed as a dead live range
//!   containing only the defining program point.
//! - The local interval of the value's live range is extended so it reaches the use. This may
//!   require creating a new live-in local interval for the block.
//! - If the live range became live-in to the block, add the block to a work-list.
//! - While the work-list is non-empty pop a live-in block and repeat the two steps above, using each
//!   of the live-in block's CFG predecessor instructions as a 'use'.
//!
//! The effect of this algorithm is to extend the live range of each to reach uses as they are
//! visited. No data about each value beyond the live range is needed between visiting uses, so
//! nothing is lost by computing the live range of all values simultaneously.
//!
//! ## Cache efficiency of Cranelift vs LLVM
//!
//! Since LLVM computes the complete live range of a virtual register in one go, it can keep the
//! whole `LiveInterval` for the register in L1 cache. Since it is visiting the instructions in use
//! chain order, some cache thrashing can occur as a result of pulling instructions into cache
//! somewhat chaotically.
//!
//! Cranelift uses a transposed algorithm, visiting instructions in order. This means that each
//! instruction is brought into cache only once, and it is likely that the other instructions on
//! the same cache line will be visited before the line is evicted.
//!
//! Cranelift's problem is that the `LiveRange` structs are visited many times and not always
//! regularly. We should strive to make the `LiveRange` struct as small as possible such that
//! multiple related values can live on the same cache line.
//!
//! - Local values should fit in a 16-byte `LiveRange` struct or smaller. The current
//!   implementation contains a 24-byte `Vec` object and a redundant `value` member pushing the
//!   size to 32 bytes.
//! - Related values should be stored on the same cache line. The current sparse set implementation
//!   does a decent job of that.
//! - For global values, the list of live-in intervals is very likely to fit on a single cache
//!   line. These lists are very likely to be found in L2 cache at least.
//!
//! There is some room for improvement.

use crate::entity::SparseMap;
use crate::flowgraph::{BlockPredecessor, ControlFlowGraph};
use crate::ir::dfg::ValueDef;
use crate::ir::{Block, Function, Inst, Layout, ProgramPoint, Value};
use crate::isa::{EncInfo, OperandConstraint, TargetIsa};
use crate::regalloc::affinity::Affinity;
use crate::regalloc::liverange::LiveRange;
use crate::timing;
use alloc::vec::Vec;
use core::mem;
use core::ops::Index;

/// A set of live ranges, indexed by value number.
type LiveRangeSet = SparseMap<Value, LiveRange>;

/// Get a mutable reference to the live range for `value`.
/// Create it if necessary.
fn get_or_create<'a>(
    lrset: &'a mut LiveRangeSet,
    value: Value,
    isa: &dyn TargetIsa,
    func: &Function,
    encinfo: &EncInfo,
) -> &'a mut LiveRange {
    // It would be better to use `get_mut()` here, but that leads to borrow checker fighting
    // which can probably only be resolved by non-lexical lifetimes.
    // https://github.com/rust-lang/rfcs/issues/811
    if lrset.get(value).is_none() {
        // Create a live range for value. We need the program point that defines it.
        let def;
        let affinity;
        match func.dfg.value_def(value) {
            ValueDef::Result(inst, rnum) => {
                def = inst.into();
                // Initialize the affinity from the defining instruction's result constraints.
                // Don't do this for call return values which are always tied to a single register.
                affinity = encinfo
                    .operand_constraints(func.encodings[inst])
                    .and_then(|rc| rc.outs.get(rnum))
                    .map(Affinity::new)
                    .or_else(|| {
                        // If this is a call, get the return value affinity.
                        func.dfg
                            .call_signature(inst)
                            .map(|sig| Affinity::abi(&func.dfg.signatures[sig].returns[rnum], isa))
                    })
                    .unwrap_or_default();
            }
            ValueDef::Param(block, num) => {
                def = block.into();
                if func.layout.entry_block() == Some(block) {
                    // The affinity for entry block parameters can be inferred from the function
                    // signature.
                    affinity = Affinity::abi(&func.signature.params[num], isa);
                } else {
                    // Give normal block parameters a register affinity matching their type.
                    let rc = isa.regclass_for_abi_type(func.dfg.value_type(value));
                    affinity = Affinity::Reg(rc.into());
                }
            }
        };
        lrset.insert(LiveRange::new(value, def, affinity));
    }
    lrset.get_mut(value).unwrap()
}

/// Extend the live range for `value` so it reaches `to` which must live in `block`.
fn extend_to_use(
    lr: &mut LiveRange,
    block: Block,
    to: Inst,
    worklist: &mut Vec<Block>,
    func: &Function,
    cfg: &ControlFlowGraph,
) {
    // This is our scratch working space, and we'll leave it empty when we return.
    debug_assert!(worklist.is_empty());

    // Extend the range locally in `block`.
    // If there already was a live interval in that block, we're done.
    if lr.extend_in_block(block, to, &func.layout) {
        worklist.push(block);
    }

    // The work list contains those blocks where we have learned that the value needs to be
    // live-in.
    //
    // This algorithm becomes a depth-first traversal up the CFG, enumerating all paths through the
    // CFG from the existing live range to `block`.
    //
    // Extend the live range as we go. The live range itself also serves as a visited set since
    // `extend_in_block` will never return true twice for the same block.
    //
    while let Some(livein) = worklist.pop() {
        // We've learned that the value needs to be live-in to the `livein` block.
        // Make sure it is also live at all predecessor branches to `livein`.
        for BlockPredecessor {
            block: pred,
            inst: branch,
        } in cfg.pred_iter(livein)
        {
            if lr.extend_in_block(pred, branch, &func.layout) {
                // This predecessor block also became live-in. We need to process it later.
                worklist.push(pred);
            }
        }
    }
}

/// Liveness analysis for a function.
///
/// Compute a live range for every SSA value used in the function.
pub struct Liveness {
    /// The live ranges that have been computed so far.
    ranges: LiveRangeSet,

    /// Working space for the `extend_to_use` algorithm.
    /// This vector is always empty, except for inside that function.
    /// It lives here to avoid repeated allocation of scratch memory.
    worklist: Vec<Block>,
}

impl Liveness {
    /// Create a new empty liveness analysis.
    ///
    /// The memory allocated for this analysis can be reused for multiple functions. Use the
    /// `compute` method to actually runs the analysis for a function.
    pub fn new() -> Self {
        Self {
            ranges: LiveRangeSet::new(),
            worklist: Vec::new(),
        }
    }

    /// Current live ranges.
    pub fn ranges(&self) -> &LiveRangeSet {
        &self.ranges
    }

    /// Clear all data structures in this liveness analysis.
    pub fn clear(&mut self) {
        self.ranges.clear();
        self.worklist.clear();
    }

    /// Get the live range for `value`, if it exists.
    pub fn get(&self, value: Value) -> Option<&LiveRange> {
        self.ranges.get(value)
    }

    /// Create a new live range for `value`.
    ///
    /// The new live range will be defined at `def` with no extent, like a dead value.
    ///
    /// This asserts that `value` does not have an existing live range.
    pub fn create_dead<PP>(&mut self, value: Value, def: PP, affinity: Affinity)
    where
        PP: Into<ProgramPoint>,
    {
        let old = self
            .ranges
            .insert(LiveRange::new(value, def.into(), affinity));
        debug_assert!(old.is_none(), "{} already has a live range", value);
    }

    /// Move the definition of `value` to `def`.
    ///
    /// The old and new def points must be in the same block, and before the end of the live range.
    pub fn move_def_locally<PP>(&mut self, value: Value, def: PP)
    where
        PP: Into<ProgramPoint>,
    {
        let lr = self.ranges.get_mut(value).expect("Value has no live range");
        lr.move_def_locally(def.into());
    }

    /// Locally extend the live range for `value` to reach `user`.
    ///
    /// It is assumed the `value` is already live before `user` in `block`.
    ///
    /// Returns a mutable reference to the value's affinity in case that also needs to be updated.
    pub fn extend_locally(
        &mut self,
        value: Value,
        block: Block,
        user: Inst,
        layout: &Layout,
    ) -> &mut Affinity {
        debug_assert_eq!(Some(block), layout.inst_block(user));
        let lr = self.ranges.get_mut(value).expect("Value has no live range");
        let livein = lr.extend_in_block(block, user, layout);
        debug_assert!(!livein, "{} should already be live in {}", value, block);
        &mut lr.affinity
    }

    /// Change the affinity of `value` to `Stack` and return the previous affinity.
    pub fn spill(&mut self, value: Value) -> Affinity {
        let lr = self.ranges.get_mut(value).expect("Value has no live range");
        mem::replace(&mut lr.affinity, Affinity::Stack)
    }

    /// Compute the live ranges of all SSA values used in `func`.
    /// This clears out any existing analysis stored in this data structure.
    pub fn compute(&mut self, isa: &dyn TargetIsa, func: &mut Function, cfg: &ControlFlowGraph) {
        let _tt = timing::ra_liveness();
        self.ranges.clear();

        // Get ISA data structures used for computing live range affinities.
        let encinfo = isa.encoding_info();
        let reginfo = isa.register_info();

        // The liveness computation needs to visit all uses, but the order doesn't matter.
        // TODO: Perhaps this traversal of the function could be combined with a dead code
        // elimination pass if we visit a post-order of the dominator tree?
        for block in func.layout.blocks() {
            // Make sure we have created live ranges for dead block parameters.
            // TODO: If these parameters are really dead, we could remove them, except for the
            // entry block which must match the function signature.
            for &arg in func.dfg.block_params(block) {
                get_or_create(&mut self.ranges, arg, isa, func, &encinfo);
            }

            for inst in func.layout.block_insts(block) {
                // Eliminate all value aliases, they would confuse the register allocator.
                func.dfg.resolve_aliases_in_arguments(inst);

                // Make sure we have created live ranges for dead defs.
                // TODO: When we implement DCE, we can use the absence of a live range to indicate
                // an unused value.
                for &def in func.dfg.inst_results(inst) {
                    get_or_create(&mut self.ranges, def, isa, func, &encinfo);
                }

                // Iterator of constraints, one per value operand.
                let encoding = func.encodings[inst];
                let operand_constraint_slice: &[OperandConstraint] =
                    encinfo.operand_constraints(encoding).map_or(&[], |c| c.ins);
                let mut operand_constraints = operand_constraint_slice.iter();

                for &arg in func.dfg.inst_args(inst) {
                    // Get the live range, create it as a dead range if necessary.
                    let lr = get_or_create(&mut self.ranges, arg, isa, func, &encinfo);

                    // Extend the live range to reach this use.
                    extend_to_use(lr, block, inst, &mut self.worklist, func, cfg);

                    // Apply operand constraint, ignoring any variable arguments after the fixed
                    // operands described by `operand_constraints`. Variable arguments are either
                    // block arguments or call/return ABI arguments.
                    if let Some(constraint) = operand_constraints.next() {
                        lr.affinity.merge(constraint, &reginfo);
                    }
                }
            }
        }
    }
}

impl Index<Value> for Liveness {
    type Output = LiveRange;
    fn index(&self, index: Value) -> &LiveRange {
        self.ranges
            .get(index)
            .unwrap_or_else(|| panic!("{} has no live range", index))
    }
}