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

coloring.rs 23 KB
Newer Older
1
2
extern crate hprof;

qinsoon's avatar
qinsoon committed
3
4
5
use ast::ir::*;
use compiler::backend;
use compiler::backend::reg_alloc::graph_coloring;
6
use compiler::backend::reg_alloc::graph_coloring::liveness::InterferenceGraph;
qinsoon's avatar
qinsoon committed
7
8
use compiler::machine_code::CompiledFunction;
use vm::VM;
9

10
use utils::vec_utils;
11
use utils::LinkedHashSet;
12
13
use utils::LinkedHashMap;
use std::collections::HashMap;
qinsoon's avatar
qinsoon committed
14

qinsoon's avatar
qinsoon committed
15
use std::cell::RefCell;
qinsoon's avatar
qinsoon committed
16

17
18
19
use compiler::backend::reg_alloc::graph_coloring::liveness::Move;
use compiler::backend::reg_alloc::graph_coloring::petgraph::graph::NodeIndex;

qinsoon's avatar
qinsoon committed
20
const COALESCING : bool = true;
21

qinsoon's avatar
qinsoon committed
22
23
24
25
26
pub struct GraphColoring<'a> {
    pub func: &'a mut MuFunctionVersion,
    pub cf: &'a mut CompiledFunction,
    pub vm: &'a VM,

27
    pub ig: InterferenceGraph,
qinsoon's avatar
qinsoon committed
28

29
    precolored: LinkedHashSet<NodeIndex>,
30
    colors: LinkedHashMap<backend::RegGroup, LinkedHashSet<MuID>>,
31
    pub colored_nodes: Vec<NodeIndex>,
qinsoon's avatar
qinsoon committed
32
    
33
    initial: Vec<NodeIndex>,
34
    degree: LinkedHashMap<NodeIndex, usize>,
qinsoon's avatar
qinsoon committed
35
    
36
    worklist_moves: Vec<Move>,
37
    movelist: LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>,
38
    active_moves: LinkedHashSet<Move>,
39
    coalesced_nodes: LinkedHashSet<NodeIndex>,
40
41
    coalesced_moves: LinkedHashSet<Move>,
    constrained_moves: LinkedHashSet<Move>,
42
    alias: LinkedHashMap<NodeIndex, NodeIndex>,
qinsoon's avatar
qinsoon committed
43
    
44
    worklist_spill: Vec<NodeIndex>,
45
    spillable: LinkedHashMap<MuID, bool>,
46
    spilled_nodes: Vec<NodeIndex>,
47
    
48
    worklist_freeze: LinkedHashSet<NodeIndex>,
49
    frozen_moves: LinkedHashSet<Move>,
50
    
51
52
    worklist_simplify: LinkedHashSet<NodeIndex>,
    select_stack: Vec<NodeIndex>
qinsoon's avatar
qinsoon committed
53
54
}

