wasmtime_cranelift/debug/transform/
expression.rs

1use super::address_transform::AddressTransform;
2use super::dbi_log;
3use crate::debug::transform::debug_transform_logging::{
4    dbi_log_enabled, log_get_value_loc, log_get_value_name, log_get_value_ranges,
5};
6use crate::debug::ModuleMemoryOffset;
7use crate::translate::get_vmctx_value_label;
8use anyhow::{Context, Error, Result};
9use core::fmt;
10use cranelift_codegen::ir::ValueLabel;
11use cranelift_codegen::isa::TargetIsa;
12use cranelift_codegen::LabelValueLoc;
13use cranelift_codegen::ValueLabelsRanges;
14use gimli::{write, Expression, Operation, Reader, ReaderOffset};
15use itertools::Itertools;
16use std::cmp::PartialEq;
17use std::collections::{HashMap, HashSet};
18use std::hash::{Hash, Hasher};
19use std::rc::Rc;
20
21#[derive(Debug)]
22pub struct FunctionFrameInfo<'a> {
23    pub value_ranges: &'a ValueLabelsRanges,
24    pub memory_offset: ModuleMemoryOffset,
25}
26
27struct ExpressionWriter(write::EndianVec<gimli::RunTimeEndian>);
28
29enum VmctxBase {
30    Reg(u16),
31    OnStack,
32}
33
34impl ExpressionWriter {
35    fn new() -> Self {
36        let endian = gimli::RunTimeEndian::Little;
37        let writer = write::EndianVec::new(endian);
38        ExpressionWriter(writer)
39    }
40
41    fn write_op(&mut self, op: gimli::DwOp) -> write::Result<()> {
42        self.write_u8(op.0)
43    }
44
45    fn write_op_reg(&mut self, reg: u16) -> write::Result<()> {
46        if reg < 32 {
47            self.write_u8(gimli::constants::DW_OP_reg0.0 + reg as u8)
48        } else {
49            self.write_op(gimli::constants::DW_OP_regx)?;
50            self.write_uleb128(reg.into())
51        }
52    }
53
54    fn write_op_breg(&mut self, reg: u16) -> write::Result<()> {
55        if reg < 32 {
56            self.write_u8(gimli::constants::DW_OP_breg0.0 + reg as u8)
57        } else {
58            self.write_op(gimli::constants::DW_OP_bregx)?;
59            self.write_uleb128(reg.into())
60        }
61    }
62
63    fn write_u8(&mut self, b: u8) -> write::Result<()> {
64        write::Writer::write_u8(&mut self.0, b)
65    }
66
67    fn write_u32(&mut self, b: u32) -> write::Result<()> {
68        write::Writer::write_u32(&mut self.0, b)
69    }
70
71    fn write_uleb128(&mut self, i: u64) -> write::Result<()> {
72        write::Writer::write_uleb128(&mut self.0, i)
73    }
74
75    fn write_sleb128(&mut self, i: i64) -> write::Result<()> {
76        write::Writer::write_sleb128(&mut self.0, i)
77    }
78
79    fn into_vec(self) -> Vec<u8> {
80        self.0.into_vec()
81    }
82
83    fn gen_address_of_memory_base_pointer(
84        &mut self,
85        vmctx: VmctxBase,
86        memory_base: &ModuleMemoryOffset,
87    ) -> write::Result<()> {
88        match *memory_base {
89            ModuleMemoryOffset::Defined(offset) => match vmctx {
90                VmctxBase::Reg(reg) => {
91                    self.write_op_breg(reg)?;
92                    self.write_sleb128(offset.into())?;
93                }
94                VmctxBase::OnStack => {
95                    self.write_op(gimli::constants::DW_OP_consts)?;
96                    self.write_sleb128(offset.into())?;
97                    self.write_op(gimli::constants::DW_OP_plus)?;
98                }
99            },
100            ModuleMemoryOffset::Imported {
101                offset_to_vm_memory_definition,
102                offset_to_memory_base,
103            } => {
104                match vmctx {
105                    VmctxBase::Reg(reg) => {
106                        self.write_op_breg(reg)?;
107                        self.write_sleb128(offset_to_vm_memory_definition.into())?;
108                    }
109                    VmctxBase::OnStack => {
110                        if offset_to_vm_memory_definition > 0 {
111                            self.write_op(gimli::constants::DW_OP_consts)?;
112                            self.write_sleb128(offset_to_vm_memory_definition.into())?;
113                        }
114                        self.write_op(gimli::constants::DW_OP_plus)?;
115                    }
116                }
117                self.write_op(gimli::constants::DW_OP_deref)?;
118                if offset_to_memory_base > 0 {
119                    self.write_op(gimli::constants::DW_OP_consts)?;
120                    self.write_sleb128(offset_to_memory_base.into())?;
121                    self.write_op(gimli::constants::DW_OP_plus)?;
122                }
123            }
124            ModuleMemoryOffset::None => return Err(write::Error::InvalidAttributeValue),
125        }
126        Ok(())
127    }
128}
129
130#[derive(Debug, Clone, PartialEq)]
131enum CompiledExpressionPart {
132    // Untranslated DWARF expression.
133    Code(Vec<u8>),
134    // The wasm-local DWARF operator. The label points to `ValueLabel`.
135    // The trailing field denotes that the operator was last in sequence,
136    // and it is the DWARF location (not a pointer).
137    Local {
138        label: ValueLabel,
139        trailing: bool,
140    },
141    // Dereference is needed.
142    Deref,
143    // Jumping in the expression.
144    Jump {
145        conditionally: bool,
146        target: JumpTargetMarker,
147    },
148    // Floating landing pad.
149    LandingPad(JumpTargetMarker),
150}
151
152#[derive(Debug, Clone, PartialEq)]
153pub struct CompiledExpression {
154    parts: Vec<CompiledExpressionPart>,
155    need_deref: bool,
156}
157
158impl CompiledExpression {
159    pub fn vmctx() -> CompiledExpression {
160        CompiledExpression::from_label(get_vmctx_value_label())
161    }
162
163    pub fn from_label(label: ValueLabel) -> CompiledExpression {
164        CompiledExpression {
165            parts: vec![CompiledExpressionPart::Local {
166                label,
167                trailing: true,
168            }],
169            need_deref: false,
170        }
171    }
172}
173
174fn translate_loc(
175    loc: LabelValueLoc,
176    isa: &dyn TargetIsa,
177    add_stack_value: bool,
178) -> Result<Option<Vec<u8>>> {
179    Ok(match loc {
180        LabelValueLoc::Reg(r) => {
181            let machine_reg = isa.map_regalloc_reg_to_dwarf(r)?;
182            let mut writer = ExpressionWriter::new();
183            if add_stack_value {
184                writer.write_op_reg(machine_reg)?;
185            } else {
186                writer.write_op_breg(machine_reg)?;
187                writer.write_sleb128(0)?;
188            }
189            Some(writer.into_vec())
190        }
191        LabelValueLoc::CFAOffset(off) => {
192            let mut writer = ExpressionWriter::new();
193            writer.write_op(gimli::constants::DW_OP_fbreg)?;
194            writer.write_sleb128(off)?;
195            if !add_stack_value {
196                writer.write_op(gimli::constants::DW_OP_deref)?;
197            }
198            return Ok(Some(writer.into_vec()));
199        }
200    })
201}
202
203fn append_memory_deref(
204    buf: &mut Vec<u8>,
205    frame_info: &FunctionFrameInfo,
206    vmctx_loc: LabelValueLoc,
207    isa: &dyn TargetIsa,
208) -> Result<bool> {
209    let mut writer = ExpressionWriter::new();
210    let vmctx_base = match vmctx_loc {
211        LabelValueLoc::Reg(r) => VmctxBase::Reg(isa.map_regalloc_reg_to_dwarf(r)?),
212        LabelValueLoc::CFAOffset(off) => {
213            writer.write_op(gimli::constants::DW_OP_fbreg)?;
214            writer.write_sleb128(off)?;
215            writer.write_op(gimli::constants::DW_OP_deref)?;
216            VmctxBase::OnStack
217        }
218    };
219    writer.gen_address_of_memory_base_pointer(vmctx_base, &frame_info.memory_offset)?;
220    writer.write_op(gimli::constants::DW_OP_deref)?;
221    writer.write_op(gimli::constants::DW_OP_swap)?;
222    writer.write_op(gimli::constants::DW_OP_const4u)?;
223    writer.write_u32(0xffff_ffff)?;
224    writer.write_op(gimli::constants::DW_OP_and)?;
225    writer.write_op(gimli::constants::DW_OP_plus)?;
226    buf.extend(writer.into_vec());
227    Ok(true)
228}
229
230impl CompiledExpression {
231    pub fn is_simple(&self) -> bool {
232        if let [CompiledExpressionPart::Code(_)] = self.parts.as_slice() {
233            true
234        } else {
235            self.parts.is_empty()
236        }
237    }
238
239    pub fn build(&self) -> Option<write::Expression> {
240        if let [CompiledExpressionPart::Code(code)] = self.parts.as_slice() {
241            return Some(write::Expression::raw(code.to_vec()));
242        }
243        // locals found, not supported
244        None
245    }
246
247    pub fn build_with_locals<'a>(
248        &'a self,
249        scope: &'a [(u64, u64)], // wasm ranges
250        addr_tr: &'a AddressTransform,
251        frame_info: Option<&'a FunctionFrameInfo>,
252        isa: &'a dyn TargetIsa,
253    ) -> impl Iterator<Item = Result<(write::Address, u64, write::Expression)>> + use<'a> {
254        enum BuildWithLocalsResult<'a> {
255            Empty,
256            Simple(
257                Box<dyn Iterator<Item = (write::Address, u64)> + 'a>,
258                Vec<u8>,
259            ),
260            Ranges(Box<dyn Iterator<Item = Result<(usize, usize, usize, Vec<u8>)>> + 'a>),
261        }
262        impl Iterator for BuildWithLocalsResult<'_> {
263            type Item = Result<(write::Address, u64, write::Expression)>;
264            fn next(&mut self) -> Option<Self::Item> {
265                match self {
266                    BuildWithLocalsResult::Empty => None,
267                    BuildWithLocalsResult::Simple(it, code) => it
268                        .next()
269                        .map(|(addr, len)| Ok((addr, len, write::Expression::raw(code.to_vec())))),
270                    BuildWithLocalsResult::Ranges(it) => it.next().map(|r| {
271                        r.map(|(symbol, start, end, code_buf)| {
272                            (
273                                write::Address::Symbol {
274                                    symbol,
275                                    addend: start as i64,
276                                },
277                                (end - start) as u64,
278                                write::Expression::raw(code_buf),
279                            )
280                        })
281                    }),
282                }
283            }
284        }
285
286        if scope.is_empty() {
287            return BuildWithLocalsResult::Empty;
288        }
289
290        // If it a simple DWARF code, no need in locals processing. Just translate
291        // the scope ranges.
292        if let [CompiledExpressionPart::Code(code)] = self.parts.as_slice() {
293            return BuildWithLocalsResult::Simple(
294                Box::new(scope.iter().flat_map(move |(wasm_start, wasm_end)| {
295                    addr_tr.translate_ranges(*wasm_start, *wasm_end)
296                })),
297                code.clone(),
298            );
299        }
300
301        let vmctx_label = get_vmctx_value_label();
302
303        // Some locals are present, preparing and divided ranges based on the scope
304        // and frame_info data.
305        let mut ranges_builder = ValueLabelRangesBuilder::new(scope, addr_tr, frame_info, isa);
306        for p in self.parts.iter() {
307            match p {
308                CompiledExpressionPart::Code(_)
309                | CompiledExpressionPart::Jump { .. }
310                | CompiledExpressionPart::LandingPad { .. } => (),
311                CompiledExpressionPart::Local { label, .. } => ranges_builder.process_label(*label),
312                CompiledExpressionPart::Deref => ranges_builder.process_label(vmctx_label),
313            }
314        }
315        if self.need_deref {
316            ranges_builder.process_label(vmctx_label);
317        }
318        let ranges = ranges_builder.into_ranges();
319
320        return BuildWithLocalsResult::Ranges(Box::new(
321            ranges
322                .into_iter()
323                .map(
324                    move |CachedValueLabelRange {
325                              func_index,
326                              start,
327                              end,
328                              label_location,
329                          }| {
330                        // build expression
331                        let mut code_buf = Vec::new();
332                        let mut jump_positions = Vec::new();
333                        let mut landing_positions = HashMap::new();
334
335                        macro_rules! deref {
336                            () => {
337                                if let (Some(vmctx_loc), Some(frame_info)) =
338                                    (label_location.get(&vmctx_label), frame_info)
339                                {
340                                    if !append_memory_deref(
341                                        &mut code_buf,
342                                        frame_info,
343                                        *vmctx_loc,
344                                        isa,
345                                    )? {
346                                        return Ok(None);
347                                    }
348                                } else {
349                                    return Ok(None);
350                                }
351                            };
352                        }
353                        for part in &self.parts {
354                            match part {
355                                CompiledExpressionPart::Code(c) => {
356                                    code_buf.extend_from_slice(c.as_slice())
357                                }
358                                CompiledExpressionPart::LandingPad(marker) => {
359                                    landing_positions.insert(marker.clone(), code_buf.len());
360                                }
361                                CompiledExpressionPart::Jump {
362                                    conditionally,
363                                    target,
364                                } => {
365                                    code_buf.push(
366                                        match conditionally {
367                                            true => gimli::constants::DW_OP_bra,
368                                            false => gimli::constants::DW_OP_skip,
369                                        }
370                                        .0,
371                                    );
372                                    code_buf.push(!0);
373                                    code_buf.push(!0); // these will be relocated below
374                                    jump_positions.push((target.clone(), code_buf.len()));
375                                }
376                                CompiledExpressionPart::Local { label, trailing } => {
377                                    let loc =
378                                        *label_location.get(&label).context("label_location")?;
379                                    if let Some(expr) = translate_loc(loc, isa, *trailing)? {
380                                        code_buf.extend_from_slice(&expr)
381                                    } else {
382                                        return Ok(None);
383                                    }
384                                }
385                                CompiledExpressionPart::Deref => deref!(),
386                            }
387                        }
388                        if self.need_deref {
389                            deref!();
390                        }
391
392                        for (marker, new_from) in jump_positions {
393                            // relocate jump targets
394                            let new_to = landing_positions[&marker];
395                            let new_diff = new_to as isize - new_from as isize;
396                            // FIXME: use encoding? LittleEndian for now...
397                            code_buf[new_from - 2..new_from]
398                                .copy_from_slice(&(new_diff as i16).to_le_bytes());
399                        }
400                        Ok(Some((func_index, start, end, code_buf)))
401                    },
402                )
403                .filter_map(Result::transpose),
404        ));
405    }
406}
407
408fn is_old_expression_format(buf: &[u8]) -> bool {
409    // Heuristic to detect old variable expression format without DW_OP_fbreg:
410    // DW_OP_plus_uconst op must be present, but not DW_OP_fbreg.
411    if buf.contains(&(gimli::constants::DW_OP_fbreg.0)) {
412        // Stop check if DW_OP_fbreg exist.
413        return false;
414    }
415    buf.contains(&(gimli::constants::DW_OP_plus_uconst.0))
416}
417
418pub fn compile_expression<R>(
419    expr: &Expression<R>,
420    encoding: gimli::Encoding,
421    frame_base: Option<&CompiledExpression>,
422) -> Result<Option<CompiledExpression>, Error>
423where
424    R: Reader,
425{
426    // Bail when `frame_base` is complicated.
427    if let Some(expr) = frame_base {
428        if expr.parts.iter().any(|p| match p {
429            CompiledExpressionPart::Jump { .. } => true,
430            _ => false,
431        }) {
432            return Ok(None);
433        }
434    }
435
436    // jump_targets key is offset in buf starting from the end
437    // (see also `unread_bytes` below)
438    let mut jump_targets: HashMap<u64, JumpTargetMarker> = HashMap::new();
439    let mut pc = expr.0.clone();
440
441    let buf = expr.0.to_slice()?;
442    let mut parts = Vec::new();
443    macro_rules! push {
444        ($part:expr) => {{
445            let part = $part;
446            if let (CompiledExpressionPart::Code(cc2), Some(CompiledExpressionPart::Code(cc1))) =
447                (&part, parts.last_mut())
448            {
449                cc1.extend_from_slice(cc2);
450            } else {
451                parts.push(part)
452            }
453        }};
454    }
455    let mut need_deref = false;
456    if is_old_expression_format(&buf) && frame_base.is_some() {
457        // Still supporting old DWARF variable expressions without fbreg.
458        parts.extend_from_slice(&frame_base.unwrap().parts);
459        if let Some(CompiledExpressionPart::Local { trailing, .. }) = parts.last_mut() {
460            *trailing = false;
461        }
462        need_deref = frame_base.unwrap().need_deref;
463    }
464    let mut code_chunk = Vec::new();
465    macro_rules! flush_code_chunk {
466        () => {
467            if !code_chunk.is_empty() {
468                push!(CompiledExpressionPart::Code(code_chunk));
469                code_chunk = Vec::new();
470                let _ = code_chunk; // suppresses warning for final flush
471            }
472        };
473    }
474
475    // Find all landing pads by scanning bytes, do not care about
476    // false location at this moment.
477    // Looks hacky but it is fast; does not need to be really exact.
478    if buf.len() > 2 {
479        for i in 0..buf.len() - 2 {
480            let op = buf[i];
481            if op == gimli::constants::DW_OP_bra.0 || op == gimli::constants::DW_OP_skip.0 {
482                // TODO fix for big-endian
483                let offset = i16::from_le_bytes([buf[i + 1], buf[i + 2]]);
484                let origin = i + 3;
485                // Discarding out-of-bounds jumps (also some of falsely detected ops)
486                if (offset >= 0 && offset as usize + origin <= buf.len())
487                    || (offset < 0 && -offset as usize <= origin)
488                {
489                    let target = buf.len() as isize - origin as isize - offset as isize;
490                    jump_targets.insert(target as u64, JumpTargetMarker::new());
491                }
492            }
493        }
494    }
495
496    while !pc.is_empty() {
497        let unread_bytes = pc.len().into_u64();
498        if let Some(marker) = jump_targets.get(&unread_bytes) {
499            flush_code_chunk!();
500            parts.push(CompiledExpressionPart::LandingPad(marker.clone()));
501        }
502
503        need_deref = true;
504
505        let pos = pc.offset_from(&expr.0).into_u64() as usize;
506        let op = Operation::parse(&mut pc, encoding)?;
507        match op {
508            Operation::FrameOffset { offset } => {
509                // Expand DW_OP_fbreg into frame location and DW_OP_plus_uconst.
510                if frame_base.is_some() {
511                    // Add frame base expressions.
512                    flush_code_chunk!();
513                    parts.extend_from_slice(&frame_base.unwrap().parts);
514                }
515                if let Some(CompiledExpressionPart::Local { trailing, .. }) = parts.last_mut() {
516                    // Reset local trailing flag.
517                    *trailing = false;
518                }
519                // Append DW_OP_plus_uconst part.
520                let mut writer = ExpressionWriter::new();
521                writer.write_op(gimli::constants::DW_OP_plus_uconst)?;
522                writer.write_uleb128(offset as u64)?;
523                code_chunk.extend(writer.into_vec());
524                continue;
525            }
526            Operation::Drop { .. }
527            | Operation::Pick { .. }
528            | Operation::Swap { .. }
529            | Operation::Rot { .. }
530            | Operation::Nop { .. }
531            | Operation::UnsignedConstant { .. }
532            | Operation::SignedConstant { .. }
533            | Operation::ConstantIndex { .. }
534            | Operation::PlusConstant { .. }
535            | Operation::Abs { .. }
536            | Operation::And { .. }
537            | Operation::Or { .. }
538            | Operation::Xor { .. }
539            | Operation::Shl { .. }
540            | Operation::Plus { .. }
541            | Operation::Minus { .. }
542            | Operation::Div { .. }
543            | Operation::Mod { .. }
544            | Operation::Mul { .. }
545            | Operation::Neg { .. }
546            | Operation::Not { .. }
547            | Operation::Lt { .. }
548            | Operation::Gt { .. }
549            | Operation::Le { .. }
550            | Operation::Ge { .. }
551            | Operation::Eq { .. }
552            | Operation::Ne { .. }
553            | Operation::TypedLiteral { .. }
554            | Operation::Convert { .. }
555            | Operation::Reinterpret { .. }
556            | Operation::Piece { .. } => (),
557            Operation::Bra { target } | Operation::Skip { target } => {
558                flush_code_chunk!();
559                let arc_to = (pc.len().into_u64() as isize - target as isize) as u64;
560                let marker = match jump_targets.get(&arc_to) {
561                    Some(m) => m.clone(),
562                    None => {
563                        // Marker not found: probably out of bounds.
564                        return Ok(None);
565                    }
566                };
567                push!(CompiledExpressionPart::Jump {
568                    conditionally: match op {
569                        Operation::Bra { .. } => true,
570                        _ => false,
571                    },
572                    target: marker,
573                });
574                continue;
575            }
576            Operation::StackValue => {
577                need_deref = false;
578
579                // Find extra stack_value, that follow wasm-local operators,
580                // and mark such locals with special flag.
581                if let (Some(CompiledExpressionPart::Local { trailing, .. }), true) =
582                    (parts.last_mut(), code_chunk.is_empty())
583                {
584                    *trailing = true;
585                    continue;
586                }
587            }
588            Operation::Deref { .. } => {
589                flush_code_chunk!();
590                push!(CompiledExpressionPart::Deref);
591                // Don't re-enter the loop here (i.e. continue), because the
592                // DW_OP_deref still needs to be kept.
593            }
594            Operation::WasmLocal { index } => {
595                flush_code_chunk!();
596                let label = ValueLabel::from_u32(index);
597                push!(CompiledExpressionPart::Local {
598                    label,
599                    trailing: false,
600                });
601                continue;
602            }
603            Operation::Shr { .. } | Operation::Shra { .. } => {
604                // Insert value normalisation part.
605                // The semantic value is 32 bits (TODO: check unit)
606                // but the target architecture is 64-bits. So we'll
607                // clean out the upper 32 bits (in a sign-correct way)
608                // to avoid contamination of the result with randomness.
609                let mut writer = ExpressionWriter::new();
610                writer.write_op(gimli::constants::DW_OP_plus_uconst)?;
611                writer.write_uleb128(32)?; // increase shift amount
612                writer.write_op(gimli::constants::DW_OP_swap)?;
613                writer.write_op(gimli::constants::DW_OP_const1u)?;
614                writer.write_u8(32)?;
615                writer.write_op(gimli::constants::DW_OP_shl)?;
616                writer.write_op(gimli::constants::DW_OP_swap)?;
617                code_chunk.extend(writer.into_vec());
618                // Don't re-enter the loop here (i.e. continue), because the
619                // DW_OP_shr* still needs to be kept.
620            }
621            Operation::Address { .. }
622            | Operation::AddressIndex { .. }
623            | Operation::Call { .. }
624            | Operation::Register { .. }
625            | Operation::RegisterOffset { .. }
626            | Operation::CallFrameCFA
627            | Operation::PushObjectAddress
628            | Operation::TLS
629            | Operation::ImplicitValue { .. }
630            | Operation::ImplicitPointer { .. }
631            | Operation::EntryValue { .. }
632            | Operation::ParameterRef { .. } => {
633                return Ok(None);
634            }
635            Operation::WasmGlobal { index: _ } | Operation::WasmStack { index: _ } => {
636                // TODO support those two
637                return Ok(None);
638            }
639        }
640        let chunk = &buf[pos..pc.offset_from(&expr.0).into_u64() as usize];
641        code_chunk.extend_from_slice(chunk);
642    }
643
644    flush_code_chunk!();
645    if let Some(marker) = jump_targets.get(&0) {
646        parts.push(CompiledExpressionPart::LandingPad(marker.clone()));
647    }
648
649    Ok(Some(CompiledExpression { parts, need_deref }))
650}
651
652#[derive(Debug, Clone)]
653struct CachedValueLabelRange {
654    func_index: usize,
655    start: usize,
656    end: usize,
657    label_location: HashMap<ValueLabel, LabelValueLoc>,
658}
659
660struct BuiltRangeSummary<'a> {
661    range: &'a CachedValueLabelRange,
662    isa: &'a dyn TargetIsa,
663}
664
665impl<'a> fmt::Debug for BuiltRangeSummary<'a> {
666    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
667        let range = self.range;
668        write!(f, "[")?;
669        let mut is_first = true;
670        for (value, value_loc) in &range.label_location {
671            if !is_first {
672                write!(f, ", ")?;
673            } else {
674                is_first = false;
675            }
676            write!(
677                f,
678                "{:?}:{:?}",
679                log_get_value_name(*value),
680                log_get_value_loc(*value_loc, self.isa)
681            )?;
682        }
683        write!(f, "]@[{}..{})", range.start, range.end)?;
684        Ok(())
685    }
686}
687
688struct ValueLabelRangesBuilder<'a, 'b> {
689    isa: &'a dyn TargetIsa,
690    ranges: Vec<CachedValueLabelRange>,
691    frame_info: Option<&'a FunctionFrameInfo<'b>>,
692    processed_labels: HashSet<ValueLabel>,
693}
694
695impl<'a, 'b> ValueLabelRangesBuilder<'a, 'b> {
696    pub fn new(
697        scope: &[(u64, u64)], // wasm ranges
698        addr_tr: &'a AddressTransform,
699        frame_info: Option<&'a FunctionFrameInfo<'b>>,
700        isa: &'a dyn TargetIsa,
701    ) -> Self {
702        let mut ranges = Vec::new();
703        for (wasm_start, wasm_end) in scope {
704            if let Some((func_index, tr)) = addr_tr.translate_ranges_raw(*wasm_start, *wasm_end) {
705                ranges.extend(tr.into_iter().map(|(start, end)| CachedValueLabelRange {
706                    func_index,
707                    start,
708                    end,
709                    label_location: HashMap::new(),
710                }));
711            }
712        }
713        ranges.sort_unstable_by(|a, b| a.start.cmp(&b.start));
714
715        dbi_log!(
716            "Building ranges for values in scope: {}\n{:?}",
717            ranges
718                .iter()
719                .map(|r| format!("[{}..{})", r.start, r.end))
720                .join(" "),
721            log_get_value_ranges(frame_info.map(|f| f.value_ranges), isa)
722        );
723        ValueLabelRangesBuilder {
724            isa,
725            ranges,
726            frame_info,
727            processed_labels: HashSet::new(),
728        }
729    }
730
731    fn process_label(&mut self, label: ValueLabel) {
732        if self.processed_labels.contains(&label) {
733            return;
734        }
735        dbi_log!("Intersecting with {:?}", log_get_value_name(label));
736        self.processed_labels.insert(label);
737
738        let value_ranges = match self.frame_info.and_then(|fi| fi.value_ranges.get(&label)) {
739            Some(value_ranges) => value_ranges,
740            None => {
741                return;
742            }
743        };
744
745        let ranges = &mut self.ranges;
746        for value_range in value_ranges {
747            let range_start = value_range.start as usize;
748            let range_end = value_range.end as usize;
749            let loc = value_range.loc;
750            if range_start == range_end {
751                continue;
752            }
753            assert!(range_start < range_end);
754
755            // Find acceptable scope of ranges to intersect with.
756            let i = match ranges.binary_search_by(|s| s.start.cmp(&range_start)) {
757                Ok(i) => i,
758                Err(i) => {
759                    if i > 0 && range_start < ranges[i - 1].end {
760                        i - 1
761                    } else {
762                        i
763                    }
764                }
765            };
766            let j = match ranges.binary_search_by(|s| s.start.cmp(&range_end)) {
767                Ok(i) | Err(i) => i,
768            };
769            // Starting from the end, intersect (range_start..range_end) with
770            // self.ranges array.
771            for i in (i..j).rev() {
772                if range_end <= ranges[i].start || ranges[i].end <= range_start {
773                    continue;
774                }
775                if range_end < ranges[i].end {
776                    // Cutting some of the range from the end.
777                    let mut tail = ranges[i].clone();
778                    ranges[i].end = range_end;
779                    tail.start = range_end;
780                    ranges.insert(i + 1, tail);
781                }
782                assert!(ranges[i].end <= range_end);
783                if range_start <= ranges[i].start {
784                    ranges[i].label_location.insert(label, loc);
785                    continue;
786                }
787                // Cutting some of the range from the start.
788                let mut tail = ranges[i].clone();
789                ranges[i].end = range_start;
790                tail.start = range_start;
791                tail.label_location.insert(label, loc);
792                ranges.insert(i + 1, tail);
793            }
794        }
795    }
796
797    pub fn into_ranges(self) -> impl Iterator<Item = CachedValueLabelRange> + use<> {
798        // Ranges with not-enough labels are discarded.
799        let processed_labels_len = self.processed_labels.len();
800        let is_valid_range =
801            move |r: &CachedValueLabelRange| r.label_location.len() == processed_labels_len;
802
803        if dbi_log_enabled!() {
804            dbi_log!("Built ranges:");
805            for range in self.ranges.iter().filter(|r| is_valid_range(*r)) {
806                dbi_log!(
807                    "{:?}",
808                    BuiltRangeSummary {
809                        range,
810                        isa: self.isa
811                    }
812                );
813            }
814            dbi_log!("");
815        }
816        self.ranges.into_iter().filter(is_valid_range)
817    }
818}
819
820/// Marker for tracking incoming jumps.
821/// Different when created new, and the same when cloned.
822#[derive(Clone, Eq)]
823struct JumpTargetMarker(Rc<u32>);
824
825impl JumpTargetMarker {
826    fn new() -> JumpTargetMarker {
827        // Create somewhat unique hash data -- using part of
828        // the pointer of the RcBox.
829        let mut rc = Rc::new(0);
830        let hash_data = rc.as_ref() as *const u32 as usize as u32;
831        *Rc::get_mut(&mut rc).unwrap() = hash_data;
832        JumpTargetMarker(rc)
833    }
834}
835
836impl PartialEq for JumpTargetMarker {
837    fn eq(&self, other: &JumpTargetMarker) -> bool {
838        Rc::ptr_eq(&self.0, &other.0)
839    }
840}
841
842impl Hash for JumpTargetMarker {
843    fn hash<H: Hasher>(&self, hasher: &mut H) {
844        hasher.write_u32(*self.0);
845    }
846}
847impl std::fmt::Debug for JumpTargetMarker {
848    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::result::Result<(), std::fmt::Error> {
849        write!(
850            f,
851            "JumpMarker<{:08x}>",
852            self.0.as_ref() as *const u32 as usize
853        )
854    }
855}
856
857#[cfg(test)]
858#[expect(trivial_numeric_casts, reason = "macro-generated code")]
859mod tests {
860    use super::{
861        compile_expression, AddressTransform, CompiledExpression, CompiledExpressionPart,
862        FunctionFrameInfo, JumpTargetMarker, ValueLabel, ValueLabelsRanges,
863    };
864    use crate::CompiledFunctionMetadata;
865    use cranelift_codegen::{isa::lookup, settings::Flags};
866    use gimli::{constants, Encoding, EndianSlice, Expression, RunTimeEndian};
867    use target_lexicon::triple;
868    use wasmtime_environ::FilePos;
869
870    macro_rules! dw_op {
871        (DW_OP_WASM_location) => {
872            0xed
873        };
874        ($i:literal) => {
875            $i
876        };
877        ($d:ident) => {
878            constants::$d.0 as u8
879        };
880        ($e:expr) => {
881            $e as u8
882        };
883    }
884
885    macro_rules! expression {
886        ($($t:tt),*) => {
887            Expression(EndianSlice::new(
888                &[$(dw_op!($t)),*],
889                RunTimeEndian::Little,
890            ))
891        }
892    }
893
894    fn find_jump_targets<'a>(ce: &'a CompiledExpression) -> Vec<&'a JumpTargetMarker> {
895        ce.parts
896            .iter()
897            .filter_map(|p| {
898                if let CompiledExpressionPart::LandingPad(t) = p {
899                    Some(t)
900                } else {
901                    None
902                }
903            })
904            .collect::<Vec<_>>()
905    }
906
907    static DWARF_ENCODING: Encoding = Encoding {
908        address_size: 4,
909        format: gimli::Format::Dwarf32,
910        version: 4,
911    };
912
913    #[test]
914    fn test_debug_expression_jump_target() {
915        let m1 = JumpTargetMarker::new();
916        let m2 = JumpTargetMarker::new();
917        assert!(m1 != m2);
918        assert!(m1 == m1.clone());
919
920        // Internal hash_data test (theoretically can fail intermittently).
921        assert!(m1.0 != m2.0);
922    }
923
924    #[test]
925    fn test_debug_parse_expressions() {
926        use cranelift_entity::EntityRef;
927
928        let (val1, val3, val20) = (ValueLabel::new(1), ValueLabel::new(3), ValueLabel::new(20));
929
930        let e = expression!(DW_OP_WASM_location, 0x0, 20, DW_OP_stack_value);
931        let ce = compile_expression(&e, DWARF_ENCODING, None)
932            .expect("non-error")
933            .expect("expression");
934        assert_eq!(
935            ce,
936            CompiledExpression {
937                parts: vec![CompiledExpressionPart::Local {
938                    label: val20,
939                    trailing: true
940                }],
941                need_deref: false,
942            }
943        );
944
945        let e = expression!(
946            DW_OP_WASM_location,
947            0x0,
948            1,
949            DW_OP_plus_uconst,
950            0x10,
951            DW_OP_stack_value
952        );
953        let ce = compile_expression(&e, DWARF_ENCODING, None)
954            .expect("non-error")
955            .expect("expression");
956        assert_eq!(
957            ce,
958            CompiledExpression {
959                parts: vec![
960                    CompiledExpressionPart::Local {
961                        label: val1,
962                        trailing: false
963                    },
964                    CompiledExpressionPart::Code(vec![35, 16, 159])
965                ],
966                need_deref: false,
967            }
968        );
969
970        let e = expression!(DW_OP_WASM_location, 0x0, 3, DW_OP_stack_value);
971        let fe = compile_expression(&e, DWARF_ENCODING, None).expect("non-error");
972        let e = expression!(DW_OP_fbreg, 0x12);
973        let ce = compile_expression(&e, DWARF_ENCODING, fe.as_ref())
974            .expect("non-error")
975            .expect("expression");
976        assert_eq!(
977            ce,
978            CompiledExpression {
979                parts: vec![
980                    CompiledExpressionPart::Local {
981                        label: val3,
982                        trailing: false
983                    },
984                    CompiledExpressionPart::Code(vec![35, 18])
985                ],
986                need_deref: true,
987            }
988        );
989
990        let e = expression!(
991            DW_OP_WASM_location,
992            0x0,
993            1,
994            DW_OP_plus_uconst,
995            5,
996            DW_OP_deref,
997            DW_OP_stack_value
998        );
999        let ce = compile_expression(&e, DWARF_ENCODING, None)
1000            .expect("non-error")
1001            .expect("expression");
1002        assert_eq!(
1003            ce,
1004            CompiledExpression {
1005                parts: vec![
1006                    CompiledExpressionPart::Local {
1007                        label: val1,
1008                        trailing: false
1009                    },
1010                    CompiledExpressionPart::Code(vec![35, 5]),
1011                    CompiledExpressionPart::Deref,
1012                    CompiledExpressionPart::Code(vec![6, 159])
1013                ],
1014                need_deref: false,
1015            }
1016        );
1017
1018        let e = expression!(
1019            DW_OP_WASM_location,
1020            0x0,
1021            1,
1022            DW_OP_lit16,
1023            DW_OP_shra,
1024            DW_OP_stack_value
1025        );
1026        let ce = compile_expression(&e, DWARF_ENCODING, None)
1027            .expect("non-error")
1028            .expect("expression");
1029        assert_eq!(
1030            ce,
1031            CompiledExpression {
1032                parts: vec![
1033                    CompiledExpressionPart::Local {
1034                        label: val1,
1035                        trailing: false
1036                    },
1037                    CompiledExpressionPart::Code(vec![64, 35, 32, 22, 8, 32, 36, 22, 38, 159])
1038                ],
1039                need_deref: false,
1040            }
1041        );
1042
1043        let e = expression!(
1044            DW_OP_lit1,
1045            DW_OP_dup,
1046            DW_OP_WASM_location,
1047            0x0,
1048            1,
1049            DW_OP_and,
1050            DW_OP_bra,
1051            5,
1052            0, // --> pointer
1053            DW_OP_swap,
1054            DW_OP_shr,
1055            DW_OP_skip,
1056            2,
1057            0, // --> done
1058            // pointer:
1059            DW_OP_plus,
1060            DW_OP_deref,
1061            // done:
1062            DW_OP_stack_value
1063        );
1064        let ce = compile_expression(&e, DWARF_ENCODING, None)
1065            .expect("non-error")
1066            .expect("expression");
1067        let targets = find_jump_targets(&ce);
1068        assert_eq!(targets.len(), 2);
1069        assert_eq!(
1070            ce,
1071            CompiledExpression {
1072                parts: vec![
1073                    CompiledExpressionPart::Code(vec![49, 18]),
1074                    CompiledExpressionPart::Local {
1075                        label: val1,
1076                        trailing: false
1077                    },
1078                    CompiledExpressionPart::Code(vec![26]),
1079                    CompiledExpressionPart::Jump {
1080                        conditionally: true,
1081                        target: targets[0].clone(),
1082                    },
1083                    CompiledExpressionPart::Code(vec![22, 35, 32, 22, 8, 32, 36, 22, 37]),
1084                    CompiledExpressionPart::Jump {
1085                        conditionally: false,
1086                        target: targets[1].clone(),
1087                    },
1088                    CompiledExpressionPart::LandingPad(targets[0].clone()), // capture from
1089                    CompiledExpressionPart::Code(vec![34]),
1090                    CompiledExpressionPart::Deref,
1091                    CompiledExpressionPart::Code(vec![6]),
1092                    CompiledExpressionPart::LandingPad(targets[1].clone()), // capture to
1093                    CompiledExpressionPart::Code(vec![159])
1094                ],
1095                need_deref: false,
1096            }
1097        );
1098
1099        let e = expression!(
1100            DW_OP_lit1,
1101            DW_OP_dup,
1102            DW_OP_bra,
1103            2,
1104            0, // --> target
1105            DW_OP_deref,
1106            DW_OP_lit0,
1107            // target:
1108            DW_OP_stack_value
1109        );
1110        let ce = compile_expression(&e, DWARF_ENCODING, None)
1111            .expect("non-error")
1112            .expect("expression");
1113        let targets = find_jump_targets(&ce);
1114        assert_eq!(targets.len(), 1);
1115        assert_eq!(
1116            ce,
1117            CompiledExpression {
1118                parts: vec![
1119                    CompiledExpressionPart::Code(vec![49, 18]),
1120                    CompiledExpressionPart::Jump {
1121                        conditionally: true,
1122                        target: targets[0].clone(),
1123                    },
1124                    CompiledExpressionPart::Deref,
1125                    CompiledExpressionPart::Code(vec![6, 48]),
1126                    CompiledExpressionPart::LandingPad(targets[0].clone()), // capture to
1127                    CompiledExpressionPart::Code(vec![159])
1128                ],
1129                need_deref: false,
1130            }
1131        );
1132
1133        let e = expression!(
1134            DW_OP_lit1,
1135            /* loop */ DW_OP_dup,
1136            DW_OP_lit25,
1137            DW_OP_ge,
1138            DW_OP_bra,
1139            5,
1140            0, // --> done
1141            DW_OP_plus_uconst,
1142            1,
1143            DW_OP_skip,
1144            (-11_i8),
1145            (!0), // --> loop
1146            /* done */ DW_OP_stack_value
1147        );
1148        let ce = compile_expression(&e, DWARF_ENCODING, None)
1149            .expect("non-error")
1150            .expect("expression");
1151        let targets = find_jump_targets(&ce);
1152        assert_eq!(targets.len(), 2);
1153        assert_eq!(
1154            ce,
1155            CompiledExpression {
1156                parts: vec![
1157                    CompiledExpressionPart::Code(vec![49]),
1158                    CompiledExpressionPart::LandingPad(targets[0].clone()),
1159                    CompiledExpressionPart::Code(vec![18, 73, 42]),
1160                    CompiledExpressionPart::Jump {
1161                        conditionally: true,
1162                        target: targets[1].clone(),
1163                    },
1164                    CompiledExpressionPart::Code(vec![35, 1]),
1165                    CompiledExpressionPart::Jump {
1166                        conditionally: false,
1167                        target: targets[0].clone(),
1168                    },
1169                    CompiledExpressionPart::LandingPad(targets[1].clone()),
1170                    CompiledExpressionPart::Code(vec![159])
1171                ],
1172                need_deref: false,
1173            }
1174        );
1175
1176        let e = expression!(DW_OP_WASM_location, 0x0, 1, DW_OP_plus_uconst, 5);
1177        let ce = compile_expression(&e, DWARF_ENCODING, None)
1178            .expect("non-error")
1179            .expect("expression");
1180        assert_eq!(
1181            ce,
1182            CompiledExpression {
1183                parts: vec![
1184                    CompiledExpressionPart::Local {
1185                        label: val1,
1186                        trailing: false
1187                    },
1188                    CompiledExpressionPart::Code(vec![35, 5])
1189                ],
1190                need_deref: true,
1191            }
1192        );
1193    }
1194
1195    fn create_mock_address_transform() -> AddressTransform {
1196        use crate::FunctionAddressMap;
1197        use cranelift_entity::PrimaryMap;
1198        use wasmtime_environ::InstructionAddressMap;
1199        use wasmtime_environ::WasmFileInfo;
1200
1201        let mut module_map = PrimaryMap::new();
1202        let code_section_offset: u32 = 100;
1203        let func = CompiledFunctionMetadata {
1204            address_map: FunctionAddressMap {
1205                instructions: vec![
1206                    InstructionAddressMap {
1207                        srcloc: FilePos::new(code_section_offset + 12),
1208                        code_offset: 5,
1209                    },
1210                    InstructionAddressMap {
1211                        srcloc: FilePos::default(),
1212                        code_offset: 8,
1213                    },
1214                    InstructionAddressMap {
1215                        srcloc: FilePos::new(code_section_offset + 17),
1216                        code_offset: 15,
1217                    },
1218                    InstructionAddressMap {
1219                        srcloc: FilePos::default(),
1220                        code_offset: 23,
1221                    },
1222                ]
1223                .into(),
1224                start_srcloc: FilePos::new(code_section_offset + 10),
1225                end_srcloc: FilePos::new(code_section_offset + 20),
1226                body_offset: 0,
1227                body_len: 30,
1228            },
1229            ..Default::default()
1230        };
1231        module_map.push(&func);
1232        let fi = WasmFileInfo {
1233            code_section_offset: code_section_offset.into(),
1234            funcs: Vec::new(),
1235            imported_func_count: 0,
1236            path: None,
1237        };
1238        AddressTransform::mock(&module_map, fi)
1239    }
1240
1241    fn create_mock_value_ranges() -> (ValueLabelsRanges, (ValueLabel, ValueLabel, ValueLabel)) {
1242        use cranelift_codegen::{LabelValueLoc, ValueLocRange};
1243        use cranelift_entity::EntityRef;
1244        use std::collections::HashMap;
1245        let mut value_ranges = HashMap::new();
1246        let value_0 = ValueLabel::new(0);
1247        let value_1 = ValueLabel::new(1);
1248        let value_2 = ValueLabel::new(2);
1249        value_ranges.insert(
1250            value_0,
1251            vec![ValueLocRange {
1252                loc: LabelValueLoc::CFAOffset(0),
1253                start: 0,
1254                end: 25,
1255            }],
1256        );
1257        value_ranges.insert(
1258            value_1,
1259            vec![ValueLocRange {
1260                loc: LabelValueLoc::CFAOffset(0),
1261                start: 5,
1262                end: 30,
1263            }],
1264        );
1265        value_ranges.insert(
1266            value_2,
1267            vec![
1268                ValueLocRange {
1269                    loc: LabelValueLoc::CFAOffset(0),
1270                    start: 0,
1271                    end: 10,
1272                },
1273                ValueLocRange {
1274                    loc: LabelValueLoc::CFAOffset(0),
1275                    start: 20,
1276                    end: 30,
1277                },
1278            ],
1279        );
1280        (value_ranges, (value_0, value_1, value_2))
1281    }
1282
1283    #[test]
1284    fn test_debug_value_range_builder() {
1285        use super::ValueLabelRangesBuilder;
1286        use crate::debug::ModuleMemoryOffset;
1287
1288        // Ignore this test if cranelift doesn't support the native platform.
1289        if cranelift_native::builder().is_err() {
1290            return;
1291        }
1292
1293        let isa = lookup(triple!("x86_64"))
1294            .expect("expect x86_64 ISA")
1295            .finish(Flags::new(cranelift_codegen::settings::builder()))
1296            .expect("Creating ISA");
1297
1298        let addr_tr = create_mock_address_transform();
1299        let (value_ranges, value_labels) = create_mock_value_ranges();
1300        let fi = FunctionFrameInfo {
1301            memory_offset: ModuleMemoryOffset::None,
1302            value_ranges: &value_ranges,
1303        };
1304
1305        // No value labels, testing if entire function range coming through.
1306        let builder = ValueLabelRangesBuilder::new(&[(10, 20)], &addr_tr, Some(&fi), isa.as_ref());
1307        let ranges = builder.into_ranges().collect::<Vec<_>>();
1308        assert_eq!(ranges.len(), 1);
1309        assert_eq!(ranges[0].func_index, 0);
1310        assert_eq!(ranges[0].start, 0);
1311        assert_eq!(ranges[0].end, 30);
1312
1313        // Two labels (val0@0..25 and val1@5..30), their common lifetime intersect at 5..25.
1314        let mut builder =
1315            ValueLabelRangesBuilder::new(&[(10, 20)], &addr_tr, Some(&fi), isa.as_ref());
1316        builder.process_label(value_labels.0);
1317        builder.process_label(value_labels.1);
1318        let ranges = builder.into_ranges().collect::<Vec<_>>();
1319        assert_eq!(ranges.len(), 1);
1320        assert_eq!(ranges[0].start, 5);
1321        assert_eq!(ranges[0].end, 25);
1322
1323        // Adds val2 with complex lifetime @0..10 and @20..30 to the previous test, and
1324        // also narrows range.
1325        let mut builder =
1326            ValueLabelRangesBuilder::new(&[(11, 17)], &addr_tr, Some(&fi), isa.as_ref());
1327        builder.process_label(value_labels.0);
1328        builder.process_label(value_labels.1);
1329        builder.process_label(value_labels.2);
1330        let ranges = builder.into_ranges().collect::<Vec<_>>();
1331        // Result is two ranges @5..10 and @20..23
1332        assert_eq!(ranges.len(), 2);
1333        assert_eq!(ranges[0].start, 5);
1334        assert_eq!(ranges[0].end, 10);
1335        assert_eq!(ranges[1].start, 20);
1336        assert_eq!(ranges[1].end, 23);
1337    }
1338}
wasmtime_cranelift/debug/transform/expression.rs

wasmtime_cranelift/debug/transform/
expression.rs
