ir.rs 35.7 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14
// Copyright 2017 The Australian National University
// 
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
// 
//     http://www.apache.org/licenses/LICENSE-2.0
// 
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

15 16 17 18 19
use ptr::P;
use types::*;
use inst::*;
use op::*;

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

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

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

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

39 40
pub type OpIndex = usize;

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

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

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

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

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

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

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

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

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

128
    pub context: FunctionContext,
129

130 131
    pub force_inline: bool,

qinsoon's avatar
qinsoon committed
132 133 134 135 136
    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 {
137
        write!(f, "FuncVer {} of Func #{}", self.hdr, self.func_id)
qinsoon's avatar
qinsoon committed
138
    }
139 140
}

141 142 143 144 145 146 147 148 149 150 151
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() {
152
            write!(f, "Block Trace: {:?}\n", self.block_trace.as_ref().unwrap())
153 154 155 156 157 158
        } else {
            write!(f, "Trace not available\n")
        }
    }
}

159
impl MuFunctionVersion {
160
    pub fn new(entity: MuEntityHeader, func: MuID, sig: P<MuFuncSig>) -> MuFunctionVersion {
161
        MuFunctionVersion{
162
            hdr: entity,
qinsoon's avatar
qinsoon committed
163
            func_id: func,
164
            sig: sig,
165
            orig_content: None,
166
            content: None,
167
            is_defined: false,
168
            is_compiled: false,
169
            context: FunctionContext::new(),
170 171
            block_trace: None,
            force_inline: false
qinsoon's avatar
qinsoon committed
172
        }
173
    }
174

qinsoon's avatar
qinsoon committed
175 176 177 178 179 180 181
    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),
182
            is_defined: true,
183
            is_compiled: false,
qinsoon's avatar
qinsoon committed
184 185 186 187 188 189 190 191 192 193
            context: context,
            block_trace: None,
            force_inline: false
        }
    }

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

194
    pub fn define(&mut self, content: FunctionContent) {
195 196 197 198 199
        if self.is_defined {
            panic!("alread defined the function: {}", self);
        }

        self.is_defined = true;
200
        self.orig_content = Some(content.clone());
qinsoon's avatar
qinsoon committed
201
        self.content = Some(content);
202
    }
203

204 205 206 207 208 209 210
    pub fn is_compiled(&self) -> bool {
        self.is_compiled
    }
    pub fn set_compiled(&mut self) {
        self.is_compiled = true;
    }

211 212
    pub fn new_ssa(&mut self, entity: MuEntityHeader, ty: P<MuType>) -> P<TreeNode> {
        let id = entity.id();
qinsoon's avatar
qinsoon committed
213
        let val = P(Value{
214
            hdr: entity,
qinsoon's avatar
qinsoon committed
215 216 217 218 219
            ty: ty,
            v: Value_::SSAVar(id)
        });

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

221
        P(TreeNode {
qinsoon's avatar
qinsoon committed
222 223
            op: pick_op_code_for_ssa(&val.ty),
            v: TreeNode_::Value(val)
224 225
        })
    }
226

qinsoon's avatar
qinsoon committed
227
    pub fn new_constant(&mut self, v: P<Value>) -> P<TreeNode> {
228
        P(TreeNode{
qinsoon's avatar
qinsoon committed
229 230 231 232 233
            op: pick_op_code_for_value(&v.ty),
            v: TreeNode_::Value(v)
        })
    }
    
qinsoon's avatar
qinsoon committed
234
    pub fn new_global(&mut self, v: P<Value>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
235 236
        P(TreeNode{
            op: pick_op_code_for_value(&v.ty),
qinsoon's avatar
qinsoon committed
237 238
            v: TreeNode_::Value(v)
        })
239
    }
240

