asm_backend.rs 127 KB
Newer Older
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1
// Copyright 2017 The Australian National University
2
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
3 4 5
// 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
6
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
7
//     http://www.apache.org/licenses/LICENSE-2.0
8
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
9 10 11 12 13 14
// 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 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
use compiler::backend::AOT_EMIT_CONTEXT_FILE;
use compiler::backend::RegGroup;
use utils::ByteSize;
use utils::Address;
use utils::POINTER_SIZE;
use compiler::backend::aarch64::*;

use compiler::backend::{Reg, Mem};
use compiler::machine_code::MachineCode;
use vm::VM;
use runtime::ValueLocation;

use utils::vec_utils;
use utils::string_utils;
use utils::LinkedHashMap;

use ast::ptr::P;
use ast::ir::*;
33
use ast::types;
34 35 36 37

use std::str;
use std::usize;
use std::ops;
38
use std::collections::HashSet;
39
use std::sync::RwLock;
40

41 42 43 44 45
macro_rules! trace_emit {
    ($arg1:tt $($arg:tt)*) => {
        trace!(concat!("emit: ", $arg1) $($arg)*)
    }
}
46 47 48 49
struct ASMCode {
    name: MuName,
    code: Vec<ASMInst>,

50
    entry: MuName,
51 52
    blocks: LinkedHashMap<MuName, ASMBlock>,

53
    frame_size_patchpoints: Vec<ASMLocation>
54 55 56 57 58 59 60 61 62 63 64 65 66
}

unsafe impl Send for ASMCode {}
unsafe impl Sync for ASMCode {}

impl ASMCode {
    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());
67
                }
68 69 70 71 72 73 74 75 76 77 78 79 80 81
                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());
82
                }
83 84 85 86 87 88 89 90 91 92 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
                None => {}
            }
        }

        ret
    }

    fn is_block_start(&self, inst: usize) -> bool {
        for block in self.blocks.values() {
            if block.start_inst == inst {
                return true;
            }
        }
        false
    }

    fn is_last_inst_in_block(&self, inst: usize) -> bool {
        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)
    }

    fn rewrite_insert(
        &self,
        insert_before: LinkedHashMap<usize, Vec<Box<ASMCode>>>,
121
        insert_after: LinkedHashMap<usize, Vec<Box<ASMCode>>>
122
    ) -> Box<ASMCode> {
123 124 125 126 127 128
        trace!("insert spilling code");
        let mut ret = ASMCode {
            name: self.name.clone(),
            entry: self.entry.clone(),
            code: vec![],
            blocks: linked_hashmap!{},
129
            frame_size_patchpoints: vec![]
130 131 132
        };

        // iterate through old machine code
133
        let mut inst_offset = 0; // how many instructions has been inserted
134 135 136 137
        let mut cur_block_start = usize::MAX;

        // inst N in old machine code is N' in new machine code
        // this map stores the relationship
138
        let mut location_map: LinkedHashMap<usize, usize> = LinkedHashMap::new();
139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200

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

            if self.is_block_start(i) {
                cur_block_start = i + inst_offset;
                trace!("  block start is shifted to {}", cur_block_start);
            }

            // 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();
                    trace!("  inserted {} insts before", insert.number_of_insts());
                }
            }

            // copy this instruction
            let mut inst = self.code[i].clone();

            // old ith inst is now the (i + inst_offset)th instruction
            location_map.insert(i, i + inst_offset);
            trace!("  Inst{} is now Inst{}", i, i + inst_offset);

            // 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;
                }
            }
            // 2. we need to delete existing preds/succs - CFA is required later
            inst.preds.clear();
            inst.succs.clear();
            // 3. add the inst
            ret.code.push(inst);


            // insert code after this instruction
            if insert_after.contains_key(&i) {
                for insert in insert_after.get(&i).unwrap() {
                    ret.append_code_sequence_all(insert);
                    inst_offset += insert.number_of_insts();
                    trace!("  inserted {} insts after", insert.number_of_insts());
                }
            }

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

                // copy the block
                let (name, block) = self.get_block_by_inst(i);

201
                let new_block = ASMBlock {
202 203 204 205
                    start_inst: cur_block_start,
                    end_inst: cur_block_end,

                    livein: vec![],
206
                    liveout: vec![]
207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224
                };

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

                cur_block_start = usize::MAX;

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

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

            ret.frame_size_patchpoints.push(new_patchpoint);
        }

        ret.control_flow_analysis();

        Box::new(ret)
    }

