mod.rs 15.5 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.

qinsoon's avatar
qinsoon committed
15 16 17
#![allow(dead_code)]
#![allow(non_upper_case_globals)]

18 19 20 21 22
pub mod inst_sel;

mod codegen;
pub use compiler::backend::x86_64::codegen::CodeGenerator;

qinsoon's avatar
qinsoon committed
23
pub mod asm_backend;
24
pub use compiler::backend::x86_64::asm_backend::ASMCodeGen;
25 26
pub use compiler::backend::x86_64::asm_backend::emit_code;
pub use compiler::backend::x86_64::asm_backend::emit_context;
qinsoon's avatar
qinsoon committed
27
pub use compiler::backend::x86_64::asm_backend::emit_context_with_reloc;
28 29
#[cfg(feature = "aot")]
pub use compiler::backend::x86_64::asm_backend::spill_rewrite;
30 31 32

use ast::ptr::P;
use ast::ir::*;
qinsoon's avatar
qinsoon committed
33
use ast::types::*;
34
use compiler::backend::RegGroup;
qinsoon's avatar
qinsoon committed
35

36
use utils::LinkedHashMap;
37 38
use std::collections::HashMap;

qinsoon's avatar
qinsoon committed
39
macro_rules! GPR_ALIAS {
40 41 42 43 44 45 46 47 48 49 50 51
    ($alias: ident: ($id64: expr, $r64: ident) -> $r32: ident, $r16: ident, $r8l: ident, $r8h: ident) => {
        lazy_static!{
            pub static ref $r64 : P<Value> = GPR!($id64,    stringify!($r64), UINT64_TYPE);
            pub static ref $r32 : P<Value> = GPR!($id64 +1, stringify!($r32), UINT32_TYPE);
            pub static ref $r16 : P<Value> = GPR!($id64 +2, stringify!($r16), UINT16_TYPE);
            pub static ref $r8l : P<Value> = GPR!($id64 +3, stringify!($r8l), UINT8_TYPE);
            pub static ref $r8h : P<Value> = GPR!($id64 +4, stringify!($r8h), UINT8_TYPE);

            pub static ref $alias : [P<Value>; 5] = [$r64.clone(), $r32.clone(), $r16.clone(), $r8l.clone(), $r8h.clone()];
        }
    };

qinsoon's avatar
qinsoon committed
52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
    ($alias: ident: ($id64: expr, $r64: ident) -> $r32: ident, $r16: ident, $r8: ident) => {
        lazy_static!{
            pub static ref $r64 : P<Value> = GPR!($id64,    stringify!($r64), UINT64_TYPE);
            pub static ref $r32 : P<Value> = GPR!($id64 +1, stringify!($r32), UINT32_TYPE);
            pub static ref $r16 : P<Value> = GPR!($id64 +2, stringify!($r16), UINT16_TYPE);
            pub static ref $r8  : P<Value> = GPR!($id64 +3, stringify!($r8) , UINT8_TYPE );

            pub static ref $alias : [P<Value>; 4] = [$r64.clone(), $r32.clone(), $r16.clone(), $r8.clone()];
        }
    };

    ($alias: ident: ($id64: expr, $r64: ident)) => {
        lazy_static!{
            pub static ref $r64 : P<Value> = GPR!($id64,    stringify!($r64), UINT64_TYPE);

            pub static ref $alias : [P<Value>; 4] = [$r64.clone(), $r64.clone(), $r64.clone(), $r64.clone()];
        }
    };
}

72
macro_rules! GPR {
qinsoon's avatar
qinsoon committed
73
    ($id:expr, $name: expr, $ty: ident) => {
qinsoon's avatar
qinsoon committed
74 75
        {
            P(Value {
qinsoon's avatar
qinsoon committed
76
                hdr: MuEntityHeader::named($id, $name.to_string()),
qinsoon's avatar
qinsoon committed
77
                ty: $ty.clone(),
qinsoon's avatar
qinsoon committed
78
                v: Value_::SSAVar($id)
qinsoon's avatar
qinsoon committed
79 80
            })
        }
qinsoon's avatar
qinsoon committed
81 82 83 84
    };
}

