inst.rs 34.9 KB
Newer Older
1
// Copyright 2017 The Australian National University
2
//
3 4 5
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
6
//
7
//     http://www.apache.org/licenses/LICENSE-2.0
8
//
9 10 11 12 13 14
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

15 16 17 18 19
use ir::*;
use ptr::*;
use types::*;
use op::*;

20
use utils::vec_utils;
21 22 23

use std::fmt;

24
/// Instruction represents a Mu instruction
25
#[derive(Debug)] // this implements Clone and Display
26
pub struct Instruction {
qinsoon's avatar
qinsoon committed
27
    pub hdr: MuEntityHeader,
28
    /// the values this instruction holds
qinsoon's avatar
qinsoon committed
29
    pub value: Option<Vec<P<Value>>>,
30 31 32
    /// ops field list all the children nodes,
    /// and in Instruction_, the children nodes are referred by indices
    /// This design makes it easy for the compiler to iterate through all the children
qinsoon's avatar
qinsoon committed
33
    pub ops: Vec<P<TreeNode>>,
34
    /// used for pattern matching
35
    pub v: Instruction_
36 37
}

38
// Instruction implements MuEntity
qinsoon's avatar
qinsoon committed
39 40
impl_mu_entity!(Instruction);

qinsoon's avatar
qinsoon committed
41 42 43
impl Clone for Instruction {
    fn clone(&self) -> Self {
        Instruction {
qinsoon's avatar
qinsoon committed
44
            hdr: self.hdr.clone(),
qinsoon's avatar
qinsoon committed
45
            value: self.value.clone(),
46
            ops: self.ops.clone(),
47
            v: self.v.clone()
qinsoon's avatar
qinsoon committed
48 49 50 51
        }
    }
}

