ir.rs 16.9 KB
Newer Older
1
use ast::ptr::P;
2
use ast::types::*;
3
use ast::inst::*;
4
use ast::op::*;
5
use utils::vec_utils::as_str as vector_as_str;
6
use utils::vec_utils;
7

8
use std::collections::HashMap;
qinsoon's avatar
qinsoon committed
9
use std::fmt;
10
use std::default;
qinsoon's avatar
qinsoon committed
11
use std::cell::Cell;
qinsoon's avatar
qinsoon committed
12

qinsoon's avatar
qinsoon committed
13 14
pub type WPID  = usize;
pub type MuID  = usize;
qinsoon's avatar
qinsoon committed
15
pub type MuName = &'static str;
qinsoon's avatar
qinsoon committed
16 17
pub type Address = usize; // TODO: replace this with Address(usize)

18 19
pub type OpIndex = usize;

20 21
#[derive(Debug)]
pub struct MuFunction {
qinsoon's avatar
qinsoon committed
22
    pub fn_name: MuName,
23
    pub sig: P<MuFuncSig>,
qinsoon's avatar
qinsoon committed
24 25
    pub cur_ver: Option<MuName>,
    pub all_vers: Vec<MuName>
26 27 28
}

impl MuFunction {
qinsoon's avatar
qinsoon committed
29
    pub fn new(fn_name: MuName, sig: P<MuFuncSig>) -> MuFunction {
30 31 32 33 34 35 36 37 38
        MuFunction {
            fn_name: fn_name,
            sig: sig,
            cur_ver: None,
            all_vers: vec![]
        }
    }
}

39
#[derive(Debug)]
40
pub struct MuFunctionVersion {
qinsoon's avatar
qinsoon committed
41 42
    pub fn_name: MuName,
    pub version: MuName,
43

qinsoon's avatar
qinsoon committed
44
    pub sig: P<MuFuncSig>,
45
    pub content: Option<FunctionContent>,
46
    pub context: FunctionContext,
47

qinsoon's avatar
qinsoon committed
48
    pub block_trace: Option<Vec<MuName>> // only available after Trace Generation Pass
49 50
}

51 52
pub const RESERVED_NODE_IDS_FOR_MACHINE : usize = 100;

53
impl MuFunctionVersion {
qinsoon's avatar
qinsoon committed
54
    pub fn new(fn_name: MuName, ver: MuName, sig: P<MuFuncSig>) -> MuFunctionVersion {
55
        MuFunctionVersion{
56
            fn_name: fn_name,
57
            version: ver,
58 59 60
            sig: sig,
            content: None,
            context: FunctionContext::new(),
61 62
            block_trace: None}
    }
63

64 65 66
    pub fn define(&mut self, content: FunctionContent) {
        self.content = Some(content)
    }
67

qinsoon's avatar
qinsoon committed
68
    pub fn new_ssa(&mut self, id: MuID, tag: MuName, ty: P<MuType>) -> P<TreeNode> {
69
        self.context.value_tags.insert(tag, id);
70
        self.context.values.insert(id, SSAVarEntry{id: id, tag: tag, ty: ty.clone(), use_count: Cell::new(0), expr: None});
71

72
        P(TreeNode {
qinsoon's avatar
qinsoon committed
73
            id: id,
74
            op: pick_op_code_for_ssa(&ty),
qinsoon's avatar
qinsoon committed
75 76 77 78 79
            v: TreeNode_::Value(P(Value{
                tag: tag,
                ty: ty,
                v: Value_::SSAVar(id)
            }))
80 81
        })
    }
82

83
    pub fn new_constant(&mut self, id: MuID, v: P<Value>) -> P<TreeNode> {
84
        P(TreeNode{
85
            id: id,
qinsoon's avatar
qinsoon committed
86 87 88 89 90
            op: pick_op_code_for_value(&v.ty),
            v: TreeNode_::Value(v)
        })
    }
    
91
    pub fn new_global(&mut self, id: MuID, v: P<Value>) -> P<TreeNode> {
qinsoon's avatar
qinsoon committed
92
        P(TreeNode{
93
            id: id,
qinsoon's avatar
qinsoon committed
94
            op: pick_op_code_for_value(&v.ty),
qinsoon's avatar
qinsoon committed
95 96
            v: TreeNode_::Value(v)
        })
97
    }
98

99
    pub fn new_inst(&mut self, id: MuID, v: Instruction) -> P<TreeNode> {
100
        P(TreeNode{
101
            id: id,
102
            op: pick_op_code_for_inst(&v),
103 104
            v: TreeNode_::Instruction(v),
        })
105
    }
106 107
}

