ir.rs 30.5 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

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

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

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

24 25
pub type OpIndex = usize;

qinsoon's avatar
qinsoon committed
26 27 28 29 30 31 32 33 34 35 36 37 38
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;
qinsoon's avatar
qinsoon committed
39
pub const  MACHINE_ID_END   : usize = 200;
qinsoon's avatar
qinsoon committed
40

qinsoon's avatar
qinsoon committed
41 42 43
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
44

qinsoon's avatar
qinsoon committed
45 46 47 48 49
#[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
50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
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
65

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

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

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

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

110 111
    pub force_inline: bool,

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

121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138
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")
        }
    }
}

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

152
    pub fn define(&mut self, content: FunctionContent) {
qinsoon's avatar
qinsoon committed
153
        self.content = Some(content);
154
    }
155

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

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

165
        P(TreeNode {
qinsoon's avatar
qinsoon committed
166 167
            op: pick_op_code_for_ssa(&val.ty),
            v: TreeNode_::Value(val)
168 169
        })
    }
170

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

qinsoon's avatar
qinsoon committed
185
    pub fn new_inst(&mut self, v: Instruction) -> Box<TreeNode> {
qinsoon's avatar
qinsoon committed
186
        Box::new(TreeNode{
187
            op: pick_op_code_for_inst(&v),
188 189
            v: TreeNode_::Instruction(v),
        })
190
    }
qinsoon's avatar
qinsoon committed
191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262

    /// get Map(CallSiteID -> FuncID) that are called by this function
    pub fn get_static_call_edges(&self) -> HashMap<MuID, MuID> {
        let mut ret = HashMap::new();

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

        for (blk_id, block) in f_content.blocks.iter() {
            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();

        for (blk_id, block) in f_content.blocks.iter() {
            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_::Throw(_) => {return true;}
                            _ => {
                                // do nothing
                            }
                        }
                    },
                    _ => {
                        unreachable!()
                    }
                }
            }
        }

        false
    }
263 264
}

qinsoon's avatar
qinsoon committed
265
#[derive(RustcEncodable, RustcDecodable, Clone)]
266
pub struct FunctionContent {
qinsoon's avatar
qinsoon committed
267 268
    pub entry: MuID,
    pub blocks: HashMap<MuID, Block>
269 270
}

271 272 273
impl fmt::Debug for FunctionContent {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let entry = self.get_entry_block();
274
        write!(f, "Entry block: ").unwrap();
275
        write!(f, "{:?}\n", entry).unwrap();
276 277

        write!(f, "Body:").unwrap();
278 279 280 281 282 283 284 285
        for blk_id in self.blocks.keys() {
            let block = self.get_block(*blk_id);
            write!(f, "{:?}\n", block).unwrap();
        }
        Ok(())
    }
}

286 287
impl FunctionContent {
    pub fn get_entry_block(&self) -> &Block {
qinsoon's avatar
qinsoon committed
288
        self.get_block(self.entry)
qinsoon's avatar
qinsoon committed
289
    } 
290

291
    pub fn get_entry_block_mut(&mut self) -> &mut Block {
qinsoon's avatar
qinsoon committed
292 293
        let entry = self.entry;
        self.get_block_mut(entry)
294
    }
295

qinsoon's avatar
qinsoon committed
296 297
    pub fn get_block(&self, id: MuID) -> &Block {
        let ret = self.blocks.get(&id);
qinsoon's avatar
qinsoon committed
298 299
        match ret {
            Some(b) => b,
qinsoon's avatar
qinsoon committed
300
            None => panic!("cannot find block #{}", id)
qinsoon's avatar
qinsoon committed
301
        }
302
    }
303

qinsoon's avatar
qinsoon committed
304 305
    pub fn get_block_mut(&mut self, id: MuID) -> &mut Block {
        let ret = self.blocks.get_mut(&id);
qinsoon's avatar
qinsoon committed
306 307
        match ret {
            Some(b) => b,
qinsoon's avatar
qinsoon committed
308
            None => panic!("cannot find block #{}", id)
qinsoon's avatar
qinsoon committed
309
        }
310
    }
311 312
}

313
#[derive(Default, Debug, RustcEncodable, RustcDecodable)]
314
pub struct FunctionContext {
315
    pub values: HashMap<MuID, SSAVarEntry>
316 317 318 319 320 321 322 323
}

impl FunctionContext {
    fn new() -> FunctionContext {
        FunctionContext {
            values: HashMap::new()
        }
    }
324 325
    