236
    fn append_code_sequence(&mut self, another: &Box<ASMCode>, start_inst: usize, n_insts: usize) {
237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270
        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);
        }
    }

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

    fn control_flow_analysis(&mut self) {
271
        const TRACE_CFA: bool = true;
272 273 274 275 276 277 278

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

        let ref mut asm = self.code;

        for i in 0..n_insts {
279
            trace_if!(TRACE_CFA, "---inst {}---", i);
280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300

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

301 302 303 304 305 306
                                    trace_if!(
                                        TRACE_CFA,
                                        "inst {}: set PREDS as previous inst - fallthrough {}",
                                        i,
                                        last_inst
                                    );
307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329
                                }
                            }
                            // otherwise do nothing
                            _ => {}
                        }
                    }
                    None => {}
                }
            }

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

330 331
                    trace_if!(TRACE_CFA, "inst {}: is a branch to {}", i, target);
                    trace_if!(TRACE_CFA, "inst {}: branch target index is {}", i, target_n);
332 333 334 335 336 337 338 339 340 341 342 343 344
                    trace_if!(
                        TRACE_CFA,
                        "inst {}: set SUCCS as branch target {}",
                        i,
                        target_n
                    );
                    trace_if!(
                        TRACE_CFA,
                        "inst {}: set PREDS as branch source {}",
                        target_n,
                        i
                    );
                }
345 346 347 348 349 350 351
                ASMBranchTarget::Conditional(ref target) => {
                    // branch to target
                    let target_n = self.blocks.get(target).unwrap().start_inst;

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

352 353
                    trace_if!(TRACE_CFA, "inst {}: is a cond branch to {}", i, target);
                    trace_if!(TRACE_CFA, "inst {}: branch target index is {}", i, target_n);
354 355 356 357 358 359
                    trace_if!(
                        TRACE_CFA,
                        "inst {}: set SUCCS as branch target {}",
                        i,
                        target_n
                    );
360 361 362

                    // target's pred is cur
                    asm[target_n].preds.push(i);
363
                    trace_if!(TRACE_CFA, "inst {}: set PREDS as {}", target_n, i);
364 365 366 367 368 369 370 371

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

372 373 374 375 376 377
                        trace_if!(
                            TRACE_CFA,
                            "inst {}: SET SUCCS as c-branch fallthrough target {}",
                            i,
                            next_inst
                        );
378 379 380
                    } else {
                        panic!("conditional branch does not have a fallthrough target");
                    }
381
                }
382 383 384 385 386 387 388
                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);

389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406
                    trace_if!(
                        TRACE_CFA,
                        "inst {}: is potentially excepting to {}",
                        i,
                        target
                    );
                    trace_if!(
                        TRACE_CFA,
                        "inst {}: excepting target index is {}",
                        i,
                        target_n
                    );
                    trace_if!(
                        TRACE_CFA,
                        "inst {}: set SUCCS as excepting target {}",
                        i,
                        target_n
                    );
407 408 409 410 411 412 413 414 415 416

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

417 418 419 420 421 422
                        trace_if!(
                            TRACE_CFA,
                            "inst {}: SET SUCCS as PEI fallthrough target {}",
                            i,
                            next_inst
                        );
423 424 425
                    } else {
                        panic!("PEI does not have a fallthrough target");
                    }
426
                }
427
                ASMBranchTarget::Return => {
428 429
                    trace_if!(TRACE_CFA, "inst {}: is a return", i);
                    trace_if!(TRACE_CFA, "inst {}: has no successor", i);
430 431 432
                }
                ASMBranchTarget::None => {
                    // not branch nor cond branch, succ is next inst
433
                    trace_if!(TRACE_CFA, "inst {}: not a branch inst", i);
434
                    if let Some(next_inst) = ASMCode::find_next_inst(i, asm) {
435 436 437 438 439 440
                        trace_if!(
                            TRACE_CFA,
                            "inst {}: set SUCCS as next inst {}",
                            i,
                            next_inst
                        );
441 442 443 444
                        asm[i].succs.push(next_inst);
                    }
                }
                ASMBranchTarget::UnconditionalReg(id) => {
445 446 447 448 449 450
                    trace_if!(
                        TRACE_CFA,
                        "inst {}: is an unconditional branch to reg {}",
                        i,
                        id
                    );
451
                    trace_if!(TRACE_CFA, "inst {}: has no successor", i);
452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540
                }
            }
        }
    }

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

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

            None
        }
    }

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

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

    fn add_frame_size_patchpoint(&mut self, patchpoint: ASMLocation) {
        self.frame_size_patchpoints.push(patchpoint);
    }
}

use std::any::Any;

