ir.rs 33.8 KB
Newer Older
qinsoon's avatar
qinsoon committed
1 2 3 4 5
use ptr::P;
use types::*;
use inst::*;
use op::*;

6
use utils::vec_utils;
7
use utils::LinkedHashMap;
8
use utils::LinkedHashSet;
9

qinsoon's avatar
qinsoon committed
10
use std::fmt;
11
use std::default;
12
use std::sync::RwLock;
qinsoon's avatar
qinsoon committed
13
use std::sync::atomic::{AtomicUsize, ATOMIC_USIZE_INIT, Ordering};
qinsoon's avatar
qinsoon committed
14

15 16
pub type WPID  = usize;
pub type MuID  = usize;
17
pub type MuName = String;
18
pub type CName  = MuName;
qinsoon's avatar
qinsoon committed
19

20 21
#[allow(non_snake_case)]
pub fn Mu(str: &'static str) -> MuName {str.to_string()}
qinsoon's avatar
qinsoon committed
22 23
#[allow(non_snake_case)]
pub fn C(str: &'static str) -> CName {str.to_string()}
24

25 26
pub type OpIndex = usize;

qinsoon's avatar
qinsoon committed
27 28 29
lazy_static! {
    pub static ref MACHINE_ID : AtomicUsize = {
        let a = ATOMIC_USIZE_INIT;
30
        a.store(MACHINE_ID_START, Ordering::SeqCst);
qinsoon's avatar
qinsoon committed
31 32 33 34
        a
    };
    pub static ref INTERNAL_ID : AtomicUsize = {
        let a = ATOMIC_USIZE_INIT;
35
        a.store(INTERNAL_ID_START, Ordering::SeqCst);
qinsoon's avatar
qinsoon committed
36 37
        a
    };
38 39 40
} 
pub const  MACHINE_ID_START : usize = 0;
pub const  MACHINE_ID_END   : usize = 200;
qinsoon's avatar
qinsoon committed
41

42 43 44
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
45

qinsoon's avatar
qinsoon committed
46 47 48 49 50
#[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
51 52
pub fn new_machine_id() -> MuID {
    let ret = MACHINE_ID.fetch_add(1, Ordering::SeqCst);
53
    if ret >= MACHINE_ID_END {
qinsoon's avatar
qinsoon committed
54 55
        panic!("machine id overflow")
    }
56
    ret
qinsoon's avatar
qinsoon committed
57 58 59 60
}

pub fn new_internal_id() -> MuID {
    let ret = INTERNAL_ID.fetch_add(1, Ordering::SeqCst);
61
    if ret >= INTERNAL_ID_END {
qinsoon's avatar
qinsoon committed
62 63
        panic!("internal id overflow")
    }
64
    ret
qinsoon's avatar
qinsoon committed
65
}
qinsoon's avatar
qinsoon committed
66

qinsoon's avatar
qinsoon committed
67
#[derive(Debug, RustcEncodable, RustcDecodable)]
68
pub struct MuFunction {
69
    pub hdr: MuEntityHeader,
qinsoon's avatar
qinsoon committed
70
    
71
    pub sig: P<MuFuncSig>,
qinsoon's avatar
qinsoon committed
72 73
    pub cur_ver: Option<MuID>,
    pub all_vers: Vec<MuID>
74 75 76
}

impl MuFunction {
qinsoon's avatar
qinsoon committed
77
    pub fn new(id: MuID, sig: P<MuFuncSig>) -> MuFunction {
78
        MuFunction {
79
            hdr: MuEntityHeader::unnamed(id),
80 81 82 83 84
            sig: sig,
            cur_ver: None,
            all_vers: vec![]
        }
    }
85 86 87 88 89 90 91 92 93
    
    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);
    }
94 95
}

qinsoon's avatar
qinsoon committed
96 97
impl fmt::Display for MuFunction {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
98
        write!(f, "Func {}", self.hdr)
qinsoon's avatar
qinsoon committed
99 100 101
    }
}

102
#[derive(RustcEncodable, RustcDecodable)]
103
pub struct MuFunctionVersion {
104
    pub hdr: MuEntityHeader,
qinsoon's avatar
qinsoon committed
105 106
         
    pub func_id: MuID,
qinsoon's avatar
qinsoon committed
107
    pub sig: P<MuFuncSig>,
108

qinsoon's avatar
[wip]  
qinsoon committed
109
    orig_content: Option<FunctionContent>,
110
    pub content: Option<FunctionContent>,
111
    is_defined: bool,
qinsoon's avatar
qinsoon committed
112
    is_compiled: bool,
113

114
    pub context: FunctionContext,
115

116 117
    pub force_inline: bool,

qinsoon's avatar
qinsoon committed
118 119 120 121 122
    pub block_trace: Option<Vec<MuID>> // only available after Trace Generation Pass
}