qinsoon's avatar
qinsoon committed
241
    pub fn new_inst(&mut self, v: Instruction) -> Box<TreeNode> {
qinsoon's avatar
qinsoon committed
242
        Box::new(TreeNode{
243
            op: pick_op_code_for_inst(&v),
244 245
            v: TreeNode_::Instruction(v),
        })
246
    }
qinsoon's avatar
qinsoon committed
247 248

    /// get Map(CallSiteID -> FuncID) that are called by this function
249 250
    pub fn get_static_call_edges(&self) -> LinkedHashMap<MuID, MuID> {
        let mut ret = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
251 252 253

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

qinsoon's avatar
qinsoon committed
254
        for (_, block) in f_content.blocks.iter() {
qinsoon's avatar
qinsoon committed
255 256 257 258 259
            let block_content = block.content.as_ref().unwrap();

            for inst in block_content.body.iter() {
                match inst.v {
                    TreeNode_::Instruction(ref inst) => {
260
                        let ref ops = inst.ops;
qinsoon's avatar
qinsoon committed
261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294

                        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
295
        for (_, block) in f_content.blocks.iter() {
qinsoon's avatar
qinsoon committed
296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316
            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
    }
317 318
}

319
#[derive(Clone)]
320
pub struct FunctionContent {
qinsoon's avatar
qinsoon committed
321
    pub entry: MuID,
322 323 324 325
    pub blocks: LinkedHashMap<MuID, Block>,

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

328 329 330
impl fmt::Debug for FunctionContent {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let entry = self.get_entry_block();
331
        write!(f, "Entry block: ").unwrap();
332
        write!(f, "{:?}\n", entry).unwrap();
333 334

        write!(f, "Body:").unwrap();
335 336 337 338 339 340 341 342
        for blk_id in self.blocks.keys() {
            let block = self.get_block(*blk_id);
            write!(f, "{:?}\n", block).unwrap();
        }
        Ok(())
    }
}

343 344
impl FunctionContent {
    pub fn new(entry: MuID, blocks: LinkedHashMap<MuID, Block>) -> FunctionContent {
qinsoon's avatar
qinsoon committed
345
        FunctionContent {
346 347 348
            entry: entry,
            blocks: blocks,
            exception_blocks: LinkedHashSet::new()
qinsoon's avatar
qinsoon committed
349 350 351
        }
    }

352
    pub fn get_entry_block(&self) -> &Block {
qinsoon's avatar
qinsoon committed
353
        self.get_block(self.entry)
qinsoon's avatar
qinsoon committed
354
    } 
355

356
    pub fn get_entry_block_mut(&mut self) -> &mut Block {
qinsoon's avatar
qinsoon committed
357 358
        let entry = self.entry;
        self.get_block_mut(entry)
359
    }
360

qinsoon's avatar
qinsoon committed
361 362
    pub fn get_block(&self, id: MuID) -> &Block {
        let ret = self.blocks.get(&id);
qinsoon's avatar
qinsoon committed
363 364
        match ret {
            Some(b) => b,
qinsoon's avatar
qinsoon committed
365
            None => panic!("cannot find block #{}", id)
qinsoon's avatar
qinsoon committed
366
        }
367
    }
368

qinsoon's avatar
qinsoon committed
369 370
    pub fn get_block_mut(&mut self, id: MuID) -> &mut Block {
        let ret = self.blocks.get_mut(&id);
qinsoon's avatar
qinsoon committed
371 372
        match ret {
            Some(b) => b,
qinsoon's avatar
qinsoon committed
373
            None => panic!("cannot find block #{}", id)
qinsoon's avatar
qinsoon committed
374
        }
375
    }
376 377 378 379 380 381 382 383 384 385

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

        panic!("cannot find block {}", name)
    }
386 387
}

388
#[derive(Default, Debug)]
389
pub struct FunctionContext {
390
    pub values: LinkedHashMap<MuID, SSAVarEntry>
391 392 393 394 395
}

impl FunctionContext {
    fn new() -> FunctionContext {
        FunctionContext {
396
            values: LinkedHashMap::new()
397 398
        }
    }
399 400
    
    pub fn make_temporary(&mut self, id: MuID, ty: P<MuType>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
401 402 403 404 405 406 407
        let val = P(Value{
            hdr: MuEntityHeader::unnamed(id),
            ty: ty,
            v: Value_::SSAVar(id)
        });

        self.values.insert(id, SSAVarEntry::new(val.clone()));
408 409

        P(TreeNode {
qinsoon's avatar
qinsoon committed
410 411
            op: pick_op_code_for_ssa(&val.ty),
            v: TreeNode_::Value(val)
412
        })
qinsoon's avatar
qinsoon committed
413 414 415 416 417 418 419 420
    }

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

422
    pub fn get_value(&self, id: MuID) -> Option<&SSAVarEntry> {
423 424
        self.values.get(&id)
    }
425

426
    pub fn get_value_mut(&mut self, id: MuID) -> Option<&mut SSAVarEntry> {
427 428 429 430
        self.values.get_mut(&id)
    }
}

431
#[derive(Clone)]
432
pub struct Block {
433
    pub hdr: MuEntityHeader,
434 435
    pub content: Option<BlockContent>,
    pub control_flow: ControlFlow
qinsoon's avatar
qinsoon committed
436 437
}

438 439 440 441 442 443 444 445 446 447 448 449 450 451
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(())
    }
}

452
impl Block {
453 454
    pub fn new(entity: MuEntityHeader) -> Block {
        Block{hdr: entity, content: None, control_flow: ControlFlow::default()}
455
    }
qinsoon's avatar
qinsoon committed
456
    
457
    pub fn is_receiving_exception_arg(&self) -> bool {
qinsoon's avatar
qinsoon committed
458 459
        return self.content.as_ref().unwrap().exn_arg.is_some()
    }
qinsoon's avatar
qinsoon committed
460 461 462 463 464 465 466 467 468 469

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

            content.body.len()
        }
    }
