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

qinsoon's avatar
qinsoon committed
53 54 55 56
/// InterferenceGraph represents the interference graph, including
/// * the graph
/// * all the nodes and its NodeIndex (a node is referred to by NodeIndex)
/// * all the moves
57
pub struct InterferenceGraph {
58 59 60 61 62
    nodes: LinkedHashMap<MuID, Node>,

    adj_set: LinkedHashSet<(MuID, MuID)>,
    adj_list: LinkedHashMap<MuID, LinkedHashSet<MuID>>,
    degree: LinkedHashMap<MuID, usize>,
63
    moves: LinkedHashSet<Move>
64 65 66
}

impl InterferenceGraph {
qinsoon's avatar
qinsoon committed
67
    /// creates a new graph
68
    fn new() -> InterferenceGraph {
qinsoon's avatar
qinsoon committed
69
        InterferenceGraph {
70 71 72
            adj_set: LinkedHashSet::new(),
            adj_list: LinkedHashMap::new(),
            degree: LinkedHashMap::new(),
73
            nodes: LinkedHashMap::new(),
74
            moves: LinkedHashSet::new()
qinsoon's avatar
qinsoon committed
75 76
        }
    }
qinsoon's avatar
qinsoon committed
77 78 79

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

        // if it is the first time, create the node
qinsoon's avatar
qinsoon committed
84
        if !self.nodes.contains_key(&reg_id) {
85
            let node = Node {
86
                temp: reg_id,
87
                color: None,
88
                group: backend::RegGroup::get_from_ty(entry.ty()),
89
                spill_cost: 0.0f32
qinsoon's avatar
qinsoon committed
90
            };
91

92 93 94
            self.nodes.insert(reg_id, node);
            self.adj_list.insert(reg_id, LinkedHashSet::new());
            self.degree.insert(reg_id, 0);
95
        }
qinsoon's avatar
qinsoon committed
96 97

        // get node
98
        let node_mut = self.nodes.get_mut(&reg_id).unwrap();
99
        // increase node spill cost
100
        node_mut.spill_cost += 1.0f32;
qinsoon's avatar
qinsoon committed
101

102
        reg_id
qinsoon's avatar
qinsoon committed
103
    }
qinsoon's avatar
qinsoon committed
104 105

    /// returns all the nodes in the graph
106 107
    pub fn nodes(&self) -> Vec<MuID> {
        self.nodes.keys().map(|x| *x).collect()
qinsoon's avatar
qinsoon committed
108
    }
qinsoon's avatar
qinsoon committed
109 110

    /// returns all the moves in the graph
111
    pub fn moves(&self) -> &LinkedHashSet<Move> {
qinsoon's avatar
qinsoon committed
112 113
        &self.moves
    }
qinsoon's avatar
qinsoon committed
114 115

    /// adds a move edge between two nodes
116
    fn add_move(&mut self, src: MuID, dst: MuID) {
qinsoon's avatar
qinsoon committed
117
        let src = {
118
            if is_precolored(src) {
qinsoon's avatar
qinsoon committed
119
                // get the color for the machine register, e.g. rax for eax/ax/al/ah
120
                backend::get_color_for_precolored(src)
qinsoon's avatar
qinsoon committed
121 122 123 124 125 126
            } else {
                src
            }
        };

        let dst = {
127 128
            if is_precolored(dst) {
                backend::get_color_for_precolored(dst)
qinsoon's avatar
qinsoon committed
129 130 131 132 133
            } else {
                dst
            }
        };

qinsoon's avatar
qinsoon committed
134
        self.moves.insert(Move { from: src, to: dst });
135
    }
qinsoon's avatar
qinsoon committed
136 137

    /// adds an interference edge between two nodes
138 139 140
    pub fn add_edge(&mut self, u: MuID, v: MuID) {
        //        // adds edge to the internal graph
        //        self.graph.update_edge(from, to, ());
qinsoon's avatar
qinsoon committed
141 142 143

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

147 148 149
        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
150

151 152 153 154 155 156 157 158 159 160
            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
161
        }
