liveness.rs 25.2 KB
Newer Older
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1
// Copyright 2017 The Australian National University
qinsoon's avatar
qinsoon committed
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
qinsoon's avatar
qinsoon committed
6
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
7
//     http://www.apache.org/licenses/LICENSE-2.0
qinsoon's avatar
qinsoon committed
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
extern crate hprof;

qinsoon's avatar
qinsoon committed
17
use compiler::machine_code::CompiledFunction;
18
use ast::ir::*;
qinsoon's avatar
qinsoon committed
19
use compiler::backend;
20
use utils::LinkedHashSet;
21
use utils::LinkedHashMap;
qinsoon's avatar
qinsoon committed
22
use std::fmt;
qinsoon's avatar
qinsoon committed
23

qinsoon's avatar
qinsoon committed
24
/// GraphNode represents a node in the interference graph.
qinsoon's avatar
qinsoon committed
25
#[derive(Clone, Copy, PartialEq)]
26
pub struct Node {
qinsoon's avatar
qinsoon committed
27
    /// temp ID (could be register)
28
    temp: MuID,
qinsoon's avatar
qinsoon committed
29
    /// assigned color
qinsoon's avatar
qinsoon committed
30
    color: Option<MuID>,
qinsoon's avatar
qinsoon committed
31
    /// temp register group (which machine register class we should assign)
32
    group: backend::RegGroup,
qinsoon's avatar
qinsoon committed
33
    /// cost to spill this temp
34
    spill_cost: f32
qinsoon's avatar
qinsoon committed
35
}
36

qinsoon's avatar
qinsoon committed
37 38 39 40 41 42 43 44 45 46 47 48 49
impl fmt::Debug for Node {
    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
        write!(
            f,
            "Node({}): color={:?}, group={:?}, spill_cost={}",
            self.temp,
            self.color,
            self.group,
            self.spill_cost
        )
    }
}

qinsoon's avatar
qinsoon committed
50 51
/// Move represents a move between two nodes (referred by index)
/// We need to know the moves so that we can coalesce.
qinsoon's avatar
qinsoon committed
52
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
qinsoon's avatar
qinsoon committed
53
pub struct Move {
54 55 56 57
    pub from: MuID,
    pub to: MuID
}

qinsoon's avatar
qinsoon committed
58 59 60 61 62 63
impl fmt::Debug for Move {
    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
        write!(f, "Move ({} -> {})", self.from, self.to)
    }
}

64 65 66 67 68 69 70
#[inline(always)]
fn is_precolored(reg: MuID) -> bool {
    if reg < MACHINE_ID_END {
        true
    } else {
        false
    }
qinsoon's avatar
qinsoon committed
71
}
72

73 74
#[inline(always)]
fn is_usable(reg: MuID) -> bool {
qinsoon's avatar
qinsoon committed
75 76 77 78
    if backend::all_usable_regs()
        .iter()
        .any(|x| x.id() == backend::get_color_for_precolored(reg))
    {
79 80 81 82 83 84
        true
    } else {
        false
    }
}

qinsoon's avatar
qinsoon committed
85 86 87 88
/// InterferenceGraph represents the interference graph, including
/// * the graph
/// * all the nodes and its NodeIndex (a node is referred to by NodeIndex)
/// * all the moves
89
pub struct InterferenceGraph {
90 91 92 93 94
    nodes: LinkedHashMap<MuID, Node>,

    adj_set: LinkedHashSet<(MuID, MuID)>,
    adj_list: LinkedHashMap<MuID, LinkedHashSet<MuID>>,
    degree: LinkedHashMap<MuID, usize>,
95
    moves: LinkedHashSet<Move>
96 97 98
}

impl InterferenceGraph {
qinsoon's avatar
qinsoon committed
99
    /// creates a new graph
100
    fn new() -> InterferenceGraph {
qinsoon's avatar
qinsoon committed
101
        InterferenceGraph {
102 103 104
            adj_set: LinkedHashSet::new(),
            adj_list: LinkedHashMap::new(),
            degree: LinkedHashMap::new(),
105
            nodes: LinkedHashMap::new(),
106
            moves: LinkedHashSet::new()
qinsoon's avatar
qinsoon committed
107 108
        }
    }
qinsoon's avatar
qinsoon committed
109 110 111

