Research GitLab has introduced a user quota limitation. The new rule limits each user to have 50 Gb. The quota doesn't restrict group projects. If you have any concern with this, please talk to CECS Gitlab Admin at N110 (b) CSIT building.

liveness.rs 20.3 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
}

266 267
#[allow(unused_variables)]
fn build_live_set(cf: &mut CompiledFunction, func: &MuFunctionVersion) {
qinsoon's avatar
qinsoon committed
268
    let n_insts = cf.mc().number_of_insts();
269
    
270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285
    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
286
            in_set_new.extend_from_slice(&cf.mc().get_inst_reg_uses(n));
287 288
            // (2) diff = out[n] - def[n]
            let mut diff = liveout[n].to_vec();
qinsoon's avatar
qinsoon committed
289
            for def in cf.mc().get_inst_reg_defines(n) {
qinsoon's avatar
qinsoon committed
290
                vec_utils::remove_value(&mut diff, def);
291 292 293 294 295 296 297 298 299 300
            }
            // (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
301
            for s in cf.mc().get_succs(n) {
302 303 304 305 306 307 308 309 310 311 312 313 314
                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
315
    for block in cf.mc().get_all_blocks().to_vec() {
316 317 318 319 320
        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());
321
    }
322 323
}

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

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

            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));
                }
            }
467 468 469 470 471 472
        }
    }
    
    ig
}

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