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

ir.rs 27.2 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

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

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

qinsoon's avatar
qinsoon committed
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
52
53
54
55
56
57
58
59
60
61
62
63
64
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
}
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 {
qinsoon's avatar
qinsoon committed
76
    pub fn new(id: MuID, sig: P<MuFuncSig>) -> MuFunction {
77
        MuFunction {
78
            hdr: MuEntityHeader::unnamed(id),
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>,
107
    pub content: Option<FunctionContent>,
108
    pub context: FunctionContext,
109

qinsoon's avatar
qinsoon committed
110
111
112
113
114
    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 {
115
        write!(f, "FuncVer {} of Func #{}", self.hdr, self.func_id)
qinsoon's avatar
qinsoon committed
116
    }
117
118
}

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

137
impl MuFunctionVersion {
qinsoon's avatar
qinsoon committed
138
    pub fn new(id: MuID, func: MuID, sig: P<MuFuncSig>) -> MuFunctionVersion {
139
        MuFunctionVersion{
140
            hdr: MuEntityHeader::unnamed(id),
qinsoon's avatar
qinsoon committed
141
            func_id: func,
qinsoon's avatar
qinsoon committed
142
143
144
            sig: sig,
            content: None,
            context: FunctionContext::new(),
qinsoon's avatar
qinsoon committed
145
146
            block_trace: None
        }
qinsoon's avatar
qinsoon committed
147
    }
qinsoon's avatar
qinsoon committed
148

149
    pub fn define(&mut self, content: FunctionContent) {
qinsoon's avatar
qinsoon committed
150
        self.content = Some(content);
151
    }
152

qinsoon's avatar
qinsoon committed
153
    pub fn new_ssa(&mut self, id: MuID, ty: P<MuType>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
154
155
156
157
158
159
160
        let val = P(Value{
            hdr: MuEntityHeader::unnamed(id),
            ty: ty,
            v: Value_::SSAVar(id)
        });

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

162
        P(TreeNode {
qinsoon's avatar
qinsoon committed
163
164
            op: pick_op_code_for_ssa(&val.ty),
            v: TreeNode_::Value(val)
165
166
        })
    }
167

qinsoon's avatar
qinsoon committed
168
    pub fn new_constant(&mut self, v: P<Value>) -> P<TreeNode> {
169
        P(TreeNode{
qinsoon's avatar
qinsoon committed
170
171
172
173
174
            op: pick_op_code_for_value(&v.ty),
            v: TreeNode_::Value(v)
        })
    }
    
qinsoon's avatar
qinsoon committed
175
    pub fn new_global(&mut self, v: P<Value>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
176
177
        P(TreeNode{
            op: pick_op_code_for_value(&v.ty),
qinsoon's avatar
qinsoon committed
178
179
            v: TreeNode_::Value(v)
        })
180
    }
qinsoon's avatar
qinsoon committed
181

qinsoon's avatar
qinsoon committed
182
    pub fn new_inst(&mut self, v: Instruction) -> Box<TreeNode> {
qinsoon's avatar
qinsoon committed
183
        Box::new(TreeNode{
qinsoon's avatar
qinsoon committed
184
            op: pick_op_code_for_inst(&v),
qinsoon's avatar
qinsoon committed
185
186
            v: TreeNode_::Instruction(v),
        })
qinsoon's avatar
qinsoon committed
187
    }
188
189
}

qinsoon's avatar
qinsoon committed
190
#[derive(RustcEncodable, RustcDecodable, Clone)]
191
pub struct FunctionContent {
qinsoon's avatar
qinsoon committed
192
193
    pub entry: MuID,
    pub blocks: HashMap<MuID, Block>
194
195
}

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

        write!(f, "Body:").unwrap();
203
204
205
206
207
208
209
210
        for blk_id in self.blocks.keys() {
            let block = self.get_block(*blk_id);
            write!(f, "{:?}\n", block).unwrap();
        }
        Ok(())
    }
}

