To protect your data, the CISO officer has suggested users to enable GitLab 2FA as soon as possible.

ir.rs 37.1 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
            let block_content = block.content.as_ref().unwrap();

            for inst in block_content.body.iter() {
                match inst.v {
                    TreeNode_::Instruction(ref inst) => {
245
                        let ref ops = inst.ops;
qinsoon's avatar
qinsoon committed
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

                        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
363
364
365
366
367
368
369
370

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

        panic!("cannot find block {}", name)
    }
371
372
}

Kunshan Wang's avatar
Kunshan Wang committed
373
#[derive(Default, Debug, RustcEncodable, RustcDecodable)]
374
pub struct FunctionContext {
375
    pub values: LinkedHashMap<MuID, SSAVarEntry>
376
377
378
379
380
}

impl FunctionContext {
    fn new() -> FunctionContext {
        FunctionContext {
381
            values: LinkedHashMap::new()
382
383
        }
    }
384
385
    
    pub fn make_temporary(&mut self, id: MuID, ty: P<MuType>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
386
387
388
389
390
391
392
        let val = P(Value{
            hdr: MuEntityHeader::unnamed(id),
            ty: ty,
            v: Value_::SSAVar(id)
        });

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

        P(TreeNode {
qinsoon's avatar
qinsoon committed
395
396
            op: pick_op_code_for_ssa(&val.ty),
            v: TreeNode_::Value(val)
397
        })
qinsoon's avatar
qinsoon committed
398
399
400
401
402
403
404
405
    }

    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
406

qinsoon's avatar
qinsoon committed
407
    pub fn get_value(&self, id: MuID) -> Option<&SSAVarEntry> {
408
409
        self.values.get(&id)
    }
410

qinsoon's avatar
qinsoon committed
411
    pub fn get_value_mut(&mut self, id: MuID) -> Option<&mut SSAVarEntry> {
412
413
414
415
        self.values.get_mut(&id)
    }
}

qinsoon's avatar
qinsoon committed
416
#[derive(RustcEncodable, RustcDecodable, Clone)]
417
pub struct Block {
418
    pub hdr: MuEntityHeader,
419
420
    pub content: Option<BlockContent>,
    pub control_flow: ControlFlow
qinsoon's avatar
qinsoon committed
421
422
}

423
424
425
426
427
428
429
430
431
432
433
434
435
436
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(())
    }
}

437
impl Block {
438
439
    pub fn new(entity: MuEntityHeader) -> Block {
        Block{hdr: entity, content: None, control_flow: ControlFlow::default()}
440
    }
qinsoon's avatar
qinsoon committed
441
    
442
    pub fn is_receiving_exception_arg(&self) -> bool {
qinsoon's avatar
qinsoon committed
443
444
        return self.content.as_ref().unwrap().exn_arg.is_some()
    }
qinsoon's avatar
qinsoon committed
445
446
447
448
449
450
451
452
453
454

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

            content.body.len()
        }
    }
455
456
}

qinsoon's avatar
qinsoon committed
457
#[derive(Debug, RustcEncodable, RustcDecodable, Clone)]
458
pub struct ControlFlow {
qinsoon's avatar
qinsoon committed
459
    pub preds : Vec<MuID>,
460
461
462
    pub succs : Vec<BlockEdge>
}

463
impl ControlFlow {
qinsoon's avatar
qinsoon committed
464
    pub fn get_hottest_succ(&self) -> Option<MuID> {
465
466
467
468
469
        if self.succs.len() == 0 {
            None
        } else {
            let mut hot_blk = self.succs[0].target;
            let mut hot_prob = self.succs[0].probability;
470

471
472
473
474
475
476
            for edge in self.succs.iter() {
                if edge.probability > hot_prob {
                    hot_blk = edge.target;
                    hot_prob = edge.probability;
                }
            }
477

478
479
480
481
482
            Some(hot_blk)
        }
    }
}

483
484
impl fmt::Display for ControlFlow {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
485
486
        write!(f, "preds: [{}], ", vec_utils::as_str(&self.preds)).unwrap();
        write!(f, "succs: [{}]", vec_utils::as_str(&self.succs))
487
488
489
490
491
492
493
494
495
    }
}

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