    /// creates a new node for a temp (if we already created a temp for the temp, returns the node)
    /// This function will increase spill cost for the node by 1 each tiem it is called for the temp
112
    fn new_node(&mut self, reg_id: MuID, context: &FunctionContext) -> MuID {
qinsoon's avatar
qinsoon committed
113
        let entry = context.get_value(reg_id).unwrap();
qinsoon's avatar
qinsoon committed
114 115

        // if it is the first time, create the node
qinsoon's avatar
qinsoon committed
116
        if !self.nodes.contains_key(&reg_id) {
117
            let node = Node {
118
                temp: reg_id,
119
                color: None,
120
                group: backend::RegGroup::get_from_ty(entry.ty()),
121
                spill_cost: 0.0f32
qinsoon's avatar
qinsoon committed
122
            };
123

124 125 126
            self.nodes.insert(reg_id, node);
            self.adj_list.insert(reg_id, LinkedHashSet::new());
            self.degree.insert(reg_id, 0);
127
        }
qinsoon's avatar
qinsoon committed
128 129

        // get node
130
        let node_mut = self.nodes.get_mut(&reg_id).unwrap();
131
        // increase node spill cost
132
        node_mut.spill_cost += 1.0f32;
qinsoon's avatar
qinsoon committed
133

134
        reg_id
qinsoon's avatar
qinsoon committed
135
    }
qinsoon's avatar
qinsoon committed
136 137

    /// returns all the nodes in the graph
138 139
    pub fn nodes(&self) -> Vec<MuID> {
        self.nodes.keys().map(|x| *x).collect()
qinsoon's avatar
qinsoon committed
140
    }
qinsoon's avatar
qinsoon committed
141 142

    /// returns all the moves in the graph
143
    pub fn moves(&self) -> &LinkedHashSet<Move> {
qinsoon's avatar
qinsoon committed
144 145
        &self.moves
    }
qinsoon's avatar
qinsoon committed
146 147

    /// adds a move edge between two nodes
148
    fn add_move(&mut self, src: MuID, dst: MuID) {
qinsoon's avatar
qinsoon committed
149
        let src = {
150
            if is_precolored(src) {
qinsoon's avatar
qinsoon committed
151
                // get the color for the machine register, e.g. rax for eax/ax/al/ah
152
                backend::get_color_for_precolored(src)
qinsoon's avatar
qinsoon committed
153 154 155 156 157 158
            } else {
                src
            }
        };

        let dst = {
159 160
            if is_precolored(dst) {
                backend::get_color_for_precolored(dst)
qinsoon's avatar
qinsoon committed
161 162 163 164 165
            } else {
                dst
            }
        };

qinsoon's avatar
qinsoon committed
166
        self.moves.insert(Move { from: src, to: dst });
167
    }
qinsoon's avatar
qinsoon committed
168 169

    /// adds an interference edge between two nodes
170
    pub fn add_edge(&mut self, u: MuID, v: MuID) {
qinsoon's avatar
qinsoon committed
171
        // if one of the node is machine register, we add
qinsoon's avatar
qinsoon committed
172
        // interference edge to its alias
qinsoon's avatar
qinsoon committed
173
        // e.g. if we have %a - %edi interfered,
qinsoon's avatar
qinsoon committed
174
        // we will add %a - %rdi interference
qinsoon's avatar
qinsoon committed
175

176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195
        let u = if is_precolored(u) {
            if is_usable(u) {
                backend::get_color_for_precolored(u)
            } else {
                // if it is not usable, we do not need to add an interference edge
                return;
            }
        } else {
            u
        };
        let v = if is_precolored(v) {
            if is_usable(v) {
                backend::get_color_for_precolored(v)
            } else {
                return;
            }
        } else {
            v
        };

196
        if !self.adj_set.contains(&(u, v)) && u != v {
qinsoon's avatar
qinsoon committed
197 198
            trace!("add edge ({}, {})", u, v);

199 200
            self.adj_set.insert((u, v));
            self.adj_set.insert((v, u));
qinsoon's avatar
qinsoon committed
201

202 203
            if !is_precolored(u) {
                self.adj_list.get_mut(&u).unwrap().insert(v);
qinsoon's avatar
qinsoon committed
204 205 206
                let degree = self.get_degree_of(u);
                self.set_degree_of(u, degree + 1);
                trace!("increase degree of {} to {}", u, degree + 1);
207 208 209
            }
            if !is_precolored(v) {
                self.adj_list.get_mut(&v).unwrap().insert(u);
qinsoon's avatar
qinsoon committed
210 211 212
                let degree = self.get_degree_of(v);
                self.set_degree_of(v, degree + 1);
                trace!("increase degree of {} to {}", v, degree + 1);
213
            }
qinsoon's avatar
qinsoon committed
214
        }
qinsoon's avatar
qinsoon committed
215 216
    }

qinsoon's avatar
qinsoon committed
217
    /// set color for a node
218 219
    pub fn color_node(&mut self, reg: MuID, color: MuID) {
        self.nodes.get_mut(&reg).unwrap().color = Some(color);
qinsoon's avatar
qinsoon committed
220
    }
qinsoon's avatar
qinsoon committed
221 222

