asm_backend.rs 120 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14
// Copyright 2017 The Australian National University
// 
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
// 
//     http://www.apache.org/licenses/LICENSE-2.0
// 
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

15 16
#![allow(unused_variables)]

17
use compiler::backend::AOT_EMIT_CONTEXT_FILE;
qinsoon's avatar
qinsoon committed
18
use compiler::backend::RegGroup;
qinsoon's avatar
qinsoon committed
19
use utils::ByteSize;
20 21
use utils::Address;
use utils::POINTER_SIZE;
22
use compiler::backend::x86_64;
23
use compiler::backend::x86_64::CodeGenerator;
24
use compiler::backend::{Reg, Mem};
25
use compiler::backend::x86_64::check_op_len;
qinsoon's avatar
qinsoon committed
26
use compiler::machine_code::MachineCode;
qinsoon's avatar
qinsoon committed
27
use vm::VM;
qinsoon's avatar
qinsoon committed
28
use runtime::ValueLocation;
29

qinsoon's avatar
qinsoon committed
30
use utils::vec_utils;
31
use utils::string_utils;
32 33
use utils::LinkedHashMap;

34 35 36
use ast::ptr::P;
use ast::ir::*;

37
use std::str;
38
use std::usize;
39
use std::slice::Iter;
40
use std::ops;
41
use std::collections::HashSet;
42 43

struct ASMCode {
qinsoon's avatar
qinsoon committed
44
    name: MuName, 
qinsoon's avatar
qinsoon committed
45
    code: Vec<ASMInst>,
qinsoon's avatar
qinsoon committed
46

47
    entry:  MuName,
48
    blocks: LinkedHashMap<MuName, ASMBlock>,
qinsoon's avatar
qinsoon committed
49 50

    frame_size_patchpoints: Vec<ASMLocation>
51 52
}

qinsoon's avatar
qinsoon committed
53 54 55
unsafe impl Send for ASMCode {} 
unsafe impl Sync for ASMCode {}

56
impl ASMCode {
qinsoon's avatar
qinsoon committed
57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
    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
87 88 89 90 91 92 93 94 95
    fn is_block_start(&self, inst: usize) -> bool {
        for block in self.blocks.values() {
            if block.start_inst == inst {
                return true;
            }
        }
        false
    }

96
    fn is_last_inst_in_block(&self, inst: usize) -> bool {
qinsoon's avatar
qinsoon committed
97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114
        for block in self.blocks.values() {
            if block.end_inst == inst + 1 {
                return true;
            }
        }
        false
    }

    fn get_block_by_inst(&self, inst: usize) -> (&String, &ASMBlock) {
        for (name, block) in self.blocks.iter() {
            if inst >= block.start_inst && inst < block.end_inst {
                return (name, block);
            }
        }

        panic!("didnt find any block for inst {}", inst)
    }

qinsoon's avatar
qinsoon committed
115 116 117 118 119 120 121 122 123 124
    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
    }

125 126
    fn rewrite_insert(
        &self,
127 128
        insert_before: LinkedHashMap<usize, Vec<Box<ASMCode>>>,
        insert_after: LinkedHashMap<usize, Vec<Box<ASMCode>>>) -> Box<ASMCode>
129
    {
130
        trace!("insert spilling code");
131 132
        let mut ret = ASMCode {
            name: self.name.clone(),
133
            entry: self.entry.clone(),
134
            code: vec![],
135
            blocks: linked_hashmap!{},
qinsoon's avatar
qinsoon committed
136
            frame_size_patchpoints: vec![]
137 138 139 140
        };

        // iterate through old machine code
        let mut inst_offset = 0;    // how many instructions has been inserted
qinsoon's avatar
qinsoon committed
141
        let mut cur_block_start = usize::MAX;
142

qinsoon's avatar
qinsoon committed
143 144
        // inst N in old machine code is N' in new machine code
        // this map stores the relationship
145
        let mut location_map : LinkedHashMap<usize, usize> = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
146

147
        for i in 0..self.number_of_insts() {
148 149
            trace!("Inst{}", i);

qinsoon's avatar
qinsoon committed
150 151
            if self.is_block_start(i) {
                cur_block_start = i + inst_offset;
152
                trace!("  block start is shifted to {}", cur_block_start);
qinsoon's avatar
qinsoon committed
153 154
            }

155 156 157 158 159
            // 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();
160
                    trace!("  inserted {} insts before", insert.number_of_insts());
161 162 163 164
                }
            }

            // copy this instruction
qinsoon's avatar
qinsoon committed
165 166
            let mut inst = self.code[i].clone();

qinsoon's avatar
qinsoon committed
167 168
            // old ith inst is now the (i + inst_offset)th instruction
            location_map.insert(i, i + inst_offset);
169
            trace!("  Inst{} is now Inst{}", i, i + inst_offset);
qinsoon's avatar
qinsoon committed
170

qinsoon's avatar
qinsoon committed
171 172 173 174 175 176 177 178 179 180 181 182 183 184 185
            // this instruction has been offset by several instructions('inst_offset')
            // update its info
            // 1. fix defines and uses
            for locs in inst.defines.values_mut() {
                for loc in locs {
                    debug_assert!(loc.line == i);
                    loc.line += inst_offset;
                }
            }
            for locs in inst.uses.values_mut() {
                for loc in locs {
                    debug_assert!(loc.line == i);
                    loc.line += inst_offset;
                }
            }
186 187 188
            // 2. we need to delete existing preds/succs - CFA is required later
            inst.preds.clear();
            inst.succs.clear();
qinsoon's avatar
qinsoon committed
189 190
            // 3. add the inst
            ret.code.push(inst);
191 192 193 194


            // insert code after this instruction
            if insert_after.contains_key(&i) {
qinsoon's avatar
qinsoon committed
195 196 197
                for insert in insert_after.get(&i).unwrap() {
                    ret.append_code_sequence_all(insert);
                    inst_offset += insert.number_of_insts();
198
                    trace!("  inserted {} insts after", insert.number_of_insts());
qinsoon's avatar
qinsoon committed
199 200 201
                }
            }

