1
//! Constraints that affect program generation
2
//!
3
//! Defines specific configurations that are not allowed, causing programs
4
//! or program fragments to be rejected during the generation process.
5
//!
6
//! The motivation for these constraints are in producing a good quality hash
7
//! function by avoiding hazards that affect timing or hash mixing. However,
8
//! they also form an integral part of the program generation model.
9
//! Generating correct HashX output depends on applying exactly the right
10
//! constraints.
11

            
12
use crate::program::{Instruction, InstructionVec, Opcode};
13
use crate::register::{RegisterId, RegisterSet, NUM_REGISTERS};
14
use crate::scheduler::Scheduler;
15

            
16
pub(crate) use model::{Pass, RegisterWriter};
17

            
18
/// The `model` attempts to document what the HashX constraints are, separate
19
/// from the process of implementing those constraints.
20
mod model {
21
    use crate::program::{Opcode, NUM_INSTRUCTIONS};
22
    use crate::register::{self, RegisterId};
23

            
24
    /// Programs require an exact number of instructions. (The instruction
25
    /// buffer must have filled without any of the other stopping conditions)
26
    pub(super) const REQUIRED_INSTRUCTIONS: usize = NUM_INSTRUCTIONS;
27

            
28
    /// Programs require an exact overall data latency, represented as the
29
    /// simulated cycle at which the last register write completes.
30
    pub(super) const REQUIRED_OVERALL_RESULT_AT_CYCLE: usize = 194;
31

            
32
    /// Programs require an exact total number of multiply instructions, they
33
    /// can't be skipped for any reason.
34
    pub(super) const REQUIRED_MULTIPLIES: usize = 192;
35

            
36
    /// Determine which ops count when testing [`REQUIRED_MULTIPLIES`].
37
    #[inline(always)]
38
4722250
    pub(super) fn is_multiply(op: Opcode) -> bool {
39
4722250
        matches!(op, Opcode::Mul | Opcode::SMulH | Opcode::UMulH)
40
4722250
    }
41

            
42
    /// Does an instruction prohibit using the same register for src and dst?
43
    ///
44
    /// Meaningful only for ops that have both a source and destination register.
45
    #[inline(always)]
46
4431960
    pub(super) fn disallow_src_is_dst(op: Opcode) -> bool {
47
1947270
        matches!(
48
4431960
            op,
49
            Opcode::AddShift | Opcode::Mul | Opcode::Sub | Opcode::Xor
50
        )
51
4431960
    }
52

            
53
    /// Special case for register R5
54
    ///
55
    /// HashX special-cases one specific register for AddShift in order to fit
56
    /// in the constraints of x86_64 under the encodings chosen by HashX's
57
    /// original x86 compiler backend. See Table 2-5 in the Intel 64 and IA-32
58
    /// Software Developer Manual Volume 2A, "Special Cases of REX Encodings".
59
    /// Register R13 in x86_64 maps directly to R5 in the original HashX
60
    /// implementation. Even on backends where this constraint is not relevant,
61
    /// the program generation process requires us to take it into account.
62
    pub(super) const DISALLOW_REGISTER_FOR_ADDSHIFT: RegisterId = register::R5;
63

            
64
    /// Should `proposed` be rejected as the immediate successor of `previous`?
65
    #[inline(always)]
66
5045105
    pub(super) fn disallow_opcode_pair(previous: Opcode, proposed: Opcode) -> bool {
67
5045105
        match proposed {
68
            // Never rejected at this stage
69
2061605
            Opcode::Mul | Opcode::UMulH | Opcode::SMulH | Opcode::Target | Opcode::Branch => false,
70
            // Disallow exact opcode duplicates
71
            Opcode::AddConst | Opcode::Xor | Opcode::XorConst | Opcode::Rotate => {
72
2240160
                previous == proposed
73
            }
74
            // Register add/sub can't be chosen back to back
75
            Opcode::AddShift | Opcode::Sub => {
76
743340
                previous == Opcode::AddShift || previous == Opcode::Sub
77
            }
78
        }
79
5045105
    }
80

            
81
    /// Should `this_writer` be allowed on a register which was previously
82
    /// written using `last_writer`?
83
    ///
84
    /// Requires the current [`Pass`].
85
    #[inline(always)]
86
19299865
    pub(super) fn writer_pair_allowed(
87
19299865
        pass: Pass,
88
19299865
        last_writer: RegisterWriter,
89
19299865
        this_writer: RegisterWriter,
90
19299865
    ) -> bool {
91
19299865
        match (last_writer, this_writer) {
92
            // HashX disallows back-to-back 64-bit multiplies on the
93
            // same destination register in Pass::Original but permits
94
            // them on the retry if the source register isn't identical.
95
2699645
            (RegisterWriter::Mul(_), RegisterWriter::Mul(_)) if matches!(pass, Pass::Original) => {
96
2687815
                false
97
            }
98

            
99
            // Other pairings are allowed if the writer info differs at all.
100
16612050
            (last_writer, this_writer) => last_writer != this_writer,
101
        }
102
19299865
    }
103

            
104
    /// One specific pass in the multi-pass instruction choice process
105
    ///
106
    /// [`super::Instruction`] choice can take multiple attempts to complete,
107
    /// and we allow the [`super::Validator`] to make different decisions on
108
    /// each pass.
109
    #[derive(Debug, Copy, Clone, Eq, PartialEq)]
110
    pub(crate) enum Pass {
111
        /// First pass, nothing has failed
112
        Original,
113
        /// Single retry pass before a timing stall
114
        Retry,
115
    }
116

            
117
    /// Information about the instruction that writes to a register, from the
118
    /// perspective of our particular constraints here
119
    ///
120
    /// This is conceptually similar to storing the last [`super::Instruction`]
121
    /// that wrote to a register, but HashX sometimes needs information for
122
    /// constraints which won't end up in the final `Instruction`.
123
    ///
124
    /// We've chosen the encoding to minimize the code size in
125
    /// writer_pair_allowed. Most pairwise comparisons can just be a register
126
    /// equality test.
127
    ///
128
    /// The instructions here fall into three categories which use their own
129
    /// format for encoding arguments:
130
    ///
131
    ///  - Wide Multiply, extra u32
132
    ///
133
    ///    UMulH and SMulH use an additional otherwise unused 32-bit value
134
    ///    from the Rng when considering writer collisions.
135
    ///
136
    ///    As far as I can tell this is a bug in the original implementation
137
    ///    but we can't change the behavior without breaking compatibility.
138
    ///
139
    ///    The collisions are rare enough not to be a worthwhile addition
140
    ///    to ASIC-resistance. It seems like this was a vestigial feature
141
    ///    left over from immediate value matching features which were removed
142
    ///    during the development of HashX, but I can't be sure.
143
    ///
144
    ///  - Constant source
145
    ///
146
    ///    Only considers the opcode itself, not the specific immediate value.
147
    ///
148
    ///  - Register source
149
    ///
150
    ///    Considers the source register, collapses add/subtract into one op.
151
    ///
152
    #[derive(Debug, Default, Clone, Copy, Eq, PartialEq)]
153
    pub(crate) enum RegisterWriter {
154
        /// Register not written yet
155
        #[default]
156
        None,
157
        /// Register source writer for [`super::Instruction::Mul`]
158
        Mul(RegisterId),
159
        /// Wide multiply writer for [`super::Instruction::UMulH`]
160
        UMulH(u32),
161
        /// Wide multiply writer for [`super::Instruction::SMulH`]
162
        SMulH(u32),
163
        /// Register source writer for [`super::Instruction::AddShift`]
164
        /// and [`super::Instruction::Sub`]
165
        AddSub(RegisterId),
166
        /// Constant source writer for [`super::Instruction::AddConst`]
167
        AddConst,
168
        /// Register source writer for [`super::Instruction::Xor`]
169
        Xor(RegisterId),
170
        /// Constant source writer for [`super::Instruction::XorConst`]
171
        XorConst,
172
        /// Constant source writer for [`super::Instruction::Rotate`]
173
        Rotate,
174
    }
175
}
176

            
177
/// Stateful program constraint checker
178
///
179
/// This keeps additional state during the construction of a new program,
180
/// in order to check constraints that may reject registers and entire programs.
181
#[derive(Debug, Clone)]
182
pub(crate) struct Validator {
183
    /// For each register in the file, keep track of the instruction it was
184
    /// written by.
185
    ///
186
    /// This becomes part of the constraints for
187
    /// destination registers in future instructions.
188
    writer_map: RegisterWriterMap,
189

            
190
    /// Total multiplication operations of all types
191
    multiply_count: usize,
192
}
193

            
194
impl Validator {
195
    /// Construct a new empty Validator.
196
    #[inline(always)]
197
9230
    pub(crate) fn new() -> Self {
198
9230
        Self {
199
9230
            writer_map: RegisterWriterMap::new(),
200
9230
            multiply_count: 0,
201
9230
        }
202
9230
    }
203

            
204
    /// Commit a new instruction to the validator state.
205
    #[inline(always)]
206
4722250
    pub(crate) fn commit_instruction(&mut self, inst: &Instruction, regw: RegisterWriter) {
207
4722250
        if model::is_multiply(inst.opcode()) {
208
1770990
            self.multiply_count += 1;
209
2951260
        }
210
4722250
        match inst.destination() {
211
295360
            None => debug_assert_eq!(regw, RegisterWriter::None),
212
4426890
            Some(dst) => self.writer_map.insert(dst, regw),
213
        }
214
4722250
    }
215

            
216
    /// Is the completed program acceptable?
217
    ///
218
    /// Once the whole program is assembled, HashX still has a chance to reject
219
    /// it if it fails certain criteria.
220
    #[inline(always)]
221
9230
    pub(crate) fn check_whole_program(
222
9230
        &self,
223
9230
        scheduler: &Scheduler,
224
9230
        instructions: &InstructionVec,
225
9230
    ) -> Result<(), ()> {
226
9230
        if instructions.len() == model::REQUIRED_INSTRUCTIONS
227
8060
            && scheduler.overall_latency().as_usize() == model::REQUIRED_OVERALL_RESULT_AT_CYCLE
228
8060
            && self.multiply_count == model::REQUIRED_MULTIPLIES
229
        {
230
8060
            Ok(())
231
        } else {
232
1170
            Err(())
233
        }
234
9230
    }
235

            
236
    /// Begin checking which destination registers are allowed for an op after
237
    /// its source is known, using the current state of the validator.
238
    ///
239
    /// Returns a DstRegisterChecker which can be used to test each specific
240
    /// destination RegisterId quickly.
241
    #[inline(always)]
242
4431960
    pub(crate) fn dst_registers_allowed(
243
4431960
        &self,
244
4431960
        op: Opcode,
245
4431960
        pass: Pass,
246
4431960
        writer_info: RegisterWriter,
247
4431960
        src: Option<RegisterId>,
248
4431960
    ) -> DstRegisterChecker<'_> {
249
4431960
        DstRegisterChecker {
250
4431960
            pass,
251
4431960
            writer_info,
252
4431960
            writer_map: &self.writer_map,
253
4431960
            op_is_add_shift: op == Opcode::AddShift,
254
4431960
            disallow_equal: if model::disallow_src_is_dst(op) {
255
2484690
                src
256
            } else {
257
1947270
                None
258
            },
259
        }
260
4431960
    }