470 471
}

472
#[derive(Debug, Clone)]
473
pub struct ControlFlow {
qinsoon's avatar
qinsoon committed
474
    pub preds : Vec<MuID>,
475 476 477
    pub succs : Vec<BlockEdge>
}

478
impl ControlFlow {
qinsoon's avatar
qinsoon committed
479
    pub fn get_hottest_succ(&self) -> Option<MuID> {
480 481 482 483 484
        if self.succs.len() == 0 {
            None
        } else {
            let mut hot_blk = self.succs[0].target;
            let mut hot_prob = self.succs[0].probability;
485

486 487 488 489 490 491
            for edge in self.succs.iter() {
                if edge.probability > hot_prob {
                    hot_blk = edge.target;
                    hot_prob = edge.probability;
                }
            }
492

493 494 495 496 497
            Some(hot_blk)
        }
    }
}

498 499
impl fmt::Display for ControlFlow {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
500 501
        write!(f, "preds: [{}], ", vec_utils::as_str(&self.preds)).unwrap();
        write!(f, "succs: [{}]", vec_utils::as_str(&self.succs))
502 503 504 505 506 507 508 509 510
    }
}

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

511
#[derive(Copy, Clone, Debug)]
512
pub struct BlockEdge {
qinsoon's avatar
qinsoon committed
513
    pub target: MuID,
514 515 516 517 518 519 520 521 522 523 524
    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)
    }
}

525
#[derive(Copy, Clone, Debug)]
526 527 528 529
pub enum EdgeKind {
    Forward, Backward
}

530
#[derive(Clone)]
531
pub struct BlockContent {
532
    pub args: Vec<P<Value>>,
533
    pub exn_arg: Option<P<Value>>,
qinsoon's avatar
qinsoon committed
534
    pub body: Vec<Box<TreeNode>>,
535
    pub keepalives: Option<Vec<P<Value>>>
536 537
}