202 203
            if self.is_last_inst_in_block(i) {
                let cur_block_end = i + 1 + inst_offset;
204

qinsoon's avatar
qinsoon committed
205 206 207
                // copy the block
                let (name, block) = self.get_block_by_inst(i);

qinsoon's avatar
qinsoon committed
208
                let new_block = ASMBlock{
209 210 211 212 213 214 215 216 217 218
                    start_inst: cur_block_start,
                    end_inst: cur_block_end,

                    livein: vec![],
                    liveout: vec![]
                };

                trace!("  old block: {:?}", block);
                trace!("  new block: {:?}", new_block);

qinsoon's avatar
qinsoon committed
219 220 221 222
                cur_block_start = usize::MAX;

                // add to the new code
                ret.blocks.insert(name.clone(), new_block);
223 224 225
            }
        }

qinsoon's avatar
qinsoon committed
226 227 228 229 230
        // fix patchpoint
        for patchpoint in self.frame_size_patchpoints.iter() {
            let new_patchpoint = ASMLocation {
                line: *location_map.get(&patchpoint.line).unwrap(),
                index: patchpoint.index,
231 232
                len: patchpoint.len,
                oplen: patchpoint.oplen
qinsoon's avatar
qinsoon committed
233 234 235 236 237
            };

            ret.frame_size_patchpoints.push(new_patchpoint);
        }

qinsoon's avatar
qinsoon committed
238 239 240
        ret.control_flow_analysis();

        Box::new(ret)
241 242 243 244 245 246 247 248
    }

    fn append_code_sequence(
        &mut self,
        another: &Box<ASMCode>,
        start_inst: usize,
        n_insts: usize)
    {
qinsoon's avatar
qinsoon committed
249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274
        let base_line = self.number_of_insts();

        for i in 0..n_insts {
            let cur_line_in_self = base_line + i;
            let cur_line_from_copy = start_inst + i;

            let mut inst = another.code[cur_line_from_copy].clone();

            // fix info
            for locs in inst.defines.values_mut() {
                for loc in locs {
                    debug_assert!(loc.line == i);
                    loc.line = cur_line_in_self;
                }
            }
            for locs in inst.uses.values_mut() {
                for loc in locs {
                    debug_assert!(loc.line == i);
                    loc.line = cur_line_in_self;
                }
            }
            // ignore preds/succs

            // add to self
            self.code.push(inst);
        }
275 276 277 278 279 280
    }

    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)
    }
qinsoon's avatar
qinsoon committed
281 282

    fn control_flow_analysis(&mut self) {
283
        const TRACE_CFA : bool = true;
qinsoon's avatar
qinsoon committed
284 285 286 287 288 289 290 291 292 293

        // control flow analysis
        let n_insts = self.number_of_insts();

        let ref blocks = self.blocks;
        let ref mut asm = self.code;

        let block_start = {
            let mut ret = vec![];
            for block in blocks.values() {
294 295 296
                if TRACE_CFA {
                    trace!("Block starts at {}", block.start_inst);
                }
qinsoon's avatar
qinsoon committed
297 298 299 300 301 302
                ret.push(block.start_inst);
            }
            ret
        };

        for i in 0..n_insts {
qinsoon's avatar
qinsoon committed
303 304 305
            if TRACE_CFA {
                trace!("---inst {}---", i);
            }
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 332 333 334

            // skip symbol
            if asm[i].is_symbol {
                continue;
            }

            // determine predecessor

            // we check if it is a fallthrough block
            if i != 0 {
                let last_inst = ASMCode::find_prev_inst(i, asm);

                match last_inst {
                    Some(last_inst) => {
                        let last_inst_branch = asm[last_inst].branch.clone();
                        match last_inst_branch {
                            // if it is a fallthrough, we set its preds as last inst
                            ASMBranchTarget::None => {
                                if !asm[i].preds.contains(&last_inst) {
                                    asm[i].preds.push(last_inst);

                                    if TRACE_CFA {
                                        trace!("inst {}: set PREDS as previous inst - fallthrough {}", i, last_inst);
                                    }
                                }
                            }
                            // otherwise do nothing
                            _ => {}
                        }
qinsoon's avatar
qinsoon committed
335
                    }
336
                    None => {}
qinsoon's avatar
qinsoon committed
337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363
                }
            }

            // determine successor
            let branch = asm[i].branch.clone();
            match branch {
                ASMBranchTarget::Unconditional(ref target) => {
                    // branch to target
                    let target_n = self.blocks.get(target).unwrap().start_inst;

                    // cur inst's succ is target
                    asm[i].succs.push(target_n);

                    // target's pred is cur
                    asm[target_n].preds.push(i);

                    if TRACE_CFA {
                        trace!("inst {}: is a branch to {}", i, target);
                        trace!("inst {}: branch target index is {}", i, target_n);
                        trace!("inst {}: set SUCCS as branch target {}", i, target_n);
                        trace!("inst {}: set PREDS as branch source {}", target_n, i);
                    }
                },
                ASMBranchTarget::Conditional(ref target) => {
                    // branch to target
                    let target_n = self.blocks.get(target).unwrap().start_inst;

364
                    // cur insts' succ is target
qinsoon's avatar
qinsoon committed
365 366 367 368 369 370 371 372 373 374 375 376 377
                    asm[i].succs.push(target_n);

                    if TRACE_CFA {
                        trace!("inst {}: is a cond branch to {}", i, target);
                        trace!("inst {}: branch target index is {}", i, target_n);
                        trace!("inst {}: set SUCCS as branch target {}", i, target_n);
                    }

                    // target's pred is cur
                    asm[target_n].preds.push(i);
                    if TRACE_CFA {
                        trace!("inst {}: set PREDS as {}", target_n, i);
                    }
378 379 380 381 382 383 384 385 386 387 388 389 390 391

                    if let Some(next_inst) = ASMCode::find_next_inst(i, asm) {
                        // cur succ is next inst
                        asm[i].succs.push(next_inst);

                        // next inst's pred is cur
                        asm[next_inst].preds.push(i);

                        if TRACE_CFA {
                            trace!("inst {}: SET SUCCS as c-branch fallthrough target {}", i, next_inst);
                        }
                    } else {
                        panic!("conditional branch does not have a fallthrough target");
                    }
qinsoon's avatar
qinsoon committed
392
                },
393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421
                ASMBranchTarget::PotentiallyExcepting(ref target) => {
                    // may trigger exception and jump to target - similar as conditional branch
                    let target_n = self.blocks.get(target).unwrap().start_inst;

                    // cur inst's succ is target
                    asm[i].succs.push(target_n);

                    if TRACE_CFA {
                        trace!("inst {}: is potentially excepting to {}", i, target);
                        trace!("inst {}: excepting target index is {}", i, target_n);
                        trace!("inst {}: set SUCCS as excepting target {}", i, target_n);
                    }

                    asm[target_n].preds.push(i);

                    if let Some(next_inst) = ASMCode::find_next_inst(i, asm) {
                        // cur succ is next inst
                        asm[i].succs.push(next_inst);

                        // next inst's pred is cur
                        asm[next_inst].preds.push(i);

                        if TRACE_CFA {
                            trace!("inst {}: SET SUCCS as PEI fallthrough target {}", i, next_inst);
                        }
                    } else {
                        panic!("PEI does not have a fallthrough target");
                    }
                },
qinsoon's avatar
qinsoon committed
422 423 424 425 426 427
                ASMBranchTarget::Return => {
                    if TRACE_CFA {
                        trace!("inst {}: is a return", i);
                        trace!("inst {}: has no successor", i);
                    }
                }
qinsoon's avatar
qinsoon committed
428 429 430 431 432
                ASMBranchTarget::None => {
                    // not branch nor cond branch, succ is next inst
                    if TRACE_CFA {
                        trace!("inst {}: not a branch inst", i);
                    }
433
                    if let Some(next_inst) = ASMCode::find_next_inst(i, asm) {
qinsoon's avatar
qinsoon committed
434
                        if TRACE_CFA {
435
                            trace!("inst {}: set SUCCS as next inst {}", i, next_inst);
qinsoon's avatar
qinsoon committed
436
                        }
437
                        asm[i].succs.push(next_inst);
qinsoon's avatar
qinsoon committed
438 439 440 441
                    }
                }
            }
        }
442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463
    }

    fn find_prev_inst(i: usize, asm: &Vec<ASMInst>) -> Option<usize> {
        if i == 0 {
            None
        } else {
            let mut cur = i - 1;
            while cur != 0 {
                if !asm[cur].is_symbol {
                    return Some(cur);
                }

                if cur == 0 {
                    return None;
                } else {
                    cur -= 1;
                }
            }

            None
        }
    }
