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.2 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;
qinsoon's avatar
qinsoon committed
10

qinsoon's avatar
qinsoon committed
11
use std::cell::RefCell;
qinsoon's avatar
qinsoon committed
12
13
use std::collections::HashMap;

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

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

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

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

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

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

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

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

            ig: ig,
qinsoon's avatar
qinsoon committed
65

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

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

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

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

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

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

177
        self
qinsoon's avatar
qinsoon committed
178
179
180
    }
    
    fn build(&mut self) {
qinsoon's avatar
qinsoon committed
181
182
        if COALESCING {
            trace!("coalescing enabled, build move list");
qinsoon's avatar
qinsoon committed
183
184
185
            let ref ig = self.ig;
            let ref mut movelist = self.movelist;
            for m in ig.moves() {
qinsoon's avatar
qinsoon committed
186
                trace!("add to movelist: {:?}", m);
187
                self.worklist_moves.push(m.clone());
qinsoon's avatar
qinsoon committed
188
189
                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
190
            }
qinsoon's avatar
qinsoon committed
191
192
        } else {
            trace!("coalescing disabled");
qinsoon's avatar
qinsoon committed
193
194
195
196
        }
    }
    
    fn make_work_list(&mut self) {
197
        trace!("Making work list from initials...");
qinsoon's avatar
qinsoon committed
198
        while !self.initial.is_empty() {
199
            let node = self.initial.pop().unwrap();
qinsoon's avatar
qinsoon committed
200
201
202
203
            
            if {
                // condition: degree >= K
                let degree = self.ig.degree_of(node); 
204
                let n_regs = self.n_regs_for_node(node);
qinsoon's avatar
qinsoon committed
205
206
207
                
                degree >= n_regs
            } {
qinsoon's avatar
qinsoon committed
208
                trace!("{} 's degree >= reg number limit (K), push to spill list", self.display_node(node));
209
                self.worklist_spill.push(node);
qinsoon's avatar
qinsoon committed
210
            } else if self.is_move_related(node) {
qinsoon's avatar
qinsoon committed
211
                trace!("{} is move related, push to freeze list", self.display_node(node));
qinsoon's avatar
qinsoon committed
212
213
                self.worklist_freeze.insert(node);
            } else {
qinsoon's avatar
qinsoon committed
214
                trace!("{} has small degree and not move related, push to simplify list", self.display_node(node));
qinsoon's avatar
qinsoon committed
215
216
217
218
219
                self.worklist_simplify.insert(node);
            }
        }
    }
    
220
    fn n_regs_for_node(&self, node: NodeIndex) -> usize {
221
222
223
        backend::number_of_regs_in_group(self.ig.get_group_of(node))
    }
    
224
    fn is_move_related(&mut self, node: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
225
226
227
        !self.node_moves(node).is_empty()
    }
    
228
    fn node_moves(&mut self, node: NodeIndex) -> LinkedHashSet<Move> {
229
        let mut moves = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
230
231
232
233
234
235
236
237
238
239
240
        
        // 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());
        }
        
241
        let mut retained = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
242
        let movelist = &GraphColoring::movelist_mut(&mut self.movelist, node).borrow();
qinsoon's avatar
qinsoon committed
243
        for m in moves.iter() {
244
            if vec_utils::find_value(movelist, *m).is_some() {
qinsoon's avatar
qinsoon committed
245
246
247
248
249
250
251
                retained.insert(*m);
            }
        }
        
        retained
    }
    
qinsoon's avatar
qinsoon committed
252
253
254
    // 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)
255
    fn movelist_mut(list: &mut HashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) -> &RefCell<Vec<Move>> {
qinsoon's avatar
qinsoon committed
256
257
258
259
        GraphColoring::movelist_check(list, node);
        unsafe {GraphColoring::movelist_nocheck(list, node)}
    }
    
260
    fn movelist_check(list: &mut HashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) {
qinsoon's avatar
qinsoon committed
261
        if !list.contains_key(&node) {
qinsoon's avatar
qinsoon committed
262
            list.insert(node, RefCell::new(Vec::new()));
qinsoon's avatar
qinsoon committed
263
        }
qinsoon's avatar
qinsoon committed
264
265
266
    }
    
    // allows getting the Vec<Move> without a mutable reference of the hashmap