538 539
impl fmt::Debug for BlockContent {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
540 541 542 543 544 545 546
        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();
        }
547 548 549 550 551 552 553
        for node in self.body.iter() {
            writeln!(f, "{}", node).unwrap();
        }
        Ok(())
    }
}

554 555 556 557 558 559 560 561 562
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) => {
563
                let ref ops = inst.ops;
564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598
                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
599
                    | Instruction_::CCall{ref resume, ..}
600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615
                    | 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);
                    }
                    
616
                    _ => panic!("didn't expect last inst as {}", inst)
617 618 619 620 621 622 623 624 625
                }
            },
            _ => panic!("expect last treenode of block is a inst")
        }
        
        ret
    }
}

626
#[derive(Debug, Clone)]
qinsoon's avatar
qinsoon committed
627 628
/// always use with P<TreeNode>
pub struct TreeNode {
629 630
    pub op: OpCode,
    pub v: TreeNode_,
qinsoon's avatar
qinsoon committed
631 632
}

633
impl TreeNode {
634
    // this is a hack to allow creating TreeNode without using a &mut MuFunctionVersion
qinsoon's avatar
qinsoon committed
635
    pub fn new_inst(v: Instruction) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
636
        P(TreeNode{
637
            op: pick_op_code_for_inst(&v),
qinsoon's avatar
qinsoon committed
638 639
            v: TreeNode_::Instruction(v),
        })
640 641
    }

qinsoon's avatar
qinsoon committed
642 643 644 645 646 647 648
    pub fn new_boxed_inst(v: Instruction) -> Box<TreeNode> {
        Box::new(TreeNode{
            op: pick_op_code_for_inst(&v),
            v: TreeNode_::Instruction(v),
        })
    }

649 650 651 652 653 654 655 656 657 658 659
    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
        }
    }
660

qinsoon's avatar
qinsoon committed
661
    pub fn clone_value(&self) -> P<Value> {
qinsoon's avatar
qinsoon committed
662
        match self.v {
qinsoon's avatar
qinsoon committed
663
            TreeNode_::Value(ref val) => val.clone(),
664 665 666 667 668 669 670
            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
671
        }
672 673
    }

qinsoon's avatar
qinsoon committed
674 675 676
    pub fn into_value(self) -> Option<P<Value>> {
        match self.v {
            TreeNode_::Value(val) => Some(val),
677
            _ => None
qinsoon's avatar
qinsoon committed
678 679
        }
    }
qinsoon's avatar
qinsoon committed
680 681 682 683 684 685 686

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

689 690
/// use +() to display a node
impl fmt::Display for TreeNode {
qinsoon's avatar
qinsoon committed
691
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
692
        match self.v {
qinsoon's avatar
qinsoon committed
693
            TreeNode_::Value(ref pv) => pv.fmt(f),
694
            TreeNode_::Instruction(ref inst) => {
695
                write!(f, "({})", inst)
696
            }
qinsoon's avatar
qinsoon committed
697
        }
qinsoon's avatar
qinsoon committed
698
    }
qinsoon's avatar
qinsoon committed
699 700
}

701
#[derive(Debug, Clone)]
qinsoon's avatar
qinsoon committed
702
pub enum TreeNode_ {
qinsoon's avatar
qinsoon committed
703
    Value(P<Value>),
704
    Instruction(Instruction)
qinsoon's avatar
qinsoon committed
705 706 707
}

/// always use with P<Value>
708 709
rodal_struct!(Value{hdr, ty, v});
#[derive(PartialEq)]
qinsoon's avatar
qinsoon committed
710
pub struct Value {
711
    pub hdr: MuEntityHeader,
qinsoon's avatar
qinsoon committed
712 713
    pub ty: P<MuType>,
    pub v: Value_
qinsoon's avatar
qinsoon committed
714 715
}