qinsoon's avatar
qinsoon committed
464

465 466 467 468 469 470 471 472 473 474 475
    fn find_next_inst(i: usize, asm: &Vec<ASMInst>) -> Option<usize> {
        if i >= asm.len() - 1 {
            None
        } else {
            let mut cur = i + 1;
            while cur < asm.len() {
                if !asm[cur].is_symbol {
                    return Some(cur);
                }

                cur += 1;
qinsoon's avatar
qinsoon committed
476
            }
477 478

            None
qinsoon's avatar
qinsoon committed
479 480
        }
    }
qinsoon's avatar
qinsoon committed
481

482 483 484 485 486
    fn find_last_inst(i: usize, asm: &Vec<ASMInst>) -> Option<usize> {
        if i == 0 {
            None
        } else {
            let mut cur = i;
487
            loop {
488 489 490 491 492 493 494 495 496 497 498 499 500
                if !asm[cur].is_symbol {
                    return Some(cur);
                }

                if cur == 0 {
                    return None;
                } else {
                    cur -= 1;
                }
            }
        }
    }

qinsoon's avatar
qinsoon committed
501 502 503
    fn add_frame_size_patchpoint(&mut self, patchpoint: ASMLocation) {
        self.frame_size_patchpoints.push(patchpoint);
    }
504 505 506 507
}

use std::any::Any;

508
impl MachineCode for ASMCode {
509 510 511
    fn as_any(&self) -> &Any {
        self
    }
512 513 514
    fn number_of_insts(&self) -> usize {
        self.code.len()
    }
515
    
516 517 518
    fn is_move(&self, index: usize) -> bool {
        let inst = self.code.get(index);
        match inst {
qinsoon's avatar
qinsoon committed
519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534
            Some(inst) => {
                let ref inst = inst.code;

                if inst.starts_with("movsd") || inst.starts_with("movss") {
                    // floating point move
                    true
                } else if inst.starts_with("movs") || inst.starts_with("movz") {
                    // sign extend, zero extend
                    false
                } else if inst.starts_with("mov") {
                    // normal mov
                    true
                } else {
                    false
                }
            },
535 536 537 538
            None => false
        }
    }
    
qinsoon's avatar
qinsoon committed
539
    fn is_using_mem_op(&self, index: usize) -> bool {
qinsoon's avatar
qinsoon committed
540
        self.code[index].is_mem_op_used
qinsoon's avatar
qinsoon committed
541
    }
542 543 544 545 546 547 548

    fn is_jmp(&self, index: usize) -> Option<MuName> {
        let inst = self.code.get(index);
        match inst {
            Some(inst) if inst.code.starts_with("jmp") => {
                let split : Vec<&str> = inst.code.split(' ').collect();

549
                Some(ASMCodeGen::unmangle_block_label(self.name.clone(), String::from(split[1])))
550 551 552 553 554 555 556 557 558 559 560
            }
            _ => None
        }
    }

    fn is_label(&self, index: usize) -> Option<MuName> {
        let inst = self.code.get(index);
        match inst {
            Some(inst) if inst.code.ends_with(':') => {
                let split : Vec<&str> = inst.code.split(':').collect();

561
                Some(ASMCodeGen::unmangle_block_label(self.name.clone(), String::from(split[0])))
562 563 564 565
            }
            _ => None
        }
    }
qinsoon's avatar
qinsoon committed
566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587

