liveness.rs 26.3 KB
Newer Older
1
// Copyright 2017 The Australian National University
qinsoon's avatar
qinsoon committed
2
//
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
//
7
//     http://www.apache.org/licenses/LICENSE-2.0
qinsoon's avatar
qinsoon committed
8
//
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::*;
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

24 25 26 27 28 29 30 31
#[derive(Copy, Clone, Debug, PartialEq)]
pub enum NodeType {
    Def,
    Use,
    Copy,
    Machine
}

qinsoon's avatar
qinsoon committed
32
/// GraphNode represents a node in the interference graph.
qinsoon's avatar
qinsoon committed
33
#[derive(Clone, Copy, PartialEq)]
34
pub struct Node {
qinsoon's avatar
qinsoon committed
35
    /// temp ID (could be register)
36
    temp: MuID,
qinsoon's avatar
qinsoon committed
37
    /// assigned color
38
    color: Option<MuID>,
qinsoon's avatar
qinsoon committed
39
    /// temp register group (which machine register class we should assign)
40
    group: backend::RegGroup,
qinsoon's avatar
qinsoon committed
41
    /// cost to spill this temp
42
    spill_cost: f32
43
}
44

qinsoon's avatar
qinsoon committed
45 46 47 48 49 50 51 52 53 54 55 56 57
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
58 59
/// 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
60
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
qinsoon's avatar
qinsoon committed
61
pub struct Move {
62 63 64 65
    pub from: MuID,
    pub to: MuID
}

qinsoon's avatar
qinsoon committed
66 67 68 69 70 71
impl fmt::Debug for Move {
    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
        write!(f, "Move ({} -> {})", self.from, self.to)
    }
}

72 73 74 75 76 77 78
#[inline(always)]
fn is_precolored(reg: MuID) -> bool {
    if reg < MACHINE_ID_END {
        true
    } else {
        false
    }
qinsoon's avatar
qinsoon committed
79
}
80

81 82
#[inline(always)]
fn is_usable(reg: MuID) -> bool {
qinsoon's avatar
qinsoon committed
83 84 85 86
    if backend::all_usable_regs()
        .iter()
        .any(|x| x.id() == backend::get_color_for_precolored(reg))
    {
87 88 89 90 91 92
        true
    } else {
        false
    }
}

93 94 95 96 97 98 99 100 101 102 103
#[inline(always)]
/// checks if a reg is machine register. If so, return its color
/// otherwise return the reg
fn c(u: MuID) -> MuID {
    if is_precolored(u) {
        backend::get_color_for_precolored(u)
    } else {
        u
    }
}

qinsoon's avatar
qinsoon committed
104 105 106 107
/// InterferenceGraph represents the interference graph, including
/// * the graph
/// * all the nodes and its NodeIndex (a node is referred to by NodeIndex)
/// * all the moves
108
pub struct InterferenceGraph {
109 110 111 112 113
    nodes: LinkedHashMap<MuID, Node>,

    adj_set: LinkedHashSet<(MuID, MuID)>,
    adj_list: LinkedHashMap<MuID, LinkedHashSet<MuID>>,
    degree: LinkedHashMap<MuID, usize>,
114
    moves: LinkedHashSet<Move>
115 116 117
}

impl InterferenceGraph {
qinsoon's avatar
qinsoon committed
118
    /// creates a new graph
119
    fn new() -> InterferenceGraph {
qinsoon's avatar
qinsoon committed
120
        InterferenceGraph {
121 122 123
            adj_set: LinkedHashSet::new(),
            adj_list: LinkedHashMap::new(),
            degree: LinkedHashMap::new(),
124
            nodes: LinkedHashMap::new(),
125
            moves: LinkedHashSet::new()
qinsoon's avatar
qinsoon committed
126 127
        }
    }
qinsoon's avatar
qinsoon committed
128 129 130