    /// is a node colored yet?
223 224
    pub fn is_colored(&self, reg: MuID) -> bool {
        self.nodes.get(&reg).unwrap().color.is_some()
qinsoon's avatar
qinsoon committed
225
    }
qinsoon's avatar
qinsoon committed
226 227

    /// gets the color of a node
228 229
    pub fn get_color_of(&self, reg: MuID) -> Option<MuID> {
        self.nodes.get(&reg).unwrap().color
230
    }
qinsoon's avatar
qinsoon committed
231 232

    /// gets the reg group of a node
233 234
    pub fn get_group_of(&self, reg: MuID) -> backend::RegGroup {
        self.nodes.get(&reg).unwrap().group
qinsoon's avatar
qinsoon committed
235
    }
qinsoon's avatar
qinsoon committed
236 237

    /// gets the temporary of a node
238 239
    pub fn get_temp_of(&self, reg: MuID) -> MuID {
        self.nodes.get(&reg).unwrap().temp
240
    }
qinsoon's avatar
qinsoon committed
241 242

    /// gets the spill cost of a node
243 244
    pub fn get_spill_cost(&self, reg: MuID) -> f32 {
        self.nodes.get(&reg).unwrap().spill_cost
245
    }
qinsoon's avatar
qinsoon committed
246 247

    /// are two nodes the same node?
248 249
    fn is_same_node(&self, reg1: MuID, reg2: MuID) -> bool {
        reg1 == reg2
qinsoon's avatar
qinsoon committed
250
    }
251

qinsoon's avatar
qinsoon committed
252
    /// are two nodes from the same reg group?
253 254
    fn is_same_group(&self, reg1: MuID, reg2: MuID) -> bool {
        self.get_group_of(reg1) == self.get_group_of(reg2)
255
    }
qinsoon's avatar
qinsoon committed
256

257 258 259
    /// gets edges from a node
    pub fn get_adj_list(&self, reg: MuID) -> &LinkedHashSet<MuID> {
        self.adj_list.get(&reg).unwrap()
qinsoon's avatar
qinsoon committed
260
    }
qinsoon's avatar
qinsoon committed
261

262 263
    pub fn is_in_adj_set(&self, u: MuID, v: MuID) -> bool {
        self.adj_set.contains(&(u, v))
264
    }
qinsoon's avatar
qinsoon committed
265 266

    /// gets degree of a node (number of edges from the node)
267
    pub fn get_degree_of(&self, reg: MuID) -> usize {
qinsoon's avatar
qinsoon committed
268 269
        let ret = *self.degree.get(&reg).unwrap();
        ret
270 271 272
    }

    pub fn set_degree_of(&mut self, reg: MuID, degree: usize) {
qinsoon's avatar
qinsoon committed
273 274
        debug!("DEGREE({}) SET TO {}", reg, degree);
        self.degree.insert(reg, degree);
qinsoon's avatar
qinsoon committed
275
    }
qinsoon's avatar
qinsoon committed
276 277

