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.7% of users enabled 2FA.

ir.rs 32.8 KB
Newer Older
qinsoon's avatar
qinsoon committed
1
2
3
4
5
use ptr::P;
use types::*;
use inst::*;
use op::*;

6
use utils::vec_utils;
7
use utils::LinkedHashMap;
8
use utils::LinkedHashSet;
9

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

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

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

24
25
pub type OpIndex = usize;

qinsoon's avatar
qinsoon committed
26
27
28
lazy_static! {
    pub static ref MACHINE_ID : AtomicUsize = {
        let a = ATOMIC_USIZE_INIT;
29
        a.store(MACHINE_ID_START, Ordering::SeqCst);
qinsoon's avatar
qinsoon committed
30
31
32
33
        a
    };
    pub static ref INTERNAL_ID : AtomicUsize = {
        let a = ATOMIC_USIZE_INIT;
34
        a.store(INTERNAL_ID_START, Ordering::SeqCst);
qinsoon's avatar
qinsoon committed
35
36
        a
    };
37
38
39
} 
pub const  MACHINE_ID_START : usize = 0;
pub const  MACHINE_ID_END   : usize = 200;
qinsoon's avatar
qinsoon committed
40

41
42
43
pub const  INTERNAL_ID_START: usize = 201;
pub const  INTERNAL_ID_END  : usize = 500;
pub const  USER_ID_START    : usize = 1001;
qinsoon's avatar
qinsoon committed
44

qinsoon's avatar
qinsoon committed
45
46
47
48
49
#[deprecated]
#[allow(dead_code)]
/// it could happen that one same machine register get different IDs
/// during serialization and restoring
/// currently I hand-write fixed ID for each machine register
qinsoon's avatar
qinsoon committed
50
51
pub fn new_machine_id() -> MuID {
    let ret = MACHINE_ID.fetch_add(1, Ordering::SeqCst);
52
    if ret >= MACHINE_ID_END {
qinsoon's avatar
qinsoon committed
53
54
        panic!("machine id overflow")
    }
55
    ret
qinsoon's avatar
qinsoon committed
56
57
58
59
}

pub fn new_internal_id() -> MuID {
    let ret = INTERNAL_ID.fetch_add(1, Ordering::SeqCst);
60
    if ret >= INTERNAL_ID_END {
qinsoon's avatar
qinsoon committed
61
62
        panic!("internal id overflow")
    }
63
    ret
qinsoon's avatar
qinsoon committed
64
}
qinsoon's avatar
qinsoon committed
65

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

impl MuFunction {
76
    pub fn new(entity: MuEntityHeader, sig: P<MuFuncSig>) -> MuFunction {
77
        MuFunction {
78
            hdr: entity,
79
80
81
82
83
            sig: sig,
            cur_ver: None,
            all_vers: vec![]
        }
    }
84
85
86
87
88
89
90
91
92
    
    pub fn new_version(&mut self, fv: MuID) {
        if self.cur_ver.is_some() {
            let obsolete_ver = self.cur_ver.unwrap();
            self.all_vers.push(obsolete_ver);
        }
        
        self.cur_ver = Some(fv);
    }
93
94
}

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

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

qinsoon's avatar
[wip]    
qinsoon committed
108
    orig_content: Option<FunctionContent>,
109
    pub content: Option<FunctionContent>,
110
    is_defined: bool,
qinsoon's avatar
qinsoon committed
111
    is_compiled: bool,
qinsoon's avatar
qinsoon committed
112

113
    pub context: FunctionContext,
114

115
116
    pub force_inline: bool,

qinsoon's avatar
qinsoon committed
117
118
119
120
121
    pub block_trace: Option<Vec<MuID>> // only available after Trace Generation Pass
}

impl fmt::Display for MuFunctionVersion {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
122
        write!(f, "FuncVer {} of Func #{}", self.hdr, self.func_id)
qinsoon's avatar
qinsoon committed
123
    }
124
125
}

126
127
128
129
130
131
132
133
134
135
136
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() {
137
            write!(f, "Block Trace: {:?}\n", self.block_trace.as_ref().unwrap())
138
139
140
141
142
143
        } else {
            write!(f, "Trace not available\n")
        }
    }
}

