inst.rs 18.8 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14
// 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.

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

21
use utils::vec_utils;
22 23 24

use std::fmt;

qinsoon's avatar
qinsoon committed
25
#[derive(Debug)]
26
// this implements Clone and Display
27
pub struct Instruction {
qinsoon's avatar
qinsoon committed
28
    pub hdr: MuEntityHeader,
qinsoon's avatar
qinsoon committed
29
    pub value : Option<Vec<P<Value>>>,
30
    pub ops : Vec<P<TreeNode>>,
31 32 33
    pub v: Instruction_
}

qinsoon's avatar
qinsoon committed
34 35
impl_mu_entity!(Instruction);

qinsoon's avatar
qinsoon committed
36 37 38
impl Clone for Instruction {
    fn clone(&self) -> Self {
        Instruction {
qinsoon's avatar
qinsoon committed
39
            hdr: self.hdr.clone(),
qinsoon's avatar
qinsoon committed
40
            value: self.value.clone(),
41
            ops: self.ops.clone(),
qinsoon's avatar
qinsoon committed
42 43 44 45 46
            v: self.v.clone()
        }
    }
}

47
impl Instruction {
48 49 50 51 52 53 54
    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
    }

55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 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
    pub fn has_exception_clause(&self) -> bool {
        ir_semantics::is_potentially_excepting_instruction(&self.v)
    }

    pub fn get_exception_target(&self) -> Option<MuID> {
        use inst::Instruction_::*;
        match self.v {
            Watchpoint {ref resume, ..}
            | Call {ref resume, ..}
            | CCall {ref resume, ..}
            | SwapStack {ref resume, ..}
            | 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(_)
            | Move(_)
108 109
            | PrintHex(_)
            | SetRetval(_) => None
110 111 112
        }
    }

113 114 115 116 117 118 119
    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 {
120
        let ref ops = self.ops;
121
        if self.value.is_some() {
122
            write!(f, "{} = {}", vec_utils::as_str(self.value.as_ref().unwrap()), self.v.debug_str(ops))
123 124 125 126 127 128
        } else {
            write!(f, "{}", self.v.debug_str(ops))
        }
    }
}

qinsoon's avatar
qinsoon committed
129
#[allow(non_camel_case_types)]
130
#[derive(Debug, Clone)]
131 132
pub enum Instruction_ {
    // non-terminal instruction
133

134
    // expressions
135 136