qinsoon's avatar
qinsoon committed
55
impl <'a> GraphColoring<'a> {
56
    pub fn start (func: &'a mut MuFunctionVersion, cf: &'a mut CompiledFunction, vm: &'a VM) -> GraphColoring<'a> {
57
        trace!("Initializing coloring allocator...");
qinsoon's avatar
qinsoon committed
58
59
        cf.mc().trace_mc();

qinsoon's avatar
qinsoon committed
60
61
        let ig = graph_coloring::build_inteference_graph(cf, func);

62
        let coloring = GraphColoring {
qinsoon's avatar
qinsoon committed
63
64
65
66
67
            func: func,
            cf: cf,
            vm: vm,

            ig: ig,
qinsoon's avatar
qinsoon committed
68

69
            precolored: LinkedHashSet::new(),
70
            colors: {
71
                let mut map = LinkedHashMap::new();
72
73
                map.insert(backend::RegGroup::GPR, LinkedHashSet::new());
                map.insert(backend::RegGroup::FPR, LinkedHashSet::new());
74
75
76
                map
            },
            colored_nodes: Vec::new(),
qinsoon's avatar
qinsoon committed
77
            
78
            initial: Vec::new(),
79
            degree: LinkedHashMap::new(),
qinsoon's avatar
qinsoon committed
80
            
81
            worklist_moves: Vec::new(),
82
            movelist: LinkedHashMap::new(),
83
84
85
86
            active_moves: LinkedHashSet::new(),
            coalesced_nodes: LinkedHashSet::new(),
            coalesced_moves: LinkedHashSet::new(),
            constrained_moves: LinkedHashSet::new(),
87
            alias: LinkedHashMap::new(),
qinsoon's avatar
qinsoon committed
88
            
89
            worklist_spill: Vec::new(),
90
            spillable: LinkedHashMap::new(),
91
92
            spilled_nodes: Vec::new(),
            
93
94
            worklist_freeze: LinkedHashSet::new(),
            frozen_moves: LinkedHashSet::new(),
95
            
96
            worklist_simplify: LinkedHashSet::new(),
97
            select_stack: Vec::new()
qinsoon's avatar
qinsoon committed
98
99
        };
        
qinsoon's avatar
qinsoon committed
100
        coloring.regalloc()
qinsoon's avatar
qinsoon committed
101
    }
qinsoon's avatar
qinsoon committed
102

103
    fn display_node(&self, node: NodeIndex) -> String {
qinsoon's avatar
qinsoon committed
104
105
106
107
108
109
110
111
112
113
114
        let id = self.ig.get_temp_of(node);
        self.display_id(id)
    }

    fn display_id(&self, id: MuID) -> String {
        self.func.context.get_temp_display(id)
    }

    fn display_move(&self, m: Move) -> String {
        format!("Move: {} -> {}", self.display_node(m.from), self.display_node(m.to))
    }
qinsoon's avatar
qinsoon committed
115
    
116
    fn regalloc(mut self) -> GraphColoring<'a> {
qinsoon's avatar
qinsoon committed
117
        trace!("---InterenceGraph---");
118
119
        let _p = hprof::enter("regalloc: graph coloring");

qinsoon's avatar
qinsoon committed
120
        self.ig.print(&self.func.context);
qinsoon's avatar
qinsoon committed
121
        
qinsoon's avatar
qinsoon committed
122
        // precolor for all machine registers
123
        for reg in backend::all_regs().values() {
124
125
126
127
128
            let reg_id = reg.extract_ssa_id().unwrap();
            let node = self.ig.get_node(reg_id);
            self.precolored.insert(node);
        }
        
qinsoon's avatar
qinsoon committed
129
        // put usable registers as available colors
130
        for reg in backend::all_usable_regs().iter() {
qinsoon's avatar
qinsoon committed
131
            let reg_id = reg.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
132
133
            let group = backend::pick_group_for_reg(reg_id);
            self.colors.get_mut(&group).unwrap().insert(reg_id);
qinsoon's avatar
qinsoon committed
134
135
136
137
        }
        
        for node in self.ig.nodes() {
            if !self.ig.is_colored(node) {
138
                self.initial.push(node);
139
                let outdegree = self.ig.outdegree_of(node);
140
                self.degree.insert(node, outdegree);
qinsoon's avatar
qinsoon committed
141

qinsoon's avatar
qinsoon committed
142
                trace!("{} has a degree of {}", self.display_node(node), outdegree);
qinsoon's avatar
qinsoon committed
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
            }
        }
        
        self.build();
        self.make_work_list();
        
        while {
            if !self.worklist_simplify.is_empty() {
                self.simplify();
            } else if !self.worklist_moves.is_empty() {
                self.coalesce();
            } else if !self.worklist_freeze.is_empty() {
                self.freeze();
            } else if !self.worklist_spill.is_empty() {
                self.select_spill();
            }
            
            ! (self.worklist_simplify.is_empty()
            && self.worklist_moves.is_empty()
            && self.worklist_freeze.is_empty()
            && self.worklist_spill.is_empty())
        } {}
        
qinsoon's avatar
qinsoon committed
166
167
        self.assign_colors();

168
169
        drop(_p);

qinsoon's avatar
qinsoon committed
170
171
        if !self.spilled_nodes.is_empty() {
            trace!("spill required");
qinsoon's avatar
qinsoon committed
172
173
174
            if cfg!(debug_assertions) {
                trace!("nodes to be spilled:");
                for node in self.spilled_nodes.iter() {
qinsoon's avatar
qinsoon committed
175
                    trace!("{}", self.display_node(*node));
qinsoon's avatar
qinsoon committed
176
177
178
                }
            }

qinsoon's avatar
qinsoon committed
179
            self.rewrite_program();
qinsoon's avatar
qinsoon committed
180

qinsoon's avatar
qinsoon committed
181
            return GraphColoring::start(self.func, self.cf, self.vm);
qinsoon's avatar
qinsoon committed
182
183
        }

184
        self
qinsoon's avatar
qinsoon committed
185
186
187
    }
    