144
impl MuFunctionVersion {
145
    pub fn new(entity: MuEntityHeader, func: MuID, sig: P<MuFuncSig>) -> MuFunctionVersion {
146
        MuFunctionVersion{
147
            hdr: entity,
qinsoon's avatar
qinsoon committed
148
            func_id: func,
qinsoon's avatar
qinsoon committed
149
            sig: sig,
qinsoon's avatar
qinsoon committed
150
            orig_content: None,
qinsoon's avatar
qinsoon committed
151
            content: None,
152
            is_defined: false,
qinsoon's avatar
qinsoon committed
153
            is_compiled: false,
qinsoon's avatar
qinsoon committed
154
            context: FunctionContext::new(),
155
156
            block_trace: None,
            force_inline: false
qinsoon's avatar
qinsoon committed
157
        }
qinsoon's avatar
qinsoon committed
158
    }
qinsoon's avatar
qinsoon committed
159

qinsoon's avatar
[wip]    
qinsoon committed
160
161
162
163
164
165
166
    pub fn new_(hdr: MuEntityHeader, id: MuID, sig: P<MuFuncSig>, content: FunctionContent, context: FunctionContext) -> MuFunctionVersion {
        MuFunctionVersion {
            hdr: hdr,
            func_id: id,
            sig: sig,
            orig_content: Some(content.clone()),
            content: Some(content),
167
            is_defined: true,
qinsoon's avatar
qinsoon committed
168
            is_compiled: false,
qinsoon's avatar
[wip]    
qinsoon committed
169
170
171
172
173
174
175
176
177
178
            context: context,
            block_trace: None,
            force_inline: false
        }
    }

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

179
    pub fn define(&mut self, content: FunctionContent) {
180
181
182
183
184
        if self.is_defined {
            panic!("alread defined the function: {}", self);
        }

        self.is_defined = true;
qinsoon's avatar
qinsoon committed
185
        self.orig_content = Some(content.clone());
qinsoon's avatar
qinsoon committed
186
        self.content = Some(content);
187
    }
188

qinsoon's avatar
qinsoon committed
189
190
191
192
193
194
195
    pub fn is_compiled(&self) -> bool {
        self.is_compiled
    }
    pub fn set_compiled(&mut self) {
        self.is_compiled = true;
    }

196
197
    pub fn new_ssa(&mut self, entity: MuEntityHeader, ty: P<MuType>) -> P<TreeNode> {
        let id = entity.id();
qinsoon's avatar
qinsoon committed
198
        let val = P(Value{
199
            hdr: entity,
qinsoon's avatar
qinsoon committed
200
201
202
203
204
            ty: ty,
            v: Value_::SSAVar(id)
        });

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

206
        P(TreeNode {
qinsoon's avatar
qinsoon committed
207
208
            op: pick_op_code_for_ssa(&val.ty),
            v: TreeNode_::Value(val)
209
210
        })
    }
211

qinsoon's avatar
qinsoon committed
212
    pub fn new_constant(&mut self, v: P<Value>) -> P<TreeNode> {
213
        P(TreeNode{
qinsoon's avatar
qinsoon committed
214
215
216
217
218
            op: pick_op_code_for_value(&v.ty),
            v: TreeNode_::Value(v)
        })
    }
    
qinsoon's avatar
qinsoon committed
219
    pub fn new_global(&mut self, v: P<Value>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
220
221
        P(TreeNode{
            op: pick_op_code_for_value(&v.ty),
qinsoon's avatar
qinsoon committed
222
223
            v: TreeNode_::Value(v)
        })
224
    }
qinsoon's avatar
qinsoon committed
225

qinsoon's avatar
qinsoon committed
226
    pub fn new_inst(&mut self, v: Instruction) -> Box<TreeNode> {
qinsoon's avatar
qinsoon committed
227
        Box::new(TreeNode{
qinsoon's avatar
qinsoon committed
228
            op: pick_op_code_for_inst(&v),
qinsoon's avatar
qinsoon committed
229
230
            v: TreeNode_::Instruction(v),
        })
qinsoon's avatar
qinsoon committed
231
    }
qinsoon's avatar
qinsoon committed
232
233

    /// get Map(CallSiteID -> FuncID) that are called by this function
234
235
    pub fn get_static_call_edges(&self) -> LinkedHashMap<MuID, MuID> {
        let mut ret = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
236
237
238

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

qinsoon's avatar
qinsoon committed
239
        for (_, block) in f_content.blocks.iter() {
qinsoon's avatar
qinsoon committed
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
            let block_content = block.content.as_ref().unwrap();

            for inst in block_content.body.iter() {
                match inst.v {
                    TreeNode_::Instruction(ref inst) => {
                        let ops = inst.ops.read().unwrap();

                        match inst.v {
                            Instruction_::ExprCall{ref data, ..}
                            | Instruction_::ExprCCall{ref data, ..}
                            | Instruction_::Call {ref data, ..}
                            | Instruction_::CCall {ref data, ..} => {
                                let ref callee = ops[data.func];

                                match callee.v {
                                    TreeNode_::Instruction(_) => {},
                                    TreeNode_::Value(ref pv) => match pv.v {
                                        Value_::Constant(Constant::FuncRef(id)) => {ret.insert(inst.id(), id);},
                                        _ => {}
                                    }
                                }
                            },
                            _ => {
                                // do nothing
                            }
                        }
                    },
                    _ => {
                        unreachable!()
                    }
                }
            }
        }

        ret
    }

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

qinsoon's avatar
qinsoon committed
280
        for (_, block) in f_content.blocks.iter() {
qinsoon's avatar
qinsoon committed
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
            let block_content = block.content.as_ref().unwrap();

            for inst in block_content.body.iter() {
                match inst.v {
                    TreeNode_::Instruction(ref inst) => {
                        match inst.v {
                            Instruction_::Throw(_) => {return true;}
                            _ => {
                                // do nothing
                            }
                        }
                    },
                    _ => {
                        unreachable!()
                    }
                }
            }
        }