impl fmt::Display for MuFunctionVersion {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
123
        write!(f, "FuncVer {} of Func #{}", self.hdr, self.func_id)
qinsoon's avatar
qinsoon committed
124
    }
125 126
}

127 128 129 130 131 132 133 134 135 136 137
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() {
138
            write!(f, "Block Trace: {:?}\n", self.block_trace.as_ref().unwrap())
139 140 141 142 143 144
        } else {
            write!(f, "Trace not available\n")
        }
    }
}

145
impl MuFunctionVersion {
qinsoon's avatar
qinsoon committed
146
    pub fn new(id: MuID, func: MuID, sig: P<MuFuncSig>) -> MuFunctionVersion {
147
        MuFunctionVersion{
148
            hdr: MuEntityHeader::unnamed(id),
qinsoon's avatar
qinsoon committed
149
            func_id: func,
150
            sig: sig,
151
            orig_content: None,
152
            content: None,
153
            is_defined: false,
qinsoon's avatar
qinsoon committed
154
            is_compiled: false,
155
            context: FunctionContext::new(),
156 157
            block_trace: None,
            force_inline: false
qinsoon's avatar
qinsoon committed
158
        }
159
    }
160

qinsoon's avatar
[wip]  
qinsoon committed
161 162 163 164 165 166 167
    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),
168
            is_defined: true,
qinsoon's avatar
qinsoon committed
169
            is_compiled: false,
qinsoon's avatar
[wip]  
qinsoon committed
170 171 172 173 174 175 176 177 178 179
            context: context,
            block_trace: None,
            force_inline: false
        }
    }

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

180
    pub fn define(&mut self, content: FunctionContent) {
181 182 183 184 185
        if self.is_defined {
            panic!("alread defined the function: {}", self);
        }

        self.is_defined = true;
186
        self.orig_content = Some(content.clone());
qinsoon's avatar
qinsoon committed
187
        self.content = Some(content);
188
    }
189

qinsoon's avatar
qinsoon committed
190 191 192 193 194 195 196
    pub fn is_compiled(&self) -> bool {
        self.is_compiled
    }
    pub fn set_compiled(&mut self) {
        self.is_compiled = true;
    }

qinsoon's avatar
qinsoon committed
197
    pub fn new_ssa(&mut self, id: MuID, ty: P<MuType>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
198 199 200 201 202 203 204
        let val = P(Value{
            hdr: MuEntityHeader::unnamed(id),
            ty: ty,
            v: Value_::SSAVar(id)
        });

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

206
        P(TreeNode {
qinsoon's avatar
qinsoon committed
207 208
            op: pick_op_code_for_ssa(&val.ty),
            v: TreeNode_::Value(val)
209 210
        })
    }
211

qinsoon's avatar
qinsoon committed
212
    pub fn new_constant(&mut self, v: P<Value>) -> P<TreeNode> {
213
        P(TreeNode{
qinsoon's avatar
qinsoon committed
214 215 216 217 218
            op: pick_op_code_for_value(&v.ty),
            v: TreeNode_::Value(v)
        })
    }
    
qinsoon's avatar
qinsoon committed
219
    pub fn new_global(&mut self, v: P<Value>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
220 221
        P(TreeNode{
            op: pick_op_code_for_value(&v.ty),
qinsoon's avatar
qinsoon committed
222 223
            v: TreeNode_::Value(v)
        })
224
    }
225

qinsoon's avatar
qinsoon committed
226
    pub fn new_inst(&mut self, v: Instruction) -> Box<TreeNode> {
qinsoon's avatar
qinsoon committed
227
        Box::new(TreeNode{
228
            op: pick_op_code_for_inst(&v),
229 230
            v: TreeNode_::Instruction(v),
        })
231
    }
qinsoon's avatar
qinsoon committed
232 233

    /// get Map(CallSiteID -> FuncID) that are called by this function