    fn build(&mut self) {
qinsoon's avatar
qinsoon committed
188
189
        if COALESCING {
            trace!("coalescing enabled, build move list");
qinsoon's avatar
qinsoon committed
190
191
192
            let ref ig = self.ig;
            let ref mut movelist = self.movelist;
            for m in ig.moves() {
qinsoon's avatar
qinsoon committed
193
                trace!("add to movelist: {:?}", m);
194
                self.worklist_moves.push(m.clone());
qinsoon's avatar
qinsoon committed
195
196
                GraphColoring::movelist_mut(movelist, m.from).borrow_mut().push(m.clone());
                GraphColoring::movelist_mut(movelist, m.to).borrow_mut().push(m.clone());
qinsoon's avatar
qinsoon committed
197
            }
qinsoon's avatar
qinsoon committed
198
199
        } else {
            trace!("coalescing disabled");
qinsoon's avatar
qinsoon committed
200
201
202
203
        }
    }
    
    fn make_work_list(&mut self) {
204
        trace!("Making work list from initials...");
qinsoon's avatar
qinsoon committed
205
        while !self.initial.is_empty() {
206
            let node = self.initial.pop().unwrap();
qinsoon's avatar
qinsoon committed
207
208
209
210
            
            if {
                // condition: degree >= K
                let degree = self.ig.degree_of(node); 
211
                let n_regs = self.n_regs_for_node(node);
qinsoon's avatar
qinsoon committed
212
213
214
                
                degree >= n_regs
            } {
qinsoon's avatar
qinsoon committed
215
                trace!("{} 's degree >= reg number limit (K), push to spill list", self.display_node(node));
216
                self.worklist_spill.push(node);
qinsoon's avatar
qinsoon committed
217
            } else if self.is_move_related(node) {
qinsoon's avatar
qinsoon committed
218
                trace!("{} is move related, push to freeze list", self.display_node(node));
qinsoon's avatar
qinsoon committed
219
220
                self.worklist_freeze.insert(node);
            } else {
qinsoon's avatar
qinsoon committed
221
                trace!("{} has small degree and not move related, push to simplify list", self.display_node(node));
qinsoon's avatar
qinsoon committed
222
223
224
225
226
                self.worklist_simplify.insert(node);
            }
        }
    }
    
227
    fn n_regs_for_node(&self, node: NodeIndex) -> usize {
228
229
230
        backend::number_of_regs_in_group(self.ig.get_group_of(node))
    }
    
231
    fn is_move_related(&mut self, node: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
232
233
234
        !self.node_moves(node).is_empty()
    }
    
235
    fn node_moves(&mut self, node: NodeIndex) -> LinkedHashSet<Move> {
236
        let mut moves = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
237
238
239
240
241
242
243
244
245
246
247
        
        // addAll(active_moves)
        for m in self.active_moves.iter() {
            moves.insert(m.clone());
        }
        
        // addAll(worklist_moves)
        for m in self.worklist_moves.iter() {
            moves.insert(m.clone());
        }
        
248
        let mut retained = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
249
        let movelist = &GraphColoring::movelist_mut(&mut self.movelist, node).borrow();
qinsoon's avatar
qinsoon committed
250
        for m in moves.iter() {
251
            if vec_utils::find_value(movelist, *m).is_some() {
qinsoon's avatar
qinsoon committed
252
253
254
255
256
257
258
                retained.insert(*m);
            }
        }
        
        retained
    }
    
qinsoon's avatar
qinsoon committed
259
260
261
    // avoid using &mut self as argument
    // in build(), we will need to mutate on self.movelist while
    // holding an immmutable reference of self(self.ig)
262
    fn movelist_mut(list: &mut LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) -> &RefCell<Vec<Move>> {
qinsoon's avatar
qinsoon committed
263
264
265
266
        GraphColoring::movelist_check(list, node);
        unsafe {GraphColoring::movelist_nocheck(list, node)}
    }
    
267
    fn movelist_check(list: &mut LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) {
qinsoon's avatar
qinsoon committed
268
        if !list.contains_key(&node) {
qinsoon's avatar
qinsoon committed
269
            list.insert(node, RefCell::new(Vec::new()));
qinsoon's avatar
qinsoon committed
270
        }
qinsoon's avatar
qinsoon committed
271
272
273
    }
    
