liveness.rs 24.2 KB
Newer Older
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1
// Copyright 2017 The Australian National University
qinsoon's avatar
qinsoon committed
2
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
3 4 5
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
qinsoon's avatar
qinsoon committed
6
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
7
//     http://www.apache.org/licenses/LICENSE-2.0
qinsoon's avatar
qinsoon committed
8
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
9 10 11 12 13 14
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

15 16
extern crate hprof;

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

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

qinsoon's avatar
qinsoon committed
36 37
/// 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
38
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
qinsoon's avatar
qinsoon committed
39
pub struct Move {
40 41 42 43 44 45 46 47 48 49 50
    pub from: MuID,
    pub to: MuID
}

#[inline(always)]
fn is_precolored(reg: MuID) -> bool {
    if reg < MACHINE_ID_END {
        true
    } else {
        false
    }
qinsoon's avatar
qinsoon committed
51
}
52

53 54
#[inline(always)]
fn is_usable(reg: MuID) -> bool {
qinsoon's avatar
qinsoon committed
55 56 57 58
    if backend::all_usable_regs()
        .iter()
        .any(|x| x.id() == backend::get_color_for_precolored(reg))
    {
59 60 61 62 63 64
        true
    } else {
        false
    }
}

qinsoon's avatar
qinsoon committed
65 66 67 68
/// InterferenceGraph represents the interference graph, including
/// * the graph
/// * all the nodes and its NodeIndex (a node is referred to by NodeIndex)
/// * all the moves
69
pub struct InterferenceGraph {
70 71 72 73 74
    nodes: LinkedHashMap<MuID, Node>,

    adj_set: LinkedHashSet<(MuID, MuID)>,
    adj_list: LinkedHashMap<MuID, LinkedHashSet<MuID>>,
    degree: LinkedHashMap<MuID, usize>,
75
    moves: LinkedHashSet<Move>
76 77 78
}

impl InterferenceGraph {
qinsoon's avatar
qinsoon committed
79
    /// creates a new graph
80
    fn new() -> InterferenceGraph {
qinsoon's avatar
qinsoon committed
81
        InterferenceGraph {
82 83 84
            adj_set: LinkedHashSet::new(),
            adj_list: LinkedHashMap::new(),
            degree: LinkedHashMap::new(),
85
            nodes: LinkedHashMap::new(),
86
            moves: LinkedHashSet::new()
qinsoon's avatar
qinsoon committed
87 88
        }
    }
qinsoon's avatar
qinsoon committed
89 90 91

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

        // if it is the first time, create the node
qinsoon's avatar
qinsoon committed
96
        if !self.nodes.contains_key(&reg_id) {
97
            let node = Node {
98
                temp: reg_id,
99
                color: None,
100
                group: backend::RegGroup::get_from_ty(entry.ty()),
101
                spill_cost: 0.0f32
qinsoon's avatar
qinsoon committed
102
            };
103

104 105 106
            self.nodes.insert(reg_id, node);
            self.adj_list.insert(reg_id, LinkedHashSet::new());
            self.degree.insert(reg_id, 0);
107
        }
qinsoon's avatar
qinsoon committed
108 109

        // get node
110
        let node_mut = self.nodes.get_mut(&reg_id).unwrap();
111
        // increase node spill cost
112
        node_mut.spill_cost += 1.0f32;
qinsoon's avatar
qinsoon committed
113

114
        reg_id
qinsoon's avatar
qinsoon committed
115
    }
qinsoon's avatar
qinsoon committed
116 117

    /// returns all the nodes in the graph
118 119
    pub fn nodes(&self) -> Vec<MuID> {
        self.nodes.keys().map(|x| *x).collect()
qinsoon's avatar
qinsoon committed
120
    }
qinsoon's avatar
qinsoon committed
121 122

    /// returns all the moves in the graph
123
    pub fn moves(&self) -> &LinkedHashSet<Move> {
qinsoon's avatar
qinsoon committed
124 125
        &self.moves
    }
qinsoon's avatar
qinsoon committed
126 127

    /// adds a move edge between two nodes