234 235
    pub fn get_static_call_edges(&self) -> LinkedHashMap<MuID, MuID> {
        let mut ret = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
236 237 238

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

qinsoon's avatar
qinsoon committed
239
        for (_, block) in f_content.blocks.iter() {
qinsoon's avatar
qinsoon committed
240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279
            let block_content = block.content.as_ref().unwrap();

            for inst in block_content.body.iter() {
                match inst.v {
                    TreeNode_::Instruction(ref inst) => {
                        let ops = inst.ops.read().unwrap();

                        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
280
        for (_, block) in f_content.blocks.iter() {
qinsoon's avatar
qinsoon committed
281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301
            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
    }
302 303
}

304
#[derive(Clone, RustcEncodable, RustcDecodable)]
305
pub struct FunctionContent {
qinsoon's avatar
qinsoon committed
306
    pub entry: MuID,
307 308 309 310
    pub blocks: LinkedHashMap<MuID, Block>,

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

313 314 315
impl fmt::Debug for FunctionContent {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let entry = self.get_entry_block();
316
        write!(f, "Entry block: ").unwrap();
317
        write!(f, "{:?}\n", entry).unwrap();
318 319

        write!(f, "Body:").unwrap();
320 321 322 323 324 325 326 327
        for blk_id in self.blocks.keys() {
            let block = self.get_block(*blk_id);
            write!(f, "{:?}\n", block).unwrap();
        }
        Ok(())
    }
}

328 329
impl FunctionContent {
    pub fn new(entry: MuID, blocks: LinkedHashMap<MuID, Block>) -> FunctionContent {
qinsoon's avatar
[wip]  
qinsoon committed
330
        FunctionContent {
331 332 333
            entry: entry,
            blocks: blocks,
            exception_blocks: LinkedHashSet::new()
qinsoon's avatar
[wip]  
qinsoon committed
334 335 336
        }
    }

337
    pub fn get_entry_block(&self) -> &Block {
qinsoon's avatar
qinsoon committed
338
        self.get_block(self.entry)
qinsoon's avatar
qinsoon committed
339
    } 
340

341
    pub fn get_entry_block_mut(&mut self) -> &mut Block {
qinsoon's avatar
qinsoon committed
342 343
        let entry = self.entry;
        self.get_block_mut(entry)
344
    }
345

qinsoon's avatar
qinsoon committed
346 347
    pub fn get_block(&self, id: MuID) -> &Block {
        let ret = self.blocks.get(&id);
qinsoon's avatar
qinsoon committed
348 349
        match ret {
            Some(b) => b,
qinsoon's avatar
qinsoon committed
350
            None => panic!("cannot find block #{}", id)
qinsoon's avatar
qinsoon committed
351
        }
352
    }
353

qinsoon's avatar
qinsoon committed
354 355
    pub fn get_block_mut(&mut self, id: MuID) -> &mut Block {
        let ret = self.blocks.get_mut(&id);
qinsoon's avatar
qinsoon committed
356 357
        match ret {
            Some(b) => b,
qinsoon's avatar
qinsoon committed
358
            None => panic!("cannot find block #{}", id)
qinsoon's avatar
qinsoon committed
359
        }
360
    }
361 362
}

363
#[derive(Default, Debug, RustcEncodable, RustcDecodable)]
364
pub struct FunctionContext {
365
    pub values: LinkedHashMap<MuID, SSAVarEntry>
366 367 368 369 370
}

impl FunctionContext {
    fn new() -> FunctionContext {
        FunctionContext {
371
            values: LinkedHashMap::new()
372 373
        }
    }
374 375
    
    pub fn make_temporary(&mut self, id: MuID, ty: P<MuType>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
376 377 378 379 380 381 382
        let val = P(Value{
            hdr: MuEntityHeader::unnamed(id),
            ty: ty,
            v: Value_::SSAVar(id)
        });

        self.values.insert(id, SSAVarEntry::new(val.clone()));
383 384

        P(TreeNode {
qinsoon's avatar
qinsoon committed
385 386
            op: pick_op_code_for_ssa(&val.ty),
            v: TreeNode_::Value(val)
387
        })
qinsoon's avatar
qinsoon committed
388 389 390 391 392 393 394 395
    }

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

397
    pub fn get_value(&self, id: MuID) -> Option<&SSAVarEntry> {
398 399
        self.values.get(&id)
    }
400

401
    pub fn get_value_mut(&mut self, id: MuID) -> Option<&mut SSAVarEntry> {
402 403 404 405
        self.values.get_mut(&id)
    }
}

qinsoon's avatar
qinsoon committed
406
#[derive(RustcEncodable, RustcDecodable, Clone)]
407
pub struct Block {
408
    pub hdr: MuEntityHeader,
409 410
    pub content: Option<BlockContent>,
    pub control_flow: ControlFlow
qinsoon's avatar
qinsoon committed
411 412
}

413 414 415 416 417 418 419 420 421 422 423 424 425 426
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(())
    }
}

427
impl Block {
qinsoon's avatar
qinsoon committed
428
    pub fn new(id: MuID) -> Block {
429
        Block{hdr: MuEntityHeader::unnamed(id), content: None, control_flow: ControlFlow::default()}
430
    }
qinsoon's avatar
qinsoon committed
431
    
432
    pub fn is_receiving_exception_arg(&self) -> bool {
qinsoon's avatar
qinsoon committed
433 434
        return self.content.as_ref().unwrap().exn_arg.is_some()
    }
qinsoon's avatar
qinsoon committed
435 436 437 438 439 440 441 442 443 444

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

            content.body.len()
        }
    }
445 446
}

