liveness.rs 26.7 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 43 44
    spill_cost: f32,
    /// cost to freeze this temp
    freeze_cost: f32
45
}
46

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

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

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

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

95 96 97 98 99 100 101 102 103 104 105
#[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
106 107 108 109
/// InterferenceGraph represents the interference graph, including
/// * the graph
/// * all the nodes and its NodeIndex (a node is referred to by NodeIndex)
/// * all the moves
110
pub struct InterferenceGraph {
111 112 113 114 115
    nodes: LinkedHashMap<MuID, Node>,

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

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

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

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

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

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

162
        reg_id
qinsoon's avatar
qinsoon committed
163
    }
qinsoon's avatar
qinsoon committed
164

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

        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
180
    /// returns all the nodes in the graph
181 182
    pub fn nodes(&self) -> Vec<MuID> {
        self.nodes.keys().map(|x| *x).collect()
183
    }
qinsoon's avatar
qinsoon committed
184 185

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

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

        let dst = {
202 203
            if is_precolored(dst) {
                backend::get_color_for_precolored(dst)
qinsoon's avatar
qinsoon committed
204 205 206 207 208
            } else {
                dst
            }
        };

qinsoon's avatar
qinsoon committed
209
        self.moves.insert(Move { from: src, to: dst });
210
    }
qinsoon's avatar
qinsoon committed
211 212

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

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

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

242 243
            self.adj_set.insert((u, v));
            self.adj_set.insert((v, u));
qinsoon's avatar
qinsoon committed
244

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

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

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

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

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

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

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

290 291 292 293 294 295 296 297 298 299
    /// sets the freeze cost of a node
    pub fn set_freeze_cost(&mut self, reg: MuID, cost: f32) {
        self.nodes.get_mut(&reg).unwrap().freeze_cost = cost;
    }

    /// gets the freeze cost of a node
    pub fn get_freeze_cost(&self, reg: MuID) -> f32 {
        self.nodes.get(&reg).unwrap().freeze_cost
    }

qinsoon's avatar
qinsoon committed
300
    /// are two nodes the same node?
301 302
    fn is_same_node(&self, reg1: MuID, reg2: MuID) -> bool {
        reg1 == reg2
qinsoon's avatar
qinsoon committed
303
    }
304

qinsoon's avatar
qinsoon committed
305
    /// are two nodes from the same reg group?
306 307
    fn is_same_group(&self, reg1: MuID, reg2: MuID) -> bool {
        self.get_group_of(reg1) == self.get_group_of(reg2)
308
    }
qinsoon's avatar
qinsoon committed
309

310 311 312
    /// 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
313
    }
qinsoon's avatar
qinsoon committed
314

315 316
    pub fn is_in_adj_set(&self, u: MuID, v: MuID) -> bool {
        self.adj_set.contains(&(u, v))
317
    }
qinsoon's avatar
qinsoon committed
318 319

    /// gets degree of a node (number of edges from the node)
320
    pub fn get_degree_of(&self, reg: MuID) -> usize {
qinsoon's avatar
qinsoon committed
321 322
        let ret = *self.degree.get(&reg).unwrap();
        ret
323 324 325
    }

    pub fn set_degree_of(&mut self, reg: MuID, degree: usize) {
326
        trace!("  (set degree({}) = {})", reg, degree);
qinsoon's avatar
qinsoon committed
327
        self.degree.insert(reg, degree);
328
    }
qinsoon's avatar
qinsoon committed
329 330

    /// prints current graph for debugging (via trace log)
qinsoon's avatar
qinsoon committed
331
    #[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
332
    pub fn print(&self, context: &FunctionContext) {
333 334
        trace!("");
        trace!("Interference Graph");
335

336
        trace!("nodes: ");
qinsoon's avatar
qinsoon committed
337 338
        for node in self.nodes.values() {
            trace!("{:?}", node);
339 340 341 342
        }

        trace!("edges: ");
        for id in self.nodes.keys() {
qinsoon's avatar
qinsoon committed
343 344 345 346 347 348 349 350 351 352 353 354 355
            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));
                }
356
            }
qinsoon's avatar
qinsoon committed
357
            trace!("{}", s);
358
        }
359
    }
qinsoon's avatar
qinsoon committed
360 361
}