impl MachineCode for ASMCode {
    fn as_any(&self) -> &Any {
        self
    }
    fn number_of_insts(&self) -> usize {
        self.code.len()
    }

    fn is_move(&self, index: usize) -> bool {
        let inst = self.code.get(index);
        match inst {
            Some(inst) => {
                let ref inst = inst.code;

                if inst.starts_with("MOV ") || inst.starts_with("FMOV ") {
                    // normal mov
                    true
                } else {
                    false
                }
541
            }
542
            None => false
543 544 545 546 547 548 549 550 551 552
        }
    }

    fn is_using_mem_op(&self, index: usize) -> bool {
        self.code[index].is_mem_op_used
    }

    fn is_jmp(&self, index: usize) -> Option<MuName> {
        let inst = self.code.get(index);
        match inst {
553 554
            Some(inst) if inst.code.starts_with("B.") || inst.code.starts_with("B ") => {
                // Destination is the first argument
555
                let split: Vec<&str> = inst.code.split(' ').collect();
556
                Some(demangle_name(String::from(split[1])))
557
            }
558
            _ => None
559 560 561 562 563 564 565
        }
    }

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

568
                Some(demangle_name(String::from(split[0])))
569
            }
570
            _ => None
571 572 573 574 575 576 577
        }
    }

    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()),
578
                _ => None
579 580 581 582 583 584 585 586 587 588
            }
        } 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()),
589
                _ => None
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
            }
        } else {
            None
        }
    }

    fn get_succs(&self, index: usize) -> &Vec<usize> {
        &self.code[index].succs
    }

    fn get_preds(&self, index: usize) -> &Vec<usize> {
        &self.code[index].preds
    }

    fn get_inst_reg_uses(&self, index: usize) -> Vec<MuID> {
        self.code[index].uses.keys().map(|x| *x).collect()
    }

    fn get_inst_reg_defines(&self, index: usize) -> Vec<MuID> {
        self.code[index].defines.keys().map(|x| *x).collect()
    }

    fn replace_reg(&mut self, from: MuID, to: MuID) {
        for loc in self.get_define_locations(from) {
            let ref mut inst_to_patch = self.code[loc.line];

            // pick the right reg based on length
            let to_reg = get_alias_for_length(to, loc.oplen);
618
            let to_reg_string = to_reg.name();
619

620 621 622 623
            string_utils::replace(
                &mut inst_to_patch.code,
                loc.index,
                &to_reg_string,
624
                to_reg_string.len()
625
            );
626 627 628 629 630 631 632
        }

        for loc in self.get_use_locations(from) {
            let ref mut inst_to_patch = self.code[loc.line];

            // pick the right reg based on length
            let to_reg = get_alias_for_length(to, loc.oplen);
633
            let to_reg_string = to_reg.name();
634

635 636 637 638
            string_utils::replace(
                &mut inst_to_patch.code,
                loc.index,
                &to_reg_string,
639
                to_reg_string.len()
640
            );
641 642 643 644
        }
    }

    fn replace_define_tmp_for_inst(&mut self, from: MuID, to: MuID, inst: usize) {
645
        let to_reg_string: MuName = REG_PLACEHOLDER.clone();
646 647 648 649 650 651 652

        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() {
653 654 655 656
                string_utils::replace(
                    &mut asm.code,
                    loc.index,
                    &to_reg_string,
657
                    to_reg_string.len()
658
                );
659 660 661 662 663 664 665 666 667
            }

            // remove old key, insert new one
            asm.defines.remove(&from);
            asm.defines.insert(to, define_locs);
        }
    }

    fn replace_use_tmp_for_inst(&mut self, from: MuID, to: MuID, inst: usize) {
668
        let to_reg_string: MuName = REG_PLACEHOLDER.clone();
669 670 671 672 673 674 675 676

        let asm = &mut self.code[inst];

        // 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() {
677 678 679 680
                string_utils::replace(
                    &mut asm.code,
                    loc.index,
                    &to_reg_string,
681
                    to_reg_string.len()
682
                );
683 684 685 686 687 688 689 690
            }

            // remove old key, insert new one
            asm.uses.remove(&from);
            asm.uses.insert(to, use_locs);
        }
    }

691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708
    fn replace_branch_dest(&mut self, inst: usize, new_dest: &str, succ: usize) {
        {
            let asm = &mut self.code[inst];

            let inst = String::from(asm.code.split_whitespace().next().unwrap());
            asm.code = format!("{} {}", inst, mangle_name(String::from(new_dest)));
            asm.succs.clear();
            asm.succs.push(succ);
        }
        {
            let asm = &mut self.code[succ];

            if !asm.preds.contains(&inst) {
                asm.preds.push(inst);
            }
        }
    }

