asm_backend.rs 50.9 KB
Newer Older
1 2
#![allow(unused_variables)]

3
use compiler::backend;
4 5
use compiler::backend::AOT_EMIT_CONTEXT_FILE;
use compiler::backend::AOT_EMIT_DIR;
qinsoon's avatar
qinsoon committed
6
use compiler::backend::RegGroup;
qinsoon's avatar
qinsoon committed
7
use utils::ByteSize;
8
use compiler::backend::x86_64;
9
use compiler::backend::x86_64::CodeGenerator;
qinsoon's avatar
qinsoon committed
10
use compiler::machine_code::MachineCode;
qinsoon's avatar
qinsoon committed
11
use vm::VM;
qinsoon's avatar
qinsoon committed
12
use runtime::ValueLocation;
13

14
use utils::string_utils;
15 16 17
use ast::ptr::P;
use ast::ir::*;

18 19
use std::collections::HashMap;
use std::str;
20
use std::usize;
21
use std::slice::Iter;
22
use std::ops;
23 24

struct ASMCode {
qinsoon's avatar
qinsoon committed
25
    name: MuName, 
qinsoon's avatar
qinsoon committed
26
    code: Vec<ASMInst>,
qinsoon's avatar
qinsoon committed
27 28

    blocks: HashMap<MuName, ASMBlock>
29 30
}

qinsoon's avatar
qinsoon committed
31 32 33
unsafe impl Send for ASMCode {} 
unsafe impl Sync for ASMCode {}

34
impl ASMCode {
qinsoon's avatar
qinsoon committed
35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
    fn get_use_locations(&self, reg: MuID) -> Vec<ASMLocation> {
        let mut ret = vec![];

        for inst in self.code.iter() {
            match inst.uses.get(&reg) {
                Some(ref locs) => {
                    ret.append(&mut locs.to_vec());
                },
                None => {}
            }
        }

        ret
    }

    fn get_define_locations(&self, reg: MuID) -> Vec<ASMLocation> {
        let mut ret = vec![];

        for inst in self.code.iter() {
            match inst.defines.get(&reg) {
                Some(ref locs) => {
                    ret.append(&mut locs.to_vec());
                },
                None => {}
            }
        }

        ret
    }

qinsoon's avatar
qinsoon committed
65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
    fn is_block_start(&self, inst: usize) -> bool {
        for block in self.blocks.values() {
            if block.start_inst == inst {
                return true;
            }
        }
        false
    }

    fn get_block_by_start_inst(&self, inst: usize) -> Option<&ASMBlock> {
        for block in self.blocks.values() {
            if block.start_inst == inst {
                return Some(block);
            }
        }

        None
    }

84 85 86 87 88 89 90 91
    fn rewrite_insert(
        &self,
        insert_before: HashMap<usize, Vec<Box<ASMCode>>>,
        insert_after: HashMap<usize, Vec<Box<ASMCode>>>) -> Box<ASMCode>
    {
        let mut ret = ASMCode {
            name: self.name.clone(),
            code: vec![],
qinsoon's avatar
qinsoon committed
92
            blocks: hashmap!{},
93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136
        };

        // iterate through old machine code
        let mut inst_offset = 0;    // how many instructions has been inserted

        for i in 0..self.number_of_insts() {
            // insert code before this instruction
            if insert_before.contains_key(&i) {
                for insert in insert_before.get(&i).unwrap() {
                    ret.append_code_sequence_all(insert);
                    inst_offset += insert.number_of_insts();
                }
            }

            // copy this instruction


            // insert code after this instruction
            if insert_after.contains_key(&i) {

            }
        }

        unimplemented!()
    }

    fn append_code_sequence(
        &mut self,
        another: &Box<ASMCode>,
        start_inst: usize,
        n_insts: usize)
    {
        let self_index = self.number_of_insts();
        unimplemented!()
    }

    fn append_code_sequence_all(&mut self, another: &Box<ASMCode>) {
        let n_insts = another.number_of_insts();
        self.append_code_sequence(another, 0, n_insts)
    }
}

use std::any::Any;

137
impl MachineCode for ASMCode {
138 139 140
    fn as_any(&self) -> &Any {
        self
    }
141 142 143
    fn number_of_insts(&self) -> usize {
        self.code.len()
    }
144
    
145 146 147 148 149 150 151 152
    fn is_move(&self, index: usize) -> bool {
        let inst = self.code.get(index);
        match inst {
            Some(inst) => inst.code.starts_with("mov"),
            None => false
        }
    }
    
qinsoon's avatar
qinsoon committed
153
    fn is_using_mem_op(&self, index: usize) -> bool {
qinsoon's avatar
qinsoon committed
154
        self.code[index].is_mem_op_used
qinsoon's avatar
qinsoon committed
155 156
    }
    
qinsoon's avatar
qinsoon committed
157
    fn get_succs(&self, index: usize) -> &Vec<usize> {
qinsoon's avatar
qinsoon committed
158
        &self.code[index].succs
qinsoon's avatar
qinsoon committed
159 160 161
    }
    