qinsoon's avatar
qinsoon committed
362 363 364 365
/// 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
366 367 368 369
/// reference: Tailoring Graph-coloring Register Allocation For Runtime Compilation
/// - CGO'06, Figure 4
pub fn build_interference_graph_chaitin_briggs(
    cf: &mut CompiledFunction,
370
    func: &MuFunctionVersion
qinsoon's avatar
qinsoon committed
371
) -> InterferenceGraph {
372 373
    use compiler::backend::reg_alloc::graph_coloring::liveness::NodeType::*;

qinsoon's avatar
qinsoon committed
374 375 376 377 378 379 380 381
    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();
382

qinsoon's avatar
qinsoon committed
383 384
    // precolor machine register nodes
    for reg in backend::all_regs().values() {
385
        let reg_id = c(reg.extract_ssa_id().unwrap());
386
        let node = ig.new_node(reg_id, Machine, 0, &func.context);
qinsoon's avatar
qinsoon committed
387 388 389 390 391 392
        let precolor = backend::get_color_for_precolored(reg_id);

        ig.color_node(node, precolor);
    }

    // initialize and creates nodes for all the involved temps/regs
393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420
    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
421

422 423 424 425 426
                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
427 428 429 430 431 432
        }
    }

    // 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
433 434 435
        let mut current_live =
            LinkedHashSet::from_vec(match cf.mc().get_ir_block_liveout(&block) {
                Some(liveout) => liveout.to_vec(),
436
                None => panic!("cannot find liveout for block {}", block)
qinsoon's avatar
qinsoon committed
437
            });
438 439 440 441 442 443 444 445 446
        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
447
            }
448 449 450 451 452 453
            trace!("current live: {}", s);
        };

        if TRACE_LIVENESS {
            trace!("---Block {}: live out---", block);
            print_set(&current_live);
qinsoon's avatar
qinsoon committed
454 455 456 457
        }

        let range = cf.mc().get_block_range(&block);
        if range.is_none() {
458
            warn!("Block {}: has no range (no instructions?)", block);
qinsoon's avatar
qinsoon committed
459 460
            continue;
        }
qinsoon's avatar
qinsoon committed
461 462
        trace_if!(
            TRACE_LIVENESS,
463
            "Block {}: range = {:?}",
qinsoon's avatar
qinsoon committed
464 465 466
            block,
            range.as_ref().unwrap()
        );
qinsoon's avatar
qinsoon committed
467 468 469

        // for every inst I in reverse order
        for i in range.unwrap().rev() {
470
            if TRACE_LIVENESS {
471
                trace!("Block {}: Inst{}", block, i);
qinsoon's avatar
qinsoon committed
472
                cf.mc().trace_inst(i);
473
                print_set(&current_live);
qinsoon's avatar
qinsoon committed
474 475
            }

qinsoon's avatar
qinsoon committed
476
            let src: Option<MuID> = {
qinsoon's avatar
qinsoon committed
477 478 479 480 481 482 483 484 485 486 487
                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 {
488 489 490
                            let src = c(src[0]);
                            let dst = c(dst[0]);
                            trace_if!(TRACE_LIVENESS, "add move {} -> {}", src, dst);
491
                            ig.add_move(src, dst);
qinsoon's avatar
qinsoon committed
492

493
                            Some(src)
qinsoon's avatar
qinsoon committed
494 495 496 497 498 499 500 501 502
                        } else {
                            None
                        }
                    }
                } else {
                    None
                }
            };

503
            let defines = cf.mc().get_inst_reg_defines(i);
qinsoon's avatar
qinsoon committed
504
            for d in defines.iter() {
505 506 507 508 509 510
                let d = c(*d);
                current_live.insert(d);
            }
            if TRACE_LIVENESS {
                trace!("after adding defines:");
                print_set(&current_live);
qinsoon's avatar
qinsoon committed
511 512 513
            }

            // for every definition D in I
514 515 516 517 518 519 520 521 522
            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
523
            for d in defines {
524
                let d = c(d);
qinsoon's avatar
qinsoon committed
525 526 527 528
                // 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()) {
529 530
                        let from = d;
                        let to = *e;
qinsoon's avatar
qinsoon committed
531

532
                        if !ig.is_same_node(from, to) && ig.is_same_group(from, to) {
qinsoon's avatar
qinsoon committed
533
                            if !ig.is_colored(from) {
534
                                trace_if!(TRACE_LIVENESS, "add edge between {} and {}", d, *e);
535
                                ig.add_edge(from, to);
qinsoon's avatar
qinsoon committed
536 537
                            }
                            if !ig.is_colored(to) {
538
                                trace_if!(TRACE_LIVENESS, "add edge between {} and {}", *e, d);
539
                                ig.add_edge(to, from);
qinsoon's avatar
qinsoon committed
540 541 542 543 544 545 546 547
                            }
                        }
                    }
                }
            }

            // for every definition D in I
            for d in cf.mc().get_inst_reg_defines(i) {
548
                let d = c(d);
qinsoon's avatar
qinsoon committed
549 550 551
                // remove D from Current_Live
                current_live.remove(&d);
            }
