ir.rs 48.6 KB
Newer Older
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1
// Copyright 2017 The Australian National University
2
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
3 4 5
// 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
6
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
7
//     http://www.apache.org/licenses/LICENSE-2.0
8
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
9 10 11 12 13 14
// 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 20 21 22
use ptr::P;
use types::*;
use inst::*;

use utils::vec_utils;
use utils::LinkedHashMap;
use utils::LinkedHashSet;

23
use std;
24 25 26 27
use std::fmt;
use std::default;
use std::sync::atomic::{AtomicUsize, ATOMIC_USIZE_INIT, Ordering};

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

#[allow(non_snake_case)]
qinsoon's avatar
qinsoon committed
34 35 36
pub fn Mu(str: &'static str) -> MuName {
    str.to_string()
}
37
#[allow(non_snake_case)]
qinsoon's avatar
qinsoon committed
38 39 40
pub fn C(str: &'static str) -> CName {
    str.to_string()
}
41 42 43 44 45 46 47 48 49 50 51 52 53 54

pub type OpIndex = usize;

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
    };
55 56
}
/// MuID reserved for machine registers
qinsoon's avatar
qinsoon committed
57 58
pub const MACHINE_ID_START: usize = 0;
pub const MACHINE_ID_END: usize = 200;
59

60
/// MuID reserved for internal types, etc.
qinsoon's avatar
qinsoon committed
61 62 63
pub const INTERNAL_ID_START: usize = 201;
pub const INTERNAL_ID_END: usize = 500;
pub const USER_ID_START: usize = 1001;
64 65 66

#[deprecated]
#[allow(dead_code)]
67 68 69
// 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
70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
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
}

86 87 88
/// MuFunction represents a Mu function (not a specific definition of a function)
/// This stores function signature, and a list of all versions of this function (as ID),
/// and its current version (as ID)
89
#[derive(Debug)]
90 91
pub struct MuFunction {
    pub hdr: MuEntityHeader,
qinsoon's avatar
qinsoon committed
92

93 94
    pub sig: P<MuFuncSig>,
    pub cur_ver: Option<MuID>,
95
    pub all_vers: Vec<MuID>
96 97
}

qinsoon's avatar
qinsoon committed
98 99 100 101
rodal_struct!(MuFunction {
    hdr,
    sig,
    cur_ver,
102
    all_vers
qinsoon's avatar
qinsoon committed
103
});
104

105
impl MuFunction {
106
    pub fn new(entity: MuEntityHeader, sig: P<MuFuncSig>) -> MuFunction {
107
        MuFunction {
108
            hdr: entity,
109 110
            sig: sig,
            cur_ver: None,
111
            all_vers: vec![]
112 113
        }
    }
114 115

    /// adds a new version to this function, and it becomes the current version
116 117 118 119 120
    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);
        }
qinsoon's avatar
qinsoon committed
121

122 123 124 125 126 127 128 129 130 131
        self.cur_ver = Some(fv);
    }
}

impl fmt::Display for MuFunction {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "Func {}", self.hdr)
    }
}

132 133 134 135 136
/// MuFunctionVersion represents a specific definition of a Mu function
/// It owns the tree structure of MuIRs for the function version

// FIXME: currently part of compilation information is also stored in this data structure
// we should move them (see Issue #18)
137 138
pub struct MuFunctionVersion {
    pub hdr: MuEntityHeader,
139

140 141
    pub func_id: MuID,
    pub sig: P<MuFuncSig>,
qinsoon's avatar
qinsoon committed
142 143
    orig_content: Option<FunctionContent>, // original IR
    pub content: Option<FunctionContent>,  // IR that may have been rewritten during compilation
144 145 146 147
    is_defined: bool,
    is_compiled: bool,
    pub context: FunctionContext,
    pub force_inline: bool,
148
    pub block_trace: Option<Vec<MuID>> // only available after Trace Generation Pass
149
}
qinsoon's avatar
qinsoon committed
150 151 152
rodal_struct!(Callsite {
    name,
    exception_destination,
153
    stack_arg_size
qinsoon's avatar
qinsoon committed
154
});
155 156 157
pub struct Callsite {
    pub name: MuName,
    pub exception_destination: Option<MuName>,
158
    pub stack_arg_size: usize
159 160
}
impl Callsite {
qinsoon's avatar
qinsoon committed
161 162 163
    pub fn new(
        name: MuName,
        exception_destination: Option<MuName>,
164
        stack_arg_size: usize
qinsoon's avatar
qinsoon committed
165 166 167 168
    ) -> Callsite {
        Callsite {
            name: name,
            exception_destination: exception_destination,
169
            stack_arg_size: stack_arg_size
qinsoon's avatar
qinsoon committed
170
        }
171 172
    }
}
173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197
impl fmt::Display for MuFunctionVersion {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "FuncVer {} of Func #{}", self.hdr, self.func_id)
    }
}

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, "Block Trace: {:?}\n", self.block_trace.as_ref().unwrap())
        } else {
            write!(f, "Trace not available\n")
        }
    }
}

