GitLab will be upgraded to the 12.10.14-ce.0 on 28 Sept 2020 at 2.00pm (AEDT) to 2.30pm (AEDT). During the update, GitLab and Mattermost services will not be available. If you have any concerns with this, please talk to us at N110 (b) CSIT building.

liveness.rs 24.3 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
    }
}

85 86 87 88 89 90 91 92 93 94 95
#[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
96 97 98 99
/// InterferenceGraph represents the interference graph, including
/// * the graph
/// * all the nodes and its NodeIndex (a node is referred to by NodeIndex)
/// * all the moves
100
pub struct InterferenceGraph {
101 102 103 104 105
    nodes: LinkedHashMap<MuID, Node>,

    adj_set: LinkedHashSet<(MuID, MuID)>,
    adj_list: LinkedHashMap<MuID, LinkedHashSet<MuID>>,
    degree: LinkedHashMap<MuID, usize>,
106
    moves: LinkedHashSet<Move>
107 108 109
}

impl InterferenceGraph {
qinsoon's avatar
qinsoon committed
110
    /// creates a new graph
111
    fn new() -> InterferenceGraph {
qinsoon's avatar
qinsoon committed
112
        InterferenceGraph {
113 114 115
            adj_set: LinkedHashSet::new(),
            adj_list: LinkedHashMap::new(),
            degree: LinkedHashMap::new(),
116
            nodes: LinkedHashMap::new(),
117
            moves: LinkedHashSet::new()
qinsoon's avatar
qinsoon committed
118 119
        }
    }
qinsoon's avatar
qinsoon committed
120 121 122

    /// 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
123
    fn new_node(&mut self, reg_id: MuID, context: &FunctionContext) -> MuID {
qinsoon's avatar
qinsoon committed
124
        let entry = context.get_value(reg_id).unwrap();
qinsoon's avatar
qinsoon committed
125 126

        // if it is the first time, create the node
qinsoon's avatar
qinsoon committed
127
        if !self.nodes.contains_key(&reg_id) {
128
            let node = Node {
129
                temp: reg_id,
130
                color: None,
131
                group: backend::RegGroup::get_from_ty(entry.ty()),
132
                spill_cost: 0.0f32
qinsoon's avatar
qinsoon committed
133
            };
134

135 136 137
            self.nodes.insert(reg_id, node);
            self.adj_list.insert(reg_id, LinkedHashSet::new());
            self.degree.insert(reg_id, 0);
138
        }
qinsoon's avatar
qinsoon committed
139 140

        // get node
141
        let node_mut = self.nodes.get_mut(&reg_id).unwrap();
142
        // increase node spill cost
143
        node_mut.spill_cost += 1.0f32;
qinsoon's avatar
qinsoon committed
144

145
        reg_id
qinsoon's avatar
qinsoon committed
146
    }
qinsoon's avatar
qinsoon committed
147 148

    /// returns all the nodes in the graph
149 150
    pub fn nodes(&self) -> Vec<MuID> {
        self.nodes.keys().map(|x| *x).collect()
qinsoon's avatar
qinsoon committed
151
    }
qinsoon's avatar
qinsoon committed
152 153

    /// returns all the moves in the graph
154
    pub fn moves(&self) -> &LinkedHashSet<Move> {
qinsoon's avatar
qinsoon committed
155 156
        &self.moves
    }
qinsoon's avatar
qinsoon committed
157 158

    /// adds a move edge between two nodes
159
    fn add_move(&mut self, src: MuID, dst: MuID) {
qinsoon's avatar
qinsoon committed
160
        let src = {
161
            if is_precolored(src) {
qinsoon's avatar
qinsoon committed
162
                // get the color for the machine register, e.g. rax for eax/ax/al/ah
163
                backend::get_color_for_precolored(src)
qinsoon's avatar
qinsoon committed
164 165 166 167 168 169
            } else {
                src
            }
        };

        let dst = {
170 171
            if is_precolored(dst) {
                backend::get_color_for_precolored(dst)
qinsoon's avatar
qinsoon committed
172 173 174 175 176
            } else {
                dst
            }
        };

qinsoon's avatar
qinsoon committed
177
        self.moves.insert(Move { from: src, to: dst });
178
    }
qinsoon's avatar
qinsoon committed
179 180

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

187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206
        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
        };

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

210 211
            self.adj_set.insert((u, v));
            self.adj_set.insert((v, u));
qinsoon's avatar
qinsoon committed
212

