WARNING! Access to this system is limited to authorised users only.
Unauthorised users may be subject to prosecution.
Unauthorised access to this system is a criminal offence under Australian law (Federal Crimes Act 1914 Part VIA)
It is a criminal offence to:
(1) Obtain access to data without authority. -Penalty 2 years imprisonment.
(2) Damage, delete, alter or insert data without authority. -Penalty 10 years imprisonment.
User activity is monitored and recorded. Anyone using this system expressly consents to such monitoring and recording.

To protect your data, the CISO officer has suggested users to enable 2FA as soon as possible.
Currently 2.7% of users enabled 2FA.

liveness.rs 20 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
use compiler::backend;
6
use utils::vec_utils;
7
use utils::LinkedHashSet;
8

qinsoon's avatar
qinsoon committed
9
10
11
12
use std::collections::{HashMap, HashSet};

use self::nalgebra::DMatrix;

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

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

impl InterferenceGraph {
    fn new() -> InterferenceGraph {
qinsoon's avatar
qinsoon committed
36
37
        InterferenceGraph {
            nodes: HashMap::new(),
qinsoon's avatar
qinsoon committed
38
            nodes_property: HashMap::new(),
qinsoon's avatar
qinsoon committed
39
40
41
42
43
            matrix: None,
            moves: HashSet::new()
        }
    }
    
qinsoon's avatar
qinsoon committed
44
45
46
47
    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
48
            let index = self.nodes.len();
49
            let node = Node(index);
qinsoon's avatar
qinsoon committed
50
51
52
53
54
            
            // add the node
            self.nodes.insert(reg_id, node.clone());
            
            // add node property
55
            let group = backend::RegGroup::get(entry.ty());
qinsoon's avatar
qinsoon committed
56
57
            let property = NodeProperty {
                color: None,
58
59
60
                group: group,
                temp: reg_id,
                spill_cost: 0.0f32
qinsoon's avatar
qinsoon committed
61
62
            };
            self.nodes_property.insert(node, property);
63
64
65
66
67
68
69
70
71
72
        } 
        
        
        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
73
74
    }
    
qinsoon's avatar
qinsoon committed
75
    pub fn get_node(&self, reg: MuID) -> Node {
qinsoon's avatar
qinsoon committed
76
        match self.nodes.get(&reg) {
qinsoon's avatar
qinsoon committed
77
            Some(index) => *index,
qinsoon's avatar
qinsoon committed
78
            None => panic!("do not have a node for {}", reg)
qinsoon's avatar
qinsoon committed
79
80
81
        }
    }
    
82
83
84
85
86
87
88
89
    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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
    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
106
107
108
109
110
    fn init_graph(&mut self) {
        let len = self.nodes.len();
        self.matrix = Some(DMatrix::from_element(len, len, false));
    }
    
qinsoon's avatar
qinsoon committed
111
112
    fn add_move(&mut self, src: Node, dst: Node) {
        self.moves.insert(Move{from: src, to: dst});
113
    }
qinsoon's avatar
qinsoon committed
114
115
116
117
118

    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
    }
119
    
qinsoon's avatar
qinsoon committed
120
    pub fn add_interference_edge(&mut self, from: Node, to: Node) {
qinsoon's avatar
qinsoon committed
121
122
123
124
125
126
        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
127
128
    }
    
129
    pub fn color_node(&mut self, node: Node, color: MuID) {
qinsoon's avatar
qinsoon committed
130
        self.nodes_property.get_mut(&node).unwrap().color = Some(color);
qinsoon's avatar
qinsoon committed
131
132
    }
    
qinsoon's avatar
qinsoon committed
133
134
135
136
    pub fn is_colored(&self, node: Node) -> bool {
        self.nodes_property.get(&node).unwrap().color.is_some()
    }
    
137
138
139
140
    pub fn get_color_of(&self, node: Node) -> Option<MuID> {
        self.nodes_property.get(&node).unwrap().color
    }
    
qinsoon's avatar
qinsoon committed
141
142
    pub fn get_group_of(&self, node: Node) -> backend::RegGroup {
        self.nodes_property.get(&node).unwrap().group
qinsoon's avatar
qinsoon committed
143
144
    }
    
145
146
147
148
149
150
151
152
    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
    }
    
153
    fn is_same_node(&self, node1: Node, node2: Node) -> bool {
qinsoon's avatar
qinsoon committed
154
        node1 == node2
qinsoon's avatar
qinsoon committed
155
156
    }
    
qinsoon's avatar
qinsoon committed
157
    pub fn is_adj(&self, from: Node, to: Node) -> bool {
158
159
        let ref matrix = self.matrix.as_ref().unwrap();
        
160
        matrix[(from.0, to.0)] || matrix[(to.0, from.0)]
qinsoon's avatar
qinsoon committed
161
162
    }
    
163
164
165
166
167
168
169
170
171
172
173
174
175
    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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
    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 {
qinsoon's avatar
fix    
qinsoon committed
199
        self.outdegree_of(node)
qinsoon's avatar
qinsoon committed
200
201
    }
    