    fn get_preds(&self, index: usize) -> &Vec<usize> {
qinsoon's avatar
qinsoon committed
162
        &self.code[index].preds
qinsoon's avatar
qinsoon committed
163 164
    }
    
qinsoon's avatar
qinsoon committed
165 166
    fn get_inst_reg_uses(&self, index: usize) -> Vec<MuID> {
        self.code[index].uses.keys().map(|x| *x).collect()
167 168
    }
    
qinsoon's avatar
qinsoon committed
169 170
    fn get_inst_reg_defines(&self, index: usize) -> Vec<MuID> {
        self.code[index].defines.keys().map(|x| *x).collect()
171
    }
172
    
173
    fn replace_reg(&mut self, from: MuID, to: MuID) {
174 175 176 177
        let to_reg_tag : MuName = match backend::all_regs().get(&to) {
            Some(reg) => reg.name().unwrap(),
            None => panic!("expecting a machine register, but we are required to replace to {}", to)
        };
178
        let to_reg_string = "%".to_string() + &to_reg_tag;
qinsoon's avatar
qinsoon committed
179 180 181 182 183 184 185

        for loc in self.get_define_locations(from) {
            let ref mut inst_to_patch = self.code[loc.line];
            for i in 0..loc.len {
                // FIXME: why loop here?
                string_utils::replace(&mut inst_to_patch.code, loc.index, &to_reg_string, to_reg_string.len());
            }
186
        }
187

qinsoon's avatar
qinsoon committed
188 189 190 191 192
        for loc in self.get_use_locations(from) {
            let ref mut inst_to_patch = self.code[loc.line];
            for i in 0..loc.len {
                string_utils::replace(&mut inst_to_patch.code, loc.index, &to_reg_string, to_reg_string.len());
            }
193 194
        }
    }
195

196
    fn replace_tmp_for_inst(&mut self, from: MuID, to: MuID, inst: usize) {
197 198 199 200 201 202 203 204
        let to_reg_string : MuName = match backend::all_regs().get(&to) {
            Some(ref machine_reg) => {
                let name = machine_reg.name().unwrap();
                "%".to_string() + &name
            },
            None => REG_PLACEHOLDER.clone()
        };

qinsoon's avatar
qinsoon committed
205 206 207 208 209 210 211 212 213
        let asm = &mut self.code[inst];
        // if this reg is defined, replace the define
        if asm.defines.contains_key(&from) {
            let define_locs = asm.defines.get(&from).unwrap().to_vec();
            // replace temps
            for loc in define_locs.iter() {
                for i in 0..loc.len {
                    string_utils::replace(&mut asm.code, loc.index, &to_reg_string, to_reg_string.len());
                }
214 215
            }

qinsoon's avatar
qinsoon committed
216 217 218
            // remove old key, insert new one
            asm.defines.remove(&from);
            asm.defines.insert(from, define_locs);
219
        }
qinsoon's avatar
qinsoon committed
220 221 222 223 224 225 226 227

        // if this reg is used, replace the use
        if asm.uses.contains_key(&from) {
            let use_locs = asm.uses.get(&from).unwrap().to_vec();
            // replace temps
            for loc in use_locs.iter() {
                for i in 0..loc.len {
                    string_utils::replace(&mut asm.code, loc.index, &to_reg_string, to_reg_string.len());
228 229 230
                }
            }

qinsoon's avatar
qinsoon committed
231 232 233
            // remove old key, insert new one
            asm.uses.remove(&from);
            asm.uses.insert(from, use_locs);
234 235
        }
    }
236
    
237 238
    fn set_inst_nop(&mut self, index: usize) {
        self.code.remove(index);
qinsoon's avatar
qinsoon committed
239
        self.code.insert(index, ASMInst::nop());
240 241
    }
    
242 243 244 245 246 247 248 249 250 251 252
    fn emit(&self) -> Vec<u8> {
        let mut ret = vec![];
        
        for inst in self.code.iter() {
            ret.append(&mut inst.code.clone().into_bytes());
            ret.append(&mut "\n".to_string().into_bytes());
        }
        
        ret
    }
    
253 254
    fn trace_mc(&self) {
        trace!("");
255

256 257
        trace!("code for {}: \n", self.name);
        
258 259
        let n_insts = self.code.len();
        for i in 0..n_insts {
260
            self.trace_inst(i);
261 262
        }
        
263 264 265 266 267 268
        trace!("")      
    }
    
    fn trace_inst(&self, i: usize) {
        trace!("#{}\t{:30}\t\tdefine: {:?}\tuses: {:?}\tpred: {:?}\tsucc: {:?}", 
            i, self.code[i].code, self.get_inst_reg_defines(i), self.get_inst_reg_uses(i),
qinsoon's avatar
qinsoon committed
269
            self.code[i].preds, self.code[i].succs);
270
    }
271
    
272
    fn get_ir_block_livein(&self, block: &str) -> Option<&Vec<MuID>> {
qinsoon's avatar
qinsoon committed
273 274 275 276
        match self.blocks.get(block) {
            Some(ref block) => Some(&block.livein),
            None => None
        }
277 278
    }
    
279
    fn get_ir_block_liveout(&self, block: &str) -> Option<&Vec<MuID>> {
qinsoon's avatar
qinsoon committed
280 281 282 283
        match self.blocks.get(block) {
            Some(ref block) => Some(&block.liveout),
            None => None
        }
284 285
    }
    
286
    fn set_ir_block_livein(&mut self, block: &str, set: Vec<MuID>) {
qinsoon's avatar
qinsoon committed
287 288
        let block = self.blocks.get_mut(block).unwrap();
        block.livein = set;
289 290 291
    }
    
    fn set_ir_block_liveout(&mut self, block: &str, set: Vec<MuID>) {
qinsoon's avatar
qinsoon committed
292 293
        let block = self.blocks.get_mut(block).unwrap();
        block.liveout = set;
294 295
    }
    
qinsoon's avatar
qinsoon committed
296 297
    fn get_all_blocks(&self) -> Vec<MuName> {
        self.blocks.keys().map(|x| x.clone()).collect()
298 299
    }
    
300
    fn get_block_range(&self, block: &str) -> Option<ops::Range<usize>> {
qinsoon's avatar
qinsoon committed
301 302
        match self.blocks.get(block) {
            Some(ref block) => Some(block.start_inst..block.end_inst),
303 304 305
            None => None
        }
    }
306 307
}

qinsoon's avatar
qinsoon committed
308 309 310 311 312 313 314 315
#[derive(Clone, Debug)]
enum ASMBranchTarget {
    None,
    Conditional(MuName),
    Unconditional(MuName)
}

struct ASMInst {
316
    code: String,
qinsoon's avatar
qinsoon committed
317 318 319 320 321 322 323 324

    defines: HashMap<MuID, Vec<ASMLocation>>,
    uses: HashMap<MuID, Vec<ASMLocation>>,

    is_mem_op_used: bool,
    preds: Vec<usize>,
    succs: Vec<usize>,
    branch: ASMBranchTarget
325 326
}

