liveness.rs 20.6 KB
Newer Older
qinsoon's avatar
qinsoon committed
1 2
extern crate nalgebra;

qinsoon's avatar
qinsoon committed
3
use compiler::machine_code::CompiledFunction;
4
use ast::ir::*;
qinsoon's avatar
qinsoon committed
5 6
use ast::types;
use compiler::backend;
7
use utils::vec_utils;
8
use utils::LinkedHashSet;
9 10

use std::collections::LinkedList;
qinsoon's avatar
qinsoon committed
11 12 13 14
use std::collections::{HashMap, HashSet};

use self::nalgebra::DMatrix;

15 16
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct Node(usize);
17
#[derive(Clone, Debug, PartialEq)]
qinsoon's avatar
qinsoon committed
18 19
pub struct NodeProperty {
    color: Option<MuID>,
20 21 22
    group: backend::RegGroup,
    temp: MuID,
    spill_cost: f32
qinsoon's avatar
qinsoon committed
23 24 25
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct Move{pub from: Node, pub to: Node}
26 27

pub struct InterferenceGraph {
qinsoon's avatar
qinsoon committed
28
    nodes: HashMap<MuID, Node>,
qinsoon's avatar
qinsoon committed
29
    nodes_property: HashMap<Node, NodeProperty>,
qinsoon's avatar
qinsoon committed
30 31 32
    
    matrix: Option<DMatrix<bool>>,
    
qinsoon's avatar
qinsoon committed
33
    moves: HashSet<Move>,
34 35 36 37
}

impl InterferenceGraph {
    fn new() -> InterferenceGraph {
qinsoon's avatar
qinsoon committed
38 39
        InterferenceGraph {
            nodes: HashMap::new(),
qinsoon's avatar
qinsoon committed
40
            nodes_property: HashMap::new(),
qinsoon's avatar
qinsoon committed
41 42 43 44 45
            matrix: None,
            moves: HashSet::new()
        }
    }
    
qinsoon's avatar
qinsoon committed
46 47 48 49
    fn new_node(&mut self, reg_id: MuID, context: &FunctionContext) -> Node {
        let entry = context.get_value(reg_id).unwrap();
        
        if !self.nodes.contains_key(&reg_id) {
qinsoon's avatar
qinsoon committed
50
            let index = self.nodes.len();
51
            let node = Node(index);
qinsoon's avatar
qinsoon committed
52 53 54 55 56 57
            
            // add the node
            self.nodes.insert(reg_id, node.clone());
            
            // add node property
            let group = {
qinsoon's avatar
qinsoon committed
58
                let ref ty = entry.ty();
qinsoon's avatar
qinsoon committed
59 60 61
                if types::is_scalar(ty) {
                    if types::is_fp(ty) {
                        backend::RegGroup::FPR
qinsoon's avatar
qinsoon committed
62 63
                    } else {
                        backend::RegGroup::GPR
qinsoon's avatar
qinsoon committed
64 65 66 67 68 69 70
                    }
                } else {
                    unimplemented!()
                }
            };
            let property = NodeProperty {
                color: None,
71 72 73
                group: group,
                temp: reg_id,
                spill_cost: 0.0f32
qinsoon's avatar
qinsoon committed
74 75
            };
            self.nodes_property.insert(node, property);
76 77 78 79 80 81 82 83 84 85
        } 
        
        
        let node = * self.nodes.get(&reg_id).unwrap();
        
        // increase node spill cost
        let property = self.nodes_property.get_mut(&node).unwrap();
        property.spill_cost += 1.0f32;
        
        node
qinsoon's avatar
qinsoon committed
86 87
    }
    
qinsoon's avatar
qinsoon committed
88
    pub fn get_node(&self, reg: MuID) -> Node {
qinsoon's avatar
qinsoon committed
89
        match self.nodes.get(&reg) {
qinsoon's avatar
qinsoon committed
90
            Some(index) => *index,
qinsoon's avatar
qinsoon committed
91
            None => panic!("do not have a node for {}", reg)
qinsoon's avatar
qinsoon committed
92 93 94
        }
    }
    
95 96 97 98 99 100 101 102
    pub fn temps(&self) -> Vec<MuID>{
        let mut ret = vec![];
        for reg in self.nodes.keys() {
            ret.push(*reg);
        }
        ret
    }
    
qinsoon's avatar
qinsoon committed
103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118
    pub fn nodes(&self) -> Vec<Node> {
        let mut ret = vec![];
        for node in self.nodes.values() {
            ret.push(node.clone());
        }
        ret
    }
    
