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 23.3 KB
Newer Older
1 2
extern crate hprof;

qinsoon's avatar
qinsoon committed
3
use compiler::machine_code::CompiledFunction;
4
use ast::ir::*;
qinsoon's avatar
qinsoon committed
5
use compiler::backend;
6
use utils::LinkedHashSet;
7
use utils::LinkedHashMap;
qinsoon's avatar
qinsoon committed
8

9 10 11
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
12

qinsoon's avatar
qinsoon committed
13
/// GraphNode represents a node in the interference graph.
14 15
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct GraphNode {
qinsoon's avatar
qinsoon committed
16
    /// temp ID (could be register)
17
    temp: MuID,
qinsoon's avatar
qinsoon committed
18
    /// assigned color
qinsoon's avatar
qinsoon committed
19
    color: Option<MuID>,
qinsoon's avatar
qinsoon committed
20
    /// temp register group (which machine register class we should assign)
21
    group: backend::RegGroup,
qinsoon's avatar
qinsoon committed
22
    /// cost to spill this temp
23
    spill_cost: f32
qinsoon's avatar
qinsoon committed
24
}
25

qinsoon's avatar
qinsoon committed
26 27
/// 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
28
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
29
pub struct Move{pub from: NodeIndex, pub to: NodeIndex}
30

qinsoon's avatar
qinsoon committed
31 32 33 34
/// InterferenceGraph represents the interference graph, including
/// * the graph
/// * all the nodes and its NodeIndex (a node is referred to by NodeIndex)
/// * all the moves
35
pub struct InterferenceGraph {
qinsoon's avatar
qinsoon committed
36
    /// the internal graph
37
    graph: Graph<GraphNode, (), petgraph::Undirected>,
qinsoon's avatar
qinsoon committed
38 39
    /// a map of all nodes (from temp ID to node index)
    /// node index is how nodes are referred to with pet_graph
40
    nodes: LinkedHashMap<MuID, NodeIndex>,
qinsoon's avatar
qinsoon committed
41
    /// a set of all moves
42
    moves: LinkedHashSet<Move>,
43 44 45
}

impl InterferenceGraph {
qinsoon's avatar
qinsoon committed
46
    /// creates a new graph
47
    fn new() -> InterferenceGraph {
qinsoon's avatar
qinsoon committed
48
        InterferenceGraph {
49
            graph: Graph::new_undirected(),
50 51
            nodes: LinkedHashMap::new(),
            moves: LinkedHashSet::new()
qinsoon's avatar
qinsoon committed
52 53
        }
    }
qinsoon's avatar
qinsoon committed
54 55 56

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

        // if it is the first time, create the node
qinsoon's avatar
qinsoon committed
61
        if !self.nodes.contains_key(&reg_id) {
62
            let node = GraphNode {
63
                temp: reg_id,
64
                color: None,
65
                group: backend::RegGroup::get_from_ty(entry.ty()),
66
                spill_cost: 0.0f32
qinsoon's avatar
qinsoon committed
67
            };
68

qinsoon's avatar
qinsoon committed
69
            // add to the graph
70
            let index = self.graph.add_node(node);
qinsoon's avatar
qinsoon committed
71
            // save index
72 73
            self.nodes.insert(reg_id, index);
        }
qinsoon's avatar
qinsoon committed
74 75

        // get the node index
76
        let node_index = *self.nodes.get(&reg_id).unwrap();
qinsoon's avatar
qinsoon committed
77
        // get node
78
        let node_mut = self.graph.node_weight_mut(node_index).unwrap();
79
        // increase node spill cost
80
        node_mut.spill_cost += 1.0f32;
81
        
82
        node_index
qinsoon's avatar
qinsoon committed
83
    }
qinsoon's avatar
qinsoon committed
84 85

    /// returns the node index for a temp
86
    pub fn get_node(&self, reg: MuID) -> NodeIndex {
qinsoon's avatar
qinsoon committed
87
        match self.nodes.get(&reg) {
qinsoon's avatar
qinsoon committed
88
            Some(index) => *index,
qinsoon's avatar
qinsoon committed
89
            None => panic!("do not have a node for {}", reg)
qinsoon's avatar
qinsoon committed
90 91
        }
    }