qinsoon's avatar
qinsoon committed
327 328 329
impl ASMInst {
    fn symbolic(line: String) -> ASMInst {
        ASMInst {
330
            code: line,
qinsoon's avatar
qinsoon committed
331 332 333 334 335 336
            defines: HashMap::new(),
            uses: HashMap::new(),
            is_mem_op_used: false,
            preds: vec![],
            succs: vec![],
            branch: ASMBranchTarget::None
337 338 339
        }
    }
    
qinsoon's avatar
qinsoon committed
340 341 342 343 344 345 346 347 348
    fn inst(
        inst: String,
        defines: HashMap<MuID, Vec<ASMLocation>>,
        uses: HashMap<MuID, Vec<ASMLocation>>,
        is_mem_op_used: bool,
        target: ASMBranchTarget
    ) -> ASMInst
    {
        ASMInst {
349 350
            code: inst,
            defines: defines,
qinsoon's avatar
qinsoon committed
351 352 353 354 355
            uses: uses,
            is_mem_op_used: is_mem_op_used,
            preds: vec![],
            succs: vec![],
            branch: target
356 357
        }
    }
358
    
qinsoon's avatar
qinsoon committed
359 360
    fn nop() -> ASMInst {
        ASMInst {
361
            code: "".to_string(),
qinsoon's avatar
qinsoon committed
362 363 364 365 366 367
            defines: HashMap::new(),
            uses: HashMap::new(),
            is_mem_op_used: false,
            preds: vec![],
            succs: vec![],
            branch: ASMBranchTarget::None
368 369
        }
    }
370 371
}

372
#[derive(Clone, Debug)]
373 374 375 376 377 378 379
struct ASMLocation {
    line: usize,
    index: usize,
    len: usize
}

impl ASMLocation {
qinsoon's avatar
qinsoon committed
380
    fn new(line: usize, index: usize, len: usize) -> ASMLocation {
381
        ASMLocation{
qinsoon's avatar
qinsoon committed
382
            line: line,
383 384 385 386 387 388
            index: index,
            len: len
        }
    }
}

qinsoon's avatar
qinsoon committed
389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409
#[derive(Clone, Debug)]
/// [start_inst, end_inst)
struct ASMBlock {
    start_inst: usize,
    end_inst: usize,

    livein: Vec<MuID>,
    liveout: Vec<MuID>
}

impl ASMBlock {
    fn new() -> ASMBlock {
        ASMBlock {
            start_inst: usize::MAX,
            end_inst: usize::MAX,
            livein: vec![],
            liveout: vec![]
        }
    }
}

410
pub struct ASMCodeGen {
411
    cur: Option<Box<ASMCode>>
412 413
}

414
const REG_PLACEHOLDER_LEN : usize = 5;
415 416 417 418 419 420
lazy_static! {
    pub static ref REG_PLACEHOLDER : String = {
        let blank_spaces = [' ' as u8; REG_PLACEHOLDER_LEN];
        
        format!("%{}", str::from_utf8(&blank_spaces).unwrap())
    };
421 422 423 424
}

impl ASMCodeGen {
    pub fn new() -> ASMCodeGen {
425
        ASMCodeGen {
426
            cur: None
427 428 429 430 431 432 433 434 435 436 437
        }
    }
    
    fn cur(&self) -> &ASMCode {
        self.cur.as_ref().unwrap()
    }
    
    fn cur_mut(&mut self) -> &mut ASMCode {
        self.cur.as_mut().unwrap()
    }
    
438 439 440 441
    fn line(&self) -> usize {
        self.cur().code.len()
    }
    
442 443
    fn add_asm_label(&mut self, code: String) {
        let l = self.line();
qinsoon's avatar
qinsoon committed
444
        self.cur_mut().code.push(ASMInst::symbolic(code));
445 446
    }
    
447
    fn add_asm_block_label(&mut self, code: String, block_name: MuName) {
448
        let l = self.line();
qinsoon's avatar
qinsoon committed
449
        self.cur_mut().code.push(ASMInst::symbolic(code));
450 451
    }
    
452
    fn add_asm_symbolic(&mut self, code: String){
qinsoon's avatar
qinsoon committed
453
        self.cur_mut().code.push(ASMInst::symbolic(code));
454 455
    }
    
456 457
    fn prepare_machine_regs(&self, regs: Iter<P<Value>>) -> Vec<MuID> {
        regs.map(|x| self.prepare_machine_reg(x)).collect()
qinsoon's avatar
qinsoon committed
458
    }
459
    
460
    fn add_asm_call(&mut self, code: String) {
qinsoon's avatar
qinsoon committed
461
        // a call instruction will use all the argument registers
qinsoon's avatar
qinsoon committed
462 463 464 465 466 467 468
        let mut uses : HashMap<MuID, Vec<ASMLocation>> = HashMap::new();
        for reg in x86_64::ARGUMENT_GPRs.iter() {
            uses.insert(reg.id(), vec![]);
        }
        for reg in x86_64::ARGUMENT_FPRs.iter() {
            uses.insert(reg.id(), vec![]);
        }
qinsoon's avatar
qinsoon committed
469 470

        // defines: return registers
qinsoon's avatar
qinsoon committed
471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487
        let mut defines : HashMap<MuID, Vec<ASMLocation>> = HashMap::new();
        for reg in x86_64::RETURN_GPRs.iter() {
            defines.insert(reg.id(), vec![]);
        }
        for reg in x86_64::RETURN_FPRs.iter() {
            defines.insert(reg.id(), vec![]);
        }
        for reg in x86_64::CALLER_SAVED_GPRs.iter() {
            if !defines.contains_key(&reg.id()) {
                defines.insert(reg.id(), vec![]);
            }
        }
        for reg in x86_64::CALLER_SAVED_FPRs.iter() {
            if !defines.contains_key(&reg.id()) {
                defines.insert(reg.id(), vec![]);
            }
        }
488
          
qinsoon's avatar
qinsoon committed
489
        self.add_asm_inst(code, defines, uses, false);
490 491 492
    }
    