552 553 554 555
            if TRACE_LIVENESS {
                trace!("removing defines from current live...");
                print_set(&current_live);
            }
qinsoon's avatar
qinsoon committed
556 557 558

            // for every use U in I
            for u in cf.mc().get_inst_reg_uses(i) {
559
                let u = c(u);
qinsoon's avatar
qinsoon committed
560 561 562
                // add U to Current_live
                current_live.insert(u);
            }
563
            if TRACE_LIVENESS {
564
                trace!("adding uses to current live...")
qinsoon's avatar
qinsoon committed
565 566 567 568 569 570 571 572 573 574 575
            }
        }
    }

    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
576
    info!("---start building live set---");
577

qinsoon's avatar
qinsoon committed
578 579 580
    // build control flow graphs, treat a whole block as one node in the graph
    let cfg = build_cfg_nodes(cf);
    // do liveness analysis
581 582 583 584 585
    global_liveness_analysis(cfg, cf, func);

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

qinsoon's avatar
qinsoon committed
586
/// CFGBlockNode represents a basic block as a whole for global liveness analysis
587 588
#[derive(Clone, Debug)]
struct CFGBlockNode {
589
    block: MuName,
590 591
    pred: Vec<String>,
    succ: Vec<String>,
qinsoon's avatar
qinsoon committed
592
    uses: Vec<MuID>,
593
    defs: Vec<MuID>
594 595
}

qinsoon's avatar
qinsoon committed
596 597 598 599 600 601
/// builds a LinkedHashMap from basic block names to CFGBlockNode
/// We need to collect for each basic block:
/// * predecessors
/// * successors
/// * uses
/// * defs
602
fn build_cfg_nodes(cf: &mut CompiledFunction) -> LinkedHashMap<MuName, CFGBlockNode> {
603 604
    info!("---local liveness analysis---");
    let mc = cf.mc();
605
    let mut ret = LinkedHashMap::new();
606 607 608
    let all_blocks = mc.get_all_blocks();

    // create maps (start_inst -> name) and (end_inst -> name)
qinsoon's avatar
qinsoon committed
609 610
    // 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
611 612
        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
613 614 615
        for block in all_blocks.iter() {
            let range = match mc.get_block_range(block) {
                Some(range) => range,
616
                None => panic!("cannot find range for block {}", block)
qinsoon's avatar
qinsoon committed
617 618 619 620 621 622
            };
            // 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
623 624 625 626 627 628 629
                None => {
                    panic!(
                        "cannot find last instruction in block {}, \
                         this block contains no instruction?",
                        block
                    )
                }
qinsoon's avatar
qinsoon committed
630
            };
qinsoon's avatar
qinsoon committed
631 632 633 634 635 636 637
            trace_if!(
                TRACE_LIVENESS,
                "Block {}: start_inst={}, end_inst(inclusive)={}",
                block,
                first_inst,
                last_inst
            );
638

qinsoon's avatar
qinsoon committed
639 640 641 642 643 644
            start_inst_map.insert(first_inst, block);
            end_inst_map.insert(last_inst, block);
        }

        (start_inst_map, end_inst_map)
    };
645

qinsoon's avatar
qinsoon committed
646
    // collect info for each basic block
647
    for block in mc.get_all_blocks().iter() {
648
        trace_if!(TRACE_LIVENESS, "---block {}---", block);
649 650
        let range = mc.get_block_range(block).unwrap();
        let start_inst = range.start;
qinsoon's avatar
qinsoon committed
651
        let end = range.end;
652

qinsoon's avatar
qinsoon committed
653 654 655 656 657 658 659
        // 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
660
            let mut all_defined: LinkedHashSet<MuID> = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
661 662 663 664 665 666

            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 {
667
                    let reg = c(reg);
qinsoon's avatar
qinsoon committed
668 669 670 671
                    if !all_defined.contains(&reg) {
                        livein.push(reg);
                    }
                }
672

qinsoon's avatar
qinsoon committed
673 674
                let reg_defs = mc.get_inst_reg_defines(i);
                for reg in reg_defs {
675
                    let reg = c(reg);
qinsoon's avatar
qinsoon committed
676
                    all_defined.insert(reg);
677 678 679
                }
            }

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

qinsoon's avatar
qinsoon committed
682 683
            (livein, defs)
        };