impl MuFunctionVersion {
198
    /// creates an empty function version
199
    pub fn new(entity: MuEntityHeader, func: MuID, sig: P<MuFuncSig>) -> MuFunctionVersion {
qinsoon's avatar
qinsoon committed
200
        MuFunctionVersion {
201
            hdr: entity,
202 203 204 205 206 207 208 209
            func_id: func,
            sig: sig,
            orig_content: None,
            content: None,
            is_defined: false,
            is_compiled: false,
            context: FunctionContext::new(),
            block_trace: None,
210
            force_inline: false
211 212 213
        }
    }

214
    /// creates a complete function version
qinsoon's avatar
qinsoon committed
215 216 217 218 219
    pub fn new_(
        hdr: MuEntityHeader,
        id: MuID,
        sig: P<MuFuncSig>,
        content: FunctionContent,
220
        context: FunctionContext
qinsoon's avatar
qinsoon committed
221
    ) -> MuFunctionVersion {
222 223 224 225 226 227 228 229 230 231
        MuFunctionVersion {
            hdr: hdr,
            func_id: id,
            sig: sig,
            orig_content: Some(content.clone()),
            content: Some(content),
            is_defined: true,
            is_compiled: false,
            context: context,
            block_trace: None,
232
            force_inline: false
233 234 235 236 237 238 239
        }
    }

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

240
    /// defines function content
241 242 243 244 245 246 247 248 249 250 251 252 253
    pub fn define(&mut self, content: FunctionContent) {
        if self.is_defined {
            panic!("alread defined the function: {}", self);
        }

        self.is_defined = true;
        self.orig_content = Some(content.clone());
        self.content = Some(content);
    }

    pub fn is_compiled(&self) -> bool {
        self.is_compiled
    }
254

255 256 257 258
    pub fn set_compiled(&mut self) {
        self.is_compiled = true;
    }

259 260
    pub fn new_ssa(&mut self, entity: MuEntityHeader, ty: P<MuType>) -> P<TreeNode> {
        let id = entity.id();
qinsoon's avatar
qinsoon committed
261
        let val = P(Value {
262
            hdr: entity,
263
            ty: ty,
264
            v: Value_::SSAVar(id)
265 266
        });

qinsoon's avatar
qinsoon committed
267 268 269
        self.context
            .values
            .insert(id, SSAVarEntry::new(val.clone()));
270 271

        P(TreeNode {
272
            v: TreeNode_::Value(val)
273 274 275 276
        })
    }

    pub fn new_constant(&mut self, v: P<Value>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
277
        P(TreeNode {
278
            v: TreeNode_::Value(v)
279 280
        })
    }
qinsoon's avatar
qinsoon committed
281

282
    pub fn new_global(&mut self, v: P<Value>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
283
        P(TreeNode {
284
            v: TreeNode_::Value(v)
285 286 287 288
        })
    }

    pub fn new_inst(&mut self, v: Instruction) -> Box<TreeNode> {
qinsoon's avatar
qinsoon committed
289
        Box::new(TreeNode {
290
            v: TreeNode_::Instruction(v)
291 292 293
        })
    }

294 295
    /// gets call outedges in this function
    /// returns Map(CallSiteID -> FuncID)
296 297 298 299 300 301 302 303 304 305 306
    pub fn get_static_call_edges(&self) -> LinkedHashMap<MuID, MuID> {
        let mut ret = LinkedHashMap::new();

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

        for (_, 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) => {
307
                        let ref ops = inst.ops;
308 309

                        match inst.v {
qinsoon's avatar
qinsoon committed
310 311 312 313
                            Instruction_::ExprCall { ref data, .. } |
                            Instruction_::ExprCCall { ref data, .. } |
                            Instruction_::Call { ref data, .. } |
                            Instruction_::CCall { ref data, .. } => {
314 315 316
                                let ref callee = ops[data.func];

                                match callee.v {
qinsoon's avatar
qinsoon committed
317 318 319 320 321 322 323 324
                                    TreeNode_::Instruction(_) => {}
                                    TreeNode_::Value(ref pv) => {
                                        match pv.v {
                                            Value_::Constant(Constant::FuncRef(id)) => {
                                                ret.insert(inst.id(), id);
                                            }
                                            _ => {}
                                        }
325 326
                                    }
                                }
qinsoon's avatar
qinsoon committed
327
                            }
328 329 330 331 332
                            _ => {
                                // do nothing
                            }
                        }
                    }
333
                    _ => unreachable!()
334 335 336 337 338 339 340
                }
            }
        }

        ret
    }

