1 //! Legalization of heaps.
2 //!
3 //! This module exports the `expand_heap_addr` function which transforms a `heap_addr`
4 //! instruction into code that depends on the kind of heap referenced.
5
6 use crate::cursor::{Cursor, FuncCursor};
7 use crate::flowgraph::ControlFlowGraph;
8 use crate::ir::condcodes::IntCC;
9 use crate::ir::{self, InstBuilder};
10 use crate::isa::TargetIsa;
11
12 /// Expand a `heap_addr` instruction according to the definition of the heap.
expand_heap_addr( inst: ir::Inst, func: &mut ir::Function, cfg: &mut ControlFlowGraph, isa: &dyn TargetIsa, )13 pub fn expand_heap_addr(
14 inst: ir::Inst,
15 func: &mut ir::Function,
16 cfg: &mut ControlFlowGraph,
17 isa: &dyn TargetIsa,
18 ) {
19 // Unpack the instruction.
20 let (heap, offset, access_size) = match func.dfg[inst] {
21 ir::InstructionData::HeapAddr {
22 opcode,
23 heap,
24 arg,
25 imm,
26 } => {
27 debug_assert_eq!(opcode, ir::Opcode::HeapAddr);
28 (heap, arg, imm.into())
29 }
30 _ => panic!("Wanted heap_addr: {}", func.dfg.display_inst(inst, None)),
31 };
32
33 match func.heaps[heap].style {
34 ir::HeapStyle::Dynamic { bound_gv } => {
35 dynamic_addr(isa, inst, heap, offset, access_size, bound_gv, func)
36 }
37 ir::HeapStyle::Static { bound } => static_addr(
38 isa,
39 inst,
40 heap,
41 offset,
42 access_size,
43 bound.into(),
44 func,
45 cfg,
46 ),
47 }
48 }
49
50 /// Expand a `heap_addr` for a dynamic heap.
dynamic_addr( isa: &dyn TargetIsa, inst: ir::Inst, heap: ir::Heap, offset: ir::Value, access_size: u32, bound_gv: ir::GlobalValue, func: &mut ir::Function, )51 fn dynamic_addr(
52 isa: &dyn TargetIsa,
53 inst: ir::Inst,
54 heap: ir::Heap,
55 offset: ir::Value,
56 access_size: u32,
57 bound_gv: ir::GlobalValue,
58 func: &mut ir::Function,
59 ) {
60 let access_size = u64::from(access_size);
61 let offset_ty = func.dfg.value_type(offset);
62 let addr_ty = func.dfg.value_type(func.dfg.first_result(inst));
63 let min_size = func.heaps[heap].min_size.into();
64 let mut pos = FuncCursor::new(func).at_inst(inst);
65 pos.use_srcloc(inst);
66
67 // Start with the bounds check. Trap if `offset + access_size > bound`.
68 let bound = pos.ins().global_value(offset_ty, bound_gv);
69 let oob;
70 if access_size == 1 {
71 // `offset > bound - 1` is the same as `offset >= bound`.
72 oob = pos
73 .ins()
74 .icmp(IntCC::UnsignedGreaterThanOrEqual, offset, bound);
75 } else if access_size <= min_size {
76 // We know that bound >= min_size, so here we can compare `offset > bound - access_size`
77 // without wrapping.
78 let adj_bound = pos.ins().iadd_imm(bound, -(access_size as i64));
79 oob = pos
80 .ins()
81 .icmp(IntCC::UnsignedGreaterThan, offset, adj_bound);
82 } else {
83 // We need an overflow check for the adjusted offset.
84 let access_size_val = pos.ins().iconst(offset_ty, access_size as i64);
85 let (adj_offset, overflow) = pos.ins().iadd_ifcout(offset, access_size_val);
86 pos.ins().trapif(
87 isa.unsigned_add_overflow_condition(),
88 overflow,
89 ir::TrapCode::HeapOutOfBounds,
90 );
91 oob = pos
92 .ins()
93 .icmp(IntCC::UnsignedGreaterThan, adj_offset, bound);
94 }
95 pos.ins().trapnz(oob, ir::TrapCode::HeapOutOfBounds);
96
97 compute_addr(isa, inst, heap, addr_ty, offset, offset_ty, pos.func);
98 }
99
100 /// Expand a `heap_addr` for a static heap.
static_addr( isa: &dyn TargetIsa, inst: ir::Inst, heap: ir::Heap, offset: ir::Value, access_size: u32, bound: u64, func: &mut ir::Function, cfg: &mut ControlFlowGraph, )101 fn static_addr(
102 isa: &dyn TargetIsa,
103 inst: ir::Inst,
104 heap: ir::Heap,
105 offset: ir::Value,
106 access_size: u32,
107 bound: u64,
108 func: &mut ir::Function,
109 cfg: &mut ControlFlowGraph,
110 ) {
111 let access_size = u64::from(access_size);
112 let offset_ty = func.dfg.value_type(offset);
113 let addr_ty = func.dfg.value_type(func.dfg.first_result(inst));
114 let mut pos = FuncCursor::new(func).at_inst(inst);
115 pos.use_srcloc(inst);
116
117 // The goal here is to trap if `offset + access_size > bound`.
118 //
119 // This first case is a trivial case where we can easily trap.
120 if access_size > bound {
121 // This will simply always trap since `offset >= 0`.
122 pos.ins().trap(ir::TrapCode::HeapOutOfBounds);
123 pos.func.dfg.replace(inst).iconst(addr_ty, 0);
124
125 // Split Block, as the trap is a terminator instruction.
126 let curr_block = pos.current_block().expect("Cursor is not in a block");
127 let new_block = pos.func.dfg.make_block();
128 pos.insert_block(new_block);
129 cfg.recompute_block(pos.func, curr_block);
130 cfg.recompute_block(pos.func, new_block);
131 return;
132 }
133
134 // After the trivial case is done we're now mostly interested in trapping
135 // if `offset > bound - access_size`. We know `bound - access_size` here is
136 // non-negative from the above comparison.
137 //
138 // If we can know `bound - access_size >= 4GB` then with a 32-bit offset
139 // we're guaranteed:
140 //
141 // bound - access_size >= 4GB > offset
142 //
143 // or, in other words, `offset < bound - access_size`, meaning we can't trap
144 // for any value of `offset`.
145 //
146 // With that we have an optimization here where with 32-bit offsets and
147 // `bound - access_size >= 4GB` we can omit a bounds check.
148 let limit = bound - access_size;
149 if offset_ty != ir::types::I32 || limit < 0xffff_ffff {
150 let oob = if limit & 1 == 1 {
151 // Prefer testing `offset >= limit - 1` when limit is odd because an even number is
152 // likely to be a convenient constant on ARM and other RISC architectures.
153 pos.ins()
154 .icmp_imm(IntCC::UnsignedGreaterThanOrEqual, offset, limit as i64 - 1)
155 } else {
156 pos.ins()
157 .icmp_imm(IntCC::UnsignedGreaterThan, offset, limit as i64)
158 };
159 pos.ins().trapnz(oob, ir::TrapCode::HeapOutOfBounds);
160 }
161
162 compute_addr(isa, inst, heap, addr_ty, offset, offset_ty, pos.func);
163 }
164
165 /// Emit code for the base address computation of a `heap_addr` instruction.
compute_addr( isa: &dyn TargetIsa, inst: ir::Inst, heap: ir::Heap, addr_ty: ir::Type, mut offset: ir::Value, offset_ty: ir::Type, func: &mut ir::Function, )166 fn compute_addr(
167 isa: &dyn TargetIsa,
168 inst: ir::Inst,
169 heap: ir::Heap,
170 addr_ty: ir::Type,
171 mut offset: ir::Value,
172 offset_ty: ir::Type,
173 func: &mut ir::Function,
174 ) {
175 let mut pos = FuncCursor::new(func).at_inst(inst);
176 pos.use_srcloc(inst);
177
178 // Convert `offset` to `addr_ty`.
179 if offset_ty != addr_ty {
180 let labels_value = offset;
181 offset = pos.ins().uextend(addr_ty, offset);
182 if let Some(values_labels) = pos.func.dfg.values_labels.as_mut() {
183 values_labels.insert(
184 offset,
185 ir::ValueLabelAssignments::Alias {
186 from: pos.func.srclocs[inst],
187 value: labels_value,
188 },
189 );
190 }
191 }
192
193 // Add the heap base address base
194 let base = if isa.flags().enable_pinned_reg() && isa.flags().use_pinned_reg_as_heap_base() {
195 pos.ins().get_pinned_reg(isa.pointer_type())
196 } else {
197 let base_gv = pos.func.heaps[heap].base;
198 pos.ins().global_value(addr_ty, base_gv)
199 };
200
201 pos.func.dfg.replace(inst).iadd(base, offset);
202 }
203