    fn is_spill_load(&self, index: usize) -> Option<P<Value>> {
        if let Some(inst) = self.code.get(index) {
            match inst.spill_info {
                Some(SpillMemInfo::Load(ref p)) => Some(p.clone()),
                _ => None
            }
        } else {
            None
        }
    }

    fn is_spill_store(&self, index: usize) -> Option<P<Value>> {
        if let Some(inst) = self.code.get(index) {
            match inst.spill_info {
                Some(SpillMemInfo::Store(ref p)) => Some(p.clone()),
                _ => None
            }
        } else {
            None
        }
    }
qinsoon's avatar
qinsoon committed
588
    
qinsoon's avatar
qinsoon committed
589
    fn get_succs(&self, index: usize) -> &Vec<usize> {
qinsoon's avatar
qinsoon committed
590
        &self.code[index].succs
qinsoon's avatar
qinsoon committed
591 592 593
    }
    
    fn get_preds(&self, index: usize) -> &Vec<usize> {
qinsoon's avatar
qinsoon committed
594
        &self.code[index].preds
qinsoon's avatar
qinsoon committed
595 596
    }
    
qinsoon's avatar
qinsoon committed
597 598
    fn get_inst_reg_uses(&self, index: usize) -> Vec<MuID> {
        self.code[index].uses.keys().map(|x| *x).collect()
599 600
    }
    
qinsoon's avatar
qinsoon committed
601 602
    fn get_inst_reg_defines(&self, index: usize) -> Vec<MuID> {
        self.code[index].defines.keys().map(|x| *x).collect()
603
    }
604
    
605
    fn replace_reg(&mut self, from: MuID, to: MuID) {
qinsoon's avatar
qinsoon committed
606 607
        for loc in self.get_define_locations(from) {
            let ref mut inst_to_patch = self.code[loc.line];
608 609 610 611 612 613 614

            // pick the right reg based on length
            let to_reg = x86_64::get_alias_for_length(to, loc.oplen);
            let to_reg_tag = to_reg.name().unwrap();
            let to_reg_string = "%".to_string() + &to_reg_tag;

            string_utils::replace(&mut inst_to_patch.code, loc.index, &to_reg_string, to_reg_string.len());
615
        }
616

qinsoon's avatar
qinsoon committed
617 618
        for loc in self.get_use_locations(from) {
            let ref mut inst_to_patch = self.code[loc.line];
619 620 621 622 623 624 625

            // pick the right reg based on length
            let to_reg = x86_64::get_alias_for_length(to, loc.oplen);
            let to_reg_tag = to_reg.name().unwrap();
            let to_reg_string = "%".to_string() + &to_reg_tag;

            string_utils::replace(&mut inst_to_patch.code, loc.index, &to_reg_string, to_reg_string.len());
626 627
        }
    }
628

629
    fn replace_define_tmp_for_inst(&mut self, from: MuID, to: MuID, inst: usize) {
630
        let to_reg_string : MuName = REG_PLACEHOLDER.clone();
631

qinsoon's avatar
qinsoon committed
632 633 634 635 636 637
        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() {
638
                string_utils::replace(&mut asm.code, loc.index, &to_reg_string, to_reg_string.len());
639 640
            }

qinsoon's avatar
qinsoon committed
641 642
            // remove old key, insert new one
            asm.defines.remove(&from);
643
            asm.defines.insert(to, define_locs);
644
        }
645 646 647
    }

    fn replace_use_tmp_for_inst(&mut self, from: MuID, to: MuID, inst: usize) {
648
        let to_reg_string : MuName = REG_PLACEHOLDER.clone();
649 650

        let asm = &mut self.code[inst];
qinsoon's avatar
qinsoon committed
651 652 653 654 655 656

        // 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() {
657
                string_utils::replace(&mut asm.code, loc.index, &to_reg_string, to_reg_string.len());
658 659
            }

qinsoon's avatar
qinsoon committed
660 661
            // remove old key, insert new one
            asm.uses.remove(&from);
662
            asm.uses.insert(to, use_locs);
663 664
        }
    }
665
    
666
    fn set_inst_nop(&mut self, index: usize) {
667 668 669
        self.code[index].code.clear();
//        self.code.remove(index);
//        self.code.insert(index, ASMInst::nop());
670
    }
qinsoon's avatar
qinsoon committed
671

672
    fn remove_unnecessary_callee_saved(&mut self, used_callee_saved: Vec<MuID>) -> HashSet<MuID> {
qinsoon's avatar
qinsoon committed
673 674 675
        // we always save rbp
        let rbp = x86_64::RBP.extract_ssa_id().unwrap();

676
        let find_op_other_than_rbp = |inst: &ASMInst| -> MuID {
qinsoon's avatar
qinsoon committed
677
            for id in inst.defines.keys() {
678 679
                if *id != rbp {
                    return *id;
qinsoon's avatar
qinsoon committed
680 681 682
                }
            }
            for id in inst.uses.keys() {
683 684
                if *id != rbp {
                    return *id;
qinsoon's avatar
qinsoon committed
685 686 687
                }
            }

688
            panic!("Expected to find a used register other than the rbp");
qinsoon's avatar
qinsoon committed
689 690 691
        };

        let mut inst_to_remove = vec![];
692
        let mut regs_to_remove = HashSet::new();
qinsoon's avatar
qinsoon committed
693 694 695 696

        for i in 0..self.number_of_insts() {
            let ref inst = self.code[i];

697 698 699 700 701 702 703
            match inst.spill_info {
                Some(SpillMemInfo::CalleeSaved) => {
                    let reg = find_op_other_than_rbp(inst);
                    if !used_callee_saved.contains(&reg) {
                        trace!("removing instruction {:?} for save/restore unnecessary callee saved regs", inst);
                        regs_to_remove.insert(reg);
                        inst_to_remove.push(i);
qinsoon's avatar
qinsoon committed
704 705
                    }
                }
706
                _ => {}
qinsoon's avatar
qinsoon committed
707 708 709 710 711 712 713 714 715
            }
        }

        for i in inst_to_remove {
            self.set_inst_nop(i);
        }

        regs_to_remove
    }
qinsoon's avatar
qinsoon committed
716