52
impl Instruction {
53 54 55 56 57 58 59
    pub fn clone_with_id(&self, new_id: MuID) -> Instruction {
        let mut clone = self.clone();
        clone.hdr = self.hdr.clone_with_id(new_id);

        clone
    }

60 61
    /// is this instruction the terminal inst of its block?
    /// Terminal instructions end Mu blocks, and Mu block ends with a terminal instruction.
62 63 64 65
    pub fn is_terminal_inst(&self) -> bool {
        use inst::Instruction_::*;

        match self.v {
qinsoon's avatar
qinsoon committed
66 67 68 69 70 71 72 73 74 75
            Return(_) |
            ThreadExit |
            Throw(_) |
            TailCall(_) |
            Branch1(_) |
            Branch2 { .. } |
            Watchpoint { .. } |
            WPBranch { .. } |
            Call { .. } |
            CCall { .. } |
76 77
            SwapStackExc { .. } |
            SwapStackKill { .. } |
qinsoon's avatar
qinsoon committed
78
            Switch { .. } |
79
            ExnInstruction { .. } => true,
qinsoon's avatar
qinsoon committed
80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121
            BinOp(_, _, _) |
            BinOpWithStatus(_, _, _, _) |
            CmpOp(_, _, _) |
            ConvOp { .. } |
            ExprCall { .. } |
            ExprCCall { .. } |
            Load { .. } |
            Store { .. } |
            CmpXchg { .. } |
            AtomicRMW { .. } |
            New(_) |
            AllocA(_) |
            NewHybrid(_, _) |
            AllocAHybrid(_, _) |
            NewStack(_) |
            NewThread(_, _) |
            NewThreadExn(_, _) |
            NewFrameCursor(_) |
            GetIRef(_) |
            GetFieldIRef { .. } |
            GetElementIRef { .. } |
            ShiftIRef { .. } |
            GetVarPartIRef { .. } |
            Select { .. } |
            Fence(_) |
            CommonInst_GetThreadLocal |
            CommonInst_SetThreadLocal(_) |
            CommonInst_Pin(_) |
            CommonInst_Unpin(_) |
            CommonInst_GetAddr(_) |
            CommonInst_Tr64IsFp(_) |
            CommonInst_Tr64IsInt(_) |
            CommonInst_Tr64IsRef(_) |
            CommonInst_Tr64FromFp(_) |
            CommonInst_Tr64FromInt(_) |
            CommonInst_Tr64FromRef(_, _) |
            CommonInst_Tr64ToFp(_) |
            CommonInst_Tr64ToInt(_) |
            CommonInst_Tr64ToRef(_) |
            CommonInst_Tr64ToTag(_) |
            Move(_) |
            PrintHex(_) |
122 123 124 125
            SetRetval(_) |
            KillStack(_) |
            CurrentStack |
            SwapStackExpr { .. } => false
126 127 128
        }
    }

129
    /// is this instruction a non-terminal instruction of its block?
130 131 132 133
    pub fn is_non_terminal_inst(&self) -> bool {
        !self.is_terminal_inst()
    }

134 135 136
    /// does this instruction has side effect?
    /// An instruction has side effect if it affects something other than its result operands.
    /// e.g. affecting memory, stack, thread, etc.
137 138 139 140 141
    // FIXME: need to check correctness
    pub fn has_side_effect(&self) -> bool {
        use inst::Instruction_::*;

        match self.v {
142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158
            ExprCall { .. } |
            ExprCCall { .. } |
            Load { .. } |
            Store { .. } |
            CmpXchg { .. } |
            AtomicRMW { .. } |
            New(_) |
            AllocA(_) |
            NewHybrid(_, _) |
            AllocAHybrid(_, _) |
            NewStack(_) |
            NewThread(_, _) |
            NewThreadExn(_, _) |
            NewFrameCursor(_) |
            Fence(_) |
            Return(_) |
            ThreadExit |
159
            Throw(_) |
160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178
            TailCall(_) |
            Branch1(_) |
            Branch2 { .. } |
            Watchpoint { .. } |
            WPBranch { .. } |
            Call { .. } |
            CCall { .. } |
            SwapStackExpr { .. } |
            SwapStackExc { .. } |
            SwapStackKill { .. } |
            Switch { .. } |
            ExnInstruction { .. } |
            CommonInst_GetThreadLocal |
            CommonInst_SetThreadLocal(_) |
            CommonInst_Pin(_) |
            CommonInst_Unpin(_) |
            CommonInst_GetAddr(_) |
            PrintHex(_) |
            SetRetval(_) |
179
            KillStack(_) => true,
180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195
            BinOp(_, _, _) |
            BinOpWithStatus(_, _, _, _) |
            CmpOp(_, _, _) |
            ConvOp { .. } |
            GetIRef(_) |
            GetFieldIRef { .. } |
            GetElementIRef { .. } |
            ShiftIRef { .. } |
            GetVarPartIRef { .. } |
            Select { .. } |
            CommonInst_Tr64IsFp(_) |
            CommonInst_Tr64IsInt(_) |
            CommonInst_Tr64IsRef(_) |
            CommonInst_Tr64FromFp(_) |
            CommonInst_Tr64FromInt(_) |
            CommonInst_Tr64FromRef(_, _) |
qinsoon's avatar
qinsoon committed
196 197 198
            CommonInst_Tr64ToFp(_) |
            CommonInst_Tr64ToInt(_) |
            CommonInst_Tr64ToRef(_) |
199
            CommonInst_Tr64ToTag(_) |
200 201
            Move(_) |
            CurrentStack => false
202 203 204
        }
    }

205 206
    /// can this instruction throw exception?
    /// an instruction with an exceptional branch can throw exception
207 208 209 210
    pub fn is_potentially_excepting_instruction(&self) -> bool {
        use inst::Instruction_::*;

        match self.v {
qinsoon's avatar
qinsoon committed
211 212 213
            Watchpoint { .. } |
            Call { .. } |
            CCall { .. } |
214
            SwapStackExc { .. } |
qinsoon's avatar
qinsoon committed
215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265
            ExnInstruction { .. } => true,
            BinOp(_, _, _) |
            BinOpWithStatus(_, _, _, _) |
            CmpOp(_, _, _) |
            ConvOp { .. } |
            ExprCall { .. } |
            ExprCCall { .. } |
            Load { .. } |
            Store { .. } |
            CmpXchg { .. } |
            AtomicRMW { .. } |
            New(_) |
            AllocA(_) |
            NewHybrid(_, _) |
            AllocAHybrid(_, _) |
            NewStack(_) |
            NewThread(_, _) |
            NewThreadExn(_, _) |
            NewFrameCursor(_) |
            GetIRef(_) |
            GetFieldIRef { .. } |
            GetElementIRef { .. } |
            ShiftIRef { .. } |
            GetVarPartIRef { .. } |
            Fence(_) |
            Return(_) |
            ThreadExit |
            Throw(_) |
            TailCall(_) |
            Branch1(_) |
            Branch2 { .. } |
            Select { .. } |
            WPBranch { .. } |
            Switch { .. } |
            CommonInst_GetThreadLocal |
            CommonInst_SetThreadLocal(_) |
            CommonInst_Pin(_) |
            CommonInst_Unpin(_) |
            CommonInst_GetAddr(_) |
            CommonInst_Tr64IsFp(_) |
            CommonInst_Tr64IsInt(_) |
            CommonInst_Tr64IsRef(_) |
            CommonInst_Tr64FromFp(_) |
            CommonInst_Tr64FromInt(_) |
            CommonInst_Tr64FromRef(_, _) |
            CommonInst_Tr64ToFp(_) |
            CommonInst_Tr64ToInt(_) |
            CommonInst_Tr64ToRef(_) |
            CommonInst_Tr64ToTag(_) |
            Move(_) |
            PrintHex(_) |
266 267 268 269 270
            SetRetval(_) |
            KillStack(_) |
            CurrentStack |
            SwapStackExpr { .. } |
            SwapStackKill { .. } => false
271 272 273
        }
    }

274
    /// does this instruction have an exceptional clause/branch?
275
    pub fn has_exception_clause(&self) -> bool {
276
        self.is_potentially_excepting_instruction()
277 278
    }

qinsoon's avatar
qinsoon committed
279 280
    /// returns exception target(block ID),
    /// returns None if this instruction does not have exceptional branch
281 282 283
    pub fn get_exception_target(&self) -> Option<MuID> {
        use inst::Instruction_::*;
        match self.v {
qinsoon's avatar
qinsoon committed
284 285 286
            Watchpoint { ref resume, .. } |
            Call { ref resume, .. } |
            CCall { ref resume, .. } |
287
            SwapStackExc { ref resume, .. } |
qinsoon's avatar
qinsoon committed
288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338
            ExnInstruction { ref resume, .. } => Some(resume.exn_dest.target),
            BinOp(_, _, _) |
            BinOpWithStatus(_, _, _, _) |
            CmpOp(_, _, _) |
            ConvOp { .. } |
            ExprCall { .. } |
            ExprCCall { .. } |
            Load { .. } |
            Store { .. } |
            CmpXchg { .. } |
            AtomicRMW { .. } |
            New(_) |
            AllocA(_) |
            NewHybrid(_, _) |
            AllocAHybrid(_, _) |
            NewStack(_) |
            NewThread(_, _) |
            NewThreadExn(_, _) |
            NewFrameCursor(_) |
            GetIRef(_) |
            GetFieldIRef { .. } |
            GetElementIRef { .. } |
            ShiftIRef { .. } |
            GetVarPartIRef { .. } |
            Fence(_) |
            Return(_) |
            ThreadExit |
            Throw(_) |
            TailCall(_) |
            Branch1(_) |
            Branch2 { .. } |
            Select { .. } |
            WPBranch { .. } |
            Switch { .. } |
            CommonInst_GetThreadLocal |
            CommonInst_SetThreadLocal(_) |
            CommonInst_Pin(_) |
            CommonInst_Unpin(_) |
            CommonInst_GetAddr(_) |
            CommonInst_Tr64IsFp(_) |
            CommonInst_Tr64IsInt(_) |
            CommonInst_Tr64IsRef(_) |
            CommonInst_Tr64FromFp(_) |
            CommonInst_Tr64FromInt(_) |
            CommonInst_Tr64FromRef(_, _) |
            CommonInst_Tr64ToFp(_) |
            CommonInst_Tr64ToInt(_) |
            CommonInst_Tr64ToRef(_) |
            CommonInst_Tr64ToTag(_) |
            Move(_) |
            PrintHex(_) |
339 340 341 342 343
            SetRetval(_) |
            KillStack(_) |
            CurrentStack |
            SwapStackExpr { .. } |
            SwapStackKill { .. } => None
344 345 346
        }
    }

347 348 349 350 351 352 353
    fn debug_str(&self, ops: &Vec<P<TreeNode>>) -> String {
        self.v.debug_str(ops)
    }
}