    pub fn make_temporary(&mut self, id: MuID, ty: P<MuType>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
326 327 328 329 330 331 332
        let val = P(Value{
            hdr: MuEntityHeader::unnamed(id),
            ty: ty,
            v: Value_::SSAVar(id)
        });

        self.values.insert(id, SSAVarEntry::new(val.clone()));
333 334

        P(TreeNode {
qinsoon's avatar
qinsoon committed
335 336
            op: pick_op_code_for_ssa(&val.ty),
            v: TreeNode_::Value(val)
337
        })
qinsoon's avatar
qinsoon committed
338 339 340 341 342 343 344 345
    }

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

347
    pub fn get_value(&self, id: MuID) -> Option<&SSAVarEntry> {
348 349
        self.values.get(&id)
    }
350

351
    pub fn get_value_mut(&mut self, id: MuID) -> Option<&mut SSAVarEntry> {
352 353 354 355
        self.values.get_mut(&id)
    }
}

qinsoon's avatar
qinsoon committed
356
#[derive(RustcEncodable, RustcDecodable, Clone)]
357
pub struct Block {
358
    pub hdr: MuEntityHeader,
359 360
    pub content: Option<BlockContent>,
    pub control_flow: ControlFlow
qinsoon's avatar
qinsoon committed
361 362
}

363 364 365 366 367 368 369 370 371 372 373 374 375 376
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(())
    }
}

377
impl Block {
qinsoon's avatar
qinsoon committed
378
    pub fn new(id: MuID) -> Block {
379
        Block{hdr: MuEntityHeader::unnamed(id), content: None, control_flow: ControlFlow::default()}
380
    }
qinsoon's avatar
qinsoon committed
381 382 383 384
    
    pub fn is_exception_block(&self) -> bool {
        return self.content.as_ref().unwrap().exn_arg.is_some()
    }
qinsoon's avatar
qinsoon committed
385 386 387 388 389 390 391 392 393 394

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

            content.body.len()
        }
    }
395 396
}

qinsoon's avatar
qinsoon committed
397
#[derive(Debug, RustcEncodable, RustcDecodable, Clone)]
398
pub struct ControlFlow {
qinsoon's avatar
qinsoon committed
399
    pub preds : Vec<MuID>,
400 401 402
    pub succs : Vec<BlockEdge>
}

403
impl ControlFlow {
qinsoon's avatar
qinsoon committed
404
    pub fn get_hottest_succ(&self) -> Option<MuID> {
405 406 407 408 409
        if self.succs.len() == 0 {
            None
        } else {
            let mut hot_blk = self.succs[0].target;
            let mut hot_prob = self.succs[0].probability;
410

411 412 413 414 415 416
            for edge in self.succs.iter() {
                if edge.probability > hot_prob {
                    hot_blk = edge.target;
                    hot_prob = edge.probability;
                }
            }
417

418 419 420 421 422
            Some(hot_blk)
        }
    }
}

423 424
impl fmt::Display for ControlFlow {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
425 426
        write!(f, "preds: [{}], ", vec_utils::as_str(&self.preds)).unwrap();
        write!(f, "succs: [{}]", vec_utils::as_str(&self.succs))
427 428 429 430 431 432 433 434 435
    }
}

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

qinsoon's avatar
qinsoon committed
436
#[derive(Copy, Clone, Debug, RustcEncodable, RustcDecodable)]
437
pub struct BlockEdge {
qinsoon's avatar
qinsoon committed
438
    pub target: MuID,
439 440 441 442 443 444 445 446 447 448 449
    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
450
#[derive(Copy, Clone, Debug, RustcEncodable, RustcDecodable)]
451 452 453 454
pub enum EdgeKind {
    Forward, Backward
}

qinsoon's avatar
qinsoon committed
455
#[derive(RustcEncodable, RustcDecodable, Clone)]
456
pub struct BlockContent {
457
    pub args: Vec<P<Value>>,
458
    pub exn_arg: Option<P<Value>>,
qinsoon's avatar
qinsoon committed
459
    pub body: Vec<Box<TreeNode>>,
460
    pub keepalives: Option<Vec<P<Value>>>
461 462
}

463 464
impl fmt::Debug for BlockContent {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
465 466 467 468 469 470 471
        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();
        }
472 473 474 475 476 477 478
        for node in self.body.iter() {
            writeln!(f, "{}", node).unwrap();
        }
        Ok(())
    }
}