128
    fn add_move(&mut self, src: MuID, dst: MuID) {
qinsoon's avatar
qinsoon committed
129
        let src = {
130
            if is_precolored(src) {
qinsoon's avatar
qinsoon committed
131
                // get the color for the machine register, e.g. rax for eax/ax/al/ah
132
                backend::get_color_for_precolored(src)
qinsoon's avatar
qinsoon committed
133 134 135 136 137 138
            } else {
                src
            }
        };

        let dst = {
139 140
            if is_precolored(dst) {
                backend::get_color_for_precolored(dst)
qinsoon's avatar
qinsoon committed
141 142 143 144 145
            } else {
                dst
            }
        };

qinsoon's avatar
qinsoon committed
146
        self.moves.insert(Move { from: src, to: dst });
147
    }
qinsoon's avatar
qinsoon committed
148 149

    /// adds an interference edge between two nodes
150
    pub fn add_edge(&mut self, u: MuID, v: MuID) {
qinsoon's avatar
qinsoon committed
151 152
        // if one of the node is machine register, we also add
        // interference edge to its alias
qinsoon's avatar
qinsoon committed
153 154
        // e.g. if we have %a - %edi interfered,
        // we also add %a - %rdi interference
qinsoon's avatar
qinsoon committed
155

156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
        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
        };

176 177 178
        if !self.adj_set.contains(&(u, v)) && u != v {
            self.adj_set.insert((u, v));
            self.adj_set.insert((v, u));
qinsoon's avatar
qinsoon committed
179

180 181 182 183 184 185 186 187 188 189
            if !is_precolored(u) {
                self.adj_list.get_mut(&u).unwrap().insert(v);
                let degree = self.degree.get_mut(&u).unwrap();
                *degree = *degree + 1;
            }
            if !is_precolored(v) {
                self.adj_list.get_mut(&v).unwrap().insert(u);
                let degree = self.degree.get_mut(&v).unwrap();
                *degree = *degree + 1;
            }
qinsoon's avatar
qinsoon committed
190
        }
qinsoon's avatar
qinsoon committed
191 192
    }

qinsoon's avatar
qinsoon committed
193
    /// set color for a node
194 195
    pub fn color_node(&mut self, reg: MuID, color: MuID) {
        self.nodes.get_mut(&reg).unwrap().color = Some(color);
qinsoon's avatar
qinsoon committed
196
    }
qinsoon's avatar
qinsoon committed
197 198

    /// is a node colored yet?
199 200
    pub fn is_colored(&self, reg: MuID) -> bool {
        self.nodes.get(&reg).unwrap().color.is_some()
qinsoon's avatar
qinsoon committed
201
    }
qinsoon's avatar
qinsoon committed
202 203

    /// gets the color of a node
204 205
    pub fn get_color_of(&self, reg: MuID) -> Option<MuID> {
        self.nodes.get(&reg).unwrap().color
206
    }
qinsoon's avatar
qinsoon committed
207 208

    /// gets the reg group of a node
209 210
    pub fn get_group_of(&self, reg: MuID) -> backend::RegGroup {
        self.nodes.get(&reg).unwrap().group
qinsoon's avatar
qinsoon committed
211
    }
qinsoon's avatar
qinsoon committed
212 213

    /// gets the temporary of a node
214 215
    pub fn get_temp_of(&self, reg: MuID) -> MuID {
        self.nodes.get(&reg).unwrap().temp
216
    }
qinsoon's avatar
qinsoon committed
217 218

    /// gets the spill cost of a node
219 220
    pub fn get_spill_cost(&self, reg: MuID) -> f32 {
        self.nodes.get(&reg).unwrap().spill_cost
221
    }
qinsoon's avatar
qinsoon committed
222 223

    /// are two nodes the same node?
224 225
    fn is_same_node(&self, reg1: MuID, reg2: MuID) -> bool {
        reg1 == reg2
qinsoon's avatar
qinsoon committed
226
    }
227

qinsoon's avatar
qinsoon committed
228
    /// are two nodes from the same reg group?
229 230
    fn is_same_group(&self, reg1: MuID, reg2: MuID) -> bool {
        self.get_group_of(reg1) == self.get_group_of(reg2)
231
    }
qinsoon's avatar
qinsoon committed
232

233 234 235
    /// 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
236
    }
qinsoon's avatar
qinsoon committed
237