213 214
            if !is_precolored(u) {
                self.adj_list.get_mut(&u).unwrap().insert(v);
qinsoon's avatar
qinsoon committed
215 216 217
                let degree = self.get_degree_of(u);
                self.set_degree_of(u, degree + 1);
                trace!("increase degree of {} to {}", u, degree + 1);
218 219 220
            }
            if !is_precolored(v) {
                self.adj_list.get_mut(&v).unwrap().insert(u);
qinsoon's avatar
qinsoon committed
221 222 223
                let degree = self.get_degree_of(v);
                self.set_degree_of(v, degree + 1);
                trace!("increase degree of {} to {}", v, degree + 1);
224
            }
qinsoon's avatar
qinsoon committed
225
        }
qinsoon's avatar
qinsoon committed
226 227
    }

qinsoon's avatar
qinsoon committed
228
    /// set color for a node
229 230
    pub fn color_node(&mut self, reg: MuID, color: MuID) {
        self.nodes.get_mut(&reg).unwrap().color = Some(color);
qinsoon's avatar
qinsoon committed
231
    }
qinsoon's avatar
qinsoon committed
232 233

    /// is a node colored yet?
234 235
    pub fn is_colored(&self, reg: MuID) -> bool {
        self.nodes.get(&reg).unwrap().color.is_some()
qinsoon's avatar
qinsoon committed
236
    }
qinsoon's avatar
qinsoon committed
237 238

    /// gets the color of a node
239 240
    pub fn get_color_of(&self, reg: MuID) -> Option<MuID> {
        self.nodes.get(&reg).unwrap().color
241
    }
qinsoon's avatar
qinsoon committed
242 243

    /// gets the reg group of a node
244 245
    pub fn get_group_of(&self, reg: MuID) -> backend::RegGroup {
        self.nodes.get(&reg).unwrap().group
qinsoon's avatar
qinsoon committed
246
    }
qinsoon's avatar
qinsoon committed
247 248

    /// gets the temporary of a node
249 250
    pub fn get_temp_of(&self, reg: MuID) -> MuID {
        self.nodes.get(&reg).unwrap().temp
251
    }
qinsoon's avatar
qinsoon committed
252 253

    /// gets the spill cost of a node
254 255
    pub fn get_spill_cost(&self, reg: MuID) -> f32 {
        self.nodes.get(&reg).unwrap().spill_cost
256
    }
qinsoon's avatar
qinsoon committed
257 258

    /// are two nodes the same node?
259 260
    fn is_same_node(&self, reg1: MuID, reg2: MuID) -> bool {
        reg1 == reg2
qinsoon's avatar
qinsoon committed
261
    }
262

qinsoon's avatar
qinsoon committed
263
    /// are two nodes from the same reg group?
264 265
    fn is_same_group(&self, reg1: MuID, reg2: MuID) -> bool {
        self.get_group_of(reg1) == self.get_group_of(reg2)
266
    }
qinsoon's avatar
qinsoon committed
267

268 269 270
    /// 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
271
    }
qinsoon's avatar
qinsoon committed
272

273 274
    pub fn is_in_adj_set(&self, u: MuID, v: MuID) -> bool {
        self.adj_set.contains(&(u, v))
275
    }
qinsoon's avatar
qinsoon committed
276 277

    /// gets degree of a node (number of edges from the node)
278
    pub fn get_degree_of(&self, reg: MuID) -> usize {
qinsoon's avatar
qinsoon committed
279 280
        let ret = *self.degree.get(&reg).unwrap();
        ret
281 282 283
    }

    pub fn set_degree_of(&mut self, reg: MuID, degree: usize) {
qinsoon's avatar
qinsoon committed
284 285
        debug!("DEGREE({}) SET TO {}", reg, degree);
        self.degree.insert(reg, degree);
qinsoon's avatar
qinsoon committed
286
    }
qinsoon's avatar
qinsoon committed
287 288

    /// prints current graph for debugging (via trace log)
qinsoon's avatar
qinsoon committed
289
    #[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
290
    pub fn print(&self, context: &FunctionContext) {
291 292
        trace!("");
        trace!("Interference Graph");
293

294
        trace!("nodes: ");
qinsoon's avatar
qinsoon committed
295 296
        for node in self.nodes.values() {
            trace!("{:?}", node);
297 298 299 300
        }

        trace!("edges: ");
        for id in self.nodes.keys() {
qinsoon's avatar
qinsoon committed
301 302 303 304 305 306 307 308 309 310 311 312 313
            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));
                }
314
            }
qinsoon's avatar
qinsoon committed
315
            trace!("{}", s);
316
        }
317
    }
qinsoon's avatar
qinsoon committed
318 319
}