108 109
#[derive(Debug)]
pub struct FunctionContent {
qinsoon's avatar
qinsoon committed
110 111
    pub entry: MuName,
    pub blocks: HashMap<MuName, Block>
112 113 114 115
}

impl FunctionContent {
    pub fn get_entry_block(&self) -> &Block {
qinsoon's avatar
qinsoon committed
116
        self.get_block(self.entry)
117
    }
118

119
    pub fn get_entry_block_mut(&mut self) -> &mut Block {
qinsoon's avatar
qinsoon committed
120 121
        let entry = self.entry;
        self.get_block_mut(entry)
122
    }
123

qinsoon's avatar
qinsoon committed
124
    pub fn get_block(&self, tag: MuName) -> &Block {
qinsoon's avatar
qinsoon committed
125 126 127 128 129
        let ret = self.blocks.get(tag);
        match ret {
            Some(b) => b,
            None => panic!("cannot find block {}", tag)
        }
130
    }
131

qinsoon's avatar
qinsoon committed
132
    pub fn get_block_mut(&mut self, tag: MuName) -> &mut Block {
qinsoon's avatar
qinsoon committed
133 134 135 136 137
        let ret = self.blocks.get_mut(tag);
        match ret {
            Some(b) => b,
            None => panic!("cannot find block {}", tag)
        }
138
    }
139 140 141 142
}

#[derive(Debug)]
pub struct FunctionContext {
qinsoon's avatar
qinsoon committed
143
    pub value_tags: HashMap<MuName, MuID>,
144
    pub values: HashMap<MuID, SSAVarEntry>
145 146 147 148 149
}

impl FunctionContext {
    fn new() -> FunctionContext {
        FunctionContext {
150
            value_tags: HashMap::new(),
151 152 153
            values: HashMap::new()
        }
    }
154

qinsoon's avatar
qinsoon committed
155
    pub fn get_value_by_tag(&self, tag: MuName) -> Option<&SSAVarEntry> {
156 157 158 159 160
        match self.value_tags.get(tag) {
            Some(id) => self.get_value(*id),
            None => None
        }
    }
161

qinsoon's avatar
qinsoon committed
162
    pub fn get_value_mut_by_tag(&mut self, tag: MuName) -> Option<&mut SSAVarEntry> {
163 164 165 166
        let id : MuID = match self.value_tags.get(tag) {
            Some(id) => *id,
            None => return None
        };
167

168 169
        self.get_value_mut(id)
    }
170

171
    pub fn get_value(&self, id: MuID) -> Option<&SSAVarEntry> {
172 173
        self.values.get(&id)
    }
174

175
    pub fn get_value_mut(&mut self, id: MuID) -> Option<&mut SSAVarEntry> {
176 177 178 179
        self.values.get_mut(&id)
    }
}

180
#[derive(Debug)]
181
pub struct Block {
qinsoon's avatar
qinsoon committed
182
    pub label: MuName,
183 184
    pub content: Option<BlockContent>,
    pub control_flow: ControlFlow
qinsoon's avatar
qinsoon committed
185 186
}

187
impl Block {
qinsoon's avatar
qinsoon committed
188
    pub fn new(label: MuName) -> Block {
189
        Block{label: label, content: None, control_flow: ControlFlow::default()}
190 191 192
    }
}

193 194
#[derive(Debug)]
pub struct ControlFlow {
qinsoon's avatar
qinsoon committed
195
    pub preds : Vec<MuName>,
196 197 198
    pub succs : Vec<BlockEdge>
}

199
impl ControlFlow {
qinsoon's avatar
qinsoon committed
200
    pub fn get_hottest_succ(&self) -> Option<MuName> {
201 202 203 204 205
        if self.succs.len() == 0 {
            None
        } else {
            let mut hot_blk = self.succs[0].target;
            let mut hot_prob = self.succs[0].probability;
206

207 208 209 210 211 212
            for edge in self.succs.iter() {
                if edge.probability > hot_prob {
                    hot_blk = edge.target;
                    hot_prob = edge.probability;
                }
            }
213

214 215 216 217 218
            Some(hot_blk)
        }
    }
}

219 220 221 222 223 224 225 226 227 228 229 230 231 232 233
impl fmt::Display for ControlFlow {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "preds: [{}], ", vector_as_str(&self.preds)).unwrap();
        write!(f, "succs: [{}]", vector_as_str(&self.succs))
    }
}

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