238 239
    pub fn is_in_adj_set(&self, u: MuID, v: MuID) -> bool {
        self.adj_set.contains(&(u, v))
240
    }
qinsoon's avatar
qinsoon committed
241 242

    /// gets degree of a node (number of edges from the node)
243 244 245 246 247 248
    pub fn get_degree_of(&self, reg: MuID) -> usize {
        *self.degree.get(&reg).unwrap()
    }

    pub fn set_degree_of(&mut self, reg: MuID, degree: usize) {
        *self.degree.get_mut(&reg).unwrap() = degree;
qinsoon's avatar
qinsoon committed
249
    }
qinsoon's avatar
qinsoon committed
250 251

    /// prints current graph for debugging (via trace log)
qinsoon's avatar
qinsoon committed
252
    pub fn print(&self, context: &FunctionContext) {
253 254 255
        use compiler::backend::reg_alloc::graph_coloring::petgraph::dot::Dot;
        use compiler::backend::reg_alloc::graph_coloring::petgraph::dot::Config;

256 257
        trace!("");
        trace!("Interference Graph");
258

259 260 261 262 263 264 265 266 267 268 269 270 271
        trace!("nodes: ");
        for n in self.nodes.values() {
            trace!("{:?}", n);
        }

        trace!("edges: ");

        for id in self.nodes.keys() {
            trace!("edges for {} ({}): ", id, self.degree.get(id).unwrap());
            for neighbour in self.get_adj_list(*id).iter() {
                trace!("{}", neighbour)
            }
        }
272
    }
qinsoon's avatar
qinsoon committed
273 274
}

