WARNING! Access to this system is limited to authorised users only.
Unauthorised users may be subject to prosecution.
Unauthorised access to this system is a criminal offence under Australian law (Federal Crimes Act 1914 Part VIA)
It is a criminal offence to:
(1) Obtain access to data without authority. -Penalty 2 years imprisonment.
(2) Damage, delete, alter or insert data without authority. -Penalty 10 years imprisonment.
User activity is monitored and recorded. Anyone using this system expressly consents to such monitoring and recording.

To protect your data, the CISO officer has suggested users to enable 2FA as soon as possible.
Currently 2.6% of users enabled 2FA.

ir.rs 36.1 KB
Newer Older
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
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.

qinsoon's avatar
qinsoon committed
15 16 17 18 19
use ptr::P;
use types::*;
use inst::*;
use op::*;

20
use utils::vec_utils;
21
use utils::LinkedHashMap;
22
use utils::LinkedHashSet;
23

24
use std;
qinsoon's avatar
qinsoon committed
25
use std::fmt;
26
use std::default;
qinsoon's avatar
qinsoon committed
27
use std::sync::atomic::{AtomicUsize, ATOMIC_USIZE_INIT, Ordering};
qinsoon's avatar
qinsoon committed
28

29 30
pub type WPID  = usize;
pub type MuID  = usize;
31
pub type MuName = String;
32
pub type CName  = MuName;
qinsoon's avatar
qinsoon committed
33

34 35
#[allow(non_snake_case)]
pub fn Mu(str: &'static str) -> MuName {str.to_string()}
qinsoon's avatar
qinsoon committed
36 37
#[allow(non_snake_case)]
pub fn C(str: &'static str) -> CName {str.to_string()}
38

39 40
pub type OpIndex = usize;

qinsoon's avatar
qinsoon committed
41 42 43
lazy_static! {
    pub static ref MACHINE_ID : AtomicUsize = {
        let a = ATOMIC_USIZE_INIT;
44
        a.store(MACHINE_ID_START, Ordering::SeqCst);
qinsoon's avatar
qinsoon committed
45 46 47 48
        a
    };
    pub static ref INTERNAL_ID : AtomicUsize = {
        let a = ATOMIC_USIZE_INIT;
49
        a.store(INTERNAL_ID_START, Ordering::SeqCst);
qinsoon's avatar
qinsoon committed
50 51
        a
    };
52 53 54
} 
pub const  MACHINE_ID_START : usize = 0;
pub const  MACHINE_ID_END   : usize = 200;
qinsoon's avatar
qinsoon committed
55

56 57 58
pub const  INTERNAL_ID_START: usize = 201;
pub const  INTERNAL_ID_END  : usize = 500;
pub const  USER_ID_START    : usize = 1001;
qinsoon's avatar
qinsoon committed
59

qinsoon's avatar
qinsoon committed
60 61 62 63 64
#[deprecated]
#[allow(dead_code)]
/// it could happen that one same machine register get different IDs
/// during serialization and restoring
/// currently I hand-write fixed ID for each machine register
qinsoon's avatar
qinsoon committed
65 66
pub fn new_machine_id() -> MuID {
    let ret = MACHINE_ID.fetch_add(1, Ordering::SeqCst);
67
    if ret >= MACHINE_ID_END {
qinsoon's avatar
qinsoon committed
68 69
        panic!("machine id overflow")
    }
70
    ret
qinsoon's avatar
qinsoon committed
71 72 73 74
}

pub fn new_internal_id() -> MuID {
    let ret = INTERNAL_ID.fetch_add(1, Ordering::SeqCst);
75
    if ret >= INTERNAL_ID_END {
qinsoon's avatar
qinsoon committed
76 77
        panic!("internal id overflow")
    }
78
    ret
qinsoon's avatar
qinsoon committed
79
}
qinsoon's avatar
qinsoon committed
80

81 82
rodal_struct!(MuFunction{hdr, sig, cur_ver, all_vers});
#[derive(Debug)]
83
pub struct MuFunction {
84
    pub hdr: MuEntityHeader,
qinsoon's avatar
qinsoon committed
85
    
86
    pub sig: P<MuFuncSig>,
qinsoon's avatar
qinsoon committed
87 88
    pub cur_ver: Option<MuID>,
    pub all_vers: Vec<MuID>
89 90 91
}

impl MuFunction {
92
    pub fn new(entity: MuEntityHeader, sig: P<MuFuncSig>) -> MuFunction {
93
        MuFunction {
94
            hdr: entity,
95 96 97 98 99
            sig: sig,
            cur_ver: None,
            all_vers: vec![]
        }
    }
100 101 102 103 104 105 106 107 108
    
    pub fn new_version(&mut self, fv: MuID) {
        if self.cur_ver.is_some() {
            let obsolete_ver = self.cur_ver.unwrap();
            self.all_vers.push(obsolete_ver);
        }
        
        self.cur_ver = Some(fv);
    }
109 110
}

qinsoon's avatar
qinsoon committed
111 112
impl fmt::Display for MuFunction {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
113
        write!(f, "Func {}", self.hdr)
qinsoon's avatar
qinsoon committed
114 115 116
    }
}

117
pub struct MuFunctionVersion {
118
    pub hdr: MuEntityHeader,
qinsoon's avatar
qinsoon committed
119 120
         
    pub func_id: MuID,
qinsoon's avatar
qinsoon committed
121
    pub sig: P<MuFuncSig>,
qinsoon's avatar
qinsoon committed
122

qinsoon's avatar
[wip]  
qinsoon committed
123
    orig_content: Option<FunctionContent>,
124
    pub content: Option<FunctionContent>,
125
    is_defined: bool,
qinsoon's avatar
qinsoon committed
126
    is_compiled: bool,
qinsoon's avatar
qinsoon committed
127

128
    pub context: FunctionContext,
129

130 131
    pub force_inline: bool,

qinsoon's avatar
qinsoon committed
132 133
    pub block_trace: Option<Vec<MuID>> // only available after Trace Generation Pass
}
134 135 136 137 138 139 140 141 142 143 144
rodal_struct!(Callsite{name, exception_destination, stack_arg_size});
pub struct Callsite {
    pub name: MuName,
    pub exception_destination: Option<MuName>,
    pub stack_arg_size: usize,
}
impl Callsite {
    pub fn new(name: MuName, exception_destination: Option<MuName>, stack_arg_size: usize)->Callsite {
        Callsite{name: name, exception_destination: exception_destination, stack_arg_size: stack_arg_size}
    }
}
qinsoon's avatar
qinsoon committed
145 146
impl fmt::Display for MuFunctionVersion {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
147
        write!(f, "FuncVer {} of Func #{}", self.hdr, self.func_id)
qinsoon's avatar
qinsoon committed
148
    }
149 150
}