    pub fn moves(&self) -> &HashSet<Move> {
        &self.moves
    }
    
    pub fn n_nodes(&self) -> usize {
        self.nodes.len()
    }
    
qinsoon's avatar
qinsoon committed
119 120 121 122 123
    fn init_graph(&mut self) {
        let len = self.nodes.len();
        self.matrix = Some(DMatrix::from_element(len, len, false));
    }
    
qinsoon's avatar
qinsoon committed
124 125
    fn add_move(&mut self, src: Node, dst: Node) {
        self.moves.insert(Move{from: src, to: dst});
126
    }
qinsoon's avatar
qinsoon committed
127 128 129 130 131

    pub fn is_same_group(&self, node1: Node, node2: Node) -> bool {
        self.nodes_property.get(&node1).unwrap().group
            == self.nodes_property.get(&node2).unwrap().group
    }
132
    
qinsoon's avatar
qinsoon committed
133
    pub fn add_interference_edge(&mut self, from: Node, to: Node) {
qinsoon's avatar
qinsoon committed
134 135 136 137 138 139
        self.matrix.as_mut().unwrap()[(from.0, to.0)] = true;
    }

    pub fn is_interferenced_with(&self, node1: Node, node2: Node) -> bool {
        self.matrix.as_ref().unwrap()[(node1.0, node2.0)]
        || self.matrix.as_ref().unwrap()[(node2.0, node1.0)]
qinsoon's avatar
qinsoon committed
140 141
    }
    
142
    pub fn color_node(&mut self, node: Node, color: MuID) {
qinsoon's avatar
qinsoon committed
143
        self.nodes_property.get_mut(&node).unwrap().color = Some(color);
qinsoon's avatar
qinsoon committed
144 145
    }
    
qinsoon's avatar
qinsoon committed
146 147 148 149
    pub fn is_colored(&self, node: Node) -> bool {
        self.nodes_property.get(&node).unwrap().color.is_some()
    }
    
150 151 152 153
    pub fn get_color_of(&self, node: Node) -> Option<MuID> {
        self.nodes_property.get(&node).unwrap().color
    }
    
qinsoon's avatar
qinsoon committed
154 155
    pub fn get_group_of(&self, node: Node) -> backend::RegGroup {
        self.nodes_property.get(&node).unwrap().group
qinsoon's avatar
qinsoon committed
156 157
    }
    
158 159 160 161 162 163 164 165
    pub fn get_temp_of(&self, node: Node) -> MuID {
        self.nodes_property.get(&node).unwrap().temp
    }
    
    pub fn get_spill_cost(&self, node: Node) -> f32 {
        self.nodes_property.get(&node).unwrap().spill_cost
    }
    
166
    fn is_same_node(&self, node1: Node, node2: Node) -> bool {
qinsoon's avatar
qinsoon committed
167
        node1 == node2
qinsoon's avatar
qinsoon committed
168 169
    }
    
qinsoon's avatar
qinsoon committed
170
    pub fn is_adj(&self, from: Node, to: Node) -> bool {
171 172
        let ref matrix = self.matrix.as_ref().unwrap();
        
173
        matrix[(from.0, to.0)] || matrix[(to.0, from.0)]
qinsoon's avatar
qinsoon committed
174 175
    }
    
176 177 178 179 180 181 182 183 184 185 186 187 188
    pub fn outedges_of(&self, node: Node) -> Vec<Node> {
        let mut ret = vec![];
        let matrix = self.matrix.as_ref().unwrap();
        
        for i in 0..self.nodes.len() {
            if matrix[(node.0, i)] {
                ret.push(Node(i));
            }
        }
        
        ret
    }
    
qinsoon's avatar
qinsoon committed
189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214
    pub fn outdegree_of(&self, node: Node) -> usize {
        let mut count = 0;
        for i in 0..self.nodes.len() {
            if self.matrix.as_ref().unwrap()[(node.0, i)] {
                count += 1;
            }
        }
        
        count
    }
    
    pub fn indegree_of(&self, node: Node) -> usize {
        let mut count = 0;
        for i in 0..self.nodes.len() {
            if self.matrix.as_ref().unwrap()[(i, node.0)] {
                count += 1;
            }
        }
        
        count
    }
    