716
impl Value {
qinsoon's avatar
qinsoon committed
717 718 719 720 721 722 723 724
    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))
        })
    }
    
725 726 727 728 729 730
    pub fn is_mem(&self) -> bool {
        match self.v {
            Value_::Memory(_) => true,
            _ => false
        }
    }
731 732

    pub fn is_reg(&self) -> bool {
733
        match self.v {
734 735 736 737 738 739 740 741
            Value_::SSAVar(_) => true,
            _ => false
        }
    }

    pub fn is_const(&self) -> bool {
        match self.v {
            Value_::Constant(_) => true,
742 743 744
            _ => false
        }
    }
745

qinsoon's avatar
qinsoon committed
746 747 748 749 750 751 752 753
    pub unsafe fn as_type(&self, ty: P<MuType>) -> P<Value> {
        P(Value{
            hdr: self.hdr.clone(),
            ty: ty,
            v: self.v.clone()
        })
    }

754 755 756 757 758 759 760 761
    pub fn is_int_ex_const(&self) -> bool {
        match self.v {
            Value_::Constant(Constant::IntEx(_)) => true,
            _ => false
        }
    }


762 763
    pub fn is_int_const(&self) -> bool {
        match self.v {
764 765
            Value_::Constant(Constant::Int(_)) => true,
            Value_::Constant(Constant::NullRef) => true,
766 767
            _ => false
        }
qinsoon's avatar
qinsoon committed
768
    }
769 770 771 772 773 774 775
    pub fn is_fp_const(&self) -> bool {
        match self.v {
            Value_::Constant(Constant::Float(_)) => true,
            Value_::Constant(Constant::Double(_)) => true,
            _ => false
        }
    }
776 777
    pub fn extract_int_const(&self) -> u64 {
        match self.v {
778 779
            Value_::Constant(Constant::Int(val)) => val,
            Value_::Constant(Constant::NullRef)  => 0,
780 781 782
            _ => panic!("expect int const")
        }
    }
783

784 785 786 787 788 789 790
    pub fn extract_int_ex_const(&self) -> Vec<u64> {
        match self.v {
            Value_::Constant(Constant::IntEx(ref val)) => val.clone(),
            _ => panic!("expect int ex const")
        }
    }

qinsoon's avatar
qinsoon committed
791 792 793 794 795 796
    pub fn extract_ssa_id(&self) -> Option<MuID> {
        match self.v {
            Value_::SSAVar(id) => Some(id),
            _ => None
        }
    }
qinsoon's avatar
qinsoon committed
797 798 799 800 801 802 803

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

806 807
const DISPLAY_ID : bool = true;
const DISPLAY_TYPE : bool = false;
808
const PRINT_ABBREVIATE_NAME: bool = true;
809

qinsoon's avatar
qinsoon committed
810 811 812 813 814 815
impl fmt::Debug for Value {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", self)
    }
}

qinsoon's avatar
qinsoon committed
816 817
impl fmt::Display for Value {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
818 819 820
        if DISPLAY_TYPE {
            match self.v {
                Value_::SSAVar(_) => {
821
                    write!(f, "{}(%{})", self.ty, self.hdr)
822 823
                },
                Value_::Constant(ref c) => {
824
                    write!(f, "{}({})", self.ty, c)
825 826
                },
                Value_::Global(ref ty) => {
827
                    write!(f, "{}(@{})", ty, self.hdr)
828 829
                },
                Value_::Memory(ref mem) => {
830
                    write!(f, "%{}{})", self.hdr, mem)
831 832 833 834 835 836 837 838
                }
            }
        } else {
            match self.v {
                Value_::SSAVar(_) => {
                    write!(f, "%{}", self.hdr)
                },
                Value_::Constant(ref c) => {
qinsoon's avatar
qinsoon committed
839
                    write!(f, "{}", c)
840 841
                },
                Value_::Global(_) => {
842
                    write!(f, "@{}", self.hdr)
843 844
                },
                Value_::Memory(ref mem) => {
845
                    write!(f, "%{}{}", self.hdr, mem)
846
                }
qinsoon's avatar
qinsoon committed
847 848 849
            }
        }
    }