151 152 153 154 155 156 157 158 159 160 161
impl fmt::Debug for MuFunctionVersion {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "FuncVer {} of Func #{}\n", self.hdr, self.func_id).unwrap();
        write!(f, "Signature: {}\n", self.sig).unwrap();
        write!(f, "IR:\n").unwrap();
        if self.content.is_some() {
            write!(f, "{:?}\n", self.content.as_ref().unwrap()).unwrap();
        } else {
            write!(f, "Empty\n").unwrap();
        }
        if self.block_trace.is_some() {
162
            write!(f, "Block Trace: {:?}\n", self.block_trace.as_ref().unwrap())
163 164 165 166 167 168
        } else {
            write!(f, "Trace not available\n")
        }
    }
}

169
impl MuFunctionVersion {
170
    pub fn new(entity: MuEntityHeader, func: MuID, sig: P<MuFuncSig>) -> MuFunctionVersion {
171
        MuFunctionVersion{
172
            hdr: entity,
qinsoon's avatar
qinsoon committed
173
            func_id: func,
qinsoon's avatar
qinsoon committed
174
            sig: sig,
qinsoon's avatar
qinsoon committed
175
            orig_content: None,
qinsoon's avatar
qinsoon committed
176
            content: None,
177
            is_defined: false,
qinsoon's avatar
qinsoon committed
178
            is_compiled: false,
qinsoon's avatar
qinsoon committed
179
            context: FunctionContext::new(),
180 181
            block_trace: None,
            force_inline: false
qinsoon's avatar
qinsoon committed
182
        }
qinsoon's avatar
qinsoon committed
183
    }
qinsoon's avatar
qinsoon committed
184

qinsoon's avatar
[wip]  
qinsoon committed
185 186 187 188 189 190 191
    pub fn new_(hdr: MuEntityHeader, id: MuID, sig: P<MuFuncSig>, content: FunctionContent, context: FunctionContext) -> MuFunctionVersion {
        MuFunctionVersion {
            hdr: hdr,
            func_id: id,
            sig: sig,
            orig_content: Some(content.clone()),
            content: Some(content),
192
            is_defined: true,
qinsoon's avatar
qinsoon committed
193
            is_compiled: false,
qinsoon's avatar
[wip]  
qinsoon committed
194 195 196 197 198 199 200 201 202 203
            context: context,
            block_trace: None,
            force_inline: false
        }
    }