    pub fn degree_of(&self, node: Node) -> usize {
        self.outdegree_of(node) + self.indegree_of(node)
    }
    
qinsoon's avatar
qinsoon committed
215
    pub fn print(&self, context: &FunctionContext) {
216 217 218
        println!("");
        println!("Interference Graph");

qinsoon's avatar
qinsoon committed
219 220
        println!("nodes:");
        for id in self.nodes.keys() {
qinsoon's avatar
qinsoon committed
221 222
            let val = context.get_value(*id).unwrap().value();
            println!("Reg {} -> {:?}", val, self.nodes.get(&id).unwrap());
qinsoon's avatar
qinsoon committed
223 224
        }

225
        println!("color:");
qinsoon's avatar
qinsoon committed
226 227 228 229
        for (node, color) in self.nodes_property.iter() {
            let node_val = context.get_value(self.get_temp_of(*node)).unwrap().value();
            let color_val = context.get_value(color.temp).unwrap().value();
            println!("Reg {} of {:?} -> Color/Reg {}", node_val, node, color_val);
230 231 232
        }
        println!("moves:");
        for mov in self.moves.iter() {
qinsoon's avatar
qinsoon committed
233
            println!("Move {:?} -> {:?}", mov.from, mov.to);
234 235 236
        }
        println!("graph:");
        {
qinsoon's avatar
qinsoon committed
237 238
            let node_to_reg_id = {
                let mut ret : HashMap<Node, MuID> = HashMap::new();
239
                
qinsoon's avatar
qinsoon committed
240 241
                for reg in self.nodes.keys() {
                    ret.insert(*self.nodes.get(reg).unwrap(), *reg);
242 243 244 245 246 247 248 249 250
                }
                
                ret 
            };
            
            let matrix = self.matrix.as_ref().unwrap();
            for i in 0..matrix.ncols() {
                for j in 0..matrix.nrows() {
                    if matrix[(i, j)] {
251 252
                        let from_node = node_to_reg_id.get(&Node(i)).unwrap();
                        let to_node = node_to_reg_id.get(&Node(j)).unwrap();
qinsoon's avatar
qinsoon committed
253 254 255 256 257

                        let from_val = context.get_value(*from_node).unwrap().value();
                        let to_val = context.get_value(*to_node).unwrap().value();

                        println!("Reg {} -> Reg {}", from_val, to_val);
258 259 260 261 262 263
                    }
                }
            }
        }
        println!("");
    }
qinsoon's avatar
qinsoon committed
264 265
}

qinsoon's avatar
qinsoon committed
266
pub fn is_machine_reg(reg: MuID) -> bool {
qinsoon's avatar
qinsoon committed
267
    if reg < MACHINE_ID_END {
qinsoon's avatar
qinsoon committed
268 269 270
        true
    } else {
        false
271 272 273
    }
}

274 275
#[allow(unused_variables)]
fn build_live_set(cf: &mut CompiledFunction, func: &MuFunctionVersion) {
qinsoon's avatar
qinsoon committed
276
    let n_insts = cf.mc().number_of_insts();
277
    
278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293
    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
294
            in_set_new.extend_from_slice(&cf.mc().get_inst_reg_uses(n));
295 296
            // (2) diff = out[n] - def[n]
            let mut diff = liveout[n].to_vec();
qinsoon's avatar
qinsoon committed
297
            for def in cf.mc().get_inst_reg_defines(n) {
qinsoon's avatar
qinsoon committed
298
                vec_utils::remove_value(&mut diff, def);
299 300 301 302 303 304 305 306 307 308
            }
            // (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
309
            for s in cf.mc().get_succs(n) {
310 311 312 313 314 315 316 317 318 319 320 321 322
                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
323 324 325 326
    for block in cf.mc().get_all_blocks().to_vec() {
        if cf.mc().get_ir_block_livein(&block).is_none() {
            let start_inst = cf.mc().get_block_range(&block).unwrap().start;
            cf.mc_mut().set_ir_block_livein(&block, livein[start_inst].to_vec());
327 328
        }
        
qinsoon's avatar
qinsoon committed
329 330 331
        if cf.mc().get_ir_block_liveout(&block).is_none() {
            let end_inst = cf.mc().get_block_range(&block).unwrap().end;
            cf.mc_mut().set_ir_block_liveout(&block, liveout[end_inst].to_vec());
332 333
        }
    }
334 335
}

336
// from Tailoring Graph-coloring Register Allocation For Runtime Compilation, Figure 4
337 338 339
pub fn build_chaitin_briggs (cf: &mut CompiledFunction, func: &MuFunctionVersion) -> InterferenceGraph {
    build_live_set(cf, func);
    
340 341 342
    let mut ig = InterferenceGraph::new();
    
    // precolor machine register nodes
343
    for reg in backend::all_regs().values() {
344 345 346 347 348 349
        let reg_id = reg.extract_ssa_id().unwrap();
        let node = ig.new_node(reg_id, &func.context);
        ig.color_node(node, reg_id);
    }
    
    // Initialize and creates nodes for all the involved temps/regs
qinsoon's avatar
qinsoon committed
350 351
    for i in 0..cf.mc().number_of_insts() {
        for reg_id in cf.mc().get_inst_reg_defines(i) {
352 353 354
            ig.new_node(reg_id, &func.context);
        }
        
qinsoon's avatar
qinsoon committed
355
        for reg_id in cf.mc().get_inst_reg_uses(i) {
356 357 358 359 360
            ig.new_node(reg_id, &func.context);
        }
    }
    
    // all nodes has been added, we init graph (create adjacency matrix)
361
    ig.init_graph();
362
    
qinsoon's avatar
qinsoon committed
363
    for block in cf.mc().get_all_blocks() {
364
        // Current_Live(B) = LiveOut(B)
qinsoon's avatar
qinsoon committed
365
        let mut current_live = LinkedHashSet::from_vec(match cf.mc().get_ir_block_liveout(&block) {
366 367 368
            Some(liveout) => liveout.to_vec(),
            None => panic!("cannot find liveout for block {}", block)
        });
qinsoon's avatar
qinsoon committed
369 370 371 372 373 374
        if cfg!(debug_assertions) {
            trace!("Block{}: live out", block);
            for ele in current_live.iter() {
                trace!("{}", func.context.get_temp_display(*ele));
            }
        }
375
        
qinsoon's avatar
qinsoon committed
376
        let range = cf.mc().get_block_range(&block);
377
        if range.is_none() {
qinsoon's avatar
qinsoon committed
378
            warn!("Block{}: has no range (no instructions?)", block);
379 380
            continue;
        }
qinsoon's avatar
qinsoon committed
381
        trace!("Block{}: range = {:?}", block, range.as_ref().unwrap());
382 383 384
        
        // for every inst I in reverse order
        for i in range.unwrap().rev() {
qinsoon's avatar
qinsoon committed
385 386 387 388 389 390 391
            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));
                }
            }

392
            let src : Option<MuID> = {
qinsoon's avatar
qinsoon committed
393 394 395
                if cf.mc().is_move(i) {
                    let src = cf.mc().get_inst_reg_uses(i);
                    let dst = cf.mc().get_inst_reg_defines(i);
396
                    
qinsoon's avatar
qinsoon committed
397 398 399
                    // src:  reg/imm/mem
                    // dest: reg/mem
                    // we dont care if src/dest is mem
qinsoon's avatar
qinsoon committed
400
                    if cf.mc().is_using_mem_op(i) {
401
                        None
qinsoon's avatar
qinsoon committed
402 403 404 405
                    } else {
                        if src.len() == 1 {
                            let node1 = ig.get_node(src[0]);
                            let node2 = ig.get_node(dst[0]);
qinsoon's avatar
qinsoon committed
406 407 408
                            trace!("add move between {} and {}",
                                   func.context.get_temp_display(src[0]),
                                   func.context.get_temp_display(dst[0]));
qinsoon's avatar
qinsoon committed
409 410 411 412 413 414
                            ig.add_move(node1, node2);
                            
                            Some(src[0])
                        } else {
                            None
                        }
415 416 417 418 419
                    }
                } else {
                    None
                }
            };
qinsoon's avatar
qinsoon committed
420
            trace!("Block{}: Inst{}: src={:?}", block, i, src);
421 422
            