qinsoon's avatar
qinsoon committed
496
#[derive(Copy, Clone, Debug, RustcEncodable, RustcDecodable)]
497
pub struct BlockEdge {
qinsoon's avatar
qinsoon committed
498
    pub target: MuID,
499
500
501
502
503
504
505
506
507
508
509
    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
510
#[derive(Copy, Clone, Debug, RustcEncodable, RustcDecodable)]
511
512
513
514
pub enum EdgeKind {
    Forward, Backward
}

qinsoon's avatar
qinsoon committed
515
#[derive(RustcEncodable, RustcDecodable, Clone)]
516
pub struct BlockContent {
517
    pub args: Vec<P<Value>>,
518
    pub exn_arg: Option<P<Value>>,
qinsoon's avatar
qinsoon committed
519
    pub body: Vec<Box<TreeNode>>,
520
    pub keepalives: Option<Vec<P<Value>>>
521
522
}

523
524
impl fmt::Debug for BlockContent {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
525
526
527
528
529
530
531
        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();
        }
532
533
534
535
536
537
538
        for node in self.body.iter() {
            writeln!(f, "{}", node).unwrap();
        }
        Ok(())
    }
}

539
540
541
542
543
544
545
546
547
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) => {
548
                let ref ops = inst.ops;
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
574
575
576
577
578
579
580
581
582
583
                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
584
                    | Instruction_::CCall{ref resume, ..}
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
                    | 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);
                    }
                    
601
                    _ => panic!("didn't expect last inst as {}", inst)
602
603
604
605
606
607
608
609
610
                }
            },
            _ => panic!("expect last treenode of block is a inst")
        }
        
        ret
    }
}

qinsoon's avatar
qinsoon committed
611
#[derive(Debug, RustcEncodable, RustcDecodable, Clone)]
qinsoon's avatar
qinsoon committed
612
613
/// always use with P<TreeNode>
pub struct TreeNode {
614
615
    pub op: OpCode,
    pub v: TreeNode_,
qinsoon's avatar
qinsoon committed
616
617
}

618
impl TreeNode {
619
    // this is a hack to allow creating TreeNode without using a &mut MuFunctionVersion
qinsoon's avatar
qinsoon committed
620
    pub fn new_inst(v: Instruction) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
621
        P(TreeNode{
qinsoon's avatar
qinsoon committed
622
            op: pick_op_code_for_inst(&v),
qinsoon's avatar
qinsoon committed
623
624
            v: TreeNode_::Instruction(v),
        })
qinsoon's avatar
qinsoon committed
625
626
    }

qinsoon's avatar
qinsoon committed
627
628
629
630
631
632
633
    pub fn new_boxed_inst(v: Instruction) -> Box<TreeNode> {
        Box::new(TreeNode{
            op: pick_op_code_for_inst(&v),
            v: TreeNode_::Instruction(v),
        })
    }

634
635
636
637
638
639
640
641
642
643
644
    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
645

qinsoon's avatar
qinsoon committed
646
    pub fn clone_value(&self) -> P<Value> {
qinsoon's avatar
qinsoon committed
647
        match self.v {
qinsoon's avatar
qinsoon committed
648
            TreeNode_::Value(ref val) => val.clone(),
649
650
651
652
653
654
655
            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
656
        }
qinsoon's avatar
qinsoon committed
657
658
    }

qinsoon's avatar
qinsoon committed
659
660
661
    pub fn into_value(self) -> Option<P<Value>> {
        match self.v {
            TreeNode_::Value(val) => Some(val),
qinsoon's avatar
qinsoon committed
662
            _ => None
qinsoon's avatar
qinsoon committed
663
664
        }
    }
qinsoon's avatar
qinsoon committed
665
666
667
668
669
670
671

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

674
675
/// use +() to display a node
impl fmt::Display for TreeNode {
qinsoon's avatar
qinsoon committed
676
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
677
        match self.v {
qinsoon's avatar
qinsoon committed
678
            TreeNode_::Value(ref pv) => pv.fmt(f),
679
            TreeNode_::Instruction(ref inst) => {
680
                write!(f, "({})", inst)
681
            }
qinsoon's avatar
qinsoon committed
682
        }
qinsoon's avatar
qinsoon committed
683
    }
qinsoon's avatar
qinsoon committed
684
685
}

