liveness.rs 17.8 KB
Newer Older
qinsoon's avatar
qinsoon committed
1
use compiler::machine_code::CompiledFunction;
2
use ast::ir::*;
qinsoon's avatar
qinsoon committed
3
use compiler::backend;
4
use utils::vec_utils;
5
use utils::LinkedHashSet;
6

qinsoon's avatar
qinsoon committed
7 8
use std::collections::{HashMap, HashSet};

9 10 11
use compiler::backend::reg_alloc::graph_coloring::petgraph;
use compiler::backend::reg_alloc::graph_coloring::petgraph::Graph;
use compiler::backend::reg_alloc::graph_coloring::petgraph::graph::NodeIndex;
qinsoon's avatar
qinsoon committed
12

13 14 15
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct GraphNode {
    temp: MuID,
qinsoon's avatar
qinsoon committed
16
    color: Option<MuID>,
17 18
    group: backend::RegGroup,
    spill_cost: f32
qinsoon's avatar
qinsoon committed
19
}
20

qinsoon's avatar
qinsoon committed
21
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
22
pub struct Move{pub from: NodeIndex, pub to: NodeIndex}
23 24

pub struct InterferenceGraph {
25 26
    graph: Graph<GraphNode, (), petgraph::Undirected>,
    nodes: HashMap<MuID, NodeIndex>,
qinsoon's avatar
qinsoon committed
27
    moves: HashSet<Move>,
28 29 30 31
}

impl InterferenceGraph {
    fn new() -> InterferenceGraph {
qinsoon's avatar
qinsoon committed
32
        InterferenceGraph {
33
            graph: Graph::new_undirected(),
qinsoon's avatar
qinsoon committed
34 35 36 37 38
            nodes: HashMap::new(),
            moves: HashSet::new()
        }
    }
    
39
    fn new_node(&mut self, reg_id: MuID, context: &FunctionContext) -> NodeIndex {
qinsoon's avatar
qinsoon committed
40 41 42
        let entry = context.get_value(reg_id).unwrap();
        
        if !self.nodes.contains_key(&reg_id) {
43
            let node = GraphNode {
44
                temp: reg_id,
45 46
                color: None,
                group: backend::RegGroup::get(entry.ty()),
47
                spill_cost: 0.0f32
qinsoon's avatar
qinsoon committed
48
            };
49 50 51 52 53

            let index = self.graph.add_node(node);

            self.nodes.insert(reg_id, index);
        }
54
        
55 56
        let node_index = *self.nodes.get(&reg_id).unwrap();
        let node_mut = self.graph.node_weight_mut(node_index).unwrap();
57 58
        
        // increase node spill cost
59
        node_mut.spill_cost += 1.0f32;
60
        
61
        node_index
qinsoon's avatar
qinsoon committed
62 63
    }
    
64
    pub fn get_node(&self, reg: MuID) -> NodeIndex {
qinsoon's avatar
qinsoon committed
65
        match self.nodes.get(&reg) {
qinsoon's avatar
qinsoon committed
66
            Some(index) => *index,
qinsoon's avatar
qinsoon committed
67
            None => panic!("do not have a node for {}", reg)
qinsoon's avatar
qinsoon committed
68 69 70
        }
    }
    
71 72 73 74 75 76 77 78
    pub fn temps(&self) -> Vec<MuID>{
        let mut ret = vec![];
        for reg in self.nodes.keys() {
            ret.push(*reg);
        }
        ret
    }
    
79
    pub fn nodes(&self) -> Vec<NodeIndex> {
qinsoon's avatar
qinsoon committed
80
        let mut ret = vec![];
81 82
        for index in self.nodes.values() {
            ret.push(*index);
qinsoon's avatar
qinsoon committed
83 84 85 86 87 88 89 90 91 92 93 94
        }
        ret
    }
    
    pub fn moves(&self) -> &HashSet<Move> {
        &self.moves
    }
    
    pub fn n_nodes(&self) -> usize {
        self.nodes.len()
    }
    
95
    fn add_move(&mut self, src: NodeIndex, dst: NodeIndex) {
qinsoon's avatar
qinsoon committed
96
        self.moves.insert(Move{from: src, to: dst});
97 98
    }
    
99 100
    pub fn add_interference_edge(&mut self, from: NodeIndex, to: NodeIndex) {
        self.graph.update_edge(from, to, ());
qinsoon's avatar
qinsoon committed
101 102
    }

103 104
    pub fn is_interferenced_with(&self, node1: NodeIndex, node2: NodeIndex) -> bool {
        self.graph.find_edge(node1, node2).is_some()
qinsoon's avatar
qinsoon committed
105 106
    }
    
107 108
    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
109 110
    }
    