479 480 481 482 483 484 485 486 487
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
488
                let ops = inst.ops.read().unwrap();
489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523
                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
524
                    | Instruction_::CCall{ref resume, ..}
525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550
                    | 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
551
#[derive(Debug, RustcEncodable, RustcDecodable, Clone)]
qinsoon's avatar
qinsoon committed
552 553
/// always use with P<TreeNode>
pub struct TreeNode {
554 555
    pub op: OpCode,
    pub v: TreeNode_,
qinsoon's avatar
qinsoon committed
556 557
}

558
impl TreeNode {
559
    // this is a hack to allow creating TreeNode without using a &mut MuFunctionVersion
qinsoon's avatar
qinsoon committed
560
    pub fn new_inst(v: Instruction) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
561
        P(TreeNode{
562
            op: pick_op_code_for_inst(&v),
qinsoon's avatar
qinsoon committed
563 564
            v: TreeNode_::Instruction(v),
        })
565 566
    }

qinsoon's avatar
qinsoon committed
567 568 569 570 571 572 573
    pub fn new_boxed_inst(v: Instruction) -> Box<TreeNode> {
        Box::new(TreeNode{
            op: pick_op_code_for_inst(&v),
            v: TreeNode_::Instruction(v),
        })
    }

574 575 576 577 578 579 580 581 582 583 584
    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
        }
    }
585

qinsoon's avatar
qinsoon committed
586
    pub fn clone_value(&self) -> P<Value> {
qinsoon's avatar
qinsoon committed
587
        match self.v {
qinsoon's avatar
qinsoon committed
588
            TreeNode_::Value(ref val) => val.clone(),
589
            TreeNode_::Instruction(ref inst) => {
590
                warn!("expecting a value, but we found an inst. Instead we use its first value");
591 592 593 594 595 596
                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
597
        }
598 599
    }

qinsoon's avatar
qinsoon committed
600 601 602
    pub fn into_value(self) -> Option<P<Value>> {
        match self.v {
            TreeNode_::Value(val) => Some(val),
603
            _ => None
qinsoon's avatar
qinsoon committed
604 605
        }
    }
qinsoon's avatar
qinsoon committed
606 607 608 609 610 611 612

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

615 616
/// use +() to display a node
impl fmt::Display for TreeNode {
qinsoon's avatar
qinsoon committed
617
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
618
        match self.v {
qinsoon's avatar
qinsoon committed
619
            TreeNode_::Value(ref pv) => pv.fmt(f),
620
            TreeNode_::Instruction(ref inst) => {
621
                write!(f, "+({})", inst)
622
            }
qinsoon's avatar
qinsoon committed
623
        }
qinsoon's avatar
qinsoon committed
624
    }
qinsoon's avatar
qinsoon committed
625 626
}

qinsoon's avatar
qinsoon committed
627
#[derive(Debug, RustcEncodable, RustcDecodable, Clone)]
qinsoon's avatar
qinsoon committed
628
pub enum TreeNode_ {
qinsoon's avatar
qinsoon committed
629
    Value(P<Value>),
630
    Instruction(Instruction)
qinsoon's avatar
qinsoon committed
631 632 633
}

/// always use with P<Value>
qinsoon's avatar
qinsoon committed
634
#[derive(Debug, PartialEq, RustcEncodable, RustcDecodable)]
qinsoon's avatar
qinsoon committed
635
pub struct Value {
636
    pub hdr: MuEntityHeader,
qinsoon's avatar
qinsoon committed
637 638
    pub ty: P<MuType>,
    pub v: Value_
qinsoon's avatar
qinsoon committed
639 640
}

641
impl Value {
qinsoon's avatar
qinsoon committed
642 643 644 645 646 647 648 649
    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))
        })
    }
    
650 651 652 653 654 655 656
    pub fn is_mem(&self) -> bool {
        match self.v {
            Value_::Memory(_) => true,
            _ => false
        }
    }
    
657 658 659 660 661 662 663 664 665 666 667 668
    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
        }
    }
669

qinsoon's avatar
qinsoon committed
670 671 672 673 674 675 676 677
    pub unsafe fn as_type(&self, ty: P<MuType>) -> P<Value> {
        P(Value{
            hdr: self.hdr.clone(),
            ty: ty,
            v: self.v.clone()
        })
    }

678 679 680 681 682 683 684 685 686
    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
