ir.rs 27.1 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::Address;
8

9
use std::collections::HashMap;
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

qinsoon's avatar
qinsoon committed
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 22
#[allow(non_snake_case)]
pub fn Mu(str: &'static str) -> MuName {str.to_string()}

23 24
pub type OpIndex = usize;

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

pub const  INTERNAL_ID_START: usize = 101;
pub const  INTERNAL_ID_END  : usize = 200;
pub const  USER_ID_START    : usize = 201;

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

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

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

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

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

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

qinsoon's avatar
qinsoon committed
109 110 111 112 113
    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 {
114
        write!(f, "FuncVer {} of Func #{}", self.hdr, self.func_id)
qinsoon's avatar
qinsoon committed
115
    }
116 117
}

118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135
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() {
            write!(f, "{:?}\n", self.block_trace.as_ref().unwrap())
        } else {
            write!(f, "Trace not available\n")
        }
    }
}

136
impl MuFunctionVersion {
qinsoon's avatar
qinsoon committed
137
    pub fn new(id: MuID, func: MuID, sig: P<MuFuncSig>) -> MuFunctionVersion {
138
        MuFunctionVersion{
139
            hdr: MuEntityHeader::unnamed(id),
qinsoon's avatar
qinsoon committed
140
            func_id: func,
141 142 143
            sig: sig,
            content: None,
            context: FunctionContext::new(),
qinsoon's avatar
qinsoon committed
144 145
            block_trace: None
        }
146
    }
147

148
    pub fn define(&mut self, content: FunctionContent) {
qinsoon's avatar
qinsoon committed
149
        self.content = Some(content);
150
    }
151

qinsoon's avatar
qinsoon committed
152
    pub fn new_ssa(&mut self, id: MuID, ty: P<MuType>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
153 154 155 156 157 158 159
        let val = P(Value{
            hdr: MuEntityHeader::unnamed(id),
            ty: ty,
            v: Value_::SSAVar(id)
        });

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

161
        P(TreeNode {
qinsoon's avatar
qinsoon committed
162 163
            op: pick_op_code_for_ssa(&val.ty),
            v: TreeNode_::Value(val)
164 165
        })
    }
166

qinsoon's avatar
qinsoon committed
167
    pub fn new_constant(&mut self, v: P<Value>) -> P<TreeNode> {
168
        P(TreeNode{
qinsoon's avatar
qinsoon committed
169 170 171 172 173
            op: pick_op_code_for_value(&v.ty),
            v: TreeNode_::Value(v)
        })
    }
    
qinsoon's avatar
qinsoon committed
174
    pub fn new_global(&mut self, v: P<Value>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
175 176
        P(TreeNode{
            op: pick_op_code_for_value(&v.ty),
qinsoon's avatar
qinsoon committed
177 178
            v: TreeNode_::Value(v)
        })
179
    }
180

qinsoon's avatar
qinsoon committed
181
    pub fn new_inst(&mut self, v: Instruction) -> Box<TreeNode> {
qinsoon's avatar
qinsoon committed
182
        Box::new(TreeNode{
183
            op: pick_op_code_for_inst(&v),
184 185
            v: TreeNode_::Instruction(v),
        })
186
    }
187 188
}

qinsoon's avatar
qinsoon committed
189
#[derive(RustcEncodable, RustcDecodable, Clone)]
190
pub struct FunctionContent {
qinsoon's avatar
qinsoon committed
191 192
    pub entry: MuID,
    pub blocks: HashMap<MuID, Block>
193 194
}

195 196 197
impl fmt::Debug for FunctionContent {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let entry = self.get_entry_block();
198
        write!(f, "Entry block: ").unwrap();
199
        write!(f, "{:?}\n", entry).unwrap();
200 201

        write!(f, "Body:").unwrap();
202 203 204 205 206 207 208 209
        for blk_id in self.blocks.keys() {
            let block = self.get_block(*blk_id);
            write!(f, "{:?}\n", block).unwrap();
        }
        Ok(())
    }
}