    /// 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
131 132 133 134 135 136 137
    fn new_node(
        &mut self,
        reg_id: MuID,
        ty: NodeType,
        loop_depth: usize,
        context: &FunctionContext
    ) -> MuID {
138
        let entry = context.get_value(reg_id).unwrap();
qinsoon's avatar
qinsoon committed
139 140

        // if it is the first time, create the node
141
        if !self.nodes.contains_key(&reg_id) {
142
            let node = Node {
143
                temp: reg_id,
144
                color: None,
145
                group: backend::RegGroup::get_from_ty(entry.ty()),
146
                spill_cost: 0.0f32
147
            };
148

149 150 151
            self.nodes.insert(reg_id, node);
            self.adj_list.insert(reg_id, LinkedHashSet::new());
            self.degree.insert(reg_id, 0);
152
        }
qinsoon's avatar
qinsoon committed
153 154

        // get node
155
        let node_mut = self.nodes.get_mut(&reg_id).unwrap();
156
        // increase node spill cost
157
        node_mut.spill_cost += InterferenceGraph::spillcost_heuristic(ty, loop_depth);
qinsoon's avatar
qinsoon committed
158

159
        reg_id
qinsoon's avatar
qinsoon committed
160
    }
qinsoon's avatar
qinsoon committed
161

162 163 164 165 166 167 168 169 170 171 172 173 174 175 176
    fn spillcost_heuristic(ty: NodeType, loop_depth: usize) -> f32 {
        const DEF_WEIGHT: f32 = 1f32;
        const USE_WEIGHT: f32 = 1f32;
        const COPY_WEIGHT: f32 = 0.5f32;

        let loop_depth = loop_depth as i32;

        match ty {
            NodeType::Machine => 0f32,
            NodeType::Def => DEF_WEIGHT * (10f32.powi(loop_depth)),
            NodeType::Use => USE_WEIGHT * (10f32.powi(loop_depth)),
            NodeType::Copy => COPY_WEIGHT * (10f32.powi(loop_depth))
        }
    }

qinsoon's avatar
qinsoon committed
177
    /// returns all the nodes in the graph
178 179
    pub fn nodes(&self) -> Vec<MuID> {
        self.nodes.keys().map(|x| *x).collect()
180
    }
qinsoon's avatar
qinsoon committed
181 182

    /// returns all the moves in the graph
183
    pub fn moves(&self) -> &LinkedHashSet<Move> {
184 185
        &self.moves
    }
qinsoon's avatar
qinsoon committed
186 187

    /// adds a move edge between two nodes
188
    fn add_move(&mut self, src: MuID, dst: MuID) {
qinsoon's avatar
qinsoon committed
189
        let src = {
190
            if is_precolored(src) {
qinsoon's avatar
qinsoon committed
191
                // get the color for the machine register, e.g. rax for eax/ax/al/ah
192
                backend::get_color_for_precolored(src)
qinsoon's avatar
qinsoon committed
193 194 195 196 197 198
            } else {
                src
            }
        };

        let dst = {
199 200
            if is_precolored(dst) {
                backend::get_color_for_precolored(dst)
qinsoon's avatar
qinsoon committed
201 202 203 204 205
            } else {
                dst
            }
        };

qinsoon's avatar
qinsoon committed
206
        self.moves.insert(Move { from: src, to: dst });
207
    }
qinsoon's avatar
qinsoon committed
208 209

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

216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235
        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
        };

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

239 240
            self.adj_set.insert((u, v));
            self.adj_set.insert((v, u));
qinsoon's avatar
qinsoon committed
241

242 243
            if !is_precolored(u) {
                self.adj_list.get_mut(&u).unwrap().insert(v);
qinsoon's avatar
qinsoon committed
244 245
                let degree = self.get_degree_of(u);
                self.set_degree_of(u, degree + 1);
246
                trace!("  increase degree of {} to {}", u, degree + 1);
247 248 249
            }
            if !is_precolored(v) {
                self.adj_list.get_mut(&v).unwrap().insert(u);
qinsoon's avatar
qinsoon committed
250 251
                let degree = self.get_degree_of(v);
                self.set_degree_of(v, degree + 1);
252
                trace!("  increase degree of {} to {}", v, degree + 1);
253
            }