impl fmt::Display for Instruction {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
354
        let ref ops = self.ops;
355
        if self.value.is_some() {
qinsoon's avatar
qinsoon committed
356 357
            write!(
                f,
358
                "{} = {} [{}]",
qinsoon's avatar
qinsoon committed
359
                vec_utils::as_str(self.value.as_ref().unwrap()),
360 361
                self.v.debug_str(ops),
                self.hdr
qinsoon's avatar
qinsoon committed
362
            )
363
        } else {
364
            write!(f, "{} [{}]", self.v.debug_str(ops), self.hdr)
365 366 367 368
        }
    }
}

369
/// Instruction_ is used for pattern matching for Instruction
qinsoon's avatar
qinsoon committed
370
#[allow(non_camel_case_types)]
371
#[derive(Debug, Clone)]
372 373
pub enum Instruction_ {
    // non-terminal instruction
374
    /// binary operations
375
    BinOp(BinOp, OpIndex, OpIndex),
376
    /// binary operations with status flag (overflow, sign, etc. )
qinsoon's avatar
qinsoon committed
377 378
    BinOpWithStatus(BinOp, BinOpStatus, OpIndex, OpIndex),

379
    /// comparison operations
380
    CmpOp(CmpOp, OpIndex, OpIndex),
381 382

    /// conversion operations (casting)
qinsoon's avatar
qinsoon committed
383
    ConvOp {
384 385 386
        operation: ConvOp,
        from_ty: P<MuType>,
        to_ty: P<MuType>,
387
        operand: OpIndex
388
    },
389

390
    /// a non-terminating Call instruction (the call does not have an exceptional branch)
qinsoon's avatar
qinsoon committed
391
    /// This instruction is not in the Mu spec, but is documented in the HOL formal spec
qinsoon's avatar
qinsoon committed
392
    ExprCall {
393
        data: CallData,
394
        is_abort: bool // T to abort, F to rethrow
395
    },
396

397
    /// a non-terminating CCall instruction (the call does not have an exceptional branch)
qinsoon's avatar
qinsoon committed
398
    /// This instruction is not in the Mu spec, but is documented in the HOL formal spec
qinsoon's avatar
qinsoon committed
399
    ExprCCall { data: CallData, is_abort: bool },
qinsoon's avatar
qinsoon committed
400

401
    /// load instruction
qinsoon's avatar
qinsoon committed
402
    Load {
403 404
        is_ptr: bool,
        order: MemoryOrder,
405
        mem_loc: OpIndex
406
    },
407

408
    /// store instruction
qinsoon's avatar
qinsoon committed
409
    Store {
410
        is_ptr: bool,
411
        order: MemoryOrder,
412
        mem_loc: OpIndex,
413
        value: OpIndex
414
    },
415

416
    /// compare and exchange, yields a pair value (oldvalue, boolean (T = success, F = failure))
qinsoon's avatar
qinsoon committed
417
    CmpXchg {
418 419 420 421 422 423
        is_ptr: bool,
        is_weak: bool,
        success_order: MemoryOrder,
        fail_order: MemoryOrder,
        mem_loc: OpIndex,
        expected_value: OpIndex,
424
        desired_value: OpIndex
425
    },
426

427
    /// atomic read-modify-write, yields old memory value
qinsoon's avatar
qinsoon committed
428
    AtomicRMW {
429 430 431 432
        is_ptr: bool, // T for iref, F for ptr
        order: MemoryOrder,
        op: AtomicRMWOp,
        mem_loc: OpIndex,
433
        value: OpIndex // operand for op
434
    },
435

436
    /// allocate an object (non hybrid type) in the heap, yields a reference of the type
437
    New(P<MuType>),
438

439
    /// allocate an object (non hybrid type) on the stack, yields an iref of the type
440
    AllocA(P<MuType>),
441

442 443
    /// allocate a hybrid type object in the heap, yields ref
    /// args: the type of the hybrid, hybrid part length
444
    NewHybrid(P<MuType>, OpIndex),
445

446 447
    /// allocate a hybrid type object on the stack, yields iref
    /// args: the type of the hybrid, hybrid part length
448
    AllocAHybrid(P<MuType>, OpIndex),
449

450 451 452
    /// create a new Mu stack, yields stack ref
    /// args: functionref of the entry function
    NewStack(OpIndex),
453

454
    /// kill the given Mu stack
455 456
    KillStack(OpIndex),

457
    /// return stackref for the current stack
458 459
    CurrentStack,

460 461
    /// create a new Mu thread, yields thread reference
    /// args: stackref of a Mu stack, a list of arguments
462
    NewThread(OpIndex, Vec<OpIndex>), // stack, args
463

464 465
    /// create a new Mu thread, yields thread reference (thread resumes with exceptional value)
    /// args: stackref of a Mu stack, an exceptional value
466
    NewThreadExn(OpIndex, OpIndex), // stack, exception
467

468 469
    /// create a frame cursor reference
    /// args: stackref of a Mu stack
470
    NewFrameCursor(OpIndex), // stack
471

472 473
    /// get internal reference of a reference
    /// args: a reference
474
    GetIRef(OpIndex),
475

476
    /// get internal reference of an iref (or uptr) to a struct/hybrid fix part
qinsoon's avatar
qinsoon committed
477
    GetFieldIRef {
478 479
        is_ptr: bool,
        base: OpIndex, // iref or uptr
480
        index: usize   // constant
481
    },
482

483
    /// get internal reference of an element of an iref (or uptr) to an array
qinsoon's avatar
qinsoon committed
484
    GetElementIRef {
485 486
        is_ptr: bool,
        base: OpIndex,
487
        index: OpIndex // can be constant or ssa var
488
    },
489

490
    /// offset an iref (or uptr) (offset is an index)
qinsoon's avatar
qinsoon committed
491
    ShiftIRef {
492 493
        is_ptr: bool,
        base: OpIndex,
494
        offset: OpIndex
495
    },
496

497
    /// get internal reference to an element in hybrid var part
qinsoon's avatar
qinsoon committed
498
    GetVarPartIRef { is_ptr: bool, base: OpIndex },
499

500
    /// a fence of certain memory order
501
    Fence(MemoryOrder),
502

503
    // terminal instruction
504 505
    /// return instruction
    /// args: a list of return values
506
    Return(Vec<OpIndex>),
507 508 509 510 511