qinsoon's avatar
qinsoon committed
320 321 322 323
/// 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
324 325 326 327
/// reference: Tailoring Graph-coloring Register Allocation For Runtime Compilation
/// - CGO'06, Figure 4
pub fn build_interference_graph_chaitin_briggs(
    cf: &mut CompiledFunction,
328
    func: &MuFunctionVersion
qinsoon's avatar
qinsoon committed
329
) -> InterferenceGraph {
qinsoon's avatar
qinsoon committed
330 331 332 333 334 335 336 337
    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();
338

qinsoon's avatar
qinsoon committed
339 340
    // precolor machine register nodes
    for reg in backend::all_regs().values() {
341
        let reg_id = c(reg.extract_ssa_id().unwrap());
qinsoon's avatar
qinsoon committed
342 343 344 345 346 347 348 349 350
        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) {
351
            let reg_id = c(reg_id);
qinsoon's avatar
qinsoon committed
352 353 354 355
            ig.new_node(reg_id, &func.context);
        }

        for reg_id in cf.mc().get_inst_reg_uses(i) {
356
            let reg_id = c(reg_id);
qinsoon's avatar
qinsoon committed
357 358 359 360 361 362 363
            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
364 365 366
        let mut current_live =
            LinkedHashSet::from_vec(match cf.mc().get_ir_block_liveout(&block) {
                Some(liveout) => liveout.to_vec(),
367
                None => panic!("cannot find liveout for block {}", block)
qinsoon's avatar
qinsoon committed
368
            });
369 370 371 372 373 374 375 376 377
        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
378
            }
379 380 381 382 383 384
            trace!("current live: {}", s);
        };

        if TRACE_LIVENESS {
            trace!("---Block {}: live out---", block);
            print_set(&current_live);
qinsoon's avatar
qinsoon committed
385 386 387 388
        }

        let range = cf.mc().get_block_range(&block);
        if range.is_none() {
389
            warn!("Block {}: has no range (no instructions?)", block);
qinsoon's avatar
qinsoon committed
390 391
            continue;
        }
qinsoon's avatar
qinsoon committed
392 393
        trace_if!(
            TRACE_LIVENESS,
394
            "Block {}: range = {:?}",
qinsoon's avatar
qinsoon committed
395 396 397
            block,
            range.as_ref().unwrap()
        );
qinsoon's avatar
qinsoon committed
398 399 400

        // for every inst I in reverse order
        for i in range.unwrap().rev() {
401
            if TRACE_LIVENESS {
402
                trace!("Block {}: Inst{}", block, i);
qinsoon's avatar
qinsoon committed
403
                cf.mc().trace_inst(i);
404
                print_set(&current_live);
qinsoon's avatar
qinsoon committed
405 406
            }

qinsoon's avatar
qinsoon committed
407
            let src: Option<MuID> = {
qinsoon's avatar
qinsoon committed
408 409 410 411 412 413 414 415 416 417 418
                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 {
419 420 421
                            let src = c(src[0]);
                            let dst = c(dst[0]);
                            trace_if!(TRACE_LIVENESS, "add move {} -> {}", src, dst);
422
                            ig.add_move(src, dst);
qinsoon's avatar
qinsoon committed
423

424
                            Some(src)
qinsoon's avatar
qinsoon committed
425 426 427 428 429 430 431 432 433
                        } else {
                            None
                        }
                    }
                } else {
                    None
                }
            };

434
            let defines = cf.mc().get_inst_reg_defines(i);
435
            for d in defines.iter() {
436 437 438 439 440 441
                let d = c(*d);
                current_live.insert(d);
            }
            if TRACE_LIVENESS {
                trace!("after adding defines:");
                print_set(&current_live);
442 443 444
            }

            // for every definition D in I
445 446 447 448 449 450 451 452 453
            trace_if!(
                TRACE_LIVENESS,
                "for every defines in the instruction, add edge..."
            );
            trace_if!(
                TRACE_LIVENESS,
                "(move source {:?} does not interference with defines)",
                src
            );
454
            for d in defines {
455
                let d = c(d);
qinsoon's avatar
qinsoon committed
456 457 458 459
                // 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()) {
460 461
                        let from = d;
                        let to = *e;
qinsoon's avatar
qinsoon committed
462

463
                        if !ig.is_same_node(from, to) && ig.is_same_group(from, to) {
qinsoon's avatar
qinsoon committed
464
                            if !ig.is_colored(from) {
465
                                trace_if!(TRACE_LIVENESS, "add edge between {} and {}", d, *e);
466
                                ig.add_edge(from, to);
qinsoon's avatar
qinsoon committed
467 468
                            }
                            if !ig.is_colored(to) {
469
                                trace_if!(TRACE_LIVENESS, "add edge between {} and {}", *e, d);
470
                                ig.add_edge(to, from);
qinsoon's avatar
qinsoon committed
471 472 473 474 475 476 477 478
                            }
                        }
                    }
                }
            }

            // for every definition D in I
            for d in cf.mc().get_inst_reg_defines(i) {
479
                let d = c(d);
qinsoon's avatar
qinsoon committed
480 481 482
                // remove D from Current_Live
                current_live.remove(&d);
            }