    /// prints current graph for debugging (via trace log)
qinsoon's avatar
qinsoon committed
278
    #[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
279
    pub fn print(&self, context: &FunctionContext) {
280 281
        trace!("");
        trace!("Interference Graph");
282

283
        trace!("nodes: ");
qinsoon's avatar
qinsoon committed
284 285
        for node in self.nodes.values() {
            trace!("{:?}", node);
286 287 288 289
        }

        trace!("edges: ");
        for id in self.nodes.keys() {
qinsoon's avatar
qinsoon committed
290 291 292 293 294 295 296 297 298 299 300 301 302
            let mut s = String::new();
            s.push_str(&format!(
                "edges for {} ({}): ",
                id,
                self.degree.get(id).unwrap()
            ));
            let mut adj = self.get_adj_list(*id).iter();
            if let Some(first) = adj.next() {
                s.push_str(&format!("{:?}", first));
                while let Some(i) = adj.next() {
                    s.push(' ');
                    s.push_str(&format!("{:?}", i));
                }
303
            }
qinsoon's avatar
qinsoon committed
304
            trace!("{}", s);
305
        }
306
    }
qinsoon's avatar
qinsoon committed
307 308
}

qinsoon's avatar
qinsoon committed
309 310 311 312
/// prints trace during building liveness for debugging?
const TRACE_LIVENESS: bool = false;