    // allows getting the Vec<Move> without a mutable reference of the hashmap
274
    unsafe fn movelist_nocheck(list: &LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) -> &RefCell<Vec<Move>> {
qinsoon's avatar
qinsoon committed
275
        list.get(&node).unwrap()
qinsoon's avatar
qinsoon committed
276
    }
277
278
    
    fn simplify(&mut self) {
279
        // remove next element from worklist_simplify, we know its not empty
280
        let node = self.worklist_simplify.pop_front().unwrap();
281
        
qinsoon's avatar
qinsoon committed
282
        trace!("Simplifying {}", self.display_node(node));
283
284
285
        
        self.select_stack.push(node);
        
286
        for m in self.adjacent(node).iter() {
287
            self.decrement_degree(*m);
288
289
290
        }
    }
    
291
    fn adjacent(&self, n: NodeIndex) -> LinkedHashSet<NodeIndex> {
292
        let mut adj = LinkedHashSet::new();
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
        
        // add n's successors
        for s in self.ig.outedges_of(n) {
            adj.insert(s);
        }
        
        // removeAll(select_stack)
        for s in self.select_stack.iter() {
            adj.remove(s);
        }
        
        // removeAll(coalesced_nodes)
        for s in self.coalesced_nodes.iter() {
            adj.remove(s);
        }
        
        adj
    }
    
312
    fn degree(&self, n: NodeIndex) -> usize {
313
314
315
316
317
318
        match self.degree.get(&n) {
            Some(d) => *d,
            None => 0
        }
    }
    
319
    fn decrement_degree(&mut self, n: NodeIndex) {
320
321
322
323
        if self.precolored.contains(&n) {
            return;
        }
        
qinsoon's avatar
qinsoon committed
324
        trace!("decrement degree of {}", self.display_node(n));
325
        
326
        let d = self.degree(n);
327
        debug_assert!(d != 0);
328
329
        self.degree.insert(n, d - 1);
        
330
        if d == self.n_regs_for_node(n) {
qinsoon's avatar
qinsoon committed
331
            trace!("{}'s degree is K, no longer need to spill it", self.display_node(n));
332
333
            let mut nodes = self.adjacent(n);
            nodes.insert(n);
qinsoon's avatar
qinsoon committed
334
            trace!("enable moves of {:?}", nodes);
335
336
337
338
339
            self.enable_moves(nodes);
            
            vec_utils::remove_value(&mut self.worklist_spill, n);
            
            if self.is_move_related(n) {
qinsoon's avatar
qinsoon committed
340
                trace!("{} is move related, push to freeze list", self.display_node(n));
341
342
                self.worklist_freeze.insert(n);
            } else {
qinsoon's avatar
qinsoon committed
343
                trace!("{} is not move related, push to simplify list", self.display_node(n));
344
345
346
347
348
                self.worklist_simplify.insert(n);
            }
        }
    }
    
349
    fn enable_moves(&mut self, nodes: LinkedHashSet<NodeIndex>) {
350
351
352
353
        for n in nodes.iter() {
            let n = *n;
            for mov in self.node_moves(n).iter() {
                let mov = *mov;
354
355
356
357
358
359
360
361
362
                if self.active_moves.contains(&mov) {
                    self.active_moves.insert(mov);
                    self.worklist_moves.push(mov);
                }
            }
        }
    }
    
