liveness.rs 24.5 KB
Newer Older
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14
// Copyright 2017 The Australian National University
// 
// 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
// 
//     http://www.apache.org/licenses/LICENSE-2.0
// 
// 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

23 24 25
use compiler::backend::reg_alloc::graph_coloring::petgraph;
use compiler::backend::reg_alloc::graph_coloring::petgraph::Graph;
use compiler::backend::reg_alloc::graph_coloring::petgraph::graph::NodeIndex;
qinsoon's avatar
qinsoon committed
26

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

qinsoon's avatar
qinsoon committed
40 41
/// 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
42
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
43
pub struct Move{pub from: NodeIndex, pub to: NodeIndex}
44

qinsoon's avatar
qinsoon committed
45 46 47 48
/// InterferenceGraph represents the interference graph, including
/// * the graph
/// * all the nodes and its NodeIndex (a node is referred to by NodeIndex)
/// * all the moves
49
pub struct InterferenceGraph {
qinsoon's avatar
qinsoon committed
50
    /// the internal graph
51
    graph: Graph<GraphNode, (), petgraph::Undirected>,
qinsoon's avatar
qinsoon committed
52 53
    /// a map of all nodes (from temp ID to node index)
    /// node index is how nodes are referred to with pet_graph
54
    nodes: LinkedHashMap<MuID, NodeIndex>,
qinsoon's avatar
qinsoon committed
55
    /// a set of all moves
56
    moves: LinkedHashSet<Move>,
57 58 59
}

impl InterferenceGraph {
qinsoon's avatar
qinsoon committed
60
    /// creates a new graph
61
    fn new() -> InterferenceGraph {
qinsoon's avatar
qinsoon committed
62
        InterferenceGraph {
63
            graph: Graph::new_undirected(),
64 65
            nodes: LinkedHashMap::new(),
            moves: LinkedHashSet::new()
qinsoon's avatar
qinsoon committed
66 67
        }
    }
qinsoon's avatar
qinsoon committed
68 69 70

    /// 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
71
    fn new_node(&mut self, reg_id: MuID, context: &FunctionContext) -> NodeIndex {
qinsoon's avatar
qinsoon committed
72
        let entry = context.get_value(reg_id).unwrap();
qinsoon's avatar
qinsoon committed
73 74

        // if it is the first time, create the node
qinsoon's avatar
qinsoon committed
75
        if !self.nodes.contains_key(&reg_id) {
76
            let node = GraphNode {
77
                temp: reg_id,
78
                color: None,
79
                group: backend::RegGroup::get_from_ty(entry.ty()),
80
                spill_cost: 0.0f32
qinsoon's avatar
qinsoon committed
81
            };
82

qinsoon's avatar
qinsoon committed
83
            // add to the graph
84
            let index = self.graph.add_node(node);
qinsoon's avatar
qinsoon committed
85
            // save index
86 87
            self.nodes.insert(reg_id, index);
        }
qinsoon's avatar
qinsoon committed
88 89

        // get the node index
90
        let node_index = *self.nodes.get(&reg_id).unwrap();
qinsoon's avatar
qinsoon committed
91
        // get node
92
        let node_mut = self.graph.node_weight_mut(node_index).unwrap();
93
        // increase node spill cost
94
        node_mut.spill_cost += 1.0f32;
95
        
96
        node_index
qinsoon's avatar
qinsoon committed
97
    }
qinsoon's avatar
qinsoon committed
98 99

    /// returns the node index for a temp
100
    pub fn get_node(&self, reg: MuID) -> NodeIndex {
qinsoon's avatar
qinsoon committed
101
        match self.nodes.get(&reg) {
qinsoon's avatar
qinsoon committed
102
            Some(index) => *index,
qinsoon's avatar
qinsoon committed
103
            None => panic!("do not have a node for {}", reg)
qinsoon's avatar
qinsoon committed
104 105
        }
    }
qinsoon's avatar
qinsoon committed
106 107