709 710
    fn set_inst_nop(&mut self, index: usize) {
        self.code[index].code.clear();
711 712
        //        self.code.remove(index);
        //        self.code.insert(index, ASMInst::nop());
713 714
    }

715
    fn remove_unnecessary_callee_saved(&mut self, used_callee_saved: Vec<MuID>) -> HashSet<MuID> {
716
        // every push pair (STP)/and pop pair (LDP) will use/define SP
717
        let fp = FP.extract_ssa_id().unwrap();
718

719 720
        // Note: this version assumes only 1 callee is pushed or poped
        let find_op_other_than_fp = |inst: &ASMInst| -> MuID {
721
            for id in inst.defines.keys() {
722 723
                if *id != fp {
                    return *id;
724 725 726
                }
            }
            for id in inst.uses.keys() {
727 728
                if *id != fp {
                    return *id;
729 730 731
                }
            }

732
            panic!("Expected to find a used register other than the FP");
733 734 735
        };

        let mut inst_to_remove = vec![];
736
        let mut regs_to_remove = HashSet::new();
737 738 739 740

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

741 742 743 744 745 746
            match inst.spill_info {
                Some(SpillMemInfo::CalleeSaved) => {
                    let reg = find_op_other_than_fp(inst);
                    if !used_callee_saved.contains(&reg) {
                        inst_to_remove.push(i);
                        regs_to_remove.insert(reg);
747 748
                    }
                }
749
                _ => {}
750 751 752 753 754 755
            }
        }

        for i in inst_to_remove {
            self.set_inst_nop(i);
        }
756
        regs_to_remove
757 758
    }

759
    fn patch_frame_size(&mut self, size: usize) {
760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815
        debug_assert!(size % 16 == 0);

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

    fn emit(&self) -> Vec<u8> {
        let mut ret = vec![];

        for inst in self.code.iter() {
            if !inst.is_symbol {
                ret.append(&mut "\t".to_string().into_bytes());
            }

            ret.append(&mut inst.code.clone().into_bytes());
            ret.append(&mut "\n".to_string().into_bytes());
        }

        ret
    }

    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
    }

    fn trace_mc(&self) {
        trace!("");

        trace!("code for {}: \n", self.name);

        let n_insts = self.code.len();
        for i in 0..n_insts {
            self.trace_inst(i);
        }

        trace!("")
    }

    fn trace_inst(&self, i: usize) {
816 817 818 819 820 821 822 823 824
        trace!(
            "#{}\t{:30}\t\tdefine: {:?}\tuses: {:?}\tpred: {:?}\tsucc: {:?}",
            i,
            demangle_text(self.code[i].code.clone()),
            self.get_inst_reg_defines(i),
            self.get_inst_reg_uses(i),
            self.code[i].preds,
            self.code[i].succs
        );
825 826 827 828 829
    }

    fn get_ir_block_livein(&self, block: &str) -> Option<&Vec<MuID>> {
        match self.blocks.get(block) {
            Some(ref block) => Some(&block.livein),
830
            None => None
831 832 833 834 835 836
        }
    }

    fn get_ir_block_liveout(&self, block: &str) -> Option<&Vec<MuID>> {
        match self.blocks.get(block) {
            Some(ref block) => Some(&block.liveout),
837
            None => None
838 839 840 841 842 843 844 845 846 847 848 849 850
        }
    }

    fn set_ir_block_livein(&mut self, block: &str, set: Vec<MuID>) {
        let block = self.blocks.get_mut(block).unwrap();
        block.livein = set;
    }

    fn set_ir_block_liveout(&mut self, block: &str, set: Vec<MuID>) {
        let block = self.blocks.get_mut(block).unwrap();
        block.liveout = set;
    }

851 852 853
    fn get_all_blocks(&self) -> Vec<MuName> {
        self.blocks.keys().map(|x| x.clone()).collect()
    }
854 855 856 857 858 859 860 861

    fn get_entry_block(&self) -> MuName {
        self.entry.clone()
    }

    fn get_block_range(&self, block: &str) -> Option<ops::Range<usize>> {
        match self.blocks.get(block) {
            Some(ref block) => Some(block.start_inst..block.end_inst),
862
            None => None
863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890
        }
    }

    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
    }

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

#[derive(Clone, Debug)]
enum ASMBranchTarget {
    None,
    Conditional(MuName),
    Unconditional(MuName),
    PotentiallyExcepting(MuName),
    Return,
891
    UnconditionalReg(MuID)
892 893 894 895 896
}