/// builds interference graph based on chaitin briggs algorithms
qinsoon's avatar
qinsoon committed
313 314 315 316
/// reference: Tailoring Graph-coloring Register Allocation For Runtime Compilation
/// - CGO'06, Figure 4
pub fn build_interference_graph_chaitin_briggs(
    cf: &mut CompiledFunction,
317
    func: &MuFunctionVersion
qinsoon's avatar
qinsoon committed
318
) -> InterferenceGraph {
qinsoon's avatar
qinsoon committed
319 320 321 322 323 324 325 326
    let _p = hprof::enter("regalloc: build global liveness");
    build_global_liveness(cf, func);
    drop(_p);

    let _p = hprof::enter("regalloc: build interference graph");

    info!("---start building interference graph---");
    let mut ig = InterferenceGraph::new();
327

qinsoon's avatar
qinsoon committed
328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350
    // precolor machine register nodes
    for reg in backend::all_regs().values() {
        let reg_id = reg.extract_ssa_id().unwrap();
        let node = ig.new_node(reg_id, &func.context);
        let precolor = backend::get_color_for_precolored(reg_id);

        ig.color_node(node, precolor);
    }

    // initialize and creates nodes for all the involved temps/regs
    for i in 0..cf.mc().number_of_insts() {
        for reg_id in cf.mc().get_inst_reg_defines(i) {
            ig.new_node(reg_id, &func.context);
        }

        for reg_id in cf.mc().get_inst_reg_uses(i) {
            ig.new_node(reg_id, &func.context);
        }
    }

    // for each basic block, insert interference edge while reversely traversing instructions
    for block in cf.mc().get_all_blocks() {
        // Current_Live(B) = LiveOut(B)
qinsoon's avatar
qinsoon committed
351 352 353
        let mut current_live =
            LinkedHashSet::from_vec(match cf.mc().get_ir_block_liveout(&block) {
                Some(liveout) => liveout.to_vec(),
354
                None => panic!("cannot find liveout for block {}", block)
qinsoon's avatar
qinsoon committed
355
            });
qinsoon's avatar
qinsoon committed
356 357 358 359 360 361 362 363 364 365 366 367
        if TRACE_LIVENESS {
            trace!("Block{}: live out", block);
            for ele in current_live.iter() {
                trace!("{}", func.context.get_temp_display(*ele));
            }
        }

        let range = cf.mc().get_block_range(&block);
        if range.is_none() {
            warn!("Block{}: has no range (no instructions?)", block);
            continue;
        }
qinsoon's avatar
qinsoon committed
368 369 370 371 372 373
        trace_if!(
            TRACE_LIVENESS,
            "Block{}: range = {:?}",
            block,
            range.as_ref().unwrap()
        );
qinsoon's avatar
qinsoon committed
374 375 376

        // for every inst I in reverse order
        for i in range.unwrap().rev() {
377
            if TRACE_LIVENESS {
qinsoon's avatar
qinsoon committed
378 379 380 381 382 383 384 385
                trace!("Block{}: Inst{}", block, i);
                cf.mc().trace_inst(i);
                trace!("current live: ");
                for ele in current_live.iter() {
                    trace!("{}", func.context.get_temp_display(*ele));
                }
            }

qinsoon's avatar
qinsoon committed
386
            let src: Option<MuID> = {
qinsoon's avatar
qinsoon committed
387 388 389 390 391 392 393 394 395 396 397
                if cf.mc().is_move(i) {
                    let src = cf.mc().get_inst_reg_uses(i);
                    let dst = cf.mc().get_inst_reg_defines(i);

                    // src:  reg/imm/mem
                    // dest: reg/mem
                    // we dont care if src/dest is mem
                    if cf.mc().is_using_mem_op(i) {
                        None
                    } else {
                        if src.len() == 1 {
398 399
                            let src = src[0];
                            let dst = dst[0];
qinsoon's avatar
qinsoon committed
400 401 402
                            trace_if!(
                                TRACE_LIVENESS,
                                "add move between {} and {}",
403 404
                                func.context.get_temp_display(src),
                                func.context.get_temp_display(dst)
qinsoon's avatar
qinsoon committed
405
                            );
406
                            ig.add_move(src, dst);
qinsoon's avatar
qinsoon committed
407

408
                            Some(src)
qinsoon's avatar
qinsoon committed
409 410 411 412 413 414 415 416
                        } else {
                            None
                        }
                    }
                } else {
                    None
                }
            };
417
            trace_if!(TRACE_LIVENESS, "Block{}: Inst{}: src={:?}", block, i, src);
qinsoon's avatar
qinsoon committed
418

419
            let defines = cf.mc().get_inst_reg_defines(i);
420 421 422 423 424 425
            for d in defines.iter() {
                current_live.insert(*d);
            }

            // for every definition D in I
            for d in defines {
qinsoon's avatar
qinsoon committed
426 427 428 429 430 431 432
                trace_if!(
                    TRACE_LIVENESS,
                    "Block{}: Inst{}: for definition {}",
                    block,
                    i,
                    func.context.get_temp_display(d)
                );
qinsoon's avatar
qinsoon committed
433 434 435
                // add an interference from D to every element E in Current_Live - {D}
                // creating nodes if necessary
                for e in current_live.iter() {
qinsoon's avatar
qinsoon committed
436 437 438 439 440 441 442
                    trace_if!(
                        TRACE_LIVENESS,
                        "Block{}: Inst{}: for each live {}",
                        block,
                        i,
                        func.context.get_temp_display(*e)
                    );
qinsoon's avatar
qinsoon committed
443
                    if src.is_none() || (src.is_some() && *e != src.unwrap()) {
444 445
                        let from = d;
                        let to = *e;
qinsoon's avatar
qinsoon committed
446

447
                        if !ig.is_same_node(from, to) && ig.is_same_group(from, to) {
qinsoon's avatar
qinsoon committed
448
                            if !ig.is_colored(from) {
qinsoon's avatar
qinsoon committed
449 450 451 452 453
                                trace_if!(
                                    TRACE_LIVENESS,
                                    "Block{}: Inst{}: add interference between {} and {}",
                                    block,
                                    i,
454
                                    func.context.get_temp_display(d),
qinsoon's avatar
qinsoon committed
455 456
                                    func.context.get_temp_display(*e)
                                );
457
                                ig.add_edge(from, to);
qinsoon's avatar
qinsoon committed
458 459
                            }
                            if !ig.is_colored(to) {
qinsoon's avatar
qinsoon committed
460 461 462 463 464
                                trace_if!(
                                    TRACE_LIVENESS,
                                    "Block{}: Inst{}: add interference between {} and {}",
                                    block,
                                    i,
465
                                    func.context.get_temp_display(*e),
qinsoon's avatar
qinsoon committed
466 467
                                    func.context.get_temp_display(d)
                                );
468
                                ig.add_edge(to, from);
qinsoon's avatar
qinsoon committed
469 470 471 472 473 474 475 476
                            }
                        }
                    }
                }
            }

            // for every definition D in I
            for d in cf.mc().get_inst_reg_defines(i) {
qinsoon's avatar
qinsoon committed
477 478 479 480 481 482 483
                trace_if!(
                    TRACE_LIVENESS,
                    "Block{}: Inst{}: remove define {} from current_live",
                    block,
                    i,
                    func.context.get_temp_display(d)
                );
qinsoon's avatar
qinsoon committed
484 485 486 487 488 489
                // remove D from Current_Live
                current_live.remove(&d);
            }

            // for every use U in I
            for u in cf.mc().get_inst_reg_uses(i) {
qinsoon's avatar
qinsoon committed
490 491 492 493 494 495 496
                trace_if!(
                    TRACE_LIVENESS,
                    "Block{}: Inst{}: add use {} to current_live",
                    block,
                    i,
                    func.context.get_temp_display(u)
                );
qinsoon's avatar
qinsoon committed
497 498 499 500
                // add U to Current_live
                current_live.insert(u);
            }

501 502
            if TRACE_LIVENESS {
                trace!("Block{}: Inst{}: done. current_live:", block, i);
qinsoon's avatar
qinsoon committed
503 504 505 506 507 508 509 510 511 512 513 514 515 516
                for ele in current_live.iter() {
                    trace!("{}", func.context.get_temp_display(*ele));
                }
            }
        }
    }

    drop(_p);
    info!("---finish building interference graph---");
    ig
}