macro_rules! FPR {
qinsoon's avatar
qinsoon committed
85
    ($id:expr, $name: expr) => {
qinsoon's avatar
qinsoon committed
86 87
        {
            P(Value {
qinsoon's avatar
qinsoon committed
88
                hdr: MuEntityHeader::named($id, $name.to_string()),
qinsoon's avatar
qinsoon committed
89
                ty: DOUBLE_TYPE.clone(),
qinsoon's avatar
qinsoon committed
90
                v: Value_::SSAVar($id)
qinsoon's avatar
qinsoon committed
91 92
            })
        }
qinsoon's avatar
qinsoon committed
93 94 95
    };
}

96 97
GPR_ALIAS!(RAX_ALIAS: (0, RAX)  -> EAX, AX , AL, AH);
GPR_ALIAS!(RCX_ALIAS: (5, RCX)  -> ECX, CX , CL, CH);
98
GPR_ALIAS!(RDX_ALIAS: (10,RDX)  -> EDX, DX , DL, DH);
99 100 101 102 103 104 105 106 107 108 109 110 111 112
GPR_ALIAS!(RBX_ALIAS: (15,RBX)  -> EBX, BX , BL, BH);
GPR_ALIAS!(RSP_ALIAS: (20,RSP)  -> ESP, SP , SPL);
GPR_ALIAS!(RBP_ALIAS: (24,RBP)  -> EBP, BP , BPL);
GPR_ALIAS!(RSI_ALIAS: (28,RSI)  -> ESI, SI , SIL);
GPR_ALIAS!(RDI_ALIAS: (32,RDI)  -> EDI, DI , DIL);
GPR_ALIAS!(R8_ALIAS : (36,R8 )  -> R8D, R8W, R8B);
GPR_ALIAS!(R9_ALIAS : (40,R9 )  -> R9D, R9W, R9B);
GPR_ALIAS!(R10_ALIAS: (44,R10) -> R10D,R10W,R10B);
GPR_ALIAS!(R11_ALIAS: (48,R11) -> R11D,R11W,R11B);
GPR_ALIAS!(R12_ALIAS: (52,R12) -> R12D,R12W,R12B);
GPR_ALIAS!(R13_ALIAS: (56,R13) -> R13D,R13W,R13B);
GPR_ALIAS!(R14_ALIAS: (60,R14) -> R14D,R14W,R14B);
GPR_ALIAS!(R15_ALIAS: (64,R15) -> R15D,R15W,R15B);
GPR_ALIAS!(RIP_ALIAS: (68,RIP));
qinsoon's avatar
qinsoon committed
113