    /// thread exit
    ThreadExit,

    /// throw an exception
512
    Throw(OpIndex),
513 514

    /// tail call a function (reuse current frame)
515
    TailCall(CallData),
516 517

    /// unconditional branch
518
    Branch1(Destination),
519 520

    /// conditional branch
qinsoon's avatar
qinsoon committed
521
    Branch2 {
522 523 524
        cond: OpIndex,
        true_dest: Destination,
        false_dest: Destination,
525
        true_prob: f32
526
    },
527 528

    /// returns value1 if condition is true, otherwise returns value2
qinsoon's avatar
qinsoon committed
529
    Select {
qinsoon's avatar
qinsoon committed
530 531
        cond: OpIndex,
        true_val: OpIndex,
532
        false_val: OpIndex
qinsoon's avatar
qinsoon committed
533
    },
534 535

    /// a watchpoint
qinsoon's avatar
qinsoon committed
536 537
    /// * Watchpoint NONE ResumptionData: serves as an unconditional trap.
    ///   Trap to client, and resume with ResumptionData
538 539 540
    /// * Watchpoint (WPID dest) ResumptionData:
    ///   * when disabled, jump to dest
    ///   * when enabled, trap to client and resume
qinsoon's avatar
qinsoon committed
541
    Watchpoint {
542 543
        id: Option<WPID>,
        disable_dest: Option<Destination>,
544
        resume: ResumptionData
545
    },
546 547

    /// a watchpoint branch, branch to different destinations based on enabled/disabled
qinsoon's avatar
qinsoon committed
548
    WPBranch {
549
        wp: WPID,
550
        disable_dest: Destination,
551
        enable_dest: Destination
552
    },
553 554

    /// a call instruction that may throw an exception
qinsoon's avatar
qinsoon committed
555
    Call {
556
        data: CallData,
557
        resume: ResumptionData
558
    },
559 560

    /// a ccall instruction that may throw an exception
qinsoon's avatar
qinsoon committed
561
    CCall {
qinsoon's avatar
qinsoon committed
562
        data: CallData,
563
        resume: ResumptionData
qinsoon's avatar
qinsoon committed
564
    },
565

566
    /// A swap stack with an exception clause (i.e. uses the RET_WITH form)
567
    SwapStackExc {
568 569 570
        stack: OpIndex,
        is_exception: bool,
        args: Vec<OpIndex>,
571
        resume: ResumptionData
572
    },
573

574 575
    /// A swap stack without an exception clause that is not a terminator
    /// (i.e. uses the RET_WITH form)
576 577 578
    SwapStackExpr {
        stack: OpIndex,
        is_exception: bool,
579
        args: Vec<OpIndex>
580 581
    },

582
    /// A swapstack without an exception clause that is a terminator (i.e. one with KILL_OLD)
583 584 585
    SwapStackKill {
        stack: OpIndex,
        is_exception: bool,
586
        args: Vec<OpIndex>
587
    },
588

589
    /// a multiway branch
qinsoon's avatar
qinsoon committed
590
    Switch {
591 592
        cond: OpIndex,
        default: Destination,
593
        branches: Vec<(OpIndex, Destination)>
594
    },
595 596 597