211
212
impl FunctionContent {
    pub fn get_entry_block(&self) -> &Block {
qinsoon's avatar
qinsoon committed
213
        self.get_block(self.entry)
qinsoon's avatar
qinsoon committed
214
    } 
215

216
    pub fn get_entry_block_mut(&mut self) -> &mut Block {
qinsoon's avatar
qinsoon committed
217
218
        let entry = self.entry;
        self.get_block_mut(entry)
219
    }
220

qinsoon's avatar
qinsoon committed
221
222
    pub fn get_block(&self, id: MuID) -> &Block {
        let ret = self.blocks.get(&id);
qinsoon's avatar
qinsoon committed
223
224
        match ret {
            Some(b) => b,
qinsoon's avatar
qinsoon committed
225
            None => panic!("cannot find block #{}", id)
qinsoon's avatar
qinsoon committed
226
        }
227
    }
228

qinsoon's avatar
qinsoon committed
229
230
    pub fn get_block_mut(&mut self, id: MuID) -> &mut Block {
        let ret = self.blocks.get_mut(&id);
qinsoon's avatar
qinsoon committed
231
232
        match ret {
            Some(b) => b,
qinsoon's avatar
qinsoon committed
233
            None => panic!("cannot find block #{}", id)
qinsoon's avatar
qinsoon committed
234
        }
235
    }
236
237
}

Kunshan Wang's avatar
Kunshan Wang committed
238
#[derive(Default, Debug, RustcEncodable, RustcDecodable)]
239
pub struct FunctionContext {
qinsoon's avatar
qinsoon committed
240
    pub values: HashMap<MuID, SSAVarEntry>
241
242
243
244
245
246
247
248
}

impl FunctionContext {
    fn new() -> FunctionContext {
        FunctionContext {
            values: HashMap::new()
        }
    }
249
250
    
    pub fn make_temporary(&mut self, id: MuID, ty: P<MuType>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
251
252
253
254
255
256
257
        let val = P(Value{
            hdr: MuEntityHeader::unnamed(id),
            ty: ty,
            v: Value_::SSAVar(id)
        });

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

        P(TreeNode {
qinsoon's avatar
qinsoon committed
260
261
            op: pick_op_code_for_ssa(&val.ty),
            v: TreeNode_::Value(val)
262
        })
qinsoon's avatar
qinsoon committed
263
264
265
266
267
268
269
270
    }

    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
271

qinsoon's avatar
qinsoon committed
272
    pub fn get_value(&self, id: MuID) -> Option<&SSAVarEntry> {
273
274
        self.values.get(&id)
    }
275

qinsoon's avatar
qinsoon committed
276
    pub fn get_value_mut(&mut self, id: MuID) -> Option<&mut SSAVarEntry> {
277
278
279
280
        self.values.get_mut(&id)
    }
}

qinsoon's avatar
qinsoon committed
281
#[derive(RustcEncodable, RustcDecodable, Clone)]
282
pub struct Block {
283
    pub hdr: MuEntityHeader,
284
285
    pub content: Option<BlockContent>,
    pub control_flow: ControlFlow
qinsoon's avatar
qinsoon committed
286
287
}

288
289
290
291
292
293
294
295
296
297
298
299
300
301
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(())
    }
}

302
impl Block {
qinsoon's avatar
qinsoon committed
303
    pub fn new(id: MuID) -> Block {
304
        Block{hdr: MuEntityHeader::unnamed(id), content: None, control_flow: ControlFlow::default()}
305
    }
qinsoon's avatar
qinsoon committed
306
307
308
309
    
    pub fn is_exception_block(&self) -> bool {
        return self.content.as_ref().unwrap().exn_arg.is_some()
    }
310
311
}

qinsoon's avatar
qinsoon committed
312
#[derive(Debug, RustcEncodable, RustcDecodable, Clone)]
313
pub struct ControlFlow {
qinsoon's avatar
qinsoon committed
314
    pub preds : Vec<MuID>,
315
316
317
    pub succs : Vec<BlockEdge>
}

318
impl ControlFlow {
qinsoon's avatar
qinsoon committed
319
    pub fn get_hottest_succ(&self) -> Option<MuID> {
320
321
322
323
324
        if self.succs.len() == 0 {
            None
        } else {
            let mut hot_blk = self.succs[0].target;
            let mut hot_prob = self.succs[0].probability;
325

326
327
328
329
330
331
            for edge in self.succs.iter() {
                if edge.probability > hot_prob {
                    hot_blk = edge.target;
                    hot_prob = edge.probability;
                }
            }
332

333
334
335
336
337
            Some(hot_blk)
        }
    }
}

338
339
impl fmt::Display for ControlFlow {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
340
341
        write!(f, "preds: [{}], ", vec_utils::as_str(&self.preds)).unwrap();
        write!(f, "succs: [{}]", vec_utils::as_str(&self.succs))
342
343
344
345
346
347
348
349
350
    }
}

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