114
lazy_static! {
115 116
    pub static ref GPR_ALIAS_TABLE : LinkedHashMap<MuID, Vec<P<Value>>> = {
        let mut ret = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138

        ret.insert(RAX.id(), RAX_ALIAS.to_vec());
        ret.insert(RCX.id(), RCX_ALIAS.to_vec());
        ret.insert(RDX.id(), RDX_ALIAS.to_vec());
        ret.insert(RBX.id(), RBX_ALIAS.to_vec());
        ret.insert(RSP.id(), RSP_ALIAS.to_vec());
        ret.insert(RBP.id(), RBP_ALIAS.to_vec());
        ret.insert(RSI.id(), RSI_ALIAS.to_vec());
        ret.insert(RDI.id(), RDI_ALIAS.to_vec());
        ret.insert(R8.id() , R8_ALIAS.to_vec() );
        ret.insert(R9.id() , R9_ALIAS.to_vec() );
        ret.insert(R10.id(), R10_ALIAS.to_vec());
        ret.insert(R11.id(), R11_ALIAS.to_vec());
        ret.insert(R12.id(), R12_ALIAS.to_vec());
        ret.insert(R13.id(), R13_ALIAS.to_vec());
        ret.insert(R14.id(), R14_ALIAS.to_vec());
        ret.insert(R15.id(), R15_ALIAS.to_vec());
        ret.insert(RIP.id(), RIP_ALIAS.to_vec());

        ret
    };

139 140 141 142 143 144 145 146 147 148 149 150 151
    // e.g. given eax, return rax
    pub static ref GPR_ALIAS_LOOKUP : HashMap<MuID, P<Value>> = {
        let mut ret = HashMap::new();

        for vec in GPR_ALIAS_TABLE.values() {
            let colorable = vec[0].clone();

            for gpr in vec {
                ret.insert(gpr.id(), colorable.clone());
            }
        }

        ret
qinsoon's avatar
qinsoon committed
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
}

pub fn get_alias_for_length(id: MuID, length: usize) -> P<Value> {
    if id < FPR_ID_START {
        let vec = match GPR_ALIAS_TABLE.get(&id) {
            Some(vec) => vec,
            None => panic!("didnt find {} as GPR", id)
        };

        match length {
            64 => vec[0].clone(),
            32 => vec[1].clone(),
            16 => vec[2].clone(),
            8 => vec[3].clone(),
            1 => vec[3].clone(),
            _ => panic!("unexpected length {} for {}", length, vec[0])
        }
    } else {
        for r in ALL_FPRs.iter() {
            if r.id() == id {
                return r.clone();
            }
        }

        panic!("didnt find {} as FPR", id)
    }
}
qinsoon's avatar
qinsoon committed
180

181
pub fn is_aliased(id1: MuID, id2: MuID) -> bool {
qinsoon's avatar
qinsoon committed
182
    if get_color_for_precolored(id1) == get_color_for_precolored(id2) {
183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204
        macro_rules! is_match {
            ($a1: expr, $a2: expr; $b: expr) => {
                $a1 == $b.id() || $a2 == $b.id()
            }
        };

        if is_match!(id1, id2; AH) {
            return false;
        } else if is_match!(id1, id2; BH) {
            return false;
        } else if is_match!(id1, id2; CH) {
            return false;
        } else if is_match!(id1, id2; DH) {
            return false;
        } else {
            return true;
        }
    } else {
        return false;
    }
}

qinsoon's avatar
qinsoon committed
205 206 207
pub fn get_color_for_precolored(id: MuID) -> MuID {
    debug_assert!(id < MACHINE_ID_END);

208 209 210 211 212 213 214 215
    if id < FPR_ID_START {
        match GPR_ALIAS_LOOKUP.get(&id) {
            Some(val) => val.id(),
            None => panic!("cannot find GPR {}", id)
        }
    } else {
        // we do not have alias for FPRs
        id
qinsoon's avatar
qinsoon committed
216 217
    }
}
218

219 220 221 222 223 224 225 226 227 228 229 230
#[inline(always)]
pub fn check_op_len(op: &P<Value>) -> usize {
    match op.ty.get_int_length() {
        Some(64) => 64,
        Some(32) => 32,
        Some(16) => 16,
        Some(8)  => 8,
        Some(1)  => 8,
        _ => panic!("unimplemented int types: {}", op.ty)
    }
}

qinsoon's avatar
qinsoon committed
231
lazy_static! {
qinsoon's avatar
qinsoon committed
232 233 234 235
    pub static ref RETURN_GPRs : [P<Value>; 2] = [
        RAX.clone(),
        RDX.clone(),
    ];
236

qinsoon's avatar
qinsoon committed
237 238 239 240 241 242 243 244
    pub static ref ARGUMENT_GPRs : [P<Value>; 6] = [
        RDI.clone(),
        RSI.clone(),
        RDX.clone(),
        RCX.clone(),
        R8.clone(),
        R9.clone()
    ];
245

qinsoon's avatar
qinsoon committed
246 247 248 249 250 251 252 253
    pub static ref CALLEE_SAVED_GPRs : [P<Value>; 6] = [
        RBX.clone(),
        RBP.clone(),
        R12.clone(),
        R13.clone(),
        R14.clone(),
        R15.clone()
    ];
qinsoon's avatar
qinsoon committed
254 255 256 257 258 259 260 261 262 263 264 265

    pub static ref CALLER_SAVED_GPRs : [P<Value>; 9] = [
        RAX.clone(),
        RCX.clone(),
        RDX.clone(),
        RSI.clone(),
        RDI.clone(),
        R8.clone(),
        R9.clone(),
        R10.clone(),
        R11.clone()
    ];
266

267
    static ref ALL_GPRs : [P<Value>; 15] = [
268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284
        RAX.clone(),
        RCX.clone(),
        RDX.clone(),
        RBX.clone(),
        RSP.clone(),
//        RBP.clone(),
        RSI.clone(),
        RDI.clone(),
        R8.clone(),
        R9.clone(),
        R10.clone(),
        R11.clone(),
        R12.clone(),
        R13.clone(),
        R14.clone(),
        R15.clone()
    ];
qinsoon's avatar
qinsoon committed
285 286
}

287
pub const FPR_ID_START : usize = 100;
288

qinsoon's avatar
qinsoon committed
289
lazy_static!{
290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305
    pub static ref XMM0  : P<Value> = FPR!(FPR_ID_START,    "xmm0");
    pub static ref XMM1  : P<Value> = FPR!(FPR_ID_START + 1,"xmm1");
    pub static ref XMM2  : P<Value> = FPR!(FPR_ID_START + 2,"xmm2");
    pub static ref XMM3  : P<Value> = FPR!(FPR_ID_START + 3,"xmm3");
    pub static ref XMM4  : P<Value> = FPR!(FPR_ID_START + 4,"xmm4");
    pub static ref XMM5  : P<Value> = FPR!(FPR_ID_START + 5,"xmm5");
    pub static ref XMM6  : P<Value> = FPR!(FPR_ID_START + 6,"xmm6");
    pub static ref XMM7  : P<Value> = FPR!(FPR_ID_START + 7,"xmm7");
    pub static ref XMM8  : P<Value> = FPR!(FPR_ID_START + 8,"xmm8");
    pub static ref XMM9  : P<Value> = FPR!(FPR_ID_START + 9,"xmm9");
    pub static ref XMM10 : P<Value> = FPR!(FPR_ID_START + 10,"xmm10");
    pub static ref XMM11 : P<Value> = FPR!(FPR_ID_START + 11,"xmm11");
    pub static ref XMM12 : P<Value> = FPR!(FPR_ID_START + 12,"xmm12");
    pub static ref XMM13 : P<Value> = FPR!(FPR_ID_START + 13,"xmm13");
    pub static ref XMM14 : P<Value> = FPR!(FPR_ID_START + 14,"xmm14");
    pub static ref XMM15 : P<Value> = FPR!(FPR_ID_START + 15,"xmm15");
306

qinsoon's avatar
qinsoon committed
307 308 309 310
    pub static ref RETURN_FPRs : [P<Value>; 2] = [
        XMM0.clone(),
        XMM1.clone()
    ];
311

qinsoon's avatar
qinsoon committed
312 313 314
    pub static ref ARGUMENT_FPRs : [P<Value>; 8] = [
        XMM0.clone(),
        XMM1.clone(),
qinsoon's avatar
qinsoon committed
315 316 317 318 319 320 321
        XMM2.clone(),
        XMM3.clone(),
        XMM4.clone(),
        XMM5.clone(),
        XMM6.clone(),
        XMM7.clone()
    ];
322

qinsoon's avatar
qinsoon committed
323
    pub static ref CALLEE_SAVED_FPRs : [P<Value>; 0] = [];
qinsoon's avatar
qinsoon committed
324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342

    pub static ref CALLER_SAVED_FPRs : [P<Value>; 16] = [
        XMM0.clone(),
        XMM1.clone(),
        XMM2.clone(),
        XMM3.clone(),
        XMM4.clone(),
        XMM5.clone(),
        XMM6.clone(),
        XMM7.clone(),
        XMM8.clone(),
        XMM9.clone(),
        XMM10.clone(),
        XMM11.clone(),
        XMM12.clone(),
        XMM13.clone(),
        XMM14.clone(),
        XMM15.clone(),
    ];
343

344
    static ref ALL_FPRs : [P<Value>; 16] = [
345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361
        XMM0.clone(),
        XMM1.clone(),
        XMM2.clone(),
        XMM3.clone(),
        XMM4.clone(),
        XMM5.clone(),
        XMM6.clone(),
        XMM7.clone(),
        XMM8.clone(),
        XMM9.clone(),
        XMM10.clone(),
        XMM11.clone(),
        XMM12.clone(),
        XMM13.clone(),
        XMM14.clone(),
        XMM15.clone(),
    ];
362 363
}

qinsoon's avatar
qinsoon committed
364
lazy_static! {
365 366
    pub static ref ALL_MACHINE_REGs : LinkedHashMap<MuID, P<Value>> = {
        let mut map = LinkedHashMap::new();
367 368 369 370 371 372 373

        for vec in GPR_ALIAS_TABLE.values() {
            for reg in vec {
                map.insert(reg.id(), reg.clone());
            }
        }

374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392
        map.insert(XMM0.id(), XMM0.clone());
        map.insert(XMM1.id(), XMM1.clone());
        map.insert(XMM2.id(), XMM2.clone());
        map.insert(XMM3.id(), XMM3.clone());
        map.insert(XMM4.id(), XMM4.clone());
        map.insert(XMM5.id(), XMM5.clone());
        map.insert(XMM6.id(), XMM6.clone());
        map.insert(XMM7.id(), XMM7.clone());
        map.insert(XMM8.id(), XMM8.clone());
        map.insert(XMM9.id(), XMM9.clone());
        map.insert(XMM10.id(), XMM10.clone());
        map.insert(XMM11.id(), XMM11.clone());
        map.insert(XMM12.id(), XMM12.clone());
        map.insert(XMM13.id(), XMM13.clone());
        map.insert(XMM14.id(), XMM14.clone());
        map.insert(XMM15.id(), XMM15.clone());

        map
    };
393

394 395 396 397 398 399 400 401 402 403 404
    // put caller saved regs first (they imposes no overhead if there is no call instruction)
    pub static ref ALL_USABLE_MACHINE_REGs : Vec<P<Value>> = vec![
        RAX.clone(),
        RCX.clone(),
        RDX.clone(),
        RSI.clone(),
        RDI.clone(),
        R8.clone(),
        R9.clone(),
        R10.clone(),
        R11.clone(),
405

406 407 408 409 410
        RBX.clone(),
        R12.clone(),
        R13.clone(),
        R14.clone(),
        R15.clone(),
411

412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428
        XMM0.clone(),
        XMM1.clone(),
        XMM2.clone(),
        XMM3.clone(),
        XMM4.clone(),
        XMM5.clone(),
        XMM6.clone(),
        XMM7.clone(),
        XMM8.clone(),
        XMM9.clone(),
        XMM10.clone(),
        XMM11.clone(),
        XMM12.clone(),
        XMM13.clone(),
        XMM14.clone(),
        XMM15.clone()
    ];
qinsoon's avatar
qinsoon committed
429 430
}

431
pub fn init_machine_regs_for_func (func_context: &mut FunctionContext) {
432
    for reg in ALL_MACHINE_REGs.values() {
433
        let reg_id = reg.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
434
        let entry = SSAVarEntry::new(reg.clone());
435

436 437 438 439 440 441
        func_context.values.insert(reg_id, entry);
    }
}

pub fn number_of_regs_in_group(group: RegGroup) -> usize {
    match group {
442 443 444
        RegGroup::GPR   => ALL_GPRs.len(),
        RegGroup::GPREX => ALL_GPRs.len(),
        RegGroup::FPR   => ALL_FPRs.len()
qinsoon's avatar
qinsoon committed
445 446 447
    }
}

448 449 450 451
pub fn number_of_all_regs() -> usize {
    ALL_MACHINE_REGs.len()
}

452
pub fn all_regs() -> &'static LinkedHashMap<MuID, P<Value>> {
453 454 455
    &ALL_MACHINE_REGs
}