        false
    }
302
303
}

304
#[derive(Clone, RustcEncodable, RustcDecodable)]
305
pub struct FunctionContent {
qinsoon's avatar
qinsoon committed
306
    pub entry: MuID,
307
308
309
310
    pub blocks: LinkedHashMap<MuID, Block>,

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

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

        write!(f, "Body:").unwrap();
320
321
322
323
324
325
326
327
        for blk_id in self.blocks.keys() {
            let block = self.get_block(*blk_id);
            write!(f, "{:?}\n", block).unwrap();
        }
        Ok(())
    }
}

328
329
impl FunctionContent {
    pub fn new(entry: MuID, blocks: LinkedHashMap<MuID, Block>) -> FunctionContent {
qinsoon's avatar
[wip]    
qinsoon committed
330
        FunctionContent {
331
332
333
            entry: entry,
            blocks: blocks,
            exception_blocks: LinkedHashSet::new()
qinsoon's avatar
[wip]    
qinsoon committed
334
335
336
        }
    }

337
    pub fn get_entry_block(&self) -> &Block {
qinsoon's avatar
qinsoon committed
338
        self.get_block(self.entry)
qinsoon's avatar
qinsoon committed
339
    } 
340

341
    pub fn get_entry_block_mut(&mut self) -> &mut Block {
qinsoon's avatar
qinsoon committed
342
343
        let entry = self.entry;
        self.get_block_mut(entry)
344
    }
345

qinsoon's avatar
qinsoon committed
346
347
    pub fn get_block(&self, id: MuID) -> &Block {
        let ret = self.blocks.get(&id);
qinsoon's avatar
qinsoon committed
348
349
        match ret {
            Some(b) => b,
qinsoon's avatar
qinsoon committed
350
            None => panic!("cannot find block #{}", id)
qinsoon's avatar
qinsoon committed
351
        }
352
    }
353

qinsoon's avatar
qinsoon committed
354
355
    pub fn get_block_mut(&mut self, id: MuID) -> &mut Block {
        let ret = self.blocks.get_mut(&id);
qinsoon's avatar
qinsoon committed
356
357
        match ret {
            Some(b) => b,
qinsoon's avatar
qinsoon committed
358
            None => panic!("cannot find block #{}", id)
qinsoon's avatar
qinsoon committed
359
        }
360
    }
361
362
}

Kunshan Wang's avatar
Kunshan Wang committed
363
#[derive(Default, Debug, RustcEncodable, RustcDecodable)]
364
pub struct FunctionContext {
365
    pub values: LinkedHashMap<MuID, SSAVarEntry>
366
367
368
369
370
}

impl FunctionContext {
    fn new() -> FunctionContext {
        FunctionContext {
371
            values: LinkedHashMap::new()
372
373
        }
    }
374
375
    
    pub fn make_temporary(&mut self, id: MuID, ty: P<MuType>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
376
377
378
379
380
381
382
        let val = P(Value{
            hdr: MuEntityHeader::unnamed(id),
            ty: ty,
            v: Value_::SSAVar(id)
        });

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

        P(TreeNode {
qinsoon's avatar
qinsoon committed
385
386
            op: pick_op_code_for_ssa(&val.ty),
            v: TreeNode_::Value(val)
387
        })
qinsoon's avatar
qinsoon committed
388
389
390
391
392
393
394
395
    }

    pub fn get_temp_display(&self, id: MuID) -> String {
        match self.get_value(id) {
            Some(entry) => format!("{}", entry.value()),
            None => "CANT_FOUND_ID".to_string()
        }
    }
qinsoon's avatar
qinsoon committed
396

qinsoon's avatar
qinsoon committed
397
    pub fn get_value(&self, id: MuID) -> Option<&SSAVarEntry> {
398
399
        self.values.get(&id)
    }
400

qinsoon's avatar
qinsoon committed
401
    pub fn get_value_mut(&mut self, id: MuID) -> Option<&mut SSAVarEntry> {
402
403
404
405
        self.values.get_mut(&id)
    }
}

qinsoon's avatar
qinsoon committed
406
#[derive(RustcEncodable, RustcDecodable, Clone)]
407
pub struct Block {
408
    pub hdr: MuEntityHeader,
409
410
    pub content: Option<BlockContent>,
    pub control_flow: ControlFlow
qinsoon's avatar
qinsoon committed
411
412
}

413
414
415
416
417
418
419
420
421
422
423
424
425
426
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(())
    }
}

427
impl Block {
428
429
    pub fn new(entity: MuEntityHeader) -> Block {
        Block{hdr: entity, content: None, control_flow: ControlFlow::default()}
430
    }
qinsoon's avatar
qinsoon committed
431
    
432
    pub fn is_receiving_exception_arg(&self) -> bool {
qinsoon's avatar
qinsoon committed
433
434
        return self.content.as_ref().unwrap().exn_arg.is_some()
    }
qinsoon's avatar
qinsoon committed
435
436
437
438
439
440
441
442
443
444

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