850 851
}

852 853
rodal_enum!(Value_{(SSAVar: id), (Constant: val), (Global: ty), (Memory: location)});
#[derive(Debug, Clone, PartialEq)]
qinsoon's avatar
qinsoon committed
854
pub enum Value_ {
855
    SSAVar(MuID),
qinsoon's avatar
qinsoon committed
856
    Constant(Constant),
857
    Global(P<MuType>), // what type is this global (without IRef)
858
    Memory(MemoryLocation)
qinsoon's avatar
qinsoon committed
859 860
}

qinsoon's avatar
qinsoon committed
861
#[derive(Debug)]
862
pub struct SSAVarEntry {
qinsoon's avatar
qinsoon committed
863
    val: P<Value>,
864

865 866
    // how many times this entry is used
    // availalbe after DefUse pass
qinsoon's avatar
qinsoon committed
867
    use_count: AtomicUsize,
868

869
    // this field is only used during TreeGeneration pass
qinsoon's avatar
qinsoon committed
870 871 872 873
    expr: Option<Instruction>,

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

876
impl SSAVarEntry {
qinsoon's avatar
qinsoon committed
877
    pub fn new(val: P<Value>) -> SSAVarEntry {
qinsoon's avatar
qinsoon committed
878
        let ret = SSAVarEntry {
qinsoon's avatar
qinsoon committed
879
            val: val,
qinsoon's avatar
qinsoon committed
880
            use_count: ATOMIC_USIZE_INIT,
qinsoon's avatar
qinsoon committed
881 882
            expr: None,
            split: None
qinsoon's avatar
qinsoon committed
883 884 885 886 887 888
        };
        
        ret.use_count.store(0, Ordering::SeqCst);
        
        ret
    }
qinsoon's avatar
qinsoon committed
889 890 891 892 893 894 895 896 897 898 899 900 901 902 903

    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);
    }
904 905 906
    pub fn reset_use_count(&self) {
        self.use_count.store(0, Ordering::SeqCst);
    }
qinsoon's avatar
qinsoon committed
907 908 909 910

    pub fn has_expr(&self) -> bool {
        self.expr.is_some()
    }
911 912 913
    pub fn assign_expr(&mut self, expr: Instruction) {
        self.expr = Some(expr)
    }
qinsoon's avatar
qinsoon committed
914 915 916 917
    pub fn take_expr(&mut self) -> Instruction {
        debug_assert!(self.has_expr());
        self.expr.take().unwrap()
    }
qinsoon's avatar
qinsoon committed
918 919 920 921 922 923 924 925 926 927

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

930
impl fmt::Display for SSAVarEntry {
931
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
932
        write!(f, "{}", self.val)
933 934 935
    }
}

936 937 938
rodal_enum!(Constant{(Int: val), (IntEx: val), (Float: val), (Double: val), (FuncRef: val),
    (Vector: val), NullRef, (ExternSym: val), (List: val)});
#[derive(Debug, Clone, PartialEq)]
939
pub enum Constant {
qinsoon's avatar
qinsoon committed
940
    Int(u64),
qinsoon's avatar
qinsoon committed
941
    IntEx(Vec<u64>),
942 943
    Float(f32),
    Double(f64),
qinsoon's avatar
qinsoon committed
944
//    IRef(Address),
qinsoon's avatar
qinsoon committed
945
    FuncRef(MuID),
946
    Vector(Vec<Constant>),
947 948
    //Pointer(Address),
    NullRef,
949 950 951
    ExternSym(CName),

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

954
impl fmt::Display for Constant {
955 956
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
qinsoon's avatar
qinsoon committed
957
            &Constant::Int(v) => write!(f, "{}", v as i64),
qinsoon's avatar
qinsoon committed
958
            &Constant::IntEx(ref v) => write!(f, "IntEx {:?}", v),
959 960
            &Constant::Float(v) => write!(f, "{}", v),
            &Constant::Double(v) => write!(f, "{}", v),
qinsoon's avatar
qinsoon committed
961
//            &Constant::IRef(v) => write!(f, "{}", v),
962
            &Constant::FuncRef(v) => write!(f, "FuncRef {}", v),
963 964 965 966 967 968 969 970 971 972
            &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, "]")
            }