#[derive(Clone, Debug)]
enum SpillMemInfo {
    Load(P<Value>),
897
    Store(P<Value>),
898
    CalleeSaved // Callee saved record
899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914
}

#[derive(Clone, Debug)]
struct ASMInst {
    code: String,

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

    is_mem_op_used: bool,
    is_symbol: bool,

    preds: Vec<usize>,
    succs: Vec<usize>,
    branch: ASMBranchTarget,

915
    spill_info: Option<SpillMemInfo>
916 917 918 919 920 921 922 923 924 925 926 927 928 929
}

impl ASMInst {
    fn symbolic(line: String) -> ASMInst {
        ASMInst {
            code: line,
            defines: LinkedHashMap::new(),
            uses: LinkedHashMap::new(),
            is_mem_op_used: false,
            is_symbol: true,
            preds: vec![],
            succs: vec![],
            branch: ASMBranchTarget::None,

930
            spill_info: None
931 932 933 934 935 936 937 938 939
        }
    }

    fn inst(
        inst: String,
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
        is_mem_op_used: bool,
        target: ASMBranchTarget,
940
        spill_info: Option<SpillMemInfo>
941
    ) -> ASMInst {
942 943 944 945 946 947 948 949 950 951
        ASMInst {
            code: inst,
            defines: defines,
            uses: uses,
            is_symbol: false,
            is_mem_op_used: is_mem_op_used,
            preds: vec![],
            succs: vec![],
            branch: target,

952
            spill_info: spill_info
953 954 955 956 957 958 959 960 961
        }
    }
}

#[derive(Clone, Debug, PartialEq, Eq)]
struct ASMLocation {
    line: usize,
    index: usize,
    len: usize,
962
    oplen: usize
963 964 965 966
}

impl ASMLocation {
    fn new(line: usize, index: usize, len: usize, oplen: usize) -> ASMLocation {
967
        ASMLocation {
968 969 970
            line: line,
            index: index,
            len: len,
971
            oplen: oplen
972 973 974 975 976 977 978 979 980 981 982
        }
    }
}

#[derive(Clone, Debug)]
/// [start_inst, end_inst)
struct ASMBlock {
    start_inst: usize,
    end_inst: usize,

    livein: Vec<MuID>,
983
    liveout: Vec<MuID>
984 985 986 987 988 989 990 991
}

impl ASMBlock {
    fn new() -> ASMBlock {
        ASMBlock {
            start_inst: usize::MAX,
            end_inst: usize::MAX,
            livein: vec![],
992
            liveout: vec![]
993 994 995 996 997
        }
    }
}

pub struct ASMCodeGen {
998
    cur: Option<Box<ASMCode>>
999 1000
}

1001
const REG_PLACEHOLDER_LEN: usize = 5;
1002 1003 1004 1005 1006 1007 1008 1009
lazy_static! {
    pub static ref REG_PLACEHOLDER : String = {
        let blank_spaces = [' ' as u8; REG_PLACEHOLDER_LEN];

        format!("{}", str::from_utf8(&blank_spaces).unwrap())
    };
}

1010
const FRAME_SIZE_PLACEHOLDER_LEN: usize = 10; // a frame is smaller than 1 << 10
1011 1012 1013 1014 1015 1016 1017 1018 1019
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())
    };
}

impl ASMCodeGen {
    pub fn new() -> ASMCodeGen {
1020
        ASMCodeGen { cur: None }
1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034
    }

    fn cur(&self) -> &ASMCode {
        self.cur.as_ref().unwrap()
    }

    fn cur_mut(&mut self) -> &mut ASMCode {
        self.cur.as_mut().unwrap()
    }

    fn line(&self) -> usize {
        self.cur().code.len()
    }

1035
    fn add_asm_symbolic(&mut self, code: String) {
1036
        trace_emit!("{}", demangle_text(code.clone()));
1037 1038 1039 1040 1041 1042 1043 1044
        self.cur_mut().code.push(ASMInst::symbolic(code));
    }

