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 22.9 KB
Newer Older
qinsoon's avatar
qinsoon committed
1
2
3
use ast::ir::*;
use compiler::backend;
use compiler::backend::reg_alloc::graph_coloring;
4
use compiler::backend::reg_alloc::graph_coloring::liveness::InterferenceGraph;
qinsoon's avatar
qinsoon committed
5
6
use compiler::machine_code::CompiledFunction;
use vm::VM;
7

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

qinsoon's avatar
qinsoon committed
13
use std::cell::RefCell;
qinsoon's avatar
qinsoon committed
14

15
16
17
use compiler::backend::reg_alloc::graph_coloring::liveness::Move;
use compiler::backend::reg_alloc::graph_coloring::petgraph::graph::NodeIndex;

qinsoon's avatar
qinsoon committed
18
const COALESCING : bool = true;
19

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

25
    pub ig: InterferenceGraph,
qinsoon's avatar
qinsoon committed
26

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

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

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

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

            ig: ig,
qinsoon's avatar
qinsoon committed
66

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

101
    fn display_node(&self, node: NodeIndex) -> String {
qinsoon's avatar
qinsoon committed
102
103
104
105
106
107
108
109
110
111
112
        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
113
    
114
    fn regalloc(mut self) -> GraphColoring<'a> {
qinsoon's avatar
qinsoon committed
115
        trace!("---InterenceGraph---");
qinsoon's avatar
qinsoon committed
116
        self.ig.print(&self.func.context);
qinsoon's avatar
qinsoon committed
117
        
qinsoon's avatar
qinsoon committed
118
        // precolor for all machine registers
119
        for reg in backend::all_regs().values() {
120
121
122
123
124
            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
125
        // put usable registers as available colors
126
        for reg in backend::all_usable_regs().iter() {
qinsoon's avatar
qinsoon committed
127
            let reg_id = reg.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
128
129
            let group = backend::pick_group_for_reg(reg_id);
            self.colors.get_mut(&group).unwrap().insert(reg_id);
qinsoon's avatar
qinsoon committed
130
131
132
133
        }
        
        for node in self.ig.nodes() {
            if !self.ig.is_colored(node) {
134
                self.initial.push(node);
135
                let outdegree = self.ig.outdegree_of(node);
136
                self.degree.insert(node, outdegree);
qinsoon's avatar
qinsoon committed
137

qinsoon's avatar
qinsoon committed
138
                trace!("{} has a degree of {}", self.display_node(node), outdegree);
qinsoon's avatar
qinsoon committed
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
            }
        }
        
        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
162
163
164
165
        self.assign_colors();

        if !self.spilled_nodes.is_empty() {
            trace!("spill required");
qinsoon's avatar
qinsoon committed
166
167
168
            if cfg!(debug_assertions) {
                trace!("nodes to be spilled:");
                for node in self.spilled_nodes.iter() {
qinsoon's avatar
qinsoon committed
169
                    trace!("{}", self.display_node(*node));
qinsoon's avatar
qinsoon committed
170
171
172
                }
            }

qinsoon's avatar
qinsoon committed
173
            self.rewrite_program();
qinsoon's avatar
qinsoon committed
174

qinsoon's avatar
qinsoon committed
175
            return GraphColoring::start(self.func, self.cf, self.vm);
qinsoon's avatar
qinsoon committed
176
177
        }

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

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

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

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

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

qinsoon's avatar
qinsoon committed
648
    #[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
649
    fn rewrite_program(&mut self) {
qinsoon's avatar
qinsoon committed
650
651
652
653
654
655
        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
656
            let ssa_entry = match self.func.context.get_value(*reg_id) {
qinsoon's avatar
qinsoon committed
657
658
659
                Some(entry) => entry,
                None => panic!("The spilled register {} is not in func context", reg_id)
            };
qinsoon's avatar
qinsoon committed
660
            let mem = self.cf.frame.alloc_slot_for_spilling(ssa_entry.value().clone(), self.vm);
qinsoon's avatar
qinsoon committed
661
662
663
664

            spilled_mem.insert(*reg_id, mem);
        }

qinsoon's avatar
qinsoon committed
665
        // though we are not using this right now
qinsoon's avatar
qinsoon committed
666
        let new_temps = backend::spill_rewrite(&spilled_mem, self.func, self.cf, self.vm);
qinsoon's avatar
qinsoon committed
667
    }
668
669
670
671
672
673
674
675
676
677
678
679
    
    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
680
    }
681
}