WARNING! Access to this system is limited to authorised users only.
Unauthorised users may be subject to prosecution.
Unauthorised access to this system is a criminal offence under Australian law (Federal Crimes Act 1914 Part VIA)
It is a criminal offence to:
(1) Obtain access to data without authority. -Penalty 2 years imprisonment.
(2) Damage, delete, alter or insert data without authority. -Penalty 10 years imprisonment.
User activity is monitored and recorded. Anyone using this system expressly consents to such monitoring and recording.

To protect your data, the CISO officer has suggested users to enable 2FA as soon as possible.
Currently 2.2% of users enabled 2FA.

ir.rs 51.4 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
#[cfg(feature = "realtime")]
pub use ir_rt::*;

18
use inst::*;
19 20 21 22 23 24 25
use ptr::P;
use types::*;

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

26
use std;
27
use std::default;
28
use std::fmt;
Javad Ebrahimian Amiri's avatar
Javad Ebrahimian Amiri committed
29
use std::sync::atomic::{AtomicUsize, Ordering};
30
pub use std::sync::Arc;
31

qinsoon's avatar
qinsoon committed
32 33
pub type WPID = usize;
pub type MuID = usize;
34
pub type MuName = Arc<String>;
qinsoon's avatar
qinsoon committed
35
pub type CName = MuName;
36 37

#[allow(non_snake_case)]
qinsoon's avatar
qinsoon committed
38
pub fn Mu(str: &'static str) -> MuName {
39
    Arc::new(str.to_string())
qinsoon's avatar
qinsoon committed
40
}
41
#[allow(non_snake_case)]
qinsoon's avatar
qinsoon committed
42
pub fn C(str: &'static str) -> CName {
43
    Arc::new(str.to_string())
qinsoon's avatar
qinsoon committed
44
}
45 46 47 48

pub type OpIndex = usize;

lazy_static! {
49
    pub static ref MACHINE_ID: AtomicUsize = {
Javad Ebrahimian Amiri's avatar
Javad Ebrahimian Amiri committed
50
        let a = AtomicUsize::new(0);
51 52 53
        a.store(MACHINE_ID_START, Ordering::SeqCst);
        a
    };
54
    pub static ref INTERNAL_ID: AtomicUsize = {
Javad Ebrahimian Amiri's avatar
Javad Ebrahimian Amiri committed
55
        let a = AtomicUsize::new(0);
56 57 58
        a.store(INTERNAL_ID_START, Ordering::SeqCst);
        a
    };
59 60
}
/// MuID reserved for machine registers
qinsoon's avatar
qinsoon committed
61 62
pub const MACHINE_ID_START: usize = 0;
pub const MACHINE_ID_END: usize = 200;
63

64
/// MuID reserved for internal types, etc.
qinsoon's avatar
qinsoon committed
65 66 67
pub const INTERNAL_ID_START: usize = 201;
pub const INTERNAL_ID_END: usize = 500;
pub const USER_ID_START: usize = 1001;
68 69 70

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

90 91 92
/// 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)
93
#[derive(Debug)]
94 95
pub struct MuFunction {
    pub hdr: MuEntityHeader,
qinsoon's avatar
qinsoon committed
96

97 98
    pub sig: P<MuFuncSig>,
    pub cur_ver: Option<MuID>,
99
    pub all_vers: Vec<MuID>
100 101
}

qinsoon's avatar
qinsoon committed
102 103 104 105
rodal_struct!(MuFunction {
    hdr,
    sig,
    cur_ver,
106
    all_vers
qinsoon's avatar
qinsoon committed
107
});
108

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

    /// adds a new version to this function, and it becomes the current version
120 121 122 123 124
    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
125

126 127 128 129 130 131 132 133 134 135
        self.cur_ver = Some(fv);
    }
}

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

136