483 484 485 486
            if TRACE_LIVENESS {
                trace!("removing defines from current live...");
                print_set(&current_live);
            }
qinsoon's avatar
qinsoon committed
487 488 489

            // for every use U in I
            for u in cf.mc().get_inst_reg_uses(i) {
490
                let u = c(u);
qinsoon's avatar
qinsoon committed
491 492 493
                // add U to Current_live
                current_live.insert(u);
            }
494
            if TRACE_LIVENESS {
495
                trace!("adding uses to current live...")
qinsoon's avatar
qinsoon committed
496 497 498 499 500 501 502 503 504 505 506
            }
        }
    }

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

qinsoon's avatar
qinsoon committed
509 510 511
    // build control flow graphs, treat a whole block as one node in the graph
    let cfg = build_cfg_nodes(cf);
    // do liveness analysis
512 513 514 515 516
    global_liveness_analysis(cfg, cf, func);

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

qinsoon's avatar
qinsoon committed
517
/// CFGBlockNode represents a basic block as a whole for global liveness analysis
518 519
#[derive(Clone, Debug)]
struct CFGBlockNode {
520
    block: MuName,
521 522
    pred: Vec<String>,
    succ: Vec<String>,
qinsoon's avatar
qinsoon committed
523
    uses: Vec<MuID>,
524
    defs: Vec<MuID>
525 526
}

qinsoon's avatar
qinsoon committed
527 528 529 530 531 532
/// builds a LinkedHashMap from basic block names to CFGBlockNode
/// We need to collect for each basic block:
/// * predecessors
/// * successors
/// * uses
/// * defs
533
fn build_cfg_nodes(cf: &mut CompiledFunction) -> LinkedHashMap<MuName, CFGBlockNode> {
534 535
    info!("---local liveness analysis---");
    let mc = cf.mc();
536
    let mut ret = LinkedHashMap::new();
537 538 539
    let all_blocks = mc.get_all_blocks();

    // create maps (start_inst -> name) and (end_inst -> name)
qinsoon's avatar
qinsoon committed
540 541
    // 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
542 543
        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
544 545 546
        for block in all_blocks.iter() {
            let range = match mc.get_block_range(block) {
                Some(range) => range,
547
                None => panic!("cannot find range for block {}", block)
qinsoon's avatar
qinsoon committed
548
            };
549

qinsoon's avatar
qinsoon committed
550 551 552 553 554
            // 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
555 556 557 558 559 560 561
                None => {
                    panic!(
                        "cannot find last instruction in block {}, \
                         this block contains no instruction?",
                        block
                    )
                }
qinsoon's avatar
qinsoon committed
562
            };
qinsoon's avatar
qinsoon committed
563 564 565 566 567 568 569
            trace_if!(
                TRACE_LIVENESS,
                "Block {}: start_inst={}, end_inst(inclusive)={}",
                block,
                first_inst,
                last_inst
            );
570

qinsoon's avatar
qinsoon committed
571 572 573 574 575 576
            start_inst_map.insert(first_inst, block);
            end_inst_map.insert(last_inst, block);
        }

        (start_inst_map, end_inst_map)
    };
577

qinsoon's avatar
qinsoon committed
578
    // collect info for each basic block
579
    for block in mc.get_all_blocks().iter() {
580
        trace_if!(TRACE_LIVENESS, "---block {}---", block);
581 582
        let range = mc.get_block_range(block).unwrap();
        let start_inst = range.start;
qinsoon's avatar
qinsoon committed
583
        let end = range.end;
584

qinsoon's avatar
qinsoon committed
585 586 587 588 589 590 591
        // 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
592
            let mut all_defined: LinkedHashSet<MuID> = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
593 594 595 596 597 598

            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 {
599
                    let reg = c(reg);
qinsoon's avatar
qinsoon committed
600 601 602 603
                    if !all_defined.contains(&reg) {
                        livein.push(reg);
                    }
                }
604

qinsoon's avatar
qinsoon committed
605 606
                let reg_defs = mc.get_inst_reg_defines(i);
                for reg in reg_defs {
607
                    let reg = c(reg);
qinsoon's avatar
qinsoon committed
608
                    all_defined.insert(reg);
609 610 611
                }
            }

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