687 688
            Value_::Constant(Constant::Double(_)) => true,
            Value_::Constant(Constant::Float(_))  => true,
689 690 691
            _ => false
        }
    }
692

693 694
    pub fn is_int_const(&self) -> bool {
        match self.v {
695 696
            Value_::Constant(Constant::Int(_)) => true,
            Value_::Constant(Constant::NullRef) => true,
697 698
            _ => false
        }
qinsoon's avatar
qinsoon committed
699
    }
700 701 702
    
    pub fn extract_int_const(&self) -> u64 {
        match self.v {
703 704
            Value_::Constant(Constant::Int(val)) => val,
            Value_::Constant(Constant::NullRef)  => 0,
705 706 707
            _ => panic!("expect int const")
        }
    }
708

qinsoon's avatar
qinsoon committed
709 710 711 712 713 714 715 716 717 718 719
    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
720
            Value_::SSAVar(_) => {
721
                write!(f, "+({} %{})", self.ty, self.hdr)
qinsoon's avatar
qinsoon committed
722 723
            },
            Value_::Constant(ref c) => {
724
                write!(f, "+({} {} @{})", self.ty, c, self.hdr)
qinsoon's avatar
qinsoon committed
725
            },
726 727
            Value_::Global(ref ty) => {
                write!(f, "+(GLOBAL {} @{})", ty, self.hdr)
728 729
            },
            Value_::Memory(ref mem) => {
730
                write!(f, "+(MEM {} %{})", mem, self.hdr)
qinsoon's avatar
qinsoon committed
731 732 733
            }
        }
    }
734 735
}

qinsoon's avatar
qinsoon committed
736
#[derive(Debug, Clone, PartialEq, RustcEncodable, RustcDecodable)]
qinsoon's avatar
qinsoon committed
737
pub enum Value_ {
738
    SSAVar(MuID),
qinsoon's avatar
qinsoon committed
739
    Constant(Constant),
740
    Global(P<MuType>), // what type is this global (without IRef)
741
    Memory(MemoryLocation)
qinsoon's avatar
qinsoon committed
742 743
}

qinsoon's avatar
qinsoon committed
744
#[derive(Debug)]
745
pub struct SSAVarEntry {
qinsoon's avatar
qinsoon committed
746
    val: P<Value>,
747

748 749
    // how many times this entry is used
    // availalbe after DefUse pass
qinsoon's avatar
qinsoon committed
750
    use_count: AtomicUsize,
751

752
    // this field is only used during TreeGeneration pass
qinsoon's avatar
qinsoon committed
753
    expr: Option<Instruction>
754 755
}

qinsoon's avatar
qinsoon committed
756 757
impl Encodable for SSAVarEntry {
    fn encode<S: Encoder> (&self, s: &mut S) -> Result<(), S::Error> {
qinsoon's avatar
qinsoon committed
758 759
        s.emit_struct("SSAVarEntry", 3, |s| {
            try!(s.emit_struct_field("val", 0, |s| self.val.encode(s)));
qinsoon's avatar
qinsoon committed
760
            let count = self.use_count.load(Ordering::SeqCst);
qinsoon's avatar
qinsoon committed
761 762
            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
763 764 765 766 767 768 769
            Ok(())
        })
    }
}

impl Decodable for SSAVarEntry {
    fn decode<D: Decoder>(d: &mut D) -> Result<SSAVarEntry, D::Error> {
qinsoon's avatar
qinsoon committed
770 771 772 773
        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
774 775
            
            let ret = SSAVarEntry {
qinsoon's avatar
qinsoon committed
776
                val: val,
qinsoon's avatar
qinsoon committed
777 778 779 780 781 782 783 784 785 786 787
                use_count: ATOMIC_USIZE_INIT,
                expr: expr
            };
            
            ret.use_count.store(count, Ordering::SeqCst);
            
            Ok(ret)
        })
    }
}

788
impl SSAVarEntry {
qinsoon's avatar
qinsoon committed
789
    pub fn new(val: P<Value>) -> SSAVarEntry {
qinsoon's avatar
qinsoon committed
790
        let ret = SSAVarEntry {
qinsoon's avatar
qinsoon committed
791
            val: val,
qinsoon's avatar
qinsoon committed
792 793 794 795 796 797 798 799
            use_count: ATOMIC_USIZE_INIT,
            expr: None
        };
        
        ret.use_count.store(0, Ordering::SeqCst);
        
        ret
    }
qinsoon's avatar
qinsoon committed
800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818

    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()
    }
