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.

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

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

11
use utils::vec_utils;
12
use utils::LinkedHashSet;
13
use utils::LinkedHashMap;
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>,
qinsoon's avatar
qinsoon committed
47
    spill_history: LinkedHashMap<MuID, P<Value>>,   // for validation, we need to log all registers get spilled
48
    
49
    worklist_freeze: LinkedHashSet<NodeIndex>,
50
    frozen_moves: LinkedHashSet<Move>,
51
    
52
53
    worklist_simplify: LinkedHashSet<NodeIndex>,
    select_stack: Vec<NodeIndex>
qinsoon's avatar
qinsoon committed
54
55
}

qinsoon's avatar
qinsoon committed
56
impl <'a> GraphColoring<'a> {
57
    pub fn start (func: &'a mut MuFunctionVersion, cf: &'a mut CompiledFunction, vm: &'a VM) -> GraphColoring<'a> {
qinsoon's avatar
qinsoon committed
58
59
60
61
        GraphColoring::start_with_spill_history(LinkedHashMap::new(), func, cf, vm)
    }

    fn start_with_spill_history(spill_history: LinkedHashMap<MuID, P<Value>>, func: &'a mut MuFunctionVersion, cf: &'a mut CompiledFunction, vm: &'a VM) -> GraphColoring<'a> {
62
        trace!("Initializing coloring allocator...");
qinsoon's avatar
qinsoon committed
63
64
        cf.mc().trace_mc();

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

67
        let coloring = GraphColoring {
qinsoon's avatar
qinsoon committed
68
69
70
71
72
            func: func,
            cf: cf,
            vm: vm,

            ig: ig,
qinsoon's avatar
qinsoon committed
73

74
            precolored: LinkedHashSet::new(),
75
            colors: {
76
                let mut map = LinkedHashMap::new();
77
78
                map.insert(backend::RegGroup::GPR, LinkedHashSet::new());
                map.insert(backend::RegGroup::FPR, LinkedHashSet::new());
79
80
81
                map
            },
            colored_nodes: Vec::new(),
qinsoon's avatar
qinsoon committed
82

83
            initial: Vec::new(),
84
            degree: LinkedHashMap::new(),
qinsoon's avatar
qinsoon committed
85

86
            worklist_moves: Vec::new(),
87
            movelist: LinkedHashMap::new(),
88
89
90
91
            active_moves: LinkedHashSet::new(),
            coalesced_nodes: LinkedHashSet::new(),
            coalesced_moves: LinkedHashSet::new(),
            constrained_moves: LinkedHashSet::new(),
92
            alias: LinkedHashMap::new(),
qinsoon's avatar
qinsoon committed
93

94
            worklist_spill: Vec::new(),
95
            spillable: LinkedHashMap::new(),
96
            spilled_nodes: Vec::new(),
qinsoon's avatar
qinsoon committed
97
98
            spill_history: spill_history,

99
100
            worklist_freeze: LinkedHashSet::new(),
            frozen_moves: LinkedHashSet::new(),
qinsoon's avatar
qinsoon committed
101

102
            worklist_simplify: LinkedHashSet::new(),
qinsoon's avatar
qinsoon committed
103
            select_stack: Vec::new(),
qinsoon's avatar
qinsoon committed
104
        };
qinsoon's avatar
qinsoon committed
105

qinsoon's avatar
qinsoon committed
106
        coloring.regalloc()
qinsoon's avatar
qinsoon committed
107
    }
qinsoon's avatar
qinsoon committed
108

109
    fn display_node(&self, node: NodeIndex) -> String {
qinsoon's avatar
qinsoon committed
110
111
112
113
114
115
116
117
118
119
120
        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
121
    
122
    fn regalloc(mut self) -> GraphColoring<'a> {
qinsoon's avatar
qinsoon committed
123
        trace!("---InterenceGraph---");
124
125
        let _p = hprof::enter("regalloc: graph coloring");

qinsoon's avatar
qinsoon committed
126
        self.ig.print(&self.func.context);
qinsoon's avatar
qinsoon committed
127
        
qinsoon's avatar
qinsoon committed
128
        // precolor for all machine registers
129
        for reg in backend::all_regs().values() {
130
131
132
133
134
            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
135
        // put usable registers as available colors
136
        for reg in backend::all_usable_regs().iter() {
qinsoon's avatar
qinsoon committed
137
            let reg_id = reg.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
138
139
            let group = backend::pick_group_for_reg(reg_id);
            self.colors.get_mut(&group).unwrap().insert(reg_id);
qinsoon's avatar
qinsoon committed
140
141
142
143
        }
        
        for node in self.ig.nodes() {
            if !self.ig.is_colored(node) {
144
                self.initial.push(node);
145
                let outdegree = self.ig.outdegree_of(node);
146
                self.degree.insert(node, outdegree);
qinsoon's avatar
qinsoon committed
147

qinsoon's avatar
qinsoon committed
148
                trace!("{} has a degree of {}", self.display_node(node), outdegree);
qinsoon's avatar
qinsoon committed
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
            }
        }
        
        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
172
173
        self.assign_colors();

174
175
        drop(_p);

qinsoon's avatar
qinsoon committed
176
177
        if !self.spilled_nodes.is_empty() {
            trace!("spill required");
qinsoon's avatar
qinsoon committed
178
179
180
            if cfg!(debug_assertions) {
                trace!("nodes to be spilled:");
                for node in self.spilled_nodes.iter() {
qinsoon's avatar
qinsoon committed
181
                    trace!("{}", self.display_node(*node));
qinsoon's avatar
qinsoon committed
182
183
184
                }
            }

qinsoon's avatar
qinsoon committed
185
            self.rewrite_program();
qinsoon's avatar
qinsoon committed
186

qinsoon's avatar
qinsoon committed
187
            return GraphColoring::start_with_spill_history(self.spill_history.clone(), self.func, self.cf, self.vm);
qinsoon's avatar
qinsoon committed
188
189
        }

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

        // 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
375
376
377
            info!("a move instruction of two temporaries of different reigsters group");
            info!("from: {:?}, to: {:?}", m.from, m.to);

qinsoon's avatar
qinsoon committed
378
379
            return;
        }
qinsoon's avatar
qinsoon committed
380
        
qinsoon's avatar
qinsoon committed
381
382
        let x = self.get_alias(m.from);
        let y = self.get_alias(m.to);
qinsoon's avatar
qinsoon committed
383
        trace!("resolve alias: from {} to {}", self.display_node(x), self.display_node(y));
qinsoon's avatar
qinsoon committed
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
        
        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
402
        trace!("u={}, v={}, precolored_u={}, precolroed_v={}", 
qinsoon's avatar
qinsoon committed
403
404
            self.display_node(u),
            self.display_node(v),
qinsoon's avatar
qinsoon committed
405
            precolored_u, precolored_v);
qinsoon's avatar
qinsoon committed
406
407
        
        if u == v {
qinsoon's avatar
qinsoon committed
408
            trace!("u == v, coalesce the move");
qinsoon's avatar
qinsoon committed
409
410
411
412
413
            self.coalesced_moves.insert(m);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else if precolored_v || self.ig.is_adj(u, v) {
414
415
            trace!("precolored_v: {}", precolored_v);
            trace!("is_adj(u, v): {}", self.ig.is_adj(u, v));
qinsoon's avatar
qinsoon committed
416
417
            trace!("v is precolored or u,v is adjacent, the move is constrained");
            self.constrained_moves.insert(m);
qinsoon's avatar
qinsoon committed
418
419
420
421
422
423
424
425
            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
426
427
428
429
            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
430
431
432
433
434
435
            self.coalesced_moves.insert(m);
            self.combine(u, v);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else {
qinsoon's avatar
qinsoon committed
436
            trace!("cannot coalesce the move");
qinsoon's avatar
qinsoon committed
437
438
439
440
            self.active_moves.insert(m);
        }
    }
    
441
    pub fn get_alias(&self, node: NodeIndex) -> NodeIndex {
qinsoon's avatar
qinsoon committed
442
443
444
445
446
447
448
        if self.coalesced_nodes.contains(&node) {
            self.get_alias(*self.alias.get(&node).unwrap())
        } else {
            node
        }
    }
    
449
    fn add_worklist(&mut self, node: NodeIndex) {
450
        if !self.is_move_related(node) && self.degree(node) < self.n_regs_for_node(node) {
qinsoon's avatar
qinsoon committed
451
452
453
454
455
            self.worklist_freeze.remove(&node);
            self.worklist_simplify.insert(node);
        }
    }
    
456
    fn ok(&self, u: NodeIndex, v: NodeIndex) -> bool {
457
458
        for t in self.adjacent(v).iter() {
            let t = *t;
459
460
461
            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
462
                return false;
463
            }
qinsoon's avatar
qinsoon committed
464
465
466
467
468
        }
        
        true
    }
    
469
    fn conservative(&self, u: NodeIndex, v: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
470
471
        let adj_u = self.adjacent(u);
        let adj_v = self.adjacent(v);
472
473
474
475
476
        let nodes = {
            let mut ret = adj_u;
            ret.add_all(adj_v);
            ret
        };
qinsoon's avatar
qinsoon committed
477
478
        
        let mut k = 0;
479
        for n in nodes.iter() {
qinsoon's avatar
qinsoon committed
480
            if self.precolored.contains(n) || self.degree(*n) >= self.n_regs_for_node(*n) {
qinsoon's avatar
qinsoon committed
481
482
483
484
                k += 1;
            }
        }
        
qinsoon's avatar
qinsoon committed
485
        k < self.n_regs_for_node(u) && k < self.n_regs_for_node(v)
qinsoon's avatar
qinsoon committed
486
487
    }
    
488
    fn combine(&mut self, u: NodeIndex, v: NodeIndex) {
qinsoon's avatar
qinsoon committed
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
        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());
        }
        
513
        let mut nodes = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
514
515
516
        nodes.insert(v);
        self.enable_moves(nodes);
        
517
518
        for t in self.adjacent(v).iter() {
            let t = *t;
qinsoon's avatar
qinsoon committed
519
520
521
522
523
            self.add_edge(t, u);
            self.decrement_degree(t);
        }
        
        if self.worklist_freeze.contains(&u)
524
          && self.degree(u) >= self.n_regs_for_node(u) {
qinsoon's avatar
qinsoon committed
525
526
527
528
529
            self.worklist_freeze.remove(&u);
            self.worklist_spill.push(u);
        }
    }
    
530
    fn add_edge(&mut self, u: NodeIndex, v: NodeIndex) {
qinsoon's avatar
qinsoon committed
531
532
533
534
535
536
537
538
539
540
541
542
        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);
            }
        }
