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

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

144
145
    pub func_id: MuID,
    pub sig: P<MuFuncSig>,
qinsoon's avatar
qinsoon committed
146
    orig_content: Option<FunctionContent>, // original IR
147
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
qinsoon's avatar
qinsoon committed
930
931
932
        }
    }

933
934
    /// extracts the MuID of an SSA TreeNode
    /// if the node is not an SSA, returns None
935
936
    pub fn extract_ssa_id(&self) -> Option<MuID> {
        match self.v {
937
938
            TreeNode_::Value(ref pv) => match pv.v {
                Value_::SSAVar(id) => Some(id),
939
                _ => None
940
            },
941
            _ => None
942
943
944
        }
    }

945
946
947
    /// 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
948
    pub fn clone_value(&self) -> P<Value> {
qinsoon's avatar
qinsoon committed
949
950
951
952
953
954
955
        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> {
956
        match self.v {
qinsoon's avatar
qinsoon committed
957
            TreeNode_::Value(ref val) => val,
958
959
960
            TreeNode_::Instruction(ref inst) => {
                let vals = inst.value.as_ref().unwrap();
                if vals.len() != 1 {
qinsoon's avatar
qinsoon committed
961
962
963
964
                    panic!(
                        "we expect an inst with 1 value, but found multiple or zero \
                         (it should not be here - folded as a child)"
                    );
965
                }
qinsoon's avatar
qinsoon committed
966
                &vals[0]
967
968
969
970
            }
        }
    }

971
972
    /// consumes the TreeNode, returns the value in it (or None if it is not a
    /// value)
973
974
975
    pub fn into_value(self) -> Option<P<Value>> {
        match self.v {
            TreeNode_::Value(val) => Some(val),
976
            _ => None
977
978
979
        }
    }

980
981
    /// consumes the TreeNode, returns the instruction in it (or None if it is
    /// not an instruction)
982
983
984
    pub fn into_inst(self) -> Option<Instruction> {
        match self.v {
            TreeNode_::Instruction(inst) => Some(inst),
985
            _ => None
986
987
        }
    }
988

989
990
    /// consumes the TreeNode, returns the instruction in it (or None if it is
    /// not an instruction)
991
    pub fn as_inst(&self) -> &Instruction {
992
993
        match &self.v {
            &TreeNode_::Instruction(ref inst) => inst,
994
            _ => panic!("expected inst")
995
996
997
        }
    }

998
999
1000
1001
1002
1003
1004
    // 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 {
1005
1006
1007
1008
                        panic!(
                            "the node {} does not have one result value",
                            self
                        );
1009
1010
1011
1012
1013
1014
1015
                    }

                    value[0].ty.clone()
                } else {
                    panic!("expected result from the node {}", self);
                }
            }
1016
            TreeNode_::Value(ref pv) => pv.ty.clone()
1017
1018
        }
    }
1019
1020
1021
1022
1023
1024
}

impl fmt::Display for TreeNode {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self.v {
            TreeNode_::Value(ref pv) => pv.fmt(f),
1025
            TreeNode_::Instruction(ref inst) => write!(f, "({})", inst)
1026
1027
1028
1029
        }
    }
}

1030
/// TreeNode_ is used for pattern matching for TreeNode
1031
#[derive(Debug, Clone)]
1032
1033
pub enum TreeNode_ {
    Value(P<Value>),
1034
    Instruction(Instruction)
1035
1036
}

1037
1038
1039
/// 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)
1040
1041
///
/// Value should always be used with P<Value> (sharable)
1042
#[derive(PartialEq)]
1043
1044
1045
pub struct Value {
    pub hdr: MuEntityHeader,
    pub ty: P<MuType>,
1046
    pub v: Value_
1047
1048
}

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