341 342
    // TODO: It may be more efficient to compute this when the instructions
    // are added to the function version and store the result in a field
343 344 345 346 347 348 349 350 351 352
    pub fn has_throw(&self) -> bool {
        let f_content = self.content.as_ref().unwrap();

        for (_, 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) => {
                        match inst.v {
qinsoon's avatar
qinsoon committed
353 354 355
                            Instruction_::Throw(_) => {
                                return true;
                            }
356 357 358 359 360
                            _ => {
                                // do nothing
                            }
                        }
                    }
361
                    _ => unreachable!()
362 363 364 365 366 367
                }
            }
        }

        false
    }
368 369 370 371 372 373 374 375 376 377 378

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

        for (_, 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) => {
                        match inst.v {
qinsoon's avatar
qinsoon committed
379 380 381
                            Instruction_::TailCall(_) => {
                                return true;
                            }
382 383 384
                            _ => {
                                // do nothing
                            }
385 386
                        }
                    }
387
                    _ => unreachable!()
388 389 390 391 392 393 394 395
                }
            }
        }

        false
    }
}

396
/// FunctionContent contains all blocks (which include all instructions) for the function
397
#[derive(Clone)]
398 399 400
pub struct FunctionContent {
    pub entry: MuID,
    pub blocks: LinkedHashMap<MuID, Block>,
401
    pub exception_blocks: LinkedHashSet<MuID> // this field only valid after control flow analysis
402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423
}

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

        write!(f, "Body:").unwrap();
        for blk_id in self.blocks.keys() {
            let block = self.get_block(*blk_id);
            write!(f, "{:?}\n", block).unwrap();
        }
        Ok(())
    }
}

impl FunctionContent {
    pub fn new(entry: MuID, blocks: LinkedHashMap<MuID, Block>) -> FunctionContent {
        FunctionContent {
            entry: entry,
            blocks: blocks,
424
            exception_blocks: LinkedHashSet::new()
425 426 427 428 429
        }
    }

    pub fn get_entry_block(&self) -> &Block {
        self.get_block(self.entry)
qinsoon's avatar
qinsoon committed
430
    }
431 432 433 434 435 436 437 438 439 440

    pub fn get_entry_block_mut(&mut self) -> &mut Block {
        let entry = self.entry;
        self.get_block_mut(entry)
    }

    pub fn get_block(&self, id: MuID) -> &Block {
        let ret = self.blocks.get(&id);
        match ret {
            Some(b) => b,
441
            None => panic!("cannot find block #{}", id)
442 443 444 445 446 447 448
        }
    }

    pub fn get_block_mut(&mut self, id: MuID) -> &mut Block {
        let ret = self.blocks.get_mut(&id);
        match ret {
            Some(b) => b,
449
            None => panic!("cannot find block #{}", id)
450 451
        }
    }
452 453 454

    pub fn get_block_by_name(&self, name: String) -> &Block {
        for block in self.blocks.values() {
455
            if block.name() == name {
456 457 458 459 460 461
                return block;
            }
        }

        panic!("cannot find block {}", name)
    }
462 463
}

464 465
/// FunctionContext contains compilation information about the function
// FIXME: should move this out of ast crate and bind its lifetime with compilation (Issue #18)
466
#[derive(Default, Debug)]
467
pub struct FunctionContext {
468
    pub values: LinkedHashMap<MuID, SSAVarEntry>
469 470 471 472 473
}

impl FunctionContext {
    fn new() -> FunctionContext {
        FunctionContext {
474
            values: LinkedHashMap::new()
475 476
        }
    }
477 478

    /// makes a TreeNode of an SSA variable
479
    pub fn make_temporary(&mut self, id: MuID, ty: P<MuType>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
480
        let val = P(Value {
481 482
            hdr: MuEntityHeader::unnamed(id),
            ty: ty,
483
            v: Value_::SSAVar(id)
484 485 486 487 488
        });

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

        P(TreeNode {
489
            v: TreeNode_::Value(val)
490 491 492
        })
    }

493
    /// shows the name for an SSA by ID
494 495 496
    pub fn get_temp_display(&self, id: MuID) -> String {
        match self.get_value(id) {
            Some(entry) => format!("{}", entry.value()),
497
            None => "CANT_FOUND_ID".to_string()
498 499 500
        }
    }

501
    /// returns a &SSAVarEntry for the given ID
502 503 504 505
    pub fn get_value(&self, id: MuID) -> Option<&SSAVarEntry> {
        self.values.get(&id)
    }

506
    /// returns a &mut SSAVarEntry for the given ID
507 508 509 510 511
    pub fn get_value_mut(&mut self, id: MuID) -> Option<&mut SSAVarEntry> {
        self.values.get_mut(&id)
    }
}