137 138
// FIXME: currently part of compilation information is also stored in this data
// structure we should move them (see Issue #18)
139
rodal_named!(MuFunctionVersion);
Javad Ebrahimian Amiri's avatar
Javad Ebrahimian Amiri committed
140 141
/// MuFunctionVersion represents a specific definition of a Mu function
/// It owns the tree structure of MuIRs for the function version
142 143
pub struct MuFunctionVersion {
    pub hdr: MuEntityHeader,
144

145 146
    pub func_id: MuID,
    pub sig: P<MuFuncSig>,
qinsoon's avatar
qinsoon committed
147
    orig_content: Option<FunctionContent>, // original IR
148 149
    pub content: Option<FunctionContent>, /* IR that may have been rewritten
                                           * during compilation */
150 151 152 153
    is_defined: bool,
    is_compiled: bool,
    pub context: FunctionContext,
    pub force_inline: bool,
154 155
    pub block_trace: Option<Vec<MuID>> /* only available after Trace
                                        * Generation Pass */
156
}
qinsoon's avatar
qinsoon committed
157 158 159
rodal_struct!(Callsite {
    name,
    exception_destination,
160
    stack_arg_size
qinsoon's avatar
qinsoon committed
161
});
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
162
#[derive(Debug)]
163 164 165
pub struct Callsite {
    pub name: MuName,
    pub exception_destination: Option<MuName>,
166
    pub stack_arg_size: usize
167 168
}
impl Callsite {
qinsoon's avatar
qinsoon committed
169 170 171
    pub fn new(
        name: MuName,
        exception_destination: Option<MuName>,
172
        stack_arg_size: usize
qinsoon's avatar
qinsoon committed
173 174 175 176
    ) -> Callsite {
        Callsite {
            name: name,
            exception_destination: exception_destination,
177
            stack_arg_size: stack_arg_size
qinsoon's avatar
qinsoon committed
178
        }
179 180
    }
}
181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205
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 {
206
    /// creates an empty function version
207 208 209 210 211
    pub fn new(
        entity: MuEntityHeader,
        func: MuID,
        sig: P<MuFuncSig>
    ) -> MuFunctionVersion {
qinsoon's avatar
qinsoon committed
212
        MuFunctionVersion {
213
            hdr: entity,
214 215 216 217 218 219 220 221
            func_id: func,
            sig: sig,
            orig_content: None,
            content: None,
            is_defined: false,
            is_compiled: false,
            context: FunctionContext::new(),
            block_trace: None,
222
            force_inline: false
223 224 225
        }
    }

226
    /// creates a complete function version
qinsoon's avatar
qinsoon committed
227 228 229 230 231
    pub fn new_(
        hdr: MuEntityHeader,
        id: MuID,
        sig: P<MuFuncSig>,
        content: FunctionContent,
232
        context: FunctionContext
qinsoon's avatar
qinsoon committed
233
    ) -> MuFunctionVersion {
234 235 236 237 238 239 240 241 242 243
        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,
244
            force_inline: false
245 246 247 248 249 250 251
        }
    }

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

252
    /// defines function content
253 254 255 256 257 258 259 260 261 262 263 264 265
    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
    }
266

267 268 269 270
    pub fn set_compiled(&mut self) {
        self.is_compiled = true;
    }

271 272 273 274 275
    pub fn new_ssa(
        &mut self,
        entity: MuEntityHeader,
        ty: P<MuType>
    ) -> P<TreeNode> {
276
        let id = entity.id();
qinsoon's avatar
qinsoon committed
277
        let val = P(Value {
278
            hdr: entity,
279
            ty: ty,
280
            v: Value_::SSAVar(id)
281 282
        });

qinsoon's avatar
qinsoon committed
283 284 285
        self.context
            .values
            .insert(id, SSAVarEntry::new(val.clone()));
286 287

        P(TreeNode {
288
            v: TreeNode_::Value(val)
289 290 291
        })
    }

292 293 294 295 296 297
    pub fn new_machine_reg(&mut self, v: P<Value>) -> P<TreeNode> {
        self.context
            .values
            .insert(v.id(), SSAVarEntry::new(v.clone()));

        P(TreeNode {
298
            v: TreeNode_::Value(v)
299 300 301
        })
    }

302
    pub fn new_constant(&mut self, v: P<Value>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
303
        P(TreeNode {
304
            v: TreeNode_::Value(v)
305 306
        })
    }
qinsoon's avatar
qinsoon committed
307

308
    pub fn new_global(&mut self, v: P<Value>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
309
        P(TreeNode {
310
            v: TreeNode_::Value(v)
311 312 313
        })
    }