    fn add_asm_ret(&mut self, code: String) {
qinsoon's avatar
qinsoon committed
493
        let uses : HashMap<MuID, Vec<ASMLocation>> = {
qinsoon's avatar
qinsoon committed
494 495 496 497 498 499 500 501 502
            let mut ret = HashMap::new();
            for reg in x86_64::RETURN_GPRs.iter() {
                ret.insert(reg.id(), vec![]);
            }
            for reg in x86_64::RETURN_FPRs.iter() {
                ret.insert(reg.id(), vec![]);
            }
            ret
        };
503
        
qinsoon's avatar
qinsoon committed
504
        self.add_asm_inst(code, hashmap!{}, uses, false);
505 506
    }
    
507
    fn add_asm_branch(&mut self, code: String, target: MuName) {
qinsoon's avatar
qinsoon committed
508
        self.add_asm_inst_internal(code, hashmap!{}, hashmap!{}, false, ASMBranchTarget::Unconditional(target));
509 510
    }
    
511
    fn add_asm_branch2(&mut self, code: String, target: MuName) {
qinsoon's avatar
qinsoon committed
512
        self.add_asm_inst_internal(code, hashmap!{}, hashmap!{}, false, ASMBranchTarget::Conditional(target));
513 514 515 516 517
    }
    
    fn add_asm_inst(
        &mut self, 
        code: String, 
qinsoon's avatar
qinsoon committed
518 519 520 521 522 523 524 525 526 527 528 529 530 531
        defines: HashMap<MuID, Vec<ASMLocation>>,
        uses: HashMap<MuID, Vec<ASMLocation>>,
        is_using_mem_op: bool)
    {
        self.add_asm_inst_internal(code, defines, uses, is_using_mem_op, ASMBranchTarget::None)
    }

    fn add_asm_inst_internal(
        &mut self,
        code: String,
        defines: HashMap<MuID, Vec<ASMLocation>>,
        uses: HashMap<MuID, Vec<ASMLocation>>,
        is_using_mem_op: bool,
        target: ASMBranchTarget)
532
    {
533 534
        let line = self.line();
        trace!("asm: {}", code);
qinsoon's avatar
qinsoon committed
535 536
        trace!("     defines: {:?}", defines);
        trace!("     uses: {:?}", uses);
537
        let mc = self.cur_mut();
qinsoon's avatar
qinsoon committed
538

539
        // put the instruction
qinsoon's avatar
qinsoon committed
540
        mc.code.push(ASMInst::inst(code, defines, uses, is_using_mem_op, target));
541 542
    }
    
543
    fn prepare_reg(&self, op: &P<Value>, loc: usize) -> (String, MuID, ASMLocation) {
544 545 546 547 548 549 550
        if cfg!(debug_assertions) {
            match op.v {
                Value_::SSAVar(_) => {},
                _ => panic!("expecting register op")
            }
        }
        
551 552
        let str = self.asm_reg_op(op);
        let len = str.len();
qinsoon's avatar
qinsoon committed
553
        (str, op.extract_ssa_id().unwrap(), ASMLocation::new(self.line(), loc, len))
554 555 556
    }
    
    fn prepare_machine_reg(&self, op: &P<Value>) -> MuID {
557 558 559 560 561 562 563
        if cfg!(debug_assertions) {
            match op.v {
                Value_::SSAVar(_) => {},
                _ => panic!("expecting machine register op")
            }
        }        
        
564
        op.extract_ssa_id().unwrap()
565
    }
566
    
567
    #[allow(unused_assignments)]
qinsoon's avatar
qinsoon committed
568
    fn prepare_mem(&self, op: &P<Value>, loc: usize) -> (String, HashMap<MuID, Vec<ASMLocation>>) {
569 570 571 572 573 574
        if cfg!(debug_assertions) {
            match op.v {
                Value_::Memory(_) => {},
                _ => panic!("expecting register op")
            }
        }        
qinsoon's avatar
qinsoon committed
575

576 577 578 579
        let mut ids : Vec<MuID> = vec![];
        let mut locs : Vec<ASMLocation> = vec![];
        let mut result_str : String = "".to_string();
        
580
        let mut loc_cursor : usize = loc;
581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662
        
        match op.v {
            // offset(base,index,scale)
            Value_::Memory(MemoryLocation::Address{ref base, ref offset, ref index, scale}) => {
                // deal with offset
                if offset.is_some() {
                    let offset = offset.as_ref().unwrap();
                    
                    match offset.v {
                        Value_::SSAVar(id) => {
                            // temp as offset
                            let (str, id, loc) = self.prepare_reg(offset, 0);
                            
                            result_str.push_str(&str);
                            ids.push(id);
                            locs.push(loc);
                            
                            loc_cursor += str.len();
                        },
                        Value_::Constant(Constant::Int(val)) => {
                            let str = val.to_string();
                            
                            result_str.push_str(&str);
                            loc_cursor += str.len();
                        },
                        _ => panic!("unexpected offset type: {:?}", offset)
                    }
                }
                
                result_str.push('(');
                loc_cursor += 1; 
                
                // deal with base, base is ssa
                let (str, id, loc) = self.prepare_reg(base, loc_cursor);
                result_str.push_str(&str);
                ids.push(id);
                locs.push(loc);
                loc_cursor += str.len();
                
                // deal with index (ssa or constant)
                if index.is_some() {
                    result_str.push(',');
                    loc_cursor += 1; // plus 1 for ,                    
                    
                    let index = index.as_ref().unwrap();
                    
                    match index.v {
                        Value_::SSAVar(id) => {
                            // temp as offset
                            let (str, id, loc) = self.prepare_reg(index, loc_cursor);
                            
                            result_str.push_str(&str);
                            ids.push(id);
                            locs.push(loc);
                            
                            loc_cursor += str.len();
                        },
                        Value_::Constant(Constant::Int(val)) => {
                            let str = val.to_string();
                            
                            result_str.push_str(&str);
                            loc_cursor += str.len();
                        },
                        _ => panic!("unexpected index type: {:?}", index)
                    }
                    
                    // scale
                    if scale.is_some() {
                        result_str.push(',');
                        loc_cursor += 1;
                        
                        let scale = scale.unwrap();
                        let str = scale.to_string();
                        
                        result_str.push_str(&str);
                        loc_cursor += str.len();
                    }
                }
                
                result_str.push(')');
                loc_cursor += 1;
            },
663 664
            Value_::Memory(MemoryLocation::Symbolic{ref base, ref label}) => {
                result_str.push_str(&symbol(label.clone()));
665 666 667 668 669 670 671 672 673 674 675
                loc_cursor += label.len();
                
                if base.is_some() {
                    result_str.push('(');
                    loc_cursor += 1;
                    
                    let (str, id, loc) = self.prepare_reg(base.as_ref().unwrap(), loc_cursor);
                    result_str.push_str(&str);
                    ids.push(id);
                    locs.push(loc);
                    loc_cursor += str.len();
qinsoon's avatar
qinsoon committed
676

677
                    result_str.push(')');
qinsoon's avatar
qinsoon committed
678
                    loc_cursor += 1;
679 680 681 682
                }
            },
            _ => panic!("expect mem location as value")
        }
qinsoon's avatar
qinsoon committed
683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700

        let uses : HashMap<MuID, Vec<ASMLocation>> = {
            let mut map : HashMap<MuID, Vec<ASMLocation>> = hashmap!{};
            for i in 0..ids.len() {
                let id = ids[i];
                let loc = locs[i].clone();

                if map.contains_key(&id) {
                    map.get_mut(&id).unwrap().push(loc);
                } else {
                    map.insert(id, vec![loc]);
                }
            }
            map
        };


        (result_str, uses)
701 702
    }
    
703 704
    fn asm_reg_op(&self, op: &P<Value>) -> String {
        let id = op.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
705
        if id < MACHINE_ID_END {
706
            // machine reg
707
            format!("%{}", op.name().unwrap())
708 709 710 711 712 713
        } else {
            // virtual register, use place holder
            REG_PLACEHOLDER.clone()
        }
    }
    
qinsoon's avatar
qinsoon committed
714
    fn asm_block_label(&self, label: MuName) -> String {
715
        symbol(format!("{}_{}", self.cur().name, label))
716
    }
717 718 719 720
    