            // for every definition D in I
qinsoon's avatar
qinsoon committed
423
            for d in cf.mc().get_inst_reg_defines(i) {
qinsoon's avatar
qinsoon committed
424
                trace!("Block{}: Inst{}: for definition {}", block, i, func.context.get_temp_display(d));
425 426 427
                // 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
428 429 430
                    trace!("Block{}: Inst{}: for each live {}",
                           block, i,
                           func.context.get_temp_display(*e));
431
                    if src.is_none() || (src.is_some() && *e != src.unwrap()) {
qinsoon's avatar
qinsoon committed
432
                        let from = ig.get_node(d);
433 434
                        let to = ig.get_node(*e);
                        
qinsoon's avatar
qinsoon committed
435
                        if !ig.is_same_node(from, to) &&ig.is_same_group(from, to) && !ig.is_adj(from, to) {
436
                            if !ig.is_colored(from) {
qinsoon's avatar
qinsoon committed
437 438 439 440
                                trace!("Block{}: Inst{}: add interference between {} and {}",
                                       block, i,
                                       func.context.get_temp_display(d),
                                       func.context.get_temp_display(*e));
441 442 443
                                ig.add_interference_edge(from, to);
                            }
                            if !ig.is_colored(to) {
qinsoon's avatar
qinsoon committed
444 445 446 447
                                trace!("Block{}: Inst{}: add interference between {} and {}",
                                       block, i,
                                       func.context.get_temp_display(*e),
                                       func.context.get_temp_display(d));
448 449 450 451 452 453 454 455
                                ig.add_interference_edge(to, from);
                            }
                        }
                    }
                }
            }
            
            // for every definition D in I