/// builds global liveness for a compiled function
fn build_global_liveness(cf: &mut CompiledFunction, func: &MuFunctionVersion) {
qinsoon's avatar
[wip]  
qinsoon committed
517
    info!("---start building live set---");
518

qinsoon's avatar
qinsoon committed
519 520 521
    // build control flow graphs, treat a whole block as one node in the graph
    let cfg = build_cfg_nodes(cf);
    // do liveness analysis
522 523 524 525 526
    global_liveness_analysis(cfg, cf, func);

    info!("---finish building live set---");
}

qinsoon's avatar
qinsoon committed
527
/// CFGBlockNode represents a basic block as a whole for global liveness analysis
528 529
#[derive(Clone, Debug)]
struct CFGBlockNode {
530
    block: MuName,
531 532
    pred: Vec<String>,
    succ: Vec<String>,
qinsoon's avatar
qinsoon committed
533
    uses: Vec<MuID>,
534
    defs: Vec<MuID>
535 536
}

qinsoon's avatar
qinsoon committed
537 538 539 540 541 542
/// builds a LinkedHashMap from basic block names to CFGBlockNode
/// We need to collect for each basic block:
/// * predecessors
/// * successors
/// * uses
/// * defs
543
fn build_cfg_nodes(cf: &mut CompiledFunction) -> LinkedHashMap<MuName, CFGBlockNode> {
544 545
    info!("---local liveness analysis---");
    let mc = cf.mc();
546
    let mut ret = LinkedHashMap::new();
547 548 549
    let all_blocks = mc.get_all_blocks();

    // create maps (start_inst -> name) and (end_inst -> name)
qinsoon's avatar
qinsoon committed
550 551
    // we will use it to find basic blocks when given a inst index
    let (start_inst_map, end_inst_map) = {
qinsoon's avatar
qinsoon committed
552 553
        let mut start_inst_map: LinkedHashMap<usize, &str> = LinkedHashMap::new();
        let mut end_inst_map: LinkedHashMap<usize, &str> = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
554 555 556
        for block in all_blocks.iter() {
            let range = match mc.get_block_range(block) {
                Some(range) => range,
557
                None => panic!("cannot find range for block {}", block)
qinsoon's avatar
qinsoon committed
558
            };
559

qinsoon's avatar
qinsoon committed
560 561 562 563 564
            // start inst
            let first_inst = range.start;
            // last inst (we need to skip symbols)
            let last_inst = match mc.get_last_inst(range.end) {
                Some(last) => last,
qinsoon's avatar
qinsoon committed
565 566 567 568 569 570 571
                None => {
                    panic!(
                        "cannot find last instruction in block {}, \
                         this block contains no instruction?",
                        block
                    )
                }
qinsoon's avatar
qinsoon committed
572
            };
qinsoon's avatar
qinsoon committed
573 574 575 576 577 578 579
            trace_if!(
                TRACE_LIVENESS,
                "Block {}: start_inst={}, end_inst(inclusive)={}",
                block,
                first_inst,
                last_inst
            );
580

qinsoon's avatar
qinsoon committed
581 582 583 584 585 586
            start_inst_map.insert(first_inst, block);
            end_inst_map.insert(last_inst, block);
        }

        (start_inst_map, end_inst_map)
    };
587

qinsoon's avatar
qinsoon committed
588
    // collect info for each basic block
589
    for block in mc.get_all_blocks().iter() {
590
        trace_if!(TRACE_LIVENESS, "---block {}---", block);
591 592
        let range = mc.get_block_range(block).unwrap();
        let start_inst = range.start;
qinsoon's avatar
qinsoon committed
593
        let end = range.end;
594

qinsoon's avatar
qinsoon committed
595 596 597 598 599 600 601
        // livein set of this block is what temps this block uses from other blocks
        // defs is what temps this block defines in the block
        let (livein, defs) = {
            // we gradually build livein
            let mut livein = vec![];
            // we need to know all temporaries defined in the block
            // if a temporary is not defined in this block, it is a livein for this block
qinsoon's avatar
qinsoon committed
602
            let mut all_defined: LinkedHashSet<MuID> = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
603 604 605 606 607 608 609 610 611 612

            for i in start_inst..end {
                let reg_uses = mc.get_inst_reg_uses(i);

                // if a reg is used but not defined before, it is a live-in
                for reg in reg_uses {
                    if !all_defined.contains(&reg) {
                        livein.push(reg);
                    }
                }
613

qinsoon's avatar
qinsoon committed
614 615 616
                let reg_defs = mc.get_inst_reg_defines(i);
                for reg in reg_defs {
                    all_defined.insert(reg);
617 618 619
                }
            }

qinsoon's avatar
qinsoon committed
620
            let defs: Vec<MuID> = all_defined.iter().map(|x| *x).collect();
621

qinsoon's avatar
qinsoon committed
622 623
            (livein, defs)
        };
624

qinsoon's avatar
qinsoon committed
625
        let preds: Vec<String> = {
626 627
            let mut ret = vec![];

qinsoon's avatar
qinsoon committed
628
            // predecessors of the first instruction is the predecessors of this block
629 630 631 632 633 634 635 636 637 638
            for pred in mc.get_preds(start_inst).into_iter() {
                match end_inst_map.get(pred) {
                    Some(str) => ret.push(String::from(*str)),
                    None => {}
                }
            }

            ret
        };

qinsoon's avatar
qinsoon committed
639
        let succs: Vec<String> = {
640 641
            let mut ret = vec![];

qinsoon's avatar
qinsoon committed
642
            // successors of the last instruction is the successors of this block
643
            for succ in mc.get_succs(mc.get_last_inst(end).unwrap()).into_iter() {
644 645 646 647 648 649 650 651 652 653 654 655 656 657
                match start_inst_map.get(succ) {
                    Some(str) => ret.push(String::from(*str)),
                    None => {}
                }
            }

            ret
        };

        let node = CFGBlockNode {
            block: block.clone(),
            pred: preds,
            succ: succs,
            uses: livein,
658
            defs: defs
659 660
        };

661
        trace_if!(TRACE_LIVENESS, "as CFGNode {:?}", node);
662 663 664 665 666 667
        ret.insert(block.clone(), node);
    }

    ret
}