819 820 821
    pub fn assign_expr(&mut self, expr: Instruction) {
        self.expr = Some(expr)
    }
qinsoon's avatar
qinsoon committed
822 823 824 825
    pub fn take_expr(&mut self) -> Instruction {
        debug_assert!(self.has_expr());
        self.expr.take().unwrap()
    }
826 827
}

828
impl fmt::Display for SSAVarEntry {
829
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
830
        write!(f, "{}", self.val)
831 832 833
    }
}

qinsoon's avatar
qinsoon committed
834
#[derive(Debug, Clone, PartialEq, RustcEncodable, RustcDecodable)]
835
pub enum Constant {
qinsoon's avatar
qinsoon committed
836
    Int(u64),
837 838
    Float(f32),
    Double(f64),
qinsoon's avatar
qinsoon committed
839
//    IRef(Address),
qinsoon's avatar
qinsoon committed
840
    FuncRef(MuID),
841
    Vector(Vec<Constant>),
842 843
    //Pointer(Address),
    NullRef,
qinsoon's avatar
qinsoon committed
844
    ExternSym(CName)
845 846
}

847
impl fmt::Display for Constant {
848 849 850 851 852
    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
853
//            &Constant::IRef(v) => write!(f, "{}", v),
854
            &Constant::FuncRef(v) => write!(f, "{}", v),
855 856 857 858 859 860 861 862 863 864
            &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, "]")
            }
865
            &Constant::NullRef => write!(f, "NullRef"),
qinsoon's avatar
qinsoon committed
866
            &Constant::ExternSym(ref name) => write!(f, "ExternSym({})", name)
867 868
        }
    }
qinsoon's avatar
qinsoon committed
869 870
}

qinsoon's avatar
qinsoon committed
871
#[derive(Debug, Clone, PartialEq, RustcEncodable, RustcDecodable)]
872 873 874 875 876 877 878 879 880
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
881
        label: MuName
882 883 884 885 886 887 888
    }
}

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
889 890 891 892 893 894 895 896 897 898 899
                // 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, "]")
900 901 902
            }
            &MemoryLocation::Symbolic{ref base, ref label} => {
                if base.is_some() {
903
                    write!(f, "{}({})", label, base.as_ref().unwrap())
904 905 906 907 908 909 910 911
                } else {
                    write!(f, "{}", label)
                }
            }
        }
    }
}

912
#[repr(C)]
qinsoon's avatar
qinsoon committed
913
#[derive(Debug)] // Display, PartialEq, Clone
914
pub struct MuEntityHeader {
915 916
    id: MuID,
    name: RwLock<Option<MuName>>
917 918
}

qinsoon's avatar
qinsoon committed
919 920 921 922 923 924 925 926 927
impl Clone for MuEntityHeader {
    fn clone(&self) -> Self {
        MuEntityHeader {
            id: self.id,
            name: RwLock::new(self.name.read().unwrap().clone())
        }
    }
}

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 953 954 955
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)
                })
        })
    }
}

956 957 958 959 960 961 962 963 964 965 966
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,
967
            name: RwLock::new(Some(MuEntityHeader::name_check(name)))
968 969 970 971 972 973 974 975
        }
    }
    
    pub fn id(&self) -> MuID {
        self.id
    }
    
    pub fn name(&self) -> Option<MuName> {
976
        self.name.read().unwrap().clone()
977
    }
978 979 980 981 982 983 984 985 986 987 988 989 990 991 992

    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
    }
993 994 995 996 997 998 999 1000 1001 1002 1003
}

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
1004
            write!(f, "UNNAMED #{}", self.id)
1005 1006 1007 1008 1009 1010
        } else {
            write!(f, "{} #{}", self.name().unwrap(), self.id)
        }
    }
}

qinsoon's avatar
qinsoon committed
1011 1012 1013
pub trait MuEntity {
    fn id(&self) -> MuID;
    fn name(&self) -> Option<MuName>;
1014
    fn set_name(&self, name: MuName);
qinsoon's avatar
qinsoon committed
1015 1016 1017 1018 1019 1020 1021 1022 1023 1024
    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
1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054
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()
        }
    }
}

1055
pub fn op_vector_str(vec: &Vec<OpIndex>, ops: &Vec<P<TreeNode>>) -> String {
1056 1057 1058 1059 1060 1061
    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(", ");
1062
        }
1063 1064
    }
    ret
1065
}