973
            &Constant::NullRef => write!(f, "NullRef"),
974 975 976 977 978 979 980 981 982
            &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, ")")
            }
983 984
        }
    }
qinsoon's avatar
qinsoon committed
985 986
}

987
#[cfg(target_arch = "x86_64")]
988 989 990
rodal_enum!(MemoryLocation{{Address: scale, base, offset, index}, {Symbolic: is_global, base, label}});
#[cfg(target_arch = "x86_64")]
#[derive(Debug, Clone, PartialEq)]
991 992
pub enum MemoryLocation {
    Address{
993
        base: P<Value>, // +8
994 995 996 997 998 999
        offset: Option<P<Value>>,
        index: Option<P<Value>>,
        scale: Option<u8>
    },
    Symbolic{
        base: Option<P<Value>>,
1000 1001
        label: MuName,
        is_global: bool
1002 1003 1004
    }
}

1005
#[cfg(target_arch = "x86_64")]
1006 1007 1008 1009
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} => {
1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020
                // 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, "]")
1021
            }
1022
            &MemoryLocation::Symbolic{ref base, ref label, ..} => {
1023
                if base.is_some() {
1024
                    write!(f, "{}({})", label, base.as_ref().unwrap())
1025 1026 1027 1028 1029 1030 1031 1032
                } else {
                    write!(f, "{}", label)
                }
            }
        }
    }
}

1033
#[cfg(target_arch = "aarch64")]
1034 1035 1036
rodal_enum!(MemoryLocation{{VirtualAddress: signed, base, offset, scale}, {Address: base, offset, shift, signed}, {Symbolic: label, is_global}});
#[cfg(target_arch = "aarch64")]
#[derive(Debug, Clone, PartialEq)]
1037 1038 1039 1040 1041 1042
pub enum MemoryLocation {
    // Represents how an adress should be computed,
    // will need to be converted to a real Address before being used
    VirtualAddress{
        // Represents base + offset*scale
        // With offset being inerpreted as signed if 'signed' is true
1043 1044 1045 1046
        base: P<Value>, //+8
        offset: Option<P<Value>>, //+16
        signed: bool, //+1
        scale: u64 //+24
1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095
    },
    Address{
        base: P<Value>, // Must be a normal 64-bit register or SP
        offset: Option<P<Value>>, // Can be any GPR or a 12-bit unsigned immediate << n
        shift: u8, // valid values are 0, log2(n)
        signed: bool, // Whether offset is signed or not (only set this if offset is a register)
        // Note: n is the number of bytes the adress refers two
    },
    Symbolic{
        label: MuName,
        is_global: bool
    }
}

#[cfg(target_arch = "aarch64")]
impl fmt::Display for MemoryLocation {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            &MemoryLocation::VirtualAddress{ref base, ref offset, scale, signed} => {
                write!(f, "[{}", base).unwrap();

                if offset.is_some() {
                    let sign_type = if signed { "SInt"} else { "UInt" };
                    write!(f, " + {}({})", sign_type, offset.as_ref().unwrap()).unwrap();
                }