210 211
impl FunctionContent {
    pub fn get_entry_block(&self) -> &Block {
qinsoon's avatar
qinsoon committed
212
        self.get_block(self.entry)
qinsoon's avatar
qinsoon committed
213
    } 
214

215
    pub fn get_entry_block_mut(&mut self) -> &mut Block {
qinsoon's avatar
qinsoon committed
216 217
        let entry = self.entry;
        self.get_block_mut(entry)
218
    }
219

qinsoon's avatar
qinsoon committed
220 221
    pub fn get_block(&self, id: MuID) -> &Block {
        let ret = self.blocks.get(&id);
qinsoon's avatar
qinsoon committed
222 223
        match ret {
            Some(b) => b,
qinsoon's avatar
qinsoon committed
224
            None => panic!("cannot find block #{}", id)
qinsoon's avatar
qinsoon committed
225
        }
226
    }
227

qinsoon's avatar
qinsoon committed
228 229
    pub fn get_block_mut(&mut self, id: MuID) -> &mut Block {
        let ret = self.blocks.get_mut(&id);
qinsoon's avatar
qinsoon committed
230 231
        match ret {
            Some(b) => b,
qinsoon's avatar
qinsoon committed
232
            None => panic!("cannot find block #{}", id)
qinsoon's avatar
qinsoon committed
233
        }
234
    }
235 236
}

237
#[derive(Default, Debug, RustcEncodable, RustcDecodable)]
238
pub struct FunctionContext {
239
    pub values: HashMap<MuID, SSAVarEntry>
240 241 242 243 244 245 246 247
}

impl FunctionContext {
    fn new() -> FunctionContext {
        FunctionContext {
            values: HashMap::new()
        }
    }
248 249
    
    pub fn make_temporary(&mut self, id: MuID, ty: P<MuType>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
250 251 252 253 254 255 256
        let val = P(Value{
            hdr: MuEntityHeader::unnamed(id),
            ty: ty,
            v: Value_::SSAVar(id)
        });

        self.values.insert(id, SSAVarEntry::new(val.clone()));
257 258

        P(TreeNode {
qinsoon's avatar
qinsoon committed
259 260
            op: pick_op_code_for_ssa(&val.ty),
            v: TreeNode_::Value(val)
261
        })
qinsoon's avatar
qinsoon committed
262 263 264 265 266 267 268 269
    }

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

271
    pub fn get_value(&self, id: MuID) -> Option<&SSAVarEntry> {
272 273
        self.values.get(&id)
    }
274

275
    pub fn get_value_mut(&mut self, id: MuID) -> Option<&mut SSAVarEntry> {
276 277 278 279
        self.values.get_mut(&id)
    }
}

qinsoon's avatar
qinsoon committed
280
#[derive(RustcEncodable, RustcDecodable, Clone)]
281
pub struct Block {
282
    pub hdr: MuEntityHeader,
283 284
    pub content: Option<BlockContent>,
    pub control_flow: ControlFlow
qinsoon's avatar
qinsoon committed
285 286
}

287 288 289 290 291 292 293 294 295 296 297 298 299 300
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(())
    }
}

301
impl Block {
qinsoon's avatar
qinsoon committed
302
    pub fn new(id: MuID) -> Block {
303
        Block{hdr: MuEntityHeader::unnamed(id), content: None, control_flow: ControlFlow::default()}
304
    }
qinsoon's avatar
qinsoon committed
305 306 307 308
    
    pub fn is_exception_block(&self) -> bool {
        return self.content.as_ref().unwrap().exn_arg.is_some()
    }
309 310
}

qinsoon's avatar
qinsoon committed
311
#[derive(Debug, RustcEncodable, RustcDecodable, Clone)]
312
pub struct ControlFlow {
qinsoon's avatar
qinsoon committed
313
    pub preds : Vec<MuID>,
314 315 316
    pub succs : Vec<BlockEdge>
}