111 112
    pub fn is_colored(&self, node: NodeIndex) -> bool {
        self.graph.node_weight(node).unwrap().color.is_some()
qinsoon's avatar
qinsoon committed
113 114
    }
    
115 116
    pub fn get_color_of(&self, node: NodeIndex) -> Option<MuID> {
        self.graph.node_weight(node).unwrap().color
117 118
    }
    
119 120
    pub fn get_group_of(&self, node: NodeIndex) -> backend::RegGroup {
        self.graph.node_weight(node).unwrap().group
qinsoon's avatar
qinsoon committed
121 122
    }
    
123 124
    pub fn get_temp_of(&self, node: NodeIndex) -> MuID {
        self.graph.node_weight(node).unwrap().temp
125 126
    }
    
127 128
    pub fn get_spill_cost(&self, node: NodeIndex) -> f32 {
        self.graph.node_weight(node).unwrap().spill_cost
129 130
    }
    
131
    fn is_same_node(&self, node1: NodeIndex, node2: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
132
        node1 == node2
qinsoon's avatar
qinsoon committed
133
    }
134 135 136 137 138 139 140

    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
141
    
142 143
    pub fn is_adj(&self, from: NodeIndex, to: NodeIndex) -> bool {
        self.is_interferenced_with(from, to)
qinsoon's avatar
qinsoon committed
144 145
    }
    
146 147
    pub fn outedges_of(&self, node: NodeIndex) -> Vec<NodeIndex> {
        self.graph.neighbors(node).collect()
148 149
    }
    
150 151
    pub fn outdegree_of(&self, node: NodeIndex) -> usize {
        self.outedges_of(node).len()
qinsoon's avatar
qinsoon committed
152 153
    }
    
154 155
    pub fn indegree_of(&self, node: NodeIndex) -> usize {
        self.outdegree_of(node)
qinsoon's avatar
qinsoon committed
156 157
    }
    
158
    pub fn degree_of(&self, node: NodeIndex) -> usize {
qinsoon's avatar
fix  
qinsoon committed
159
        self.outdegree_of(node)
qinsoon's avatar
qinsoon committed
160 161
    }
    
qinsoon's avatar
qinsoon committed
162
    pub fn print(&self, context: &FunctionContext) {
qinsoon's avatar
qinsoon committed
163 164
        debug!("");
        debug!("Interference Graph");
165

qinsoon's avatar
qinsoon committed
166
        debug!("nodes:");
qinsoon's avatar
qinsoon committed
167
        for id in self.nodes.keys() {
qinsoon's avatar
qinsoon committed
168
            let val = context.get_value(*id).unwrap().value();
qinsoon's avatar
qinsoon committed
169
            debug!("Reg {} -> {:?}", val, self.nodes.get(&id).unwrap());
qinsoon's avatar
qinsoon committed
170 171
        }

qinsoon's avatar
qinsoon committed
172
        debug!("moves:");
173
        for mov in self.moves.iter() {
qinsoon's avatar
qinsoon committed
174
            debug!("Move {:?} -> {:?}", mov.from, mov.to);
175
        }
qinsoon's avatar
qinsoon committed
176

177 178
        debug!("graph:");
        debug!("{:?}", self.graph);
qinsoon's avatar
qinsoon committed
179
        debug!("");
180
    }
qinsoon's avatar
qinsoon committed
181 182
}

