To protect your data, the CISO officer has suggested users to enable GitLab 2FA as soon as possible.

coloring.rs 25.2 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
48
49
50

    // for validation
    spill_history: LinkedHashMap<MuID, P<Value>>,   // we need to log all registers get spilled with their spill location
    spill_scratch_temps: LinkedHashMap<MuID, MuID>, // we need to know the mapping between scratch temp -> original temp
51
    
52
    worklist_freeze: LinkedHashSet<NodeIndex>,
53
    frozen_moves: LinkedHashSet<Move>,
54
    
55
56
    worklist_simplify: LinkedHashSet<NodeIndex>,
    select_stack: Vec<NodeIndex>
qinsoon's avatar
qinsoon committed
57
58
}

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

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

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

73
        let coloring = GraphColoring {
qinsoon's avatar
qinsoon committed
74
75
76
77
78
            func: func,
            cf: cf,
            vm: vm,

            ig: ig,
qinsoon's avatar
qinsoon committed
79

80
            precolored: LinkedHashSet::new(),
81
            colors: {
82
                let mut map = LinkedHashMap::new();
83
84
                map.insert(backend::RegGroup::GPR, LinkedHashSet::new());
                map.insert(backend::RegGroup::FPR, LinkedHashSet::new());
85
86
87
                map
            },
            colored_nodes: Vec::new(),
qinsoon's avatar
qinsoon committed
88

89
            initial: Vec::new(),
90
            degree: LinkedHashMap::new(),
qinsoon's avatar
qinsoon committed
91

92
            worklist_moves: Vec::new(),
93
            movelist: LinkedHashMap::new(),
94
95
96
97
            active_moves: LinkedHashSet::new(),
            coalesced_nodes: LinkedHashSet::new(),
            coalesced_moves: LinkedHashSet::new(),
            constrained_moves: LinkedHashSet::new(),
98
            alias: LinkedHashMap::new(),
qinsoon's avatar
qinsoon committed
99

100
            worklist_spill: Vec::new(),
101
            spillable: LinkedHashMap::new(),
102
            spilled_nodes: Vec::new(),
qinsoon's avatar
qinsoon committed
103

qinsoon's avatar
qinsoon committed
104
            spill_history: spill_history,
qinsoon's avatar
qinsoon committed
105
            spill_scratch_temps: spill_scratch_temps,
qinsoon's avatar
qinsoon committed
106

107
108
            worklist_freeze: LinkedHashSet::new(),
            frozen_moves: LinkedHashSet::new(),
qinsoon's avatar
qinsoon committed
109

110
            worklist_simplify: LinkedHashSet::new(),
qinsoon's avatar
qinsoon committed
111
            select_stack: Vec::new(),
qinsoon's avatar
qinsoon committed
112
        };
qinsoon's avatar
qinsoon committed
113

qinsoon's avatar
qinsoon committed
114
        coloring.regalloc()
qinsoon's avatar
qinsoon committed
115
    }
qinsoon's avatar
qinsoon committed
116

117
    fn display_node(&self, node: NodeIndex) -> String {
qinsoon's avatar
qinsoon committed
118
119
120
121
122
123
124
125
126
127
128
        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
129
    
130
    fn regalloc(mut self) -> GraphColoring<'a> {
qinsoon's avatar
qinsoon committed
131
        trace!("---InterenceGraph---");
132
133
        let _p = hprof::enter("regalloc: graph coloring");

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

qinsoon's avatar
qinsoon committed
156
                trace!("{} has a degree of {}", self.display_node(node), outdegree);
qinsoon's avatar
qinsoon committed
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
            }
        }
        
        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
180
181
        self.assign_colors();

182
183
        drop(_p);

qinsoon's avatar
qinsoon committed
184
185
        if !self.spilled_nodes.is_empty() {
            trace!("spill required");
qinsoon's avatar
qinsoon committed
186
187
188
            if cfg!(debug_assertions) {
                trace!("nodes to be spilled:");
                for node in self.spilled_nodes.iter() {
qinsoon's avatar
qinsoon committed
189
                    trace!("{}", self.display_node(*node));
qinsoon's avatar
qinsoon committed
190
191
192
                }
            }

qinsoon's avatar
qinsoon committed
193
            self.rewrite_program();
qinsoon's avatar
qinsoon committed
194

qinsoon's avatar
qinsoon committed
195
            return GraphColoring::start_with_spill_history(self.spill_history.clone(), self.spill_scratch_temps.clone(), self.func, self.cf, self.vm);
qinsoon's avatar
qinsoon committed
196
197
        }

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

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

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

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

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

qinsoon's avatar
qinsoon committed
668
    fn rewrite_program(&mut self) {
qinsoon's avatar
qinsoon committed
669
670
        let spills = self.spills();

671
        let mut spilled_mem = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
672
673
674

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

qinsoon's avatar
qinsoon committed
681
682
            spilled_mem.insert(*reg_id, mem.clone());
            self.spill_history.insert(*reg_id, mem);
qinsoon's avatar
qinsoon committed
683
684
        }

qinsoon's avatar
qinsoon committed
685
686
687
688
        let scratch_temps = backend::spill_rewrite(&spilled_mem, self.func, self.cf, self.vm);
        for (k, v) in scratch_temps {
            self.spill_scratch_temps.insert(k, v);
        }
qinsoon's avatar
qinsoon committed
689
    }
690
691
692
693
694
695
696
697
698
699
700
701
    
    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
702
    }
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731

    pub fn get_assignments(&self) -> LinkedHashMap<MuID, MuID> {
        let mut ret = LinkedHashMap::new();

        for node in self.ig.nodes() {
            let temp = self.ig.get_temp_of(node);

            if temp < MACHINE_ID_END {
                continue;
            } else {
                let alias = self.get_alias(node);
                let machine_reg = match self.ig.get_color_of(alias) {
                    Some(reg) => reg,
                    None => panic!(
                        "Reg{}/{:?} (aliased as Reg{}/{:?}) is not assigned with a color",
                        self.ig.get_temp_of(node), node,
                        self.ig.get_temp_of(alias), alias)
                };

                ret.insert(temp, machine_reg);
            }
        }
        
        ret
    }

    pub fn get_spill_history(&self) -> LinkedHashMap<MuID, P<Value>> {
        self.spill_history.clone()
    }
732

qinsoon's avatar
qinsoon committed
733
734
735
736
    pub fn get_spill_scratch_temps(&self) -> LinkedHashMap<MuID, MuID> {
        self.spill_scratch_temps.clone()
    }

737
738
739
740
741
742
743
744
745
746
747
748
749
    pub fn get_coalesced(&self) -> LinkedHashMap<MuID, MuID> {
        let mut ret = LinkedHashMap::new();

        for mov in self.coalesced_moves.iter() {
            let from = self.ig.get_temp_of(mov.from);
            let to   = self.ig.get_temp_of(mov.to);

            ret.insert(from, to);
            ret.insert(to  , from);
        }

        ret
    }
750
}