317
impl ControlFlow {
qinsoon's avatar
qinsoon committed
318
    pub fn get_hottest_succ(&self) -> Option<MuID> {
319 320 321 322 323
        if self.succs.len() == 0 {
            None
        } else {
            let mut hot_blk = self.succs[0].target;
            let mut hot_prob = self.succs[0].probability;
324

325 326 327 328 329 330
            for edge in self.succs.iter() {
                if edge.probability > hot_prob {
                    hot_blk = edge.target;
                    hot_prob = edge.probability;
                }
            }
331

332 333 334 335 336
            Some(hot_blk)
        }
    }
}

337 338
impl fmt::Display for ControlFlow {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
339 340
        write!(f, "preds: [{}], ", vec_utils::as_str(&self.preds)).unwrap();
        write!(f, "succs: [{}]", vec_utils::as_str(&self.succs))
341 342 343 344 345 346 347 348 349
    }
}

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

qinsoon's avatar
qinsoon committed
350
#[derive(Copy, Clone, Debug, RustcEncodable, RustcDecodable)]
351
pub struct BlockEdge {
qinsoon's avatar
qinsoon committed
352
    pub target: MuID,
353 354 355 356 357 358 359 360 361 362 363
    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
364
#[derive(Copy, Clone, Debug, RustcEncodable, RustcDecodable)]
365 366 367 368
pub enum EdgeKind {
    Forward, Backward
}

qinsoon's avatar
qinsoon committed
369
#[derive(RustcEncodable, RustcDecodable, Clone)]
370
pub struct BlockContent {
371
    pub args: Vec<P<Value>>,
372
    pub exn_arg: Option<P<Value>>,
qinsoon's avatar
qinsoon committed
373
    pub body: Vec<Box<TreeNode>>,
374
    pub keepalives: Option<Vec<P<Value>>>
375 376
}

377 378
impl fmt::Debug for BlockContent {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
379 380 381 382 383 384 385
        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();
        }
386 387 388 389 390 391 392
        for node in self.body.iter() {
            writeln!(f, "{}", node).unwrap();
        }
        Ok(())
    }
}

393 394 395 396 397 398 399 400 401
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
402
                let ops = inst.ops.read().unwrap();
403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463
                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, ..}
                    | 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
464
#[derive(Debug, RustcEncodable, RustcDecodable, Clone)]
qinsoon's avatar
qinsoon committed
465 466
/// always use with P<TreeNode>
pub struct TreeNode {
467 468
    pub op: OpCode,
    pub v: TreeNode_,
qinsoon's avatar
qinsoon committed
469 470
}

471
impl TreeNode {
472
    // this is a hack to allow creating TreeNode without using a &mut MuFunctionVersion
qinsoon's avatar
qinsoon committed
473
    pub fn new_inst(v: Instruction) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
474
        P(TreeNode{
475
            op: pick_op_code_for_inst(&v),
qinsoon's avatar
qinsoon committed
476 477
            v: TreeNode_::Instruction(v),
        })
478 479
    }

480 481 482 483 484 485 486 487 488 489 490
    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
        }
    }
491

qinsoon's avatar
qinsoon committed
492
    pub fn clone_value(&self) -> P<Value> {
qinsoon's avatar
qinsoon committed
493
        match self.v {
qinsoon's avatar
qinsoon committed
494
            TreeNode_::Value(ref val) => val.clone(),
495
            TreeNode_::Instruction(ref inst) => {
496
                warn!("expecting a value, but we found an inst. Instead we use its first value");
497 498 499 500 501 502
                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
503
        }
504 505
    }

qinsoon's avatar
qinsoon committed
506 507 508
    pub fn into_value(self) -> Option<P<Value>> {
        match self.v {
            TreeNode_::Value(val) => Some(val),
509
            _ => None
qinsoon's avatar
qinsoon committed
510 511
        }
    }
qinsoon's avatar
qinsoon committed
512 513
}