            content.body.len()
        }
    }
445
446
}

qinsoon's avatar
qinsoon committed
447
#[derive(Debug, RustcEncodable, RustcDecodable, Clone)]
448
pub struct ControlFlow {
qinsoon's avatar
qinsoon committed
449
    pub preds : Vec<MuID>,
450
451
452
    pub succs : Vec<BlockEdge>
}

453
impl ControlFlow {
qinsoon's avatar
qinsoon committed
454
    pub fn get_hottest_succ(&self) -> Option<MuID> {
455
456
457
458
459
        if self.succs.len() == 0 {
            None
        } else {
            let mut hot_blk = self.succs[0].target;
            let mut hot_prob = self.succs[0].probability;
460

461
462
463
464
465
466
            for edge in self.succs.iter() {
                if edge.probability > hot_prob {
                    hot_blk = edge.target;
                    hot_prob = edge.probability;
                }
            }
467

468
469
470
471
472
            Some(hot_blk)
        }
    }
}

473
474
impl fmt::Display for ControlFlow {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
475
476
        write!(f, "preds: [{}], ", vec_utils::as_str(&self.preds)).unwrap();
        write!(f, "succs: [{}]", vec_utils::as_str(&self.succs))
477
478
479
480
481
482
483
484
485
    }
}

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

qinsoon's avatar
qinsoon committed
486
#[derive(Copy, Clone, Debug, RustcEncodable, RustcDecodable)]
487
pub struct BlockEdge {
qinsoon's avatar
qinsoon committed
488
    pub target: MuID,
489
490
491
492
493
494
495
496
497
498
499
    pub kind: EdgeKind,
    pub is_exception: bool,
    pub probability: f32
}

impl fmt::Display for BlockEdge {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{} ({:?}{} - {})", self.target, self.kind, select_value!(self.is_exception, ", exceptional", ""), self.probability)
    }
}

qinsoon's avatar
qinsoon committed
500
#[derive(Copy, Clone, Debug, RustcEncodable, RustcDecodable)]
501
502
503
504
pub enum EdgeKind {
    Forward, Backward
}

qinsoon's avatar
qinsoon committed
505
#[derive(RustcEncodable, RustcDecodable, Clone)]
506
pub struct BlockContent {
507
    pub args: Vec<P<Value>>,
508
    pub exn_arg: Option<P<Value>>,
qinsoon's avatar
qinsoon committed
509
    pub body: Vec<Box<TreeNode>>,
510
    pub keepalives: Option<Vec<P<Value>>>
511
512
}

513
514
impl fmt::Debug for BlockContent {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
515
516
517
518
519
520
521
        writeln!(f, "args: {}", vec_utils::as_str(&self.args)).unwrap();
        if self.exn_arg.is_some() {
            writeln!(f, "exception arg: {}", self.exn_arg.as_ref().unwrap()).unwrap();
        }
        if self.keepalives.is_some() {
            writeln!(f, "keepalives: {}", vec_utils::as_str(self.keepalives.as_ref().unwrap())).unwrap();
        }
522
523
524
525
526
527
528
        for node in self.body.iter() {
            writeln!(f, "{}", node).unwrap();
        }
        Ok(())
    }
}

529
530
531
532
533
534
535
536
537
impl BlockContent {
    pub fn get_out_arguments(&self) -> Vec<P<Value>> {
        let n_insts = self.body.len();
        let ref last_inst = self.body[n_insts - 1];
        
        let mut ret : Vec<P<Value>> = vec![];
        
        match last_inst.v {
            TreeNode_::Instruction(ref inst) => {
qinsoon's avatar
qinsoon committed
538
                let ops = inst.ops.read().unwrap();
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
                match inst.v {
                    Instruction_::Return(_)
                    | Instruction_::ThreadExit
                    | Instruction_::Throw(_)
                    | Instruction_::TailCall(_) => {
                        // they do not have explicit liveouts
                    }
                    Instruction_::Branch1(ref dest) => {
                        let mut live_outs = dest.get_arguments(&ops);
                        vec_utils::append_unique(&mut ret, &mut live_outs);
                    }
                    Instruction_::Branch2{ref true_dest, ref false_dest, ..} => {
                        let mut live_outs = true_dest.get_arguments(&ops);
                        live_outs.append(&mut false_dest.get_arguments(&ops));
                        
                        vec_utils::append_unique(&mut ret, &mut live_outs);
                    }
                    Instruction_::Watchpoint{ref disable_dest, ref resume, ..} => {
                        let mut live_outs = vec![];
                        
                        if disable_dest.is_some() {
                            live_outs.append(&mut disable_dest.as_ref().unwrap().get_arguments(&ops));
                        }
                        live_outs.append(&mut resume.normal_dest.get_arguments(&ops));
                        live_outs.append(&mut resume.exn_dest.get_arguments(&ops));
                        
                        vec_utils::append_unique(&mut ret, &mut live_outs);
                    }
                    Instruction_::WPBranch{ref disable_dest, ref enable_dest, ..} => {
                        let mut live_outs = vec![];
                        live_outs.append(&mut disable_dest.get_arguments(&ops));
                        live_outs.append(&mut enable_dest.get_arguments(&ops));
                        vec_utils::append_unique(&mut ret, &mut live_outs);
                    }
                    Instruction_::Call{ref resume, ..}
qinsoon's avatar
qinsoon committed
574
                    | Instruction_::CCall{ref resume, ..}
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
                    | Instruction_::SwapStack{ref resume, ..}
                    | Instruction_::ExnInstruction{ref resume, ..} => {
                        let mut live_outs = vec![];
                        live_outs.append(&mut resume.normal_dest.get_arguments(&ops));
                        live_outs.append(&mut resume.exn_dest.get_arguments(&ops));
                        vec_utils::append_unique(&mut ret, &mut live_outs);
                    }
                    Instruction_::Switch{ref default, ref branches, ..} => {
                        let mut live_outs = vec![];
                        live_outs.append(&mut default.get_arguments(&ops));
                        for &(_, ref dest) in branches {
                            live_outs.append(&mut dest.get_arguments(&ops));
                        }
                        vec_utils::append_unique(&mut ret, &mut live_outs);
                    }
                    
591
                    _ => panic!("didn't expect last inst as {}", inst)
592
593
594
595
596
597
598
599
600
                }
            },
            _ => panic!("expect last treenode of block is a inst")
        }
        
        ret
    }
}