qinsoon's avatar
qinsoon committed
614 615
            (livein, defs)
        };
616

qinsoon's avatar
qinsoon committed
617
        let preds: Vec<String> = {
618 619
            let mut ret = vec![];

qinsoon's avatar
qinsoon committed
620
            // predecessors of the first instruction is the predecessors of this block
621 622 623 624 625 626 627 628 629 630
            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
631
        let succs: Vec<String> = {
632 633
            let mut ret = vec![];

qinsoon's avatar
qinsoon committed
634
            // successors of the last instruction is the successors of this block
635
            for succ in mc.get_succs(mc.get_last_inst(end).unwrap()).into_iter() {
636 637 638 639 640 641 642 643 644 645 646 647 648 649
                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,
650
            defs: defs
651 652
        };

653
        trace_if!(TRACE_LIVENESS, "as CFGNode {:?}", node);
654 655 656 657 658 659
        ret.insert(block.clone(), node);
    }

    ret
}

qinsoon's avatar
qinsoon committed
660
/// global analysis, the iterative algorithm to compute livenss until livein/out reaches a fix point
qinsoon's avatar
qinsoon committed
661
fn global_liveness_analysis(
662
    blocks: LinkedHashMap<MuName, CFGBlockNode>,
qinsoon's avatar
qinsoon committed
663
    cf: &mut CompiledFunction,
664
    func: &MuFunctionVersion
qinsoon's avatar
qinsoon committed
665
) {
666 667
    info!("---global liveness analysis---");
    info!("{} blocks", blocks.len());
668 669

    // init live in and live out
670
    let mut livein: LinkedHashMap<MuName, LinkedHashSet<MuID>> = {
671
        let mut ret = LinkedHashMap::new();
672 673 674 675 676
        for name in blocks.keys() {
            ret.insert(name.clone(), LinkedHashSet::new());
        }
        ret
    };
677
    let mut liveout: LinkedHashMap<MuName, LinkedHashSet<MuID>> = {
678
        let mut ret = LinkedHashMap::new();
679 680 681 682 683 684
        for name in blocks.keys() {
            ret.insert(name.clone(), LinkedHashSet::new());
        }
        ret
    };

qinsoon's avatar
qinsoon committed
685
    // is the result changed in this iteration?
686
    let mut is_changed = true;
qinsoon's avatar
qinsoon committed
687
    // record iteration count
688 689 690
    let mut i = 0;

    while is_changed {
691
        trace_if!(TRACE_LIVENESS, "---iteration {}---", i);
692 693 694 695 696 697 698 699
        i += 1;

        // reset
        is_changed = false;

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

qinsoon's avatar
qinsoon committed
700
            // old livein/out
qinsoon's avatar
qinsoon committed
701
            let in_set_old = livein.get(node).unwrap().clone();
702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732
            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
733 734
            let n_changed = !in_set_old.equals(livein.get(node).unwrap()) ||
                !out_set_old.equals(liveout.get(node).unwrap());
735

qinsoon's avatar
qinsoon committed
736
            if TRACE_LIVENESS {
737 738 739 740 741 742 743 744 745 746 747
                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;
        }
    }

748 749
    info!("finished in {} iterations", i);

qinsoon's avatar
qinsoon committed
750
    // set live in and live out
751
    for block in blocks.keys() {
qinsoon's avatar
qinsoon committed
752 753 754 755 756 757 758
        let livein: Vec<MuID> = livein
            .get(block)
            .unwrap()
            .clone()
            .iter()
            .map(|x| *x)
            .collect();
759
        if TRACE_LIVENESS {
qinsoon's avatar
qinsoon committed
760 761 762 763
            let display_array: Vec<String> = livein
                .iter()
                .map(|x| func.context.get_temp_display(*x))
                .collect();
764 765 766 767
            trace!("livein  for block {}: {:?}", block, display_array);
        }
        cf.mc_mut().set_ir_block_livein(block, livein);

qinsoon's avatar
qinsoon committed
768 769 770 771 772 773 774
        let liveout: Vec<MuID> = liveout
            .get(block)
            .unwrap()
            .clone()
            .iter()
            .map(|x| *x)
            .collect();
775
        if TRACE_LIVENESS {
qinsoon's avatar
qinsoon committed
776 777 778 779
            let display_array: Vec<String> = liveout
                .iter()
                .map(|x| func.context.get_temp_display(*x))
                .collect();
780 781 782 783
            trace!("liveout for block {}: {:?}", block, display_array);
        }
        cf.mc_mut().set_ir_block_liveout(block, liveout);
    }
qinsoon's avatar
qinsoon committed
784
}