qinsoon's avatar
qinsoon committed
275 276 277 278
/// 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
279 280 281 282
/// reference: Tailoring Graph-coloring Register Allocation For Runtime Compilation
/// - CGO'06, Figure 4
pub fn build_interference_graph_chaitin_briggs(
    cf: &mut CompiledFunction,
283
    func: &MuFunctionVersion
qinsoon's avatar
qinsoon committed
284
) -> InterferenceGraph {
qinsoon's avatar
qinsoon committed
285 286 287 288 289 290 291 292
    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();
293

qinsoon's avatar
qinsoon committed
294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316
    // precolor machine register nodes
    for reg in backend::all_regs().values() {
        let reg_id = reg.extract_ssa_id().unwrap();
        let node = ig.new_node(reg_id, &func.context);
        let precolor = backend::get_color_for_precolored(reg_id);

        ig.color_node(node, precolor);
    }

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

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

    // for each basic block, insert interference edge while reversely traversing instructions
    for block in cf.mc().get_all_blocks() {
        // Current_Live(B) = LiveOut(B)
qinsoon's avatar
qinsoon committed
317 318 319
        let mut current_live =
            LinkedHashSet::from_vec(match cf.mc().get_ir_block_liveout(&block) {
                Some(liveout) => liveout.to_vec(),
320
                None => panic!("cannot find liveout for block {}", block)
qinsoon's avatar
qinsoon committed
321
            });
qinsoon's avatar
qinsoon committed
322 323 324 325 326 327 328 329 330 331 332 333
        if TRACE_LIVENESS {
            trace!("Block{}: live out", block);
            for ele in current_live.iter() {
                trace!("{}", func.context.get_temp_display(*ele));
            }
        }

        let range = cf.mc().get_block_range(&block);
        if range.is_none() {
            warn!("Block{}: has no range (no instructions?)", block);
            continue;
        }
qinsoon's avatar
qinsoon committed
334 335 336 337 338 339
        trace_if!(
            TRACE_LIVENESS,
            "Block{}: range = {:?}",
            block,
            range.as_ref().unwrap()
        );
qinsoon's avatar
qinsoon committed
340 341 342

        // for every inst I in reverse order
        for i in range.unwrap().rev() {
343
            if TRACE_LIVENESS {
qinsoon's avatar
qinsoon committed
344 345 346 347 348 349 350 351
                trace!("Block{}: Inst{}", block, i);
                cf.mc().trace_inst(i);
                trace!("current live: ");
                for ele in current_live.iter() {
                    trace!("{}", func.context.get_temp_display(*ele));
                }
            }

qinsoon's avatar
qinsoon committed
352
            let src: Option<MuID> = {
qinsoon's avatar
qinsoon committed
353 354 355 356 357 358 359 360 361 362 363
                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 {
364 365
                            let src = src[0];
                            let dst = dst[0];
qinsoon's avatar
qinsoon committed
366 367 368
                            trace_if!(
                                TRACE_LIVENESS,
                                "add move between {} and {}",
369 370
                                func.context.get_temp_display(src),
                                func.context.get_temp_display(dst)
qinsoon's avatar
qinsoon committed
371
                            );
372
                            ig.add_move(src, dst);
qinsoon's avatar
qinsoon committed
373

374
                            Some(src)
qinsoon's avatar
qinsoon committed
375 376 377 378 379 380 381 382
                        } else {
                            None
                        }
                    }
                } else {
                    None
                }
            };
383
            trace_if!(TRACE_LIVENESS, "Block{}: Inst{}: src={:?}", block, i, src);
qinsoon's avatar
qinsoon committed
384

385
            let defines = cf.mc().get_inst_reg_defines(i);
386 387 388 389 390 391
            for d in defines.iter() {
                current_live.insert(*d);
            }

            // for every definition D in I
            for d in defines {
qinsoon's avatar
qinsoon committed
392 393 394 395 396 397 398
                trace_if!(
                    TRACE_LIVENESS,
                    "Block{}: Inst{}: for definition {}",
                    block,
                    i,
                    func.context.get_temp_display(d)
                );
qinsoon's avatar
qinsoon committed
399 400 401
                // add an interference from D to every element E in Current_Live - {D}
                // creating nodes if necessary
                for e in current_live.iter() {
qinsoon's avatar
qinsoon committed
402 403 404 405 406 407 408
                    trace_if!(
                        TRACE_LIVENESS,
                        "Block{}: Inst{}: for each live {}",
                        block,
                        i,
                        func.context.get_temp_display(*e)
                    );
qinsoon's avatar
qinsoon committed
409
                    if src.is_none() || (src.is_some() && *e != src.unwrap()) {
410 411
                        let from = d;
                        let to = *e;
qinsoon's avatar
qinsoon committed
412

413
                        if !ig.is_same_node(from, to) && ig.is_same_group(from, to) {
qinsoon's avatar
qinsoon committed
414
                            if !ig.is_colored(from) {
qinsoon's avatar
qinsoon committed
415 416 417 418 419
                                trace_if!(
                                    TRACE_LIVENESS,
                                    "Block{}: Inst{}: add interference between {} and {}",
                                    block,
                                    i,
420
                                    func.context.get_temp_display(d),
qinsoon's avatar
qinsoon committed
421 422
                                    func.context.get_temp_display(*e)
                                );
423
                                ig.add_edge(from, to);
qinsoon's avatar
qinsoon committed
424 425
                            }
                            if !ig.is_colored(to) {
qinsoon's avatar
qinsoon committed
426 427 428 429 430
                                trace_if!(
                                    TRACE_LIVENESS,
                                    "Block{}: Inst{}: add interference between {} and {}",
                                    block,
                                    i,
431
                                    func.context.get_temp_display(*e),
qinsoon's avatar
qinsoon committed
432 433
                                    func.context.get_temp_display(d)
                                );
434
                                ig.add_edge(to, from);
qinsoon's avatar
qinsoon committed
435 436 437 438 439 440 441 442
                            }
                        }
                    }
                }
            }

            // for every definition D in I
            for d in cf.mc().get_inst_reg_defines(i) {
qinsoon's avatar
qinsoon committed
443 444 445 446 447 448 449
                trace_if!(
                    TRACE_LIVENESS,
                    "Block{}: Inst{}: remove define {} from current_live",
                    block,
                    i,
                    func.context.get_temp_display(d)
                );
qinsoon's avatar
qinsoon committed
450 451 452 453 454 455
                // remove D from Current_Live
                current_live.remove(&d);
            }

            // for every use U in I
            for u in cf.mc().get_inst_reg_uses(i) {
qinsoon's avatar
qinsoon committed
456 457 458 459 460 461 462
                trace_if!(
                    TRACE_LIVENESS,
                    "Block{}: Inst{}: add use {} to current_live",
                    block,
                    i,
                    func.context.get_temp_display(u)
                );
qinsoon's avatar
qinsoon committed
463 464 465 466
                // add U to Current_live
                current_live.insert(u);
            }

467 468
            if TRACE_LIVENESS {
                trace!("Block{}: Inst{}: done. current_live:", block, i);
qinsoon's avatar
qinsoon committed
469 470 471 472 473 474 475 476 477 478 479 480 481 482
                for ele in current_live.iter() {
                    trace!("{}", func.context.get_temp_display(*ele));
                }
            }
        }
    }

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

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