684

qinsoon's avatar
qinsoon committed
685
        let preds: Vec<String> = {
686 687
            let mut ret = vec![];

qinsoon's avatar
qinsoon committed
688
            // predecessors of the first instruction is the predecessors of this block
689 690 691 692 693 694 695 696 697 698
            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
699
        let succs: Vec<String> = {
700 701
            let mut ret = vec![];

qinsoon's avatar
qinsoon committed
702
            // successors of the last instruction is the successors of this block
703
            for succ in mc.get_succs(mc.get_last_inst(end).unwrap()).into_iter() {
704 705 706 707 708 709 710 711 712 713 714 715 716 717
                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,
718
            defs: defs
719 720
        };

721
        trace_if!(TRACE_LIVENESS, "as CFGNode {:?}", node);
722 723 724 725 726 727
        ret.insert(block.clone(), node);
    }

    ret
}

qinsoon's avatar
qinsoon committed
728
/// global analysis, the iterative algorithm to compute livenss until livein/out reaches a fix point
qinsoon's avatar
qinsoon committed
729
fn global_liveness_analysis(
730
    blocks: LinkedHashMap<MuName, CFGBlockNode>,
qinsoon's avatar
qinsoon committed
731
    cf: &mut CompiledFunction,
732
    func: &MuFunctionVersion
qinsoon's avatar
qinsoon committed
733
) {
734 735
    info!("---global liveness analysis---");
    info!("{} blocks", blocks.len());
736 737

    // init live in and live out
738
    let mut livein: LinkedHashMap<MuName, LinkedHashSet<MuID>> = {
739
        let mut ret = LinkedHashMap::new();
740 741 742 743 744
        for name in blocks.keys() {
            ret.insert(name.clone(), LinkedHashSet::new());
        }
        ret
    };
745
    let mut liveout: LinkedHashMap<MuName, LinkedHashSet<MuID>> = {
746
        let mut ret = LinkedHashMap::new();
747 748 749 750 751 752
        for name in blocks.keys() {
            ret.insert(name.clone(), LinkedHashSet::new());
        }
        ret
    };

qinsoon's avatar
qinsoon committed
753
    // is the result changed in this iteration?
754
    let mut is_changed = true;
qinsoon's avatar
qinsoon committed
755
    // record iteration count
756 757 758
    let mut i = 0;

    while is_changed {
759
        trace_if!(TRACE_LIVENESS, "---iteration {}---", i);
760 761 762 763 764 765 766 767
        i += 1;

        // reset
        is_changed = false;

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

qinsoon's avatar
qinsoon committed
768
            // old livein/out
qinsoon's avatar
qinsoon committed
769
            let in_set_old = livein.get(node).unwrap().clone();
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
            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
801 802
            let n_changed = !in_set_old.equals(livein.get(node).unwrap()) ||
                !out_set_old.equals(liveout.get(node).unwrap());
803

qinsoon's avatar
qinsoon committed
804
            if TRACE_LIVENESS {
805 806 807 808 809 810 811 812 813 814 815
                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;
        }
    }

816 817
    info!("finished in {} iterations", i);

qinsoon's avatar
qinsoon committed
818
    // set live in and live out
819
    for block in blocks.keys() {
qinsoon's avatar
qinsoon committed
820 821 822 823 824 825 826
        let livein: Vec<MuID> = livein
            .get(block)
            .unwrap()
            .clone()
            .iter()
            .map(|x| *x)
            .collect();
827
        if TRACE_LIVENESS {
qinsoon's avatar
qinsoon committed
828 829 830 831
            let display_array: Vec<String> = livein
                .iter()
                .map(|x| func.context.get_temp_display(*x))
                .collect();
832 833 834 835
            trace!("livein  for block {}: {:?}", block, display_array);
        }
        cf.mc_mut().set_ir_block_livein(block, livein);

qinsoon's avatar
qinsoon committed
836 837 838 839 840 841 842
        let liveout: Vec<MuID> = liveout
            .get(block)
            .unwrap()
            .clone()
            .iter()
            .map(|x| *x)
            .collect();
843
        if TRACE_LIVENESS {
qinsoon's avatar
qinsoon committed
844 845 846 847
            let display_array: Vec<String> = liveout
                .iter()
                .map(|x| func.context.get_temp_display(*x))
                .collect();
848 849 850 851
            trace!("liveout for block {}: {:?}", block, display_array);
        }
        cf.mc_mut().set_ir_block_liveout(block, liveout);
    }
qinsoon's avatar
qinsoon committed
852
}