314 315
    pub fn new_inst(&mut self, v: Instruction) -> P<TreeNode> {
        P(TreeNode {
316
            v: TreeNode_::Instruction(v)
317 318 319
        })
    }

320
    /// gets call outedges in this function
321 322
    /// returns Map(CallSiteID -> (FuncID, has exception clause))
    pub fn get_static_call_edges(&self) -> LinkedHashMap<MuID, (MuID, bool)> {
323 324 325 326 327 328 329 330 331 332
        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) => {
333
                        let ref ops = inst.ops;
334
                        match inst.v {
335 336 337 338
                            Instruction_::ExprCall { ref data, .. }
                            | Instruction_::ExprCCall { ref data, .. }
                            | Instruction_::Call { ref data, .. }
                            | Instruction_::CCall { ref data, .. } => {
339 340 341
                                let ref callee = ops[data.func];

                                match callee.v {
qinsoon's avatar
qinsoon committed
342
                                    TreeNode_::Instruction(_) => {}
343 344 345 346 347 348
                                    TreeNode_::Value(ref pv) => {
                                        match &pv.v {
                                            &Value_::Constant(
                                                Constant::FuncRef(ref func)
                                            ) => {
                                                ret.insert(
349 350 351
                                                inst.id(),
                                                (func.id(), inst.has_exception_clause()),
                                            );
352 353
                                            }
                                            _ => {}
qinsoon's avatar
qinsoon committed
354
                                        }
355
                                    }
356
                                }
qinsoon's avatar
qinsoon committed
357
                            }
358 359 360 361 362
                            _ => {
                                // do nothing
                            }
                        }
                    }
363
                    _ => unreachable!()
364 365 366 367 368 369 370
                }
            }
        }

        ret
    }

371 372
    // 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
373
    pub fn could_throw(&self) -> bool {
374 375 376 377 378 379 380 381
        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) => {
382 383
                        if inst.is_potentially_throwing() {
                            // TODO: Do some smarter checking
384 385 386 387
                            // (e.g. if this is a CALL to a function where
                            // !could_throw,
                            // or a division where the divisor can't possibly be
                            // zero..)
388
                            return true;
389 390
                        }
                    }
391
                    _ => unreachable!()
392 393 394 395 396 397
                }
            }
        }

        false
    }
398 399 400 401 402 403 404 405 406 407 408

    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
409 410 411
                            Instruction_::TailCall(_) => {
                                return true;
                            }
412 413 414
                            _ => {
                                // do nothing
                            }
415 416
                        }
                    }
417
                    _ => unreachable!()
418 419 420 421 422 423 424 425
                }
            }
        }

        false
    }
}

426 427
/// FunctionContent contains all blocks (which include all instructions) for the
/// function
428
#[derive(Clone)]
429 430 431
pub struct FunctionContent {
    pub entry: MuID,
    pub blocks: LinkedHashMap<MuID, Block>,
432 433
    pub exception_blocks: LinkedHashSet<MuID> /* this field only valid after
                                               * control flow analysis */
434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451
}

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 {
452 453 454 455
    pub fn new(
        entry: MuID,
        blocks: LinkedHashMap<MuID, Block>
    ) -> FunctionContent {
456 457 458
        FunctionContent {
            entry: entry,
            blocks: blocks,
459
            exception_blocks: LinkedHashSet::new()
460 461 462 463 464
        }
    }

    pub fn get_entry_block(&self) -> &Block {
        self.get_block(self.entry)
qinsoon's avatar
qinsoon committed
465
    }
466 467 468 469 470 471 472 473 474 475

    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,
476
            None => panic!("cannot find block #{}", id)
477 478 479 480 481 482 483
        }
    }

    pub fn get_block_mut(&mut self, id: MuID) -> &mut Block {
        let ret = self.blocks.get_mut(&id);
        match ret {
            Some(b) => b,
484
            None => panic!("cannot find block #{}", id)
485 486
        }
    }
487

488
    pub fn get_block_by_name(&self, name: MuName) -> &Block {
489
        for block in self.blocks.values() {
490
            if block.name() == name {
491 492 493 494 495 496
                return block;
            }
        }

        panic!("cannot find block {}", name)
    }
497 498
}