514 515
/// use +() to display a node
impl fmt::Display for TreeNode {
qinsoon's avatar
qinsoon committed
516
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
517
        match self.v {
qinsoon's avatar
qinsoon committed
518
            TreeNode_::Value(ref pv) => pv.fmt(f),
519
            TreeNode_::Instruction(ref inst) => {
520
                write!(f, "+({})", inst)
521
            }
qinsoon's avatar
qinsoon committed
522
        }
qinsoon's avatar
qinsoon committed
523
    }
qinsoon's avatar
qinsoon committed
524 525
}

qinsoon's avatar
qinsoon committed
526
#[derive(Debug, RustcEncodable, RustcDecodable, Clone)]
qinsoon's avatar
qinsoon committed
527
pub enum TreeNode_ {
qinsoon's avatar
qinsoon committed
528
    Value(P<Value>),
529
    Instruction(Instruction)
qinsoon's avatar
qinsoon committed
530 531 532
}

/// always use with P<Value>
qinsoon's avatar
qinsoon committed
533
#[derive(Debug, PartialEq, RustcEncodable, RustcDecodable)]
qinsoon's avatar
qinsoon committed
534
pub struct Value {
535
    pub hdr: MuEntityHeader,
qinsoon's avatar
qinsoon committed
536 537
    pub ty: P<MuType>,
    pub v: Value_
qinsoon's avatar
qinsoon committed
538 539
}

540
impl Value {
qinsoon's avatar
qinsoon committed
541 542 543 544 545 546 547 548
    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))
        })
    }
    
549 550 551 552 553 554 555
    pub fn is_mem(&self) -> bool {
        match self.v {
            Value_::Memory(_) => true,
            _ => false
        }
    }
    
556 557 558 559 560 561 562 563 564 565 566 567
    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
        }
    }
568

569 570 571 572 573 574 575 576 577 578 579 580
    pub fn is_fp_reg(&self) -> bool {
        match self.v {
            Value_::SSAVar(_) => {
                if is_scalar(&self.ty) && is_fp(&self.ty) {
                    true
                } else {
                    false
                }
            },
            _ => false
        }
    }
581

582 583 584
    pub fn is_int_const(&self) -> bool {
        match self.v {
            Value_::Constant(_) => {
qinsoon's avatar
qinsoon committed
585 586 587
                let ty : &MuType = &self.ty;
                match ty.v {
                    MuType_::Int(_) => true,
588 589 590 591 592
                    _ => false
                }
            }
            _ => false
        }
qinsoon's avatar
qinsoon committed
593
    }
594 595 596 597 598 599 600 601 602 603 604 605
    
    pub fn extract_int_const(&self) -> u64 {
        match self.v {
            Value_::Constant(ref c) => {
                match c {
                    &Constant::Int(val) => val,
                    _ => panic!("expect int const")
                }
            },
            _ => panic!("expect int const")
        }
    }
606

qinsoon's avatar
qinsoon committed
607 608 609 610 611 612 613 614 615 616 617
    pub fn extract_ssa_id(&self) -> Option<MuID> {
        match self.v {
            Value_::SSAVar(id) => Some(id),
            _ => None
        }
    }
}

impl fmt::Display for Value {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self.v {
qinsoon's avatar
qinsoon committed
618
            Value_::SSAVar(_) => {
619
                write!(f, "+({} %{})", self.ty, self.hdr)
qinsoon's avatar
qinsoon committed
620 621
            },
            Value_::Constant(ref c) => {
622
                write!(f, "+({} {} @{})", self.ty, c, self.hdr)
qinsoon's avatar
qinsoon committed
623
            },
624 625
            Value_::Global(ref ty) => {
                write!(f, "+(GLOBAL {} @{})", ty, self.hdr)
626 627
            },
            Value_::Memory(ref mem) => {
628
                write!(f, "+(MEM {} %{})", mem, self.hdr)
qinsoon's avatar
qinsoon committed
629 630 631
            }
        }
    }
632 633
}