qinsoon's avatar
qinsoon committed
162 163
    }

qinsoon's avatar
qinsoon committed
164
    /// set color for a node
165 166
    pub fn color_node(&mut self, reg: MuID, color: MuID) {
        self.nodes.get_mut(&reg).unwrap().color = Some(color);
qinsoon's avatar
qinsoon committed
167
    }
qinsoon's avatar
qinsoon committed
168 169

    /// is a node colored yet?
170 171
    pub fn is_colored(&self, reg: MuID) -> bool {
        self.nodes.get(&reg).unwrap().color.is_some()
qinsoon's avatar
qinsoon committed
172
    }
qinsoon's avatar
qinsoon committed
173 174

    /// gets the color of a node
175 176
    pub fn get_color_of(&self, reg: MuID) -> Option<MuID> {
        self.nodes.get(&reg).unwrap().color
177
    }
qinsoon's avatar
qinsoon committed
178 179

    /// gets the reg group of a node
180 181
    pub fn get_group_of(&self, reg: MuID) -> backend::RegGroup {
        self.nodes.get(&reg).unwrap().group
qinsoon's avatar
qinsoon committed
182
    }
qinsoon's avatar
qinsoon committed
183 184

    /// gets the temporary of a node
185 186
    pub fn get_temp_of(&self, reg: MuID) -> MuID {
        self.nodes.get(&reg).unwrap().temp
187
    }
qinsoon's avatar
qinsoon committed
188 189

    /// gets the spill cost of a node
190 191
    pub fn get_spill_cost(&self, reg: MuID) -> f32 {
        self.nodes.get(&reg).unwrap().spill_cost
192
    }
qinsoon's avatar
qinsoon committed
193 194

    /// are two nodes the same node?
195 196
    fn is_same_node(&self, reg1: MuID, reg2: MuID) -> bool {
        reg1 == reg2
qinsoon's avatar
qinsoon committed
197
    }
198

qinsoon's avatar
qinsoon committed
199
    /// are two nodes from the same reg group?
200 201
    fn is_same_group(&self, reg1: MuID, reg2: MuID) -> bool {
        self.get_group_of(reg1) == self.get_group_of(reg2)
202
    }
qinsoon's avatar
qinsoon committed
203

204 205 206
    /// 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
207
    }
qinsoon's avatar
qinsoon committed
208

209 210
    pub fn is_in_adj_set(&self, u: MuID, v: MuID) -> bool {
        self.adj_set.contains(&(u, v))
211
    }
qinsoon's avatar
qinsoon committed
212 213

    /// gets degree of a node (number of edges from the node)
214 215 216 217 218 219
    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
220
    }
qinsoon's avatar
qinsoon committed
221 222

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

227 228
        trace!("");
        trace!("Interference Graph");
229

230
        trace!("not available");
231
    }
qinsoon's avatar
qinsoon committed
232 233
}