512
/// Block contains BlockContent, which includes all the instructions for the block
513 514
//  FIXME: control_flow field should be moved out of ast crate (Issue #18)
//  FIXME: trace_hint should also be moved
515
#[derive(Clone)]
516 517
pub struct Block {
    pub hdr: MuEntityHeader,
518
    /// the actual content of this block
519
    pub content: Option<BlockContent>,
520 521 522
    /// a trace scheduling hint about where to layout this block
    pub trace_hint: TraceHint,
    /// control flow info about this block (predecessors, successors, etc)
523
    pub control_flow: ControlFlow
524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539
}

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

540 541 542 543 544 545
impl fmt::Display for Block {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", self.name())
    }
}

546
impl Block {
547
    pub fn new(entity: MuEntityHeader) -> Block {
qinsoon's avatar
qinsoon committed
548 549 550 551
        Block {
            hdr: entity,
            content: None,
            trace_hint: TraceHint::None,
552
            control_flow: ControlFlow::default()
qinsoon's avatar
qinsoon committed
553
        }
554
    }
555 556

    /// does this block have an exception arguments?
557
    pub fn is_receiving_exception_arg(&self) -> bool {
qinsoon's avatar
qinsoon committed
558
        return self.content.as_ref().unwrap().exn_arg.is_some();
559 560
    }

561
    /// how many IR instruction does this block have?
562 563 564 565 566 567 568 569 570
    pub fn number_of_irs(&self) -> usize {
        if self.content.is_none() {
            0
        } else {
            let content = self.content.as_ref().unwrap();

            content.body.len()
        }
    }
571 572 573

    /// is this block ends with a conditional branch?
    pub fn ends_with_cond_branch(&self) -> bool {
qinsoon's avatar
qinsoon committed
574
        let block: &BlockContent = self.content.as_ref().unwrap();
575 576 577
        match block.body.last() {
            Some(node) => {
                match node.v {
qinsoon's avatar
qinsoon committed
578 579 580 581
                    TreeNode_::Instruction(Instruction {
                        v: Instruction_::Branch2 { .. },
                        ..
                    }) => true,
582
                    _ => false
583 584
                }
            }
585
            None => false
586 587 588 589 590
        }
    }

    /// is this block ends with a return?
    pub fn ends_with_return(&self) -> bool {
qinsoon's avatar
qinsoon committed
591
        let block: &BlockContent = self.content.as_ref().unwrap();
592 593 594
        match block.body.last() {
            Some(node) => {
                match node.v {
qinsoon's avatar
qinsoon committed
595 596 597 598
                    TreeNode_::Instruction(Instruction {
                        v: Instruction_::Return(_),
                        ..
                    }) => true,
599
                    _ => false
600 601
                }
            }
602
            None => false
603 604
        }
    }
605 606
}

607
/// TraceHint is a hint for the compiler to generate better trace for this block
608 609 610 611 612 613
//  Note: for a sequence of blocks that are supposed to be fast/slow path, only mark the
//  first block with TraceHint, and let the trace scheduler to normally layout other
//  blocks. Otherwise, the scheduler will take every TraceHint into consideration,
//  and may not generate the trace as expected.
//  FIXME: Issue #18
#[derive(Clone, PartialEq)]
614 615 616 617 618 619 620 621
pub enum TraceHint {
    /// no hint provided. Trace scheduler should use its own heuristics to decide
    None,
    /// this block is fast path, and should be put in straightline code where possible
    FastPath,
    /// this block is slow path, and should be kept out of hot loops
    SlowPath,
    /// this block is return sink, and should be put at the end of a function
622
    ReturnSink
623 624
}

625
/// ControlFlow stores compilation info about control flows of a block
626
//  FIXME: Issue #18
627
#[derive(Debug, Clone)]
628
pub struct ControlFlow {
qinsoon's avatar
qinsoon committed
629
    pub preds: Vec<MuID>,
630
    pub succs: Vec<BlockEdge>
631 632 633
}