499
/// FunctionContext contains compilation information about the function
500 501
// FIXME: should move this out of ast crate and bind its lifetime with
// compilation (Issue #18)
502
#[derive(Default, Debug)]
503
pub struct FunctionContext {
504
    pub values: LinkedHashMap<MuID, SSAVarEntry>
505 506 507 508 509
}

impl FunctionContext {
    fn new() -> FunctionContext {
        FunctionContext {
510
            values: LinkedHashMap::new()
511 512
        }
    }
513 514

    /// makes a TreeNode of an SSA variable
515
    pub fn make_temporary(&mut self, id: MuID, ty: P<MuType>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
516
        let val = P(Value {
517 518
            hdr: MuEntityHeader::unnamed(id),
            ty: ty,
519
            v: Value_::SSAVar(id)
520 521 522 523 524
        });

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

        P(TreeNode {
525
            v: TreeNode_::Value(val)
526 527 528
        })
    }

529
    /// shows the name for an SSA by ID
530 531 532
    pub fn get_temp_display(&self, id: MuID) -> String {
        match self.get_value(id) {
            Some(entry) => format!("{}", entry.value()),
533
            None => "CANT_FOUND_ID".to_string()
534 535 536
        }
    }

537
    /// returns a &SSAVarEntry for the given ID
538 539 540 541
    pub fn get_value(&self, id: MuID) -> Option<&SSAVarEntry> {
        self.values.get(&id)
    }

542
    /// returns a &mut SSAVarEntry for the given ID
543 544 545 546 547
    pub fn get_value_mut(&mut self, id: MuID) -> Option<&mut SSAVarEntry> {
        self.values.get_mut(&id)
    }
}

548 549
/// Block contains BlockContent, which includes all the instructions for the
/// block
550 551
//  FIXME: control_flow field should be moved out of ast crate (Issue #18)
//  FIXME: trace_hint should also be moved
552
#[derive(Clone)]
553 554
pub struct Block {
    pub hdr: MuEntityHeader,
555
    /// the actual content of this block
556
    pub content: Option<BlockContent>,
557 558 559
    /// a trace scheduling hint about where to layout this block
    pub trace_hint: TraceHint,
    /// control flow info about this block (predecessors, successors, etc)
560
    pub control_flow: ControlFlow
561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576
}

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

577 578 579 580 581 582
impl fmt::Display for Block {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", self.name())
    }
}

583
impl Block {
584
    pub fn new(entity: MuEntityHeader) -> Block {
qinsoon's avatar
qinsoon committed
585 586 587 588
        Block {
            hdr: entity,
            content: None,
            trace_hint: TraceHint::None,
589
            control_flow: ControlFlow::default()
qinsoon's avatar
qinsoon committed
590
        }
591
    }
592

qinsoon's avatar
qinsoon committed
593 594 595 596 597 598 599 600
    pub fn clear_insts(&mut self) {
        self.content.as_mut().unwrap().body.clear();
    }

    pub fn append_inst(&mut self, inst: P<TreeNode>) {
        self.content.as_mut().unwrap().body.push(inst);
    }

601
    /// does this block have an exception arguments?
602
    pub fn is_receiving_exception_arg(&self) -> bool {
qinsoon's avatar
qinsoon committed
603
        return self.content.as_ref().unwrap().exn_arg.is_some();
604 605
    }

606
    /// how many IR instruction does this block have?
607 608 609 610 611 612 613 614 615
    pub fn number_of_irs(&self) -> usize {
        if self.content.is_none() {
            0
        } else {
            let content = self.content.as_ref().unwrap();

            content.body.len()
        }
    }
616 617 618

    /// is this block ends with a conditional branch?
    pub fn ends_with_cond_branch(&self) -> bool {
qinsoon's avatar
qinsoon committed
619
        let block: &BlockContent = self.content.as_ref().unwrap();
620
        match block.body.last() {
621 622 623 624 625
            Some(node) => match node.v {
                TreeNode_::Instruction(Instruction {
                    v: Instruction_::Branch2 { .. },
                    ..
                }) => true,
626
                _ => false
627
            },
628
            None => false
629 630 631 632 633
        }
    }