qinsoon's avatar
qinsoon committed
447
#[derive(Debug, RustcEncodable, RustcDecodable, Clone)]
448
pub struct ControlFlow {
qinsoon's avatar
qinsoon committed
449
    pub preds : Vec<MuID>,
450 451 452
    pub succs : Vec<BlockEdge>
}

453
impl ControlFlow {
qinsoon's avatar
qinsoon committed
454
    pub fn get_hottest_succ(&self) -> Option<MuID> {
455 456 457 458 459
        if self.succs.len() == 0 {
            None
        } else {
            let mut hot_blk = self.succs[0].target;
            let mut hot_prob = self.succs[0].probability;
460

461 462 463 464 465 466
            for edge in self.succs.iter() {
                if edge.probability > hot_prob {
                    hot_blk = edge.target;
                    hot_prob = edge.probability;
                }
            }
467

468 469 470 471 472
            Some(hot_blk)
        }
    }
}

473 474
impl fmt::Display for ControlFlow {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
475 476
        write!(f, "preds: [{}], ", vec_utils::as_str(&self.preds)).unwrap();
        write!(f, "succs: [{}]", vec_utils::as_str(&self.succs))
477 478 479 480 481 482 483 484 485
    }
}

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

qinsoon's avatar
qinsoon committed
486
#[derive(Copy, Clone, Debug, RustcEncodable, RustcDecodable)]
487
pub struct BlockEdge {
qinsoon's avatar
qinsoon committed
488
    pub target: MuID,
489 490 491 492 493 494 495 496 497 498 499
    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)
    }
}

qinsoon's avatar
qinsoon committed
500
#[derive(Copy, Clone, Debug, RustcEncodable, RustcDecodable)]
501 502 503 504
pub enum EdgeKind {
    Forward, Backward
}

qinsoon's avatar
qinsoon committed
505
#[derive(RustcEncodable, RustcDecodable, Clone)]
506
pub struct BlockContent {
507
    pub args: Vec<P<Value>>,
508
    pub exn_arg: Option<P<Value>>,
qinsoon's avatar
qinsoon committed
509
    pub body: Vec<Box<TreeNode>>,
510
    pub keepalives: Option<Vec<P<Value>>>
511 512
}

513 514
impl fmt::Debug for BlockContent {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
515 516 517 518 519 520 521
        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();
        }
522 523 524 525 526 527 528
        for node in self.body.iter() {
            writeln!(f, "{}", node).unwrap();
        }
        Ok(())
    }
}

529 530 531 532 533 534 535 536 537
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) => {
qinsoon's avatar
qinsoon committed
538
                let ops = inst.ops.read().unwrap();
539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573
                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
574
                    | Instruction_::CCall{ref resume, ..}
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
                    | 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);
                    }
                    
                    _ => panic!("didn't expect last inst as {:?}", inst) 
                }
            },
            _ => panic!("expect last treenode of block is a inst")
        }
        
        ret
    }
}

qinsoon's avatar
qinsoon committed
601
#[derive(Debug, RustcEncodable, RustcDecodable, Clone)]
qinsoon's avatar
qinsoon committed
602 603
/// always use with P<TreeNode>
pub struct TreeNode {
604 605
    pub op: OpCode,
    pub v: TreeNode_,
qinsoon's avatar
qinsoon committed
606 607
}

608
impl TreeNode {
609
    // this is a hack to allow creating TreeNode without using a &mut MuFunctionVersion
qinsoon's avatar
qinsoon committed
610
    pub fn new_inst(v: Instruction) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
611
        P(TreeNode{
612
            op: pick_op_code_for_inst(&v),
qinsoon's avatar
qinsoon committed
613 614
            v: TreeNode_::Instruction(v),
        })
615 616
    }

qinsoon's avatar
qinsoon committed
617 618 619 620 621 622 623
    pub fn new_boxed_inst(v: Instruction) -> Box<TreeNode> {
        Box::new(TreeNode{
            op: pick_op_code_for_inst(&v),
            v: TreeNode_::Instruction(v),
        })
    }

624 625 626 627 628 629 630 631 632 633 634
    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
        }
    }
635

qinsoon's avatar
qinsoon committed
636
    pub fn clone_value(&self) -> P<Value> {
qinsoon's avatar
qinsoon committed
637
        match self.v {
qinsoon's avatar
qinsoon committed
638
            TreeNode_::Value(ref val) => val.clone(),
639 640 641 642 643 644 645
            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
646
        }
647 648
    }

qinsoon's avatar
qinsoon committed
649 650 651
    pub fn into_value(self) -> Option<P<Value>> {
        match self.v {
            TreeNode_::Value(val) => Some(val),
652
            _ => None
qinsoon's avatar
qinsoon committed
653 654
        }
    }