267
    unsafe fn movelist_nocheck(list: &HashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) -> &RefCell<Vec<Move>> {
qinsoon's avatar
qinsoon committed
268
        list.get(&node).unwrap()
qinsoon's avatar
qinsoon committed
269
    }
270
271
    
    fn simplify(&mut self) {
272
        // remove next element from worklist_simplify, we know its not empty
273
        let node = self.worklist_simplify.pop_front().unwrap();
274
        
qinsoon's avatar
qinsoon committed
275
        trace!("Simplifying {}", self.display_node(node));
276
277
278
        
        self.select_stack.push(node);
        
279
        for m in self.adjacent(node).iter() {
280
            self.decrement_degree(*m);
281
282
283
        }
    }
    
284
    fn adjacent(&self, n: NodeIndex) -> LinkedHashSet<NodeIndex> {
285
        let mut adj = LinkedHashSet::new();
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
        
        // 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
    }
    
305
    fn degree(&self, n: NodeIndex) -> usize {
306
307
308
309
310
311
        match self.degree.get(&n) {
            Some(d) => *d,
            None => 0
        }
    }
    
312
    fn decrement_degree(&mut self, n: NodeIndex) {
313
314
315
316
        if self.precolored.contains(&n) {
            return;
        }
        
qinsoon's avatar
qinsoon committed
317
        trace!("decrement degree of {}", self.display_node(n));
318
        
319
        let d = self.degree(n);
320
        debug_assert!(d != 0);
321
322
        self.degree.insert(n, d - 1);
        
323
        if d == self.n_regs_for_node(n) {
qinsoon's avatar
qinsoon committed
324
            trace!("{}'s degree is K, no longer need to spill it", self.display_node(n));
325
326
            let mut nodes = self.adjacent(n);
            nodes.insert(n);
qinsoon's avatar
qinsoon committed
327
            trace!("enable moves of {:?}", nodes);
328
329
330
331
332
            self.enable_moves(nodes);
            
            vec_utils::remove_value(&mut self.worklist_spill, n);
            
            if self.is_move_related(n) {
qinsoon's avatar
qinsoon committed
333
                trace!("{} is move related, push to freeze list", self.display_node(n));
334
335
                self.worklist_freeze.insert(n);
            } else {
qinsoon's avatar
qinsoon committed
336
                trace!("{} is not move related, push to simplify list", self.display_node(n));
337
338
339
340
341
                self.worklist_simplify.insert(n);
            }
        }
    }
    
