wasmtime_cranelift/debug/transform/
expression.rs

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

wasmtime_cranelift/debug/transform/
expression.rs