    fn add_asm_inst(
        &mut self,
        code: String,
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
1045
        is_using_mem_op: bool
1046
    ) {
1047 1048 1049 1050 1051 1052
        self.add_asm_inst_internal(
            code,
            defines,
            uses,
            is_using_mem_op,
            ASMBranchTarget::None,
1053
            None
1054
        )
1055 1056
    }

1057 1058 1059 1060 1061
    fn add_asm_inst_with_callee_saved(
        &mut self,
        code: String,
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
1062
        is_using_mem_op: bool
1063
    ) {
1064 1065 1066 1067 1068 1069
        self.add_asm_inst_internal(
            code,
            defines,
            uses,
            is_using_mem_op,
            ASMBranchTarget::None,
1070
            Some(SpillMemInfo::CalleeSaved)
1071
        )
1072 1073
    }

1074 1075 1076 1077 1078 1079
    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,
1080
        spill_info: SpillMemInfo
1081
    ) {
1082 1083 1084 1085 1086 1087
        self.add_asm_inst_internal(
            code,
            defines,
            uses,
            is_using_mem_op,
            ASMBranchTarget::None,
1088
            Some(spill_info)
1089
        )
1090 1091 1092 1093 1094 1095 1096 1097 1098
    }

    fn add_asm_inst_internal(
        &mut self,
        code: String,
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
        is_using_mem_op: bool,
        target: ASMBranchTarget,
1099
        spill_info: Option<SpillMemInfo>
1100
    ) {
1101
        trace!("asm: {}", demangle_text(code.clone()));
1102 1103
        trace!("     defines: {:?}", defines);
        trace!("     uses: {:?}", uses);
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1104
        trace!("     target: {:?}", target);
1105 1106 1107
        let mc = self.cur_mut();

        // put the instruction
1108 1109 1110 1111 1112 1113
        mc.code.push(ASMInst::inst(
            code,
            defines,
            uses,
            is_using_mem_op,
            target,
1114
            spill_info
1115
        ));
1116 1117 1118 1119 1120
    }

    fn prepare_reg(&self, op: &P<Value>, loc: usize) -> (String, MuID, ASMLocation) {
        if cfg!(debug_assertions) {
            match op.v {
1121
                Value_::SSAVar(_) => {}
1122
                _ => panic!("expecting register op")
1123 1124 1125 1126 1127
            }
        }

        let str = self.asm_reg_op(op);
        let len = str.len();
1128 1129 1130
        (
            str,
            op.extract_ssa_id().unwrap(),
1131
            ASMLocation::new(self.line(), loc, len, check_op_len(&op.ty))
1132
        )
1133 1134
    }

1135 1136 1137
    fn prepare_mem(
        &self,
        op: &P<Value>,
1138
        loc: usize
1139
    ) -> (String, LinkedHashMap<MuID, Vec<ASMLocation>>) {
1140 1141
        if cfg!(debug_assertions) {
            match op.v {
1142
                Value_::Memory(_) => {}
1143
                _ => panic!("expecting memory op")
1144 1145 1146
            }
        }

1147 1148 1149
        let mut ids: Vec<MuID> = vec![];
        let mut locs: Vec<ASMLocation> = vec![];
        let mut result_str: String = "".to_string();
1150

1151
        let mut loc_cursor: usize = loc;
1152 1153
        match op.v {
            // offset(base,index,scale)
1154 1155 1156 1157
            Value_::Memory(MemoryLocation::Address {
                ref base,
                ref offset,
                shift,
1158
                signed
1159
            }) => {
1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185
                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 offset
                if offset.is_some() {
                    result_str.push(',');
                    loc_cursor += 1;

                    let offset = offset.as_ref().unwrap();
                    match offset.v {
                        Value_::SSAVar(_) => {
                            // temp as offset
                            let (str, id, loc) = self.prepare_reg(offset, loc_cursor);

                            result_str.push_str(&str);
                            ids.push(id);
                            locs.push(loc);

                            result_str.push_str(",");
                            let n = offset.ty.get_int_length().unwrap();
1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200
                            let shift_type = if n == 64 {
                                if signed {
                                    "SXTX"
                                } else {
                                    "LSL"
                                }
                            } else if n == 32 {
                                if signed {
                                    "SXTW"
                                } else {
                                    "UXTW"
                                }
                            } else {
                                panic!("Unexpected size for offset register")
                            };
1201 1202 1203 1204 1205

                            result_str.push_str(&shift_type);
                            result_str.push_str(" #");
                            let shift_str = shift.to_string();
                            result_str.push_str(&shift_str);
1206
                        }
1207 1208 1209 1210 1211
                        Value_::Constant(Constant::Int(val)) => {
                            let str = (val as i32).to_string();

                            result_str.push('#');
                            result_str.push_str(&str);
1212
                        }
1213 1214 1215 1216
                        Value_::Constant(Constant::ExternSym(ref name)) => {
                            result_str.push('#');
                            result_str.push_str(name.as_str());
                        }
1217
                        _ => panic!("unexpected offset type: {:?}", offset)
1218 1219 1220 1221
                    }
                }

                // scale (for LSL type)
1222
                if shift != 0 {}
1223 1224

                result_str.push(']');
1225
            }
1226

1227 1228 1229
            Value_::Memory(MemoryLocation::Symbolic {
                ref label,
                is_global,
1230
                is_native
1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241
            }) => {
                let label = if is_native {
                    "/*C*/".to_string() + label.as_str()
                } else {
                    mangle_name(label.clone())
                };
                let label = if is_global {
                    format!(":got:{}", label.clone())
                } else {
                    label.clone()
                };
1242
                result_str.push_str(label.as_str());
1243
            }
1244

1245
            Value_::Memory(MemoryLocation::VirtualAddress { .. }) => {
1246 1247
                panic!("Can't directly use a virtual adress (try calling emit_mem first)");
            }
1248
            _ => panic!("expect mem location as value")
1249 1250
        }

1251
        let uses: LinkedHashMap<MuID, Vec<ASMLocation>> = {
1252
            let mut map: LinkedHashMap<MuID, Vec<ASMLocation>> = linked_hashmap!{};
1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273
            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)
    }

    fn asm_reg_op(&self, op: &P<Value>) -> String {
        let id = op.extract_ssa_id().unwrap();
        if id < MACHINE_ID_END {
            // machine reg
1274
            format!("{}", op.name())
1275 1276 1277 1278 1279 1280 1281 1282 1283 1284
        } else {
            // virtual register, use place holder
            REG_PLACEHOLDER.clone()
        }
    }

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