qinsoon's avatar
qinsoon committed
92 93

    /// returns all the nodes in the graph
94
    pub fn nodes(&self) -> Vec<NodeIndex> {
qinsoon's avatar
qinsoon committed
95
        let mut ret = vec![];
96 97
        for index in self.nodes.values() {
            ret.push(*index);
qinsoon's avatar
qinsoon committed
98 99 100
        }
        ret
    }
qinsoon's avatar
qinsoon committed
101 102

    /// returns all the moves in the graph
103
    pub fn moves(&self) -> &LinkedHashSet<Move> {
qinsoon's avatar
qinsoon committed
104 105
        &self.moves
    }
qinsoon's avatar
qinsoon committed
106 107

    /// adds a move edge between two nodes
108
    fn add_move(&mut self, src: NodeIndex, dst: NodeIndex) {
qinsoon's avatar
qinsoon committed
109 110 111
        let src = {
            let temp_src = self.get_temp_of(src);
            if temp_src < MACHINE_ID_END {
qinsoon's avatar
qinsoon committed
112 113
                // 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
114 115 116 117 118 119 120 121 122
                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
123
                let alias = backend::get_color_for_precolored(temp_dst);
qinsoon's avatar
qinsoon committed
124 125 126 127 128 129
                self.get_node(alias)
            } else {
                dst
            }
        };

qinsoon's avatar
qinsoon committed
130
        self.moves.insert(Move{from: src, to: dst});
131
    }
qinsoon's avatar
qinsoon committed
132 133

    /// adds an interference edge between two nodes
134
    pub fn add_interference_edge(&mut self, from: NodeIndex, to: NodeIndex) {
qinsoon's avatar
qinsoon committed
135
        // adds edge to the internal graph
136
        self.graph.update_edge(from, to, ());
qinsoon's avatar
qinsoon committed
137 138 139

        // if one of the node is machine register, we also add
        // interference edge to its alias
qinsoon's avatar
qinsoon committed
140 141
        // e.g. if we have %a - %edi interfered,
        // we also add %a - %rdi interference
qinsoon's avatar
qinsoon committed
142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162

        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
163 164
    }

qinsoon's avatar
qinsoon committed
165 166
    /// is two nodes interfered?
    pub fn is_interfered_with(&self, node1: NodeIndex, node2: NodeIndex) -> bool {
167 168
        let edge = self.graph.find_edge(node1, node2);
        edge.is_some()
qinsoon's avatar
qinsoon committed
169
    }
qinsoon's avatar
qinsoon committed
170 171

    /// set color for a node
172 173
    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
174
    }
qinsoon's avatar
qinsoon committed
175 176

    /// is a node colored yet?
177 178
    pub fn is_colored(&self, node: NodeIndex) -> bool {
        self.graph.node_weight(node).unwrap().color.is_some()
qinsoon's avatar
qinsoon committed
179
    }
qinsoon's avatar
qinsoon committed
180 181

    /// gets the color of a node
182 183
    pub fn get_color_of(&self, node: NodeIndex) -> Option<MuID> {
        self.graph.node_weight(node).unwrap().color
184
    }
qinsoon's avatar
qinsoon committed
185 186

    /// gets the reg group of a node
187 188
    pub fn get_group_of(&self, node: NodeIndex) -> backend::RegGroup {
        self.graph.node_weight(node).unwrap().group
qinsoon's avatar
qinsoon committed
189
    }
qinsoon's avatar
qinsoon committed
190 191

    /// gets the temporary of a node
192 193
    pub fn get_temp_of(&self, node: NodeIndex) -> MuID {
        self.graph.node_weight(node).unwrap().temp
194
    }
qinsoon's avatar
qinsoon committed
195 196

    /// gets the spill cost of a node
197 198
    pub fn get_spill_cost(&self, node: NodeIndex) -> f32 {
        self.graph.node_weight(node).unwrap().spill_cost
199
    }
qinsoon's avatar
qinsoon committed
200 201

    /// are two nodes the same node?
202
    fn is_same_node(&self, node1: NodeIndex, node2: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
203
        node1 == node2
qinsoon's avatar
qinsoon committed
204
    }
205

qinsoon's avatar
qinsoon committed
206
    /// are two nodes from the same reg group?
207 208 209 210 211 212
    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