qinsoon's avatar
qinsoon committed
686
#[derive(Debug, RustcEncodable, RustcDecodable, Clone)]
qinsoon's avatar
qinsoon committed
687
pub enum TreeNode_ {
qinsoon's avatar
qinsoon committed
688
    Value(P<Value>),
689
    Instruction(Instruction)
qinsoon's avatar
qinsoon committed
690
691
692
}

/// always use with P<Value>
qinsoon's avatar
qinsoon committed
693
#[derive(PartialEq, RustcEncodable, RustcDecodable)]
qinsoon's avatar
qinsoon committed
694
pub struct Value {
695
    pub hdr: MuEntityHeader,
qinsoon's avatar
qinsoon committed
696
697
    pub ty: P<MuType>,
    pub v: Value_
qinsoon's avatar
qinsoon committed
698
699
}

700
impl Value {
qinsoon's avatar
qinsoon committed
701
702
703
704
705
706
707
708
    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))
        })
    }
    
709
710
711
712
713
714
    pub fn is_mem(&self) -> bool {
        match self.v {
            Value_::Memory(_) => true,
            _ => false
        }
    }
715
716

    pub fn is_reg(&self) -> bool {
717
        match self.v {
718
719
720
721
722
723
724
725
            Value_::SSAVar(_) => true,
            _ => false
        }
    }

    pub fn is_const(&self) -> bool {
        match self.v {
            Value_::Constant(_) => true,
726
727
728
            _ => false
        }
    }
qinsoon's avatar
qinsoon committed
729

qinsoon's avatar
qinsoon committed
730
731
732
733
734
735
736
737
    pub unsafe fn as_type(&self, ty: P<MuType>) -> P<Value> {
        P(Value{
            hdr: self.hdr.clone(),
            ty: ty,
            v: self.v.clone()
        })
    }

738
739
740
741
742
743
744
745
    pub fn is_int_ex_const(&self) -> bool {
        match self.v {
            Value_::Constant(Constant::IntEx(_)) => true,
            _ => false
        }
    }


746
747
    pub fn is_int_const(&self) -> bool {
        match self.v {
748
749
            Value_::Constant(Constant::Int(_)) => true,
            Value_::Constant(Constant::NullRef) => true,
750
751
            _ => false
        }
qinsoon's avatar
qinsoon committed
752
    }
753
754
755
756
757
758
759
    pub fn is_fp_const(&self) -> bool {
        match self.v {
            Value_::Constant(Constant::Float(_)) => true,
            Value_::Constant(Constant::Double(_)) => true,
            _ => false
        }
    }
760
761
    pub fn extract_int_const(&self) -> u64 {
        match self.v {
762
763
            Value_::Constant(Constant::Int(val)) => val,
            Value_::Constant(Constant::NullRef)  => 0,
764
765
766
            _ => panic!("expect int const")
        }
    }
qinsoon's avatar
qinsoon committed
767

768
769
770
771
772
773
774
    pub fn extract_int_ex_const(&self) -> Vec<u64> {
        match self.v {
            Value_::Constant(Constant::IntEx(ref val)) => val.clone(),
            _ => panic!("expect int ex const")
        }
    }

qinsoon's avatar
qinsoon committed
775
776
777
778
779
780
    pub fn extract_ssa_id(&self) -> Option<MuID> {
        match self.v {
            Value_::SSAVar(id) => Some(id),
            _ => None
        }
    }
qinsoon's avatar
qinsoon committed
781
782
783
784
785
786
787

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

790
791
const DISPLAY_ID : bool = true;
const DISPLAY_TYPE : bool = false;
qinsoon's avatar
qinsoon committed
792
const PRINT_ABBREVIATE_NAME: bool = true;
793

qinsoon's avatar
qinsoon committed
794
795
796
797
798
799
impl fmt::Debug for Value {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", self)
    }
}