qinsoon's avatar
qinsoon committed
254
        }
qinsoon's avatar
qinsoon committed
255 256
    }

qinsoon's avatar
qinsoon committed
257
    /// set color for a node
258 259
    pub fn color_node(&mut self, reg: MuID, color: MuID) {
        self.nodes.get_mut(&reg).unwrap().color = Some(color);
qinsoon's avatar
qinsoon committed
260
    }
qinsoon's avatar
qinsoon committed
261 262

    /// is a node colored yet?
263 264
    pub fn is_colored(&self, reg: MuID) -> bool {
        self.nodes.get(&reg).unwrap().color.is_some()
265
    }
qinsoon's avatar
qinsoon committed
266 267

    /// gets the color of a node
268 269
    pub fn get_color_of(&self, reg: MuID) -> Option<MuID> {
        self.nodes.get(&reg).unwrap().color
270
    }
qinsoon's avatar
qinsoon committed
271 272

    /// gets the reg group of a node
273 274
    pub fn get_group_of(&self, reg: MuID) -> backend::RegGroup {
        self.nodes.get(&reg).unwrap().group
qinsoon's avatar
qinsoon committed
275
    }
qinsoon's avatar
qinsoon committed
276 277

    /// gets the temporary of a node
278 279
    pub fn get_temp_of(&self, reg: MuID) -> MuID {
        self.nodes.get(&reg).unwrap().temp
280
    }
qinsoon's avatar
qinsoon committed
281 282

    /// gets the spill cost of a node
283 284
    pub fn get_spill_cost(&self, reg: MuID) -> f32 {
        self.nodes.get(&reg).unwrap().spill_cost
285
    }
qinsoon's avatar
qinsoon committed
286 287

    /// are two nodes the same node?
288 289
    fn is_same_node(&self, reg1: MuID, reg2: MuID) -> bool {
        reg1 == reg2
qinsoon's avatar
qinsoon committed
290
    }
291

qinsoon's avatar
qinsoon committed
292
    /// are two nodes from the same reg group?
293 294
    fn is_same_group(&self, reg1: MuID, reg2: MuID) -> bool {
        self.get_group_of(reg1) == self.get_group_of(reg2)
295
    }
qinsoon's avatar
qinsoon committed
296

297 298 299
    /// 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
300
    }
qinsoon's avatar
qinsoon committed
301

302 303
    pub fn is_in_adj_set(&self, u: MuID, v: MuID) -> bool {
        self.adj_set.contains(&(u, v))
304
    }
qinsoon's avatar
qinsoon committed
305 306

    /// gets degree of a node (number of edges from the node)
307
    pub fn get_degree_of(&self, reg: MuID) -> usize {
qinsoon's avatar
qinsoon committed
308 309
        let ret = *self.degree.get(&reg).unwrap();
        ret
310 311 312
    }

    pub fn set_degree_of(&mut self, reg: MuID, degree: usize) {
313
        trace!("  set degree({}) = {}", reg, degree);
qinsoon's avatar
qinsoon committed
314
        self.degree.insert(reg, degree);
315
    }
qinsoon's avatar
qinsoon committed
316 317

    /// prints current graph for debugging (via trace log)
qinsoon's avatar
qinsoon committed
318
    #[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
319
    pub fn print(&self, context: &FunctionContext) {
320 321
        trace!("");
        trace!("Interference Graph");
322

323
        trace!("nodes: ");
qinsoon's avatar
qinsoon committed
324 325
        for node in self.nodes.values() {
            trace!("{:?}", node);
326 327 328 329
        }

        trace!("edges: ");
        for id in self.nodes.keys() {
qinsoon's avatar
qinsoon committed
330 331 332 333 334 335 336 337 338 339 340 341 342
            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));
                }
343
            }
qinsoon's avatar
qinsoon committed
344
            trace!("{}", s);
345
        }
346
    }
qinsoon's avatar
qinsoon committed
347 348
}