impl ControlFlow {
634 635
    /// returns the successor with highest branching probability
    /// (in case of tie, returns first met successor)
636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663
    pub fn get_hottest_succ(&self) -> Option<MuID> {
        if self.succs.len() == 0 {
            None
        } else {
            let mut hot_blk = self.succs[0].target;
            let mut hot_prob = self.succs[0].probability;

            for edge in self.succs.iter() {
                if edge.probability > hot_prob {
                    hot_blk = edge.target;
                    hot_prob = edge.probability;
                }
            }

            Some(hot_blk)
        }
    }
}

impl fmt::Display for ControlFlow {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "preds: [{}], ", vec_utils::as_str(&self.preds)).unwrap();
        write!(f, "succs: [{}]", vec_utils::as_str(&self.succs))
    }
}

impl default::Default for ControlFlow {
    fn default() -> ControlFlow {
qinsoon's avatar
qinsoon committed
664 665
        ControlFlow {
            preds: vec![],
666
            succs: vec![]
qinsoon's avatar
qinsoon committed
667
        }
668 669 670
    }
}

671
/// BlockEdge represents an edge in control flow graph
672
#[derive(Copy, Clone, Debug)]
673 674 675 676
pub struct BlockEdge {
    pub target: MuID,
    pub kind: EdgeKind,
    pub is_exception: bool,
677
    pub probability: f32
678 679 680 681
}

impl fmt::Display for BlockEdge {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
682 683 684 685 686 687 688 689
        write!(
            f,
            "{} ({:?}{} - {})",
            self.target,
            self.kind,
            select_value!(self.is_exception, ", exceptional", ""),
            self.probability
        )
690 691 692
    }
}

693
#[derive(Copy, Clone, Debug)]
694
pub enum EdgeKind {
qinsoon's avatar
qinsoon committed
695
    Forward,
696
    Backward
697 698
}

699
/// BlockContent describes arguments to this block, and owns all the IR instructions
700
#[derive(Clone)]
701 702 703 704
pub struct BlockContent {
    pub args: Vec<P<Value>>,
    pub exn_arg: Option<P<Value>>,
    pub body: Vec<Box<TreeNode>>,
705
    pub keepalives: Option<Vec<P<Value>>>
706 707 708 709 710 711 712 713 714
}

impl fmt::Debug for BlockContent {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        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() {
qinsoon's avatar
qinsoon committed
715 716 717 718 719
            writeln!(
                f,
                "keepalives: {}",
                vec_utils::as_str(self.keepalives.as_ref().unwrap())
            ).unwrap();
720 721 722 723 724 725 726 727 728
        }
        for node in self.body.iter() {
            writeln!(f, "{}", node).unwrap();
        }
        Ok(())
    }
}

impl BlockContent {
729
    /// returns all the arguments passed to its successors
730 731 732
    pub fn get_out_arguments(&self) -> Vec<P<Value>> {
        let n_insts = self.body.len();
        let ref last_inst = self.body[n_insts - 1];
qinsoon's avatar
qinsoon committed
733 734 735

        let mut ret: Vec<P<Value>> = vec![];

736 737
        match last_inst.v {
            TreeNode_::Instruction(ref inst) => {
738
                let ref ops = inst.ops;
739
                match inst.v {
qinsoon's avatar
qinsoon committed
740 741 742 743
                    Instruction_::Return(_) |
                    Instruction_::ThreadExit |
                    Instruction_::Throw(_) |
                    Instruction_::TailCall(_) => {
744 745 746 747
                        // they do not have explicit liveouts
                    }
                    Instruction_::Branch1(ref dest) => {
                        let mut live_outs = dest.get_arguments(&ops);
qinsoon's avatar
qinsoon committed
748
                        vec_utils::add_all_unique(&mut ret, &mut live_outs);
749
                    }
qinsoon's avatar
qinsoon committed
750 751 752 753 754
                    Instruction_::Branch2 {
                        ref true_dest,
                        ref false_dest,
                        ..
                    } => {
755 756
                        let mut live_outs = true_dest.get_arguments(&ops);
                        live_outs.append(&mut false_dest.get_arguments(&ops));
qinsoon's avatar
qinsoon committed
757

qinsoon's avatar
qinsoon committed
758
                        vec_utils::add_all_unique(&mut ret, &mut live_outs);
759
                    }
qinsoon's avatar
qinsoon committed
760 761 762 763 764
                    Instruction_::Watchpoint {
                        ref disable_dest,
                        ref resume,
                        ..
                    } => {
765
                        let mut live_outs = vec![];
qinsoon's avatar
qinsoon committed
766

767
                        if disable_dest.is_some() {
qinsoon's avatar
qinsoon committed
768 769
                            live_outs
                                .append(&mut disable_dest.as_ref().unwrap().get_arguments(&ops));
770 771 772
                        }
                        live_outs.append(&mut resume.normal_dest.get_arguments(&ops));
                        live_outs.append(&mut resume.exn_dest.get_arguments(&ops));
qinsoon's avatar
qinsoon committed
773

qinsoon's avatar
qinsoon committed
774
                        vec_utils::add_all_unique(&mut ret, &mut live_outs);
775
                    }
qinsoon's avatar
qinsoon committed
776 777 778 779 780
                    Instruction_::WPBranch {
                        ref disable_dest,
                        ref enable_dest,
                        ..
                    } => {
781 782 783
                        let mut live_outs = vec![];
                        live_outs.append(&mut disable_dest.get_arguments(&ops));
                        live_outs.append(&mut enable_dest.get_arguments(&ops));
qinsoon's avatar
qinsoon committed
784
                        vec_utils::add_all_unique(&mut ret, &mut live_outs);
785
                    }
qinsoon's avatar
qinsoon committed
786 787
                    Instruction_::Call { ref resume, .. } |
                    Instruction_::CCall { ref resume, .. } |
788
                    Instruction_::SwapStackExc { ref resume, .. } |
qinsoon's avatar
qinsoon committed
789
                    Instruction_::ExnInstruction { ref resume, .. } => {
790 791 792
                        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));
qinsoon's avatar
qinsoon committed
793
                        vec_utils::add_all_unique(&mut ret, &mut live_outs);
794
                    }
qinsoon's avatar
qinsoon committed
795 796 797 798 799
                    Instruction_::Switch {
                        ref default,
                        ref branches,
                        ..
                    } => {
800 801 802 803 804
                        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));
                        }
qinsoon's avatar
qinsoon committed
805
                        vec_utils::add_all_unique(&mut ret, &mut live_outs);
806
                    }