    /// returns all the nodes in the graph
108
    pub fn nodes(&self) -> Vec<NodeIndex> {
qinsoon's avatar
qinsoon committed
109
        let mut ret = vec![];
110 111
        for index in self.nodes.values() {
            ret.push(*index);
qinsoon's avatar
qinsoon committed
112 113 114
        }
        ret
    }
qinsoon's avatar
qinsoon committed
115 116

    /// returns all the moves in the graph
117
    pub fn moves(&self) -> &LinkedHashSet<Move> {
qinsoon's avatar
qinsoon committed
118 119
        &self.moves
    }
qinsoon's avatar
qinsoon committed
120 121

    /// adds a move edge between two nodes
122
    fn add_move(&mut self, src: NodeIndex, dst: NodeIndex) {
qinsoon's avatar
qinsoon committed
123 124 125
        let src = {
            let temp_src = self.get_temp_of(src);
            if temp_src < MACHINE_ID_END {
qinsoon's avatar
qinsoon committed
126 127
                // get the color for the machine register, e.g. rax for eax/ax/al/ah
                let alias = backend::get_color_for_precolored(temp_src);
qinsoon's avatar
qinsoon committed
128 129 130 131 132 133 134 135 136
                self.get_node(alias)
            } else {
                src
            }
        };

        let dst = {
            let temp_dst = self.get_temp_of(dst);
            if temp_dst < MACHINE_ID_END {
qinsoon's avatar
qinsoon committed
137
                let alias = backend::get_color_for_precolored(temp_dst);
qinsoon's avatar
qinsoon committed
138 139 140 141 142 143
                self.get_node(alias)
            } else {
                dst
            }
        };

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

    /// adds an interference edge between two nodes
148
    pub fn add_interference_edge(&mut self, from: NodeIndex, to: NodeIndex) {
qinsoon's avatar
qinsoon committed
149
        // adds edge to the internal graph
150
        self.graph.update_edge(from, to, ());
qinsoon's avatar
qinsoon committed
151 152 153

        // if one of the node is machine register, we also add
        // interference edge to its alias
qinsoon's avatar
qinsoon committed
154 155
        // e.g. if we have %a - %edi interfered,
        // we also add %a - %rdi interference
qinsoon's avatar
qinsoon committed
156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176

        let from_tmp = self.graph.node_weight(from).unwrap().temp;
        let to_tmp   = self.graph.node_weight(to).unwrap().temp;

        if from_tmp < MACHINE_ID_END || to_tmp < MACHINE_ID_END {
            let from_tmp = if from_tmp < MACHINE_ID_END {
                backend::get_color_for_precolored(from_tmp)
            } else {
                from_tmp
            };

            let to_tmp = if to_tmp < MACHINE_ID_END {
                backend::get_color_for_precolored(to_tmp)
            } else {
                to_tmp
            };

            let from_tmp_node = self.get_node(from_tmp);
            let to_tmp_node   = self.get_node(to_tmp);
            self.graph.update_edge(from_tmp_node, to_tmp_node, ());
        }
qinsoon's avatar
qinsoon committed
177 178
    }

qinsoon's avatar
qinsoon committed
179 180
    /// is two nodes interfered?
    pub fn is_interfered_with(&self, node1: NodeIndex, node2: NodeIndex) -> bool {
181 182
        let edge = self.graph.find_edge(node1, node2);
        edge.is_some()
qinsoon's avatar
qinsoon committed
183
    }
qinsoon's avatar
qinsoon committed
184 185

    /// set color for a node
186 187
    pub fn color_node(&mut self, node: NodeIndex, color: MuID) {
        self.graph.node_weight_mut(node).unwrap().color = Some(color);
qinsoon's avatar
qinsoon committed
188
    }
qinsoon's avatar
qinsoon committed
189 190

    /// is a node colored yet?
191 192
    pub fn is_colored(&self, node: NodeIndex) -> bool {
        self.graph.node_weight(node).unwrap().color.is_some()
qinsoon's avatar
qinsoon committed
193
    }
qinsoon's avatar
qinsoon committed
194 195

    /// gets the color of a node
196 197
    pub fn get_color_of(&self, node: NodeIndex) -> Option<MuID> {
        self.graph.node_weight(node).unwrap().color
198
    }
qinsoon's avatar
qinsoon committed
199 200

    /// gets the reg group of a node
201 202
    pub fn get_group_of(&self, node: NodeIndex) -> backend::RegGroup {
        self.graph.node_weight(node).unwrap().group
qinsoon's avatar
qinsoon committed
203
    }
qinsoon's avatar
qinsoon committed
204 205

    /// gets the temporary of a node
206 207
    pub fn get_temp_of(&self, node: NodeIndex) -> MuID {
        self.graph.node_weight(node).unwrap().temp
208
    }
qinsoon's avatar
qinsoon committed
209 210

    /// gets the spill cost of a node
211 212
    pub fn get_spill_cost(&self, node: NodeIndex) -> f32 {
        self.graph.node_weight(node).unwrap().spill_cost
213
    }
qinsoon's avatar
qinsoon committed
214 215

    /// are two nodes the same node?
216
    fn is_same_node(&self, node1: NodeIndex, node2: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
217
        node1 == node2
qinsoon's avatar
qinsoon committed
218
    }
219

qinsoon's avatar
qinsoon committed
220
    /// are two nodes from the same reg group?
221 222 223 224 225 226
    fn is_same_group(&self, node1: NodeIndex, node2: NodeIndex) -> bool {
        let node1 = self.graph.node_weight(node1).unwrap();
        let node2 = self.graph.node_weight(node2).unwrap();

        node1.group == node2.group
    }
qinsoon's avatar
qinsoon committed
227 228

    /// are two nodes adjacent?
229
    pub fn is_adj(&self, from: NodeIndex, to: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
230
        self.is_interfered_with(from, to)
qinsoon's avatar
qinsoon committed
231
    }
qinsoon's avatar
qinsoon committed
232 233 234

    /// gets edges from a node
    pub fn get_edges_of(&self, node: NodeIndex) -> Vec<NodeIndex> {
235
        self.graph.neighbors(node).collect()
236
    }
qinsoon's avatar
qinsoon committed
237 238 239 240

    /// gets degree of a node (number of edges from the node)
    pub fn get_degree_of(&self, node: NodeIndex) -> usize {
        self.get_edges_of(node).len()
qinsoon's avatar
qinsoon committed
241
    }
qinsoon's avatar
qinsoon committed
242 243

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

248 249
        trace!("");
        trace!("Interference Graph");
250

251
        trace!("nodes:");
qinsoon's avatar
qinsoon committed
252
        for id in self.nodes.keys() {
qinsoon's avatar
qinsoon committed
253
            let val = context.get_value(*id).unwrap().value();
254
            trace!("Reg {} -> {:?}", val, self.nodes.get(&id).unwrap());
qinsoon's avatar
qinsoon committed
255 256
        }

257
        trace!("moves:");
258
        for mov in self.moves.iter() {
259
            trace!("Move {:?} -> {:?}", mov.from, mov.to);
260
        }
qinsoon's avatar
qinsoon committed
261

262 263 264
        trace!("graph:");
        trace!("\n\n{:?}\n", Dot::with_config(&self.graph, &[Config::EdgeNoLabel]));
        trace!("");
265
    }
qinsoon's avatar
qinsoon committed
266 267
}