    fn control_flow_analysis(&mut self) {
        // control flow analysis
        let n_insts = self.line();
qinsoon's avatar
qinsoon committed
721

722
        let code = self.cur_mut();
qinsoon's avatar
qinsoon committed
723
        let ref blocks = code.blocks;
qinsoon's avatar
qinsoon committed
724
        let ref mut asm = code.code;
qinsoon's avatar
qinsoon committed
725 726 727 728 729 730 731 732

        let block_start = {
            let mut ret = vec![];
            for block in blocks.values() {
                ret.push(block.start_inst);
            }
            ret
        };
733 734 735
        
        for i in 0..n_insts {
            // determine predecessor - if cur is not block start, its predecessor is previous insts
qinsoon's avatar
qinsoon committed
736 737
            let is_block_start = block_start.contains(&i);
            if !is_block_start {
738
                if i > 0 {
739 740
                    trace!("inst {}: not a block start", i);
                    trace!("inst {}: set PREDS as previous inst {}", i, i-1);
qinsoon's avatar
qinsoon committed
741
                    asm[i].preds.push(i - 1);
742 743 744 745 746 747 748
                }
            } else {
                // if cur is a branch target, we already set its predecessor
                // if cur is a fall-through block, we set it in a sanity check pass
            }
            
            // determine successor
qinsoon's avatar
qinsoon committed
749 750 751 752 753 754
            let branch = asm[i].branch.clone();
            match branch {
                ASMBranchTarget::Unconditional(ref target) => {
                    // branch to target
                    trace!("inst {}: is a branch to {}", i, target);

qinsoon's avatar
qinsoon committed
755
                    let target_n = code.blocks.get(target).unwrap().start_inst;
qinsoon's avatar
qinsoon committed
756 757 758 759
                    trace!("inst {}: branch target index is {}", i, target_n);

                    // cur inst's succ is target
                    trace!("inst {}: set SUCCS as branch target {}", i, target_n);
qinsoon's avatar
qinsoon committed
760
                    asm[i].succs.push(target_n);
qinsoon's avatar
qinsoon committed
761 762 763

                    // target's pred is cur
                    trace!("inst {}: set PREDS as branch source {}", target_n, i);
qinsoon's avatar
qinsoon committed
764
                    asm[target_n].preds.push(i);
qinsoon's avatar
qinsoon committed
765 766
                },
                ASMBranchTarget::Conditional(ref target) => {
767
                    // branch to target
768
                    trace!("inst {}: is a cond branch to {}", i, target);
qinsoon's avatar
qinsoon committed
769

qinsoon's avatar
qinsoon committed
770
                    let target_n = code.blocks.get(target).unwrap().start_inst;
771
                    trace!("inst {}: branch target index is {}", i, target_n);
qinsoon's avatar
qinsoon committed
772

773
                    // cur insts' succ is target and next inst
qinsoon's avatar
qinsoon committed
774
                    asm[i].succs.push(target_n);
775
                    trace!("inst {}: set SUCCS as branch target {}", i, target_n);
776
                    if i < n_insts - 1 {
qinsoon's avatar
qinsoon committed
777 778
                        trace!("inst {}: set SUCCS as next inst", i + 1);
                        asm[i].succs.push(i + 1);
779
                    }
qinsoon's avatar
qinsoon committed
780

781
                    // target's pred is cur
qinsoon's avatar
qinsoon committed
782 783
                    asm[target_n].preds.push(i);
                    trace!("inst {}: set PREDS as {}", target_n, i);
qinsoon's avatar
qinsoon committed
784 785
                },
                ASMBranchTarget::None => {
786
                    // not branch nor cond branch, succ is next inst
787
                    trace!("inst {}: not a branch inst", i);
788
                    if i < n_insts - 1 {
789
                        trace!("inst {}: set SUCCS as next inst {}", i, i + 1);
qinsoon's avatar
qinsoon committed
790
                        asm[i].succs.push(i + 1);
791 792
                    }
                }
qinsoon's avatar
qinsoon committed
793
            }
794 795 796 797
        }
        
        // a sanity check for fallthrough blocks
        for i in 0..n_insts {
qinsoon's avatar
qinsoon committed
798 799
            if i != 0 && asm[i].preds.len() == 0 {
                asm[i].preds.push(i - 1);
800 801 802
            }
        }        
    }
803 804 805 806