543
544
545
    }
    
    fn freeze(&mut self) {
qinsoon's avatar
qinsoon committed
546
        // it is not empty (checked before)
547
        let node = self.worklist_freeze.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
548
        trace!("Freezing {}...", self.display_node(node));
qinsoon's avatar
qinsoon committed
549
550
551
552
553
        
        self.worklist_simplify.insert(node);
        self.freeze_moves(node);
    }
    
554
    fn freeze_moves(&mut self, u: NodeIndex) {
555
556
        for m in self.node_moves(u).iter() {
            let m = *m;
qinsoon's avatar
qinsoon committed
557
558
559
560
561
562
563
564
565
566
            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()
567
               && self.degree(v) < self.n_regs_for_node(v) {
qinsoon's avatar
qinsoon committed
568
569
570
571
                self.worklist_freeze.remove(&v);
                self.worklist_simplify.insert(v);
            }
        }
572
573
574
    }
    
    fn select_spill(&mut self) {
qinsoon's avatar
qinsoon committed
575
        trace!("Selecting a node to spill...");
576
        let mut m : Option<NodeIndex> = None;
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
603
        
        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
604
        trace!("Spilling {}...", self.display_node(m));
qinsoon's avatar
qinsoon committed
605
        
606
607
608
        vec_utils::remove_value(&mut self.worklist_spill, m);
        self.worklist_simplify.insert(m);
        self.freeze_moves(m);
609
610
    }
    