qinsoon's avatar
qinsoon committed
268 269 270 271 272 273 274 275 276 277 278 279 280 281
/// prints trace during building liveness for debugging?
const TRACE_LIVENESS: bool = false;

/// builds interference graph based on chaitin briggs algorithms
/// (reference: Tailoring Graph-coloring Register Allocation For Runtime Compilation - CGO'06, Figure 4)
pub fn build_interference_graph_chaitin_briggs(cf: &mut CompiledFunction, func: &MuFunctionVersion) -> InterferenceGraph {
    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();
282

qinsoon's avatar
qinsoon committed
283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321
    // 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)
        let mut current_live = LinkedHashSet::from_vec(match cf.mc().get_ir_block_liveout(&block) {
            Some(liveout) => liveout.to_vec(),
            None => panic!("cannot find liveout for block {}", block)
        });
        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;
        }
322
        trace_if!(TRACE_LIVENESS, "Block{}: range = {:?}", block, range.as_ref().unwrap());
qinsoon's avatar
qinsoon committed
323 324 325

        // for every inst I in reverse order
        for i in range.unwrap().rev() {
326
            if TRACE_LIVENESS {
qinsoon's avatar
qinsoon committed
327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348
                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));
                }
            }

            let src : Option<MuID> = {
                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 {
                            let node1 = ig.get_node(src[0]);
                            let node2 = ig.get_node(dst[0]);
349
                            trace_if!(TRACE_LIVENESS, "add move between {} and {}",
qinsoon's avatar
qinsoon committed
350 351 352 353 354 355 356 357 358 359 360 361 362
                            func.context.get_temp_display(src[0]),
                            func.context.get_temp_display(dst[0]));
                            ig.add_move(node1, node2);

                            Some(src[0])
                        } else {
                            None
                        }
                    }
                } else {
                    None
                }
            };
