ir.rs 15.3 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 15 16 17
pub type WPID  = usize;
pub type MuID  = usize;
pub type MuTag = &'static str;
pub type Address = usize; // TODO: replace this with Address(usize)

18 19
pub type OpIndex = usize;

20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
#[derive(Debug)]
pub struct MuFunction {
    pub fn_name: MuTag,
    pub sig: P<MuFuncSig>,
    pub cur_ver: Option<MuTag>,
    pub all_vers: Vec<MuTag>
}

impl MuFunction {
    pub fn new(fn_name: MuTag, sig: P<MuFuncSig>) -> MuFunction {
        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
    pub fn_name: MuTag,
42
    pub version: MuTag,
43

44
    pub next_id: MuID,
45

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

50
    pub block_trace: Option<Vec<MuTag>> // only available after Trace Generation Pass
51 52
}

53 54
pub const RESERVED_NODE_IDS_FOR_MACHINE : usize = 100;

55
impl MuFunctionVersion {
56
    pub fn new(fn_name: MuTag, ver: MuTag, sig: P<MuFuncSig>) -> MuFunctionVersion {
57
        MuFunctionVersion{
58
            fn_name: fn_name,
59
            version: ver,
60 61 62 63
            next_id: RESERVED_NODE_IDS_FOR_MACHINE,
            sig: sig,
            content: None,
            context: FunctionContext::new(),
64 65
            block_trace: None}
    }
66

67 68 69 70
    fn get_id(&mut self) -> MuID {
        let ret = self.next_id;
        self.next_id += 1;
        ret
71
    }
72

73 74 75
    pub fn define(&mut self, content: FunctionContent) {
        self.content = Some(content)
    }
76

qinsoon's avatar
qinsoon committed
77
    pub fn new_ssa(&mut self, tag: MuTag, ty: P<MuType>) -> P<TreeNode> {
78
        let id = self.get_id();
79

80
        self.context.value_tags.insert(tag, id);
81
        self.context.values.insert(id, SSAVarEntry{id: id, tag: tag, ty: ty.clone(), use_count: Cell::new(0), expr: None});
82

83
        P(TreeNode {
qinsoon's avatar
qinsoon committed
84
            id: id,
85
            op: pick_op_code_for_ssa(&ty),
qinsoon's avatar
qinsoon committed
86 87 88 89 90
            v: TreeNode_::Value(P(Value{
                tag: tag,
                ty: ty,
                v: Value_::SSAVar(id)
            }))
91 92
        })
    }
93 94

    pub fn new_constant(&mut self, v: P<Value>) -> P<TreeNode> {
95
        P(TreeNode{
96
            id: self.get_id(),
97
            op: pick_op_code_for_const(&v.ty),
qinsoon's avatar
qinsoon committed
98 99
            v: TreeNode_::Value(v)
        })
100
    }
101

102 103 104
    pub fn new_inst(&mut self, v: Instruction) -> P<TreeNode> {
        P(TreeNode{
            id: self.get_id(),
105
            op: pick_op_code_for_inst(&v),
106 107
            v: TreeNode_::Instruction(v),
        })
108
    }
109 110
}

111 112 113 114 115 116 117 118
#[derive(Debug)]
pub struct FunctionContent {
    pub entry: MuTag,
    pub blocks: HashMap<MuTag, Block>
}

impl FunctionContent {
    pub fn get_entry_block(&self) -> &Block {
qinsoon's avatar
qinsoon committed
119
        self.get_block(self.entry)
120
    }
121

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

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

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

#[derive(Debug)]
pub struct FunctionContext {
146
    pub value_tags: HashMap<MuTag, MuID>,
147
    pub values: HashMap<MuID, SSAVarEntry>
148 149 150 151 152
}

impl FunctionContext {
    fn new() -> FunctionContext {
        FunctionContext {
153
            value_tags: HashMap::new(),
154 155 156
            values: HashMap::new()
        }
    }
157

158
    pub fn get_value_by_tag(&self, tag: MuTag) -> Option<&SSAVarEntry> {
159 160 161 162 163
        match self.value_tags.get(tag) {
            Some(id) => self.get_value(*id),
            None => None
        }
    }
164

165
    pub fn get_value_mut_by_tag(&mut self, tag: MuTag) -> Option<&mut SSAVarEntry> {
166 167 168 169
        let id : MuID = match self.value_tags.get(tag) {
            Some(id) => *id,
            None => return None
        };
170

171 172
        self.get_value_mut(id)
    }
173

174
    pub fn get_value(&self, id: MuID) -> Option<&SSAVarEntry> {
175 176
        self.values.get(&id)
    }
177

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

183
#[derive(Debug)]
184
pub struct Block {
185
    pub label: MuTag,
186 187
    pub content: Option<BlockContent>,
    pub control_flow: ControlFlow
qinsoon's avatar
qinsoon committed
188 189
}

190 191
impl Block {
    pub fn new(label: MuTag) -> Block {
192
        Block{label: label, content: None, control_flow: ControlFlow::default()}
193 194 195
    }
}

196 197 198 199 200 201
#[derive(Debug)]
pub struct ControlFlow {
    pub preds : Vec<MuTag>,
    pub succs : Vec<BlockEdge>
}

202 203 204 205 206 207 208
impl ControlFlow {
    pub fn get_hottest_succ(&self) -> Option<MuTag> {
        if self.succs.len() == 0 {
            None
        } else {
            let mut hot_blk = self.succs[0].target;
            let mut hot_prob = self.succs[0].probability;
209

210 211 212 213 214 215
            for edge in self.succs.iter() {
                if edge.probability > hot_prob {
                    hot_blk = edge.target;
                    hot_prob = edge.probability;
                }
            }
216

217 218 219 220 221
            Some(hot_blk)
        }
    }
}

222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253
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 {
    pub target: MuTag,
    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
}

254
#[derive(Debug)]
255
pub struct BlockContent {
256
    pub args: Vec<P<Value>>,
qinsoon's avatar
qinsoon committed
257
    pub body: Vec<P<TreeNode>>,
258
    pub keepalives: Option<Vec<P<Value>>>
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 329 330 331
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
    }
}

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

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

350 351 352 353 354 355 356 357 358 359 360
    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
        }
    }