    BinOp(BinOp, OpIndex, OpIndex),
qinsoon's avatar
qinsoon committed
137 138
    BinOpWithStatus(BinOp, BinOpStatus, OpIndex, OpIndex),

139
    CmpOp(CmpOp, OpIndex, OpIndex),
140 141 142 143 144 145
    ConvOp{
        operation: ConvOp,
        from_ty: P<MuType>,
        to_ty: P<MuType>,
        operand: OpIndex
    },
146

147 148 149
    // yields a tuple of results from the call
    ExprCall{
        data: CallData,
qinsoon's avatar
qinsoon committed
150
        is_abort: bool, // T to abort, F to rethrow - FIXME: current, always rethrow for now
151
    },
152

qinsoon's avatar
qinsoon committed
153 154 155 156 157
    ExprCCall{
        data: CallData,
        is_abort: bool
    },

158 159 160 161 162 163
    // yields the memory value
    Load{
        is_ptr: bool,
        order: MemoryOrder,
        mem_loc: OpIndex
    },
164

165 166 167
    // yields nothing
    Store{
        is_ptr: bool,
168
        order: MemoryOrder,
169 170 171
        mem_loc: OpIndex,
        value: OpIndex
    },
172

173 174 175 176 177 178 179 180 181 182
    // yields pair (oldvalue, boolean (T = success, F = failure))
    CmpXchg{
        is_ptr: bool,
        is_weak: bool,
        success_order: MemoryOrder,
        fail_order: MemoryOrder,
        mem_loc: OpIndex,
        expected_value: OpIndex,
        desired_value: OpIndex
    },
183

184 185 186 187 188 189 190 191
    // yields old memory value
    AtomicRMW{
        is_ptr: bool, // T for iref, F for ptr
        order: MemoryOrder,
        op: AtomicRMWOp,
        mem_loc: OpIndex,
        value: OpIndex // operand for op
    },
192

193 194
    // yields a reference of the type
    New(P<MuType>),
195

196 197
    // yields an iref of the type
    AllocA(P<MuType>),
198

199 200
    // yields ref
    NewHybrid(P<MuType>, OpIndex),
201

202 203
    // yields iref
    AllocAHybrid(P<MuType>, OpIndex),
204

205 206 207
    // yields stack ref
    NewStack(OpIndex), // func
                           // TODO: common inst
208

209 210
    // yields thread reference
    NewThread(OpIndex, Vec<OpIndex>), // stack, args
211

212 213
    // yields thread reference (thread resumes with exceptional value)
    NewThreadExn(OpIndex, OpIndex), // stack, exception
214

215 216
    // yields frame cursor
    NewFrameCursor(OpIndex), // stack
217

218 219
    // ref<T> -> iref<T>
    GetIRef(OpIndex),
220

221 222 223 224
    // iref|uptr<struct|hybrid<T>> int<M> -> iref|uptr<U>
    GetFieldIRef{
        is_ptr: bool,
        base: OpIndex, // iref or uptr
225
        index: usize // constant
226
    },
227

228 229 230 231 232 233
    // iref|uptr<array<T N>> int<M> -> iref|uptr<T>
    GetElementIRef{
        is_ptr: bool,
        base: OpIndex,
        index: OpIndex // can be constant or ssa var
    },
234

235 236 237 238 239 240
    // iref|uptr<T> int<M> -> iref|uptr<T>
    ShiftIRef{
        is_ptr: bool,
        base: OpIndex,
        offset: OpIndex
    },
241

242 243 244 245 246
    // iref|uptr<hybrid<T U>> -> iref|uptr<U>
    GetVarPartIRef{
        is_ptr: bool,
        base: OpIndex
    },
247

248 249 250 251 252 253 254 255 256
//    PushFrame{
//        stack: P<Value>,
//        func: P<Value>
//    },
//    PopFrame{
//        stack: P<Value>
//    }

    Fence(MemoryOrder),
257

258 259 260
    // terminal instruction
    Return(Vec<OpIndex>),
    ThreadExit, // TODO:  common inst
261
    Throw(OpIndex),
262 263 264 265 266 267 268 269
    TailCall(CallData),
    Branch1(Destination),
    Branch2{
        cond: OpIndex,
        true_dest: Destination,
        false_dest: Destination,
        true_prob: f32
    },
qinsoon's avatar
qinsoon committed
270 271 272 273 274
    Select{
        cond: OpIndex,
        true_val: OpIndex,
        false_val: OpIndex
    },
275 276 277 278 279 280 281 282
    Watchpoint{ // Watchpoint NONE ResumptionData
                //   serves as an unconditional trap. Trap to client, and resume with ResumptionData
                // Watchpoint (WPID dest) ResumptionData
                //   when disabled, jump to dest
                //   when enabled, trap to client and resume
        id: Option<WPID>,
        disable_dest: Option<Destination>,
        resume: ResumptionData
283
    },
284
    WPBranch{
285
        wp: WPID,
286 287 288 289 290 291 292
        disable_dest: Destination,
        enable_dest: Destination
    },
    Call{
        data: CallData,
        resume: ResumptionData
    },
qinsoon's avatar
qinsoon committed
293 294 295 296
    CCall{
        data: CallData,
        resume: ResumptionData
    },
297 298 299 300 301 302 303 304 305 306 307 308
    SwapStack{
        stack: OpIndex,
        is_exception: bool,
        args: Vec<OpIndex>,
        resume: ResumptionData
    },
    Switch{
        cond: OpIndex,
        default: Destination,
        branches: Vec<(OpIndex, Destination)>
    },
    ExnInstruction{
qinsoon's avatar
qinsoon committed
309
        inner: Box<Instruction>,
310
        resume: ResumptionData
311 312 313 314
    },