qinsoon's avatar
qinsoon committed
655 656 657 658 659 660 661

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

664 665
/// use +() to display a node
impl fmt::Display for TreeNode {
qinsoon's avatar
qinsoon committed
666
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
667
        match self.v {
qinsoon's avatar
qinsoon committed
668
            TreeNode_::Value(ref pv) => pv.fmt(f),
669
            TreeNode_::Instruction(ref inst) => {
670
                write!(f, "+({})", inst)
671
            }
qinsoon's avatar
qinsoon committed
672
        }
qinsoon's avatar
qinsoon committed
673
    }
qinsoon's avatar
qinsoon committed
674 675
}

qinsoon's avatar
qinsoon committed
676
#[derive(Debug, RustcEncodable, RustcDecodable, Clone)]
qinsoon's avatar
qinsoon committed
677
pub enum TreeNode_ {
qinsoon's avatar
qinsoon committed
678
    Value(P<Value>),
679
    Instruction(Instruction)
qinsoon's avatar
qinsoon committed
680 681 682
}

/// always use with P<Value>
qinsoon's avatar
qinsoon committed
683
#[derive(PartialEq, RustcEncodable, RustcDecodable)]
qinsoon's avatar
qinsoon committed
684
pub struct Value {
685
    pub hdr: MuEntityHeader,
qinsoon's avatar
qinsoon committed
686 687
    pub ty: P<MuType>,
    pub v: Value_
qinsoon's avatar
qinsoon committed
688 689
}

690
impl Value {
qinsoon's avatar
qinsoon committed
691 692 693 694 695 696 697 698
    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))
        })
    }
    
699 700 701 702 703 704 705
    pub fn is_mem(&self) -> bool {
        match self.v {
            Value_::Memory(_) => true,
            _ => false
        }
    }
    
706 707 708 709 710 711 712 713 714 715 716 717
    pub fn is_int_reg(&self) -> bool {
        match self.v {
            Value_::SSAVar(_) => {
                if is_scalar(&self.ty) && !is_fp(&self.ty) {
                    true
                } else {
                    false
                }
            }
            _ => false
        }
    }
718

qinsoon's avatar
qinsoon committed
719 720 721 722 723 724 725 726
    pub unsafe fn as_type(&self, ty: P<MuType>) -> P<Value> {
        P(Value{
            hdr: self.hdr.clone(),
            ty: ty,
            v: self.v.clone()
        })
    }

727 728 729 730 731 732 733 734 735
    pub fn is_fp_reg(&self) -> bool {
        match self.v {
            Value_::SSAVar(_) => {
                if is_scalar(&self.ty) && is_fp(&self.ty) {
                    true
                } else {
                    false
                }
            },
qinsoon's avatar
qinsoon committed
736 737
            Value_::Constant(Constant::Double(_)) => true,
            Value_::Constant(Constant::Float(_))  => true,
738 739 740
            _ => false
        }
    }
741

742 743
    pub fn is_int_const(&self) -> bool {
        match self.v {
744 745
            Value_::Constant(Constant::Int(_)) => true,
            Value_::Constant(Constant::NullRef) => true,
746 747
            _ => false
        }
qinsoon's avatar
qinsoon committed
748
    }
749 750 751
    
    pub fn extract_int_const(&self) -> u64 {
        match self.v {
752 753
            Value_::Constant(Constant::Int(val)) => val,
            Value_::Constant(Constant::NullRef)  => 0,
754 755 756
            _ => panic!("expect int const")
        }
    }
757

qinsoon's avatar
qinsoon committed
758 759 760 761 762 763 764 765
    pub fn extract_ssa_id(&self) -> Option<MuID> {
        match self.v {
            Value_::SSAVar(id) => Some(id),
            _ => None
        }
    }
}

766
const DISPLAY_TYPE : bool = false;
767
const PRINT_ABBREVIATE_NAME: bool = true;
768

qinsoon's avatar
qinsoon committed
769 770 771 772 773 774
impl fmt::Debug for Value {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", self)
    }
}

qinsoon's avatar
qinsoon committed
775 776
impl fmt::Display for Value {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797
        if DISPLAY_TYPE {
            match self.v {
                Value_::SSAVar(_) => {
                    write!(f, "+({} %{})", self.ty, self.hdr)
                },
                Value_::Constant(ref c) => {
                    write!(f, "+({} {} @{})", self.ty, c, self.hdr)
                },
                Value_::Global(ref ty) => {
                    write!(f, "+(GLOBAL {} @{})", ty, self.hdr)
                },
                Value_::Memory(ref mem) => {
                    write!(f, "+(MEM {} %{})", mem, self.hdr)
                }
            }
        } else {
            match self.v {
                Value_::SSAVar(_) => {
                    write!(f, "%{}", self.hdr)
                },
                Value_::Constant(ref c) => {
qinsoon's avatar
qinsoon committed
798
                    write!(f, "{}", c)
799 800 801 802 803 804 805
                },
                Value_::Global(_) => {
                    write!(f, "GLOBAL @{}", self.hdr)
                },
                Value_::Memory(ref mem) => {
                    write!(f, "MEM {} %{}", mem, self.hdr)
                }
qinsoon's avatar
qinsoon committed
806 807 808
            }
        }
    }