717
    fn patch_frame_size(&mut self, size: usize) {
qinsoon's avatar
qinsoon committed
718 719 720 721 722 723 724 725 726 727
        let size = size.to_string();

        debug_assert!(size.len() <= FRAME_SIZE_PLACEHOLDER_LEN);

        for loc in self.frame_size_patchpoints.iter() {
            let ref mut inst = self.code[loc.line];

            string_utils::replace(&mut inst.code, loc.index, &size, size.len());
        }
    }
728
    
729 730 731 732
    fn emit(&self) -> Vec<u8> {
        let mut ret = vec![];
        
        for inst in self.code.iter() {
733 734 735 736
            if !inst.is_symbol {
                ret.append(&mut "\t".to_string().into_bytes());
            }

737 738 739 740 741 742
            ret.append(&mut inst.code.clone().into_bytes());
            ret.append(&mut "\n".to_string().into_bytes());
        }
        
        ret
    }
743 744 745 746 747 748 749 750 751 752 753 754 755 756

    fn emit_inst(&self, index: usize) -> Vec<u8> {
        let mut ret = vec![];

        let ref inst = self.code[index];

        if !inst.is_symbol {
            ret.append(&mut "\t".to_string().into_bytes());
        }

        ret.append(&mut inst.code.clone().into_bytes());

        ret
    }
757
    
758 759
    fn trace_mc(&self) {
        trace!("");
760

761 762
        trace!("code for {}: \n", self.name);
        
763 764
        let n_insts = self.code.len();
        for i in 0..n_insts {
765
            self.trace_inst(i);
766 767
        }
        
768 769 770 771 772 773
        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
774
            self.code[i].preds, self.code[i].succs);
775
    }
776
    
777
    fn get_ir_block_livein(&self, block: &str) -> Option<&Vec<MuID>> {
qinsoon's avatar
qinsoon committed
778 779 780 781
        match self.blocks.get(block) {
            Some(ref block) => Some(&block.livein),
            None => None
        }
782 783
    }
    
784
    fn get_ir_block_liveout(&self, block: &str) -> Option<&Vec<MuID>> {
qinsoon's avatar
qinsoon committed
785 786 787 788
        match self.blocks.get(block) {
            Some(ref block) => Some(&block.liveout),
            None => None
        }
789 790
    }
    
791
    fn set_ir_block_livein(&mut self, block: &str, set: Vec<MuID>) {
qinsoon's avatar
qinsoon committed
792 793
        let block = self.blocks.get_mut(block).unwrap();
        block.livein = set;
794 795 796
    }
    
    fn set_ir_block_liveout(&mut self, block: &str, set: Vec<MuID>) {
qinsoon's avatar
qinsoon committed
797 798
        let block = self.blocks.get_mut(block).unwrap();
        block.liveout = set;
799 800
    }
    
qinsoon's avatar
qinsoon committed
801 802
    fn get_all_blocks(&self) -> Vec<MuName> {
        self.blocks.keys().map(|x| x.clone()).collect()
803
    }
804 805 806 807

    fn get_entry_block(&self) -> MuName {
        self.entry.clone()
    }
808
    
809
    fn get_block_range(&self, block: &str) -> Option<ops::Range<usize>> {
qinsoon's avatar
qinsoon committed
810 811
        match self.blocks.get(block) {
            Some(ref block) => Some(block.start_inst..block.end_inst),
812 813 814
            None => None
        }
    }
815

816 817 818 819 820 821 822 823 824 825
    fn get_block_for_inst(&self, index: usize) -> Option<MuName> {
        for (name, block) in self.blocks.iter() {
            if index >= block.start_inst && index < block.end_inst {
                return Some(name.clone());
            }
        }

        None
    }

826 827 828 829 830 831 832
    fn get_next_inst(&self, index: usize) -> Option<usize> {
        ASMCode::find_next_inst(index, &self.code)
    }

    fn get_last_inst(&self, index: usize) -> Option<usize> {
        ASMCode::find_last_inst(index, &self.code)
    }
833 834
}

qinsoon's avatar
qinsoon committed
835 836 837 838
#[derive(Clone, Debug)]
enum ASMBranchTarget {
    None,
    Conditional(MuName),
qinsoon's avatar
qinsoon committed
839
    Unconditional(MuName),
840
    PotentiallyExcepting(MuName),
qinsoon's avatar
qinsoon committed
841
    Return
qinsoon's avatar
qinsoon committed
842 843
}

844 845 846
#[derive(Clone, Debug)]
enum SpillMemInfo {
    Load(P<Value>),
847 848
    Store(P<Value>),
    CalleeSaved, // Callee saved record
849 850
}

qinsoon's avatar
qinsoon committed
851
#[derive(Clone, Debug)]
qinsoon's avatar
qinsoon committed
852
struct ASMInst {
853
    code: String,
qinsoon's avatar
qinsoon committed
854

855 856
    defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
    uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
qinsoon's avatar
qinsoon committed
857 858

    is_mem_op_used: bool,
859 860
    is_symbol: bool,

qinsoon's avatar
qinsoon committed
861 862
    preds: Vec<usize>,
    succs: Vec<usize>,
863 864 865
    branch: ASMBranchTarget,

    spill_info: Option<SpillMemInfo>
866 867
}