qinsoon's avatar
qinsoon committed
807

808
                    _ => panic!("didn't expect last inst as {}", inst)
809
                }
qinsoon's avatar
qinsoon committed
810
            }
811
            _ => panic!("expect last treenode of block is a inst")
812
        }
qinsoon's avatar
qinsoon committed
813

814 815
        ret
    }
816 817 818 819 820 821

    pub fn clone_empty(&self) -> BlockContent {
        BlockContent {
            args: self.args.clone(),
            exn_arg: self.exn_arg.clone(),
            body: vec![],
822
            keepalives: self.keepalives.clone()
823 824
        }
    }
825 826
}

827 828
/// TreeNode represents a node in the AST, it could either be an instruction,
/// or an value (SSA, constant, global, etc)
829
#[derive(Debug, Clone)]
830
pub struct TreeNode {
831
    pub v: TreeNode_
832 833 834
}

impl TreeNode {
835
    /// creates a sharable Instruction TreeNode
836
    pub fn new_inst(v: Instruction) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
837
        P(TreeNode {
838
            v: TreeNode_::Instruction(v)
839 840 841
        })
    }

842
    /// creates an owned Instruction TreeNode
843
    pub fn new_boxed_inst(v: Instruction) -> Box<TreeNode> {
qinsoon's avatar
qinsoon committed
844
        Box::new(TreeNode {
845
            v: TreeNode_::Instruction(v)
846 847 848
        })
    }

qinsoon's avatar
qinsoon committed
849 850 851
    /// creates a sharable Value TreeNode
    pub fn new_value(v: P<Value>) -> P<TreeNode> {
        P(TreeNode {
852
            v: TreeNode_::Value(v)
qinsoon's avatar
qinsoon committed
853 854 855
        })
    }

856 857
    /// extracts the MuID of an SSA TreeNode
    /// if the node is not an SSA, returns None
858 859 860 861 862
    pub fn extract_ssa_id(&self) -> Option<MuID> {
        match self.v {
            TreeNode_::Value(ref pv) => {
                match pv.v {
                    Value_::SSAVar(id) => Some(id),
863
                    _ => None
864
                }
qinsoon's avatar
qinsoon committed
865
            }
866
            _ => None
867 868 869
        }
    }

870 871 872
    /// clones the value from the TreeNode
    /// * if this is a Instruction TreeNode, returns its first result value
    /// * if this is a value, returns a clone of it
873
    pub fn clone_value(&self) -> P<Value> {
qinsoon's avatar
qinsoon committed
874 875 876 877 878 879 880
        self.as_value().clone()
    }

    /// returns the value from the TreeNode
    /// * if this is a Instruction TreeNode, returns its first result value
    /// * if this is a value, returns a clone of it
    pub fn as_value(&self) -> &P<Value> {
881
        match self.v {
qinsoon's avatar
qinsoon committed
882
            TreeNode_::Value(ref val) => val,
883 884 885
            TreeNode_::Instruction(ref inst) => {
                let vals = inst.value.as_ref().unwrap();
                if vals.len() != 1 {
qinsoon's avatar
qinsoon committed
886 887 888 889
                    panic!(
                        "we expect an inst with 1 value, but found multiple or zero \
                         (it should not be here - folded as a child)"
                    );
890
                }
qinsoon's avatar
qinsoon committed
891
                &vals[0]
892 893 894 895
            }
        }
    }