809 810
}

qinsoon's avatar
qinsoon committed
811
#[derive(Debug, Clone, PartialEq, RustcEncodable, RustcDecodable)]
qinsoon's avatar
qinsoon committed
812
pub enum Value_ {
813
    SSAVar(MuID),
qinsoon's avatar
qinsoon committed
814
    Constant(Constant),
815
    Global(P<MuType>), // what type is this global (without IRef)
816
    Memory(MemoryLocation)
qinsoon's avatar
qinsoon committed
817 818
}

qinsoon's avatar
qinsoon committed
819
#[derive(Debug)]
820
pub struct SSAVarEntry {
qinsoon's avatar
qinsoon committed
821
    val: P<Value>,
822

823 824
    // how many times this entry is used
    // availalbe after DefUse pass
qinsoon's avatar
qinsoon committed
825
    use_count: AtomicUsize,
826

827
    // this field is only used during TreeGeneration pass
qinsoon's avatar
qinsoon committed
828
    expr: Option<Instruction>
829 830
}

qinsoon's avatar
qinsoon committed
831 832
impl Encodable for SSAVarEntry {
    fn encode<S: Encoder> (&self, s: &mut S) -> Result<(), S::Error> {
qinsoon's avatar
qinsoon committed
833 834
        s.emit_struct("SSAVarEntry", 3, |s| {
            try!(s.emit_struct_field("val", 0, |s| self.val.encode(s)));
qinsoon's avatar
qinsoon committed
835
            let count = self.use_count.load(Ordering::SeqCst);
qinsoon's avatar
qinsoon committed
836 837
            try!(s.emit_struct_field("use_count", 1, |s| s.emit_usize(count)));
            try!(s.emit_struct_field("expr", 2, |s| self.expr.encode(s)));
qinsoon's avatar
qinsoon committed
838 839 840 841 842 843 844
            Ok(())
        })
    }
}

impl Decodable for SSAVarEntry {
    fn decode<D: Decoder>(d: &mut D) -> Result<SSAVarEntry, D::Error> {
qinsoon's avatar
qinsoon committed
845 846 847 848
        d.read_struct("SSAVarEntry", 3, |d| {
            let val = try!(d.read_struct_field("val", 0, |d| Decodable::decode(d)));
            let count = try!(d.read_struct_field("use_count", 1, |d| d.read_usize()));
            let expr = try!(d.read_struct_field("expr", 2, |d| Decodable::decode(d)));
qinsoon's avatar
qinsoon committed
849 850
            
            let ret = SSAVarEntry {
qinsoon's avatar
qinsoon committed
851
                val: val,
qinsoon's avatar
qinsoon committed
852 853 854 855 856 857 858 859 860 861 862
                use_count: ATOMIC_USIZE_INIT,
                expr: expr
            };
            
            ret.use_count.store(count, Ordering::SeqCst);
            
            Ok(ret)
        })
    }
}

863
impl SSAVarEntry {
qinsoon's avatar
qinsoon committed
864
    pub fn new(val: P<Value>) -> SSAVarEntry {
qinsoon's avatar
qinsoon committed
865
        let ret = SSAVarEntry {
qinsoon's avatar
qinsoon committed
866
            val: val,
qinsoon's avatar
qinsoon committed
867 868 869 870 871 872 873 874
            use_count: ATOMIC_USIZE_INIT,
            expr: None
        };
        
        ret.use_count.store(0, Ordering::SeqCst);
        
        ret
    }
qinsoon's avatar
qinsoon committed
875 876 877 878 879 880 881 882 883 884 885 886 887 888 889

    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);
    }
890 891 892
    pub fn reset_use_count(&self) {
        self.use_count.store(0, Ordering::SeqCst);
    }
qinsoon's avatar
qinsoon committed
893 894 895 896

    pub fn has_expr(&self) -> bool {
        self.expr.is_some()
    }
897 898 899
    pub fn assign_expr(&mut self, expr: Instruction) {
        self.expr = Some(expr)
    }
qinsoon's avatar
qinsoon committed
900 901 902 903
    pub fn take_expr(&mut self) -> Instruction {
        debug_assert!(self.has_expr());
        self.expr.take().unwrap()
    }
904 905
}

906
impl fmt::Display for SSAVarEntry {
907
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
908
        write!(f, "{}", self.val)
909 910 911
    }
}