213 214

    /// are two nodes adjacent?
215
    pub fn is_adj(&self, from: NodeIndex, to: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
216
        self.is_interfered_with(from, to)
qinsoon's avatar
qinsoon committed
217
    }
qinsoon's avatar
qinsoon committed
218 219 220

    /// gets edges from a node
    pub fn get_edges_of(&self, node: NodeIndex) -> Vec<NodeIndex> {
221
        self.graph.neighbors(node).collect()
222
    }
qinsoon's avatar
qinsoon committed
223 224 225 226

    /// 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
227
    }
qinsoon's avatar
qinsoon committed
228 229

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

234 235
        trace!("");
        trace!("Interference Graph");
236

237
        trace!("nodes:");
qinsoon's avatar
qinsoon committed
238
        for id in self.nodes.keys() {
qinsoon's avatar
qinsoon committed
239
            let val = context.get_value(*id).unwrap().value();
240
            trace!("Reg {} -> {:?}", val, self.nodes.get(&id).unwrap());
qinsoon's avatar
qinsoon committed
241 242
        }

243
        trace!("moves:");
244
        for mov in self.moves.iter() {
245
            trace!("Move {:?} -> {:?}", mov.from, mov.to);
246
        }
qinsoon's avatar
qinsoon committed
247

248 249 250
        trace!("graph:");
        trace!("\n\n{:?}\n", Dot::with_config(&self.graph, &[Config::EdgeNoLabel]));
        trace!("");
251
    }
qinsoon's avatar
qinsoon committed
252 253
}

qinsoon's avatar
qinsoon committed
254 255 256 257 258 259 260 261 262 263 264 265 266 267
/// 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();
268

qinsoon's avatar
qinsoon committed
269 270 271 272 273 274 275 276 277 278 279 280 281 282 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 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433
    // 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;
        }
        if TRACE_LIVENESS {
            trace!("Block{}: range = {:?}", block, range.as_ref().unwrap());
        }

        // for every inst I in reverse order
        for i in range.unwrap().rev() {
            if cfg!(debug_assertions) {
                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]);
                            trace!("add move between {} and {}",
                            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
                }
            };
            if TRACE_LIVENESS {
                trace!("Block{}: Inst{}: src={:?}", block, i, src);
            }

            // for every definition D in I
            for d in cf.mc().get_inst_reg_defines(i) {
                if TRACE_LIVENESS {
                    trace!("Block{}: Inst{}: for definition {}", block, i, func.context.get_temp_display(d));
                }
                // add an interference from D to every element E in Current_Live - {D}
                // creating nodes if necessary
                for e in current_live.iter() {
                    if TRACE_LIVENESS {
                        trace!("Block{}: Inst{}: for each live {}", block, i, func.context.get_temp_display(*e));
                    }
                    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) {
                                if TRACE_LIVENESS {
                                    trace!("Block{}: Inst{}: add interference between {} and {}",
                                        block, i,
                                        func.context.get_temp_display(d),
                                        func.context.get_temp_display(*e));
                                }
                                ig.add_interference_edge(from, to);
                            }
                            if !ig.is_colored(to) {
                                if TRACE_LIVENESS {
                                    trace!("Block{}: Inst{}: add interference between {} and {}",
                                        block, i,
                                        func.context.get_temp_display(*e),
                                        func.context.get_temp_display(d));
                                }
                                ig.add_interference_edge(to, from);
                            }
                        }
                    }
                }
            }

            // for every definition D in I
            for d in cf.mc().get_inst_reg_defines(i) {
                if TRACE_LIVENESS {
                    trace!("Block{}: Inst{}: remove define {} from current_live",
                        block, i,
                        func.context.get_temp_display(d));
                }
                // 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) {
                if TRACE_LIVENESS {
                    trace!("Block{}: Inst{}: add use {} to current_live",
                        block, i,
                        func.context.get_temp_display(u));
                }
                // add U to Current_live
                current_live.insert(u);
            }

            if cfg!(debug_assertions) {
                if TRACE_LIVENESS {
                    trace!("Block{}: Inst{}: done. current_live:", block, i);
                }
                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
434
    info!("---start building live set---");
435

qinsoon's avatar
qinsoon committed
436 437 438
    // build control flow graphs, treat a whole block as one node in the graph
    let cfg = build_cfg_nodes(cf);
    // do liveness analysis
439 440 441 442 443
    global_liveness_analysis(cfg, cf, func);

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

qinsoon's avatar
qinsoon committed
444
/// CFGBlockNode represents a basic block as a whole for global liveness analysis
445 446 447 448 449 450 451 452 453
#[derive(Clone, Debug)]
struct CFGBlockNode {
    block: String,
    pred: Vec<String>,
    succ: Vec<String>,
    uses:  Vec<MuID>,
    defs: Vec<MuID>
}

qinsoon's avatar
qinsoon committed
454 455 456 457 458 459 460
/// 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> {
461 462
    info!("---local liveness analysis---");
    let mc = cf.mc();
463
    let mut ret = LinkedHashMap::new();
464 465 466
    let all_blocks = mc.get_all_blocks();

    // create maps (start_inst -> name) and (end_inst -> name)
qinsoon's avatar
qinsoon committed
467 468 469 470 471 472 473 474 475
    // 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)
            };