    /// is this block ends with a return?
    pub fn ends_with_return(&self) -> bool {
qinsoon's avatar
qinsoon committed
634
        let block: &BlockContent = self.content.as_ref().unwrap();
635
        match block.body.last() {
636 637 638 639 640
            Some(node) => match node.v {
                TreeNode_::Instruction(Instruction {
                    v: Instruction_::Return(_),
                    ..
                }) => true,
641
                _ => false
642
            },
643
            None => false
644 645
        }
    }
646 647
}

648
/// TraceHint is a hint for the compiler to generate better trace for this block
649 650 651 652
//  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.
653 654
//  FIXME: Issue #18
#[derive(Clone, PartialEq)]
655
pub enum TraceHint {
656 657
    /// no hint provided. Trace scheduler should use its own heuristics to
    /// decide
658
    None,
659 660
    /// this block is fast path, and should be put in straightline code where
    /// possible
661 662 663 664
    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
665
    ReturnSink
666 667
}

668
/// ControlFlow stores compilation info about control flows of a block
669
//  FIXME: Issue #18
670
#[derive(Debug, Clone)]
671
pub struct ControlFlow {
qinsoon's avatar
qinsoon committed
672
    pub preds: Vec<MuID>,
673
    pub succs: Vec<BlockEdge>
674 675 676
}

impl ControlFlow {
677 678
    /// returns the successor with highest branching probability
    /// (in case of tie, returns first met successor)
679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706
    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
707 708
        ControlFlow {
            preds: vec![],
709
            succs: vec![]
qinsoon's avatar
qinsoon committed
710
        }
711 712 713
    }
}

714
/// BlockEdge represents an edge in control flow graph
715
#[derive(Copy, Clone, Debug)]
716 717 718 719
pub struct BlockEdge {
    pub target: MuID,
    pub kind: EdgeKind,
    pub is_exception: bool,
720
    pub probability: f32
721 722 723 724
}

impl fmt::Display for BlockEdge {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
725 726 727 728 729 730 731 732
        write!(
            f,
            "{} ({:?}{} - {})",
            self.target,
            self.kind,
            select_value!(self.is_exception, ", exceptional", ""),
            self.probability
        )
733 734 735
    }
}

736
#[derive(Copy, Clone, Debug)]
737
pub enum EdgeKind {
qinsoon's avatar
qinsoon committed
738
    Forward,
739
    Backward
740 741
}

742 743
/// BlockContent describes arguments to this block, and owns all the IR
/// instructions
744
#[derive(Clone)]
745 746 747
pub struct BlockContent {
    pub args: Vec<P<Value>>,
    pub exn_arg: Option<P<Value>>,
748
    pub body: Vec<P<TreeNode>>,
749
    pub keepalives: Option<Vec<P<Value>>>
750 751 752 753 754 755
}

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() {
756 757
            writeln!(f, "exception arg: {}", self.exn_arg.as_ref().unwrap())
                .unwrap();
758 759
        }
        if self.keepalives.is_some() {
qinsoon's avatar
qinsoon committed
760 761 762 763
            writeln!(
                f,
                "keepalives: {}",
                vec_utils::as_str(self.keepalives.as_ref().unwrap())
764 765
            )
            .unwrap();
766 767 768 769 770 771 772 773 774
        }
        for node in self.body.iter() {
            writeln!(f, "{}", node).unwrap();
        }
        Ok(())
    }
}