qinsoon's avatar
qinsoon committed
668
/// global analysis, the iterative algorithm to compute livenss until livein/out reaches a fix point
qinsoon's avatar
qinsoon committed
669
fn global_liveness_analysis(
670
    blocks: LinkedHashMap<MuName, CFGBlockNode>,
qinsoon's avatar
qinsoon committed
671
    cf: &mut CompiledFunction,
672
    func: &MuFunctionVersion
qinsoon's avatar
qinsoon committed
673
) {
674 675
    info!("---global liveness analysis---");
    info!("{} blocks", blocks.len());
676 677

    // init live in and live out
678
    let mut livein: LinkedHashMap<MuName, LinkedHashSet<MuID>> = {
679
        let mut ret = LinkedHashMap::new();
680 681 682 683 684
        for name in blocks.keys() {
            ret.insert(name.clone(), LinkedHashSet::new());
        }
        ret
    };
685
    let mut liveout: LinkedHashMap<MuName, LinkedHashSet<MuID>> = {
686
        let mut ret = LinkedHashMap::new();
687 688 689 690 691 692
        for name in blocks.keys() {
            ret.insert(name.clone(), LinkedHashSet::new());
        }
        ret
    };

qinsoon's avatar
qinsoon committed
693
    // is the result changed in this iteration?
694
    let mut is_changed = true;
qinsoon's avatar
qinsoon committed
695
    // record iteration count
696 697 698
    let mut i = 0;

    while is_changed {
699
        trace_if!(TRACE_LIVENESS, "---iteration {}---", i);
700 701 702 703 704 705 706 707
        i += 1;

        // reset
        is_changed = false;

        for node in blocks.keys() {
            let cfg_node = blocks.get(node).unwrap();

qinsoon's avatar
qinsoon committed
708
            // old livein/out
qinsoon's avatar
qinsoon committed
709
            let in_set_old = livein.get(node).unwrap().clone();
710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740
            let out_set_old = liveout.get(node).unwrap().clone();

            // in <- use + (out - def)
            {
                let mut inset = livein.get_mut(node).unwrap();

                inset.clear();

                // (1) out - def
                inset.add_all(liveout.get(node).unwrap().clone());
                for def in cfg_node.defs.iter() {
                    inset.remove(def);
                }

                // (2) in + (out - def)
                for in_reg in cfg_node.uses.iter() {
                    inset.insert(*in_reg);
                }
            }

            // out[n] <- union(in[s] for every successor s of n)
            {
                let mut outset = liveout.get_mut(node).unwrap();
                outset.clear();

                for s in cfg_node.succ.iter() {
                    outset.add_all(livein.get(s).unwrap().clone());
                }
            }

            // is in/out changed in this iteration?
qinsoon's avatar
qinsoon committed
741 742
            let n_changed = !in_set_old.equals(livein.get(node).unwrap()) ||
                !out_set_old.equals(liveout.get(node).unwrap());
743

qinsoon's avatar
qinsoon committed
744
            if TRACE_LIVENESS {
745 746 747 748 749 750 751 752 753 754 755
                trace!("block {}", node);
                trace!("in(old)  = {:?}", in_set_old);
                trace!("in(new)  = {:?}", livein.get(node).unwrap());
                trace!("out(old) = {:?}", out_set_old);
                trace!("out(new) = {:?}", liveout.get(node).unwrap());
            }

            is_changed = is_changed || n_changed;
        }
    }

756 757
    info!("finished in {} iterations", i);

qinsoon's avatar
qinsoon committed
758
    // set live in and live out
759
    for block in blocks.keys() {
qinsoon's avatar
qinsoon committed
760 761 762 763 764 765 766
        let livein: Vec<MuID> = livein
            .get(block)
            .unwrap()
            .clone()
            .iter()
            .map(|x| *x)
            .collect();
767
        if TRACE_LIVENESS {
qinsoon's avatar
qinsoon committed
768 769 770 771
            let display_array: Vec<String> = livein
                .iter()
                .map(|x| func.context.get_temp_display(*x))
                .collect();
772 773 774 775
            trace!("livein  for block {}: {:?}", block, display_array);
        }
        cf.mc_mut().set_ir_block_livein(block, livein);

qinsoon's avatar
qinsoon committed
776 777 778 779 780 781 782
        let liveout: Vec<MuID> = liveout
            .get(block)
            .unwrap()
            .clone()
            .iter()
            .map(|x| *x)
            .collect();
783
        if TRACE_LIVENESS {
qinsoon's avatar
qinsoon committed
784 785 786 787
            let display_array: Vec<String> = liveout
                .iter()
                .map(|x| func.context.get_temp_display(*x))
                .collect();
788 789 790 791
            trace!("liveout for block {}: {:?}", block, display_array);
        }
        cf.mc_mut().set_ir_block_liveout(block, liveout);
    }
qinsoon's avatar
qinsoon committed
792
}