qinsoon's avatar
qinsoon committed
349 350 351 352
/// 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
353 354 355 356
/// reference: Tailoring Graph-coloring Register Allocation For Runtime Compilation
/// - CGO'06, Figure 4
pub fn build_interference_graph_chaitin_briggs(
    cf: &mut CompiledFunction,
357
    func: &MuFunctionVersion
qinsoon's avatar
qinsoon committed
358
) -> InterferenceGraph {
359 360
    use compiler::backend::reg_alloc::graph_coloring::liveness::NodeType::*;

qinsoon's avatar
qinsoon committed
361 362 363 364 365 366 367 368
    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();
369

qinsoon's avatar
qinsoon committed
370 371
    // precolor machine register nodes
    for reg in backend::all_regs().values() {
372
        let reg_id = c(reg.extract_ssa_id().unwrap());
373
        let node = ig.new_node(reg_id, Machine, 0, &func.context);
qinsoon's avatar
qinsoon committed
374 375 376 377 378 379
        let precolor = backend::get_color_for_precolored(reg_id);

        ig.color_node(node, precolor);
    }

    // initialize and creates nodes for all the involved temps/regs
380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407
    let mc = cf.mc();
    for block in mc.get_all_blocks() {
        debug!("build graph node for block {}", block);
        let loop_depth: usize = match cf.loop_analysis.as_ref().unwrap().loop_depth.get(&block) {
            Some(depth) => *depth,
            None => 0
        };
        debug!("loop depth = {}", loop_depth);
        for i in mc.get_block_range(&block).unwrap() {
            // we separate the case of move nodes, and normal instruction
            // as they yield different spill cost
            // (we prefer spill a node in move instruction
            // as the move instruction can be eliminated)
            if mc.is_move(i) {
                for reg_id in mc.get_inst_reg_defines(i) {
                    let reg_id = c(reg_id);
                    ig.new_node(reg_id, Copy, loop_depth, &func.context);
                }

                for reg_id in mc.get_inst_reg_uses(i) {
                    let reg_id = c(reg_id);
                    ig.new_node(reg_id, Copy, loop_depth, &func.context);
                }
            } else {
                for reg_id in mc.get_inst_reg_defines(i) {
                    let reg_id = c(reg_id);
                    ig.new_node(reg_id, Def, loop_depth, &func.context);
                }
qinsoon's avatar
qinsoon committed
408

409 410 411 412 413
                for reg_id in mc.get_inst_reg_uses(i) {
                    let reg_id = c(reg_id);
                    ig.new_node(reg_id, Use, loop_depth, &func.context);
                }
            }
qinsoon's avatar
qinsoon committed
414 415 416 417 418 419
        }
    }

    // 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
420 421 422
        let mut current_live =
            LinkedHashSet::from_vec(match cf.mc().get_ir_block_liveout(&block) {
                Some(liveout) => liveout.to_vec(),
423
                None => panic!("cannot find liveout for block {}", block)
qinsoon's avatar
qinsoon committed
424
            });
425 426 427 428 429 430 431 432 433
        let print_set = |set: &LinkedHashSet<MuID>| {
            let mut s = String::new();
            let mut iter = set.iter();
            if let Some(first) = iter.next() {
                s.push_str(&format!("{}", first));
                while let Some(i) = iter.next() {
                    s.push(' ');
                    s.push_str(&format!("{}", i));
                }
qinsoon's avatar
qinsoon committed
434
            }
435 436 437 438 439 440
            trace!("current live: {}", s);
        };

        if TRACE_LIVENESS {
            trace!("---Block {}: live out---", block);
            print_set(&current_live);
qinsoon's avatar
qinsoon committed
441 442 443 444
        }

        let range = cf.mc().get_block_range(&block);
        if range.is_none() {
445
            warn!("Block {}: has no range (no instructions?)", block);
qinsoon's avatar
qinsoon committed
446 447
            continue;
        }
qinsoon's avatar
qinsoon committed
448 449
        trace_if!(
            TRACE_LIVENESS,
450
            "Block {}: range = {:?}",
qinsoon's avatar
qinsoon committed
451 452 453
            block,
            range.as_ref().unwrap()
        );
qinsoon's avatar
qinsoon committed
454 455 456

        // for every inst I in reverse order
        for i in range.unwrap().rev() {
457
            if TRACE_LIVENESS {
458
                trace!("Block {}: Inst{}", block, i);
qinsoon's avatar
qinsoon committed
459
                cf.mc().trace_inst(i);
460
                print_set(&current_live);
qinsoon's avatar
qinsoon committed
461 462
            }

qinsoon's avatar
qinsoon committed
463
            let src: Option<MuID> = {
qinsoon's avatar
qinsoon committed
464 465 466 467 468 469 470 471 472 473 474
                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 {
475 476 477
                            let src = c(src[0]);
                            let dst = c(dst[0]);
                            trace_if!(TRACE_LIVENESS, "add move {} -> {}", src, dst);
478
                            ig.add_move(src, dst);
qinsoon's avatar
qinsoon committed
479

480
                            Some(src)
qinsoon's avatar
qinsoon committed
481 482 483 484 485 486 487 488 489
                        } else {
                            None
                        }
                    }
                } else {
                    None
                }
            };