qinsoon's avatar
qinsoon committed
351
#[derive(Copy, Clone, Debug, RustcEncodable, RustcDecodable)]
352
pub struct BlockEdge {
qinsoon's avatar
qinsoon committed
353
    pub target: MuID,
354
355
356
357
358
359
360
361
362
363
364
    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
365
#[derive(Copy, Clone, Debug, RustcEncodable, RustcDecodable)]
366
367
368
369
pub enum EdgeKind {
    Forward, Backward
}

qinsoon's avatar
qinsoon committed
370
#[derive(RustcEncodable, RustcDecodable, Clone)]
371
pub struct BlockContent {
372
    pub args: Vec<P<Value>>,
373
    pub exn_arg: Option<P<Value>>,
qinsoon's avatar
qinsoon committed
374
    pub body: Vec<Box<TreeNode>>,
375
    pub keepalives: Option<Vec<P<Value>>>
376
377
}

378
379
impl fmt::Debug for BlockContent {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
380
381
382
383
384
385
386
        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();
        }
387
388
389
390
391
392
393
        for node in self.body.iter() {
            writeln!(f, "{}", node).unwrap();
        }
        Ok(())
    }
}

394
395
396
397
398
399
400
401
402
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
403
                let ops = inst.ops.read().unwrap();
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
                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
439
                    | Instruction_::CCall{ref resume, ..}
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
                    | 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);
                    }
                    
                    _ => panic!("didn't expect last inst as {:?}", inst) 
                }
            },
            _ => panic!("expect last treenode of block is a inst")
        }
        
        ret
    }
}

qinsoon's avatar
qinsoon committed
466
#[derive(Debug, RustcEncodable, RustcDecodable, Clone)]
qinsoon's avatar
qinsoon committed
467
468
/// always use with P<TreeNode>
pub struct TreeNode {
469
470
    pub op: OpCode,
    pub v: TreeNode_,
qinsoon's avatar
qinsoon committed
471
472
}

473
impl TreeNode {
474
    // this is a hack to allow creating TreeNode without using a &mut MuFunctionVersion
qinsoon's avatar
qinsoon committed
475
    pub fn new_inst(v: Instruction) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
476
        P(TreeNode{
qinsoon's avatar
qinsoon committed
477
            op: pick_op_code_for_inst(&v),
qinsoon's avatar
qinsoon committed
478
479
            v: TreeNode_::Instruction(v),
        })
qinsoon's avatar
qinsoon committed
480
481
    }

482
483
484
485
486
487
488
489
490
491
492
    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
493

qinsoon's avatar
qinsoon committed
494
    pub fn clone_value(&self) -> P<Value> {
qinsoon's avatar
qinsoon committed
495
        match self.v {
qinsoon's avatar
qinsoon committed
496
            TreeNode_::Value(ref val) => val.clone(),
497
            TreeNode_::Instruction(ref inst) => {
498
                warn!("expecting a value, but we found an inst. Instead we use its first value");
499
500
501
502
503
504
                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
505
        }
qinsoon's avatar
qinsoon committed
506
507
    }

qinsoon's avatar
qinsoon committed
508
509
510
    pub fn into_value(self) -> Option<P<Value>> {
        match self.v {
            TreeNode_::Value(val) => Some(val),
qinsoon's avatar
qinsoon committed
511
            _ => None
qinsoon's avatar
qinsoon committed
512
513
        }
    }
qinsoon's avatar
qinsoon committed
514
515
}

516
517
/// use +() to display a node
impl fmt::Display for TreeNode {
qinsoon's avatar
qinsoon committed
518
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
519
        match self.v {
qinsoon's avatar
qinsoon committed
520
            TreeNode_::Value(ref pv) => pv.fmt(f),
521
            TreeNode_::Instruction(ref inst) => {
522
                write!(f, "+({})", inst)
523
            }
qinsoon's avatar
qinsoon committed
524
        }
qinsoon's avatar
qinsoon committed
525
    }
qinsoon's avatar
qinsoon committed
526
527
}

qinsoon's avatar
qinsoon committed
528
#[derive(Debug, RustcEncodable, RustcDecodable, Clone)]
qinsoon's avatar
qinsoon committed
529
pub enum TreeNode_ {
qinsoon's avatar
qinsoon committed
530
    Value(P<Value>),
531
    Instruction(Instruction)
qinsoon's avatar
qinsoon committed
532
533
534
}

/// always use with P<Value>
qinsoon's avatar
qinsoon committed
535
#[derive(Debug, PartialEq, RustcEncodable, RustcDecodable)]
qinsoon's avatar
qinsoon committed
536
pub struct Value {
537
    pub hdr: MuEntityHeader,
qinsoon's avatar
qinsoon committed
538
539
    pub ty: P<MuType>,
    pub v: Value_
qinsoon's avatar
qinsoon committed
540
541
}