qinsoon's avatar
qinsoon committed
202
    pub fn print(&self, context: &FunctionContext) {
203
204
205
        println!("");
        println!("Interference Graph");

qinsoon's avatar
qinsoon committed
206
207
        println!("nodes:");
        for id in self.nodes.keys() {
qinsoon's avatar
qinsoon committed
208
209
            let val = context.get_value(*id).unwrap().value();
            println!("Reg {} -> {:?}", val, self.nodes.get(&id).unwrap());
qinsoon's avatar
qinsoon committed
210
211
        }

212
        println!("color:");
qinsoon's avatar
qinsoon committed
213
214
215
216
        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);
217
218
219
        }
        println!("moves:");
        for mov in self.moves.iter() {
qinsoon's avatar
qinsoon committed
220
            println!("Move {:?} -> {:?}", mov.from, mov.to);
221
222
223
        }
        println!("graph:");
        {
qinsoon's avatar
qinsoon committed
224
225
            let node_to_reg_id = {
                let mut ret : HashMap<Node, MuID> = HashMap::new();
226
                
qinsoon's avatar
qinsoon committed
227
228
                for reg in self.nodes.keys() {
                    ret.insert(*self.nodes.get(reg).unwrap(), *reg);
229
230
231
232
233
234
235
236
237
                }
                
                ret 
            };
            
            let matrix = self.matrix.as_ref().unwrap();
            for i in 0..matrix.ncols() {
                for j in 0..matrix.nrows() {
                    if matrix[(i, j)] {
238
239
                        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
240
241
242
243
244

                        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);
245
246
247
248
249
250
                    }
                }
            }
        }
        println!("");
    }
qinsoon's avatar
qinsoon committed
251
252
}

253
254
#[allow(unused_variables)]
fn build_live_set(cf: &mut CompiledFunction, func: &MuFunctionVersion) {
qinsoon's avatar
qinsoon committed
255
    let n_insts = cf.mc().number_of_insts();
256
    
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
    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
273
            in_set_new.extend_from_slice(&cf.mc().get_inst_reg_uses(n));
274
275
            // (2) diff = out[n] - def[n]
            let mut diff = liveout[n].to_vec();
qinsoon's avatar
qinsoon committed
276
            for def in cf.mc().get_inst_reg_defines(n) {
qinsoon's avatar
qinsoon committed
277
                vec_utils::remove_value(&mut diff, def);
278
279
280
281
282
283
284
285
286
287
            }
            // (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
288
            for s in cf.mc().get_succs(n) {
289
290
291
292
293
294
295
296
297
298
299
300
301
                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
302
    for block in cf.mc().get_all_blocks().to_vec() {
303
304
305
306
307
        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());
308
    }
309
310
}

311
// from Tailoring Graph-coloring Register Allocation For Runtime Compilation, Figure 4
312
313
314
pub fn build_chaitin_briggs (cf: &mut CompiledFunction, func: &MuFunctionVersion) -> InterferenceGraph {
    build_live_set(cf, func);
    
315
316
317
    let mut ig = InterferenceGraph::new();
    
    // precolor machine register nodes
318
    for reg in backend::all_regs().values() {
319
320
        let reg_id = reg.extract_ssa_id().unwrap();
        let node = ig.new_node(reg_id, &func.context);
qinsoon's avatar
qinsoon committed
321
322
323
324

        let precolor = backend::get_color_for_precolroed(reg_id);

        ig.color_node(node, precolor);
325
326
327
    }
    
    // Initialize and creates nodes for all the involved temps/regs
qinsoon's avatar
qinsoon committed
328
329
    for i in 0..cf.mc().number_of_insts() {
        for reg_id in cf.mc().get_inst_reg_defines(i) {
330
331
332
            ig.new_node(reg_id, &func.context);
        }
        
qinsoon's avatar
qinsoon committed
333
        for reg_id in cf.mc().get_inst_reg_uses(i) {
334
335
336
337
338
            ig.new_node(reg_id, &func.context);
        }
    }
    
    // all nodes has been added, we init graph (create adjacency matrix)
339
    ig.init_graph();
340
    
qinsoon's avatar
qinsoon committed
341
    for block in cf.mc().get_all_blocks() {
342
        // Current_Live(B) = LiveOut(B)
qinsoon's avatar
qinsoon committed
343
        let mut current_live = LinkedHashSet::from_vec(match cf.mc().get_ir_block_liveout(&block) {
344
345
346
            Some(liveout) => liveout.to_vec(),
            None => panic!("cannot find liveout for block {}", block)
        });
qinsoon's avatar
qinsoon committed
347
348
349
350
351
352
        if cfg!(debug_assertions) {
            trace!("Block{}: live out", block);
            for ele in current_live.iter() {
                trace!("{}", func.context.get_temp_display(*ele));
            }
        }
353
        
qinsoon's avatar
qinsoon committed
354
        let range = cf.mc().get_block_range(&block);
355
        if range.is_none() {
qinsoon's avatar
qinsoon committed
356
            warn!("Block{}: has no range (no instructions?)", block);
357
358
            continue;
        }
qinsoon's avatar
qinsoon committed
359
        trace!("Block{}: range = {:?}", block, range.as_ref().unwrap());
360
361
362
        
        // for every inst I in reverse order
        for i in range.unwrap().rev() {
qinsoon's avatar
qinsoon committed
363
364
365
366
367
368
369
            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));
                }
            }

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

            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));
                }
            }
457
458
459
460
461
462
        }
    }
    
    ig
}

463
// from tony's code src/RegAlloc/Liveness.java
464
// this function is no longer used
qinsoon's avatar
qinsoon committed
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
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
//#[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
//}