490
            let defines = cf.mc().get_inst_reg_defines(i);
qinsoon's avatar
qinsoon committed
491
            for d in defines.iter() {
492 493 494 495 496 497
                let d = c(*d);
                current_live.insert(d);
            }
            if TRACE_LIVENESS {
                trace!("after adding defines:");
                print_set(&current_live);
qinsoon's avatar
qinsoon committed
498 499 500
            }

            // for every definition D in I
501 502 503 504 505 506 507 508 509
            trace_if!(
                TRACE_LIVENESS,
                "for every defines in the instruction, add edge..."
            );
            trace_if!(
                TRACE_LIVENESS,
                "(move source {:?} does not interference with defines)",
                src
            );
qinsoon's avatar
qinsoon committed
510
            for d in defines {
511
                let d = c(d);
qinsoon's avatar
qinsoon committed
512 513 514 515
                // add an interference from D to every element E in Current_Live - {D}
                // creating nodes if necessary
                for e in current_live.iter() {
                    if src.is_none() || (src.is_some() && *e != src.unwrap()) {
516 517
                        let from = d;
                        let to = *e;
qinsoon's avatar
qinsoon committed
518

519
                        if !ig.is_same_node(from, to) && ig.is_same_group(from, to) {
qinsoon's avatar
qinsoon committed
520
                            if !ig.is_colored(from) {
521
                                trace_if!(TRACE_LIVENESS, "add edge between {} and {}", d, *e);
522
                                ig.add_edge(from, to);
qinsoon's avatar
qinsoon committed
523 524
                            }
                            if !ig.is_colored(to) {
525
                                trace_if!(TRACE_LIVENESS, "add edge between {} and {}", *e, d);
526
                                ig.add_edge(to, from);
qinsoon's avatar
qinsoon committed
527 528 529 530 531 532 533 534
                            }
                        }
                    }
                }
            }

            // for every definition D in I
            for d in cf.mc().get_inst_reg_defines(i) {
535
                let d = c(d);
qinsoon's avatar
qinsoon committed
536 537 538
                // remove D from Current_Live
                current_live.remove(&d);
            }
539 540 541 542
            if TRACE_LIVENESS {
                trace!("removing defines from current live...");
                print_set(&current_live);
            }
qinsoon's avatar
qinsoon committed
543 544 545

            // for every use U in I
            for u in cf.mc().get_inst_reg_uses(i) {
546
                let u = c(u);
qinsoon's avatar
qinsoon committed
547 548 549
                // add U to Current_live
                current_live.insert(u);
            }
550
            if TRACE_LIVENESS {
551
                trace!("adding uses to current live...")
qinsoon's avatar
qinsoon committed
552 553 554 555 556 557 558 559 560 561 562
            }
        }
    }

    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
qinsoon committed
563
    info!("---start building live set---");
564

qinsoon's avatar
qinsoon committed
565 566 567
    // build control flow graphs, treat a whole block as one node in the graph
    let cfg = build_cfg_nodes(cf);
    // do liveness analysis