    // common inst
    CommonInst_GetThreadLocal,
315 316
    CommonInst_SetThreadLocal(OpIndex),

317 318 319 320
    // pin/unpin
    CommonInst_Pin  (OpIndex),
    CommonInst_Unpin(OpIndex),

321
    // internal use: mov from ops[0] to value
322 323
    Move(OpIndex),
    // internal use: print op as hex value
324 325 326
    PrintHex(OpIndex),
    // internal use: set return value for main
    SetRetval(OpIndex),
327 328 329 330 331 332
}

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
333 334 335
            &Instruction_::BinOpWithStatus(op, status, op1, op2) => {
                format!("{:?} {:?} {} {}", op, status, ops[op1], ops[op2])
            }
336
            &Instruction_::CmpOp(op, op1, op2) => format!("{:?} {} {}", op, ops[op1], ops[op2]),
qinsoon's avatar
qinsoon committed
337 338 339
            &Instruction_::ConvOp{operation, ref from_ty, ref to_ty, operand} => {
                format!("{:?} {} {} {}", operation, from_ty, to_ty, ops[operand])
            }
340 341 342 343
            &Instruction_::ExprCall{ref data, is_abort} => {
                let abort = select_value!(is_abort, "ABORT_ON_EXN", "RETHROW");
                format!("CALL {} {}", data.debug_str(ops), abort)
            },
qinsoon's avatar
qinsoon committed
344 345 346 347
            &Instruction_::ExprCCall{ref data, is_abort} => {
                let abort = select_value!(is_abort, "ABORT_ON_EXN", "RETHROW");
                format!("CCALL {} {}", data.debug_str(ops), abort)
            }
348 349
            &Instruction_::Load{is_ptr, mem_loc, order} => {
                let ptr = select_value!(is_ptr, "PTR", "");
350
                format!("LOAD {} {:?} {}", ptr, order, ops[mem_loc])
351 352 353 354 355
            },
            &Instruction_::Store{value, is_ptr, mem_loc, order} => {
                let ptr = select_value!(is_ptr, "PTR", "");
                format!("STORE {} {:?} {} {}", ptr, order, ops[mem_loc], ops[value])
            },
356
            &Instruction_::CmpXchg{is_ptr, is_weak, success_order, fail_order,
357 358 359
                mem_loc, expected_value, desired_value} => {
                let ptr = select_value!(is_ptr, "PTR", "");
                let weak = select_value!(is_weak, "WEAK", "");
360 361
                format!("CMPXCHG {} {} {:?} {:?} {} {} {}",
                    ptr, weak, success_order, fail_order, ops[mem_loc], ops[expected_value], ops[desired_value])
362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377
            },
            &Instruction_::AtomicRMW{is_ptr, order, op, mem_loc, value} => {
                let ptr = select_value!(is_ptr, "PTR", "");
                format!("ATOMICRMW {} {:?} {:?} {} {}", ptr, order, op, 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]),
            &Instruction_::AllocAHybrid(ref ty, len) => format!("ALLOCAHYBRID {} {}", ty, ops[len]),
            &Instruction_::NewStack(func) => format!("NEWSTACK {}", ops[func]),
            &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]),
            &Instruction_::NewFrameCursor(stack) => format!("NEWFRAMECURSOR {}", ops[stack]),
            &Instruction_::GetIRef(reference) => format!("GETIREF {}", ops[reference]),
            &Instruction_::GetFieldIRef{is_ptr, base, index} => {
                let ptr = select_value!(is_ptr, "PTR", "");
378
                format!("GETFIELDIREF {} {} {}", ptr, ops[base], index)
379 380 381 382 383 384 385 386 387 388 389 390 391
            },
            &Instruction_::GetElementIRef{is_ptr, base, index} => {
                let ptr = select_value!(is_ptr, "PTR", "");
                format!("GETELEMENTIREF {} {} {}", ptr, ops[base], ops[index])
            },
            &Instruction_::ShiftIRef{is_ptr, base, offset} => {
                let ptr = select_value!(is_ptr, "PTR", "");
                format!("SHIFTIREF {} {} {}", ptr, ops[base], ops[offset])
            },
            &Instruction_::GetVarPartIRef{is_ptr, base} => {
                let ptr = select_value!(is_ptr, "PTR", "");
                format!("GETVARPARTIREF {} {}", ptr, ops[base])
            },