    pub fn get_orig_ir(&self) -> Option<&FunctionContent> {
        self.orig_content.as_ref()
    }

204
    pub fn define(&mut self, content: FunctionContent) {
205 206 207 208 209
        if self.is_defined {
            panic!("alread defined the function: {}", self);
        }

        self.is_defined = true;
qinsoon's avatar
qinsoon committed
210
        self.orig_content = Some(content.clone());
qinsoon's avatar
qinsoon committed
211
        self.content = Some(content);
212
    }
213

qinsoon's avatar
qinsoon committed
214 215 216 217 218 219 220
    pub fn is_compiled(&self) -> bool {
        self.is_compiled
    }
    pub fn set_compiled(&mut self) {
        self.is_compiled = true;
    }

221 222
    pub fn new_ssa(&mut self, entity: MuEntityHeader, ty: P<MuType>) -> P<TreeNode> {
        let id = entity.id();
qinsoon's avatar
qinsoon committed
223
        let val = P(Value{
224
            hdr: entity,
qinsoon's avatar
qinsoon committed
225 226 227 228 229
            ty: ty,
            v: Value_::SSAVar(id)
        });

        self.context.values.insert(id, SSAVarEntry::new(val.clone()));
230

231
        P(TreeNode {
qinsoon's avatar
qinsoon committed
232 233
            op: pick_op_code_for_ssa(&val.ty),
            v: TreeNode_::Value(val)
234 235
        })
    }
236

qinsoon's avatar
qinsoon committed
237
    pub fn new_constant(&mut self, v: P<Value>) -> P<TreeNode> {
238
        P(TreeNode{
qinsoon's avatar
qinsoon committed
239 240 241 242 243
            op: pick_op_code_for_value(&v.ty),
            v: TreeNode_::Value(v)
        })
    }
    
qinsoon's avatar
qinsoon committed
244
    pub fn new_global(&mut self, v: P<Value>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
245 246
        P(TreeNode{
            op: pick_op_code_for_value(&v.ty),
qinsoon's avatar
qinsoon committed
247 248
            v: TreeNode_::Value(v)
        })
249
    }
qinsoon's avatar
qinsoon committed
250

qinsoon's avatar
qinsoon committed
251
    pub fn new_inst(&mut self, v: Instruction) -> Box<TreeNode> {
qinsoon's avatar
qinsoon committed
252
        Box::new(TreeNode{
qinsoon's avatar
qinsoon committed
253
            op: pick_op_code_for_inst(&v),
qinsoon's avatar
qinsoon committed
254 255
            v: TreeNode_::Instruction(v),
        })
qinsoon's avatar
qinsoon committed
256
    }
qinsoon's avatar
qinsoon committed
257 258

    /// get Map(CallSiteID -> FuncID) that are called by this function
259 260
    pub fn get_static_call_edges(&self) -> LinkedHashMap<MuID, MuID> {
        let mut ret = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
261 262 263

        let f_content = self.content.as_ref().unwrap();

qinsoon's avatar
qinsoon committed
264
        for (_, block) in f_content.blocks.iter() {
qinsoon's avatar
qinsoon committed
265 266 267 268 269
            let block_content = block.content.as_ref().unwrap();

            for inst in block_content.body.iter() {
                match inst.v {
                    TreeNode_::Instruction(ref inst) => {
270
                        let ref ops = inst.ops;
qinsoon's avatar
qinsoon committed
271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304

                        match inst.v {
                            Instruction_::ExprCall{ref data, ..}
                            | Instruction_::ExprCCall{ref data, ..}
                            | Instruction_::Call {ref data, ..}
                            | Instruction_::CCall {ref data, ..} => {
                                let ref callee = ops[data.func];

                                match callee.v {
                                    TreeNode_::Instruction(_) => {},
                                    TreeNode_::Value(ref pv) => match pv.v {
                                        Value_::Constant(Constant::FuncRef(id)) => {ret.insert(inst.id(), id);},
                                        _ => {}
                                    }
                                }
                            },
                            _ => {
                                // do nothing
                            }
                        }
                    },
                    _ => {
                        unreachable!()
                    }
                }
            }
        }

        ret
    }

    pub fn has_throw(&self) -> bool {
        let f_content = self.content.as_ref().unwrap();

qinsoon's avatar
qinsoon committed
305
        for (_, block) in f_content.blocks.iter() {
qinsoon's avatar
qinsoon committed
306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326
            let block_content = block.content.as_ref().unwrap();

            for inst in block_content.body.iter() {
                match inst.v {
                    TreeNode_::Instruction(ref inst) => {
                        match inst.v {
                            Instruction_::Throw(_) => {return true;}
                            _ => {
                                // do nothing
                            }
                        }
                    },
                    _ => {
                        unreachable!()
                    }
                }
            }
        }

        false
    }
327 328
}

329
#[derive(Clone)]
330
pub struct FunctionContent {
qinsoon's avatar
qinsoon committed
331
    pub entry: MuID,
332 333 334 335
    pub blocks: LinkedHashMap<MuID, Block>,

    // this field only valid after control flow analysis
    pub exception_blocks: LinkedHashSet<MuID>
336 337
}