qinsoon's avatar
qinsoon committed
601
#[derive(Debug, RustcEncodable, RustcDecodable, Clone)]
qinsoon's avatar
qinsoon committed
602
603
/// always use with P<TreeNode>
pub struct TreeNode {
604
605
    pub op: OpCode,
    pub v: TreeNode_,
qinsoon's avatar
qinsoon committed
606
607
}

608
impl TreeNode {
609
    // this is a hack to allow creating TreeNode without using a &mut MuFunctionVersion
qinsoon's avatar
qinsoon committed
610
    pub fn new_inst(v: Instruction) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
611
        P(TreeNode{
qinsoon's avatar
qinsoon committed
612
            op: pick_op_code_for_inst(&v),
qinsoon's avatar
qinsoon committed
613
614
            v: TreeNode_::Instruction(v),
        })
qinsoon's avatar
qinsoon committed
615
616
    }

qinsoon's avatar
qinsoon committed
617
618
619
620
621
622
623
    pub fn new_boxed_inst(v: Instruction) -> Box<TreeNode> {
        Box::new(TreeNode{
            op: pick_op_code_for_inst(&v),
            v: TreeNode_::Instruction(v),
        })
    }

624
625
626
627
628
629
630
631
632
633
634
    pub fn extract_ssa_id(&self) -> Option<MuID> {
        match self.v {
            TreeNode_::Value(ref pv) => {
                match pv.v {
                    Value_::SSAVar(id) => Some(id),
                    _ => None
                }
            },
            _ => None
        }
    }
qinsoon's avatar
qinsoon committed
635

qinsoon's avatar
qinsoon committed
636
    pub fn clone_value(&self) -> P<Value> {
qinsoon's avatar
qinsoon committed
637
        match self.v {
qinsoon's avatar
qinsoon committed
638
            TreeNode_::Value(ref val) => val.clone(),
639
640
641
642
643
644
645
            TreeNode_::Instruction(ref inst) => {
                let vals = inst.value.as_ref().unwrap();
                if vals.len() != 1 {
                    panic!("we expect an inst with 1 value, but found multiple or zero (it should not be here - folded as a child)");
                }
                vals[0].clone()
            }
qinsoon's avatar
qinsoon committed
646
        }
qinsoon's avatar
qinsoon committed
647
648
    }

qinsoon's avatar
qinsoon committed
649
650
651
    pub fn into_value(self) -> Option<P<Value>> {
        match self.v {
            TreeNode_::Value(val) => Some(val),
qinsoon's avatar
qinsoon committed
652
            _ => None
qinsoon's avatar
qinsoon committed
653
654
        }
    }
qinsoon's avatar
qinsoon committed
655
656
657
658
659
660
661

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

664
665
/// use +() to display a node
impl fmt::Display for TreeNode {
qinsoon's avatar
qinsoon committed
666
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
667
        match self.v {
qinsoon's avatar
qinsoon committed
668
            TreeNode_::Value(ref pv) => pv.fmt(f),
669
            TreeNode_::Instruction(ref inst) => {
670
                write!(f, "+({})", inst)
671
            }
qinsoon's avatar
qinsoon committed
672
        }
qinsoon's avatar
qinsoon committed
673
    }
qinsoon's avatar
qinsoon committed
674
675
}

qinsoon's avatar
qinsoon committed
676
#[derive(Debug, RustcEncodable, RustcDecodable, Clone)]
qinsoon's avatar
qinsoon committed
677
pub enum TreeNode_ {
qinsoon's avatar
qinsoon committed
678
    Value(P<Value>),
679
    Instruction(Instruction)
qinsoon's avatar
qinsoon committed
680
681
682
}