896
    /// consumes the TreeNode, returns the value in it (or None if it is not a value)
897 898 899
    pub fn into_value(self) -> Option<P<Value>> {
        match self.v {
            TreeNode_::Value(val) => Some(val),
900
            _ => None
901 902 903
        }
    }

904
    /// consumes the TreeNode, returns the instruction in it (or None if it is not an instruction)
905 906 907
    pub fn into_inst(self) -> Option<Instruction> {
        match self.v {
            TreeNode_::Instruction(inst) => Some(inst),
908
            _ => None
909 910
        }
    }
911

912 913 914 915 916 917 918 919
    /// consumes the TreeNode, returns the instruction in it (or None if it is not an instruction)
    pub fn as_inst_ref(&self) -> &Instruction {
        match &self.v {
            &TreeNode_::Instruction(ref inst) => inst,
            _ => panic!("expected inst")
        }
    }

920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937
    // The type of the node (for a value node)
    pub fn ty(&self) -> P<MuType> {
        match self.v {
            TreeNode_::Instruction(ref inst) => {
                if inst.value.is_some() {
                    let ref value = inst.value.as_ref().unwrap();
                    if value.len() != 1 {
                        panic!("the node {} does not have one result value", self);
                    }

                    value[0].ty.clone()
                } else {
                    panic!("expected result from the node {}", self);
                }
            }
            TreeNode_::Value(ref pv) => pv.ty.clone()
        }
    }
938 939 940 941 942 943
}

impl fmt::Display for TreeNode {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self.v {
            TreeNode_::Value(ref pv) => pv.fmt(f),
944
            TreeNode_::Instruction(ref inst) => write!(f, "({})", inst)
945 946 947 948
        }
    }
}

949
/// TreeNode_ is used for pattern matching for TreeNode
950
#[derive(Debug, Clone)]
951 952
pub enum TreeNode_ {
    Value(P<Value>),
953
    Instruction(Instruction)
954 955
}

956 957 958 959 960
/// Value represents a value in the tree, it could be SSA variables, constants, globals,
/// which all will appear in Mu IR. Value may also represent a memory (as in transformed tree,
/// we need to represent memory as well)
///
/// Value should always be used with P<Value> (sharable)
961
#[derive(PartialEq)]
962 963 964
pub struct Value {
    pub hdr: MuEntityHeader,
    pub ty: P<MuType>,
965
    pub v: Value_
966 967
}

qinsoon's avatar
qinsoon committed
968
rodal_struct!(Value { hdr, ty, v });
969

970
impl Value {
971
    /// creates an int constant value
972
    pub fn make_int_const(id: MuID, val: u64) -> P<Value> {
973 974 975 976
        Value::make_int_const_ty(id, UINT32_TYPE.clone(), val)
    }

    pub fn make_int_const_ty(id: MuID, ty: P<MuType>, val: u64) -> P<Value> {
qinsoon's avatar
qinsoon committed
977
        P(Value {
978
            hdr: MuEntityHeader::unnamed(id),
979
            ty: ty,
980
            v: Value_::Constant(Constant::Int(val))
981 982
        })
    }
qinsoon's avatar
qinsoon committed
983

984 985 986
    pub fn is_mem(&self) -> bool {
        match self.v {
            Value_::Memory(_) => true,
987
            _ => false
988 989
        }
    }
990 991

    pub fn is_reg(&self) -> bool {
992
        match self.v {
993
            Value_::SSAVar(_) => true,
994
            _ => false
995 996 997 998 999 1000
        }
    }