338 339 340
impl fmt::Debug for FunctionContent {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let entry = self.get_entry_block();
341
        write!(f, "Entry block: ").unwrap();
342
        write!(f, "{:?}\n", entry).unwrap();
343 344

        write!(f, "Body:").unwrap();
345 346 347 348 349 350 351 352
        for blk_id in self.blocks.keys() {
            let block = self.get_block(*blk_id);
            write!(f, "{:?}\n", block).unwrap();
        }
        Ok(())
    }
}

353 354
impl FunctionContent {
    pub fn new(entry: MuID, blocks: LinkedHashMap<MuID, Block>) -> FunctionContent {
qinsoon's avatar
[wip]  
qinsoon committed
355
        FunctionContent {
356 357 358
            entry: entry,
            blocks: blocks,
            exception_blocks: LinkedHashSet::new()
qinsoon's avatar
[wip]  
qinsoon committed
359 360 361
        }
    }

362
    pub fn get_entry_block(&self) -> &Block {
qinsoon's avatar
qinsoon committed
363
        self.get_block(self.entry)
qinsoon's avatar
qinsoon committed
364
    } 
365

366
    pub fn get_entry_block_mut(&mut self) -> &mut Block {
qinsoon's avatar
qinsoon committed
367 368
        let entry = self.entry;
        self.get_block_mut(entry)
369
    }
370

qinsoon's avatar
qinsoon committed
371 372
    pub fn get_block(&self, id: MuID) -> &Block {
        let ret = self.blocks.get(&id);
qinsoon's avatar
qinsoon committed
373 374
        match ret {
            Some(b) => b,
qinsoon's avatar
qinsoon committed
375
            None => panic!("cannot find block #{}", id)
qinsoon's avatar
qinsoon committed
376
        }
377
    }
378

qinsoon's avatar
qinsoon committed
379 380
    pub fn get_block_mut(&mut self, id: MuID) -> &mut Block {
        let ret = self.blocks.get_mut(&id);
qinsoon's avatar
qinsoon committed
381 382
        match ret {
            Some(b) => b,
qinsoon's avatar
qinsoon committed
383
            None => panic!("cannot find block #{}", id)
qinsoon's avatar
qinsoon committed
384
        }
385
    }
386 387 388 389 390 391 392 393 394 395

    pub fn get_block_by_name(&self, name: String) -> &Block {
        for block in self.blocks.values() {
            if block.name().unwrap() == name {
                return block;
            }
        }

        panic!("cannot find block {}", name)
    }
396 397
}

398
#[derive(Default, Debug)]
399
pub struct FunctionContext {
400
    pub values: LinkedHashMap<MuID, SSAVarEntry>
401 402 403 404 405
}

impl FunctionContext {
    fn new() -> FunctionContext {
        FunctionContext {
406
            values: LinkedHashMap::new()
407 408
        }
    }
409 410
    
    pub fn make_temporary(&mut self, id: MuID, ty: P<MuType>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
411 412 413 414 415 416 417
        let val = P(Value{
            hdr: MuEntityHeader::unnamed(id),
            ty: ty,
            v: Value_::SSAVar(id)
        });

        self.values.insert(id, SSAVarEntry::new(val.clone()));
418 419

        P(TreeNode {
qinsoon's avatar
qinsoon committed
420 421
            op: pick_op_code_for_ssa(&val.ty),
            v: TreeNode_::Value(val)
422
        })
qinsoon's avatar
qinsoon committed
423 424 425 426 427 428 429 430
    }

    pub fn get_temp_display(&self, id: MuID) -> String {
        match self.get_value(id) {
            Some(entry) => format!("{}", entry.value()),
            None => "CANT_FOUND_ID".to_string()
        }
    }
qinsoon's avatar
qinsoon committed
431

qinsoon's avatar
qinsoon committed
432
    pub fn get_value(&self, id: MuID) -> Option<&SSAVarEntry> {
433 434
        self.values.get(&id)
    }
435

qinsoon's avatar
qinsoon committed
436
    pub fn get_value_mut(&mut self, id: MuID) -> Option<&mut SSAVarEntry> {
437 438 439 440
        self.values.get_mut(&id)
    }
}

441
#[derive(Clone)]
442
pub struct Block {
443
    pub hdr: MuEntityHeader,
444 445
    pub content: Option<BlockContent>,
    pub control_flow: ControlFlow
qinsoon's avatar
qinsoon committed
446 447
}

448 449 450 451 452 453 454 455 456 457 458 459 460 461
impl fmt::Debug for Block {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        writeln!(f, "Block {}", self.hdr).unwrap();
        writeln!(f, "with preds: {:?}", self.control_flow.preds).unwrap();
        writeln!(f, "     succs: {:?}", self.control_flow.succs).unwrap();
        if self.content.is_some() {
            writeln!(f, "{:?}", self.content.as_ref().unwrap()).unwrap();
        } else {
            writeln!(f, "Empty").unwrap();
        }
        Ok(())
    }
}