    fn coalesce(&mut self) {
qinsoon's avatar
qinsoon committed
363
364
        let m = self.worklist_moves.pop().unwrap();
        
qinsoon's avatar
qinsoon committed
365
        trace!("Coalescing on {}", self.display_move(m));
qinsoon's avatar
qinsoon committed
366
367
368

        // if they are not from the same register group, we cannot coalesce them
        if self.ig.get_group_of(m.from) != self.ig.get_group_of(m.to) {
qinsoon's avatar
qinsoon committed
369
370
371
            info!("a move instruction of two temporaries of different reigsters group");
            info!("from: {:?}, to: {:?}", m.from, m.to);

qinsoon's avatar
qinsoon committed
372
373
            return;
        }
qinsoon's avatar
qinsoon committed
374
        
qinsoon's avatar
qinsoon committed
375
376
        let x = self.get_alias(m.from);
        let y = self.get_alias(m.to);
qinsoon's avatar
qinsoon committed
377
        trace!("resolve alias: from {} to {}", self.display_node(x), self.display_node(y));
qinsoon's avatar
qinsoon committed
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
        
        let (u, v, precolored_u, precolored_v) = {
            if self.precolored.contains(&y) {
                let u = y;
                let v = x;
                let precolored_u = true;
                let precolored_v = self.precolored.contains(&v);
                
                (u, v, precolored_u, precolored_v)
            } else {
                let u = x;
                let v = y;
                let precolored_u = self.precolored.contains(&u);
                let precolored_v = self.precolored.contains(&v);
                
                (u, v, precolored_u, precolored_v)
            }
        };
qinsoon's avatar
qinsoon committed
396
        trace!("u={}, v={}, precolored_u={}, precolroed_v={}", 
qinsoon's avatar
qinsoon committed
397
398
            self.display_node(u),
            self.display_node(v),
qinsoon's avatar
qinsoon committed
399
            precolored_u, precolored_v);
qinsoon's avatar
qinsoon committed
400
401
        
        if u == v {
qinsoon's avatar
qinsoon committed
402
            trace!("u == v, coalesce the move");
qinsoon's avatar
qinsoon committed
403
404
405
406
407
            self.coalesced_moves.insert(m);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else if precolored_v || self.ig.is_adj(u, v) {
408
409
            trace!("precolored_v: {}", precolored_v);
            trace!("is_adj(u, v): {}", self.ig.is_adj(u, v));
qinsoon's avatar
qinsoon committed
410
411
            trace!("v is precolored or u,v is adjacent, the move is constrained");
            self.constrained_moves.insert(m);
qinsoon's avatar
qinsoon committed
412
413
414
415
416
417
418
419
            if !precolored_u {
                self.add_worklist(u);
            }
            if !precolored_v {
                self.add_worklist(v);
            }
        } else if (precolored_u && self.ok(u, v)) 
          || (!precolored_u && self.conservative(u, v)) {
qinsoon's avatar
qinsoon committed
420
421
422
423
            trace!("ok(u, v) = {}", self.ok(u, v));
            trace!("conservative(u, v) = {}", self.conservative(u, v));

            trace!("precolored_u&&ok(u,v) || !precolored_u&&conserv(u,v), coalesce and combine the move");
qinsoon's avatar
qinsoon committed
424
425
426
427
428
429
            self.coalesced_moves.insert(m);
            self.combine(u, v);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else {
qinsoon's avatar
qinsoon committed
430
            trace!("cannot coalesce the move");
qinsoon's avatar
qinsoon committed
431
432
433
434
            self.active_moves.insert(m);
        }
    }
    
435
    pub fn get_alias(&self, node: NodeIndex) -> NodeIndex {
qinsoon's avatar
qinsoon committed
436
437
438
439
440
441
442
        if self.coalesced_nodes.contains(&node) {
            self.get_alias(*self.alias.get(&node).unwrap())
        } else {
            node
        }
    }
    
443
    fn add_worklist(&mut self, node: NodeIndex) {
444
        if !self.is_move_related(node) && self.degree(node) < self.n_regs_for_node(node) {
qinsoon's avatar
qinsoon committed
445
446
447
448
449
            self.worklist_freeze.remove(&node);
            self.worklist_simplify.insert(node);
        }
    }
    
450
    fn ok(&self, u: NodeIndex, v: NodeIndex) -> bool {
451
452
        for t in self.adjacent(v).iter() {
            let t = *t;
453
454
455
            if !(self.degree(t) < self.n_regs_for_node(t)
                || self.precolored.contains(&t)
                || self.ig.is_adj(t, u)) {
qinsoon's avatar
qinsoon committed
456
                return false;
457
            }
qinsoon's avatar
qinsoon committed
458
459
460
461
462
        }
        
        true
    }
    
463
    fn conservative(&self, u: NodeIndex, v: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
464
465
        let adj_u = self.adjacent(u);
        let adj_v = self.adjacent(v);
466
467
468
469
470
        let nodes = {
            let mut ret = adj_u;
            ret.add_all(adj_v);
            ret
        };
qinsoon's avatar
qinsoon committed
471
472
        
        let mut k = 0;
473
        for n in nodes.iter() {
qinsoon's avatar
qinsoon committed
474
            if self.precolored.contains(n) || self.degree(*n) >= self.n_regs_for_node(*n) {
qinsoon's avatar
qinsoon committed
475
476
477
478
                k += 1;
            }
        }
        
qinsoon's avatar
qinsoon committed
479
        k < self.n_regs_for_node(u) && k < self.n_regs_for_node(v)
qinsoon's avatar
qinsoon committed
480
481
    }
    
482
    fn combine(&mut self, u: NodeIndex, v: NodeIndex) {
qinsoon's avatar
qinsoon committed
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
        if self.worklist_freeze.contains(&v) {
            self.worklist_freeze.remove(&v);
            self.coalesced_nodes.insert(v);
        } else {
            vec_utils::remove_value(&mut self.worklist_spill, v);
            self.coalesced_nodes.insert(v);
        }
        
        self.alias.insert(v, u); 
        
        {
            let ref mut movelist = self.movelist;
            GraphColoring::movelist_check(movelist, u);
            GraphColoring::movelist_check(movelist, v);
            // we checked before getting the movelist, its safe
            // use nocheck version which requires only immutable references of movelist
            // avoid maintaining a mutable reference of movelist alive
            let movelist_u = &mut unsafe {GraphColoring::movelist_nocheck(movelist, u)}.borrow_mut();
            let movelist_v = &mut unsafe {GraphColoring::movelist_nocheck(movelist, v)}.borrow_mut();
            
            // addAll()
            movelist_u.extend_from_slice(movelist_v.as_slice());
        }
        
507
        let mut nodes = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
508
509
510
        nodes.insert(v);
        self.enable_moves(nodes);
        
511
512
        for t in self.adjacent(v).iter() {
            let t = *t;
qinsoon's avatar
qinsoon committed
513
514
515
516
517
            self.add_edge(t, u);
            self.decrement_degree(t);
        }
        
        if self.worklist_freeze.contains(&u)
518
          && self.degree(u) >= self.n_regs_for_node(u) {
qinsoon's avatar
qinsoon committed
519
520
521
522
523
            self.worklist_freeze.remove(&u);
            self.worklist_spill.push(u);
        }
    }
    
524
    fn add_edge(&mut self, u: NodeIndex, v: NodeIndex) {
qinsoon's avatar
qinsoon committed
525
526
527
528
529
530
531
532
533
534
535
536
        if u != v && !self.ig.is_adj(u, v) {
            if !self.precolored.contains(&u) {
                self.ig.add_interference_edge(u, v);
                let degree_u = self.degree(u);
                self.degree.insert(u, degree_u + 1);
            }
            if !self.precolored.contains(&v) {
                self.ig.add_interference_edge(v, u);
                let degree_v = self.degree(v);
                self.degree.insert(v, degree_v + 1);
            }
        }
537
538
539
    }
    
    fn freeze(&mut self) {
qinsoon's avatar
qinsoon committed
540
        // it is not empty (checked before)
541
        let node = self.worklist_freeze.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
542
        trace!("Freezing {}...", self.display_node(node));
qinsoon's avatar
qinsoon committed
543
544
545
546
547
        
        self.worklist_simplify.insert(node);
        self.freeze_moves(node);
    }
    
548
    fn freeze_moves(&mut self, u: NodeIndex) {
549
550
        for m in self.node_moves(u).iter() {
            let m = *m;
qinsoon's avatar
qinsoon committed
551
552
553
554
555
556
557
558
559
560
            let mut v = self.get_alias(m.from);
            if v == self.get_alias(u) {
                v = self.get_alias(m.to);
            }
            
            self.active_moves.remove(&m);
            self.frozen_moves.insert(m);
            
            if !self.precolored.contains(&v) 
               && self.node_moves(v).is_empty()
561
               && self.degree(v) < self.n_regs_for_node(v) {
qinsoon's avatar
qinsoon committed
562
563
564
565
                self.worklist_freeze.remove(&v);
                self.worklist_simplify.insert(v);
            }
        }
566
567
568
    }
    
    fn select_spill(&mut self) {
qinsoon's avatar
qinsoon committed
569
        trace!("Selecting a node to spill...");
570
        let mut m : Option<NodeIndex> = None;
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
        
        for n in self.worklist_spill.iter() {
            let n = *n;
            if m.is_none() {
                m = Some(n);
            } else if {
                // m is not none
                let temp = self.ig.get_temp_of(m.unwrap());
                let spillable = {match self.spillable.get(&temp) {
                    None => {
                        //by default, its spillable
                        true
                    },
                    Some(b) => *b
                }};
                
                !spillable
            } {
                m = Some(n);
            } else if (self.ig.get_spill_cost(n) / (self.degree(n) as f32)) 
              < (self.ig.get_spill_cost(m.unwrap()) / (self.degree(m.unwrap()) as f32)) {
                m = Some(n);
            }
        }
        
        // m is not none
        let m = m.unwrap();
qinsoon's avatar
qinsoon committed
598
        trace!("Spilling {}...", self.display_node(m));
qinsoon's avatar
qinsoon committed
599
        
600
601
602
        vec_utils::remove_value(&mut self.worklist_spill, m);
        self.worklist_simplify.insert(m);
        self.freeze_moves(m);
603
604
    }
    
605
    fn assign_colors(&mut self) {
qinsoon's avatar
qinsoon committed
606
        trace!("---coloring done---");
607
608
        while !self.select_stack.is_empty() {
            let n = self.select_stack.pop().unwrap();
qinsoon's avatar
qinsoon committed
609
            trace!("Assigning color to {}", self.display_node(n));
610
            
611
            let mut ok_colors : LinkedHashSet<MuID> = self.colors.get(&self.ig.get_group_of(n)).unwrap().clone();
qinsoon's avatar
qinsoon committed
612
613
614

            trace!("all the colors for this temp: {:?}", ok_colors);

615
            for w in self.ig.outedges_of(n) {
qinsoon's avatar
qinsoon committed
616
617
                let w_alias = self.get_alias(w);
                match self.ig.get_color_of(w_alias) {
618
                    None => {}, // do nothing
qinsoon's avatar
qinsoon committed
619
620
621
622
                    Some(color) => {
                        trace!("color {} is used for its neighbor {:?} (aliasing to {:?})", color, self.display_node(w), self.display_node(w_alias));
                        ok_colors.remove(&color);
                    }
623
624
                }
            }
qinsoon's avatar
qinsoon committed
625
            trace!("available colors: {:?}", ok_colors);
626
627
            
            if ok_colors.is_empty() {
qinsoon's avatar
qinsoon committed
628
                trace!("{} is a spilled node", self.display_node(n));
629
630
                self.spilled_nodes.push(n);
            } else {
631
                let first_available_color = ok_colors.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
632
                trace!("Color {} as {}", self.display_node(n), first_available_color);
633
634
                
                if !backend::is_callee_saved(first_available_color) {
635
                    warn!("Use caller saved register {}", first_available_color);
636
637
                }
                
638
                self.colored_nodes.push(n);
qinsoon's avatar
qinsoon committed
639
                self.ig.color_node(n, first_available_color);
640
641
642
            }
        }
        
qinsoon's avatar
qinsoon committed
643
        for n in self.colored_nodes.iter() {
644
645
646
            let n = *n;
            let alias = self.get_alias(n);
            let alias_color = self.ig.get_color_of(alias).unwrap();
qinsoon's avatar
qinsoon committed
647
            
qinsoon's avatar
qinsoon committed
648
649
            trace!("Assign color to {} based on aliased {}", self.display_node(n), self.display_node(alias));
            trace!("Color {} as {}", self.display_node(n), alias_color);
650
651
652
            self.ig.color_node(n, alias_color);
        }
    }
qinsoon's avatar
qinsoon committed
653

qinsoon's avatar
qinsoon committed
654
    #[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
655
    fn rewrite_program(&mut self) {
qinsoon's avatar
qinsoon committed
656
657
658
659
660
661
        let spills = self.spills();

        let mut spilled_mem = HashMap::new();

        // allocating frame slots for every spilled temp
        for reg_id in spills.iter() {
qinsoon's avatar
qinsoon committed
662
            let ssa_entry = match self.func.context.get_value(*reg_id) {
qinsoon's avatar
qinsoon committed
663
664
665
                Some(entry) => entry,
                None => panic!("The spilled register {} is not in func context", reg_id)
            };
qinsoon's avatar
qinsoon committed
666
            let mem = self.cf.frame.alloc_slot_for_spilling(ssa_entry.value().clone(), self.vm);
qinsoon's avatar
qinsoon committed
667
668
669
670

            spilled_mem.insert(*reg_id, mem);
        }

qinsoon's avatar
qinsoon committed
671
        // though we are not using this right now
qinsoon's avatar
qinsoon committed
672
        let new_temps = backend::spill_rewrite(&spilled_mem, self.func, self.cf, self.vm);
qinsoon's avatar
qinsoon committed
673
    }
674
675
676
677
678
679
680
681
682
683
684
685
    
    pub fn spills(&self) -> Vec<MuID> {
        let mut spills = vec![];
        
        let spill_count = self.spilled_nodes.len();
        if spill_count > 0 {
            for n in self.spilled_nodes.iter() {
                spills.push(self.ig.get_temp_of(*n));
            }
        }
        
        spills
686
    }
687
}