342
    fn enable_moves(&mut self, nodes: LinkedHashSet<NodeIndex>) {
343
344
345
346
        for n in nodes.iter() {
            let n = *n;
            for mov in self.node_moves(n).iter() {
                let mov = *mov;
347
348
349
350
351
352
353
354
355
                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
356
357
        let m = self.worklist_moves.pop().unwrap();
        
qinsoon's avatar
qinsoon committed
358
        trace!("Coalescing on {}", self.display_move(m));
qinsoon's avatar
qinsoon committed
359
        
qinsoon's avatar
qinsoon committed
360
361
        let x = self.get_alias(m.from);
        let y = self.get_alias(m.to);
qinsoon's avatar
qinsoon committed
362
        trace!("resolve alias: from {} to {}", self.display_node(x), self.display_node(y));
qinsoon's avatar
qinsoon committed
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
        
        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
381
        trace!("u={}, v={}, precolored_u={}, precolroed_v={}", 
qinsoon's avatar
qinsoon committed
382
383
            self.display_node(u),
            self.display_node(v),
qinsoon's avatar
qinsoon committed
384
            precolored_u, precolored_v);
qinsoon's avatar
qinsoon committed
385
386
        
        if u == v {
qinsoon's avatar
qinsoon committed
387
            trace!("u == v, coalesce the move");
qinsoon's avatar
qinsoon committed
388
389
390
391
392
            self.coalesced_moves.insert(m);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else if precolored_v || self.ig.is_adj(u, v) {
393
394
            trace!("precolored_v: {}", precolored_v);
            trace!("is_adj(u, v): {}", self.ig.is_adj(u, v));
qinsoon's avatar
qinsoon committed
395
396
            trace!("v is precolored or u,v is adjacent, the move is constrained");
            self.constrained_moves.insert(m);
qinsoon's avatar
qinsoon committed
397
398
399
400
401
402
403
404
            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
405
            trace!("precolored_u&&ok(u,v) || !precolored_u&&conserv(u,v), coalesce and combine the move");  
qinsoon's avatar
qinsoon committed
406
407
408
409
410
411
            self.coalesced_moves.insert(m);
            self.combine(u, v);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else {
qinsoon's avatar
qinsoon committed
412
            trace!("cannot coalesce the move");
qinsoon's avatar
qinsoon committed
413
414
415
416
            self.active_moves.insert(m);
        }
    }
    
417
    pub fn get_alias(&self, node: NodeIndex) -> NodeIndex {
qinsoon's avatar
qinsoon committed
418
419
420
421
422
423
424
        if self.coalesced_nodes.contains(&node) {
            self.get_alias(*self.alias.get(&node).unwrap())
        } else {
            node
        }
    }
    
425
    fn add_worklist(&mut self, node: NodeIndex) {
426
        if !self.is_move_related(node) && self.degree(node) < self.n_regs_for_node(node) {
qinsoon's avatar
qinsoon committed
427
428
429
430
431
            self.worklist_freeze.remove(&node);
            self.worklist_simplify.insert(node);
        }
    }
    
432
    fn ok(&self, u: NodeIndex, v: NodeIndex) -> bool {
433
434
        for t in self.adjacent(v).iter() {
            let t = *t;
435
436
437
            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
438
                return false;
439
            }
qinsoon's avatar
qinsoon committed
440
441
442
443
444
        }
        
        true
    }
    
445
    fn conservative(&self, u: NodeIndex, v: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
446
447
448
449
        debug_assert!(self.ig.get_group_of(u) == self.ig.get_group_of(v));
        
        let adj_u = self.adjacent(u);
        let adj_v = self.adjacent(v);
450
451
452
453
454
        let nodes = {
            let mut ret = adj_u;
            ret.add_all(adj_v);
            ret
        };
qinsoon's avatar
qinsoon committed
455
456
        
        let mut k = 0;
457
        for n in nodes.iter() {
458
459
//            if self.precolored.contains(n) || self.degree(*n) >= self.n_regs_for_node(*n) {
            if self.degree(*n) >= self.n_regs_for_node(*n) {
qinsoon's avatar
qinsoon committed
460
461
462
463
464
465
466
                k += 1;
            }
        }
        
        k < self.n_regs_for_node(u)
    }
    
467
    fn combine(&mut self, u: NodeIndex, v: NodeIndex) {
qinsoon's avatar
qinsoon committed
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
        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());
        }
        
492
        let mut nodes = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
493
494
495
        nodes.insert(v);
        self.enable_moves(nodes);
        
496
497
        for t in self.adjacent(v).iter() {
            let t = *t;
qinsoon's avatar
qinsoon committed
498
499
500
501
502
            self.add_edge(t, u);
            self.decrement_degree(t);
        }
        
        if self.worklist_freeze.contains(&u)
503
          && self.degree(u) >= self.n_regs_for_node(u) {
qinsoon's avatar
qinsoon committed
504
505
506
507
508
            self.worklist_freeze.remove(&u);
            self.worklist_spill.push(u);
        }
    }
    
509
    fn add_edge(&mut self, u: NodeIndex, v: NodeIndex) {
qinsoon's avatar
qinsoon committed
510
511
512
513
514
515
516
517
518
519
520
521
        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);
            }
        }
522
523
524
    }
    
    fn freeze(&mut self) {
qinsoon's avatar
qinsoon committed
525
        // it is not empty (checked before)
526
        let node = self.worklist_freeze.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
527
        trace!("Freezing {}...", self.display_node(node));
qinsoon's avatar
qinsoon committed
528
529
530
531
532
        
        self.worklist_simplify.insert(node);
        self.freeze_moves(node);
    }
    