462
impl Block {
463 464
    pub fn new(entity: MuEntityHeader) -> Block {
        Block{hdr: entity, content: None, control_flow: ControlFlow::default()}
465
    }
qinsoon's avatar
qinsoon committed
466
    
467
    pub fn is_receiving_exception_arg(&self) -> bool {
qinsoon's avatar
qinsoon committed
468 469
        return self.content.as_ref().unwrap().exn_arg.is_some()
    }
qinsoon's avatar
qinsoon committed
470 471 472 473 474 475 476 477 478 479

    pub fn number_of_irs(&self) -> usize {
        if self.content.is_none() {
            0
        } else {
            let content = self.content.as_ref().unwrap();

            content.body.len()
        }
    }
480 481
}

482
#[derive(Debug, Clone)]
483
pub struct ControlFlow {
qinsoon's avatar
qinsoon committed
484
    pub preds : Vec<MuID>,
485 486 487
    pub succs : Vec<BlockEdge>
}

488
impl ControlFlow {
qinsoon's avatar
qinsoon committed
489
    pub fn get_hottest_succ(&self) -> Option<MuID> {
490 491 492 493 494
        if self.succs.len() == 0 {
            None
        } else {
            let mut hot_blk = self.succs[0].target;
            let mut hot_prob = self.succs[0].probability;
495

496 497 498 499 500 501
            for edge in self.succs.iter() {
                if edge.probability > hot_prob {
                    hot_blk = edge.target;
                    hot_prob = edge.probability;
                }
            }
502

503 504 505 506 507
            Some(hot_blk)
        }
    }
}

508 509
impl fmt::Display for ControlFlow {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
510 511
        write!(f, "preds: [{}], ", vec_utils::as_str(&self.preds)).unwrap();
        write!(f, "succs: [{}]", vec_utils::as_str(&self.succs))
512 513 514 515 516 517 518 519 520
    }
}

impl default::Default for ControlFlow {
    fn default() -> ControlFlow {
        ControlFlow {preds: vec![], succs: vec![]}
    }
}

521
#[derive(Copy, Clone, Debug)]
522
pub struct BlockEdge {
qinsoon's avatar
qinsoon committed
523
    pub target: MuID,
524 525 526 527 528 529 530 531 532 533 534
    pub kind: EdgeKind,
    pub is_exception: bool,
    pub probability: f32
}

impl fmt::Display for BlockEdge {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{} ({:?}{} - {})", self.target, self.kind, select_value!(self.is_exception, ", exceptional", ""), self.probability)
    }
}

535
#[derive(Copy, Clone, Debug)]
536 537 538 539
pub enum EdgeKind {
    Forward, Backward
}

540
#[derive(Clone)]
541
pub struct BlockContent {
542
    pub args: Vec<P<Value>>,
543
    pub exn_arg: Option<P<Value>>,
qinsoon's avatar
qinsoon committed
544
    pub body: Vec<Box<TreeNode>>,
545
    pub keepalives: Option<Vec<P<Value>>>
546 547
}

548 549
impl fmt::Debug for BlockContent {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
550 551 552 553 554 555 556
        writeln!(f, "args: {}", vec_utils::as_str(&self.args)).unwrap();
        if self.exn_arg.is_some() {
            writeln!(f, "exception arg: {}", self.exn_arg.as_ref().unwrap()).unwrap();
        }
        if self.keepalives.is_some() {
            writeln!(f, "keepalives: {}", vec_utils::as_str(self.keepalives.as_ref().unwrap())).unwrap();
        }
557 558 559 560 561 562 563
        for node in self.body.iter() {
            writeln!(f, "{}", node).unwrap();
        }
        Ok(())
    }
}