183 184
#[allow(unused_variables)]
fn build_live_set(cf: &mut CompiledFunction, func: &MuFunctionVersion) {
qinsoon's avatar
qinsoon committed
185
    let n_insts = cf.mc().number_of_insts();
186
    
187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202
    let mut livein  : Vec<Vec<MuID>> = vec![vec![]; n_insts];
    let mut liveout : Vec<Vec<MuID>> = vec![vec![]; n_insts];    
    
    let mut is_changed = true;
    
    while is_changed {
        // reset
        is_changed = false;
        
        for n in 0..n_insts {
            let in_set_old = livein[n].to_vec(); // copy to new vec
            let out_set_old = liveout[n].to_vec();
            
            // in[n] <- use[n] + (out[n] - def[n])
            // (1) in[n] = use[n]
            let mut in_set_new = vec![];
qinsoon's avatar
qinsoon committed
203
            in_set_new.extend_from_slice(&cf.mc().get_inst_reg_uses(n));
204 205
            // (2) diff = out[n] - def[n]
            let mut diff = liveout[n].to_vec();
qinsoon's avatar
qinsoon committed
206
            for def in cf.mc().get_inst_reg_defines(n) {
qinsoon's avatar
qinsoon committed
207
                vec_utils::remove_value(&mut diff, def);
208 209 210 211 212 213 214 215 216 217
            }
            // (3) in[n] = in[n] + diff
            vec_utils::append_unique(&mut in_set_new, &mut diff);
            
            // update livein[n]
            livein[n].clear();
            livein[n].extend_from_slice(&in_set_new);
            
            // out[n] <- union(in[s] for every successor s of n)
            let mut union = vec![];
qinsoon's avatar
qinsoon committed
218
            for s in cf.mc().get_succs(n) {
219 220 221 222 223 224 225 226 227 228 229 230 231
                vec_utils::append_clone_unique(&mut union, &livein[*s]);
            }
            
            // update liveout[n]
            liveout[n].clear();
            liveout[n].extend_from_slice(&union);
            
            let n_changed = !vec_utils::is_identical_ignore_order(&livein[n], &in_set_old)
                || !vec_utils::is_identical_ignore_order(&liveout[n], &out_set_old);
            is_changed = is_changed || n_changed;
        }
    }
    
qinsoon's avatar
qinsoon committed
232
    for block in cf.mc().get_all_blocks().to_vec() {
233 234 235 236 237
        let start_inst = cf.mc().get_block_range(&block).unwrap().start;
        cf.mc_mut().set_ir_block_livein(&block, livein[start_inst].to_vec());

        let end_inst = cf.mc().get_block_range(&block).unwrap().end;
        cf.mc_mut().set_ir_block_liveout(&block, liveout[end_inst].to_vec());
238
    }
239 240
}