    /// a wrapper for any instruction that may throw an exception
    //  This is not used at the moment
qinsoon's avatar
qinsoon committed
598
    ExnInstruction {
qinsoon's avatar
qinsoon committed
599
        inner: Box<Instruction>,
600
        resume: ResumptionData
601 602
    },

603
    /// common inst: get thread local
604
    CommonInst_GetThreadLocal,
605
    /// common inst: set thread local
606 607
    CommonInst_SetThreadLocal(OpIndex),

608
    /// common inst: pin an object (prevent it being moved and reclaimed by GC), yields a uptr
qinsoon's avatar
qinsoon committed
609
    CommonInst_Pin(OpIndex),
610
    /// common inst: unpin an object (the object is automatically managed by GC)
611
    CommonInst_Unpin(OpIndex),
qinsoon's avatar
qinsoon committed
612 613
    /// common inst: get address of a global cell or a pinned object
    CommonInst_GetAddr(OpIndex),
614

615
    /// common inst: is the tagref a floating point?
616
    CommonInst_Tr64IsFp(OpIndex),
617
    /// common inst: is the tagref an int?
618
    CommonInst_Tr64IsInt(OpIndex),
619
    /// common inst: is the tagref a ref?
620
    CommonInst_Tr64IsRef(OpIndex),
621
    /// common inst: creates a tagref from floating point (double)
622
    CommonInst_Tr64FromFp(OpIndex),
623
    /// common inst: creates a tagref from int<52>
624
    CommonInst_Tr64FromInt(OpIndex),
625
    /// common inst: creates a tagref from reference (a ref-void typed ref, 6 bits tag)
626
    CommonInst_Tr64FromRef(OpIndex, OpIndex),
627
    /// common inst: converts a tagref to floating point (double)
628
    CommonInst_Tr64ToFp(OpIndex),
629
    /// common inst: converts a tagref to integer (int<52>)
630
    CommonInst_Tr64ToInt(OpIndex),
631
    /// common inst: converts a tagref to reference
632
    CommonInst_Tr64ToRef(OpIndex),
633
    /// common inst: converts a tagref to a tag (int<64>)
634 635
    CommonInst_Tr64ToTag(OpIndex),

636
    /// internal use: move from value to value
637
    Move(OpIndex),
638
    /// internal use: print op as hex value
639
    PrintHex(OpIndex),
640
    /// internal use: set return value for main
641
    SetRetval(OpIndex)
642 643 644 645 646 647
}