363
            trace_if!(TRACE_LIVENESS, "Block{}: Inst{}: src={:?}", block, i, src);
qinsoon's avatar
qinsoon committed
364 365

            // for every definition D in I
366 367
            let defines = cf.mc().get_inst_reg_defines(i);
            for d in defines.clone() {
368 369
                trace_if!(TRACE_LIVENESS, "Block{}: Inst{}: for definition {}",
                    block, i, func.context.get_temp_display(d));
qinsoon's avatar
qinsoon committed
370 371 372
                // add an interference from D to every element E in Current_Live - {D}
                // creating nodes if necessary
                for e in current_live.iter() {
373 374
                    trace_if!(TRACE_LIVENESS, "Block{}: Inst{}: for each live {}",
                        block, i, func.context.get_temp_display(*e));
qinsoon's avatar
qinsoon committed
375 376 377 378 379 380
                    if src.is_none() || (src.is_some() && *e != src.unwrap()) {
                        let from = ig.get_node(d);
                        let to = ig.get_node(*e);

                        if !ig.is_same_node(from, to) &&ig.is_same_group(from, to) && !ig.is_adj(from, to) {
                            if !ig.is_colored(from) {
381 382 383 384
                                trace_if!(TRACE_LIVENESS, "Block{}: Inst{}: add interference between {} and {}",
                                    block, i,
                                    func.context.get_temp_display(d),
                                    func.context.get_temp_display(*e));
qinsoon's avatar
qinsoon committed
385 386 387
                                ig.add_interference_edge(from, to);
                            }
                            if !ig.is_colored(to) {
388 389 390 391
                                trace_if!(TRACE_LIVENESS, "Block{}: Inst{}: add interference between {} and {}",
                                    block, i,
                                    func.context.get_temp_display(*e),
                                    func.context.get_temp_display(d));
qinsoon's avatar
qinsoon committed
392 393 394 395 396
                                ig.add_interference_edge(to, from);
                            }
                        }
                    }
                }
397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412

                // D also interferes with other definition D_ in I
                for d_ in defines.iter() {
                    let node1 = ig.get_node(d);
                    let node2 = ig.get_node(*d_);

                    // if D and D_ are not the same node, not already interfered, and in the same reg group
                    // we add an intereference edge between them
                    if !ig.is_same_node(node1, node2) && ig.is_same_group(node1, node2) && !ig.is_adj(node1, node2){
                        trace_if!(TRACE_LIVENESS, "Block{}: Inst{}: add intereference between {} and {}",
                            block, i,
                            func.context.get_temp_display(d),
                            func.context.get_temp_display(*d_));
                        ig.add_interference_edge(node1, node2);
                    }
                }
qinsoon's avatar
qinsoon committed
413 414 415 416
            }

            // for every definition D in I
            for d in cf.mc().get_inst_reg_defines(i) {
417 418 419
                trace_if!(TRACE_LIVENESS, "Block{}: Inst{}: remove define {} from current_live",
                    block, i,
                    func.context.get_temp_display(d));
qinsoon's avatar
qinsoon committed
420 421 422 423 424 425
                // 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) {
426 427 428
                trace_if!(TRACE_LIVENESS, "Block{}: Inst{}: add use {} to current_live",
                    block, i,
                    func.context.get_temp_display(u));
qinsoon's avatar
qinsoon committed
429 430 431 432
                // add U to Current_live
                current_live.insert(u);
            }