qinsoon's avatar
qinsoon committed
456
            for d in cf.mc().get_inst_reg_defines(i) {
qinsoon's avatar
qinsoon committed
457 458 459
                trace!("Block{}: Inst{}: remove define {} from current_live",
                       block, i,
                       func.context.get_temp_display(d));
460
                // remove D from Current_Live
qinsoon's avatar
qinsoon committed
461
                current_live.remove(&d);
462 463 464
            }
            
            // for every use U in I
qinsoon's avatar
qinsoon committed
465
            for u in cf.mc().get_inst_reg_uses(i) {
qinsoon's avatar
qinsoon committed
466 467 468
                trace!("Block{}: Inst{}: add use {} to current_live",
                       block, i,
                       func.context.get_temp_display(u));
469
                // add U to Current_live
qinsoon's avatar
qinsoon committed
470
                current_live.insert(u);
471
            }
qinsoon's avatar
qinsoon committed
472 473 474 475 476 477 478

            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));
                }
            }
479 480 481 482 483 484
        }
    }
    
    ig
}

485
// from tony's code src/RegAlloc/Liveness.java
486 487
// this function is no longer used
#[allow(dead_code)]
488
pub fn build (cf: &CompiledFunction, func: &MuFunctionVersion) -> InterferenceGraph {
489 490
    let mut ig = InterferenceGraph::new();
    
qinsoon's avatar
qinsoon committed
491
    // precolor machine register nodes
492
    for reg in backend::all_regs().values() {
qinsoon's avatar
qinsoon committed
493 494 495 496
        let reg_id = reg.extract_ssa_id().unwrap();
        let node = ig.new_node(reg_id, &func.context);
        ig.color_node(node, reg_id);
    }
497 498
    
    // Liveness Analysis
qinsoon's avatar
qinsoon committed
499
    let n_insts = cf.mc().number_of_insts();
500 501 502 503 504 505 506 507 508
    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];
        
qinsoon's avatar
qinsoon committed
509
        for reg_id in cf.mc().get_inst_reg_defines(i) {
qinsoon's avatar
qinsoon committed
510
            ig.new_node(reg_id, &func.context);
511 512
        }
        
qinsoon's avatar
qinsoon committed
513
        for reg_id in cf.mc().get_inst_reg_uses(i) {
qinsoon's avatar
qinsoon committed
514
            ig.new_node(reg_id, &func.context);
qinsoon's avatar
qinsoon committed
515 516
            
            in_set.push(reg_id);
517 518 519 520 521
        }
        
        work_list.push_front(i);
    }
    
qinsoon's avatar
qinsoon committed
522 523 524 525
    // all nodes has been added, we init graph (create adjacency matrix)
    ig.init_graph();
    
    // compute liveIn and liveOut iteratively
526
    trace!("build live outs");