    fn finish_code_sequence_asm(&mut self) -> Box<ASMCode> {
        self.cur.take().unwrap()
    }
807 808 809
}

impl CodeGenerator for ASMCodeGen {
qinsoon's avatar
qinsoon committed
810
    fn start_code(&mut self, func_name: MuName) -> ValueLocation {
811
        self.cur = Some(Box::new(ASMCode {
812
                name: func_name.clone(),
813
                code: vec![],
qinsoon's avatar
qinsoon committed
814
                blocks: hashmap!{},
815
            }));
816
        
qinsoon's avatar
qinsoon committed
817
        // to link with C sources via gcc
qinsoon's avatar
qinsoon committed
818 819 820 821
        let func_symbol = symbol(func_name.clone());
        self.add_asm_symbolic(directive_globl(func_symbol.clone()));
        self.add_asm_symbolic(format!("{}:", func_symbol.clone()));
        
822
        ValueLocation::Relocatable(RegGroup::GPR, func_name)
823 824
    }
    
825
    fn finish_code(&mut self, func_name: MuName) -> (Box<MachineCode + Sync + Send>, ValueLocation) {
826 827
        let func_end = {
            let mut symbol = func_name.clone();
qinsoon's avatar
qinsoon committed
828 829 830
            symbol.push_str("_end");
            symbol
        };
831 832
        self.add_asm_symbolic(directive_globl(symbol(func_end.clone())));
        self.add_asm_symbolic(format!("{}:", symbol(func_end.clone())));
qinsoon's avatar
qinsoon committed
833
        
834
        self.control_flow_analysis();
qinsoon's avatar
qinsoon committed
835 836 837
        
        (
            self.cur.take().unwrap(),
838
            ValueLocation::Relocatable(RegGroup::GPR, func_end)
qinsoon's avatar
qinsoon committed
839
        )
840
    }
841 842 843 844 845

    fn start_code_sequence(&mut self) {
        self.cur = Some(Box::new(ASMCode {
            name: "snippet".to_string(),
            code: vec![],
qinsoon's avatar
qinsoon committed
846
            blocks: hashmap!{}
847 848 849 850
        }));
    }

    fn finish_code_sequence(&mut self) -> Box<MachineCode + Sync + Send> {
851
        self.finish_code_sequence_asm()
852 853
    }

854 855 856 857 858 859 860
    fn print_cur_code(&self) {
        println!("");
        
        if self.cur.is_some() {
            let code = self.cur.as_ref().unwrap();
            
            println!("code for {}: ", code.name);
861 862 863 864
            let n_insts = code.code.len();
            for i in 0..n_insts {
                let ref line = code.code[i];
                println!("#{}\t{}", i, line.code);
865 866 867 868 869 870 871 872
            }
        } else {
            println!("no current code");
        }
        
        println!("");
    }
    
qinsoon's avatar
qinsoon committed
873
    fn start_block(&mut self, block_name: MuName) {
874 875
        let label = format!("{}:", self.asm_block_label(block_name.clone()));        
        self.add_asm_block_label(label, block_name.clone());
qinsoon's avatar
qinsoon committed
876 877

        self.cur_mut().blocks.insert(block_name.clone(), ASMBlock::new());
878
        let start = self.line();
qinsoon's avatar
qinsoon committed
879
        self.cur_mut().blocks.get_mut(&block_name).unwrap().start_inst = start;
880 881
    }
    
qinsoon's avatar
qinsoon committed
882
    fn start_exception_block(&mut self, block_name: MuName) -> ValueLocation {
883 884 885
        let block = self.asm_block_label(block_name.clone());
        self.add_asm_symbolic(directive_globl(symbol(block.clone())));
        self.add_asm_symbolic(format!("{}:", symbol(block.clone())));
qinsoon's avatar
qinsoon committed
886 887 888
        
        self.start_block(block_name);
        
889
        ValueLocation::Relocatable(RegGroup::GPR, block)
qinsoon's avatar
qinsoon committed
890 891
    }
    
qinsoon's avatar
qinsoon committed
892
    fn end_block(&mut self, block_name: MuName) {
qinsoon's avatar
qinsoon committed
893 894 895 896 897 898 899
        let line = self.line();
        match self.cur_mut().blocks.get_mut(&block_name) {
            Some(ref mut block) => {
                block.end_inst = line;
            }
            None => panic!("trying to end block {} which hasnt been started", block_name)
        }
900 901
    }
    
qinsoon's avatar
qinsoon committed
902
    fn set_block_livein(&mut self, block_name: MuName, live_in: &Vec<P<Value>>) {
903
        let cur = self.cur_mut();
qinsoon's avatar
qinsoon committed
904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921

        match cur.blocks.get_mut(&block_name) {
            Some(ref mut block) => {
                if block.livein.is_empty() {
                    let mut live_in = {
                        let mut ret = vec![];
                        for p in live_in {
                            match p.extract_ssa_id() {
                                Some(id) => ret.push(id),
                                None => warn!("{} as live-in of block {} is not SSA", p, block_name)
                            }
                        }
                        ret
                    };
                    block.livein.append(&mut live_in);
                } else {
                    panic!("seems we are inserting livein to block {} twice", block_name);
                }
922
            }
qinsoon's avatar
qinsoon committed
923
            None => panic!("haven't created ASMBlock for {}", block_name)
924 925 926
        }
    }
    
qinsoon's avatar
qinsoon committed
927
    fn set_block_liveout(&mut self, block_name: MuName, live_out: &Vec<P<Value>>) {
928
        let cur = self.cur_mut();
qinsoon's avatar
qinsoon committed
929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946

        match cur.blocks.get_mut(&block_name) {
            Some(ref mut block) => {
                if block.liveout.is_empty() {
                    let mut live_out = {
                        let mut ret = vec![];
                        for p in live_out {
                            match p.extract_ssa_id() {
                                Some(id) => ret.push(id),
                                None => warn!("{} as live-out of block {} is not SSA", p, block_name)
                            }
                        }
                        ret
                    };
                    block.liveout.append(&mut live_out);
                } else {
                    panic!("seems we are inserting liveout to block {} twice", block_name);
                }
947
            }
qinsoon's avatar
qinsoon committed
948 949
            None => panic!("haven't created ASMBlock for {}", block_name)
        }
950 951
    }
    
952 953 954 955 956 957 958
    fn emit_nop(&mut self, bytes: usize) {
        trace!("emit: nop ({} bytes)", bytes);
        
        let asm = String::from("nop");
        
        self.add_asm_inst(
            asm,
qinsoon's avatar
qinsoon committed
959 960
            hashmap!{},
            hashmap!{},
961 962 963 964
            false
        );
    }
    
965
    fn emit_cmp_r64_r64(&mut self, op1: &P<Value>, op2: &P<Value>) {
qinsoon's avatar
qinsoon committed
966
        trace!("emit: cmp {} {}", op1, op2);
967
        
968 969
        let (reg1, id1, loc1) = self.prepare_reg(op1, 4 + 1);
        let (reg2, id2, loc2) = self.prepare_reg(op2, 4 + 1 + reg1.len() + 1);
970
        
qinsoon's avatar
qinsoon committed
971
        let asm = format!("cmpq {},{}", reg1, reg2);
972
        
973 974
        self.add_asm_inst(
            asm,
qinsoon's avatar
qinsoon committed
975 976 977 978 979
            hashmap!{},
            hashmap!{
                id1 => vec![loc1],
                id2 => vec![loc2]
            },
qinsoon's avatar
qinsoon committed
980
            false
981
        );
982 983
    }
    
984
    fn emit_cmp_r64_imm32(&mut self, op1: &P<Value>, op2: i32) {
qinsoon's avatar
qinsoon committed
985
        trace!("emit: cmp {} {}", op1, op2);
986
        
987
        let (reg1, id1, loc1) = self.prepare_reg(op1, 4 + 1 + 1 + op2.to_string().len() + 1);
988
        
qinsoon's avatar
qinsoon committed
989
        let asm = format!("cmpq ${},{}", op2, reg1);
990
        
991 992
        self.add_asm_inst(
            asm,
qinsoon's avatar
qinsoon committed
993 994 995 996
            hashmap!{},
            hashmap!{
                id1 => vec![loc1]
            },
qinsoon's avatar
qinsoon committed
997
            false
998
        )
999 1000 1001
    }
    