1285
    fn internal_simple(&mut self, inst: &str) {
1286
        let inst = inst.to_string();
1287
        trace_emit!("\t{}", inst);
1288 1289 1290

        let asm = inst;

1291
        self.add_asm_inst(asm, linked_hashmap!{}, linked_hashmap!{}, false)
1292 1293
    }

1294
    fn internal_simple_imm(&mut self, inst: &str, val: u64) {
1295
        let inst = inst.to_string();
1296
        trace_emit!("\t{} {}", inst, val);
1297 1298 1299

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

1300
        self.add_asm_inst(asm, linked_hashmap!{}, linked_hashmap!{}, false)
1301 1302
    }

1303
    fn internal_simple_str(&mut self, inst: &str, option: &str) {
1304 1305
        let inst = inst.to_string();
        let option = option.to_string();
1306
        trace_emit!("\t{} {}", inst, option);
1307 1308 1309

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

1310
        self.add_asm_inst(asm, linked_hashmap!{}, linked_hashmap!{}, false)
1311 1312
    }

1313
    // A system instruction
1314
    fn internal_system(&mut self, inst: &str, option: &str, src: &P<Value>) {
1315 1316
        let inst = inst.to_string();
        let option = option.to_string();
1317
        trace_emit!("\t{} {} {}", inst, option, src);
1318 1319 1320 1321 1322 1323 1324

        let (reg1, id1, loc1) = self.prepare_reg(src, inst.len() + 1 + option.len() + 1);

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

        self.add_asm_inst(
            asm,
1325
            linked_hashmap!{},
1326
            ignore_zero_register(id1, vec![loc1]),
1327
            false
1328 1329 1330
        )
    }

1331
    fn internal_branch_op(&mut self, inst: &str, src: &P<Value>, dest_name: MuName) {
1332
        trace_emit!("\t{} {}, {}", inst, src, dest_name);
1333 1334 1335

        let (reg1, id1, loc1) = self.prepare_reg(src, inst.len() + 1);
        // symbolic label, we dont need to patch it
1336
        let asm = format!("{} {},{}", inst, reg1, mangle_name(dest_name.clone()));
1337 1338 1339 1340 1341 1342
        self.add_asm_inst_internal(
            asm,
            linked_hashmap!{},
            linked_hashmap! { id1 => vec![loc1]},
            false,
            ASMBranchTarget::Conditional(dest_name),
1343
            None
1344
        );
1345 1346
    }

1347
    fn internal_branch_op_imm(&mut self, inst: &str, src1: &P<Value>, src2: u8, dest_name: MuName) {
1348
        trace_emit!("\t{} {},{},{}", inst, src1, src2, dest_name);
1349 1350 1351

        let (reg1, id1, loc1) = self.prepare_reg(src1, inst.len() + 1);
        // symbolic label, we dont need to patch it
1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364
        let asm = format!(
            "{} {},#{},{}",
            inst,
            reg1,
            src2,
            mangle_name(dest_name.clone())
        );
        self.add_asm_inst_internal(
            asm,
            linked_hashmap!{},
            linked_hashmap! { id1 => vec![loc1]},
            false,
            ASMBranchTarget::Conditional(dest_name),
1365
            None
1366
        );
1367 1368
    }