impl BlockContent {
775 776 777 778
    pub fn get_own_args(&self, index: usize) -> &P<Value> {
        &self.args[index]
    }

779
    /// returns all the arguments passed to its successors
780 781 782
    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
783 784 785

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

786 787
        match last_inst.v {
            TreeNode_::Instruction(ref inst) => {
788
                let ref ops = inst.ops;
789
                match inst.v {
790 791 792 793
                    Instruction_::Return(_)
                    | Instruction_::ThreadExit
                    | Instruction_::Throw(_)
                    | Instruction_::TailCall(_) => {
794 795 796 797
                        // they do not have explicit liveouts
                    }
                    Instruction_::Branch1(ref dest) => {
                        let mut live_outs = dest.get_arguments(&ops);
qinsoon's avatar
qinsoon committed
798
                        vec_utils::add_all_unique(&mut ret, &mut live_outs);
799
                    }
qinsoon's avatar
qinsoon committed
800 801 802 803 804
                    Instruction_::Branch2 {
                        ref true_dest,
                        ref false_dest,
                        ..
                    } => {
805 806
                        let mut live_outs = true_dest.get_arguments(&ops);
                        live_outs.append(&mut false_dest.get_arguments(&ops));
qinsoon's avatar
qinsoon committed
807

qinsoon's avatar
qinsoon committed
808
                        vec_utils::add_all_unique(&mut ret, &mut live_outs);
809
                    }
qinsoon's avatar
qinsoon committed
810 811 812 813 814
                    Instruction_::Watchpoint {
                        ref disable_dest,
                        ref resume,
                        ..
                    } => {
815
                        let mut live_outs = vec![];
qinsoon's avatar
qinsoon committed
816

817
                        if disable_dest.is_some() {
818 819 820 821 822 823
                            live_outs.append(
                                &mut disable_dest
                                    .as_ref()
                                    .unwrap()
                                    .get_arguments(&ops)
                            );
824
                        }
825 826 827 828 829
                        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
830

qinsoon's avatar
qinsoon committed
831
                        vec_utils::add_all_unique(&mut ret, &mut live_outs);
832
                    }
qinsoon's avatar
qinsoon committed
833 834 835 836 837
                    Instruction_::WPBranch {
                        ref disable_dest,
                        ref enable_dest,
                        ..
                    } => {
838 839 840
                        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
841
                        vec_utils::add_all_unique(&mut ret, &mut live_outs);
842
                    }
843 844 845 846
                    Instruction_::Call { ref resume, .. }
                    | Instruction_::CCall { ref resume, .. }
                    | Instruction_::SwapStackExc { ref resume, .. }
                    | Instruction_::ExnInstruction { ref resume, .. } => {
847
                        let mut live_outs = vec![];
848 849 850 851 852
                        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
853
                        vec_utils::add_all_unique(&mut ret, &mut live_outs);
854
                    }
qinsoon's avatar
qinsoon committed
855 856 857 858 859
                    Instruction_::Switch {
                        ref default,
                        ref branches,
                        ..
                    } => {
860 861 862 863 864
                        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
865
                        vec_utils::add_all_unique(&mut ret, &mut live_outs);
866
                    }
qinsoon's avatar
qinsoon committed
867

868
                    _ => panic!("didn't expect last inst as {}", inst)
869
                }
qinsoon's avatar
qinsoon committed
870
            }
871
            _ => panic!("expect last treenode of block is a inst")
872
        }
qinsoon's avatar
qinsoon committed
873

874 875
        ret
    }
876 877 878 879 880 881

    pub fn clone_empty(&self) -> BlockContent {
        BlockContent {
            args: self.args.clone(),
            exn_arg: self.exn_arg.clone(),
            body: vec![],
882
            keepalives: self.keepalives.clone()
883 884
        }
    }
885 886
}

887 888
/// TreeNode represents a node in the AST, it could either be an instruction,
/// or an value (SSA, constant, global, etc)
889
#[derive(Debug, Clone)]
890
pub struct TreeNode {
891
    pub v: TreeNode_
892 893 894
}

impl TreeNode {
895
    /// creates a sharable Instruction TreeNode
896
    pub fn new_inst(v: Instruction) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
897
        P(TreeNode {
898
            v: TreeNode_::Instruction(v)
899 900 901
        })
    }

qinsoon's avatar
qinsoon committed
902 903 904
    /// creates a sharable Value TreeNode
    pub fn new_value(v: P<Value>) -> P<TreeNode> {
        P(TreeNode {
905
            v: TreeNode_::Value(v)
qinsoon's avatar
qinsoon committed
906 907 908
        })
    }

qinsoon's avatar
qinsoon committed
909 910 911 912
    /// is instruction
    pub fn is_inst(&self) -> bool {
        match self.v {
            TreeNode_::Instruction(_) => true,
913
            _ => false
qinsoon's avatar
qinsoon committed
914 915 916 917 918 919 920
        }
    }

    /// is value
    pub fn is_value(&self) -> bool {
        match self.v {
            TreeNode_::Value(_) => true,
921
            _ => false
qinsoon's avatar
qinsoon committed
922 923 924 925 926 927 928
        }
    }

    /// is constant value
    pub fn is_const_value(&self) -> bool {
        match self.v {
            TreeNode_::Value(ref val) => val.is_const(),
929
            _ => false