527 528
    while !work_list.is_empty() {
        let n = work_list.pop_front().unwrap();
529
        trace!("build liveout for #{}", n);
530
        let ref mut out_set = live_out[n];
qinsoon's avatar
qinsoon committed
531 532
        
        // out = union(in[succ]) for all succs
qinsoon's avatar
qinsoon committed
533
        for succ in cf.mc().get_succs(n) {
534
            trace!("add successor's livein {:?} to #{}", &live_in[*succ], n); 
535
            vec_utils::add_all(out_set, &live_in[*succ]);
qinsoon's avatar
qinsoon committed
536 537 538 539
        }
        
        // in = use(i.e. live_in) + (out - def) 
        let mut diff = out_set.clone();
qinsoon's avatar
qinsoon committed
540
        for def in cf.mc().get_inst_reg_defines(n) {
qinsoon's avatar
qinsoon committed
541 542
            vec_utils::remove_value(&mut diff, def);
            trace!("removing def: {}", def);
543
            trace!("diff = {:?}", diff);
qinsoon's avatar
qinsoon committed
544
        }
545
        trace!("out - def = {:?}", diff);
qinsoon's avatar
qinsoon committed
546 547 548
        
        if !diff.is_empty() {
            let ref mut in_set = live_in[n];
549
            trace!("in = (use) {:?}", in_set);
qinsoon's avatar
qinsoon committed
550
            
551
            if vec_utils::add_all(in_set, &diff) {
qinsoon's avatar
qinsoon committed
552
                for p in cf.mc().get_preds(n) {
qinsoon's avatar
qinsoon committed
553 554 555 556
                    work_list.push_front(*p);
                }
            }
        }
557
        trace!("in = use + (out - def) = {:?}", live_in[n]);
558 559 560 561 562 563 564 565 566
    }
    
    // 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);
        }
qinsoon's avatar
qinsoon committed
567 568 569 570 571 572 573
    }
    
    // build interference graph
    for n in 0..n_insts {
        let ref mut live = live_out[n];
        
        let src : Option<MuID> = {
qinsoon's avatar
qinsoon committed
574 575 576
            if cf.mc().is_move(n) {
                let src = cf.mc().get_inst_reg_uses(n);
                let dst = cf.mc().get_inst_reg_defines(n);
qinsoon's avatar
qinsoon committed
577
                
578 579
                // src may be an immediate number
                // but dest is definitly a register
qinsoon's avatar
qinsoon committed
580 581
                debug_assert!(dst.len() == 1);
                
582
                if src.len() == 1 {
qinsoon's avatar
qinsoon committed
583 584 585
                    let node1 = ig.get_node(src[0]);
                    let node2 = ig.get_node(dst[0]);
                    ig.add_move(node1, node2);
586 587 588 589 590
                    
                    Some(src[0])
                } else {
                    None
                }
qinsoon's avatar
qinsoon committed
591 592 593 594 595
            } else {
                None
            }
        };
        
qinsoon's avatar
qinsoon committed
596
        for d in cf.mc().get_inst_reg_defines(n) {
qinsoon's avatar
qinsoon committed
597 598
            for t in live.iter() {
                if src.is_none() || (src.is_some() && *t != src.unwrap()) {
qinsoon's avatar
qinsoon committed
599
                    let from = ig.get_node(d);
600
                    let to = ig.get_node(*t);
qinsoon's avatar
qinsoon committed
601 602
                    
                    if !ig.is_same_node(from, to) && !ig.is_adj(from, to) {
qinsoon's avatar
qinsoon committed
603
                        if !ig.is_colored(from) {
qinsoon's avatar
qinsoon committed
604 605
                            ig.add_interference_edge(from, to);
                        }
qinsoon's avatar
qinsoon committed
606
                        if !ig.is_colored(to) {
qinsoon's avatar
qinsoon committed
607 608 609 610 611 612 613
                            ig.add_interference_edge(to, from);
                        }
                    }
                }
            }
        }
        
qinsoon's avatar
qinsoon committed
614
        for d in cf.mc().get_inst_reg_defines(n) {
qinsoon's avatar
qinsoon committed
615
            vec_utils::remove_value(live, d);
qinsoon's avatar
qinsoon committed
616 617
        }
        
qinsoon's avatar
qinsoon committed
618
        for u in cf.mc().get_inst_reg_uses(n) {
qinsoon's avatar
qinsoon committed
619
            live.push(u);
qinsoon's avatar
qinsoon committed
620 621 622 623
        }
    }
    
    ig
624
}