564 565 566 567 568 569 570 571 572
impl BlockContent {
    pub fn get_out_arguments(&self) -> Vec<P<Value>> {
        let n_insts = self.body.len();
        let ref last_inst = self.body[n_insts - 1];
        
        let mut ret : Vec<P<Value>> = vec![];
        
        match last_inst.v {
            TreeNode_::Instruction(ref inst) => {
573
                let ref ops = inst.ops;
574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608
                match inst.v {
                    Instruction_::Return(_)
                    | Instruction_::ThreadExit
                    | Instruction_::Throw(_)
                    | Instruction_::TailCall(_) => {
                        // they do not have explicit liveouts
                    }
                    Instruction_::Branch1(ref dest) => {
                        let mut live_outs = dest.get_arguments(&ops);
                        vec_utils::append_unique(&mut ret, &mut live_outs);
                    }
                    Instruction_::Branch2{ref true_dest, ref false_dest, ..} => {
                        let mut live_outs = true_dest.get_arguments(&ops);
                        live_outs.append(&mut false_dest.get_arguments(&ops));
                        
                        vec_utils::append_unique(&mut ret, &mut live_outs);
                    }
                    Instruction_::Watchpoint{ref disable_dest, ref resume, ..} => {
                        let mut live_outs = vec![];
                        
                        if disable_dest.is_some() {
                            live_outs.append(&mut disable_dest.as_ref().unwrap().get_arguments(&ops));
                        }
                        live_outs.append(&mut resume.normal_dest.get_arguments(&ops));
                        live_outs.append(&mut resume.exn_dest.get_arguments(&ops));
                        
                        vec_utils::append_unique(&mut ret, &mut live_outs);
                    }
                    Instruction_::WPBranch{ref disable_dest, ref enable_dest, ..} => {
                        let mut live_outs = vec![];
                        live_outs.append(&mut disable_dest.get_arguments(&ops));
                        live_outs.append(&mut enable_dest.get_arguments(&ops));
                        vec_utils::append_unique(&mut ret, &mut live_outs);
                    }
                    Instruction_::Call{ref resume, ..}
qinsoon's avatar
qinsoon committed
609
                    | Instruction_::CCall{ref resume, ..}
610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625
                    | Instruction_::SwapStack{ref resume, ..}
                    | Instruction_::ExnInstruction{ref resume, ..} => {
                        let mut live_outs = vec![];
                        live_outs.append(&mut resume.normal_dest.get_arguments(&ops));
                        live_outs.append(&mut resume.exn_dest.get_arguments(&ops));
                        vec_utils::append_unique(&mut ret, &mut live_outs);
                    }
                    Instruction_::Switch{ref default, ref branches, ..} => {
                        let mut live_outs = vec![];
                        live_outs.append(&mut default.get_arguments(&ops));
                        for &(_, ref dest) in branches {
                            live_outs.append(&mut dest.get_arguments(&ops));
                        }
                        vec_utils::append_unique(&mut ret, &mut live_outs);
                    }
                    
626
                    _ => panic!("didn't expect last inst as {}", inst)
627 628 629 630 631 632 633 634 635
                }
            },
            _ => panic!("expect last treenode of block is a inst")
        }
        
        ret
    }
}

636
#[derive(Debug, Clone)]
qinsoon's avatar
qinsoon committed
637 638
/// always use with P<TreeNode>
pub struct TreeNode {
639 640
    pub op: OpCode,
    pub v: TreeNode_,
qinsoon's avatar
qinsoon committed
641 642
}

643
impl TreeNode {
644
    // this is a hack to allow creating TreeNode without using a &mut MuFunctionVersion
qinsoon's avatar
qinsoon committed
645
    pub fn new_inst(v: Instruction) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
646
        P(TreeNode{
qinsoon's avatar
qinsoon committed
647
            op: pick_op_code_for_inst(&v),
qinsoon's avatar
qinsoon committed
648 649
            v: TreeNode_::Instruction(v),
        })
qinsoon's avatar
qinsoon committed
650 651
    }

qinsoon's avatar
qinsoon committed
652 653 654 655 656 657 658
    pub fn new_boxed_inst(v: Instruction) -> Box<TreeNode> {
        Box::new(TreeNode{
            op: pick_op_code_for_inst(&v),
            v: TreeNode_::Instruction(v),
        })
    }

659 660 661 662 663 664 665 666 667 668 669
    pub fn extract_ssa_id(&self) -> Option<MuID> {
        match self.v {
            TreeNode_::Value(ref pv) => {
                match pv.v {
                    Value_::SSAVar(id) => Some(id),
                    _ => None
                }
            },
            _ => None
        }
    }
qinsoon's avatar
qinsoon committed
670

qinsoon's avatar
qinsoon committed
671
    pub fn clone_value(&self) -> P<Value> {
qinsoon's avatar
qinsoon committed
672
        match self.v {
qinsoon's avatar
qinsoon committed
673
            TreeNode_::Value(ref val) => val.clone(),
674 675 676 677 678 679 680
            TreeNode_::Instruction(ref inst) => {
                let vals = inst.value.as_ref().unwrap();
                if vals.len() != 1 {
                    panic!("we expect an inst with 1 value, but found multiple or zero (it should not be here - folded as a child)");
                }
                vals[0].clone()
            }
qinsoon's avatar
qinsoon committed
681
        }
qinsoon's avatar
qinsoon committed
682 683
    }

qinsoon's avatar
qinsoon committed
684 685 686
    pub fn into_value(self) -> Option<P<Value>> {
        match self.v {
            TreeNode_::Value(val) => Some(val),
qinsoon's avatar
qinsoon committed
687
            _ => None
qinsoon's avatar
qinsoon committed
688 689
        }
    }
qinsoon's avatar
qinsoon committed
690 691 692 693 694 695 696

    pub fn into_inst(self) -> Option<Instruction> {
        match self.v {
            TreeNode_::Instruction(inst) => Some(inst),
            _ => None
        }
    }