qinsoon's avatar
qinsoon committed
868 869 870
impl ASMInst {
    fn symbolic(line: String) -> ASMInst {
        ASMInst {
871
            code: line,
872 873
            defines: LinkedHashMap::new(),
            uses: LinkedHashMap::new(),
qinsoon's avatar
qinsoon committed
874
            is_mem_op_used: false,
875
            is_symbol: true,
qinsoon's avatar
qinsoon committed
876 877
            preds: vec![],
            succs: vec![],
878 879 880
            branch: ASMBranchTarget::None,

            spill_info: None
881 882 883
        }
    }
    
qinsoon's avatar
qinsoon committed
884 885
    fn inst(
        inst: String,
886 887
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
qinsoon's avatar
qinsoon committed
888
        is_mem_op_used: bool,
889 890
        target: ASMBranchTarget,
        spill_info: Option<SpillMemInfo>
qinsoon's avatar
qinsoon committed
891 892 893
    ) -> ASMInst
    {
        ASMInst {
894 895
            code: inst,
            defines: defines,
qinsoon's avatar
qinsoon committed
896
            uses: uses,
897
            is_symbol: false,
qinsoon's avatar
qinsoon committed
898 899 900
            is_mem_op_used: is_mem_op_used,
            preds: vec![],
            succs: vec![],
901 902 903
            branch: target,

            spill_info: spill_info
904 905
        }
    }
906
    
qinsoon's avatar
qinsoon committed
907 908
    fn nop() -> ASMInst {
        ASMInst {
909
            code: "".to_string(),
910 911
            defines: LinkedHashMap::new(),
            uses: LinkedHashMap::new(),
912
            is_symbol: false,
qinsoon's avatar
qinsoon committed
913 914 915
            is_mem_op_used: false,
            preds: vec![],
            succs: vec![],
916 917 918
            branch: ASMBranchTarget::None,

            spill_info: None
919 920
        }
    }
921 922
}

923
#[derive(Clone, Debug, PartialEq, Eq)]
924 925 926
struct ASMLocation {
    line: usize,
    index: usize,
927 928
    len: usize,
    oplen: usize,
929 930 931
}

impl ASMLocation {
932
    fn new(line: usize, index: usize, len: usize, oplen: usize) -> ASMLocation {
933
        ASMLocation{
qinsoon's avatar
qinsoon committed
934
            line: line,
935
            index: index,
936 937
            len: len,
            oplen: oplen
938 939 940 941
        }
    }
}

qinsoon's avatar
qinsoon committed
942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962
#[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![]
        }
    }
}

963
pub struct ASMCodeGen {
964
    cur: Option<Box<ASMCode>>
965 966
}

967
const REG_PLACEHOLDER_LEN : usize = 5;
968 969 970 971 972 973
lazy_static! {
    pub static ref REG_PLACEHOLDER : String = {
        let blank_spaces = [' ' as u8; REG_PLACEHOLDER_LEN];
        
        format!("%{}", str::from_utf8(&blank_spaces).unwrap())
    };
974 975
}

qinsoon's avatar
qinsoon committed
976 977 978 979 980 981 982 983
const FRAME_SIZE_PLACEHOLDER_LEN : usize = 10; // a frame is smaller than 1 << 10
lazy_static! {
    pub static ref FRAME_SIZE_PLACEHOLDER : String = {
        let blank_spaces = [' ' as u8; FRAME_SIZE_PLACEHOLDER_LEN];
        format!("{}", str::from_utf8(&blank_spaces).unwrap())
    };
}

984 985
impl ASMCodeGen {
    pub fn new() -> ASMCodeGen {
986
        ASMCodeGen {
987
            cur: None
988 989 990 991 992 993 994 995 996 997 998
        }
    }
    
    fn cur(&self) -> &ASMCode {
        self.cur.as_ref().unwrap()
    }
    
    fn cur_mut(&mut self) -> &mut ASMCode {
        self.cur.as_mut().unwrap()
    }
    
999 1000 1001 1002
    fn line(&self) -> usize {
        self.cur().code.len()
    }
    
1003 1004
    fn add_asm_label(&mut self, code: String) {
        let l = self.line();
qinsoon's avatar
qinsoon committed
1005
        self.cur_mut().code.push(ASMInst::symbolic(code));
1006 1007
    }
    
1008
    fn add_asm_block_label(&mut self, code: String, block_name: MuName) {
1009
        let l = self.line();
qinsoon's avatar
qinsoon committed
1010
        self.cur_mut().code.push(ASMInst::symbolic(code));
1011 1012
    }
    
1013
    fn add_asm_symbolic(&mut self, code: String){
qinsoon's avatar
qinsoon committed
1014
        self.cur_mut().code.push(ASMInst::symbolic(code));
1015 1016
    }
    
1017 1018
    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
1019
    }
1020 1021 1022 1023 1024 1025 1026 1027

    fn add_asm_call_with_extra_uses(&mut self,
                              code: String,
                              extra_uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
                              potentially_excepting: Option<MuName>) {
        let uses = extra_uses;

        // defines
1028
        let mut defines : LinkedHashMap<MuID, Vec<ASMLocation>> = LinkedHashMap::new();
1029
        // return registers get defined
qinsoon's avatar
qinsoon committed
1030 1031 1032 1033 1034 1035
        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![]);
        }
1036
        // caller saved register will be destroyed
qinsoon's avatar
qinsoon committed
1037 1038 1039 1040 1041 1042 1043 1044 1045 1046
        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![]);
            }
        }
1047

1048 1049 1050 1051 1052 1053 1054
        self.add_asm_inst_internal(code, defines, uses, false, {
            if potentially_excepting.is_some() {
                ASMBranchTarget::PotentiallyExcepting(potentially_excepting.unwrap())
            } else {
                ASMBranchTarget::None
            }
        }, None)
1055 1056
    }
    
1057 1058 1059 1060
    fn add_asm_call(&mut self, code: String, potentially_excepting: Option<MuName>) {
        self.add_asm_call_with_extra_uses(code, LinkedHashMap::new(), potentially_excepting);
    }
    
1061
    fn add_asm_ret(&mut self, code: String) {
1062 1063 1064 1065
        // return instruction does not use anything (not RETURN REGS)
        // otherwise it will keep RETURN REGS alive
        // and if there is no actual move into RETURN REGS, it will keep RETURN REGS for alive for very long
        // and prevents anything using those regsiters
1066
        self.add_asm_inst_internal(code, linked_hashmap!{}, linked_hashmap!{}, false, ASMBranchTarget::Return, None);
1067 1068
    }
    
1069
    fn add_asm_branch(&mut self, code: String, target: MuName) {
1070
        self.add_asm_inst_internal(code, linked_hashmap!{}, linked_hashmap!{}, false, ASMBranchTarget::Unconditional(target), None);
1071 1072
    }
    