/// always use with P<Value>
qinsoon's avatar
qinsoon committed
683
#[derive(PartialEq, RustcEncodable, RustcDecodable)]
qinsoon's avatar
qinsoon committed
684
pub struct Value {
685
    pub hdr: MuEntityHeader,
qinsoon's avatar
qinsoon committed
686
687
    pub ty: P<MuType>,
    pub v: Value_
qinsoon's avatar
qinsoon committed
688
689
}

690
impl Value {
qinsoon's avatar
qinsoon committed
691
692
693
694
695
696
697
698
    pub fn make_int_const(id: MuID, val: u64) -> P<Value> {
        P(Value{
            hdr: MuEntityHeader::unnamed(id),
            ty: UINT32_TYPE.clone(),
            v: Value_::Constant(Constant::Int(val))
        })
    }
    
699
700
701
702
703
704
    pub fn is_mem(&self) -> bool {
        match self.v {
            Value_::Memory(_) => true,
            _ => false
        }
    }
705
706

    pub fn is_reg(&self) -> bool {
707
        match self.v {
708
709
710
711
712
713
714
715
            Value_::SSAVar(_) => true,
            _ => false
        }
    }

    pub fn is_const(&self) -> bool {
        match self.v {
            Value_::Constant(_) => true,
716
717
718
            _ => false
        }
    }
qinsoon's avatar
qinsoon committed
719

qinsoon's avatar
qinsoon committed
720
721
722
723
724
725
726
727
    pub unsafe fn as_type(&self, ty: P<MuType>) -> P<Value> {
        P(Value{
            hdr: self.hdr.clone(),
            ty: ty,
            v: self.v.clone()
        })
    }

728
729
    pub fn is_int_const(&self) -> bool {
        match self.v {
730
731
            Value_::Constant(Constant::Int(_)) => true,
            Value_::Constant(Constant::NullRef) => true,
732
733
            _ => false
        }
qinsoon's avatar
qinsoon committed
734
    }
735
736
737
    
    pub fn extract_int_const(&self) -> u64 {
        match self.v {
738
739
            Value_::Constant(Constant::Int(val)) => val,
            Value_::Constant(Constant::NullRef)  => 0,
740
741
742
            _ => panic!("expect int const")
        }
    }
qinsoon's avatar
qinsoon committed
743

qinsoon's avatar
qinsoon committed
744
745
746
747
748
749
750
751
    pub fn extract_ssa_id(&self) -> Option<MuID> {
        match self.v {
            Value_::SSAVar(id) => Some(id),
            _ => None
        }
    }
}

qinsoon's avatar
qinsoon committed
752
const DISPLAY_TYPE : bool = true;
qinsoon's avatar
qinsoon committed
753
const PRINT_ABBREVIATE_NAME: bool = true;
754

qinsoon's avatar
qinsoon committed
755
756
757
758
759
760
impl fmt::Debug for Value {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", self)
    }
}

qinsoon's avatar
qinsoon committed
761
762
impl fmt::Display for Value {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
        if DISPLAY_TYPE {
            match self.v {
                Value_::SSAVar(_) => {
                    write!(f, "+({} %{})", self.ty, self.hdr)
                },
                Value_::Constant(ref c) => {
                    write!(f, "+({} {} @{})", self.ty, c, self.hdr)
                },
                Value_::Global(ref ty) => {
                    write!(f, "+(GLOBAL {} @{})", ty, self.hdr)
                },
                Value_::Memory(ref mem) => {
                    write!(f, "+(MEM {} %{})", mem, self.hdr)
                }
            }
        } else {
            match self.v {
                Value_::SSAVar(_) => {
                    write!(f, "%{}", self.hdr)
                },
                Value_::Constant(ref c) => {
qinsoon's avatar
qinsoon committed
784
                    write!(f, "{}", c)
785
786
787
788
789
790
791
                },
                Value_::Global(_) => {
                    write!(f, "GLOBAL @{}", self.hdr)
                },
                Value_::Memory(ref mem) => {
                    write!(f, "MEM {} %{}", mem, self.hdr)
                }
qinsoon's avatar
qinsoon committed
792
793
794
            }
        }
    }
795
796
}

qinsoon's avatar
qinsoon committed
797
#[derive(Debug, Clone, PartialEq, RustcEncodable, RustcDecodable)]
qinsoon's avatar
qinsoon committed
798
pub enum Value_ {
799
    SSAVar(MuID),
qinsoon's avatar
qinsoon committed
800
    Constant(Constant),
801
    Global(P<MuType>), // what type is this global (without IRef)
802
    Memory(MemoryLocation)
qinsoon's avatar
qinsoon committed
803
804
}

qinsoon's avatar
qinsoon committed
805
#[derive(Debug)]
qinsoon's avatar
qinsoon committed
806
pub struct SSAVarEntry {
qinsoon's avatar
qinsoon committed
807
    val: P<Value>,
808

809
810
    // how many times this entry is used
    // availalbe after DefUse pass
qinsoon's avatar
qinsoon committed
811
    use_count: AtomicUsize,
812

813
    // this field is only used during TreeGeneration pass
qinsoon's avatar
qinsoon committed
814
    expr: Option<Instruction>
815
816
}