361

qinsoon's avatar
qinsoon committed
362
    pub fn clone_value(&self) -> P<Value> {
qinsoon's avatar
qinsoon committed
363
        match self.v {
qinsoon's avatar
qinsoon committed
364
            TreeNode_::Value(ref val) => val.clone(),
365 366 367 368 369 370 371 372
            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
373
        }
374 375
    }

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

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

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

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

419 420 421 422 423 424 425 426 427 428 429 430 431
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
        }
    }
432

433 434 435 436 437 438 439 440 441 442 443 444
    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
        }
    }
445

446 447 448 449 450 451 452 453 454 455 456
    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
457
    }
458

qinsoon's avatar
qinsoon committed
459 460 461 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)
            }
        }
    }
478 479
}

480
#[derive(Debug, Clone, PartialEq)]
qinsoon's avatar
qinsoon committed
481
pub enum Value_ {
482
    SSAVar(MuID),
qinsoon's avatar
qinsoon committed
483
    Constant(Constant)
qinsoon's avatar
qinsoon committed
484 485
}

486
#[derive(Debug, Clone)]
487
pub struct SSAVarEntry {
488 489 490
    pub id: MuID,
    pub tag: MuTag,
    pub ty: P<MuType>,
491

492 493 494
    // how many times this entry is used
    // availalbe after DefUse pass
    pub use_count: Cell<usize>,
495

496
    // this field is only used during TreeGeneration pass
497 498 499
    pub expr: Option<Instruction>
}

500
impl SSAVarEntry {
501 502 503
    pub fn assign_expr(&mut self, expr: Instruction) {
        self.expr = Some(expr)
    }
504 505
}

506
impl fmt::Display for SSAVarEntry {
507
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
508
        write!(f, "{} {}#{}", self.ty, self.tag, self.id)
509 510 511
    }
}

512
#[derive(Debug, Clone, PartialEq)]
513
pub enum Constant {
514 515 516 517
    Int(usize),
    Float(f32),
    Double(f64),
    IRef(Address),
518 519
    FuncRef(MuTag),
    UFuncRef(MuTag),
520
    Vector(Vec<Constant>),
521 522
}

523
impl fmt::Display for Constant {
524 525 526 527 528 529 530 531
    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),
532 533 534 535 536 537 538 539 540 541
            &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, "]")
            }
542 543
        }
    }
qinsoon's avatar
qinsoon committed
544 545
}

546
pub fn op_vector_str(vec: &Vec<OpIndex>, ops: &Vec<P<TreeNode>>) -> String {
547 548 549 550 551 552
    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(", ");
553
        }
554 555
    }
    ret
556
}