568 569 570 571 572
    global_liveness_analysis(cfg, cf, func);

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

qinsoon's avatar
qinsoon committed
573
/// CFGBlockNode represents a basic block as a whole for global liveness analysis
574 575
#[derive(Clone, Debug)]
struct CFGBlockNode {
576
    block: MuName,
577 578
    pred: Vec<String>,
    succ: Vec<String>,
qinsoon's avatar
qinsoon committed
579
    uses: Vec<MuID>,
580
    defs: Vec<MuID>
581 582
}

qinsoon's avatar
qinsoon committed
583 584 585 586 587 588
/// builds a LinkedHashMap from basic block names to CFGBlockNode
/// We need to collect for each basic block:
/// * predecessors
/// * successors
/// * uses
/// * defs
589
fn build_cfg_nodes(cf: &mut CompiledFunction) -> LinkedHashMap<MuName, CFGBlockNode> {
590 591
    info!("---local liveness analysis---");
    let mc = cf.mc();
592
    let mut ret = LinkedHashMap::new();
593 594 595
    let all_blocks = mc.get_all_blocks();

    // create maps (start_inst -> name) and (end_inst -> name)
qinsoon's avatar
qinsoon committed
596 597
    // 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
598 599
        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
600 601 602
        for block in all_blocks.iter() {
            let range = match mc.get_block_range(block) {
                Some(range) => range,
603
                None => panic!("cannot find range for block {}", block)
qinsoon's avatar
qinsoon committed
604
            };
605

qinsoon's avatar
qinsoon committed
606 607 608 609 610
            // 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
611 612 613 614 615 616 617
                None => {
                    panic!(
                        "cannot find last instruction in block {}, \
                         this block contains no instruction?",
                        block
                    )
                }
qinsoon's avatar
qinsoon committed
618
            };
qinsoon's avatar
qinsoon committed
619 620 621 622 623 624 625
            trace_if!(
                TRACE_LIVENESS,
                "Block {}: start_inst={}, end_inst(inclusive)={}",
                block,
                first_inst,
                last_inst
            );
626

qinsoon's avatar
qinsoon committed
627 628 629 630 631 632
            start_inst_map.insert(first_inst, block);
            end_inst_map.insert(last_inst, block);
        }

        (start_inst_map, end_inst_map)
    };
633

qinsoon's avatar
qinsoon committed
634
    // collect info for each basic block
635
    for block in mc.get_all_blocks().iter() {
636
        trace_if!(TRACE_LIVENESS, "---block {}---", block);
637 638
        let range = mc.get_block_range(block).unwrap();
        let start_inst = range.start;
qinsoon's avatar
qinsoon committed
639
        let end = range.end;
640

qinsoon's avatar
qinsoon committed
641 642 643 644 645 646 647
        // 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
648
            let mut all_defined: LinkedHashSet<MuID> = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
649 650 651 652 653 654

            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 {
655
                    let reg = c(reg);
qinsoon's avatar
qinsoon committed
656 657 658 659
                    if !all_defined.contains(&reg) {
                        livein.push(reg);
                    }
                }
660

qinsoon's avatar
qinsoon committed
661 662
                let reg_defs = mc.get_inst_reg_defines(i);
                for reg in reg_defs {
663
                    let reg = c(reg);
qinsoon's avatar
qinsoon committed
664
                    all_defined.insert(reg);
665 666 667
                }
            }

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

qinsoon's avatar
qinsoon committed
670 671
            (livein, defs)
        };
672

qinsoon's avatar
qinsoon committed
673
        let preds: Vec<String> = {
674 675
            let mut ret = vec![];

qinsoon's avatar
qinsoon committed
676
            // predecessors of the first instruction is the predecessors of this block
677 678 679 680 681 682 683 684 685 686
            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
687
        let succs: Vec<String> = {
688 689
            let mut ret = vec![];

qinsoon's avatar
qinsoon committed
690
            // successors of the last instruction is the successors of this block
691
            for succ in mc.get_succs(mc.get_last_inst(end).unwrap()).into_iter() {
692 693 694 695 696 697 698 699 700 701 702 703 704 705
                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,
706
            defs: defs
707 708
        };

709
        trace_if!(TRACE_LIVENESS, "as CFGNode {:?}", node);
710 711 712 713 714 715
        ret.insert(block.clone(), node);
    }

    ret
}

