inst.rs

// Copyright 2017 The Australian National University
//
// 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
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// 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.

use ir::*;
use op::*;
use ptr::*;
use types::*;

use utils::vec_utils;

use std::fmt;

/// Instruction represents a Mu instruction
#[derive(Debug, Clone)] // this implements Display
pub struct Instruction {
    pub hdr: MuEntityHeader,
    /// the values this instruction holds
    pub value: Option<Vec<P<Value>>>,
    /// 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
    pub ops: Vec<P<TreeNode>>,
    /// used for pattern matching
    pub v: Instruction_
}

// Instruction implements MuEntity
impl_mu_entity!(Instruction);

impl Instruction {
    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
    }

    // RTMU add new rt instructions to various spec functions here

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

        match self.v {
            Return(_)
            | ThreadExit
            | Throw(_)
            | TailCall(_)
            | Branch1(_)
            | Branch2 { .. }
            | Watchpoint { .. }
            | WPBranch { .. }
            | Call { .. }
            | CCall { .. }
            | SwapStackExc { .. }
            | SwapStackKill { .. }
            | Switch { .. }
            | ExnInstruction { .. } => true,
            BinOp(_, _, _)
            | BinOpWithStatus(_, _, _, _)
            | CmpOp(_, _, _)
            | ConvOp { .. }
            | ExprCall { .. }
            | ExprCCall { .. }
            | Load { .. }
            | Store { .. }
            | CmpXchg { .. }
            | AtomicRMW { .. }
            | New(_)
            | AllocA(_)
            | NewHybrid(_, _)
            | AllocAHybrid(_, _)
            | NewStack(_)
            | NewThread { .. }
            | NewRTThread { .. }
            | NewFutex(_)
            | DeleteFutex(_)
            | LockFutex(_,_)
            | UnlockFutex(_,_)
            | CondVarNew
            | CondVarDelete(_)
            | CondVarAcqLock(_)
            | CondVarRelLock(_)
            | CondVarWait(_)
            | CondVarSignal(_)
            | CondVarBroadcast(_)
            | AllocAU(_)
            | AllocAUHybrid(_,_)
            | NewReg(_)
            | DeleteReg(_)
            | Intrinsic_CollectReg(_)
            | Intrinsic_FindReg(_)
            | Intrinsic_GetAllocatedReg(_)
            | Intrinsic_GetFreeReg(_)
            | rAlloc(_, _)
            | rAllocHybrid(_, _, _)
            | eAlloc(_)
            | eAllocHybrid(_, _)
            | eDelete(_)
            | NotifyThread(_)       // TODO remove - not needed anymore
            | ThreadSetPriority(_,_)
            | ThreadGetPriority(_)
            | ThreadSetCPU(_,_)
            | ThreadClearCPU(_,_)
            | ThreadIssetCPU(_,_)
            | GetTime
            | SetTime(_)
            | NewTimer
            | SetTimer { .. }
            | CancelTimer(_)
            | DeleteTimer(_)
            | Sleep(_)
            | NewAttr
            | DeleteAttr(_)
            | ThreadSetAttr(_,_)
            | ThreadGetAttr(_)
            | AttrClearCPU(_,_)
            | AttrIssetCPU(_,_)
            | AttrSetCPU(_,_)
            | AttrZeroCPU(_)
            | AttrSetPriority(_,_)
            | AttrGetPriority(_)
            | eAllocPA(_,_)
            | eAllocHybridPA(_,_,_)
            | BindObject(_)
            | UnbindObject(_)
            | NewRegionPA(_,_)
            | BindRegion(_)
            | UnbindRegion(_)
            | 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(_)
            | PrintBool(_)
            | PrintTime(_)
            | SetRetval(_)
            | GetVMThreadLocal
            | KillStack(_)
            | CurrentStack
            | RandF(_,_)
            | RandI(_,_)
            | SwapStackExpr { .. } => false,
        }
    }

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

    /// 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.
    // FIXME: need to check correctness
    pub fn has_side_effect(&self) -> bool {
        use inst::Instruction_::*;

        match self.v {
            ExprCall { .. }
            | ExprCCall { .. }
            | Load { .. }
            | Store { .. }
            | CmpXchg { .. }
            | AtomicRMW { .. }
            | New(_)
            | AllocA(_)
            | NewHybrid(_, _)
            | AllocAHybrid(_, _)
            | AllocAU(_)
            | AllocAUHybrid(_,_)
            | NewReg(_)
            | DeleteReg(_)
            | Intrinsic_CollectReg(_)
            | rAlloc(_, _)
            | rAllocHybrid(_,_,_)
            | eAlloc(_)
            | eAllocHybrid(_,_)
            | eDelete(_)
            | NewStack(_)
            | NewThread { .. }
            | NewRTThread { .. }
            | NewFutex(_)
            | DeleteFutex(_)
            | LockFutex(_,_)
            | UnlockFutex(_,_)
            | CondVarNew
            | CondVarDelete(_)
            | CondVarAcqLock(_)
            | CondVarRelLock(_)
            | CondVarWait(_)
            | CondVarSignal(_)
            | CondVarBroadcast(_)
            | NotifyThread(_)
            | ThreadSetPriority(_, _)
            | ThreadClearCPU(_, _)
            | ThreadSetCPU(_, _)
//            | AffinityZero(_)
            | SetTime(_)
            | NewTimer
            | SetTimer { .. }
            | CancelTimer(_)
            | DeleteTimer(_)
            | Sleep(_)
            | NewAttr
            | DeleteAttr(_)
            | ThreadSetAttr(_,_)
            | AttrClearCPU(_,_)
            | AttrSetCPU(_,_)
            | AttrZeroCPU(_)
            | AttrSetPriority(_,_)
            | eAllocPA(_,_)
            | eAllocHybridPA(_,_,_)
            | BindObject(_)
            | UnbindObject(_)
            | NewRegionPA(_,_)
            | BindRegion(_)
            | UnbindRegion(_)
            | NewFrameCursor(_)
            | Fence(_)
            | Return(_)
            | ThreadExit
            | Throw(_)
            | TailCall(_)
            | Branch1(_)
            | Branch2 { .. }
            | Watchpoint { .. }
            | WPBranch { .. }
            | Call { .. }
            | CCall { .. }
            | SwapStackExpr { .. }
            | SwapStackExc { .. }
            | SwapStackKill { .. }
            | Switch { .. }
            | ExnInstruction { .. }
            | CommonInst_GetThreadLocal
            | CommonInst_SetThreadLocal(_)
            | CommonInst_Pin(_)
            | CommonInst_Unpin(_)
            | CommonInst_GetAddr(_)
            | PrintHex(_)
            | PrintBool(_)
            | PrintTime(_)
            | SetRetval(_)
            | KillStack(_) => true,
            BinOp(_, _, _)
            | BinOpWithStatus(_, _, _, _)
            | CmpOp(_, _, _)
            | ConvOp { .. }
            | GetIRef(_)
            | GetFieldIRef { .. }
            | GetElementIRef { .. }
            | ShiftIRef { .. }
            | GetVarPartIRef { .. }
            | Select { .. }
            | CommonInst_Tr64IsFp(_)
            | CommonInst_Tr64IsInt(_)
            | CommonInst_Tr64IsRef(_)
            | CommonInst_Tr64FromFp(_)
            | CommonInst_Tr64FromInt(_)
            | CommonInst_Tr64FromRef(_, _)
            | CommonInst_Tr64ToFp(_)
            | CommonInst_Tr64ToInt(_)
            | CommonInst_Tr64ToRef(_)
            | CommonInst_Tr64ToTag(_)
            | Move(_)
            | CurrentStack
            | GetVMThreadLocal
            | ThreadGetPriority(_)
            | GetTime
            | ThreadGetAttr(_)
            | AttrIssetCPU(_,_)
            | AttrGetPriority(_)
            | RandF(_,_)
            | RandI(_,_)
            | Intrinsic_GetAllocatedReg(_)
            | Intrinsic_GetFreeReg(_)
            | Intrinsic_FindReg(_)
            | ThreadIssetCPU(_, _) => false,
//            | AffinityEqual(_, _)
        }
    }

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

        match self.v {
            Watchpoint { .. }
            | Call { .. }
            | CCall { .. }
            | SwapStackExc { .. }
            | ExnInstruction { .. } => true,
            BinOp(_, _, _)
            | BinOpWithStatus(_, _, _, _)
            | CmpOp(_, _, _)
            | ConvOp { .. }
            | ExprCall { .. }
            | ExprCCall { .. }
            | Load { .. }
            | Store { .. }
            | CmpXchg { .. }
            | AtomicRMW { .. }
            | New(_)
            | AllocA(_)
            | NewHybrid(_, _)
            | AllocAHybrid(_, _)
            | NewStack(_)
            | AllocAU(_)
            | AllocAUHybrid(_, _)
            | NewReg(_)
            | DeleteReg(_)
            | Intrinsic_CollectReg(_)
            | Intrinsic_FindReg(_)
            | Intrinsic_GetAllocatedReg(_)
            | Intrinsic_GetFreeReg(_)
            | rAlloc(_, _)
            | rAllocHybrid(_, _, _)
            | eAlloc(_)
            | eAllocHybrid(_, _)
            | eDelete(_)
            | NewThread { .. }
            | NewRTThread { .. }
            | NewFutex(_)
            | DeleteFutex(_)
            | LockFutex(_, _)
            | UnlockFutex(_, _)
            | CondVarNew
            | CondVarDelete(_)
            | CondVarAcqLock(_)
            | CondVarRelLock(_)
            | CondVarWait(_)
            | CondVarSignal(_)
            | CondVarBroadcast(_)
            | NotifyThread(_)
            | ThreadSetPriority(_, _)
            | ThreadGetPriority(_)
            | ThreadClearCPU(_, _)
            | ThreadSetCPU(_, _)
            | ThreadIssetCPU(_, _)
            | GetTime
            | SetTime(_)
            | NewTimer
            | SetTimer { .. }
            | CancelTimer(_)
            | DeleteTimer(_)
            | Sleep(_)
            | NewAttr
            | DeleteAttr(_)
            | ThreadSetAttr(_, _)
            | ThreadGetAttr(_)
            | AttrClearCPU(_, _)
            | AttrIssetCPU(_, _)
            | AttrSetCPU(_, _)
            | AttrZeroCPU(_)
            | AttrSetPriority(_, _)
            | AttrGetPriority(_)
            | eAllocPA(_, _)
            | eAllocHybridPA(_, _, _)
            | BindObject(_)
            | UnbindObject(_)
            | NewRegionPA(_, _)
            | BindRegion(_)
            | UnbindRegion(_)
            | 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(_)
            | PrintBool(_)
            | PrintTime(_)
            | SetRetval(_)
            | GetVMThreadLocal
            | KillStack(_)
            | CurrentStack
            | RandI(_, _)
            | RandF(_, _)
            | SwapStackExpr { .. }
            | SwapStackKill { .. } => false
        }
    }

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

    /// returns exception target(block ID),
    /// returns None if this instruction does not have exceptional branch
    pub fn get_exception_target(&self) -> Option<MuID> {
        use inst::Instruction_::*;
        match self.v {
            Watchpoint { ref resume, .. }
            | Call { ref resume, .. }
            | CCall { ref resume, .. }
            | SwapStackExc { ref resume, .. }
            | ExnInstruction { ref resume, .. } => Some(resume.exn_dest.target.id()),
            BinOp(_, _, _)
            | BinOpWithStatus(_, _, _, _)
            | CmpOp(_, _, _)
            | ConvOp { .. }
            | ExprCall { .. }
            | ExprCCall { .. }
            | Load { .. }
            | Store { .. }
            | CmpXchg { .. }
            | AtomicRMW { .. }
            | New(_)
            | AllocA(_)
            | NewHybrid(_, _)
            | AllocAU(_)
            | AllocAUHybrid(_,_)
            | NewReg(_)
            | DeleteReg(_)
            | Intrinsic_CollectReg(_)
            | Intrinsic_FindReg(_)
            | Intrinsic_GetAllocatedReg(_)
            | Intrinsic_GetFreeReg(_)
            | rAlloc(_, _)
            | rAllocHybrid(_,_,_)
//            | rAllocT(_)
            | eAlloc(_)
            | eAllocHybrid(_,_)
//            | eAllocT(_)
            | eDelete(_)
//            | eDeleteT(_)
            | AllocAHybrid(_, _)
            | NewStack(_)
            | NewThread { .. }
            | NewRTThread { .. }
            | NewFutex(_)
            | DeleteFutex(_)
            | LockFutex(_,_)
            | UnlockFutex(_,_)
            | CondVarNew
            | CondVarDelete(_)
            | CondVarAcqLock(_)
            | CondVarRelLock(_)
            | CondVarWait(_)
            | CondVarSignal(_)
            | CondVarBroadcast(_)
            | NotifyThread(_)
            | ThreadSetPriority(_,_)  // FIXME - Not sure about these
            | ThreadGetPriority(_)
            | ThreadClearCPU(_,_)
//            | AffinityEqual(_,_)
            | ThreadIssetCPU(_,_)
            | ThreadSetCPU(_,_)
//            | AffinityZero(_)
            | SetTime(_)
            | GetTime
            | NewTimer
            | SetTimer { .. }
            | CancelTimer(_)
            | DeleteTimer(_)
            | Sleep(_)
            | NewAttr
            | DeleteAttr(_)
            | ThreadSetAttr(_,_)
            | ThreadGetAttr(_)
            | AttrClearCPU(_,_)
            | AttrIssetCPU(_,_)
            | AttrSetCPU(_,_)
            | AttrZeroCPU(_)
            | AttrSetPriority(_,_)
            | AttrGetPriority(_)
            | eAllocPA(_,_)
            | eAllocHybridPA(_,_,_)
            | BindObject(_)
            | UnbindObject(_)
            | NewRegionPA(_,_)
            | BindRegion(_)
            | UnbindRegion(_)
            | 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(_)
            | PrintBool(_)
            | PrintTime(_)
            | SetRetval(_)
            | GetVMThreadLocal
            | KillStack(_)
            | CurrentStack
            | RandF(_,_)
            | RandI(_,_)
            | SwapStackExpr { .. }
            | SwapStackKill { .. } => None,
        }
    }

    /// can this instruction throw exception?
    /// (whether or not it containjs a ctach for it)
    pub fn is_potentially_throwing(&self) -> bool {
        use inst::Instruction_::*;

        match self.v {
            // Note: commented out ones are ones where we haven't implemented exceptions yet
            Watchpoint { .. } |
            Call { .. } |
            CCall { .. } |
            SwapStackExc { .. } |
            SwapStackExpr { .. } |
            ExnInstruction { .. } |
            ExprCall { .. } |
            ExprCCall { .. } |
            //Load { .. } |
            //Store { .. } |
            //CmpXchg { .. } |
            //AtomicRMW { .. } |
            //New(_) |
            //NewHybrid(_, _) |
            Throw(_)  => true,

            // BinOp(op, _, _) |
            // BinOpWithStatus(op, _, _, _) if op.may_throw() => true,
            BinOp(_, _, _) |
            BinOpWithStatus(_, _, _, _) |
            CmpOp(_, _, _) |
            ConvOp { .. } |
            AllocA(_) |
            AllocAHybrid(_, _) |
            NewStack(_) |
            NewThread { .. } |
            NewRTThread { .. } |
            NewFutex(_)
            | DeleteFutex(_)
            | LockFutex(_,_)
            | UnlockFutex(_,_)
            | CondVarNew
            | CondVarDelete(_)
            | CondVarAcqLock(_)
            | CondVarRelLock(_)
            | CondVarWait(_)
            | CondVarSignal(_)
            | CondVarBroadcast(_)
            | NotifyThread(_) |
            ThreadSetPriority(_,_) |
            NewFrameCursor(_) |
            GetIRef(_) |
            GetFieldIRef { .. } |
            GetElementIRef { .. } |
            ShiftIRef { .. } |
            GetVarPartIRef { .. } |
            Fence(_) |
            Return(_) |
            ThreadExit |
            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(_) |
            PrintBool(_) |
            PrintTime(_) |
            SetRetval(_) |
            GetVMThreadLocal |
            KillStack(_) |
            CurrentStack |
            SwapStackKill { .. } => false,

            _ => false
        }
    }

    fn debug_str(&self, ops: &Vec<P<TreeNode>>) -> String {
        match &self.v {
            &Instruction_::BinOp(op, op1, op2) => {
                format!("{}<{}> {} {}", op, ops[op1].ty(), ops[op1], ops[op2])
            }
            &Instruction_::BinOpWithStatus(op, status, op1, op2) => format!(
                "{}{}<{}> {} {}",
                op,
                status,
                ops[op1].ty(),
                ops[op1],
                ops[op2]
            ),
            &Instruction_::CmpOp(op, op1, op2) => {
                format!("{}<{}> {} {}", op, ops[op1].ty(), ops[op1], ops[op2])
            }
            &Instruction_::ConvOp {
                operation,
                ref from_ty,
                ref to_ty,
                operand
            } => format!(
                "{} <{} {}> {}",
                operation, from_ty, to_ty, ops[operand]
            ),
            &Instruction_::ExprCall { ref data, is_abort } => {
                if is_abort {
                    panic!("ABORT is not supported");
                }
                format!("CALL{}", data.debug_str(ops))
            }
            &Instruction_::ExprCCall { ref data, is_abort } => {
                if is_abort {
                    panic!("ABORT is not supported");
                }
                format!("CCALL{}", data.debug_str(ops))
            }
            &Instruction_::Load {
                is_ptr,
                mem_loc,
                order
            } => {
                let ptr = select_value!(is_ptr, " PTR", "");
                format!(
                    "LOAD{} {}<{}> {}",
                    ptr,
                    order,
                    ops[mem_loc].ty().get_referent_ty().unwrap(),
                    ops[mem_loc]
                )
            }
            &Instruction_::Store {
                value,
                is_ptr,
                mem_loc,
                order
            } => {
                let ptr = select_value!(is_ptr, " PTR", "");
                format!(
                    "STORE{} {}<{}> {} {}",
                    ptr,
                    order,
                    ops[mem_loc].ty().get_referent_ty().unwrap(),
                    ops[mem_loc],
                    ops[value]
                )
            }
            &Instruction_::CmpXchg {
                is_ptr,
                is_weak,
                success_order,
                fail_order,
                mem_loc,
                expected_value,
                desired_value
            } => {
                let ptr = select_value!(is_ptr, " PTR", "");
                let weak = select_value!(is_weak, " WEAK", "");
                format!(
                    "CMPXCHG{}{} {} {}<{}> {} {} {}",
                    ptr,
                    weak,
                    success_order,
                    fail_order,
                    ops[mem_loc].ty().get_referent_ty().unwrap(),
                    ops[mem_loc],
                    ops[expected_value],
                    ops[desired_value]
                )
            }
            &Instruction_::AtomicRMW {
                is_ptr,
                order,
                op,
                mem_loc,
                value
            } => {
                let ptr = select_value!(is_ptr, " PTR", "");
                format!(
                    "ATOMICRMW{} {} {}<{}> {} {}",
                    ptr,
                    order,
                    op,
                    ops[mem_loc].ty().get_referent_ty().unwrap(),
                    ops[mem_loc],
                    ops[value]
                )
            }
            &Instruction_::New(ref ty) => format!("NEW<{}>", ty),
            &Instruction_::AllocA(ref ty) => format!("ALLOCA<{}>", ty),
            &Instruction_::NewHybrid(ref ty, len) => {
                format!("NEWHYBRID<{} {}> {}", ty, ops[len].ty(), ops[len])
            }
            &Instruction_::AllocAHybrid(ref ty, len) => {
                format!("ALLOCAHYBRID<{} {}> {}", ty, ops[len].ty(), ops[len])
            }
            &Instruction_::NewStack(func) => format!(
                "COMMINST @uvm.new_stack<[{}]>({})",
                ops[func].ty().get_sig().unwrap(),
                ops[func]
            ),
            &Instruction_::NewReg(size) => {
                format!("COMMINST @uvm.new_region({})", ops[size])
            }
            &Instruction_::DeleteReg(regref) => {
                format!("COMMINST @uvm.delete_region({})", ops[regref])
            }
            &Instruction_::Intrinsic_CollectReg(regref) => {
                format!("INTRINSIC @uvm.collect_region({})", ops[regref])
            }
            &Instruction_::Intrinsic_FindReg(regref) => {
                format!("INTRINSIC @uvm.find_region({})", ops[regref])
            }
            &Instruction_::Intrinsic_GetAllocatedReg(regref) => {
                format!("INTRINSIC @uvm.get_allocated_region({})", ops[regref])
            }
            &Instruction_::Intrinsic_GetFreeReg(regref) => {
                format!("INTRINSIC @uvm.get_free_region({})", ops[regref])
            }
            &Instruction_::AllocAU(ref ty) => {
                format!("COMMINST @uvm.AllocAU({})", ty.id())
            }
            &Instruction_::AllocAUHybrid(ref ty, var_len) => format!(
                "COMMINST @uvm.AllocAUHybrid({}, {})",
                ty.id(),
                ops[var_len]
            ),
            &Instruction_::rAlloc(regref, ref ty) => {
                format!("COMMINST @uvm.rAlloc({}, {})", ops[regref], ty.id())
            }
            &Instruction_::rAllocHybrid(regref, ref ty, var_len) => format!(
                "COMMINST @uvm.rAllocHybrid({}, {}, {})",
                ops[regref],
                ty.id(),
                ops[var_len]
            ),
            //            &Instruction_::rAllocT(regref, ty) => format!(
            //                "COMMINST @uvm.rAllocT({}, {})",
            //                ops[regref],
            //                ops[ty]
            //            ),
            &Instruction_::eAlloc(ref ty) => {
                format!("COMMINST @uvm.eAlloc({})", ty.id())
            }
            &Instruction_::eAllocHybrid(ref ty, var_len) => format!(
                "COMMINST @uvm.eAllocHybrid({}, {})",
                ty.id(),
                ops[var_len]
            ),
            //            &Instruction_::eAllocT( ty) => format!(
            //                "COMMINST @uvm.eAllocT({})",
            //                ops[ty]
            //            ),
            &Instruction_::eDelete(obj) => {
                format!("COMMINST @uvm.eDelete({})", ops[obj])
            }
            //            &Instruction_::eDeleteT( obj) => format!(
            //                "COMMINST @uvm.eDeleteT({})",
            //                ops[obj]
            //            ),
            &Instruction_::NewThread {
                stack,
                thread_local,
                is_exception,
                ref args
            } => {
                let new_stack_clause =
                    format_new_stack_clause(is_exception, args, ops);
                let thread_local = thread_local
                    .map(|t| format!(" THREADLOCAL({})", ops[t]))
                    .unwrap_or("".to_string());
                format!(
                    "NEWTHREAD {}{} {}",
                    ops[stack], thread_local, new_stack_clause,
                )
            }

            &Instruction_::NewFutex(init_val) => {
                format!("NEWFUTEX {}", ops[init_val])
            }
            &Instruction_::DeleteFutex(futexref) => {
                format!("DELETEFUTEX {}", ops[futexref])
            }
            &Instruction_::LockFutex(futexref, timeout) => {
                format!("LockFUTEX ({}, {})", ops[futexref], ops[timeout])
            }
            &Instruction_::UnlockFutex(futexref, count) => {
                format!("UNLOCKFUTEX {}, {}", ops[futexref], ops[count])
            }

            &Instruction_::CondVarNew => format!("CONDVAR_NEW"),
            &Instruction_::CondVarDelete(addr) => {
                format!("CONDVAR_DELETE {}", ops[addr])
            }
            &Instruction_::CondVarAcqLock(addr) => {
                format!("CONDVAR_ACQ_LOCK {}", ops[addr])
            }
            &Instruction_::CondVarRelLock(addr) => {
                format!("CONDVAR_REL_LOCK {}", ops[addr])
            }
            &Instruction_::CondVarWait(addr) => {
                format!("CONDVAR_WAIT {}", ops[addr])
            }
            &Instruction_::CondVarSignal(addr) => {
                format!("CONDVAR_SIGNAL {}", ops[addr])
            }
            &Instruction_::CondVarBroadcast(addr) => {
                format!("CONDVAR_BROADCAST {}", ops[addr])
            }

            &Instruction_::NewRTThread {
                attr,
                stack,
                thread_local,
                is_exception,
                ref args
            } => {
                let new_stack_clause =
                    format_new_stack_clause(is_exception, args, ops);
                let thread_local = thread_local
                    .map(|t| format!(" THREADLOCAL({})", ops[t]))
                    .unwrap_or("".to_string());
                format!(
                    "NEWRTTHREAD {}, {}, {}, {}",
                    ops[attr], ops[stack], thread_local, new_stack_clause,
                )
            }

            &Instruction_::NotifyThread(thread) => {
                format!("COMMINST @uvm.notifythread({})", ops[thread])
            }
            &Instruction_::ThreadSetPriority(thread, priority) => format!(
                "COMMINST @uvm.threadsetpriority({}, {})",
                ops[thread], ops[priority]
            ),
            &Instruction_::ThreadGetPriority(thread) => {
                format!("COMMINST @uvm.threadgetpriority({})", ops[thread])
            }
            &Instruction_::ThreadClearCPU(thread, cpu) => format!(
                "COMMINST @uvm.threadclearcpu({}, {})",
                ops[thread], ops[cpu]
            ),
            &Instruction_::ThreadSetCPU(thread, cpu) => format!(
                "COMMINST @uvm.threadsetcpu({}, {})",
                ops[thread], ops[cpu]
            ),
            &Instruction_::ThreadIssetCPU(thread, cpu) => format!(
                "COMMINST @uvm.threadissetcpu({}, {})",
                ops[thread], ops[cpu]
            ),
            &Instruction_::GetTime => format!("COMMINST @uvm.gettime()",),
            &Instruction_::SetTime(time) => {
                format!("COMMINST @uvm.settime({})", ops[time])
            }
            &Instruction_::NewTimer => format!("COMMINST @uvm.newtimer"),
            &Instruction_::SetTimer {
                tmr,
                tm,
                prd,
                ref data
            } => format!(
                "COMMINST @uvm.settimer({}, {}, {}) ",
                ops[tmr], ops[tm], ops[prd]
            ),
            &Instruction_::CancelTimer(tmr) => {
                format!("COMMINST @uvm.canceltimer({})", ops[tmr])
            }
            &Instruction_::DeleteTimer(tmr) => {
                format!("COMMINST @uvm.deletetimer({})", ops[tmr])
            }
            &Instruction_::Sleep(dur) => {
                format!("COMMINST @uvm.sleep_ns({})", ops[dur])
            }

            &Instruction_::NewAttr => format!("NEWATTR()"),
            &Instruction_::DeleteAttr(aref) => {
                format!("DELETEATTR({})", ops[aref])
            }
            &Instruction_::ThreadSetAttr(tref, aref) => {
                format!("SETATTR({}, {})", ops[tref], ops[aref])
            }
            &Instruction_::ThreadGetAttr(tref) => {
                format!("GETATTR({})", ops[tref])
            }
            &Instruction_::AttrSetPriority(aref, p) => format!(
                "COMMINST @uvm.attr.setpriority({}, {})",
                ops[aref], ops[p]
            ),
            &Instruction_::AttrGetPriority(aref) => {
                format!("COMMINST @uvm.attr.getpriority({})", ops[aref])
            }
            &Instruction_::AttrSetCPU(aref, c) => {
                format!("COMMINST @uvm.attr.setcpu({}, {})", ops[aref], ops[c])
            }
            &Instruction_::AttrClearCPU(aref, c) => format!(
                "COMMINST @uvm.attr.clearcpu({}, {})",
                ops[aref], ops[c]
            ),
            &Instruction_::AttrIssetCPU(aref, c) => format!(
                "COMMINST @uvm.attr.issetcpu({}, {})",
                ops[aref], ops[c]
            ),
            &Instruction_::AttrZeroCPU(aref) => {
                format!("COMMINST @uvm.attr.zerocpu({})", ops[aref])
            }
            &Instruction_::eAllocPA(ref ty, addr) => format!(
                "COMMINST @uvm.emm.eallocpa({}, {})",
                ty.id(),
                ops[addr]
            ),
            &Instruction_::eAllocHybridPA(ref ty, len, addr) => format!(
                "COMMINST @uvm.emm.eallochybridpa({}, {}, {})",
                ty.id(),
                ops[len],
                ops[addr]
            ),
            &Instruction_::BindObject(obj) => {
                format!("COMMINST @uvm.emm.bindobject({})", ops[obj])
            }
            &Instruction_::UnbindObject(obj) => {
                format!("COMMINST @uvm.emm.unbindobject({})", ops[obj])
            }
            &Instruction_::NewRegionPA(size, addr) => format!(
                "COMMINST @uvm.regions.newregionpa({}, {})",
                ops[size], ops[addr]
            ),
            &Instruction_::BindRegion(reg) => {
                format!("COMMINST @uvm.regions.bindregion({})", ops[reg])
            }
            &Instruction_::UnbindRegion(reg) => {
                format!("COMMINST @uvm.regions.unbindregion({})", ops[reg])
            }

            &Instruction_::NewFrameCursor(stack) => {
                format!("COMMINST @uvm.meta.new_cursor({})", ops[stack])
            }
            &Instruction_::GetIRef(reference) => format!(
                "GETIREF<{}> {}",
                ops[reference].ty().get_referent_ty().unwrap(),
                ops[reference]
            ),
            &Instruction_::GetFieldIRef {
                is_ptr,
                base,
                index
            } => {
                let ptr = select_value!(is_ptr, " PTR", "");
                format!(
                    "GETFIELDIREF{}<{} {}> {}",
                    ptr,
                    ops[base].ty().get_referent_ty().unwrap(),
                    index,
                    ops[base]
                )
            }
            &Instruction_::GetElementIRef {
                is_ptr,
                base,
                index
            } => {
                let ptr = select_value!(is_ptr, " PTR", "");
                format!(
                    "GETELEMIREF{}<{} {}>{} {}",
                    ptr,
                    ops[base].ty().get_referent_ty().unwrap(),
                    ops[index].ty(),
                    ops[base],
                    ops[index]
                )
            }
            &Instruction_::ShiftIRef {
                is_ptr,
                base,
                offset
            } => {
                let ptr = select_value!(is_ptr, " PTR", "");
                format!(
                    "SHIFTIREF{}<{} {}>{} {}",
                    ptr,
                    ops[base].ty().get_referent_ty().unwrap(),
                    ops[offset].ty(),
                    ops[base],
                    ops[offset]
                )
            }
            &Instruction_::GetVarPartIRef { is_ptr, base } => {
                let ptr = select_value!(is_ptr, " PTR", "");
                format!(
                    "GETVARPARTIREF{}<{}> {}",
                    ptr,
                    ops[base].ty().get_referent_ty().unwrap(),
                    ops[base]
                )
            }

            &Instruction_::Fence(order) => format!("FENCE {}", order),

            &Instruction_::Return(ref vals) => {
                if vals.len() == 0 {
                    format!("RET")
                } else if vals.len() == 1 {
                    format!("RET {}", ops[vals[0]])
                } else {
                    format!("RET ({})", op_vector_str(vals, ops))
                }
            }
            &Instruction_::ThreadExit => {
                "COMMINST @uvm.thread_exit".to_string()
            }
            &Instruction_::CurrentStack => {
                "COMMINST @uvm.current_stack".to_string()
            }
            &Instruction_::KillStack(s) => {
                format!("COMMINST @uvm.kill_stack({})", ops[s])
            }
            &Instruction_::Throw(exn_obj) => format!("THROW {}", ops[exn_obj]),
            &Instruction_::TailCall(ref call) => {
                format!("TAILCALL{}", call.debug_str(ops))
            }
            &Instruction_::Branch1(ref dest) => {
                format!("BRANCH {}", dest.debug_str(ops))
            }
            &Instruction_::Branch2 {
                cond,
                ref true_dest,
                ref false_dest,
                ..
            } => format!(
                "BRANCH2 {} {} {}",
                ops[cond],
                true_dest.debug_str(ops),
                false_dest.debug_str(ops)
            ),
            &Instruction_::Select {
                cond,
                true_val,
                false_val
            } => format!(
                "SELECT<{} {}> {} {} {}",
                ops[cond].ty(),
                ops[true_val].ty(),
                ops[cond],
                ops[true_val],
                ops[false_val]
            ),
            &Instruction_::Watchpoint {
                id,
                ref disable_dest,
                ref resume
            } => {
                match id {
                    Some(id) => {
                        format!(
                            // TODO: WPEXC should be optional
                            "WATCHPOINT {}<{}> {} {} WPEXC({})",
                            id,
                            format_value_types(&self.value),
                            disable_dest.as_ref().unwrap().debug_str(ops),
                            resume.normal_dest.debug_str(ops),
                            resume.exn_dest.debug_str(ops)
                        )
                    }
                    //TRAP < Ts > excClause keepAliveClause
                    None => format!(
                        "TRAP<{}> {}",
                        format_value_types(&self.value),
                        resume.debug_str(ops)
                    )
                }
            }
            &Instruction_::WPBranch {
                wp,
                ref disable_dest,
                ref enable_dest
            } => format!(
                "WPBRANCH {} {} {}",
                wp,
                disable_dest.debug_str(ops),
                enable_dest.debug_str(ops)
            ),
            &Instruction_::Call {
                ref data,
                ref resume
            } => {
                format!("CALL{} {}", data.debug_str(ops), resume.debug_str(ops))
            }
            &Instruction_::CCall {
                ref data,
                ref resume
            } => format!(
                "CCALL{} {}",
                data.debug_str(ops),
                resume.debug_str(ops)
            ),
            &Instruction_::SwapStackExpr {
                stack,
                is_exception,
                ref args
            } => format!(
                "SWAPSTACK {} RET_WITH<{}> {}",
                ops[stack],
                format_value_types(&self.value),
                format_new_stack_clause(is_exception, args, ops)
            ),
            &Instruction_::SwapStackExc {
                stack,
                is_exception,
                ref args,
                ref resume
            } => format!(
                "SWAPSTACK {} RET_WITH<{}> {} {}",
                ops[stack],
                format_value_types(&self.value),
                format_new_stack_clause(is_exception, args, ops),
                resume.debug_str(ops)
            ),

            &Instruction_::SwapStackKill {
                stack,
                is_exception,
                ref args
            } => format!(
                "SWAPSTACK {} KILL_OLD {}",
                ops[stack],
                format_new_stack_clause(is_exception, args, ops)
            ),

            &Instruction_::Switch {
                cond,
                ref default,
                ref branches
            } => {
                //SWITCH < T > opnd default { ( value dest ) rep }
                let mut ret = format!(
                    "SWITCH<{}> {} {} {{",
                    ops[cond].ty(),
                    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("}");

                ret
            }
            &Instruction_::ExnInstruction {
                ref inner,
                ref resume
            } => format!("{} {}", inner.debug_str(ops), resume.debug_str(ops)),

            // common inst
            &Instruction_::CommonInst_GetThreadLocal => {
                format!("COMMINST @uvm.get_threadlocal")
            }
            &Instruction_::CommonInst_SetThreadLocal(op) => {
                format!("COMMINST @uvm.set_threadlocal({})", ops[op])
            }

            &Instruction_::CommonInst_Pin(op) => format!(
                "COMMINST @uvm.native.pin<{}>({})",
                ops[op].ty(),
                ops[op]
            ),
            &Instruction_::CommonInst_Unpin(op) => format!(
                "COMMINST @uvm.native.unpin<{}>({})",
                ops[op].ty(),
                ops[op]
            ),
            &Instruction_::CommonInst_GetAddr(op) => format!(
                "COMMINST @uvm.native.get_addr<{}>({})",
                ops[op].ty(),
                ops[op]
            ),
            // Tagerf64
            &Instruction_::CommonInst_Tr64IsFp(op) => {
                format!("COMMINST @uvm.tr64.is_fp({})", ops[op])
            }
            &Instruction_::CommonInst_Tr64IsInt(op) => {
                format!("COMMINST @uvm.tr64.is_int({})", ops[op])
            }
            &Instruction_::CommonInst_Tr64IsRef(op) => {
                format!("COMMINST @uvm.tr64.is_ref({})", ops[op])
            }
            &Instruction_::CommonInst_Tr64FromFp(op) => {
                format!("COMMINST @uvm.tr64.from_fp({})", ops[op])
            }
            &Instruction_::CommonInst_Tr64FromInt(op) => {
                format!("COMMINST @uvm.tr64.from_int({})", ops[op])
            }
            &Instruction_::CommonInst_Tr64FromRef(op1, op2) => format!(
                "COMMINST @uvm.tr64.from_ref({} {})",
                ops[op1], ops[op2]
            ),
            &Instruction_::CommonInst_Tr64ToFp(op) => {
                format!("COMMINST @uvm.tr64.to_fp({})", ops[op])
            }
            &Instruction_::CommonInst_Tr64ToInt(op) => {
                format!("COMMINST @uvm.tr64.to_int({})", ops[op])
            }
            &Instruction_::CommonInst_Tr64ToRef(op) => {
                format!("COMMINST @uvm.tr64.to_ref({})", ops[op])
            }
            &Instruction_::CommonInst_Tr64ToTag(op) => {
                format!("COMMINST @uvm.tr64.to_tag({})", ops[op])
            }

            // move
            &Instruction_::Move(from) => {
                format!("MOVE<{}> {}", ops[from].ty(), ops[from])
            }
            // print hex
            &Instruction_::PrintHex(i) => {
                format!("PRINTHEX<{}> {}", ops[i].ty(), ops[i])
            }
            &Instruction_::PrintBool(i) => {
                format!("PRINTBOOL<{}> {}", ops[i].ty(), ops[i])
            }
            &Instruction_::PrintTime(i) => {
                format!("PRINTTIME<{}> {}", ops[i].ty(), ops[i])
            }
            // set retval
            &Instruction_::SetRetval(val) => format!("SETRETVAL {}", ops[val]),
            &Instruction_::RandI(min, max) => {
                format!("RandI ({}, {})", ops[min], ops[max])
            }
            &Instruction_::RandF(min, max) => {
                format!("RandF ({}, {})", ops[min], ops[max])
            }
            // get vm thread local
            &Instruction_::GetVMThreadLocal => format!("GETVMTHREADLOCAL")
        }
    }
}

const PRINT_INST_NAME: bool = false;

impl fmt::Display for Instruction {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let ref ops = self.ops;
        let value = match &self.value {
            &Some(ref v) if v.len() == 0 => format!(""),
            &Some(ref v) if v.len() == 1 => format!("{} = ", v[0]),
            &Some(ref v) => format!("({}) = ", vec_utils::as_str_sp(&v)),
            &None => format!("")
        };

        if PRINT_INST_NAME {
            write!(f, "{}[{}]{}", value, self.hdr, self.debug_str(ops))