#[derive(Copy, Clone, Debug)]
pub struct BlockEdge {
qinsoon's avatar
qinsoon committed
234
    pub target: MuName,
235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250
    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)
    }
}

#[derive(Copy, Clone, Debug)]
pub enum EdgeKind {
    Forward, Backward
}

251
#[derive(Debug)]
252
pub struct BlockContent {
253
    pub args: Vec<P<Value>>,
qinsoon's avatar
qinsoon committed
254
    pub body: Vec<P<TreeNode>>,
255
    pub keepalives: Option<Vec<P<Value>>>
256 257
}

258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328
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) => {
                let ops = inst.ops.borrow();
                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, ..}
                    | 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
    }
}

329
#[derive(Debug, Clone)]
qinsoon's avatar
qinsoon committed
330 331
/// always use with P<TreeNode>
pub struct TreeNode {
qinsoon's avatar
qinsoon committed
332
    pub id: MuID,
333 334
    pub op: OpCode,
    pub v: TreeNode_,
qinsoon's avatar
qinsoon committed
335 336
}

337
impl TreeNode {
338
    // this is a hack to allow creating TreeNode without using a &mut MuFunctionVersion
qinsoon's avatar
qinsoon committed
339 340 341
    pub fn new_inst(id: MuID, v: Instruction) -> P<TreeNode> {
        P(TreeNode{
            id: id,
342
            op: pick_op_code_for_inst(&v),
qinsoon's avatar
qinsoon committed
343 344
            v: TreeNode_::Instruction(v),
        })
345 346
    }

347 348 349 350 351 352 353 354 355 356 357
    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
        }
    }
358

qinsoon's avatar
qinsoon committed
359
    pub fn clone_value(&self) -> P<Value> {
qinsoon's avatar
qinsoon committed
360
        match self.v {
qinsoon's avatar
qinsoon committed
361
            TreeNode_::Value(ref val) => val.clone(),
362 363 364 365 366 367 368 369
            TreeNode_::Instruction(ref inst) => {
                info!("expecting a value, but we found an inst. Instead we use its first value");
                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
370
        }
371 372
    }

qinsoon's avatar
qinsoon committed
373 374 375
    pub fn into_value(self) -> Option<P<Value>> {
        match self.v {
            TreeNode_::Value(val) => Some(val),
376
            _ => None
qinsoon's avatar
qinsoon committed
377 378
        }
    }
qinsoon's avatar
qinsoon committed
379 380
}

381 382
/// use +() to display a node
impl fmt::Display for TreeNode {
qinsoon's avatar
qinsoon committed
383
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
384 385 386
        match self.v {
            TreeNode_::Value(ref pv) => {
                match pv.v {
387
                    Value_::SSAVar(id) => {
388
                        write!(f, "+({} %{}#{})", pv.ty, pv.tag, id)
389 390
                    },
                    Value_::Constant(ref c) => {
391
                        write!(f, "+({} {})", pv.ty, c)
qinsoon's avatar
qinsoon committed
392 393
                    },
                    Value_::Global(ref g) => {
394 395 396 397
                        write!(f, "+({} to GLOBAL {} @{})", pv.ty, g.ty, g.tag)
                    },
                    Value_::Memory(ref mem) => {
                        write!(f, "+({})", mem)
398 399 400 401
                    }
                }
            },
            TreeNode_::Instruction(ref inst) => {
402
                write!(f, "+({})", inst)
403
            }
qinsoon's avatar
qinsoon committed
404
        }
qinsoon's avatar
qinsoon committed
405
    }
qinsoon's avatar
qinsoon committed
406 407
}

408
#[derive(Debug, Clone)]
qinsoon's avatar
qinsoon committed
409
pub enum TreeNode_ {
qinsoon's avatar
qinsoon committed
410
    Value(P<Value>),
411
    Instruction(Instruction)
qinsoon's avatar
qinsoon committed
412 413 414
}

/// always use with P<Value>
415
#[derive(Debug, Clone, PartialEq)]
qinsoon's avatar
qinsoon committed
416
pub struct Value {
qinsoon's avatar
qinsoon committed
417
    pub tag: MuName,
qinsoon's avatar
qinsoon committed
418 419
    pub ty: P<MuType>,
    pub v: Value_
qinsoon's avatar
qinsoon committed
420 421
}