impl Instruction_ {
    fn debug_str(&self, ops: &Vec<P<TreeNode>>) -> String {
        match self {
            &Instruction_::BinOp(op, op1, op2) => format!("{:?} {} {}", op, ops[op1], ops[op2]),
qinsoon's avatar
qinsoon committed
648 649 650
            &Instruction_::BinOpWithStatus(op, status, op1, op2) => {
                format!("{:?} {:?} {} {}", op, status, ops[op1], ops[op2])
            }
651
            &Instruction_::CmpOp(op, op1, op2) => format!("{:?} {} {}", op, ops[op1], ops[op2]),
qinsoon's avatar
qinsoon committed
652 653 654 655
            &Instruction_::ConvOp {
                operation,
                ref from_ty,
                ref to_ty,
656
                operand
qinsoon's avatar
qinsoon committed
657 658
            } => format!("{:?} {} {} {}", operation, from_ty, to_ty, ops[operand]),
            &Instruction_::ExprCall { ref data, is_abort } => {
659 660
                let abort = select_value!(is_abort, "ABORT_ON_EXN", "RETHROW");
                format!("CALL {} {}", data.debug_str(ops), abort)
qinsoon's avatar
qinsoon committed
661 662
            }
            &Instruction_::ExprCCall { ref data, is_abort } => {
qinsoon's avatar
qinsoon committed
663 664 665
                let abort = select_value!(is_abort, "ABORT_ON_EXN", "RETHROW");
                format!("CCALL {} {}", data.debug_str(ops), abort)
            }
qinsoon's avatar
qinsoon committed
666 667 668
            &Instruction_::Load {
                is_ptr,
                mem_loc,
669
                order
qinsoon's avatar
qinsoon committed
670
            } => {
671
                let ptr = select_value!(is_ptr, "PTR", "");
672
                format!("LOAD {} {:?} {}", ptr, order, ops[mem_loc])
qinsoon's avatar
qinsoon committed
673 674 675 676 677
            }
            &Instruction_::Store {
                value,
                is_ptr,
                mem_loc,
678
                order
qinsoon's avatar
qinsoon committed
679
            } => {
680 681
                let ptr = select_value!(is_ptr, "PTR", "");
                format!("STORE {} {:?} {} {}", ptr, order, ops[mem_loc], ops[value])
qinsoon's avatar
qinsoon committed
682 683 684 685 686 687 688 689
            }
            &Instruction_::CmpXchg {
                is_ptr,
                is_weak,
                success_order,
                fail_order,
                mem_loc,
                expected_value,
690
                desired_value
qinsoon's avatar
qinsoon committed
691
            } => {
692 693
                let ptr = select_value!(is_ptr, "PTR", "");
                let weak = select_value!(is_weak, "WEAK", "");
qinsoon's avatar
qinsoon committed
694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709
                format!(
                    "CMPXCHG {} {} {:?} {:?} {} {} {}",
                    ptr,
                    weak,
                    success_order,
                    fail_order,
                    ops[mem_loc],
                    ops[expected_value],
                    ops[desired_value]
                )
            }
            &Instruction_::AtomicRMW {
                is_ptr,
                order,
                op,
                mem_loc,
710
                value
qinsoon's avatar
qinsoon committed
711
            } => {
712
                let ptr = select_value!(is_ptr, "PTR", "");
qinsoon's avatar
qinsoon committed
713 714 715 716 717 718 719 720 721
                format!(
                    "ATOMICRMW {} {:?} {:?} {} {}",
                    ptr,
                    order,
                    op,
                    ops[mem_loc],
                    ops[value]
                )
            }
722 723 724 725
            &Instruction_::New(ref ty) => format!("NEW {}", ty),
            &Instruction_::AllocA(ref ty) => format!("ALLOCA {}", ty),
            &Instruction_::NewHybrid(ref ty, len) => format!("NEWHYBRID {} {}", ty, ops[len]),
            &Instruction_::AllocAHybrid(ref ty, len) => format!("ALLOCAHYBRID {} {}", ty, ops[len]),
726
            &Instruction_::NewStack(func) => format!("NEW_STACK {}", ops[func]),
qinsoon's avatar
qinsoon committed
727 728 729 730 731 732 733 734 735 736
            &Instruction_::NewThread(stack, ref args) => {
                format!(
                    "NEWTHREAD {} PASS_VALUES {}",
                    ops[stack],
                    op_vector_str(args, ops)
                )
            }
            &Instruction_::NewThreadExn(stack, exn) => {
                format!("NEWTHREAD {} THROW_EXC {}", ops[stack], ops[exn])
            }
737 738
            &Instruction_::NewFrameCursor(stack) => format!("NEWFRAMECURSOR {}", ops[stack]),
            &Instruction_::GetIRef(reference) => format!("GETIREF {}", ops[reference]),
qinsoon's avatar
qinsoon committed
739 740 741
            &Instruction_::GetFieldIRef {
                is_ptr,
                base,
742
                index
qinsoon's avatar
qinsoon committed
743
            } => {
744
                let ptr = select_value!(is_ptr, "PTR", "");
745
                format!("GETFIELDIREF {} {} {}", ptr, ops[base], index)
qinsoon's avatar
qinsoon committed
746 747 748 749
            }
            &Instruction_::GetElementIRef {
                is_ptr,
                base,
750
                index
qinsoon's avatar
qinsoon committed
751
            } => {
752 753
                let ptr = select_value!(is_ptr, "PTR", "");
                format!("GETELEMENTIREF {} {} {}", ptr, ops[base], ops[index])
qinsoon's avatar
qinsoon committed
754 755 756 757
            }
            &Instruction_::ShiftIRef {
                is_ptr,
                base,
758
                offset
qinsoon's avatar
qinsoon committed
759
            } => {
760 761
                let ptr = select_value!(is_ptr, "PTR", "");
                format!("SHIFTIREF {} {} {}", ptr, ops[base], ops[offset])
qinsoon's avatar
qinsoon committed
762 763
            }
            &Instruction_::GetVarPartIRef { is_ptr, base } => {
764 765
                let ptr = select_value!(is_ptr, "PTR", "");
                format!("GETVARPARTIREF {} {}", ptr, ops[base])
qinsoon's avatar
qinsoon committed
766
            }
767

qinsoon's avatar
qinsoon committed
768
            &Instruction_::Fence(order) => format!("FENCE {:?}", order),
769

770 771
            &Instruction_::Return(ref vals) => format!("RET {}", op_vector_str(vals, ops)),
            &Instruction_::ThreadExit => "THREADEXIT".to_string(),
772 773
            &Instruction_::CurrentStack => "CURRENT_STACK".to_string(),
            &Instruction_::KillStack(s) => format!("RET {}", ops[s]),
774
            &Instruction_::Throw(exn_obj) => format!("THROW {}", ops[exn_obj]),
775 776
            &Instruction_::TailCall(ref call) => format!("TAILCALL {}", call.debug_str(ops)),
            &Instruction_::Branch1(ref dest) => format!("BRANCH {}", dest.debug_str(ops)),
qinsoon's avatar
qinsoon committed
777 778 779 780
            &Instruction_::Branch2 {
                cond,
                ref true_dest,
                ref false_dest,
781
                true_prob
qinsoon's avatar
qinsoon committed
782 783 784 785 786 787 788 789 790 791 792 793
            } => {
                format!(
                    "BRANCH2 {} {}({}) {}",
                    ops[cond],
                    true_dest.debug_str(ops),
                    true_prob,
                    false_dest.debug_str(ops)
                )
            }
            &Instruction_::Select {
                cond,
                true_val,
794
                false_val
qinsoon's avatar
qinsoon committed
795 796 797 798 799 800 801
            } => {
                format!(
                    "SELECT if {} then {} else {}",
                    ops[cond],
                    ops[true_val],
                    ops[false_val]
                )
qinsoon's avatar
qinsoon committed
802
            }
qinsoon's avatar
qinsoon committed
803 804 805
            &Instruction_::Watchpoint {
                id,
                ref disable_dest,
806
                ref resume
qinsoon's avatar
qinsoon committed
807
            } => {
808 809
                match id {
                    Some(id) => {
qinsoon's avatar
qinsoon committed
810 811 812 813 814 815
                        format!(
                            "WATCHPOINT {} {} {}",
                            id,
                            disable_dest.as_ref().unwrap().debug_str(ops),
                            resume.debug_str(ops)
                        )
816
                    }
817
                    None => format!("TRAP {}", resume.debug_str(ops))
818
                }
qinsoon's avatar
qinsoon committed
819 820 821 822
            }
            &Instruction_::WPBranch {
                wp,
                ref disable_dest,
823
                ref enable_dest
qinsoon's avatar
qinsoon committed
824 825 826 827 828 829 830 831 832 833
            } => {
                format!(
                    "WPBRANCH {} {} {}",
                    wp,
                    disable_dest.debug_str(ops),
                    enable_dest.debug_str(ops)
                )
            }
            &Instruction_::Call {
                ref data,
834
                ref resume
qinsoon's avatar
qinsoon committed
835 836 837
            } => format!("CALL {} {}", data.debug_str(ops), resume.debug_str(ops)),
            &Instruction_::CCall {
                ref data,
838
                ref resume
qinsoon's avatar
qinsoon committed
839
            } => format!("CCALL {} {}", data.debug_str(ops), resume.debug_str(ops)),
840 841 842
            &Instruction_::SwapStackExpr {
                stack,
                is_exception,
843
                ref args
844 845 846 847 848 849 850 851 852
            } => {
                format!(
                    "SWAPSTACK {} {} {}",
                    ops[stack],
                    is_exception,
                    op_vector_str(args, ops),
                )
            }
            &Instruction_::SwapStackExc {
qinsoon's avatar
qinsoon committed
853 854 855
                stack,
                is_exception,
                ref args,
856
                ref resume
qinsoon's avatar
qinsoon committed
857 858 859 860 861 862 863 864 865
            } => {
                format!(
                    "SWAPSTACK {} {} {} {}",
                    ops[stack],
                    is_exception,
                    op_vector_str(args, ops),
                    resume.debug_str(ops)
                )
            }
866 867 868 869

            &Instruction_::SwapStackKill {
                stack,
                is_exception,
870
                ref args
871 872 873 874 875 876 877 878
            } => {
                format!(
                    "SWAPSTACK {} {} {}",
                    ops[stack],
                    is_exception,
                    op_vector_str(args, ops),
                )
            }
879

qinsoon's avatar
qinsoon committed
880 881 882
            &Instruction_::Switch {
                cond,
                ref default,
883
                ref branches
qinsoon's avatar
qinsoon committed
884
            } => {
885 886 887 888 889 890 891 892 893
                let mut ret = format!("SWITCH {} {} {{", ops[cond], default.debug_str(ops));
                for i in 0..branches.len() {
                    let (op, ref dest) = branches[i];
                    ret.push_str(format!("{} {}", ops[op], dest.debug_str(ops)).as_str());
                    if i != branches.len() - 1 {
                        ret.push_str(", ");
                    }
                }
                ret.push_str("}}");
894

895
                ret
qinsoon's avatar
qinsoon committed
896 897 898
            }
            &Instruction_::ExnInstruction {
                ref inner,
899
                ref resume
qinsoon's avatar
qinsoon committed
900
            } => format!("{} {}", inner.debug_str(ops), resume.debug_str(ops)),
901 902

            // common inst
903
            &Instruction_::CommonInst_GetThreadLocal => format!("COMMONINST GetThreadLocal"),
qinsoon's avatar
qinsoon committed
904 905 906
            &Instruction_::CommonInst_SetThreadLocal(op) => {
                format!("COMMONINST SetThreadLocal {}", ops[op])
            }
907

qinsoon's avatar
qinsoon committed
908 909 910
            &Instruction_::CommonInst_Pin(op) => format!("COMMONINST Pin {}", ops[op]),
            &Instruction_::CommonInst_Unpin(op) => format!("COMMONINST Unpin {}", ops[op]),
            &Instruction_::CommonInst_GetAddr(op) => format!("COMMONINST GetAddr {}", ops[op]),
911
            // Tagerf64
qinsoon's avatar
qinsoon committed
912 913 914 915 916 917 918 919 920 921 922 923 924
            &Instruction_::CommonInst_Tr64IsFp(op) => format!("COMMONINST Tr64IsFp {}", ops[op]),
            &Instruction_::CommonInst_Tr64IsInt(op) => format!("COMMONINST Tr64IsInt {}", ops[op]),
            &Instruction_::CommonInst_Tr64IsRef(op) => format!("COMMONINST Tr64IsRef {}", ops[op]),
            &Instruction_::CommonInst_Tr64FromFp(op) => {
                format!("COMMONINST Tr64FromFp {}", ops[op])
            }
            &Instruction_::CommonInst_Tr64FromInt(op) => {
                format!("COMMONINST Tr64FromInt {}", ops[op])
            }
            &Instruction_::CommonInst_Tr64FromRef(op1, op2) => {
                format!("COMMONINST Tr64FromRet {} {}", ops[op1], ops[op2])
            }
            &Instruction_::CommonInst_Tr64ToFp(op) => format!("COMMONINST Tr64ToFp {}", ops[op]),
925 926 927 928
            &Instruction_::CommonInst_Tr64ToInt(op) => format!("COMMONINST Tr64ToInt {}", ops[op]),
            &Instruction_::CommonInst_Tr64ToRef(op) => format!("COMMONINST Tr64ToRef {}", ops[op]),
            &Instruction_::CommonInst_Tr64ToTag(op) => format!("COMMONINST Tr64ToTag {}", ops[op]),

929
            // move
930 931
            &Instruction_::Move(from) => format!("MOVE {}", ops[from]),
            // print hex
932 933
            &Instruction_::PrintHex(i) => format!("PRINTHEX {}", ops[i]),
            // set retval
934
            &Instruction_::SetRetval(val) => format!("SETRETVAL {}", ops[val])
935
        }
936
    }
937 938
}