qinsoon's avatar
qinsoon committed
697 698
}

699 700
/// use +() to display a node
impl fmt::Display for TreeNode {
qinsoon's avatar
qinsoon committed
701
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
702
        match self.v {
qinsoon's avatar
qinsoon committed
703
            TreeNode_::Value(ref pv) => pv.fmt(f),
704
            TreeNode_::Instruction(ref inst) => {
705
                write!(f, "({})", inst)
706
            }
qinsoon's avatar
qinsoon committed
707
        }
qinsoon's avatar
qinsoon committed
708
    }
qinsoon's avatar
qinsoon committed
709 710
}

711
#[derive(Debug, Clone)]
qinsoon's avatar
qinsoon committed
712
pub enum TreeNode_ {
qinsoon's avatar
qinsoon committed
713
    Value(P<Value>),
714
    Instruction(Instruction)
qinsoon's avatar
qinsoon committed
715 716 717
}

/// always use with P<Value>
718 719
rodal_struct!(Value{hdr, ty, v});
#[derive(PartialEq)]
qinsoon's avatar
qinsoon committed
720
pub struct Value {
721
    pub hdr: MuEntityHeader,
qinsoon's avatar
qinsoon committed
722 723
    pub ty: P<MuType>,
    pub v: Value_
qinsoon's avatar
qinsoon committed
724 725
}

726
impl Value {
qinsoon's avatar
qinsoon committed
727 728 729 730 731 732 733 734
    pub fn make_int_const(id: MuID, val: u64) -> P<Value> {
        P(Value{
            hdr: MuEntityHeader::unnamed(id),
            ty: UINT32_TYPE.clone(),
            v: Value_::Constant(Constant::Int(val))
        })
    }
    
735 736 737 738 739 740
    pub fn is_mem(&self) -> bool {
        match self.v {
            Value_::Memory(_) => true,
            _ => false
        }
    }
741 742

    pub fn is_reg(&self) -> bool {
743
        match self.v {
744 745 746 747 748 749 750 751
            Value_::SSAVar(_) => true,
            _ => false
        }
    }

    pub fn is_const(&self) -> bool {
        match self.v {
            Value_::Constant(_) => true,
752 753 754
            _ => false
        }
    }
qinsoon's avatar
qinsoon committed
755

qinsoon's avatar
qinsoon committed
756 757 758 759 760 761 762 763
    pub unsafe fn as_type(&self, ty: P<MuType>) -> P<Value> {
        P(Value{
            hdr: self.hdr.clone(),
            ty: ty,
            v: self.v.clone()
        })
    }

764 765 766 767 768 769 770 771
    pub fn is_int_ex_const(&self) -> bool {
        match self.v {
            Value_::Constant(Constant::IntEx(_)) => true,
            _ => false
        }
    }


772 773
    pub fn is_int_const(&self) -> bool {
        match self.v {
774 775
            Value_::Constant(Constant::Int(_)) => true,
            Value_::Constant(Constant::NullRef) => true,
776 777
            _ => false
        }
qinsoon's avatar
qinsoon committed
778
    }
779 780 781 782 783 784 785
    pub fn is_fp_const(&self) -> bool {
        match self.v {
            Value_::Constant(Constant::Float(_)) => true,
            Value_::Constant(Constant::Double(_)) => true,
            _ => false
        }
    }
786 787
    pub fn extract_int_const(&self) -> u64 {
        match self.v {
788 789
            Value_::Constant(Constant::Int(val)) => val,
            Value_::Constant(Constant::NullRef)  => 0,
790 791 792
            _ => panic!("expect int const")
        }
    }
qinsoon's avatar
qinsoon committed
793

794 795 796 797 798 799 800
    pub fn extract_int_ex_const(&self) -> Vec<u64> {
        match self.v {
            Value_::Constant(Constant::IntEx(ref val)) => val.clone(),
            _ => panic!("expect int ex const")
        }
    }

qinsoon's avatar
qinsoon committed
801 802 803 804 805 806
    pub fn extract_ssa_id(&self) -> Option<MuID> {
        match self.v {
            Value_::SSAVar(id) => Some(id),
            _ => None
        }
    }
qinsoon's avatar
qinsoon committed
807 808 809 810 811 812 813

    pub fn extract_memory_location(&self) -> Option<MemoryLocation> {
        match self.v {
            Value_::Memory(ref loc) => Some(loc.clone()),
            _ => None
        }
    }
qinsoon's avatar
qinsoon committed
814 815
}

816 817
const DISPLAY_ID : bool = true;
const DISPLAY_TYPE : bool = false;
qinsoon's avatar
qinsoon committed
818
const PRINT_ABBREVIATE_NAME: bool = true;
819

qinsoon's avatar
qinsoon committed
820 821 822 823 824 825
impl fmt::Debug for Value {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", self)
    }
}