433 434
            if TRACE_LIVENESS {
                trace!("Block{}: Inst{}: done. current_live:", block, i);
qinsoon's avatar
qinsoon committed
435 436 437 438 439 440 441 442 443 444 445 446 447 448
                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
449
    info!("---start building live set---");
450

qinsoon's avatar
qinsoon committed
451 452 453
    // build control flow graphs, treat a whole block as one node in the graph
    let cfg = build_cfg_nodes(cf);
    // do liveness analysis
454 455 456 457 458
    global_liveness_analysis(cfg, cf, func);

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

qinsoon's avatar
qinsoon committed
459
/// CFGBlockNode represents a basic block as a whole for global liveness analysis
460 461 462 463 464 465 466 467 468
#[derive(Clone, Debug)]
struct CFGBlockNode {
    block: String,
    pred: Vec<String>,
    succ: Vec<String>,
    uses:  Vec<MuID>,
    defs: Vec<MuID>
}

qinsoon's avatar
qinsoon committed
469 470 471 472 473 474 475
/// builds a LinkedHashMap from basic block names to CFGBlockNode
/// We need to collect for each basic block:
/// * predecessors
/// * successors
/// * uses
/// * defs
fn build_cfg_nodes(cf: &mut CompiledFunction) -> LinkedHashMap<String, CFGBlockNode> {
476 477
    info!("---local liveness analysis---");
    let mc = cf.mc();
478
    let mut ret = LinkedHashMap::new();
479 480 481
    let all_blocks = mc.get_all_blocks();

    // create maps (start_inst -> name) and (end_inst -> name)
qinsoon's avatar
qinsoon committed
482 483 484 485 486 487 488 489 490
    // we will use it to find basic blocks when given a inst index
    let (start_inst_map, end_inst_map) = {
        let mut start_inst_map : LinkedHashMap<usize, &str> = LinkedHashMap::new();
        let mut end_inst_map   : LinkedHashMap<usize, &str> = LinkedHashMap::new();
        for block in all_blocks.iter() {
            let range = match mc.get_block_range(block) {
                Some(range) => range,
                None => panic!("cannot find range for block {}", block)
            };
491

qinsoon's avatar
qinsoon committed
492 493 494 495 496 497 498
            // 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,
                None => panic!("cannot find last instruction in block {}, this block contains no instruction?", block)
            };
499
            trace_if!(TRACE_LIVENESS, "Block {}: start_inst={}, end_inst(inclusive)={}", block, first_inst, last_inst);
500

qinsoon's avatar
qinsoon committed
501 502 503 504 505 506
            start_inst_map.insert(first_inst, block);
            end_inst_map.insert(last_inst, block);
        }

        (start_inst_map, end_inst_map)
    };
507

qinsoon's avatar
qinsoon committed
508
    // collect info for each basic block
509
    for block in mc.get_all_blocks().iter() {
510
        trace_if!(TRACE_LIVENESS, "---block {}---", block);
511 512 513 514
        let range = mc.get_block_range(block).unwrap();
        let start_inst = range.start;
        let end        = range.end;

qinsoon's avatar
qinsoon committed
515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532
        // 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
            let mut all_defined : LinkedHashSet<MuID> = LinkedHashSet::new();

            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);
                    }
                }
533