939
/// BinOpStatus represents status flags from a binary operation
940
#[derive(Copy, Clone)]
qinsoon's avatar
qinsoon committed
941
pub struct BinOpStatus {
942
    /// negative flag
qinsoon's avatar
qinsoon committed
943
    pub flag_n: bool,
944
    /// zero flag
qinsoon's avatar
qinsoon committed
945
    pub flag_z: bool,
946
    /// carry flag
qinsoon's avatar
qinsoon committed
947
    pub flag_c: bool,
948
    /// overflow flag
949
    pub flag_v: bool
qinsoon's avatar
qinsoon committed
950 951 952
}

impl BinOpStatus {
953
    pub fn none() -> BinOpStatus {
qinsoon's avatar
qinsoon committed
954 955 956 957
        BinOpStatus {
            flag_n: false,
            flag_z: false,
            flag_c: false,
958
            flag_v: false
qinsoon's avatar
qinsoon committed
959
        }
960 961
    }

qinsoon's avatar
qinsoon committed
962
    pub fn n() -> BinOpStatus {
qinsoon's avatar
qinsoon committed
963 964 965 966
        BinOpStatus {
            flag_n: true,
            flag_z: false,
            flag_c: false,
967
            flag_v: false
qinsoon's avatar
qinsoon committed
968
        }
qinsoon's avatar
qinsoon committed
969 970 971
    }

    pub fn z() -> BinOpStatus {
qinsoon's avatar
qinsoon committed
972 973 974 975
        BinOpStatus {
            flag_n: false,
            flag_z: true,
            flag_c: false,
976
            flag_v: false
qinsoon's avatar
qinsoon committed
977
        }
qinsoon's avatar
qinsoon committed
978 979 980
    }