422 423 424 425 426 427 428 429 430 431 432 433 434
impl Value {
    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
        }
    }
435

436 437 438 439 440 441 442 443 444 445 446 447
    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
        }
    }
448

449 450 451 452 453 454 455 456 457 458 459
    pub fn is_int_const(&self) -> bool {
        match self.v {
            Value_::Constant(_) => {
                let ty : &MuType_ = &self.ty;
                match ty {
                    &MuType_::Int(_) => true,
                    _ => false
                }
            }
            _ => false
        }
qinsoon's avatar
qinsoon committed
460
    }
461

qinsoon's avatar
qinsoon committed
462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477
    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 {
            Value_::SSAVar(id) => {
                write!(f, "+({} %{}#{})", self.ty, self.tag, id)
            },
            Value_::Constant(ref c) => {
                write!(f, "+({} {})", self.ty, c)
qinsoon's avatar
qinsoon committed
478 479
            },
            Value_::Global(ref g) => {
480 481 482 483
                write!(f, "+({} to GLOBAL {} @{})", self.ty, g.ty, g.tag)
            },
            Value_::Memory(ref mem) => {
                write!(f, "+({})", mem)
qinsoon's avatar
qinsoon committed
484 485 486
            }
        }
    }
487 488
}

489
#[derive(Debug, Clone, PartialEq)]
qinsoon's avatar
qinsoon committed
490
pub enum Value_ {
491
    SSAVar(MuID),
qinsoon's avatar
qinsoon committed
492
    Constant(Constant),
493 494
    Global(P<GlobalCell>),
    Memory(MemoryLocation)
qinsoon's avatar
qinsoon committed
495 496
}

497
#[derive(Debug, Clone)]
498
pub struct SSAVarEntry {
499
    pub id: MuID,
qinsoon's avatar
qinsoon committed
500
    pub tag: MuName,
501
    pub ty: P<MuType>,
502

503 504 505
    // how many times this entry is used
    // availalbe after DefUse pass
    pub use_count: Cell<usize>,
506

507
    // this field is only used during TreeGeneration pass
508 509 510
    pub expr: Option<Instruction>
}

511
impl SSAVarEntry {
512 513 514
    pub fn assign_expr(&mut self, expr: Instruction) {
        self.expr = Some(expr)
    }
515 516
}

517
impl fmt::Display for SSAVarEntry {
518
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
519
        write!(f, "{} {}#{}", self.ty, self.tag, self.id)
520 521 522
    }
}

523
#[derive(Debug, Clone, PartialEq)]
524
pub enum Constant {
525 526 527 528
    Int(usize),
    Float(f32),
    Double(f64),
    IRef(Address),
qinsoon's avatar
qinsoon committed
529 530
    FuncRef(MuName),
    UFuncRef(MuName),
531
    Vector(Vec<Constant>),
532 533
}

534
impl fmt::Display for Constant {
535 536 537 538 539 540 541 542
    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),
            &Constant::IRef(v) => write!(f, "{}", v),
            &Constant::FuncRef(v) => write!(f, "{}", v),
            &Constant::UFuncRef(v) => write!(f, "{}", v),
543 544 545 546 547 548 549 550 551 552
            &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, "]")
            }
553 554
        }
    }
qinsoon's avatar
qinsoon committed
555 556
}

557 558 559 560 561 562 563 564 565 566
#[derive(Debug, Clone, PartialEq)]
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
567
        label: MuName
568 569 570 571 572 573 574 575 576 577 578
    }
}

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} => {
                write!(f, "{} + {} + {} * {}", base, offset.as_ref().unwrap(), index.as_ref().unwrap(), scale.unwrap())
            }
            &MemoryLocation::Symbolic{ref base, ref label} => {
                if base.is_some() {
579
                    write!(f, "{}({})", label, base.as_ref().unwrap())
580 581 582 583 584 585 586 587
                } else {
                    write!(f, "{}", label)
                }
            }
        }
    }
}

qinsoon's avatar
qinsoon committed
588 589
#[derive(Debug, Clone, PartialEq)]
pub struct GlobalCell {
qinsoon's avatar
qinsoon committed
590
    pub tag: MuName,
qinsoon's avatar
qinsoon committed
591 592 593
    pub ty: P<MuType>
}

594
pub fn op_vector_str(vec: &Vec<OpIndex>, ops: &Vec<P<TreeNode>>) -> String {
595 596 597 598 599 600
    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(", ");
601
        }
602 603
    }
    ret
604
}