qinsoon's avatar
qinsoon committed
634
#[derive(Debug, Clone, PartialEq, RustcEncodable, RustcDecodable)]
qinsoon's avatar
qinsoon committed
635
pub enum Value_ {
636
    SSAVar(MuID),
qinsoon's avatar
qinsoon committed
637
    Constant(Constant),
638
    Global(P<MuType>), // what type is this global (without IRef)
639
    Memory(MemoryLocation)
qinsoon's avatar
qinsoon committed
640 641
}

qinsoon's avatar
qinsoon committed
642
#[derive(Debug)]
643
pub struct SSAVarEntry {
qinsoon's avatar
qinsoon committed
644
    val: P<Value>,
645

646 647
    // how many times this entry is used
    // availalbe after DefUse pass
qinsoon's avatar
qinsoon committed
648
    use_count: AtomicUsize,
649

650
    // this field is only used during TreeGeneration pass
qinsoon's avatar
qinsoon committed
651
    expr: Option<Instruction>
652 653
}

qinsoon's avatar
qinsoon committed
654 655
impl Encodable for SSAVarEntry {
    fn encode<S: Encoder> (&self, s: &mut S) -> Result<(), S::Error> {
qinsoon's avatar
qinsoon committed
656 657
        s.emit_struct("SSAVarEntry", 3, |s| {
            try!(s.emit_struct_field("val", 0, |s| self.val.encode(s)));
qinsoon's avatar
qinsoon committed
658
            let count = self.use_count.load(Ordering::SeqCst);
qinsoon's avatar
qinsoon committed
659 660
            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
661 662 663 664 665 666 667
            Ok(())
        })
    }
}

impl Decodable for SSAVarEntry {
    fn decode<D: Decoder>(d: &mut D) -> Result<SSAVarEntry, D::Error> {
qinsoon's avatar
qinsoon committed
668 669 670 671
        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
672 673
            
            let ret = SSAVarEntry {
qinsoon's avatar
qinsoon committed
674
                val: val,
qinsoon's avatar
qinsoon committed
675 676 677 678 679 680 681 682 683 684 685
                use_count: ATOMIC_USIZE_INIT,
                expr: expr
            };
            
            ret.use_count.store(count, Ordering::SeqCst);
            
            Ok(ret)
        })
    }
}

686
impl SSAVarEntry {
qinsoon's avatar
qinsoon committed
687
    pub fn new(val: P<Value>) -> SSAVarEntry {
qinsoon's avatar
qinsoon committed
688
        let ret = SSAVarEntry {
qinsoon's avatar
qinsoon committed
689
            val: val,
qinsoon's avatar
qinsoon committed
690 691 692 693 694 695 696 697
            use_count: ATOMIC_USIZE_INIT,
            expr: None
        };
        
        ret.use_count.store(0, Ordering::SeqCst);
        
        ret
    }
qinsoon's avatar
qinsoon committed
698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716

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

    pub fn has_expr(&self) -> bool {
        self.expr.is_some()
    }
717 718 719
    pub fn assign_expr(&mut self, expr: Instruction) {
        self.expr = Some(expr)
    }
qinsoon's avatar
qinsoon committed
720 721 722 723
    pub fn take_expr(&mut self) -> Instruction {
        debug_assert!(self.has_expr());
        self.expr.take().unwrap()
    }
724 725
}

726
impl fmt::Display for SSAVarEntry {
727
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
728
        write!(f, "{}", self.val)
729 730 731
    }
}

qinsoon's avatar
qinsoon committed
732
#[derive(Debug, Clone, PartialEq, RustcEncodable, RustcDecodable)]
733
pub enum Constant {
qinsoon's avatar
qinsoon committed
734
    Int(u64),
735 736
    Float(f32),
    Double(f64),
qinsoon's avatar
qinsoon committed
737
//    IRef(Address),
qinsoon's avatar
qinsoon committed
738 739
    FuncRef(MuID),
    UFuncRef(MuID),
740
    Vector(Vec<Constant>),
741 742
    //Pointer(Address),
    NullRef,
743 744
}