qinsoon's avatar
qinsoon committed
817
818
impl Encodable for SSAVarEntry {
    fn encode<S: Encoder> (&self, s: &mut S) -> Result<(), S::Error> {
qinsoon's avatar
qinsoon committed
819
820
        s.emit_struct("SSAVarEntry", 3, |s| {
            try!(s.emit_struct_field("val", 0, |s| self.val.encode(s)));
qinsoon's avatar
qinsoon committed
821
            let count = self.use_count.load(Ordering::SeqCst);
qinsoon's avatar
qinsoon committed
822
823
            try!(s.emit_struct_field("use_count", 1, |s| s.emit_usize(count)));
            try!(s.emit_struct_field("expr", 2, |s| self.expr.encode(s)));
qinsoon's avatar
qinsoon committed
824
825
826
827
828
829
830
            Ok(())
        })
    }
}

impl Decodable for SSAVarEntry {
    fn decode<D: Decoder>(d: &mut D) -> Result<SSAVarEntry, D::Error> {
qinsoon's avatar
qinsoon committed
831
832
833
834
        d.read_struct("SSAVarEntry", 3, |d| {
            let val = try!(d.read_struct_field("val", 0, |d| Decodable::decode(d)));
            let count = try!(d.read_struct_field("use_count", 1, |d| d.read_usize()));
            let expr = try!(d.read_struct_field("expr", 2, |d| Decodable::decode(d)));
qinsoon's avatar
qinsoon committed
835
836
            
            let ret = SSAVarEntry {
qinsoon's avatar
qinsoon committed
837
                val: val,
qinsoon's avatar
qinsoon committed
838
839
840
841
842
843
844
845
846
847
848
                use_count: ATOMIC_USIZE_INIT,
                expr: expr
            };
            
            ret.use_count.store(count, Ordering::SeqCst);
            
            Ok(ret)
        })
    }
}

qinsoon's avatar
qinsoon committed
849
impl SSAVarEntry {
qinsoon's avatar
qinsoon committed
850
    pub fn new(val: P<Value>) -> SSAVarEntry {
qinsoon's avatar
qinsoon committed
851
        let ret = SSAVarEntry {
qinsoon's avatar
qinsoon committed
852
            val: val,
qinsoon's avatar
qinsoon committed
853
854
855
856
857
858
859
860
            use_count: ATOMIC_USIZE_INIT,
            expr: None
        };
        
        ret.use_count.store(0, Ordering::SeqCst);
        
        ret
    }
qinsoon's avatar
qinsoon committed
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875

    pub fn ty(&self) -> &P<MuType> {
        &self.val.ty
    }

    pub fn value(&self) -> &P<Value> {
        &self.val
    }

    pub fn use_count(&self) -> usize {
        self.use_count.load(Ordering::SeqCst)
    }
    pub fn increase_use_count(&self) {
        self.use_count.fetch_add(1, Ordering::SeqCst);
    }
876
877
878
    pub fn reset_use_count(&self) {
        self.use_count.store(0, Ordering::SeqCst);
    }
qinsoon's avatar
qinsoon committed
879
880
881
882

    pub fn has_expr(&self) -> bool {
        self.expr.is_some()
    }
883
884
885
    pub fn assign_expr(&mut self, expr: Instruction) {
        self.expr = Some(expr)
    }
qinsoon's avatar
qinsoon committed
886
887
888
889
    pub fn take_expr(&mut self) -> Instruction {
        debug_assert!(self.has_expr());
        self.expr.take().unwrap()
    }
890
891
}

qinsoon's avatar
qinsoon committed
892
impl fmt::Display for SSAVarEntry {
893
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
894
        write!(f, "{}", self.val)
895
896
897
    }
}

qinsoon's avatar
qinsoon committed
898
#[derive(Debug, Clone, PartialEq, RustcEncodable, RustcDecodable)]
899
pub enum Constant {
qinsoon's avatar
qinsoon committed
900
    Int(u64),
901
902
    Float(f32),
    Double(f64),
qinsoon's avatar
qinsoon committed
903
//    IRef(Address),
qinsoon's avatar
qinsoon committed
904
    FuncRef(MuID),
905
    Vector(Vec<Constant>),
906
907
    //Pointer(Address),
    NullRef,
908
909
910
    ExternSym(CName),

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

913
impl fmt::Display for Constant {
914
915
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
qinsoon's avatar
qinsoon committed
916
            &Constant::Int(v) => write!(f, "{}", v as i64),
917
918
            &Constant::Float(v) => write!(f, "{}", v),
            &Constant::Double(v) => write!(f, "{}", v),
qinsoon's avatar
qinsoon committed
919
//            &Constant::IRef(v) => write!(f, "{}", v),
qinsoon's avatar
qinsoon committed
920
            &Constant::FuncRef(v) => write!(f, "FuncRef {}", v),
921
922
923
924
925
926
927
928
929
930
            &Constant::Vector(ref v) => {
                write!(f, "[").unwrap();
                for i in 0..v.len() {
                    write!(f, "{}", v[i]).unwrap();
                    if i != v.len() - 1 {
                        write!(f, ", ").unwrap();
                    }
                }
                write!(f, "]")
            }
931
            &Constant::NullRef => write!(f, "NullRef"),
932
933
934
935
936
937
938
939
940
            &Constant::ExternSym(ref name) => write!(f, "ExternSym({})", name),