1073
    fn add_asm_branch2(&mut self, code: String, target: MuName) {
1074
        self.add_asm_inst_internal(code, linked_hashmap!{}, linked_hashmap!{}, false, ASMBranchTarget::Conditional(target), None);
1075 1076 1077 1078 1079
    }
    
    fn add_asm_inst(
        &mut self, 
        code: String, 
1080 1081
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
1082 1083 1084 1085 1086
        is_using_mem_op: bool
    ) {
        self.add_asm_inst_internal(code, defines, uses, is_using_mem_op, ASMBranchTarget::None, None)
    }

1087 1088 1089 1090 1091 1092 1093 1094 1095 1096
    fn add_asm_inst_with_callee_saved(
        &mut self,
        code: String,
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
        is_using_mem_op: bool,
    ) {
        self.add_asm_inst_internal(code, defines, uses, is_using_mem_op, ASMBranchTarget::None, Some(SpillMemInfo::CalleeSaved))
    }

1097 1098 1099 1100 1101 1102 1103 1104 1105
    fn add_asm_inst_with_spill(
        &mut self,
        code: String,
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
        is_using_mem_op: bool,
        spill_info: SpillMemInfo
    ) {
        self.add_asm_inst_internal(code, defines, uses, is_using_mem_op, ASMBranchTarget::None, Some(spill_info))
qinsoon's avatar
qinsoon committed
1106 1107 1108 1109 1110
    }

    fn add_asm_inst_internal(
        &mut self,
        code: String,
1111 1112
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
qinsoon's avatar
qinsoon committed
1113
        is_using_mem_op: bool,
1114 1115
        target: ASMBranchTarget,
        spill_info: Option<SpillMemInfo>)
1116
    {
1117 1118
        let line = self.line();
        trace!("asm: {}", code);
qinsoon's avatar
qinsoon committed
1119 1120
        trace!("     defines: {:?}", defines);
        trace!("     uses: {:?}", uses);
1121
        let mc = self.cur_mut();
qinsoon's avatar
qinsoon committed
1122

1123
        // put the instruction
1124
        mc.code.push(ASMInst::inst(code, defines, uses, is_using_mem_op, target, spill_info));
1125 1126
    }
    
1127
    fn prepare_reg(&self, op: &P<Value>, loc: usize) -> (String, MuID, ASMLocation) {
1128 1129 1130 1131 1132 1133 1134
        if cfg!(debug_assertions) {
            match op.v {
                Value_::SSAVar(_) => {},
                _ => panic!("expecting register op")
            }
        }
        
1135 1136
        let str = self.asm_reg_op(op);
        let len = str.len();
1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150
        (str, op.extract_ssa_id().unwrap(), ASMLocation::new(self.line(), loc, len, check_op_len(op)))
    }

    fn prepare_fpreg(&self, op: &P<Value>, loc: usize) -> (String, MuID, ASMLocation) {
        if cfg!(debug_assertions) {
            match op.v {
                Value_::SSAVar(_) => {},
                _ => panic!("expecting register op")
            }
        }

        let str = self.asm_reg_op(op);
        let len = str.len();
        (str, op.extract_ssa_id().unwrap(), ASMLocation::new(self.line(), loc, len, 64))
1151 1152 1153
    }
    
    fn prepare_machine_reg(&self, op: &P<Value>) -> MuID {
1154 1155 1156 1157 1158 1159 1160
        if cfg!(debug_assertions) {
            match op.v {
                Value_::SSAVar(_) => {},
                _ => panic!("expecting machine register op")
            }
        }        
        
1161
        op.extract_ssa_id().unwrap()
1162
    }
1163
    
1164
    #[allow(unused_assignments)]
1165
    fn prepare_mem(&self, op: &P<Value>, loc: usize) -> (String, LinkedHashMap<MuID, Vec<ASMLocation>>) {
1166 1167 1168
        if cfg!(debug_assertions) {
            match op.v {
                Value_::Memory(_) => {},
qinsoon's avatar
qinsoon committed
1169
                _ => panic!("expecting memory op")
1170 1171
            }
        }        
qinsoon's avatar
qinsoon committed
1172

1173 1174 1175 1176
        let mut ids : Vec<MuID> = vec![];
        let mut locs : Vec<ASMLocation> = vec![];
        let mut result_str : String = "".to_string();
        
1177
        let mut loc_cursor : usize = loc;
1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188
        
        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
qinsoon's avatar
qinsoon committed
1189
                            let (str, id, loc) = self.prepare_reg(offset, loc_cursor);
1190 1191 1192 1193 1194 1195 1196 1197
                            
                            result_str.push_str(&str);
                            ids.push(id);
                            locs.push(loc);
                            
                            loc_cursor += str.len();
                        },
                        Value_::Constant(Constant::Int(val)) => {
1198
                            let str = (val as i32).to_string();
1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235
                            
                            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)) => {
1236
                            let str = (val as i32).to_string();
1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259
                            
                            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;
            },
1260 1261
            Value_::Memory(MemoryLocation::Symbolic{ref base, ref label, is_global}) => {
                if base.is_some() && base.as_ref().unwrap().id() == x86_64::RIP.id() && is_global {
qinsoon's avatar
qinsoon committed
1262
                    // pc relative address
1263 1264
                    let pic_symbol = pic_symbol(label.clone());
//                    let pic_symbol = symbol(label.clone()); // not sure if we need this
qinsoon's avatar
qinsoon committed
1265 1266 1267 1268 1269 1270 1271
                    result_str.push_str(&pic_symbol);
                    loc_cursor += label.len();
                } else {
                    let symbol = symbol(label.clone());
                    result_str.push_str(&symbol);
                    loc_cursor += label.len();
                }
1272 1273 1274 1275 1276 1277 1278 1279 1280 1281
                
                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
1282

1283
                    result_str.push(')');
qinsoon's avatar
qinsoon committed
1284
                    loc_cursor += 1;
1285 1286 1287 1288
                }
            },
            _ => panic!("expect mem location as value")
        }
qinsoon's avatar
qinsoon committed
1289

1290 1291
        let uses : LinkedHashMap<MuID, Vec<ASMLocation>> = {
            let mut map : LinkedHashMap<MuID, Vec<ASMLocation>> = linked_hashmap!{};
qinsoon's avatar
qinsoon committed
1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306
            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)