745
impl fmt::Display for Constant {
746 747 748 749 750
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            &Constant::Int(v) => write!(f, "{}", v),
            &Constant::Float(v) => write!(f, "{}", v),
            &Constant::Double(v) => write!(f, "{}", v),
qinsoon's avatar
qinsoon committed
751
//            &Constant::IRef(v) => write!(f, "{}", v),
752 753
            &Constant::FuncRef(v) => write!(f, "{}", v),
            &Constant::UFuncRef(v) => write!(f, "{}", v),
754 755 756 757 758 759 760 761 762 763
            &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, "]")
            }
764
            &Constant::NullRef => write!(f, "NullRef"),
765 766
        }
    }
qinsoon's avatar
qinsoon committed
767 768
}

qinsoon's avatar
qinsoon committed
769
#[derive(Debug, Clone, PartialEq, RustcEncodable, RustcDecodable)]
770 771 772 773 774 775 776 777 778
pub enum MemoryLocation {
    Address{
        base: P<Value>,
        offset: Option<P<Value>>,
        index: Option<P<Value>>,
        scale: Option<u8>
    },
    Symbolic{
        base: Option<P<Value>>,
qinsoon's avatar
qinsoon committed
779
        label: MuName
780 781 782 783 784 785 786
    }
}

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
787 788 789 790 791 792 793 794 795 796 797
                // 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, "]")
798 799 800
            }
            &MemoryLocation::Symbolic{ref base, ref label} => {
                if base.is_some() {
801
                    write!(f, "{}({})", label, base.as_ref().unwrap())
802 803 804 805 806 807 808 809
                } else {
                    write!(f, "{}", label)
                }
            }
        }
    }
}

810
#[repr(C)]
qinsoon's avatar
qinsoon committed
811
#[derive(Debug)] // Display, PartialEq, Clone
812
pub struct MuEntityHeader {
813 814
    id: MuID,
    name: RwLock<Option<MuName>>
815 816
}

qinsoon's avatar
qinsoon committed
817 818 819 820 821 822 823 824 825
impl Clone for MuEntityHeader {
    fn clone(&self) -> Self {
        MuEntityHeader {
            id: self.id,
            name: RwLock::new(self.name.read().unwrap().clone())
        }
    }
}

826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853
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{
                    id: id,
                    name: RwLock::new(name)
                })
        })
    }
}

854 855 856 857 858 859 860 861 862 863 864
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,
865
            name: RwLock::new(Some(MuEntityHeader::name_check(name)))
866 867 868 869 870 871 872 873
        }
    }
    
    pub fn id(&self) -> MuID {
        self.id
    }
    
    pub fn name(&self) -> Option<MuName> {
874
        self.name.read().unwrap().clone()
875
    }
876 877 878 879 880 881 882 883 884 885 886 887 888 889 890

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

    fn name_check(name: MuName) -> MuName {
        if name.starts_with("@") || name.starts_with("%") {
            let (_, name) = name.split_at(1);

            return name.to_string();
        }

        name
    }
891 892 893 894 895 896 897 898 899 900 901
}

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
902
            write!(f, "UNNAMED #{}", self.id)
903 904 905 906 907 908
        } else {
            write!(f, "{} #{}", self.name().unwrap(), self.id)
        }
    }
}

qinsoon's avatar
qinsoon committed
909 910 911
pub trait MuEntity {
    fn id(&self) -> MuID;
    fn name(&self) -> Option<MuName>;
912
    fn set_name(&self, name: MuName);
qinsoon's avatar
qinsoon committed
913 914 915 916 917 918 919 920 921 922
    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
923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952
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()
        }
    }
}

953
pub fn op_vector_str(vec: &Vec<OpIndex>, ops: &Vec<P<TreeNode>>) -> String {
954 955 956 957 958 959
    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(", ");
960
        }
961 962
    }
    ret
963
}