456 457 458 459
pub fn all_usable_regs() -> &'static Vec<P<Value>> {
    &ALL_USABLE_MACHINE_REGs
}

460
pub fn pick_group_for_reg(reg_id: MuID) -> RegGroup {
461
    let reg = all_regs().get(&reg_id).unwrap();
462
    RegGroup::get_from_value(reg)
463 464
}

465 466 467 468 469 470
pub fn is_callee_saved(reg_id: MuID) -> bool {
    for reg in CALLEE_SAVED_GPRs.iter() {
        if reg_id == reg.extract_ssa_id().unwrap() {
            return true;
        }
    }
471 472

    false
473 474
}

475
pub fn is_valid_x86_imm(op: &P<Value>) -> bool {
qinsoon's avatar
qinsoon committed
476
    use std::u32;
qinsoon's avatar
qinsoon committed
477
    match op.v {
qinsoon's avatar
qinsoon committed
478
        Value_::Constant(Constant::Int(val)) if val <= u32::MAX as u64 => {
qinsoon's avatar
qinsoon committed
479 480
            true
        },
481 482
        _ => false
    }
483 484 485 486 487 488 489 490 491
}

use ast::inst::*;
pub fn estimate_insts_for_ir(inst: &Instruction) -> usize {
    use ast::inst::Instruction_::*;

    match inst.v {
        // simple
        BinOp(_, _, _)  => 1,
qinsoon's avatar
qinsoon committed
492
        BinOpWithStatus(_, _, _, _) => 2,
493
        CmpOp(_, _, _)  => 1,
494
        ConvOp{..}      => 0,
495 496

        // control flow
497 498 499
        Branch1(_)     => 1,
        Branch2{..}    => 1,
        Select{..}     => 2,
500
        Watchpoint{..} => 1,
501 502
        WPBranch{..}   => 2,
        Switch{..}     => 3,
503 504 505

        // call
        ExprCall{..} | ExprCCall{..} | Call{..} | CCall{..} => 5,
506
        Return(_)   => 1,
507 508 509 510
        TailCall(_) => 1,

        // memory access
        Load{..} | Store{..} => 1,
511 512 513 514 515
        CmpXchg{..}          => 1,
        AtomicRMW{..}        => 1,
        AllocA(_)            => 1,
        AllocAHybrid(_, _)   => 1,
        Fence(_)             => 1,
516 517 518 519 520 521 522

        // memory addressing
        GetIRef(_) | GetFieldIRef{..} | GetElementIRef{..} | ShiftIRef{..} | GetVarPartIRef{..} => 0,

        // runtime
        New(_) | NewHybrid(_, _) => 10,
        NewStack(_) | NewThread(_, _) | NewThreadExn(_, _) | NewFrameCursor(_) => 10,
523 524
        ThreadExit    => 10,
        Throw(_)      => 10,
525 526
        SwapStack{..} => 10,
        CommonInst_GetThreadLocal | CommonInst_SetThreadLocal(_) => 10,
527
        CommonInst_Pin(_) | CommonInst_Unpin(_) => 10,
528 529 530

        // others
        Move(_) => 0,
531
        PrintHex(_) => 10,
532 533
        ExnInstruction{ref inner, ..} => estimate_insts_for_ir(&inner)
    }
534
}