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::LinkedHashSet;
5

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

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

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

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

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

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

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

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

102
    pub fn is_interferenced_with(&self, node1: NodeIndex, node2: NodeIndex) -> bool {
103 104 105 106 107 108
        trace!("trying to find edge between {:?} and {:?}", node1, node2);
        let edge = self.graph.find_edge(node1, node2);

        trace!("edge: {:?}", edge);

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

    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
145
    
146 147
    pub fn is_adj(&self, from: NodeIndex, to: NodeIndex) -> bool {
        self.is_interferenced_with(from, to)
qinsoon's avatar
qinsoon committed
148 149
    }
    
150 151
    pub fn outedges_of(&self, node: NodeIndex) -> Vec<NodeIndex> {
        self.graph.neighbors(node).collect()
152 153
    }
    
154 155
    pub fn outdegree_of(&self, node: NodeIndex) -> usize {
        self.outedges_of(node).len()
qinsoon's avatar
qinsoon committed
156 157
    }
    
158 159
    pub fn indegree_of(&self, node: NodeIndex) -> usize {
        self.outdegree_of(node)
qinsoon's avatar
qinsoon committed
160 161
    }
    
162
    pub fn degree_of(&self, node: NodeIndex) -> usize {
qinsoon's avatar
fix  
qinsoon committed
163
        self.outdegree_of(node)
qinsoon's avatar
qinsoon committed
164 165
    }
    
qinsoon's avatar
qinsoon committed
166
    pub fn print(&self, context: &FunctionContext) {
167 168 169
        use compiler::backend::reg_alloc::graph_coloring::petgraph::dot::Dot;
        use compiler::backend::reg_alloc::graph_coloring::petgraph::dot::Config;

qinsoon's avatar
qinsoon committed
170 171
        debug!("");
        debug!("Interference Graph");
172

qinsoon's avatar
qinsoon committed
173
        debug!("nodes:");
qinsoon's avatar
qinsoon committed
174
        for id in self.nodes.keys() {
qinsoon's avatar
qinsoon committed
175
            let val = context.get_value(*id).unwrap().value();
qinsoon's avatar
qinsoon committed
176
            debug!("Reg {} -> {:?}", val, self.nodes.get(&id).unwrap());
qinsoon's avatar
qinsoon committed
177 178
        }

qinsoon's avatar
qinsoon committed
179
        debug!("moves:");
180
        for mov in self.moves.iter() {
qinsoon's avatar
qinsoon committed
181
            debug!("Move {:?} -> {:?}", mov.from, mov.to);
182
        }
qinsoon's avatar
qinsoon committed
183

184
        debug!("graph:");
185
        debug!("\n\n{:?}\n", Dot::with_config(&self.graph, &[Config::EdgeNoLabel]));
qinsoon's avatar
qinsoon committed
186
        debug!("");
187
    }
qinsoon's avatar
qinsoon committed
188 189
}

190 191 192
fn build_live_set (cf: &mut CompiledFunction) {
    info!("start building live set");

qinsoon's avatar
qinsoon committed
193
    let n_insts = cf.mc().number_of_insts();
194 195 196 197

    let mut livein  : Vec<LinkedHashSet<MuID>> = vec![LinkedHashSet::new(); n_insts];
    let mut liveout : Vec<LinkedHashSet<MuID>> = vec![LinkedHashSet::new(); n_insts];

198
    let mut is_changed = true;
199

200 201 202
    while is_changed {
        // reset
        is_changed = false;
203

204
        for n in 0..n_insts {
205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221
            let in_set_old = livein[n].clone();
            let out_set_old = liveout[n].clone();

            // in[n] <- use[n] + (out[n] - def[n]);
            {
                let ref mut inset = livein[n];

                inset.clear();

                // (1) in[n] = use[n]
                inset.add_from_vec(cf.mc().get_inst_reg_uses(n));
                // (2) + out[n]
                inset.add_all(liveout[n].clone());
                // (3) - def[n]
                for def in cf.mc().get_inst_reg_defines(n) {
                    inset.remove(&def);
                }
222
            }
223

224
            // out[n] <- union(in[s] for every successor s of n)
225 226 227 228 229 230 231
            {
                let ref mut outset = liveout[n];
                outset.clear();

                for s in cf.mc().get_succs(n) {
                    outset.add_all(livein[*s].clone());
                }
232
            }
233 234 235 236

            // is in/out changed in this iteration?
            let n_changed = !in_set_old.equals(&livein[n]) || !out_set_old.equals(&liveout[n]);

237 238 239
            is_changed = is_changed || n_changed;
        }
    }
240

qinsoon's avatar
qinsoon committed
241
    for block in cf.mc().get_all_blocks().to_vec() {
242
        let start_inst = cf.mc().get_block_range(&block).unwrap().start;
243
        cf.mc_mut().set_ir_block_livein(&block, livein[start_inst].clone().to_vec());
244 245

        let end_inst = cf.mc().get_block_range(&block).unwrap().end;
246
        cf.mc_mut().set_ir_block_liveout(&block, liveout[end_inst].clone().to_vec());
247
    }
248 249
}

250
// from Tailoring Graph-coloring Register Allocation For Runtime Compilation, Figure 4
251
pub fn build_chaitin_briggs (cf: &mut CompiledFunction, func: &MuFunctionVersion) -> InterferenceGraph {
252
    build_live_set(cf);
253
    
254 255 256
    let mut ig = InterferenceGraph::new();
    
    // precolor machine register nodes
257
    for reg in backend::all_regs().values() {
258 259
        let reg_id = reg.extract_ssa_id().unwrap();
        let node = ig.new_node(reg_id, &func.context);
qinsoon's avatar
qinsoon committed
260 261 262 263

        let precolor = backend::get_color_for_precolroed(reg_id);

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

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

            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));
                }
            }
393 394 395 396 397 398
        }
    }
    
    ig
}

399
// from tony's code src/RegAlloc/Liveness.java
400
// this function is no longer used
qinsoon's avatar
qinsoon committed
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 530 531 532 533 534 535 536 537 538
//#[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
//}