    fn emit_cmp_r64_mem64(&mut self, op1: &P<Value>, op2: &P<Value>) {
qinsoon's avatar
qinsoon committed
1002
        trace!("emit: cmp {} {}", op1, op2);
1003 1004
        
        let (reg, id1, loc1) = self.prepare_reg(op1, 4 + 1);
qinsoon's avatar
qinsoon committed
1005
        let (mem, mut uses) = self.prepare_mem(op2, 4 + 1 + reg.len() + 1);
1006 1007 1008 1009
        
        let asm = format!("cmpq {},{}", reg, mem);
        
        // merge use vec
qinsoon's avatar
qinsoon committed
1010 1011 1012 1013 1014
        if uses.contains_key(&id1) {
            uses.get_mut(&id1).unwrap().push(loc1);
        } else {
            uses.insert(id1, vec![loc1]);
        }
1015 1016 1017
        
        self.add_asm_inst(
            asm,
qinsoon's avatar
qinsoon committed
1018 1019
            hashmap!{},
            uses,
1020 1021
            true
        )
1022 1023
    }
    
1024
    fn emit_mov_r64_imm32(&mut self, dest: &P<Value>, src: i32) {
qinsoon's avatar
qinsoon committed
1025
        trace!("emit: mov {} -> {}", src, dest);
1026
        
1027
        let (reg1, id1, loc1) = self.prepare_reg(dest, 4 + 1 + 1 + src.to_string().len() + 1);
1028
        
qinsoon's avatar
qinsoon committed
1029
        let asm = format!("movq ${},{}", src, reg1);
1030
        
1031 1032
        self.add_asm_inst(
            asm,
qinsoon's avatar
qinsoon committed
1033 1034 1035 1036
            hashmap!{
                id1 => vec![loc1]
            },
            hashmap!{},
qinsoon's avatar
qinsoon committed
1037
            false
1038
        )
1039 1040
    }
    
1041
    // load
1042
    fn emit_mov_r64_mem64(&mut self, dest: &P<Value>, src: &P<Value>) {
qinsoon's avatar
qinsoon committed
1043
        trace!("emit: mov {} -> {}", src, dest);
1044
        
qinsoon's avatar
qinsoon committed
1045
        let (mem, uses) = self.prepare_mem(src, 4 + 1);
1046 1047 1048 1049 1050 1051
        let (reg, id2, loc2) = self.prepare_reg(dest, 4 + 1 + mem.len() + 1);
        
        let asm = format!("movq {},{}", mem, reg);
        
        self.add_asm_inst(
            asm,
qinsoon's avatar
qinsoon committed
1052 1053 1054 1055
            hashmap!{
                id2 => vec![loc2]
            },
            uses,
qinsoon's avatar
qinsoon committed
1056
            true
1057 1058 1059
        )
    }
    
1060
    // store
1061 1062 1063 1064
    fn emit_mov_mem64_r64(&mut self, dest: &P<Value>, src: &P<Value>) {
        trace!("emit: mov {} -> {}", src, dest);
        
        let (reg, id1, loc1) = self.prepare_reg(src, 4 + 1);
qinsoon's avatar
qinsoon committed
1065
        let (mem, mut uses) = self.prepare_mem(dest, 4 + 1 + reg.len() + 1);
1066 1067
        
        // the register we used for the memory location is counted as 'use'
1068
        // use the vec from mem as 'use' (push use reg from src to it)
qinsoon's avatar
qinsoon committed
1069 1070 1071 1072 1073
        if uses.contains_key(&id1) {
            uses.get_mut(&id1).unwrap().push(loc1);
        } else {
            uses.insert(id1, vec![loc1]);
        }
1074 1075 1076 1077 1078
        
        let asm = format!("movq {},{}", reg, mem);
        
        self.add_asm_inst(
            asm,
qinsoon's avatar
qinsoon committed
1079 1080
            hashmap!{},
            uses,
qinsoon's avatar
qinsoon committed
1081
            true
1082 1083 1084
        )
    }
    
1085
    fn emit_mov_mem64_imm32(&mut self, dest: &P<Value>, src: i32) {
1086 1087
        trace!("emit: mov {} -> {}", src, dest);
        
qinsoon's avatar
qinsoon committed
1088
        let (mem, uses) = self.prepare_mem(dest, 4 + 1 + 1 + src.to_string().len() + 1);
1089 1090 1091 1092 1093
        
        let asm = format!("movq ${},{}", src, mem);
        
        self.add_asm_inst(
            asm,
qinsoon's avatar
qinsoon committed
1094 1095
            hashmap!{},
            uses,
qinsoon's avatar
qinsoon committed
1096
            true
1097
        )
qinsoon's avatar
qinsoon committed
1098 1099 1100 1101
    }
    
