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.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
}