542
impl Value {
qinsoon's avatar
qinsoon committed
543
544
545
546
547
548
549
550
    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))
        })
    }
    
551
552
553
554
555
556
557
    pub fn is_mem(&self) -> bool {
        match self.v {
            Value_::Memory(_) => true,
            _ => false
        }
    }
    
558
559
560
561
562
563
564
565
566
567
568
569
    pub fn is_int_reg(&self) -> bool {
        match self.v {
            Value_::SSAVar(_) => {
                if is_scalar(&self.ty) && !is_fp(&self.ty) {
                    true
                } else {
                    false
                }
            }
            _ => false
        }
    }
qinsoon's avatar
qinsoon committed
570

qinsoon's avatar
qinsoon committed
571
572
573
574
575
576
577
578
    pub unsafe fn as_type(&self, ty: P<MuType>) -> P<Value> {
        P(Value{
            hdr: self.hdr.clone(),
            ty: ty,
            v: self.v.clone()
        })
    }

579
580
581
582
583
584
585
586
587
588
589
590
    pub fn is_fp_reg(&self) -> bool {
        match self.v {
            Value_::SSAVar(_) => {
                if is_scalar(&self.ty) && is_fp(&self.ty) {
                    true
                } else {
                    false
                }
            },
            _ => false
        }
    }
qinsoon's avatar
qinsoon committed
591

592
593
    pub fn is_int_const(&self) -> bool {
        match self.v {
594
595
            Value_::Constant(Constant::Int(_)) => true,
            Value_::Constant(Constant::NullRef) => true,
596
597
            _ => false
        }
qinsoon's avatar
qinsoon committed
598
    }
599
600
601
    
    pub fn extract_int_const(&self) -> u64 {
        match self.v {
602
603
            Value_::Constant(Constant::Int(val)) => val,
            Value_::Constant(Constant::NullRef)  => 0,
604
605
606
            _ => panic!("expect int const")
        }
    }
qinsoon's avatar
qinsoon committed
607

qinsoon's avatar
qinsoon committed
608
609
610
611
612
613
614
615
616
617
618
    pub fn extract_ssa_id(&self) -> Option<MuID> {
        match self.v {
            Value_::SSAVar(id) => Some(id),
            _ => None
        }
    }
}

impl fmt::Display for Value {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self.v {
qinsoon's avatar
qinsoon committed
619
            Value_::SSAVar(_) => {
620
                write!(f, "+({} %{})", self.ty, self.hdr)
qinsoon's avatar
qinsoon committed
621
622
            },
            Value_::Constant(ref c) => {
623
                write!(f, "+({} {} @{})", self.ty, c, self.hdr)
qinsoon's avatar
qinsoon committed
624
            },
625
626
            Value_::Global(ref ty) => {
                write!(f, "+(GLOBAL {} @{})", ty, self.hdr)
627
628
            },
            Value_::Memory(ref mem) => {
629
                write!(f, "+(MEM {} %{})", mem, self.hdr)
qinsoon's avatar
qinsoon committed
630
631
632
            }
        }
    }
633
634
}

qinsoon's avatar
qinsoon committed
635
#[derive(Debug, Clone, PartialEq, RustcEncodable, RustcDecodable)]
qinsoon's avatar
qinsoon committed
636
pub enum Value_ {
637
    SSAVar(MuID),
qinsoon's avatar
qinsoon committed
638
    Constant(Constant),
639
    Global(P<MuType>), // what type is this global (without IRef)
640
    Memory(MemoryLocation)
qinsoon's avatar
qinsoon committed
641
642
}

qinsoon's avatar
qinsoon committed
643
#[derive(Debug)]
qinsoon's avatar
qinsoon committed
644
pub struct SSAVarEntry {
qinsoon's avatar
qinsoon committed
645
    val: P<Value>,
646

647
648
    // how many times this entry is used
    // availalbe after DefUse pass
qinsoon's avatar
qinsoon committed
649
    use_count: AtomicUsize,
650

651
    // this field is only used during TreeGeneration pass
qinsoon's avatar
qinsoon committed
652
    expr: Option<Instruction>
653
654
}