    fn emit_mov_r64_r64(&mut self, dest: &P<Value>, src: &P<Value>) {
        trace!("emit: mov {} -> {}", src, dest);
1102
        
1103 1104
        let (reg1, id1, loc1) = self.prepare_reg(src, 4 + 1);
        let (reg2, id2, loc2) = self.prepare_reg(dest, 4 + 1 + reg1.len() + 1);
1105
        
qinsoon's avatar
qinsoon committed
1106
        let asm = format!("movq {},{}", reg1, reg2);
1107
        
1108 1109
        self.add_asm_inst(
            asm,
qinsoon's avatar
qinsoon committed
1110 1111 1112 1113 1114 1115
            hashmap!{
                id2 => vec![loc2]
            },
            hashmap!{
                id1 => vec![loc1]
            },
qinsoon's avatar
qinsoon committed
1116
            false
1117
        )
qinsoon's avatar
qinsoon committed
1118 1119 1120 1121
    }
    
    fn emit_add_r64_r64(&mut self, dest: &P<Value>, src: &P<Value>) {
        trace!("emit: add {}, {} -> {}", dest, src, dest);
1122
        
1123 1124
        let (reg1, id1, loc1) = self.prepare_reg(src, 4 + 1);
        let (reg2, id2, loc2) = self.prepare_reg(dest, 4 + 1 + reg1.len() + 1);
1125
        
qinsoon's avatar
qinsoon committed
1126
        let asm = format!("addq {},{}", reg1, reg2);
1127
        
1128 1129
        self.add_asm_inst(
            asm,
qinsoon's avatar
qinsoon committed
1130 1131 1132 1133 1134 1135 1136
            hashmap!{
                id2 => vec![loc2.clone()]
            },
            hashmap!{
                id1 => vec![loc1],
                id2 => vec![loc2]
            },
qinsoon's avatar
qinsoon committed
1137
            false
1138
        )
qinsoon's avatar
qinsoon committed
1139 1140
    }
    
1141 1142 1143
    fn emit_lea_r64(&mut self, dest: &P<Value>, src: &P<Value>) {
        trace!("emit: lea {} -> {}", src, dest);
        
qinsoon's avatar
qinsoon committed
1144
        let (mem, uses) = self.prepare_mem(src, 4 + 1);
1145 1146 1147 1148 1149 1150
        let (reg, id2, loc2) = self.prepare_reg(dest, 4 + 1 + mem.len() + 1);
        
        let asm = format!("leaq {},{}", mem, reg);
        
        self.add_asm_inst(
            asm,
qinsoon's avatar
qinsoon committed
1151 1152 1153 1154
            hashmap!{
                id2 => vec![loc2]
            },
            uses,
1155 1156 1157 1158
            true
        ) 
    }
    
1159
    fn emit_and_r64_imm32(&mut self, dest: &P<Value>, src: i32) {
1160 1161 1162 1163 1164 1165 1166 1167
        trace!("emit: and {}, {} -> {}", src, dest, dest);
        
        let (reg1, id1, loc1) = self.prepare_reg(dest, 4 + 1 + 1 + src.to_string().len() + 1);

        let asm = format!("andq ${},{}", src, reg1);
        
        self.add_asm_inst(
            asm,
qinsoon's avatar
qinsoon committed
1168 1169 1170 1171 1172 1173
            hashmap!{
                id1 => vec![loc1.clone()]
            },
            hashmap!{
                id1 => vec![loc1]
            },
1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187
            false
        )
    }
    
    fn emit_and_r64_r64(&mut self, dest: &P<Value>, src: &P<Value>) {
        trace!("emit: and {}, {} -> {}", src, dest, dest);
        
        let (reg1, id1, loc1) = self.prepare_reg(src, 4 + 1);
        let (reg2, id2, loc2) = self.prepare_reg(dest, 4 + 1 + reg1.len() + 1); 

        let asm = format!("andq {},{}", reg1, reg2);
        
        self.add_asm_inst(
            asm,
qinsoon's avatar
qinsoon committed
1188 1189 1190 1191 1192 1193 1194
            hashmap!{
                id2 => vec![loc2.clone()]
            },
            hashmap!{
                id1 => vec![loc1],
                id2 => vec![loc2]
            },
1195 1196 1197 1198
            false
        )
    }    
    
qinsoon's avatar
qinsoon committed
1199 1200
    fn emit_add_r64_mem64(&mut self, dest: &P<Value>, src: &P<Value>) {
        trace!("emit: add {}, {} -> {}", dest, src, dest);