241
// from Tailoring Graph-coloring Register Allocation For Runtime Compilation, Figure 4
242 243 244
pub fn build_chaitin_briggs (cf: &mut CompiledFunction, func: &MuFunctionVersion) -> InterferenceGraph {
    build_live_set(cf, func);
    
245 246 247
    let mut ig = InterferenceGraph::new();
    
    // precolor machine register nodes
248
    for reg in backend::all_regs().values() {
249 250
        let reg_id = reg.extract_ssa_id().unwrap();
        let node = ig.new_node(reg_id, &func.context);
qinsoon's avatar
qinsoon committed
251 252 253 254

        let precolor = backend::get_color_for_precolroed(reg_id);

        ig.color_node(node, precolor);
255 256 257
    }
    
    // Initialize and creates nodes for all the involved temps/regs
qinsoon's avatar
qinsoon committed
258 259
    for i in 0..cf.mc().number_of_insts() {
        for reg_id in cf.mc().get_inst_reg_defines(i) {
260 261 262
            ig.new_node(reg_id, &func.context);
        }
        
qinsoon's avatar
qinsoon committed
263
        for reg_id in cf.mc().get_inst_reg_uses(i) {
264 265 266 267
            ig.new_node(reg_id, &func.context);
        }
    }
    
qinsoon's avatar
qinsoon committed
268
    for block in cf.mc().get_all_blocks() {
269
        // Current_Live(B) = LiveOut(B)
qinsoon's avatar
qinsoon committed
270
        let mut current_live = LinkedHashSet::from_vec(match cf.mc().get_ir_block_liveout(&block) {
271 272 273
            Some(liveout) => liveout.to_vec(),
            None => panic!("cannot find liveout for block {}", block)
        });
qinsoon's avatar
qinsoon committed
274 275 276 277 278 279
        if cfg!(debug_assertions) {
            trace!("Block{}: live out", block);
            for ele in current_live.iter() {
                trace!("{}", func.context.get_temp_display(*ele));
            }
        }
280
        
qinsoon's avatar
qinsoon committed
281
        let range = cf.mc().get_block_range(&block);
282
        if range.is_none() {
qinsoon's avatar
qinsoon committed
283
            warn!("Block{}: has no range (no instructions?)", block);
284 285
            continue;
        }
qinsoon's avatar
qinsoon committed
286
        trace!("Block{}: range = {:?}", block, range.as_ref().unwrap());
287 288 289
        
        // for every inst I in reverse order
        for i in range.unwrap().rev() {
qinsoon's avatar
qinsoon committed
290 291 292 293 294 295 296
            if cfg!(debug_assertions) {
                trace!("Block{}: Inst{}: start. current_live:", block, i);
                for ele in current_live.iter() {
                    trace!("{}", func.context.get_temp_display(*ele));
                }
            }

297
            let src : Option<MuID> = {
qinsoon's avatar
qinsoon committed
298 299 300
                if cf.mc().is_move(i) {
                    let src = cf.mc().get_inst_reg_uses(i);
                    let dst = cf.mc().get_inst_reg_defines(i);
301
                    
qinsoon's avatar
qinsoon committed
302 303 304
                    // src:  reg/imm/mem
                    // dest: reg/mem
                    // we dont care if src/dest is mem
qinsoon's avatar
qinsoon committed
305
                    if cf.mc().is_using_mem_op(i) {
306
                        None
qinsoon's avatar
qinsoon committed
307 308 309 310
                    } else {
                        if src.len() == 1 {
                            let node1 = ig.get_node(src[0]);
                            let node2 = ig.get_node(dst[0]);
qinsoon's avatar
qinsoon committed
311 312 313
                            trace!("add move between {} and {}",
                                   func.context.get_temp_display(src[0]),
                                   func.context.get_temp_display(dst[0]));
qinsoon's avatar
qinsoon committed
314 315 316 317 318 319
                            ig.add_move(node1, node2);
                            
                            Some(src[0])
                        } else {
                            None
                        }
320 321 322 323 324
                    }
                } else {
                    None
                }
            };
qinsoon's avatar
qinsoon committed
325
            trace!("Block{}: Inst{}: src={:?}", block, i, src);
326 327
            
            // for every definition D in I
qinsoon's avatar
qinsoon committed
328
            for d in cf.mc().get_inst_reg_defines(i) {
qinsoon's avatar
qinsoon committed
329
                trace!("Block{}: Inst{}: for definition {}", block, i, func.context.get_temp_display(d));
330 331 332
                // 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
333 334 335
                    trace!("Block{}: Inst{}: for each live {}",
                           block, i,
                           func.context.get_temp_display(*e));
336
                    if src.is_none() || (src.is_some() && *e != src.unwrap()) {
qinsoon's avatar
qinsoon committed
337
                        let from = ig.get_node(d);
338 339
                        let to = ig.get_node(*e);
                        
qinsoon's avatar
qinsoon committed
340
                        if !ig.is_same_node(from, to) &&ig.is_same_group(from, to) && !ig.is_adj(from, to) {
341
                            if !ig.is_colored(from) {
qinsoon's avatar
qinsoon committed
342 343 344 345
                                trace!("Block{}: Inst{}: add interference between {} and {}",
                                       block, i,
                                       func.context.get_temp_display(d),
                                       func.context.get_temp_display(*e));
346 347 348
                                ig.add_interference_edge(from, to);
                            }
                            if !ig.is_colored(to) {
qinsoon's avatar
qinsoon committed
349 350 351 352
                                trace!("Block{}: Inst{}: add interference between {} and {}",
                                       block, i,
                                       func.context.get_temp_display(*e),
                                       func.context.get_temp_display(d));
353 354 355 356 357 358 359 360
                                ig.add_interference_edge(to, from);
                            }
                        }
                    }
                }
            }
            
            // for every definition D in I
qinsoon's avatar
qinsoon committed
361
            for d in cf.mc().get_inst_reg_defines(i) {
qinsoon's avatar
qinsoon committed
362 363 364
                trace!("Block{}: Inst{}: remove define {} from current_live",
                       block, i,
                       func.context.get_temp_display(d));
365
                // remove D from Current_Live
qinsoon's avatar
qinsoon committed
366
                current_live.remove(&d);
367 368 369
            }
            
            // for every use U in I
qinsoon's avatar
qinsoon committed
370
            for u in cf.mc().get_inst_reg_uses(i) {
qinsoon's avatar
qinsoon committed
371 372 373
                trace!("Block{}: Inst{}: add use {} to current_live",
                       block, i,
                       func.context.get_temp_display(u));
374
                // add U to Current_live
qinsoon's avatar
qinsoon committed
375
                current_live.insert(u);
376
            }
qinsoon's avatar
qinsoon committed
377 378 379 380 381 382 383

            if cfg!(debug_assertions) {
                trace!("Block{}: Inst{}: done. current_live:", block, i);
                for ele in current_live.iter() {
                    trace!("{}", func.context.get_temp_display(*ele));
                }
            }
384 385 386 387 388 389
        }
    }
    
    ig
}