533
    fn freeze_moves(&mut self, u: NodeIndex) {
534
535
        for m in self.node_moves(u).iter() {
            let m = *m;
qinsoon's avatar
qinsoon committed
536
537
538
539
540
541
542
543
544
545
            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()
546
               && self.degree(v) < self.n_regs_for_node(v) {
qinsoon's avatar
qinsoon committed
547
548
549
550
                self.worklist_freeze.remove(&v);
                self.worklist_simplify.insert(v);
            }
        }
551
552
553
    }
    
    fn select_spill(&mut self) {
qinsoon's avatar
qinsoon committed
554
        trace!("Selecting a node to spill...");
555
        let mut m : Option<NodeIndex> = None;
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
        
        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
583
        trace!("Spilling {}...", self.display_node(m));
qinsoon's avatar
qinsoon committed
584
        
585
586
587
        vec_utils::remove_value(&mut self.worklist_spill, m);
        self.worklist_simplify.insert(m);
        self.freeze_moves(m);
588
589
    }
    
590
    fn assign_colors(&mut self) {
qinsoon's avatar
qinsoon committed
591
        trace!("---coloring done---");
592
593
        while !self.select_stack.is_empty() {
            let n = self.select_stack.pop().unwrap();
qinsoon's avatar
qinsoon committed
594
            trace!("Assigning color to {}", self.display_node(n));
595
            
596
            let mut ok_colors : LinkedHashSet<MuID> = self.colors.get(&self.ig.get_group_of(n)).unwrap().clone();
597
598
599
600
601
602
603
            for w in self.ig.outedges_of(n) {
                let w = self.get_alias(w);
                match self.ig.get_color_of(w) {
                    None => {}, // do nothing
                    Some(color) => {ok_colors.remove(&color);}
                }
            }
qinsoon's avatar
qinsoon committed
604
            trace!("available colors: {:?}", ok_colors);
605
606
            
            if ok_colors.is_empty() {
qinsoon's avatar
qinsoon committed
607
                trace!("{} is a spilled node", self.display_node(n));
608
609
                self.spilled_nodes.push(n);
            } else {
610
                let first_available_color = ok_colors.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
611
                trace!("Color {} as {}", self.display_node(n), first_available_color);
612
613
                
                if !backend::is_callee_saved(first_available_color) {
614
                    warn!("Use caller saved register {}", first_available_color);
615
616
                }
                
617
                self.colored_nodes.push(n);
qinsoon's avatar
qinsoon committed
618
                self.ig.color_node(n, first_available_color);
619
620
621
            }
        }
        
qinsoon's avatar
qinsoon committed
622
        for n in self.colored_nodes.iter() {
623
624
625
            let n = *n;
            let alias = self.get_alias(n);
            let alias_color = self.ig.get_color_of(alias).unwrap();
qinsoon's avatar
qinsoon committed
626
            
qinsoon's avatar
qinsoon committed
627
628
            trace!("Assign color to {} based on aliased {}", self.display_node(n), self.display_node(alias));
            trace!("Color {} as {}", self.display_node(n), alias_color);
629
630
631
            self.ig.color_node(n, alias_color);
        }
    }
qinsoon's avatar
qinsoon committed
632

qinsoon's avatar
qinsoon committed
633
    #[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
634
    fn rewrite_program(&mut self) {
qinsoon's avatar
qinsoon committed
635
636
637
638
639
640
        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
641
            let ssa_entry = match self.func.context.get_value(*reg_id) {
qinsoon's avatar
qinsoon committed
642
643
644
                Some(entry) => entry,
                None => panic!("The spilled register {} is not in func context", reg_id)
            };
qinsoon's avatar
qinsoon committed
645
            let mem = self.cf.frame.alloc_slot_for_spilling(ssa_entry.value().clone(), self.vm);
qinsoon's avatar
qinsoon committed
646
647
648
649

            spilled_mem.insert(*reg_id, mem);
        }

qinsoon's avatar
qinsoon committed
650
        // though we are not using this right now
qinsoon's avatar
qinsoon committed
651
        let new_temps = backend::spill_rewrite(&spilled_mem, self.func, self.cf, self.vm);
qinsoon's avatar
qinsoon committed
652
    }
653
654
655
656
657
658
659
660
661
662
663
664
    
    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
665
    }
666
}