qinsoon's avatar
qinsoon committed
485 486 487
    // build control flow graphs, treat a whole block as one node in the graph
    let cfg = build_cfg_nodes(cf);
    // do liveness analysis
488 489 490 491 492
    global_liveness_analysis(cfg, cf, func);

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

qinsoon's avatar
qinsoon committed
493
/// CFGBlockNode represents a basic block as a whole for global liveness analysis
494 495
#[derive(Clone, Debug)]
struct CFGBlockNode {
496
    block: MuName,
497 498
    pred: Vec<String>,
    succ: Vec<String>,
qinsoon's avatar
qinsoon committed
499
    uses: Vec<MuID>,
500
    defs: Vec<MuID>
501 502
}

qinsoon's avatar
qinsoon committed
503 504 505 506 507 508
/// builds a LinkedHashMap from basic block names to CFGBlockNode
/// We need to collect for each basic block:
/// * predecessors
/// * successors
/// * uses
/// * defs
509
fn build_cfg_nodes(cf: &mut CompiledFunction) -> LinkedHashMap<MuName, CFGBlockNode> {
510 511
    info!("---local liveness analysis---");
    let mc = cf.mc();
512
    let mut ret = LinkedHashMap::new();
513 514 515
    let all_blocks = mc.get_all_blocks();

    // create maps (start_inst -> name) and (end_inst -> name)
qinsoon's avatar
qinsoon committed
516 517
    // 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
518 519
        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
520 521 522
        for block in all_blocks.iter() {
            let range = match mc.get_block_range(block) {
                Some(range) => range,
523
                None => panic!("cannot find range for block {}", block)
qinsoon's avatar
qinsoon committed
524
            };
525

qinsoon's avatar
qinsoon committed
526 527 528 529 530
            // 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
531 532 533 534 535 536 537
                None => {
                    panic!(
                        "cannot find last instruction in block {}, \
                         this block contains no instruction?",
                        block
                    )
                }
qinsoon's avatar
qinsoon committed
538
            };
qinsoon's avatar
qinsoon committed
539 540 541 542 543 544 545
            trace_if!(
                TRACE_LIVENESS,
                "Block {}: start_inst={}, end_inst(inclusive)={}",
                block,
                first_inst,
                last_inst
            );
546

qinsoon's avatar
qinsoon committed
547 548 549 550 551 552
            start_inst_map.insert(first_inst, block);
            end_inst_map.insert(last_inst, block);
        }

        (start_inst_map, end_inst_map)
    };
553

qinsoon's avatar
qinsoon committed
554
    // collect info for each basic block
555
    for block in mc.get_all_blocks().iter() {
556
        trace_if!(TRACE_LIVENESS, "---block {}---", block);
557 558
        let range = mc.get_block_range(block).unwrap();
        let start_inst = range.start;
qinsoon's avatar
qinsoon committed
559
        let end = range.end;
560

qinsoon's avatar
qinsoon committed
561 562 563 564 565 566 567
        // 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
568
            let mut all_defined: LinkedHashSet<MuID> = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
569 570 571 572 573 574 575 576 577 578

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

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

qinsoon's avatar
qinsoon committed
580 581 582
                let reg_defs = mc.get_inst_reg_defines(i);
                for reg in reg_defs {
                    all_defined.insert(reg);
583 584 585
                }
            }

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

qinsoon's avatar
qinsoon committed
588 589
            (livein, defs)
        };
590