qinsoon's avatar
qinsoon committed
655
656
impl Encodable for SSAVarEntry {
    fn encode<S: Encoder> (&self, s: &mut S) -> Result<(), S::Error> {
qinsoon's avatar
qinsoon committed
657
658
        s.emit_struct("SSAVarEntry", 3, |s| {
            try!(s.emit_struct_field("val", 0, |s| self.val.encode(s)));
qinsoon's avatar
qinsoon committed
659
            let count = self.use_count.load(Ordering::SeqCst);
qinsoon's avatar
qinsoon committed
660
661
            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
662
663
664
665
666
667
668
            Ok(())
        })
    }
}

impl Decodable for SSAVarEntry {
    fn decode<D: Decoder>(d: &mut D) -> Result<SSAVarEntry, D::Error> {
qinsoon's avatar
qinsoon committed
669
670
671
672
        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
673
674
            
            let ret = SSAVarEntry {
qinsoon's avatar
qinsoon committed
675
                val: val,
qinsoon's avatar
qinsoon committed
676
677
678
679
680
681
682
683
684
685
686
                use_count: ATOMIC_USIZE_INIT,
                expr: expr
            };
            
            ret.use_count.store(count, Ordering::SeqCst);
            
            Ok(ret)
        })
    }
}

qinsoon's avatar
qinsoon committed
687
impl SSAVarEntry {
qinsoon's avatar
qinsoon committed
688
    pub fn new(val: P<Value>) -> SSAVarEntry {
qinsoon's avatar
qinsoon committed
689
        let ret = SSAVarEntry {
qinsoon's avatar
qinsoon committed
690
            val: val,
qinsoon's avatar
qinsoon committed
691
692
693
694
695
696
697
698
            use_count: ATOMIC_USIZE_INIT,
            expr: None
        };
        
        ret.use_count.store(0, Ordering::SeqCst);
        
        ret
    }
qinsoon's avatar
qinsoon committed
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717

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

    pub fn has_expr(&self) -> bool {
        self.expr.is_some()
    }
718
719
720
    pub fn assign_expr(&mut self, expr: Instruction) {
        self.expr = Some(expr)
    }
qinsoon's avatar
qinsoon committed
721
722
723
724
    pub fn take_expr(&mut self) -> Instruction {
        debug_assert!(self.has_expr());
        self.expr.take().unwrap()
    }
725
726
}

qinsoon's avatar
qinsoon committed
727
impl fmt::Display for SSAVarEntry {
728
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
729
        write!(f, "{}", self.val)
730
731
732
    }
}

qinsoon's avatar
qinsoon committed
733
#[derive(Debug, Clone, PartialEq, RustcEncodable, RustcDecodable)]
734
pub enum Constant {
qinsoon's avatar
qinsoon committed
735
    Int(u64),
736
737
    Float(f32),
    Double(f64),
qinsoon's avatar
qinsoon committed
738
//    IRef(Address),
qinsoon's avatar
qinsoon committed
739
    FuncRef(MuID),
740
    Vector(Vec<Constant>),
741
742
    //Pointer(Address),
    NullRef,
qinsoon's avatar
qinsoon committed
743
    ExternSym(CName)
744
745
}

746
impl fmt::Display for Constant {
747
748
749
750
751
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            &Constant::Int(v) => write!(f, "{}", v),
            &Constant::Float(v) => write!(f, "{}", v),
            &Constant::Double(v) => write!(f, "{}", v),
qinsoon's avatar
qinsoon committed
752
//            &Constant::IRef(v) => write!(f, "{}", v),
753
            &Constant::FuncRef(v) => write!(f, "{}", v),
754
755
756
757
758
759
760
761
762
763
            &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, "]")
            }
764
            &Constant::NullRef => write!(f, "NullRef"),
qinsoon's avatar
qinsoon committed
765
            &Constant::ExternSym(ref name) => write!(f, "ExternSym({})", name)
766
767
        }
    }
qinsoon's avatar
qinsoon committed
768
769
}

qinsoon's avatar
qinsoon committed
770
#[derive(Debug, Clone, PartialEq, RustcEncodable, RustcDecodable)]
771
772
773
774
775
776
777
778
779
pub enum MemoryLocation {
    Address{
        base: P<Value>,
        offset: Option<P<Value>>,
        index: Option<P<Value>>,
        scale: Option<u8>
    },
    Symbolic{
        base: Option<P<Value>>,
qinsoon's avatar
qinsoon committed
780
        label: MuName
781
782
783
784
785
786
787
    }
}

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
788
789
790
791
792
793
794
795
796
797
798
                // 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, "]")