qinsoon's avatar
qinsoon committed
800
801
impl fmt::Display for Value {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
802
803
804
        if DISPLAY_TYPE {
            match self.v {
                Value_::SSAVar(_) => {
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
805
                    write!(f, "{}(%{})", self.ty, self.hdr)
806
807
                },
                Value_::Constant(ref c) => {
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
808
                    write!(f, "{}({})", self.ty, c)
809
810
                },
                Value_::Global(ref ty) => {
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
811
                    write!(f, "{}(@{})", ty, self.hdr)
812
813
                },
                Value_::Memory(ref mem) => {
814
                    write!(f, "%{}{})", self.hdr, mem)
815
816
817
818
819
820
821
822
                }
            }
        } else {
            match self.v {
                Value_::SSAVar(_) => {
                    write!(f, "%{}", self.hdr)
                },
                Value_::Constant(ref c) => {
qinsoon's avatar
qinsoon committed
823
                    write!(f, "{}", c)
824
825
                },
                Value_::Global(_) => {
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
826
                    write!(f, "@{}", self.hdr)
827
828
                },
                Value_::Memory(ref mem) => {
829
                    write!(f, "%{}{}", self.hdr, mem)
830
                }
qinsoon's avatar
qinsoon committed
831
832
833
            }
        }
    }
834
835
}

qinsoon's avatar
qinsoon committed
836
#[derive(Debug, Clone, PartialEq, RustcEncodable, RustcDecodable)]
qinsoon's avatar
qinsoon committed
837
pub enum Value_ {
838
    SSAVar(MuID),
qinsoon's avatar
qinsoon committed
839
    Constant(Constant),
840
    Global(P<MuType>), // what type is this global (without IRef)
841
    Memory(MemoryLocation)
qinsoon's avatar
qinsoon committed
842
843
}

qinsoon's avatar
qinsoon committed
844
#[derive(Debug)]
qinsoon's avatar
qinsoon committed
845
pub struct SSAVarEntry {
qinsoon's avatar
qinsoon committed
846
    val: P<Value>,
847

848
849
    // how many times this entry is used
    // availalbe after DefUse pass
qinsoon's avatar
qinsoon committed
850
    use_count: AtomicUsize,
851

852
    // this field is only used during TreeGeneration pass
qinsoon's avatar
qinsoon committed
853
854
855
856
    expr: Option<Instruction>,

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

qinsoon's avatar
qinsoon committed
859
860
impl Encodable for SSAVarEntry {
    fn encode<S: Encoder> (&self, s: &mut S) -> Result<(), S::Error> {
qinsoon's avatar
qinsoon committed
861
862
        s.emit_struct("SSAVarEntry", 3, |s| {
            try!(s.emit_struct_field("val", 0, |s| self.val.encode(s)));
qinsoon's avatar
qinsoon committed
863
            let count = self.use_count.load(Ordering::SeqCst);
qinsoon's avatar
qinsoon committed
864
865
            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
866
            try!(s.emit_struct_field("split", 3, |s| self.split.encode(s)));
qinsoon's avatar
qinsoon committed
867
868
869
870
871
872
873
            Ok(())
        })
    }
}

impl Decodable for SSAVarEntry {
    fn decode<D: Decoder>(d: &mut D) -> Result<SSAVarEntry, D::Error> {
qinsoon's avatar
qinsoon committed
874
        d.read_struct("SSAVarEntry", 3, |d| {
qinsoon's avatar
qinsoon committed
875
            let val   = try!(d.read_struct_field("val", 0, |d| Decodable::decode(d)));
qinsoon's avatar
qinsoon committed
876
            let count = try!(d.read_struct_field("use_count", 1, |d| d.read_usize()));
qinsoon's avatar
qinsoon committed
877
878
            let expr  = try!(d.read_struct_field("expr", 2, |d| Decodable::decode(d)));
            let split = try!(d.read_struct_field("split", 3, |d| Decodable::decode(d)));
qinsoon's avatar
qinsoon committed
879
880
            
            let ret = SSAVarEntry {
qinsoon's avatar
qinsoon committed
881
                val: val,
qinsoon's avatar
qinsoon committed
882
                use_count: ATOMIC_USIZE_INIT,
qinsoon's avatar
qinsoon committed
883
                expr: expr,
884
                split: split
qinsoon's avatar
qinsoon committed
885
886
887
888
889
890
891
892
893
            };
            
            ret.use_count.store(count, Ordering::SeqCst);
            
            Ok(ret)
        })
    }
}

qinsoon's avatar
qinsoon committed
894
impl SSAVarEntry {
qinsoon's avatar
qinsoon committed
895
    pub fn new(val: P<Value>) -> SSAVarEntry {
qinsoon's avatar
qinsoon committed
896
        let ret = SSAVarEntry {
qinsoon's avatar
qinsoon committed
897
            val: val,
qinsoon's avatar
qinsoon committed
898
            use_count: ATOMIC_USIZE_INIT,
qinsoon's avatar
qinsoon committed
899
900
            expr: None,
            split: None
qinsoon's avatar
qinsoon committed
901
902
903
904
905
906
        };
        
        ret.use_count.store(0, Ordering::SeqCst);
        
        ret
    }
qinsoon's avatar
qinsoon committed
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921

    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);
    }