qinsoon's avatar
qinsoon committed
912
#[derive(Debug, Clone, PartialEq, RustcEncodable, RustcDecodable)]
913
pub enum Constant {
qinsoon's avatar
qinsoon committed
914
    Int(u64),
915 916
    Float(f32),
    Double(f64),
qinsoon's avatar
qinsoon committed
917
//    IRef(Address),
qinsoon's avatar
qinsoon committed
918
    FuncRef(MuID),
919
    Vector(Vec<Constant>),
920 921
    //Pointer(Address),
    NullRef,
922 923 924
    ExternSym(CName),

    List(Vec<P<Value>>) // a composite type of several constants
925 926
}

927
impl fmt::Display for Constant {
928 929
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
qinsoon's avatar
qinsoon committed
930
            &Constant::Int(v) => write!(f, "{}", v as i64),
931 932
            &Constant::Float(v) => write!(f, "{}", v),
            &Constant::Double(v) => write!(f, "{}", v),
qinsoon's avatar
qinsoon committed
933
//            &Constant::IRef(v) => write!(f, "{}", v),
934
            &Constant::FuncRef(v) => write!(f, "FuncRef {}", v),
935 936 937 938 939 940 941 942 943 944
            &Constant::Vector(ref v) => {
                write!(f, "[").unwrap();
                for i in 0..v.len() {
                    write!(f, "{}", v[i]).unwrap();
                    if i != v.len() - 1 {
                        write!(f, ", ").unwrap();
                    }
                }
                write!(f, "]")
            }
945
            &Constant::NullRef => write!(f, "NullRef"),
946 947 948 949 950 951 952 953 954
            &Constant::ExternSym(ref name) => write!(f, "ExternSym({})", name),

            &Constant::List(ref vec) => {
                write!(f, "List(").unwrap();
                for val in vec.iter() {
                    write!(f, "{}, ", val).unwrap();
                }
                write!(f, ")")
            }
955 956
        }
    }
qinsoon's avatar
qinsoon committed
957 958
}

qinsoon's avatar
qinsoon committed
959
#[derive(Debug, Clone, PartialEq, RustcEncodable, RustcDecodable)]
960 961 962 963 964 965 966 967 968
pub enum MemoryLocation {
    Address{
        base: P<Value>,
        offset: Option<P<Value>>,
        index: Option<P<Value>>,
        scale: Option<u8>
    },
    Symbolic{
        base: Option<P<Value>>,
969 970
        label: MuName,
        is_global: bool
971 972 973 974 975 976 977
    }
}

impl fmt::Display for MemoryLocation {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            &MemoryLocation::Address{ref base, ref offset, ref index, scale} => {
qinsoon's avatar
qinsoon committed
978 979 980 981 982 983 984 985 986 987 988
                // base
                write!(f, "[{}", base).unwrap();
                // offset
                if offset.is_some() {
                    write!(f, " + {}", offset.as_ref().unwrap()).unwrap();
                }
                // index/scale
                if index.is_some() && scale.is_some() {
                    write!(f, " + {} * {}", index.as_ref().unwrap(), scale.unwrap()).unwrap();
                }
                write!(f, "]")
989
            }
990
            &MemoryLocation::Symbolic{ref base, ref label, ..} => {
991
                if base.is_some() {
992
                    write!(f, "{}({})", label, base.as_ref().unwrap())
993 994 995 996 997 998 999 1000
                } else {
                    write!(f, "{}", label)
                }
            }
        }
    }
}

1001
#[repr(C)]
qinsoon's avatar
qinsoon committed
1002
#[derive(Debug)] // Display, PartialEq, Clone
1003
pub struct MuEntityHeader {
1004 1005
    id: MuID,
    name: RwLock<Option<MuName>>
1006 1007
}

qinsoon's avatar
qinsoon committed
1008 1009 1010 1011 1012 1013 1014 1015 1016
impl Clone for MuEntityHeader {
    fn clone(&self) -> Self {
        MuEntityHeader {
            id: self.id,
            name: RwLock::new(self.name.read().unwrap().clone())
        }
    }
}

1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037
use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
impl Encodable for MuEntityHeader {
    fn encode<S: Encoder> (&self, s: &mut S) -> Result<(), S::Error> {
        s.emit_struct("MuEntityHeader", 2, |s| {
            try!(s.emit_struct_field("id", 0, |s| self.id.encode(s)));
            
            let name = &self.name.read().unwrap();
            try!(s.emit_struct_field("name", 1, |s| name.encode(s)));
            
            Ok(())
        })
    }
}