    pub fn c() -> BinOpStatus {
qinsoon's avatar
qinsoon committed
981 982 983 984
        BinOpStatus {
            flag_n: false,
            flag_z: false,
            flag_c: true,
985
            flag_v: false
qinsoon's avatar
qinsoon committed
986
        }
qinsoon's avatar
qinsoon committed
987 988 989
    }

    pub fn v() -> BinOpStatus {
qinsoon's avatar
qinsoon committed
990 991 992 993
        BinOpStatus {
            flag_n: false,
            flag_z: false,
            flag_c: false,
994
            flag_v: true
qinsoon's avatar
qinsoon committed
995
        }
qinsoon's avatar
qinsoon committed
996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016
    }
}

impl fmt::Debug for BinOpStatus {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        if self.flag_n {
            write!(f, "#N").unwrap();
        }
        if self.flag_z {
            write!(f, "#Z").unwrap();
        }
        if self.flag_c {
            write!(f, "#C").unwrap();
        }
        if self.flag_v {
            write!(f, "#V").unwrap();
        }
        Ok(())
    }
}

1017
#[derive(PartialEq, Eq, Copy, Clone, Debug)]
1018 1019 1020 1021 1022 1023 1024
pub enum MemoryOrder {
    NotAtomic,
    Relaxed,
    Consume,
    Acquire,
    Release,
    AcqRel,
1025
    SeqCst
1026 1027
}

1028
#[derive(Copy, Clone, Debug)]
1029 1030
pub enum CallConvention {
    Mu,
1031
    Foreign(ForeignFFI)
1032 1033
}

1034
#[derive(Copy, Clone, Debug)]
1035
pub enum ForeignFFI {
1036
    C
1037 1038
}

1039
#[derive(Clone, Debug)]
1040 1041 1042
pub struct CallData {
    pub func: OpIndex,
    pub args: Vec<OpIndex>,
1043
    pub convention: CallConvention
1044 1045 1046 1047
}

impl CallData {
    fn debug_str(&self, ops: &Vec<P<TreeNode>>) -> String {
1048
        let func_name = ops[self.func].name();
qinsoon's avatar
qinsoon committed
1049 1050 1051 1052 1053 1054
        format!(
            "{:?} {} [{}]",
            self.convention,
            func_name,
            op_vector_str(&self.args, ops)
        )
1055 1056 1057
    }
}

1058
#[derive(Clone, Debug)]
1059 1060
pub struct ResumptionData {
    pub normal_dest: Destination,
1061
    pub exn_dest: Destination
1062 1063 1064 1065
}

impl ResumptionData {
    fn debug_str(&self, ops: &Vec<P<TreeNode>>) -> String {
qinsoon's avatar
qinsoon committed
1066 1067 1068 1069 1070
        format!(
            "normal: {}, exception: {}",
            self.normal_dest.debug_str(ops),
            self.exn_dest.debug_str(ops)
        )
1071 1072 1073
    }
}

1074
#[derive(Clone, Debug)]
1075
pub struct Destination {
qinsoon's avatar
qinsoon committed
1076
    pub target: MuID,
1077
    pub args: Vec<DestArg>
1078 1079 1080 1081
}

impl Destination {
    fn debug_str(&self, ops: &Vec<P<TreeNode>>) -> String {
1082 1083
        let mut ret = format!("{}", self.target);
        ret.push('(');
1084 1085 1086 1087 1088 1089 1090
        for i in 0..self.args.len() {
            let ref arg = self.args[i];
            ret.push_str(arg.debug_str(ops).as_str());
            if i != self.args.len() - 1 {
                ret.push_str(", ");
            }
        }
1091
        ret.push(')');
1092

1093 1094
        ret
    }
1095 1096

    pub fn get_arguments_as_node(&self, ops: &Vec<P<TreeNode>>) -> Vec<P<TreeNode>> {
qinsoon's avatar
qinsoon committed
1097 1098
        vec_utils::map(&self.args, |x| match x {
            &DestArg::Normal(i) => ops[i].clone(),
1099
            &DestArg::Freshbound(_) => unimplemented!()
qinsoon's avatar
qinsoon committed
1100
        })
1101 1102
    }

1103
    pub fn get_arguments(&self, ops: &Vec<P<TreeNode>>) -> Vec<P<Value>> {
qinsoon's avatar
qinsoon committed
1104 1105
        vec_utils::map(&self.args, |x| match x {
            &DestArg::Normal(i) => ops[i].clone_value(),
1106
            &DestArg::Freshbound(_) => unimplemented!()
1107 1108
        })
    }
1109 1110
}

1111
#[derive(Clone, Debug)]
1112
pub enum DestArg {
1113
    /// a normal destination argument is an SSA value (appears in the ops field of the instruction)
1114
    Normal(OpIndex),
1115
    /// a freshbound argument is an undeclared/anonymous value (currently not support this)
1116
    Freshbound(usize)
1117 1118 1119 1120 1121 1122
}

impl DestArg {
    fn debug_str(&self, ops: &Vec<P<TreeNode>>) -> String {
        match self {
            &DestArg::Normal(index) => format!("{}", ops[index]),
1123
            &DestArg::Freshbound(n) => format!("${}", n)
1124 1125
        }
    }
1126
}
1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137

fn op_vector_str(vec: &Vec<OpIndex>, ops: &Vec<P<TreeNode>>) -> String {
    let mut ret = String::new();
    for i in 0..vec.len() {
        let index = vec[i];
        ret.push_str(format!("{}", ops[index]).as_str());
        if i != vec.len() - 1 {
            ret.push_str(", ");
        }
    }
    ret
qinsoon's avatar
qinsoon committed
1138
}