qinsoon's avatar
qinsoon committed
534 535 536
                let reg_defs = mc.get_inst_reg_defines(i);
                for reg in reg_defs {
                    all_defined.insert(reg);
537 538 539
                }
            }

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

qinsoon's avatar
qinsoon committed
542 543
            (livein, defs)
        };
544 545 546 547

        let preds : Vec<String> = {
            let mut ret = vec![];

qinsoon's avatar
qinsoon committed
548
            // predecessors of the first instruction is the predecessors of this block
549 550 551 552 553 554 555 556 557 558 559 560 561
            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
        };

        let succs : Vec<String> = {
            let mut ret = vec![];

qinsoon's avatar
qinsoon committed
562
            // successors of the last instruction is the successors of this block
563
            for succ in mc.get_succs(mc.get_last_inst(end).unwrap()).into_iter() {
564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580
                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,
            defs: defs
        };

581
        trace_if!(TRACE_LIVENESS, "as CFGNode {:?}", node);
582 583 584 585 586 587
        ret.insert(block.clone(), node);
    }

    ret
}

qinsoon's avatar
qinsoon committed
588
/// global analysis, the iterative algorithm to compute livenss until livein/out reaches a fix point
589
fn global_liveness_analysis(blocks: LinkedHashMap<String, CFGBlockNode>, cf: &mut CompiledFunction, func: &MuFunctionVersion) {
590 591
    info!("---global liveness analysis---");
    info!("{} blocks", blocks.len());
592 593

    // init live in and live out
594 595
    let mut livein  : LinkedHashMap<String, LinkedHashSet<MuID>> = {
        let mut ret = LinkedHashMap::new();
596 597 598 599 600
        for name in blocks.keys() {
            ret.insert(name.clone(), LinkedHashSet::new());
        }
        ret
    };
601 602
    let mut liveout  : LinkedHashMap<String, LinkedHashSet<MuID>> = {
        let mut ret = LinkedHashMap::new();
603 604 605 606 607 608
        for name in blocks.keys() {
            ret.insert(name.clone(), LinkedHashSet::new());
        }
        ret
    };

qinsoon's avatar
qinsoon committed
609
    // is the result changed in this iteration?
610
    let mut is_changed = true;
qinsoon's avatar
qinsoon committed
611
    // record iteration count
612 613 614
    let mut i = 0;

    while is_changed {
615
        trace_if!(TRACE_LIVENESS, "---iteration {}---", i);
616 617 618 619 620 621 622 623
        i += 1;

        // reset
        is_changed = false;

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

qinsoon's avatar
qinsoon committed
624
            // old livein/out
625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658
            let in_set_old  = livein.get(node).unwrap().clone();
            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?
            let n_changed = !in_set_old.equals(livein.get(node).unwrap()) || !out_set_old.equals(liveout.get(node).unwrap());

qinsoon's avatar
qinsoon committed
659
            if TRACE_LIVENESS {
660 661 662 663 664 665 666 667 668 669 670
                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;
        }
    }

671 672
    info!("finished in {} iterations", i);

qinsoon's avatar
qinsoon committed
673
    // set live in and live out
674 675
    for block in blocks.keys() {
        let livein : Vec<MuID> = livein.get(block).unwrap().clone().iter().map(|x| *x).collect();
676
        if TRACE_LIVENESS {
677 678 679 680 681 682
            let display_array : Vec<String> =  livein.iter().map(|x| func.context.get_temp_display(*x)).collect();
            trace!("livein  for block {}: {:?}", block, display_array);
        }
        cf.mc_mut().set_ir_block_livein(block, livein);

        let liveout : Vec<MuID> = liveout.get(block).unwrap().clone().iter().map(|x| *x).collect();
683
        if TRACE_LIVENESS {
684 685 686 687 688 689
            let display_array : Vec<String> = liveout.iter().map(|x| func.context.get_temp_display(*x)).collect();
            trace!("liveout for block {}: {:?}", block, display_array);
        }
        cf.mc_mut().set_ir_block_liveout(block, liveout);
    }
}