qinsoon's avatar
qinsoon committed
234 235 236 237
/// 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
238 239 240 241
/// reference: Tailoring Graph-coloring Register Allocation For Runtime Compilation
/// - CGO'06, Figure 4
pub fn build_interference_graph_chaitin_briggs(
    cf: &mut CompiledFunction,
242
    func: &MuFunctionVersion
qinsoon's avatar
qinsoon committed
243
) -> InterferenceGraph {
qinsoon's avatar
qinsoon committed
244 245 246 247 248 249 250 251
    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();
252

qinsoon's avatar
qinsoon committed
253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275
    // 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
276 277 278
        let mut current_live =
            LinkedHashSet::from_vec(match cf.mc().get_ir_block_liveout(&block) {
                Some(liveout) => liveout.to_vec(),
279
                None => panic!("cannot find liveout for block {}", block)
qinsoon's avatar
qinsoon committed
280
            });
qinsoon's avatar
qinsoon committed
281 282 283 284 285 286 287 288 289 290 291 292
        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
293 294 295 296 297 298
        trace_if!(
            TRACE_LIVENESS,
            "Block{}: range = {:?}",
            block,
            range.as_ref().unwrap()
        );
qinsoon's avatar
qinsoon committed
299 300 301

        // for every inst I in reverse order
        for i in range.unwrap().rev() {
302
            if TRACE_LIVENESS {
qinsoon's avatar
qinsoon committed
303 304 305 306 307 308 309 310
                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
311
            let src: Option<MuID> = {
qinsoon's avatar
qinsoon committed
312 313 314 315 316 317 318 319 320 321 322
                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 {
323 324
                            let src = src[0];
                            let dst = dst[0];
qinsoon's avatar
qinsoon committed
325 326 327
                            trace_if!(
                                TRACE_LIVENESS,
                                "add move between {} and {}",
328 329
                                func.context.get_temp_display(src),
                                func.context.get_temp_display(dst)
qinsoon's avatar
qinsoon committed
330
                            );
331
                            ig.add_move(src, dst);
qinsoon's avatar
qinsoon committed
332

333
                            Some(src)
qinsoon's avatar
qinsoon committed
334 335 336 337 338 339 340 341
                        } else {
                            None
                        }
                    }
                } else {
                    None
                }
            };
342
            trace_if!(TRACE_LIVENESS, "Block{}: Inst{}: src={:?}", block, i, src);
qinsoon's avatar
qinsoon committed
343

344
            let defines = cf.mc().get_inst_reg_defines(i);
345 346 347 348 349 350
            for d in defines.iter() {
                current_live.insert(*d);
            }

            // for every definition D in I
            for d in defines {
qinsoon's avatar
qinsoon committed
351 352 353 354 355 356 357
                trace_if!(
                    TRACE_LIVENESS,
                    "Block{}: Inst{}: for definition {}",
                    block,
                    i,
                    func.context.get_temp_display(d)
                );
qinsoon's avatar
qinsoon committed
358 359 360
                // 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
361 362 363 364 365 366 367
                    trace_if!(
                        TRACE_LIVENESS,
                        "Block{}: Inst{}: for each live {}",
                        block,
                        i,
                        func.context.get_temp_display(*e)
                    );
qinsoon's avatar
qinsoon committed
368
                    if src.is_none() || (src.is_some() && *e != src.unwrap()) {
369 370
                        let from = d;
                        let to = *e;
qinsoon's avatar
qinsoon committed
371

372
                        if !ig.is_same_node(from, to) && ig.is_same_group(from, to) {
qinsoon's avatar
qinsoon committed
373
                            if !ig.is_colored(from) {
qinsoon's avatar
qinsoon committed
374 375 376 377 378
                                trace_if!(
                                    TRACE_LIVENESS,
                                    "Block{}: Inst{}: add interference between {} and {}",
                                    block,
                                    i,
379
                                    func.context.get_temp_display(d),
qinsoon's avatar
qinsoon committed
380 381
                                    func.context.get_temp_display(*e)
                                );
382
                                ig.add_edge(from, to);
qinsoon's avatar
qinsoon committed
383 384
                            }
                            if !ig.is_colored(to) {
qinsoon's avatar
qinsoon committed
385 386 387 388 389
                                trace_if!(
                                    TRACE_LIVENESS,
                                    "Block{}: Inst{}: add interference between {} and {}",
                                    block,
                                    i,
390
                                    func.context.get_temp_display(*e),
qinsoon's avatar
qinsoon committed
391 392
                                    func.context.get_temp_display(d)
                                );
393
                                ig.add_edge(to, from);
qinsoon's avatar
qinsoon committed
394 395 396 397 398 399 400 401
                            }
                        }
                    }
                }
            }

            // for every definition D in I
            for d in cf.mc().get_inst_reg_defines(i) {
qinsoon's avatar
qinsoon committed
402 403 404 405 406 407 408
                trace_if!(
                    TRACE_LIVENESS,
                    "Block{}: Inst{}: remove define {} from current_live",
                    block,
                    i,
                    func.context.get_temp_display(d)
                );
qinsoon's avatar
qinsoon committed
409 410 411 412 413 414
                // 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
415 416 417 418 419 420 421
                trace_if!(
                    TRACE_LIVENESS,
                    "Block{}: Inst{}: add use {} to current_live",
                    block,
                    i,
                    func.context.get_temp_display(u)
                );
qinsoon's avatar
qinsoon committed
422 423 424 425
                // add U to Current_live
                current_live.insert(u);
            }