qinsoon's avatar
qinsoon committed
716
/// global analysis, the iterative algorithm to compute livenss until livein/out reaches a fix point
qinsoon's avatar
qinsoon committed
717
fn global_liveness_analysis(
718
    blocks: LinkedHashMap<MuName, CFGBlockNode>,
qinsoon's avatar
qinsoon committed
719
    cf: &mut CompiledFunction,
720
    func: &MuFunctionVersion
qinsoon's avatar
qinsoon committed
721
) {
722 723
    info!("---global liveness analysis---");
    info!("{} blocks", blocks.len());
724 725

    // init live in and live out
726
    let mut livein: LinkedHashMap<MuName, LinkedHashSet<MuID>> = {
727
        let mut ret = LinkedHashMap::new();
728 729 730 731 732
        for name in blocks.keys() {
            ret.insert(name.clone(), LinkedHashSet::new());
        }
        ret
    };
733
    let mut liveout: LinkedHashMap<MuName, LinkedHashSet<MuID>> = {
734
        let mut ret = LinkedHashMap::new();
735 736 737 738 739 740
        for name in blocks.keys() {
            ret.insert(name.clone(), LinkedHashSet::new());
        }
        ret
    };

qinsoon's avatar
qinsoon committed
741
    // is the result changed in this iteration?
742
    let mut is_changed = true;
qinsoon's avatar
qinsoon committed
743
    // record iteration count
744 745 746
    let mut i = 0;

    while is_changed {
747
        trace_if!(TRACE_LIVENESS, "---iteration {}---", i);
748 749 750 751 752 753 754 755
        i += 1;

        // reset
        is_changed = false;

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

qinsoon's avatar
qinsoon committed
756
            // old livein/out
qinsoon's avatar
qinsoon committed
757
            let in_set_old = livein.get(node).unwrap().clone();
758 759 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
            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
789 790
            let n_changed = !in_set_old.equals(livein.get(node).unwrap()) ||
                !out_set_old.equals(liveout.get(node).unwrap());
791

qinsoon's avatar
qinsoon committed
792
            if TRACE_LIVENESS {
793 794 795 796 797 798 799 800 801 802 803
                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;
        }
    }

804 805
    info!("finished in {} iterations", i);

qinsoon's avatar
qinsoon committed
806
    // set live in and live out
807
    for block in blocks.keys() {
qinsoon's avatar
qinsoon committed
808 809 810 811 812 813 814
        let livein: Vec<MuID> = livein
            .get(block)
            .unwrap()
            .clone()
            .iter()
            .map(|x| *x)
            .collect();
815
        if TRACE_LIVENESS {
qinsoon's avatar
qinsoon committed
816 817 818 819
            let display_array: Vec<String> = livein
                .iter()
                .map(|x| func.context.get_temp_display(*x))
                .collect();
820 821 822 823
            trace!("livein  for block {}: {:?}", block, display_array);
        }
        cf.mc_mut().set_ir_block_livein(block, livein);

qinsoon's avatar
qinsoon committed
824 825 826 827 828 829 830
        let liveout: Vec<MuID> = liveout
            .get(block)
            .unwrap()
            .clone()
            .iter()
            .map(|x| *x)
            .collect();
831
        if TRACE_LIVENESS {
qinsoon's avatar
qinsoon committed
832 833 834 835
            let display_array: Vec<String> = liveout
                .iter()
                .map(|x| func.context.get_temp_display(*x))
                .collect();
836 837 838 839
            trace!("liveout for block {}: {:?}", block, display_array);
        }
        cf.mc_mut().set_ir_block_liveout(block, liveout);
    }
qinsoon's avatar
qinsoon committed
840
}