392

393 394 395
            &Instruction_::Fence(order) => {
                format!("FENCE {:?}", order)
            },
396

397 398
            &Instruction_::Return(ref vals) => format!("RET {}", op_vector_str(vals, ops)),
            &Instruction_::ThreadExit => "THREADEXIT".to_string(),
399
            &Instruction_::Throw(exn_obj) => format!("THROW {}", ops[exn_obj]),
400 401 402 403 404
            &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))
            },
qinsoon's avatar
qinsoon committed
405 406 407
            &Instruction_::Select{cond, true_val, false_val} => {
                format!("SELECT if {} then {} else {}", ops[cond], ops[true_val], ops[false_val])
            }
408 409 410 411 412 413 414 415 416 417 418 419 420 421
            &Instruction_::Watchpoint{id, ref disable_dest, ref resume} => {
                match id {
                    Some(id) => {
                        format!("WATCHPOINT {} {} {}", id, disable_dest.as_ref().unwrap().debug_str(ops), resume.debug_str(ops))
                    },
                    None => {
                        format!("TRAP {}", 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)),
qinsoon's avatar
qinsoon committed
422
            &Instruction_::CCall{ref data, ref resume} => format!("CCALL {} {}", data.debug_str(ops), resume.debug_str(ops)),
423 424 425 426 427 428 429 430 431 432 433 434 435
            &Instruction_::SwapStack{stack, is_exception, ref args, ref resume} => {
                format!("SWAPSTACK {} {} {} {}", ops[stack], is_exception, op_vector_str(args, ops), resume.debug_str(ops))
            },
            &Instruction_::Switch{cond, ref default, ref branches} => {
                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("}}");
436

437 438 439 440
                ret
            },
            &Instruction_::ExnInstruction{ref inner, ref resume} => {
                format!("{} {}", inner.debug_str(ops), resume.debug_str(ops))
441
            },
442 443

            // common inst
444
            &Instruction_::CommonInst_GetThreadLocal => format!("COMMONINST GetThreadLocal"),
445 446
            &Instruction_::CommonInst_SetThreadLocal(op) => format!("COMMONINST SetThreadLocal {}", ops[op]),

447 448 449
            &Instruction_::CommonInst_Pin(op)   => format!("COMMONINST Pin {}",   ops[op]),
            &Instruction_::CommonInst_Unpin(op) => format!("COMMONINST Unpin {}", ops[op]),

450
            // move
451 452
            &Instruction_::Move(from) => format!("MOVE {}", ops[from]),
            // print hex
453 454 455
            &Instruction_::PrintHex(i) => format!("PRINTHEX {}", ops[i]),
            // set retval
            &Instruction_::SetRetval(val) => format!("SETRETVAL {}", ops[val]),
456
        }
457
    }
458 459
}

460
#[derive(Copy, Clone)]
qinsoon's avatar
qinsoon committed
461 462 463 464 465 466 467 468
pub struct BinOpStatus {
    pub flag_n: bool,
    pub flag_z: bool,
    pub flag_c: bool,
    pub flag_v: bool
}

impl BinOpStatus {
469 470 471 472
    pub fn none() -> BinOpStatus {
        BinOpStatus {flag_n: false, flag_z: false, flag_c: false, flag_v: false}
    }

qinsoon's avatar
qinsoon committed
473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507
    pub fn n() -> BinOpStatus {
        BinOpStatus {flag_n: true, flag_z: false, flag_c: false, flag_v: false}
    }