    pub fn is_const(&self) -> bool {
        match self.v {
            Value_::Constant(_) => true,
1001
            _ => false
1002 1003 1004
        }
    }

1005 1006 1007
    /// disguises a value as another type.
    /// This is usually used for treat an integer type as an integer of a different length
    /// This method is unsafe
1008
    pub unsafe fn as_type(&self, ty: P<MuType>) -> P<Value> {
qinsoon's avatar
qinsoon committed
1009
        P(Value {
1010 1011
            hdr: self.hdr.clone(),
            ty: ty,
1012
            v: self.v.clone()
1013 1014 1015
        })
    }

1016 1017 1018
    pub fn is_int_ex_const(&self) -> bool {
        match self.v {
            Value_::Constant(Constant::IntEx(_)) => true,
1019
            _ => false
1020 1021 1022 1023
        }
    }


1024 1025 1026 1027
    pub fn is_int_const(&self) -> bool {
        match self.v {
            Value_::Constant(Constant::Int(_)) => true,
            Value_::Constant(Constant::NullRef) => true,
1028
            _ => false
1029 1030
        }
    }
1031

1032 1033 1034 1035
    pub fn is_fp_const(&self) -> bool {
        match self.v {
            Value_::Constant(Constant::Float(_)) => true,
            Value_::Constant(Constant::Double(_)) => true,
1036
            _ => false
1037 1038
        }
    }
1039

1040
    pub fn extract_int_const(&self) -> Option<u64> {
1041
        match self.v {
1042
            Value_::Constant(Constant::Int(val)) => Some(val),
qinsoon's avatar
qinsoon committed
1043
            Value_::Constant(Constant::NullRef) => Some(0),
1044
            _ => None
1045 1046 1047
        }
    }

1048 1049 1050
    pub fn extract_int_ex_const(&self) -> Vec<u64> {
        match self.v {
            Value_::Constant(Constant::IntEx(ref val)) => val.clone(),
1051
            _ => panic!("expect int ex const")
1052 1053 1054
        }
    }

1055 1056 1057
    pub fn extract_ssa_id(&self) -> Option<MuID> {
        match self.v {
            Value_::SSAVar(id) => Some(id),
1058
            _ => None
1059 1060
        }
    }
qinsoon's avatar
qinsoon committed
1061 1062 1063 1064

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

qinsoon's avatar
qinsoon committed
1070
const DISPLAY_ID: bool = true;
1071
const DISPLAY_TYPE: bool = true;
1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083
const PRINT_ABBREVIATE_NAME: bool = true;

impl fmt::Debug for Value {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", self)
    }
}

impl fmt::Display for Value {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        if DISPLAY_TYPE {
            match self.v {
qinsoon's avatar
qinsoon committed
1084 1085 1086
                Value_::SSAVar(_) => write!(f, "{}(%{})", self.ty, self.hdr),
                Value_::Constant(ref c) => write!(f, "{}({})", self.ty, c),
                Value_::Global(ref ty) => write!(f, "{}(@{})", ty, self.hdr),
1087
                Value_::Memory(ref mem) => write!(f, "%{}{})", self.hdr, mem)
1088 1089 1090
            }
        } else {
            match self.v {
qinsoon's avatar
qinsoon committed
1091 1092 1093
                Value_::SSAVar(_) => write!(f, "%{}", self.hdr),
                Value_::Constant(ref c) => write!(f, "{}", c),
                Value_::Global(_) => write!(f, "@{}", self.hdr),
1094
                Value_::Memory(ref mem) => write!(f, "%{}{}", self.hdr, mem)
1095 1096 1097 1098 1099
            }
        }
    }
}

1100
/// Value_ is used for pattern matching for Value
1101
#[derive(Debug, Clone, PartialEq)]
1102 1103 1104 1105
pub enum Value_ {
    SSAVar(MuID),
    Constant(Constant),
    Global(P<MuType>), // what type is this global (without IRef)
1106
    Memory(MemoryLocation)
1107 1108
}

1109 1110
rodal_enum!(Value_{(SSAVar: id), (Constant: val), (Global: ty), (Memory: location)});

1111
/// SSAVarEntry represent compilation info for an SSA variable
qinsoon's avatar
qinsoon committed
1112
//  FIXME: Issue#18
1113 1114 1115 1116 1117
#[derive(Debug)]
pub struct SSAVarEntry {
    val: P<Value>,

    // how many times this entry is used
1118
    // available after DefUse pass
1119 1120 1121
    use_count: AtomicUsize,

    // this field is only used during TreeGeneration pass
qinsoon's avatar
qinsoon committed
1122 1123 1124
    expr: Option<Instruction>,

    // some ssa vars (such as int128) needs to be split into smaller vars
1125
    split: Option<Vec<P<Value>>>
1126 1127 1128 1129 1130 1131 1132
}

impl SSAVarEntry {
    pub fn new(val: P<Value>) -> SSAVarEntry {
        let ret = SSAVarEntry {
            val: val,
            use_count: ATOMIC_USIZE_INIT,
qinsoon's avatar
qinsoon committed
1133
            expr: None,
1134
            split: None
1135
        };
qinsoon's avatar
qinsoon committed
1136

1137
        ret.use_count.store(0, Ordering::SeqCst);
qinsoon's avatar
qinsoon committed
1138

1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150