impl Decodable for MuEntityHeader {
    fn decode<D: Decoder>(d: &mut D) -> Result<MuEntityHeader, D::Error> {
        d.read_struct("MuEntityHeader", 2, |d| {
            let id = try!(d.read_struct_field("id", 0, |d| {d.read_usize()}));
            let name = try!(d.read_struct_field("name", 1, |d| Decodable::decode(d)));
            
            Ok(MuEntityHeader{
1038
                    id: id,
1039 1040 1041 1042 1043 1044
                    name: RwLock::new(name)
                })
        })
    }
}

1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055
impl MuEntityHeader {
    pub fn unnamed(id: MuID) -> MuEntityHeader {
        MuEntityHeader {
            id: id,
            name: RwLock::new(None)
        }
    }
    
    pub fn named(id: MuID, name: MuName) -> MuEntityHeader {
        MuEntityHeader {
            id: id,
1056
            name: RwLock::new(Some(MuEntityHeader::name_check(name)))
1057 1058 1059 1060 1061 1062 1063 1064
        }
    }
    
    pub fn id(&self) -> MuID {
        self.id
    }
    
    pub fn name(&self) -> Option<MuName> {
1065
        self.name.read().unwrap().clone()
1066
    }
1067 1068 1069 1070 1071 1072

    pub fn set_name(&self, name: MuName) {
        let mut name_guard = self.name.write().unwrap();
        *name_guard = Some(MuEntityHeader::name_check(name));
    }

1073
    pub fn name_check(name: MuName) -> MuName {
1074 1075
        let name = name.replace('.', "$");

1076 1077 1078 1079 1080 1081 1082 1083
        if name.starts_with("@") || name.starts_with("%") {
            let (_, name) = name.split_at(1);

            return name.to_string();
        }

        name
    }
1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106

    fn abbreviate_name(&self) -> Option<MuName> {
        match self.name() {
            Some(name) => {
                let split: Vec<&str> = name.split('$').collect();

                let mut ret = "".to_string();

                for i in 0..split.len() - 1 {
                    ret.push(match split[i].chars().next() {
                        Some(c) => c,
                        None => '_'
                    });
                    ret.push('.');
                }

                ret.push_str(split.last().unwrap());

                Some(ret)
            }
            None => None
        }
    }
1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117
}

impl PartialEq for MuEntityHeader {
    fn eq(&self, other: &Self) -> bool {
        self.id == other.id
    }
}

impl fmt::Display for MuEntityHeader {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        if self.name().is_none() {
qinsoon's avatar
qinsoon committed
1118
            write!(f, "UNNAMED #{}", self.id)
1119
        } else {
1120
            if PRINT_ABBREVIATE_NAME {
1121
                write!(f, "{} #{}", self.abbreviate_name().unwrap(), self.id)
1122 1123 1124
            } else {
                write!(f, "{} #{}", self.name().unwrap(), self.id)
            }
1125 1126 1127 1128
        }
    }
}

qinsoon's avatar
qinsoon committed
1129 1130 1131
pub trait MuEntity {
    fn id(&self) -> MuID;
    fn name(&self) -> Option<MuName>;
1132
    fn set_name(&self, name: MuName);
qinsoon's avatar
qinsoon committed
1133 1134 1135 1136 1137 1138 1139 1140 1141 1142
    fn as_entity(&self) -> &MuEntity;
}

impl_mu_entity!(MuFunction);
impl_mu_entity!(MuFunctionVersion);
impl_mu_entity!(Block);
impl_mu_entity!(MuType);
impl_mu_entity!(Value);
impl_mu_entity!(MuFuncSig);

qinsoon's avatar
qinsoon committed
1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172
impl MuEntity for TreeNode {
    fn id(&self) -> MuID {
        match self.v {
            TreeNode_::Instruction(ref inst) => inst.id(),
            TreeNode_::Value(ref pv) => pv.id()
        }
    }

    fn name(&self) -> Option<MuName> {
        match self.v {
            TreeNode_::Instruction(ref inst) => inst.name(),
            TreeNode_::Value(ref pv) => pv.name()
        }
    }

    fn set_name(&self, name: MuName) {
        match self.v {
            TreeNode_::Instruction(ref inst) => inst.set_name(name),
            TreeNode_::Value(ref pv) => pv.set_name(name)
        }
    }

    fn as_entity(&self) -> &MuEntity {
        match self.v {
            TreeNode_::Instruction(ref inst) => inst.as_entity(),
            TreeNode_::Value(ref pv) => pv.as_entity()
        }
    }
}

1173
pub fn op_vector_str(vec: &Vec<OpIndex>, ops: &Vec<P<TreeNode>>) -> String {
1174 1175 1176 1177 1178 1179
    let mut ret = String::new();
    for i in 0..vec.len() {
        let index = vec[i];
        ret.push_str(format!("{}", ops[index]).as_str());
        if i != vec.len() - 1 {
            ret.push_str(", ");
1180
        }
1181 1182
    }
    ret
1183
}