426 427
            if TRACE_LIVENESS {
                trace!("Block{}: Inst{}: done. current_live:", block, i);
qinsoon's avatar
qinsoon committed
428 429 430 431 432 433 434 435 436 437 438 439 440 441
                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
442
    info!("---start building live set---");
443

qinsoon's avatar
qinsoon committed
444 445 446
    // build control flow graphs, treat a whole block as one node in the graph
    let cfg = build_cfg_nodes(cf);
    // do liveness analysis
447 448 449 450 451
    global_liveness_analysis(cfg, cf, func);

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

qinsoon's avatar
qinsoon committed
452
/// CFGBlockNode represents a basic block as a whole for global liveness analysis
453 454
#[derive(Clone, Debug)]
struct CFGBlockNode {
455
    block: MuName,
456 457
    pred: Vec<String>,
    succ: Vec<String>,
qinsoon's avatar
qinsoon committed
458
    uses: Vec<MuID>,
459
    defs: Vec<MuID>
460 461
}

qinsoon's avatar
qinsoon committed
462 463 464 465 466 467
/// builds a LinkedHashMap from basic block names to CFGBlockNode
/// We need to collect for each basic block:
/// * predecessors
/// * successors
/// * uses
/// * defs
468
fn build_cfg_nodes(cf: &mut CompiledFunction) -> LinkedHashMap<MuName, CFGBlockNode> {
469 470
    info!("---local liveness analysis---");
    let mc = cf.mc();
471
    let mut ret = LinkedHashMap::new();
472 473 474
    let all_blocks = mc.get_all_blocks();

    // create maps (start_inst -> name) and (end_inst -> name)
qinsoon's avatar
qinsoon committed
475 476
    // 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
477 478
        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
479 480 481
        for block in all_blocks.iter() {
            let range = match mc.get_block_range(block) {
                Some(range) => range,
482
                None => panic!("cannot find range for block {}", block)
qinsoon's avatar
qinsoon committed
483
            };
484

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

qinsoon's avatar
qinsoon committed
506 507 508 509 510 511
            start_inst_map.insert(first_inst, block);
            end_inst_map.insert(last_inst, block);
        }

        (start_inst_map, end_inst_map)
    };
512

qinsoon's avatar
qinsoon committed
513
    // collect info for each basic block
514
    for block in mc.get_all_blocks().iter() {
515
        trace_if!(TRACE_LIVENESS, "---block {}---", block);
516 517
        let range = mc.get_block_range(block).unwrap();
        let start_inst = range.start;
qinsoon's avatar
qinsoon committed
518
        let end = range.end;
519

qinsoon's avatar
qinsoon committed
520 521 522 523 524 525 526
        // 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
527
            let mut all_defined: LinkedHashSet<MuID> = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
528 529 530 531 532 533 534 535 536 537

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

qinsoon's avatar
qinsoon committed
539 540 541
                let reg_defs = mc.get_inst_reg_defines(i);
                for reg in reg_defs {
                    all_defined.insert(reg);
542 543 544
                }
            }

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

qinsoon's avatar
qinsoon committed
547 548
            (livein, defs)
        };
549

