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

15 16
extern crate hprof;

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

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

qinsoon's avatar
qinsoon committed
36 37
/// Move represents a move between two nodes (referred by index)
/// We need to know the moves so that we can coalesce.
qinsoon's avatar
qinsoon committed
38
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
qinsoon's avatar
qinsoon committed
39
pub struct Move {
40 41 42 43 44 45 46 47 48 49 50
    pub from: MuID,
    pub to: MuID
}

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

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

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

    adj_set: LinkedHashSet<(MuID, MuID)>,
    adj_list: LinkedHashMap<MuID, LinkedHashSet<MuID>>,
    degree: LinkedHashMap<MuID, usize>,
72
    moves: LinkedHashSet<Move>
73 74 75
}

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

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

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

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

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

111
        reg_id
qinsoon's avatar
qinsoon committed
112
    }
qinsoon's avatar
qinsoon committed
113 114

    /// returns all the nodes in the graph
115 116
    pub fn nodes(&self) -> Vec<MuID> {
        self.nodes.keys().map(|x| *x).collect()
qinsoon's avatar
qinsoon committed
117
    }
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: MuID, dst: MuID) {
qinsoon's avatar
qinsoon committed
126
        let src = {
127
            if is_precolored(src) {
qinsoon's avatar
qinsoon committed
128
                // get the color for the machine register, e.g. rax for eax/ax/al/ah
129
                backend::get_color_for_precolored(src)
qinsoon's avatar
qinsoon committed
130 131 132 133 134 135
            } else {
                src
            }
        };

        let dst = {
136 137
            if is_precolored(dst) {
                backend::get_color_for_precolored(dst)
qinsoon's avatar
qinsoon committed
138 139 140 141 142
            } else {
                dst
            }
        };

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

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

153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172
        let u = if is_precolored(u) {
            if is_usable(u) {
                backend::get_color_for_precolored(u)
            } else {
                // if it is not usable, we do not need to add an interference edge
                return;
            }
        } else {
            u
        };
        let v = if is_precolored(v) {
            if is_usable(v) {
                backend::get_color_for_precolored(v)
            } else {
                return;
            }
        } else {
            v
        };

173 174 175
        if !self.adj_set.contains(&(u, v)) && u != v {
            self.adj_set.insert((u, v));
            self.adj_set.insert((v, u));
qinsoon's avatar
qinsoon committed
176

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

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

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

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

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

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

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

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

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

230 231 232
    /// gets edges from a node
    pub fn get_adj_list(&self, reg: MuID) -> &LinkedHashSet<MuID> {
        self.adj_list.get(&reg).unwrap()
qinsoon's avatar
qinsoon committed
233
    }
qinsoon's avatar
qinsoon committed
234

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

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

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

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

253 254
        trace!("");
        trace!("Interference Graph");
255

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

        trace!("edges: ");

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

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

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

        // for every inst I in reverse order
        for i in range.unwrap().rev() {
340
            if TRACE_LIVENESS {
qinsoon's avatar
qinsoon committed
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));
                }
            }

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

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

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

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

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

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

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

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

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

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

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

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

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

qinsoon's avatar
qinsoon committed
544 545 546 547 548 549
            start_inst_map.insert(first_inst, block);
            end_inst_map.insert(last_inst, block);
        }

        (start_inst_map, end_inst_map)
    };
550

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

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

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

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

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

qinsoon's avatar
qinsoon committed
585 586
            (livein, defs)
        };
587

qinsoon's avatar
qinsoon committed
588
        let preds: Vec<String> = {
589 590
            let mut ret = vec![];

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

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

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

    ret
}

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

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

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

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

        // reset
        is_changed = false;

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

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

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

719 720
    info!("finished in {} iterations", i);

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

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