    pub fn z() -> BinOpStatus {
        BinOpStatus {flag_n: false, flag_z: true, flag_c: false, flag_v: false}
    }

    pub fn c() -> BinOpStatus {
        BinOpStatus {flag_n: false, flag_z: false, flag_c: true, flag_v: false}
    }

    pub fn v() -> BinOpStatus {
        BinOpStatus {flag_n: false, flag_z: false, flag_c: false, flag_v: true}
    }
}

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(())
    }
}

508
#[derive(Copy, Clone, Debug)]
509 510 511 512 513 514 515 516 517 518
pub enum MemoryOrder {
    NotAtomic,
    Relaxed,
    Consume,
    Acquire,
    Release,
    AcqRel,
    SeqCst
}

519
#[derive(Copy, Clone, Debug)]
520 521 522 523 524
pub enum CallConvention {
    Mu,
    Foreign(ForeignFFI)
}

525
#[derive(Copy, Clone, Debug)]
526 527 528 529
pub enum ForeignFFI {
    C
}

530
#[derive(Clone, Debug)]
531 532 533 534 535 536 537 538
pub struct CallData {
    pub func: OpIndex,
    pub args: Vec<OpIndex>,
    pub convention: CallConvention
}

impl CallData {
    fn debug_str(&self, ops: &Vec<P<TreeNode>>) -> String {
qinsoon's avatar
qinsoon committed
539 540 541 542 543
        let func_name = match ops[self.func].name() {
            Some(name) => name,
            None => "Anonymous Function".to_string()
        };
        format!("{:?} {} [{}]", self.convention, func_name, op_vector_str(&self.args, ops))
544 545 546
    }
}

547
#[derive(Clone, Debug)]
548 549 550 551 552 553 554 555 556 557 558
pub struct ResumptionData {
    pub normal_dest: Destination,
    pub exn_dest: Destination
}

impl ResumptionData {
    fn debug_str(&self, ops: &Vec<P<TreeNode>>) -> String {
        format!("normal: {}, exception: {}", self.normal_dest.debug_str(ops), self.exn_dest.debug_str(ops))
    }
}

559
#[derive(Clone, Debug)]
560
pub struct Destination {
qinsoon's avatar
qinsoon committed
561
    pub target: MuID,
562 563 564 565 566
    pub args: Vec<DestArg>
}

impl Destination {
    fn debug_str(&self, ops: &Vec<P<TreeNode>>) -> String {
567 568
        let mut ret = format!("{}", self.target);
        ret.push('(');
569 570 571 572 573 574 575
        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(", ");
            }
        }
576
        ret.push(')');
577

578 579
        ret
    }
580 581 582 583 584 585 586 587 588 589 590

    pub fn get_arguments_as_node(&self, ops: &Vec<P<TreeNode>>) -> Vec<P<TreeNode>> {
       vec_utils::map(&self.args,
           |x| {
               match x {
                   &DestArg::Normal(i) => ops[i].clone(),
                   &DestArg::Freshbound(_) => unimplemented!()
               }
       })
    }

591 592 593 594 595 596 597 598 599
    pub fn get_arguments(&self, ops: &Vec<P<TreeNode>>) -> Vec<P<Value>> {
        vec_utils::map(&self.args, 
            |x| {
                match x {
                    &DestArg::Normal(i) => ops[i].clone_value(),
                    &DestArg::Freshbound(_) => unimplemented!()
                }
        })
    }
600 601
}

602
#[derive(Clone, Debug)]
603 604 605 606 607 608 609 610 611
pub enum DestArg {
    Normal(OpIndex),
    Freshbound(usize)
}

impl DestArg {
    fn debug_str(&self, ops: &Vec<P<TreeNode>>) -> String {
        match self {
            &DestArg::Normal(index) => format!("{}", ops[index]),
612
            &DestArg::Freshbound(n) => format!("${}", n)
613 614
        }
    }
615
}