qinsoon's avatar
qinsoon committed
591
        let preds: Vec<String> = {
592 593
            let mut ret = vec![];

qinsoon's avatar
qinsoon committed
594
            // predecessors of the first instruction is the predecessors of this block
595 596 597 598 599 600 601 602 603 604
            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
605
        let succs: Vec<String> = {
606 607
            let mut ret = vec![];

qinsoon's avatar
qinsoon committed
608
            // successors of the last instruction is the successors of this block
609
            for succ in mc.get_succs(mc.get_last_inst(end).unwrap()).into_iter() {
610 611 612 613 614 615 616 617 618 619 620 621 622 623
                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,
624
            defs: defs
625 626
        };

627
        trace_if!(TRACE_LIVENESS, "as CFGNode {:?}", node);
628 629 630 631 632 633
        ret.insert(block.clone(), node);
    }

    ret
}

qinsoon's avatar
qinsoon committed
634
/// global analysis, the iterative algorithm to compute livenss until livein/out reaches a fix point
qinsoon's avatar
qinsoon committed
635
fn global_liveness_analysis(
636
    blocks: LinkedHashMap<MuName, CFGBlockNode>,
qinsoon's avatar
qinsoon committed
637
    cf: &mut CompiledFunction,
638
    func: &MuFunctionVersion
qinsoon's avatar
qinsoon committed
639
) {
640 641
    info!("---global liveness analysis---");
    info!("{} blocks", blocks.len());
642 643

    // init live in and live out
644
    let mut livein: LinkedHashMap<MuName, LinkedHashSet<MuID>> = {
645
        let mut ret = LinkedHashMap::new();
646 647 648 649 650
        for name in blocks.keys() {
            ret.insert(name.clone(), LinkedHashSet::new());
        }
        ret
    };
651
    let mut liveout: LinkedHashMap<MuName, LinkedHashSet<MuID>> = {
652
        let mut ret = LinkedHashMap::new();
653 654 655 656 657 658
        for name in blocks.keys() {
            ret.insert(name.clone(), LinkedHashSet::new());
        }
        ret
    };

qinsoon's avatar
qinsoon committed
659
    // is the result changed in this iteration?
660
    let mut is_changed = true;
qinsoon's avatar
qinsoon committed
661
    // record iteration count
662 663 664
    let mut i = 0;

    while is_changed {
665
        trace_if!(TRACE_LIVENESS, "---iteration {}---", i);
666 667 668 669 670 671 672 673
        i += 1;

        // reset
        is_changed = false;

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

qinsoon's avatar
qinsoon committed
674
            // old livein/out
qinsoon's avatar
qinsoon committed
675
            let in_set_old = livein.get(node).unwrap().clone();
676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706
            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
707 708
            let n_changed = !in_set_old.equals(livein.get(node).unwrap()) ||
                !out_set_old.equals(liveout.get(node).unwrap());
709

qinsoon's avatar
qinsoon committed
710
            if TRACE_LIVENESS {
711 712 713 714 715 716 717 718 719 720 721
                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;
        }
    }

722 723
    info!("finished in {} iterations", i);

qinsoon's avatar
qinsoon committed
724
    // set live in and live out
725
    for block in blocks.keys() {
qinsoon's avatar
qinsoon committed
726 727 728 729 730 731 732
        let livein: Vec<MuID> = livein
            .get(block)
            .unwrap()
            .clone()
            .iter()
            .map(|x| *x)
            .collect();
733
        if TRACE_LIVENESS {
qinsoon's avatar
qinsoon committed
734 735 736 737
            let display_array: Vec<String> = livein
                .iter()
                .map(|x| func.context.get_temp_display(*x))
                .collect();
738 739 740 741
            trace!("livein  for block {}: {:?}", block, display_array);
        }
        cf.mc_mut().set_ir_block_livein(block, livein);

qinsoon's avatar
qinsoon committed
742 743 744 745 746 747 748
        let liveout: Vec<MuID> = liveout
            .get(block)
            .unwrap()
            .clone()
            .iter()
            .map(|x| *x)
            .collect();
749
        if TRACE_LIVENESS {
qinsoon's avatar
qinsoon committed
750 751 752 753
            let display_array: Vec<String> = liveout
                .iter()
                .map(|x| func.context.get_temp_display(*x))
                .collect();
754 755 756 757
            trace!("liveout for block {}: {:?}", block, display_array);
        }
        cf.mc_mut().set_ir_block_liveout(block, liveout);
    }
qinsoon's avatar
qinsoon committed
758
}