qinsoon's avatar
qinsoon committed
826 827
impl fmt::Display for Value {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
828 829 830
        if DISPLAY_TYPE {
            match self.v {
                Value_::SSAVar(_) => {
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
831
                    write!(f, "{}(%{})", self.ty, self.hdr)
832 833
                },
                Value_::Constant(ref c) => {
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
834
                    write!(f, "{}({})", self.ty, c)
835 836
                },
                Value_::Global(ref ty) => {
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
837
                    write!(f, "{}(@{})", ty, self.hdr)
838 839
                },
                Value_::Memory(ref mem) => {
840
                    write!(f, "%{}{})", self.hdr, mem)
841 842 843 844 845 846 847 848
                }
            }
        } else {
            match self.v {
                Value_::SSAVar(_) => {
                    write!(f, "%{}", self.hdr)
                },
                Value_::Constant(ref c) => {
qinsoon's avatar
qinsoon committed
849
                    write!(f, "{}", c)
850 851
                },
                Value_::Global(_) => {
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
852
                    write!(f, "@{}", self.hdr)
853 854
                },
                Value_::Memory(ref mem) => {
855
                    write!(f, "%{}{}", self.hdr, mem)
856
                }
qinsoon's avatar
qinsoon committed
857 858 859
            }
        }
    }
860 861
}

862 863
rodal_enum!(Value_{(SSAVar: id), (Constant: val), (Global: ty), (Memory: location)});
#[derive(Debug, Clone, PartialEq)]
qinsoon's avatar
qinsoon committed
864
pub enum Value_ {
865
    SSAVar(MuID),
qinsoon's avatar
qinsoon committed
866
    Constant(Constant),
867
    Global(P<MuType>), // what type is this global (without IRef)
868
    Memory(MemoryLocation)
qinsoon's avatar
qinsoon committed
869 870
}

qinsoon's avatar
qinsoon committed
871
#[derive(Debug)]
qinsoon's avatar
qinsoon committed
872
pub struct SSAVarEntry {
qinsoon's avatar
qinsoon committed
873
    val: P<Value>,
874

875 876
    // how many times this entry is used
    // availalbe after DefUse pass
qinsoon's avatar
qinsoon committed
877
    use_count: AtomicUsize,
878

879
    // this field is only used during TreeGeneration pass
qinsoon's avatar
qinsoon committed
880 881 882 883
    expr: Option<Instruction>,

    // some ssa vars (such as int128) needs to be split into smaller vars
    split: Option<Vec<P<Value>>>
884 885
}

qinsoon's avatar
qinsoon committed
886
impl SSAVarEntry {
qinsoon's avatar
qinsoon committed
887
    pub fn new(val: P<Value>) -> SSAVarEntry {
qinsoon's avatar
qinsoon committed
888
        let ret = SSAVarEntry {
qinsoon's avatar
qinsoon committed
889
            val: val,
qinsoon's avatar
qinsoon committed
890
            use_count: ATOMIC_USIZE_INIT,
qinsoon's avatar
qinsoon committed
891 892
            expr: None,
            split: None
qinsoon's avatar
qinsoon committed
893 894 895 896 897 898
        };
        
        ret.use_count.store(0, Ordering::SeqCst);
        
        ret
    }
qinsoon's avatar
qinsoon committed
899 900 901 902 903 904 905 906 907 908 909 910 911 912 913

    pub fn ty(&self) -> &P<MuType> {
        &self.val.ty
    }

    pub fn value(&self) -> &P<Value> {
        &self.val
    }

    pub fn use_count(&self) -> usize {
        self.use_count.load(Ordering::SeqCst)
    }
    pub fn increase_use_count(&self) {
        self.use_count.fetch_add(1, Ordering::SeqCst);
    }
914 915 916
    pub fn reset_use_count(&self) {
        self.use_count.store(0, Ordering::SeqCst);
    }
qinsoon's avatar
qinsoon committed
917 918 919 920

    pub fn has_expr(&self) -> bool {
        self.expr.is_some()
    }
921 922 923
    pub fn assign_expr(&mut self, expr: Instruction) {
        self.expr = Some(expr)
    }
qinsoon's avatar
qinsoon committed
924 925 926 927
    pub fn take_expr(&mut self) -> Instruction {
        debug_assert!(self.has_expr());
        self.expr.take().unwrap()
    }
qinsoon's avatar
qinsoon committed
928 929 930 931 932 933 934 935 936 937

    pub fn has_split(&self) -> bool {
        self.split.is_some()
    }
    pub fn set_split(&mut self, vec: Vec<P<Value>>) {
        self.split = Some(vec);
    }
    pub fn get_split(&self) -> &Option<Vec<P<Value>>> {
        &self.split
    }
938 939
}

qinsoon's avatar
qinsoon committed