1369
    // Same as inetnral_binop except extends the second source register
1370 1371 1372 1373 1374 1375 1376
    fn internal_binop_ext(
        &mut self,
        inst: &str,
        dest: &P<Value>,
        src1: &P<Value>,
        src2: &P<Value>,
        signed: bool,
1377
        shift: u8
1378
    ) {
1379 1380 1381
        let inst = inst.to_string();
        let ext_s = if signed { "S" } else { "U" };
        let ext_p = match src2.ty.get_int_length() {
1382
            Some(8) => "B",
1383 1384 1385
            Some(16) => "H",
            Some(32) => "W",
            Some(64) => "X",
1386 1387 1388 1389 1390 1391
            _ => {
                panic!(
                    "op size: {} dose not support extension",
                    src2.ty.get_int_length().unwrap()
                )
            }
1392 1393 1394
        };
        let ext = ext_s.to_string() + "XT" + ext_p;

1395 1396 1397 1398 1399 1400 1401 1402 1403
        trace_emit!(
            "\t{} {}, {} {} {} -> {}",
            inst,
            src1,
            src2,
            ext,
            shift,
            dest
        );
1404 1405 1406 1407


        let (reg1, id1, loc1) = self.prepare_reg(dest, inst.len() + 1);
        let (reg2, id2, loc2) = self.prepare_reg(src1, inst.len() + 1 + reg1.len() + 1);
1408 1409
        let (reg3, id3, loc3) =
            self.prepare_reg(src2, inst.len() + 1 + reg1.len() + 1 + reg2.len() + 1);
1410

1411 1412 1413 1414 1415
        let asm = if shift == 0 {
            format!("{} {},{},{},{}", inst, reg1, reg2, reg3, ext)
        } else {
            format!("{} {},{},{},{} #{}", inst, reg1, reg2, reg3, ext, shift)
        };
1416 1417 1418 1419


        self.add_asm_inst(
            asm,
1420 1421
            ignore_zero_register(id1, vec![loc1]),
            create_hash_map(vec![(id2, loc2), (id3, loc3)]),
1422
            false
1423 1424 1425
        )
    }

1426 1427 1428 1429 1430 1431
    fn internal_binop_imm(
        &mut self,
        inst: &str,
        dest: &P<Value>,
        src1: &P<Value>,
        src2: u64,
1432
        shift: u8
1433
    ) {
1434
        let inst = inst.to_string();
1435
        trace_emit!("\t{} {}, {} LSL {} -> {}", inst, src1, src2, shift, dest);
1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447

        let (reg1, id1, loc1) = self.prepare_reg(dest, inst.len() + 1);
        let (reg2, id2, loc2) = self.prepare_reg(src1, inst.len() + 1 + reg1.len() + 1);

        let asm = if shift == 0 {
            format!("{} {},{},#{}", inst, reg1, reg2, src2)
        } else {
            format!("{} {},{},#{},LSL #{}", inst, reg1, reg2, src2, shift)
        };

        self.add_asm_inst(
            asm,
1448 1449
            ignore_zero_register(id1, vec![loc1]),
            ignore_zero_register(id2, vec![loc2]),
1450
            false
1451 1452 1453
        )
    }

1454
    // dest <= inst(src1, src2)
1455 1456 1457 1458 1459 1460
    fn internal_unop_shift(
        &mut self,
        inst: &str,
        dest: &P<Value>,
        src: &P<Value>,
        shift: &str,
1461
        amount: u8
1462
    ) {
1463
        let inst = inst.to_string();
1464
        trace_emit!("\t{} {}, {} {} -> {}", inst, src, shift, amount, dest);
1465 1466 1467 1468 1469 1470 1471 1472

        let (reg1, id1, loc1) = self.prepare_reg(dest, inst.len() + 1);
        let (reg2, id2, loc2) = self.prepare_reg(src, inst.len() + 1 + reg1.len() + 1);

        let asm = format!("{} {},{},{} #{}", inst, reg1, reg2, shift, amount);

        self.add_asm_inst(
            asm,
1473 1474
            ignore_zero_register(id1, vec![loc1]),
            ignore_zero_register(id2, vec![loc2]),
1475
            false
1476 1477 1478
        )
    }

1479
    // dest <= inst(src)
1480
    fn internal_unop(&mut self, inst: &str, dest: &P<Value>, src: &P<Value>) {
1481
        let inst = inst.to_string();
1482
        trace_emit!("\t{} {} -> {}", inst, src, dest);