qinsoon's avatar
qinsoon committed
550
        let preds: Vec<String> = {
551 552
            let mut ret = vec![];

qinsoon's avatar
qinsoon committed
553
            // predecessors of the first instruction is the predecessors of this block
554 555 556 557 558 559 560 561 562 563
            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
564
        let succs: Vec<String> = {
565 566
            let mut ret = vec![];

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

586
        trace_if!(TRACE_LIVENESS, "as CFGNode {:?}", node);
587 588 589 590 591 592
        ret.insert(block.clone(), node);
    }

    ret
}

qinsoon's avatar
qinsoon committed
593
/// global analysis, the iterative algorithm to compute livenss until livein/out reaches a fix point
qinsoon's avatar
qinsoon committed
594
fn global_liveness_analysis(
595
    blocks: LinkedHashMap<MuName, CFGBlockNode>,
qinsoon's avatar
qinsoon committed
596
    cf: &mut CompiledFunction,
597
    func: &MuFunctionVersion
qinsoon's avatar
qinsoon committed
598
) {
599 600
    info!("---global liveness analysis---");
    info!("{} blocks", blocks.len());
601 602

    // init live in and live out
603
    let mut livein: LinkedHashMap<MuName, LinkedHashSet<MuID>> = {
604
        let mut ret = LinkedHashMap::new();
605 606 607 608 609
        for name in blocks.keys() {
            ret.insert(name.clone(), LinkedHashSet::new());
        }
        ret
    };
610
    let mut liveout: LinkedHashMap<MuName, LinkedHashSet<MuID>> = {
611
        let mut ret = LinkedHashMap::new();
612 613 614 615 616 617
        for name in blocks.keys() {
            ret.insert(name.clone(), LinkedHashSet::new());
        }
        ret
    };

qinsoon's avatar
qinsoon committed
618
    // is the result changed in this iteration?
619
    let mut is_changed = true;
qinsoon's avatar
qinsoon committed
620
    // record iteration count
621 622 623
    let mut i = 0;

    while is_changed {
624
        trace_if!(TRACE_LIVENESS, "---iteration {}---", i);
625 626 627 628 629 630 631 632
        i += 1;

        // reset
        is_changed = false;

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

qinsoon's avatar
qinsoon committed
633
            // old livein/out
qinsoon's avatar
qinsoon committed
634
            let in_set_old = livein.get(node).unwrap().clone();
635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665
            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
666 667
            let n_changed = !in_set_old.equals(livein.get(node).unwrap()) ||
                !out_set_old.equals(liveout.get(node).unwrap());
668

qinsoon's avatar
qinsoon committed
669
            if TRACE_LIVENESS {
670 671 672 673 674 675 676 677 678 679 680
                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;
        }
    }

681 682
    info!("finished in {} iterations", i);

qinsoon's avatar
qinsoon committed
683
    // set live in and live out
684
    for block in blocks.keys() {
qinsoon's avatar
qinsoon committed
685 686 687 688 689 690 691
        let livein: Vec<MuID> = livein
            .get(block)
            .unwrap()
            .clone()
            .iter()
            .map(|x| *x)
            .collect();
692
        if TRACE_LIVENESS {
qinsoon's avatar
qinsoon committed
693 694 695 696
            let display_array: Vec<String> = livein
                .iter()
                .map(|x| func.context.get_temp_display(*x))
                .collect();
697 698 699 700
            trace!("livein  for block {}: {:?}", block, display_array);
        }
        cf.mc_mut().set_ir_block_livein(block, livein);

qinsoon's avatar
qinsoon committed
701 702 703 704 705 706 707
        let liveout: Vec<MuID> = liveout
            .get(block)
            .unwrap()
            .clone()
            .iter()
            .map(|x| *x)
            .collect();
708
        if TRACE_LIVENESS {
qinsoon's avatar
qinsoon committed
709 710 711 712
            let display_array: Vec<String> = liveout
                .iter()
                .map(|x| func.context.get_temp_display(*x))
                .collect();
713 714 715 716
            trace!("liveout for block {}: {:?}", block, display_array);
        }
        cf.mc_mut().set_ir_block_liveout(block, liveout);
    }
qinsoon's avatar
qinsoon committed
717
}