799
800
801
            }
            &MemoryLocation::Symbolic{ref base, ref label} => {
                if base.is_some() {
802
                    write!(f, "{}({})", label, base.as_ref().unwrap())
803
804
805
806
807
808
809
810
                } else {
                    write!(f, "{}", label)
                }
            }
        }
    }
}

811
#[repr(C)]
qinsoon's avatar
qinsoon committed
812
#[derive(Debug)] // Display, PartialEq, Clone
813
pub struct MuEntityHeader {
814
815
    id: MuID,
    name: RwLock<Option<MuName>>
816
817
}

qinsoon's avatar
qinsoon committed
818
819
820
821
822
823
824
825
826
impl Clone for MuEntityHeader {
    fn clone(&self) -> Self {
        MuEntityHeader {
            id: self.id,
            name: RwLock::new(self.name.read().unwrap().clone())
        }
    }
}

827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
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)));
            
            let name = &self.name.read().unwrap();
            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{
                    id: id,
                    name: RwLock::new(name)
                })
        })
    }
}

855
856
857
858
859
860
861
862
863
864
865
impl MuEntityHeader {
    pub fn unnamed(id: MuID) -> MuEntityHeader {
        MuEntityHeader {
            id: id,
            name: RwLock::new(None)
        }
    }
    
    pub fn named(id: MuID, name: MuName) -> MuEntityHeader {
        MuEntityHeader {
            id: id,
866
            name: RwLock::new(Some(MuEntityHeader::name_check(name)))
867
868
869
870
871
872
873
874
        }
    }
    
    pub fn id(&self) -> MuID {
        self.id
    }
    
    pub fn name(&self) -> Option<MuName> {
875
        self.name.read().unwrap().clone()
876
    }
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891

    pub fn set_name(&self, name: MuName) {
        let mut name_guard = self.name.write().unwrap();
        *name_guard = Some(MuEntityHeader::name_check(name));
    }

    fn name_check(name: MuName) -> MuName {
        if name.starts_with("@") || name.starts_with("%") {
            let (_, name) = name.split_at(1);

            return name.to_string();
        }

        name
    }
892
893
894
895
896
897
898
899
900
901
902
}

impl PartialEq for MuEntityHeader {
    fn eq(&self, other: &Self) -> bool {
        self.id == other.id
    }
}

impl fmt::Display for MuEntityHeader {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        if self.name().is_none() {
qinsoon's avatar
qinsoon committed
903
            write!(f, "UNNAMED #{}", self.id)
904
905
906
907
908
909
        } else {
            write!(f, "{} #{}", self.name().unwrap(), self.id)
        }
    }
}

qinsoon's avatar
qinsoon committed
910
911
912
pub trait MuEntity {
    fn id(&self) -> MuID;
    fn name(&self) -> Option<MuName>;
913
    fn set_name(&self, name: MuName);
qinsoon's avatar
qinsoon committed
914
915
916
917
918
919
920
921
922
923
    fn as_entity(&self) -> &MuEntity;
}

impl_mu_entity!(MuFunction);
impl_mu_entity!(MuFunctionVersion);
impl_mu_entity!(Block);
impl_mu_entity!(MuType);
impl_mu_entity!(Value);
impl_mu_entity!(MuFuncSig);

qinsoon's avatar
qinsoon committed
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
impl MuEntity for TreeNode {
    fn id(&self) -> MuID {
        match self.v {
            TreeNode_::Instruction(ref inst) => inst.id(),
            TreeNode_::Value(ref pv) => pv.id()
        }
    }

    fn name(&self) -> Option<MuName> {
        match self.v {
            TreeNode_::Instruction(ref inst) => inst.name(),
            TreeNode_::Value(ref pv) => pv.name()
        }
    }

    fn set_name(&self, name: MuName) {
        match self.v {
            TreeNode_::Instruction(ref inst) => inst.set_name(name),
            TreeNode_::Value(ref pv) => pv.set_name(name)
        }
    }

    fn as_entity(&self) -> &MuEntity {
        match self.v {
            TreeNode_::Instruction(ref inst) => inst.as_entity(),
            TreeNode_::Value(ref pv) => pv.as_entity()
        }
    }
}

954
pub fn op_vector_str(vec: &Vec<OpIndex>, ops: &Vec<P<TreeNode>>) -> String {
955
956
957
958
959
960
    let mut ret = String::new();
    for i in 0..vec.len() {
        let index = vec[i];
        ret.push_str(format!("{}", ops[index]).as_str());
        if i != vec.len() - 1 {
            ret.push_str(", ");
961
        }
962
963
    }
    ret
964
}