liveness.rs 25.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

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)]
qinsoon's avatar
qinsoon committed
43 44
pub struct Move {
    pub from: NodeIndex,
45
    pub to: NodeIndex
qinsoon's avatar
qinsoon committed
46
}
47

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

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

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

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

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

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

99
        node_index
qinsoon's avatar
qinsoon committed
100
    }
qinsoon's avatar
qinsoon committed
101 102

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

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

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

    /// adds a move edge between two nodes
125
    fn add_move(&mut self, src: NodeIndex, dst: NodeIndex) {
qinsoon's avatar
qinsoon committed
126 127 128
        let src = {
            let temp_src = self.get_temp_of(src);
            if temp_src < MACHINE_ID_END {
qinsoon's avatar
qinsoon committed
129 130
                // 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
131 132 133 134 135 136 137 138 139
                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
140
                let alias = backend::get_color_for_precolored(temp_dst);
qinsoon's avatar
qinsoon committed
141 142 143 144 145 146
                self.get_node(alias)
            } else {
                dst
            }
        };

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

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

        // if one of the node is machine register, we also add
        // interference edge to its alias
qinsoon's avatar
qinsoon committed
157 158
        // e.g. if we have %a - %edi interfered,
        // we also add %a - %rdi interference
qinsoon's avatar
qinsoon committed
159 160

        let from_tmp = self.graph.node_weight(from).unwrap().temp;
qinsoon's avatar
qinsoon committed
161
        let to_tmp = self.graph.node_weight(to).unwrap().temp;
qinsoon's avatar
qinsoon committed
162 163 164 165 166 167 168 169 170 171 172 173 174 175 176

        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);
qinsoon's avatar
qinsoon committed
177
            let to_tmp_node = self.get_node(to_tmp);
qinsoon's avatar
qinsoon committed
178 179
            self.graph.update_edge(from_tmp_node, to_tmp_node, ());
        }
qinsoon's avatar
qinsoon committed
180 181
    }

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

    /// set color for a node
189 190
    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
191
    }
qinsoon's avatar
qinsoon committed
192 193

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

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

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

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

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

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

qinsoon's avatar
qinsoon committed
223
    /// are two nodes from the same reg group?
224 225 226 227 228 229
    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
230 231

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

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

    /// 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
244
    }
qinsoon's avatar
qinsoon committed
245 246

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

251 252
        trace!("");
        trace!("Interference Graph");
253

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

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

265
        trace!("graph:");
qinsoon's avatar
qinsoon committed
266 267 268 269
        trace!(
            "\n\n{:?}\n",
            Dot::with_config(&self.graph, &[Config::EdgeNoLabel])
        );
270
        trace!("");
271
    }
qinsoon's avatar
qinsoon committed
272 273
}

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

qinsoon's avatar
qinsoon committed
293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315
    // 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
316 317 318
        let mut current_live =
            LinkedHashSet::from_vec(match cf.mc().get_ir_block_liveout(&block) {
                Some(liveout) => liveout.to_vec(),
319
                None => panic!("cannot find liveout for block {}", block)
qinsoon's avatar
qinsoon committed
320
            });
qinsoon's avatar
qinsoon committed
321 322 323 324 325 326 327 328 329 330 331 332
        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
333 334 335 336 337 338
        trace_if!(
            TRACE_LIVENESS,
            "Block{}: range = {:?}",
            block,
            range.as_ref().unwrap()
        );
qinsoon's avatar
qinsoon committed
339 340 341

        // for every inst I in reverse order
        for i in range.unwrap().rev() {
342
            if TRACE_LIVENESS {
qinsoon's avatar
qinsoon committed
343 344 345 346 347 348 349 350
                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
351
            let src: Option<MuID> = {
qinsoon's avatar
qinsoon committed
352 353 354 355 356 357 358 359 360 361 362 363 364
                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]);
qinsoon's avatar
qinsoon committed
365 366 367 368 369 370
                            trace_if!(
                                TRACE_LIVENESS,
                                "add move between {} and {}",
                                func.context.get_temp_display(src[0]),
                                func.context.get_temp_display(dst[0])
                            );
qinsoon's avatar
qinsoon committed
371 372 373 374 375 376 377 378 379 380 381
                            ig.add_move(node1, node2);

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

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

            // for every definition D in I
            for d in defines {
qinsoon's avatar
qinsoon committed
391 392 393 394 395 396 397
                trace_if!(
                    TRACE_LIVENESS,
                    "Block{}: Inst{}: for definition {}",
                    block,
                    i,
                    func.context.get_temp_display(d)
                );
qinsoon's avatar
qinsoon committed
398 399 400
                // 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
401 402 403 404 405 406 407
                    trace_if!(
                        TRACE_LIVENESS,
                        "Block{}: Inst{}: for each live {}",
                        block,
                        i,
                        func.context.get_temp_display(*e)
                    );
qinsoon's avatar
qinsoon committed
408 409 410 411
                    if src.is_none() || (src.is_some() && *e != src.unwrap()) {
                        let from = ig.get_node(d);
                        let to = ig.get_node(*e);

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

            // for every definition D in I
            for d in cf.mc().get_inst_reg_defines(i) {
qinsoon's avatar
qinsoon committed
444 445 446 447 448 449 450
                trace_if!(
                    TRACE_LIVENESS,
                    "Block{}: Inst{}: remove define {} from current_live",
                    block,
                    i,
                    func.context.get_temp_display(d)
                );
qinsoon's avatar
qinsoon committed
451 452 453 454 455 456
                // 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
457 458 459 460 461 462 463
                trace_if!(
                    TRACE_LIVENESS,
                    "Block{}: Inst{}: add use {} to current_live",
                    block,
                    i,
                    func.context.get_temp_display(u)
                );
qinsoon's avatar
qinsoon committed
464 465 466 467
                // add U to Current_live
                current_live.insert(u);
            }

468 469
            if TRACE_LIVENESS {
                trace!("Block{}: Inst{}: done. current_live:", block, i);
qinsoon's avatar
qinsoon committed
470 471 472 473 474 475 476 477 478 479 480 481 482 483
                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
484
    info!("---start building live set---");
485

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

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

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

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

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

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

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

        (start_inst_map, end_inst_map)
    };
554

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

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

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

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

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

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

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

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

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

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

    ret
}

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

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

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

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

        // reset
        is_changed = false;

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

qinsoon's avatar
qinsoon committed
675
            // old livein/out
qinsoon's avatar
qinsoon committed
676
            let in_set_old = livein.get(node).unwrap().clone();
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 707
            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
708 709
            let n_changed = !in_set_old.equals(livein.get(node).unwrap()) ||
                !out_set_old.equals(liveout.get(node).unwrap());
710

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

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

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

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