922
923
924
    pub fn reset_use_count(&self) {
        self.use_count.store(0, Ordering::SeqCst);
    }
qinsoon's avatar
qinsoon committed
925
926
927
928

    pub fn has_expr(&self) -> bool {
        self.expr.is_some()
    }
929
930
931
    pub fn assign_expr(&mut self, expr: Instruction) {
        self.expr = Some(expr)
    }
qinsoon's avatar
qinsoon committed
932
933
934
935
    pub fn take_expr(&mut self) -> Instruction {
        debug_assert!(self.has_expr());
        self.expr.take().unwrap()
    }
qinsoon's avatar
qinsoon committed
936
937
938
939
940
941
942
943
944
945

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

qinsoon's avatar
qinsoon committed
948
impl fmt::Display for SSAVarEntry {
949
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
950
        write!(f, "{}", self.val)
951
952
953
    }
}

qinsoon's avatar
qinsoon committed
954
#[derive(Debug, Clone, PartialEq, RustcEncodable, RustcDecodable)]
955
pub enum Constant {
qinsoon's avatar
qinsoon committed
956
    Int(u64),
qinsoon's avatar
qinsoon committed
957
    IntEx(Vec<u64>),
958
959
    Float(f32),
    Double(f64),
qinsoon's avatar
qinsoon committed
960
//    IRef(Address),
qinsoon's avatar
qinsoon committed
961
    FuncRef(MuID),
962
    Vector(Vec<Constant>),
963
964
    //Pointer(Address),
    NullRef,
965
966
967
    ExternSym(CName),

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

970
impl fmt::Display for Constant {
971
972
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
qinsoon's avatar
qinsoon committed
973
            &Constant::Int(v) => write!(f, "{}", v as i64),
qinsoon's avatar
qinsoon committed
974
            &Constant::IntEx(ref v) => write!(f, "IntEx {:?}", v),
975
976
            &Constant::Float(v) => write!(f, "{}", v),
            &Constant::Double(v) => write!(f, "{}", v),
qinsoon's avatar
qinsoon committed
977
//            &Constant::IRef(v) => write!(f, "{}", v),
qinsoon's avatar
qinsoon committed
978
            &Constant::FuncRef(v) => write!(f, "FuncRef {}", v),
979
980
981
982
983
984
985
986
987
988
            &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, "]")
            }
989
            &Constant::NullRef => write!(f, "NullRef"),
990
991
992
993
994
995
996
997
998
            &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, ")")
            }
999
1000
        }
    }
qinsoon's avatar
qinsoon committed
1001
1002
}

1003
#[cfg(target_arch = "x86_64")]
qinsoon's avatar
qinsoon committed
1004
#[derive(Debug, Clone, PartialEq, RustcEncodable, RustcDecodable)]
1005
1006
1007
1008
1009
1010
1011
1012
1013
pub enum MemoryLocation {
    Address{
        base: P<Value>,
        offset: Option<P<Value>>,
        index: Option<P<Value>>,
        scale: Option<u8>
    },
    Symbolic{
        base: Option<P<Value>>,
1014
1015
        label: MuName,
        is_global: bool
1016
1017
1018
    }
}

1019
#[cfg(target_arch = "x86_64")]
1020
1021
1022
1023
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
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
                // 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, "]")
1035
            }
1036
            &MemoryLocation::Symbolic{ref base, ref label, ..} => {
1037
                if base.is_some() {
1038
                    write!(f, "{}({})", label, base.as_ref().unwrap())
1039
1040
1041
1042
1043
1044
1045
1046
                } else {
                    write!(f, "{}", label)
                }
            }
        }
    }
}