1307
    }
1308 1309 1310 1311 1312 1313 1314 1315 1316 1317

    fn prepare_imm(&self, op: i32, len: usize) -> i32 {
        match len {
            64 => op,
            32 => op,
            16 => op as i16 as i32,
            8  => op as i8  as i32,
            _ => unimplemented!()
        }
    }
1318
    
1319 1320
    fn asm_reg_op(&self, op: &P<Value>) -> String {
        let id = op.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
1321
        if id < MACHINE_ID_END {
1322
            // machine reg
1323
            format!("%{}", op.name().unwrap())
1324 1325 1326 1327 1328 1329
        } else {
            // virtual register, use place holder
            REG_PLACEHOLDER.clone()
        }
    }
    
qinsoon's avatar
qinsoon committed
1330 1331
    fn mangle_block_label(&self, label: MuName) -> String {
        format!("{}_{}", self.cur().name, label)
1332
    }
1333

1334 1335 1336 1337 1338 1339 1340
    fn unmangle_block_label(fn_name: MuName, label: String) -> MuName {
        // input: _fn_name_BLOCK_NAME
        // return BLOCK_NAME
        let split : Vec<&str> = label.splitn(2, &(fn_name + "_")).collect();
        String::from(split[1])
    }

1341 1342 1343
    fn finish_code_sequence_asm(&mut self) -> Box<ASMCode> {
        self.cur.take().unwrap()
    }
1344

1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361
    fn internal_uniop_def_r(&mut self, inst: &str, op: &P<Value>) {
        trace!("emit: {} {}", inst, op);

        let (reg, id, loc) = self.prepare_reg(op, inst.len() + 1);

        let asm = format!("{} {}", inst, reg);

        self.add_asm_inst(
            asm,
            linked_hashmap!{
                id => vec![loc]
            },
            linked_hashmap!{},
            false
        )
    }

1362 1363
    fn internal_binop_no_def_r_r(&mut self, inst: &str, op1: &P<Value>, op2: &P<Value>) {
        let len = check_op_len(op1);
1364

1365 1366 1367
        // with postfix
        let inst = inst.to_string() + &op_postfix(len);
        trace!("emit: {} {} {}", inst, op1, op2);
1368

1369 1370
        let (reg1, id1, loc1) = self.prepare_reg(op1, inst.len() + 1);
        let (reg2, id2, loc2) = self.prepare_reg(op2, inst.len() + 1 + reg1.len() + 1);
1371

1372
        let asm = format!("{} {},{}", inst, reg1, reg2);
1373

1374 1375
        self.add_asm_inst(
            asm,
1376
            linked_hashmap!{},
1377 1378
            {
                if id1 == id2 {
1379
                    linked_hashmap!{
1380
                        id1 => vec![loc1, loc2]
1381
                    }
1382
                } else {
1383
                    linked_hashmap!{
1384 1385 1386 1387 1388 1389 1390
                        id1 => vec![loc1],
                        id2 => vec![loc2]
                    }
                }
            },
            false
        )
1391 1392
    }

1393 1394
    fn internal_binop_no_def_imm_r(&mut self, inst: &str, op1: i32, op2: &P<Value>) {
        let len = check_op_len(op2);
1395

1396 1397
        let inst = inst.to_string() + &op_postfix(len);
        trace!("emit: {} {} {}", inst, op1, op2);
1398

1399 1400
        let imm = self.prepare_imm(op1, len);
        let (reg2, id2, loc2) = self.prepare_reg(op2, inst.len() + 1 + 1 + imm.to_string().len() + 1);
1401

1402
        let asm = format!("{} ${},{}", inst, imm, reg2);
1403

1404 1405
        self.add_asm_inst(
            asm,
1406 1407
            linked_hashmap!{},
            linked_hashmap!{
1408 1409 1410 1411
                id2 => vec![loc2]
            },
            false
        )
1412 1413
    }

1414 1415
    fn internal_binop_no_def_mem_r(&mut self, inst: &str, op1: &P<Value>, op2: &P<Value>) {
        let len = check_op_len(op2);
1416

1417 1418
        let inst = inst.to_string() + &op_postfix(len);
        trace!("emit: {} {} {}", inst, op1, op2);
1419

1420 1421
        let (mem, mut uses)  = self.prepare_mem(op1, inst.len() + 1);
        let (reg, id1, loc1) = self.prepare_reg(op2, inst.len() + 1 + mem.len() + 1);
1422

1423
        let asm = format!("{} {},{}", inst, mem, reg);
1424

1425 1426 1427 1428 1429 1430
        // merge use vec
        if uses.contains_key(&id1) {
            let mut locs = uses.get_mut(&id1).unwrap();
            vec_utils::add_unique(locs, loc1.clone());
        } else {
            uses.insert(id1, vec![loc1]);
1431
        }
1432 1433 1434

        self.add_asm_inst(
            asm,
1435
            linked_hashmap!{},
1436 1437 1438
            uses,
            true
        )
1439 1440
    }

1441 1442
    fn internal_binop_no_def_r_mem(&mut self, inst: &str, op1: &P<Value>, op2: &P<Value>) {
        let len = check_op_len(op1);
1443

1444 1445
        let inst = inst.to_string() + &op_postfix(len);
        trace!("emit: {} {} {}", inst, op1, op2);
1446

1447 1448
        let (mem, mut uses) = self.prepare_mem(op2, inst.len() + 1);
        let (reg, id1, loc1) = self.prepare_reg(op1, inst.len() + 1 + mem.len() + 1);
1449

1450 1451 1452 1453 1454
        if uses.contains_key(&id1) {
            let mut locs = uses.get_mut(&id1).unwrap();
            vec_utils::add_unique(locs, loc1.clone());
        } else {
            uses.insert(id1, vec![loc1.clone()]);
1455 1456
        }

1457
        let asm = format!("{} {},{}", inst, mem, reg);
1458

1459 1460
        self.add_asm_inst(
            asm,
1461
            linked_hashmap!{},
1462 1463 1464
            uses,
            true
        )
1465 1466
    }

1467