476

qinsoon's avatar
qinsoon committed
477 478 479 480 481 482 483 484
            // 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)
            };
            trace!("Block {}: start_inst={}, end_inst(inclusive)={}", block, first_inst, last_inst);
485

qinsoon's avatar
qinsoon committed
486 487 488 489 490 491
            start_inst_map.insert(first_inst, block);
            end_inst_map.insert(last_inst, block);
        }

        (start_inst_map, end_inst_map)
    };
492

qinsoon's avatar
qinsoon committed
493
    // collect info for each basic block
494 495 496 497 498 499
    for block in mc.get_all_blocks().iter() {
        trace!("---block {}---", block);
        let range = mc.get_block_range(block).unwrap();
        let start_inst = range.start;
        let end        = range.end;

qinsoon's avatar
qinsoon committed
500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517
        // 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);
                    }
                }
518

qinsoon's avatar
qinsoon committed
519 520 521
                let reg_defs = mc.get_inst_reg_defines(i);
                for reg in reg_defs {
                    all_defined.insert(reg);
522 523 524
                }
            }

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

qinsoon's avatar
qinsoon committed
527 528
            (livein, defs)
        };
529 530 531 532

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

qinsoon's avatar
qinsoon committed
533
            // predecessors of the first instruction is the predecessors of this block
534 535 536 537 538 539 540 541 542 543 544 545 546
            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
547
            // successors of the last instruction is the successors of this block
548
            for succ in mc.get_succs(mc.get_last_inst(end).unwrap()).into_iter() {
549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572
                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
        };

        trace!("as CFGNode {:?}", node);
        ret.insert(block.clone(), node);
    }

    ret
}

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

    // init live in and live out
579 580
    let mut livein  : LinkedHashMap<String, LinkedHashSet<MuID>> = {
        let mut ret = LinkedHashMap::new();
581 582 583 584 585
        for name in blocks.keys() {
            ret.insert(name.clone(), LinkedHashSet::new());
        }
        ret
    };
586 587
    let mut liveout  : LinkedHashMap<String, LinkedHashSet<MuID>> = {
        let mut ret = LinkedHashMap::new();
588 589 590 591 592 593
        for name in blocks.keys() {
            ret.insert(name.clone(), LinkedHashSet::new());
        }
        ret
    };

qinsoon's avatar
qinsoon committed
594
    // is the result changed in this iteration?
595
    let mut is_changed = true;
qinsoon's avatar
qinsoon committed
596
    // record iteration count
597 598 599 600 601 602 603 604 605 606 607 608
    let mut i = 0;

    while is_changed {
        trace!("---iteration {}---", i);
        i += 1;

        // reset
        is_changed = false;

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

qinsoon's avatar
qinsoon committed
609
            // old livein/out
610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643
            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
644
            if TRACE_LIVENESS {
645 646 647 648 649 650 651 652 653 654 655
                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;
        }
    }

656 657
    info!("finished in {} iterations", i);

qinsoon's avatar
qinsoon committed
658
    // set live in and live out
659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674
    for block in blocks.keys() {
        let livein : Vec<MuID> = livein.get(block).unwrap().clone().iter().map(|x| *x).collect();
        {
            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();
        {
            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);
    }
}