611
    fn assign_colors(&mut self) {
qinsoon's avatar
qinsoon committed
612
        trace!("---coloring done---");
613
614
        while !self.select_stack.is_empty() {
            let n = self.select_stack.pop().unwrap();
qinsoon's avatar
qinsoon committed
615
            trace!("Assigning color to {}", self.display_node(n));
616
            
617
            let mut ok_colors : LinkedHashSet<MuID> = self.colors.get(&self.ig.get_group_of(n)).unwrap().clone();
qinsoon's avatar
qinsoon committed
618
619
620

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

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

qinsoon's avatar
qinsoon committed
660
    #[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
661
    fn rewrite_program(&mut self) {
qinsoon's avatar
qinsoon committed
662
663
        let spills = self.spills();

664
        let mut spilled_mem = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
665
666
667

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

qinsoon's avatar
qinsoon committed
674
675
            spilled_mem.insert(*reg_id, mem.clone());
            self.spill_history.insert(*reg_id, mem);
qinsoon's avatar
qinsoon committed
676
677
        }

qinsoon's avatar
qinsoon committed
678
        // though we are not using this right now
qinsoon's avatar
qinsoon committed
679
        let new_temps = backend::spill_rewrite(&spilled_mem, self.func, self.cf, self.vm);
qinsoon's avatar
qinsoon committed
680
    }
681
682
683
684
685
686
687
688
689
690
691
692
    
    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
693
    }
694
}