261
}
262

            
263
/// State information returned by [`Validator::dst_registers_allowed`]
264
#[derive(Debug, Clone)]
265
pub(crate) struct DstRegisterChecker<'v> {
266
    /// Is this the original or retry pass?
267
    pass: Pass,
268
    /// Reference to a table of [`RegisterWriter`] information for each register
269
    writer_map: &'v RegisterWriterMap,
270
    /// The new [`RegisterWriter`] under consideration
271
    writer_info: RegisterWriter,
272
    /// Was this [`Opcode::AddShift`]?
273
    op_is_add_shift: bool,
274
    /// Optionally disallow one matching register, used to implement [`model::disallow_src_is_dst`]
275
    disallow_equal: Option<RegisterId>,
276
}
277

            
278
impl<'v> DstRegisterChecker<'v> {
279
    /// Check a single destination register for usability, using context from
280
    /// [`Validator::dst_registers_allowed`]
281
    #[inline(always)]
282
21918975
    pub(crate) fn check(&self, dst: RegisterId) -> bool {
283
21918975
        // One register specified by DISALLOW_REGISTER_FOR_ADDSHIFT can't
284
21918975
        // be used as destination for AddShift.
285
21918975
        if self.op_is_add_shift && dst == model::DISALLOW_REGISTER_FOR_ADDSHIFT {
286
177515
            return false;
287
21741460
        }
288
21741460

            
289
21741460
        // A few instructions disallow choosing src and dst as the same
290
21741460
        if Some(dst) == self.disallow_equal {
291
2441595
            return false;
292
19299865
        }
293
19299865

            
294
19299865
        // Additional constraints are written on the pair of previous and
295
19299865
        // current instructions with the same destination.
296
19299865
        model::writer_pair_allowed(self.pass, self.writer_map.get(dst), self.writer_info)
297
21918975
    }
298
}
299

            
300
/// Figure out the allowed register set for an operation, given what's available
301
/// in the schedule.
302
#[inline(always)]
303
2780050
pub(crate) fn src_registers_allowed(available: RegisterSet, op: Opcode) -> RegisterSet {
304
2780050
    // HashX defines a special case DISALLOW_REGISTER_FOR_ADDSHIFT for
305
2780050
    // destination registers, and it also includes a look-ahead
306
2780050
    // condition here in source register allocation to prevent the dst
307
2780050
    // allocation from getting stuck as often. If we have only two
308
2780050
    // remaining registers for AddShift and one is the disallowed reg,
309
2780050
    // HashX defines that the random choice is short-circuited early
310
2780050
    // here and we always choose the one combination which is actually
311
2780050
    // allowed.
312
2780050
    if op == Opcode::AddShift
313
318370
        && available.contains(model::DISALLOW_REGISTER_FOR_ADDSHIFT)
314
177515
        && available.len() == 2
315
    {
316
        RegisterSet::from_filter(
317
            #[inline(always)]
318
            |reg| reg == model::DISALLOW_REGISTER_FOR_ADDSHIFT,
319
        )
320
    } else {
321
2780050
        available
322
    }
323
2780050
}
324

            
325
/// Should `proposed` be allowed as an opcode selector output immediately
326
/// following an output of `previous`?
327
///
328
/// Some pairs of adjacent [`Opcode`]s are rejected at the opcode selector level
329
/// without causing an entire instruction generation pass to fail.
330
#[inline(always)]
331
5054335
pub(crate) fn opcode_pair_allowed(previous: Option<Opcode>, proposed: Opcode) -> Result<(), ()> {
332
5054335
    match previous {
333
9230
        None => Ok(()),
334
5045105
        Some(previous) => {
335
5045105
            if model::disallow_opcode_pair(previous, proposed) {
336
327015
                Err(())
337
            } else {
338
4718090
                Ok(())
339
            }
340
        }
341
    }
342
5054335
}
343

            
344
/// Map each [`RegisterId`] to an [`RegisterWriter`]
345
#[derive(Default, Debug, Clone)]
346
struct RegisterWriterMap([RegisterWriter; NUM_REGISTERS]);
347

            
348
impl RegisterWriterMap {
349
    /// Make a new empty register writer map.
350
    ///
351
    /// All registers are set to None.
352
    #[inline(always)]
353
9230
    fn new() -> Self {
354
9230
        Default::default()
355
9230
    }
356

            
357
    /// Write or overwrite the last [`RegisterWriter`] associated with `reg`.
358
    #[inline(always)]
359
4426890
    fn insert(&mut self, reg: RegisterId, writer: RegisterWriter) {
360
4426890
        self.0[reg.as_usize()] = writer;
361
4426890
    }
362

            
363
    /// Return the most recent mapping for 'reg', if any.
364
    #[inline(always)]
365
19299865
    fn get(&self, reg: RegisterId) -> RegisterWriter {
366
19299865
        self.0[reg.as_usize()]
367
19299865
    }
368
}