            &Constant::List(ref vec) => {
                write!(f, "List(").unwrap();
                for val in vec.iter() {
                    write!(f, "{}, ", val).unwrap();
                }
                write!(f, ")")
            }
941
942
        }
    }
qinsoon's avatar
qinsoon committed
943
944
}

qinsoon's avatar
qinsoon committed
945
#[derive(Debug, Clone, PartialEq, RustcEncodable, RustcDecodable)]
946
947
948
949
950
951
952
953
954
pub enum MemoryLocation {
    Address{
        base: P<Value>,
        offset: Option<P<Value>>,
        index: Option<P<Value>>,
        scale: Option<u8>
    },
    Symbolic{
        base: Option<P<Value>>,
955
956
        label: MuName,
        is_global: bool
957
958
959
960
961
962
963
    }
}

impl fmt::Display for MemoryLocation {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            &MemoryLocation::Address{ref base, ref offset, ref index, scale} => {
qinsoon's avatar
qinsoon committed
964
965
966
967
968
969
970
971
972
973
974
                // base
                write!(f, "[{}", base).unwrap();
                // offset
                if offset.is_some() {
                    write!(f, " + {}", offset.as_ref().unwrap()).unwrap();
                }
                // index/scale
                if index.is_some() && scale.is_some() {
                    write!(f, " + {} * {}", index.as_ref().unwrap(), scale.unwrap()).unwrap();
                }
                write!(f, "]")
975
            }
976
            &MemoryLocation::Symbolic{ref base, ref label, ..} => {
977
                if base.is_some() {
978
                    write!(f, "{}({})", label, base.as_ref().unwrap())
979
980
981
982
983
984
985
986
                } else {
                    write!(f, "{}", label)
                }
            }
        }
    }
}

987
#[repr(C)]
qinsoon's avatar
qinsoon committed
988
#[derive(Debug)] // Display, PartialEq, Clone
989
pub struct MuEntityHeader {
990
    id: MuID,
991
    name: Option<MuName>
992
993
}

qinsoon's avatar
qinsoon committed
994
995
996
997
impl Clone for MuEntityHeader {
    fn clone(&self) -> Self {
        MuEntityHeader {
            id: self.id,
998
            name: self.name.clone()
qinsoon's avatar
qinsoon committed
999
1000
1001
1002
        }
    }
}

1003
1004
1005
1006
1007
1008
use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
impl Encodable for MuEntityHeader {
    fn encode<S: Encoder> (&self, s: &mut S) -> Result<(), S::Error> {
        s.emit_struct("MuEntityHeader", 2, |s| {
            try!(s.emit_struct_field("id", 0, |s| self.id.encode(s)));
            
1009
            let name = &self.name;
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
            try!(s.emit_struct_field("name", 1, |s| name.encode(s)));
            
            Ok(())
        })
    }
}

impl Decodable for MuEntityHeader {
    fn decode<D: Decoder>(d: &mut D) -> Result<MuEntityHeader, D::Error> {
        d.read_struct("MuEntityHeader", 2, |d| {
            let id = try!(d.read_struct_field("id", 0, |d| {d.read_usize()}));
            let name = try!(d.read_struct_field("name", 1, |d| Decodable::decode(d)));
            
            Ok(MuEntityHeader{
1024
                    id: id,
1025
                    name: name
1026
1027
1028
1029
1030
                })
        })
    }
}

1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
pub fn name_check(name: MuName) -> MuName {
    let name = name.replace('.', "$");

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

        return name.to_string();
    }

    name
}

1043
1044
1045
1046
impl MuEntityHeader {
    pub fn unnamed(id: MuID) -> MuEntityHeader {
        MuEntityHeader {
            id: id,
1047
            name: None
1048
1049
1050
1051
1052
1053
        }
    }
    
    pub fn named(id: MuID, name: MuName) -> MuEntityHeader {
        MuEntityHeader {
            id: id,
1054
            name: Some(name_check(name))
1055
1056
1057
1058
1059
1060
1061
1062
        }
    }
    
    pub fn id(&self) -> MuID {
        self.id
    }
    
    pub fn name(&self) -> Option<MuName> {
1063
        self.name.clone()
1064
    }
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087

    fn abbreviate_name(&self) -> Option<MuName> {
        match self.name() {
            Some(name) => {
                let split: Vec<&str> = name.split('$').collect();

                let mut ret = "".to_string();

                for i in 0..split.len() - 1 {
                    ret.push(match split[i].chars().next() {
                        Some(c) => c,
                        None => '_'
                    });
                    ret.push('.');
                }

                ret.push_str(split.last().unwrap());

                Some(ret)
            }
            None => None
        }
    }
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097