                write!(f, " * {}", scale).unwrap();
                write!(f, "]")
            }
            &MemoryLocation::Address{ref base, ref offset, shift, signed} => {
                write!(f, "[{}", base).unwrap();

                if offset.is_some() {
                    let sign_type = if signed { "SInt"} else { "UInt" };
                    write!(f, " + {}({})", sign_type, offset.as_ref().unwrap()).unwrap();
                }

                if shift != 0 {
                    write!(f, " LSL {}", shift).unwrap();
                }
                write!(f, "]")
            }
            &MemoryLocation::Symbolic{ref label, ..} => {
                write!(f, "{}", label)
            }
        }
    }
}

1096
rodal_struct!(MuEntityHeader{id, name});
1097
#[repr(C)]
qinsoon's avatar
qinsoon committed
1098
#[derive(Debug)] // Display, PartialEq, Clone
1099
pub struct MuEntityHeader {
1100
    id: MuID,
1101
    name: Option<MuName>
1102 1103
}

qinsoon's avatar
qinsoon committed
1104 1105 1106 1107
impl Clone for MuEntityHeader {
    fn clone(&self) -> Self {
        MuEntityHeader {
            id: self.id,
1108
            name: self.name.clone()
qinsoon's avatar
qinsoon committed
1109 1110 1111 1112
        }
    }
}

1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124
pub fn name_check(name: MuName) -> MuName {
    let name = name.replace('.', "$");

    if name.starts_with("@") || name.starts_with("%") {
        let (_, name) = name.split_at(1);

        return name.to_string();
    }

    name
}

1125 1126 1127 1128
impl MuEntityHeader {
    pub fn unnamed(id: MuID) -> MuEntityHeader {
        MuEntityHeader {
            id: id,
1129
            name: None
1130 1131 1132 1133 1134 1135
        }
    }
    
    pub fn named(id: MuID, name: MuName) -> MuEntityHeader {
        MuEntityHeader {
            id: id,
1136
            name: Some(name_check(name))
1137 1138 1139 1140 1141 1142 1143 1144
        }
    }
    
    pub fn id(&self) -> MuID {
        self.id
    }
    
    pub fn name(&self) -> Option<MuName> {
1145
        self.name.clone()
1146
    }
1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169

    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
        }
    }
1170 1171 1172 1173 1174 1175 1176

    pub fn clone_with_id(&self, new_id: MuID) -> MuEntityHeader {
        let mut clone = self.clone();
        clone.id = new_id;

        clone
    }
1177 1178 1179 1180 1181 1182 1183 1184 1185 1186
}

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 {
1187 1188
        if DISPLAY_ID {
            if self.name().is_none() {
1189
                write!(f, "{}", self.id)
1190 1191 1192 1193 1194 1195 1196
            } else {
                if PRINT_ABBREVIATE_NAME {
                    write!(f, "{} #{}", self.abbreviate_name().unwrap(), self.id)
                } else {
                    write!(f, "{} #{}", self.name().unwrap(), self.id)
                }
            }
1197
        } else {
1198 1199
            if self.name().is_none() {
                write!(f, "{}", self.id)
1200
            } else {
1201 1202 1203 1204 1205
                if PRINT_ABBREVIATE_NAME {
                    write!(f, "{}", self.abbreviate_name().unwrap())
                } else {
                    write!(f, "{}", self.name().unwrap())
                }
1206
            }
1207 1208 1209 1210
        }
    }
}

qinsoon's avatar
qinsoon committed
1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223
pub trait MuEntity {
    fn id(&self) -> MuID;
    fn name(&self) -> Option<MuName>;
    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
1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246
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 as_entity(&self) -> &MuEntity {
        match self.v {
            TreeNode_::Instruction(ref inst) => inst.as_entity(),
            TreeNode_::Value(ref pv) => pv.as_entity()
        }
    }
}

1247
pub fn op_vector_str(vec: &Vec<OpIndex>, ops: &Vec<P<TreeNode>>) -> String {
1248 1249 1250 1251 1252 1253
    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(", ");
1254
        }
1255 1256
    }
    ret
1257
}