390
// from tony's code src/RegAlloc/Liveness.java
391
// this function is no longer used
qinsoon's avatar
qinsoon committed
392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529
//#[allow(dead_code)]
//pub fn build (cf: &CompiledFunction, func: &MuFunctionVersion) -> InterferenceGraph {
//    let mut ig = InterferenceGraph::new();
//
//    // 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);
//        ig.color_node(node, reg_id);
//    }
//
//    // Liveness Analysis
//    let n_insts = cf.mc().number_of_insts();
//    let mut live_in : Vec<Vec<MuID>> = vec![vec![]; n_insts];
//    let mut live_out : Vec<Vec<MuID>> = vec![vec![]; n_insts];
//    let mut work_list : LinkedList<usize> = LinkedList::new();
//
//    // Initialize 'in' sets for each node in the flow graph
//    // and creates nodes for all the involved temps/regs
//    for i in 0..n_insts {
//        let ref mut in_set = live_in[i];
//
//        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);
//
//            in_set.push(reg_id);
//        }
//
//        work_list.push_front(i);
//    }
//
//    // all nodes has been added, we init graph (create adjacency matrix)
//    ig.init_graph();
//
//    // compute liveIn and liveOut iteratively
//    trace!("build live outs");
//    while !work_list.is_empty() {
//        let n = work_list.pop_front().unwrap();
//        trace!("build liveout for #{}", n);
//        let ref mut out_set = live_out[n];
//
//        // out = union(in[succ]) for all succs
//        for succ in cf.mc().get_succs(n) {
//            trace!("add successor's livein {:?} to #{}", &live_in[*succ], n);
//            vec_utils::add_all(out_set, &live_in[*succ]);
//        }
//
//        // in = use(i.e. live_in) + (out - def)
//        let mut diff = out_set.clone();
//        for def in cf.mc().get_inst_reg_defines(n) {
//            vec_utils::remove_value(&mut diff, def);
//            trace!("removing def: {}", def);
//            trace!("diff = {:?}", diff);
//        }
//        trace!("out - def = {:?}", diff);
//
//        if !diff.is_empty() {
//            let ref mut in_set = live_in[n];
//            trace!("in = (use) {:?}", in_set);
//
//            if vec_utils::add_all(in_set, &diff) {
//                for p in cf.mc().get_preds(n) {
//                    work_list.push_front(*p);
//                }
//            }
//        }
//        trace!("in = use + (out - def) = {:?}", live_in[n]);
//    }
//
//    // debug live-outs
//    if cfg!(debug_assertions) {
//        trace!("check live-outs");
//        for n in 0..n_insts {
//            let ref mut live = live_out[n];
//            trace!("#{}\t{:?}", n, live);
//        }
//    }
//
//    // build interference graph
//    for n in 0..n_insts {
//        let ref mut live = live_out[n];
//
//        let src : Option<MuID> = {
//            if cf.mc().is_move(n) {
//                let src = cf.mc().get_inst_reg_uses(n);
//                let dst = cf.mc().get_inst_reg_defines(n);
//
//                // src may be an immediate number
//                // but dest is definitly a register
//                debug_assert!(dst.len() == 1);
//
//                if src.len() == 1 {
//                    let node1 = ig.get_node(src[0]);
//                    let node2 = ig.get_node(dst[0]);
//                    ig.add_move(node1, node2);
//
//                    Some(src[0])
//                } else {
//                    None
//                }
//            } else {
//                None
//            }
//        };
//
//        for d in cf.mc().get_inst_reg_defines(n) {
//            for t in live.iter() {
//                if src.is_none() || (src.is_some() && *t != src.unwrap()) {
//                    let from = ig.get_node(d);
//                    let to = ig.get_node(*t);
//
//                    if !ig.is_same_node(from, to) && !ig.is_adj(from, to) {
//                        if !ig.is_colored(from) {
//                            ig.add_interference_edge(from, to);
//                        }
//                        if !ig.is_colored(to) {
//                            ig.add_interference_edge(to, from);
//                        }
//                    }
//                }
//            }
//        }
//
//        for d in cf.mc().get_inst_reg_defines(n) {
//            vec_utils::remove_value(live, d);
//        }
//
//        for u in cf.mc().get_inst_reg_uses(n) {
//            live.push(u);
//        }
//    }
//
//    ig
//}