GitLab will be upgraded on 30 Jan 2023 from 2.00 pm (AEDT) to 3.00 pm (AEDT). During the update, GitLab and Mattermost services will not be available. If you have any concerns with this, please talk to us at N110 (b) CSIT building.

liveness.rs 17.8 KB
Newer Older
qinsoon's avatar
qinsoon committed
1
use compiler::machine_code::CompiledFunction;
2
use ast::ir::*;
qinsoon's avatar
qinsoon committed
3
use compiler::backend;
4
use utils::LinkedHashSet;
5

qinsoon's avatar
qinsoon committed
6
7
use std::collections::{HashMap, HashSet};

8
9
10
use compiler::backend::reg_alloc::graph_coloring::petgraph;
use compiler::backend::reg_alloc::graph_coloring::petgraph::Graph;
use compiler::backend::reg_alloc::graph_coloring::petgraph::graph::NodeIndex;
qinsoon's avatar
qinsoon committed
11

12
13
14
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct GraphNode {
    temp: MuID,
qinsoon's avatar
qinsoon committed
15
    color: Option<MuID>,
16
17
    group: backend::RegGroup,
    spill_cost: f32
qinsoon's avatar
qinsoon committed
18
}
19

qinsoon's avatar
qinsoon committed
20
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
21
pub struct Move{pub from: NodeIndex, pub to: NodeIndex}
22
23

pub struct InterferenceGraph {
24
25
    graph: Graph<GraphNode, (), petgraph::Undirected>,
    nodes: HashMap<MuID, NodeIndex>,
qinsoon's avatar
qinsoon committed
26
    moves: HashSet<Move>,
27
28
29
30
}

impl InterferenceGraph {
    fn new() -> InterferenceGraph {
qinsoon's avatar
qinsoon committed
31
        InterferenceGraph {
32
            graph: Graph::new_undirected(),
qinsoon's avatar
qinsoon committed
33
34
35
36
37
            nodes: HashMap::new(),
            moves: HashSet::new()
        }
    }
    
38
    fn new_node(&mut self, reg_id: MuID, context: &FunctionContext) -> NodeIndex {
qinsoon's avatar
qinsoon committed
39
40
41
        let entry = context.get_value(reg_id).unwrap();
        
        if !self.nodes.contains_key(&reg_id) {
42
            let node = GraphNode {
43
                temp: reg_id,
44
45
                color: None,
                group: backend::RegGroup::get(entry.ty()),
46
                spill_cost: 0.0f32
qinsoon's avatar
qinsoon committed
47
            };
48
49
50
51
52

            let index = self.graph.add_node(node);

            self.nodes.insert(reg_id, index);
        }
53
        
54
55
        let node_index = *self.nodes.get(&reg_id).unwrap();
        let node_mut = self.graph.node_weight_mut(node_index).unwrap();
56
57
        
        // increase node spill cost
58
        node_mut.spill_cost += 1.0f32;
59
        
60
        node_index
qinsoon's avatar
qinsoon committed
61
62
    }
    
63
    pub fn get_node(&self, reg: MuID) -> NodeIndex {
qinsoon's avatar
qinsoon committed
64
        match self.nodes.get(&reg) {
qinsoon's avatar
qinsoon committed
65
            Some(index) => *index,
qinsoon's avatar
qinsoon committed
66
            None => panic!("do not have a node for {}", reg)
qinsoon's avatar
qinsoon committed
67
68
69
        }
    }
    
70
71
72
73
74
75
76
77
    pub fn temps(&self) -> Vec<MuID>{
        let mut ret = vec![];
        for reg in self.nodes.keys() {
            ret.push(*reg);
        }
        ret
    }
    
78
    pub fn nodes(&self) -> Vec<NodeIndex> {
qinsoon's avatar
qinsoon committed
79
        let mut ret = vec![];
80
81
        for index in self.nodes.values() {
            ret.push(*index);
qinsoon's avatar
qinsoon committed
82
83
84
85
86
87
88
89
90
91
92
93
        }
        ret
    }
    
    pub fn moves(&self) -> &HashSet<Move> {
        &self.moves
    }
    
    pub fn n_nodes(&self) -> usize {
        self.nodes.len()
    }
    
94
    fn add_move(&mut self, src: NodeIndex, dst: NodeIndex) {
qinsoon's avatar
qinsoon committed
95
        self.moves.insert(Move{from: src, to: dst});
96
97
    }
    
98
99
    pub fn add_interference_edge(&mut self, from: NodeIndex, to: NodeIndex) {
        self.graph.update_edge(from, to, ());
qinsoon's avatar
qinsoon committed
100
101
    }

102
    pub fn is_interferenced_with(&self, node1: NodeIndex, node2: NodeIndex) -> bool {
103
104
105
106
107
108
        trace!("trying to find edge between {:?} and {:?}", node1, node2);
        let edge = self.graph.find_edge(node1, node2);

        trace!("edge: {:?}", edge);

        edge.is_some()
qinsoon's avatar
qinsoon committed
109
110
    }
    
111
112
    pub fn color_node(&mut self, node: NodeIndex, color: MuID) {
        self.graph.node_weight_mut(node).unwrap().color = Some(color);
qinsoon's avatar
qinsoon committed
113
114
    }
    
115
116
    pub fn is_colored(&self, node: NodeIndex) -> bool {
        self.graph.node_weight(node).unwrap().color.is_some()
qinsoon's avatar
qinsoon committed
117
118
    }
    
119
120
    pub fn get_color_of(&self, node: NodeIndex) -> Option<MuID> {
        self.graph.node_weight(node).unwrap().color
121
122
    }
    
123
124
    pub fn get_group_of(&self, node: NodeIndex) -> backend::RegGroup {
        self.graph.node_weight(node).unwrap().group
qinsoon's avatar
qinsoon committed
125
126
    }
    
127
128
    pub fn get_temp_of(&self, node: NodeIndex) -> MuID {
        self.graph.node_weight(node).unwrap().temp
129
130
    }
    
131
132
    pub fn get_spill_cost(&self, node: NodeIndex) -> f32 {
        self.graph.node_weight(node).unwrap().spill_cost
133
134
    }
    
135
    fn is_same_node(&self, node1: NodeIndex, node2: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
136
        node1 == node2
qinsoon's avatar
qinsoon committed
137
    }
138
139
140
141
142
143
144

    fn is_same_group(&self, node1: NodeIndex, node2: NodeIndex) -> bool {
        let node1 = self.graph.node_weight(node1).unwrap();
        let node2 = self.graph.node_weight(node2).unwrap();

        node1.group == node2.group
    }
qinsoon's avatar
qinsoon committed
145
    
146
147
    pub fn is_adj(&self, from: NodeIndex, to: NodeIndex) -> bool {
        self.is_interferenced_with(from, to)
qinsoon's avatar
qinsoon committed
148
149
    }
    
150
151
    pub fn outedges_of(&self, node: NodeIndex) -> Vec<NodeIndex> {
        self.graph.neighbors(node).collect()
152
153
    }
    
154
155
    pub fn outdegree_of(&self, node: NodeIndex) -> usize {
        self.outedges_of(node).len()
qinsoon's avatar
qinsoon committed
156
157
    }
    
158
159
    pub fn indegree_of(&self, node: NodeIndex) -> usize {
        self.outdegree_of(node)
qinsoon's avatar
qinsoon committed
160
161
    }
    
162
    pub fn degree_of(&self, node: NodeIndex) -> usize {
qinsoon's avatar
fix    
qinsoon committed
163
        self.outdegree_of(node)
qinsoon's avatar
qinsoon committed
164
165
    }
    
qinsoon's avatar
qinsoon committed
166
    pub fn print(&self, context: &FunctionContext) {
167
168
169
        use compiler::backend::reg_alloc::graph_coloring::petgraph::dot::Dot;
        use compiler::backend::reg_alloc::graph_coloring::petgraph::dot::Config;

qinsoon's avatar
qinsoon committed
170
171
        debug!("");
        debug!("Interference Graph");
172

qinsoon's avatar
qinsoon committed
173
        debug!("nodes:");
qinsoon's avatar
qinsoon committed
174
        for id in self.nodes.keys() {
qinsoon's avatar
qinsoon committed
175
            let val = context.get_value(*id).unwrap().value();
qinsoon's avatar
qinsoon committed
176
            debug!("Reg {} -> {:?}", val, self.nodes.get(&id).unwrap());
qinsoon's avatar
qinsoon committed
177
178
        }

qinsoon's avatar
qinsoon committed
179
        debug!("moves:");
180
        for mov in self.moves.iter() {
qinsoon's avatar
qinsoon committed
181
            debug!("Move {:?} -> {:?}", mov.from, mov.to);
182
        }
qinsoon's avatar
qinsoon committed
183

184
        debug!("graph:");
185
        debug!("\n\n{:?}\n", Dot::with_config(&self.graph, &[Config::EdgeNoLabel]));
qinsoon's avatar
qinsoon committed
186
        debug!("");
187
    }
qinsoon's avatar
qinsoon committed
188
189
}

190
191
192
fn build_live_set (cf: &mut CompiledFunction) {
    info!("start building live set");

qinsoon's avatar
qinsoon committed
193
    let n_insts = cf.mc().number_of_insts();
194
195
196
197

    let mut livein  : Vec<LinkedHashSet<MuID>> = vec![LinkedHashSet::new(); n_insts];
    let mut liveout : Vec<LinkedHashSet<MuID>> = vec![LinkedHashSet::new(); n_insts];

198
    let mut is_changed = true;
199

200
201
202
    while is_changed {
        // reset
        is_changed = false;
203

204
        for n in 0..n_insts {
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
            let in_set_old = livein[n].clone();
            let out_set_old = liveout[n].clone();

            // in[n] <- use[n] + (out[n] - def[n]);
            {
                let ref mut inset = livein[n];

                inset.clear();

                // (1) in[n] = use[n]
                inset.add_from_vec(cf.mc().get_inst_reg_uses(n));
                // (2) + out[n]
                inset.add_all(liveout[n].clone());
                // (3) - def[n]
                for def in cf.mc().get_inst_reg_defines(n) {
                    inset.remove(&def);
                }
222
            }
223

224
            // out[n] <- union(in[s] for every successor s of n)
225
226
227
228
229
230
231
            {
                let ref mut outset = liveout[n];
                outset.clear();

                for s in cf.mc().get_succs(n) {
                    outset.add_all(livein[*s].clone());
                }
232
            }
233
234
235
236

            // is in/out changed in this iteration?
            let n_changed = !in_set_old.equals(&livein[n]) || !out_set_old.equals(&liveout[n]);

237
238
239
            is_changed = is_changed || n_changed;
        }
    }
240

qinsoon's avatar
qinsoon committed
241
    for block in cf.mc().get_all_blocks().to_vec() {
242
        let start_inst = cf.mc().get_block_range(&block).unwrap().start;
243
        cf.mc_mut().set_ir_block_livein(&block, livein[start_inst].clone().to_vec());
244
245

        let end_inst = cf.mc().get_block_range(&block).unwrap().end;
246
        cf.mc_mut().set_ir_block_liveout(&block, liveout[end_inst].clone().to_vec());
247
    }
248
249
}

250
// from Tailoring Graph-coloring Register Allocation For Runtime Compilation, Figure 4
251
pub fn build_chaitin_briggs (cf: &mut CompiledFunction, func: &MuFunctionVersion) -> InterferenceGraph {
252
    build_live_set(cf);
253
    
254
255
256
    let mut ig = InterferenceGraph::new();
    
    // precolor machine register nodes
257
    for reg in backend::all_regs().values() {
258
259
        let reg_id = reg.extract_ssa_id().unwrap();
        let node = ig.new_node(reg_id, &func.context);
qinsoon's avatar
qinsoon committed
260
261
262
263

        let precolor = backend::get_color_for_precolroed(reg_id);

        ig.color_node(node, precolor);
264
265
266
    }
    
    // Initialize and creates nodes for all the involved temps/regs
qinsoon's avatar
qinsoon committed
267
268
    for i in 0..cf.mc().number_of_insts() {
        for reg_id in cf.mc().get_inst_reg_defines(i) {
269
270
271
            ig.new_node(reg_id, &func.context);
        }
        
qinsoon's avatar
qinsoon committed
272
        for reg_id in cf.mc().get_inst_reg_uses(i) {
273
274
275
276
            ig.new_node(reg_id, &func.context);
        }
    }
    
qinsoon's avatar
qinsoon committed
277
    for block in cf.mc().get_all_blocks() {
278
        // Current_Live(B) = LiveOut(B)
qinsoon's avatar
qinsoon committed
279
        let mut current_live = LinkedHashSet::from_vec(match cf.mc().get_ir_block_liveout(&block) {
280
281
282
            Some(liveout) => liveout.to_vec(),
            None => panic!("cannot find liveout for block {}", block)
        });
qinsoon's avatar
qinsoon committed
283
284
285
286
287
288
        if cfg!(debug_assertions) {
            trace!("Block{}: live out", block);
            for ele in current_live.iter() {
                trace!("{}", func.context.get_temp_display(*ele));
            }
        }
289
        
qinsoon's avatar
qinsoon committed
290
        let range = cf.mc().get_block_range(&block);
291
        if range.is_none() {
qinsoon's avatar
qinsoon committed
292
            warn!("Block{}: has no range (no instructions?)", block);
293
294
            continue;
        }
qinsoon's avatar
qinsoon committed
295
        trace!("Block{}: range = {:?}", block, range.as_ref().unwrap());
296
297
298
        
        // for every inst I in reverse order
        for i in range.unwrap().rev() {
qinsoon's avatar
qinsoon committed
299
300
301
302
303
304
305
            if cfg!(debug_assertions) {
                trace!("Block{}: Inst{}: start. current_live:", block, i);
                for ele in current_live.iter() {
                    trace!("{}", func.context.get_temp_display(*ele));
                }
            }

306
            let src : Option<MuID> = {
qinsoon's avatar
qinsoon committed
307
308
309
                if cf.mc().is_move(i) {
                    let src = cf.mc().get_inst_reg_uses(i);
                    let dst = cf.mc().get_inst_reg_defines(i);
310
                    
qinsoon's avatar
qinsoon committed
311
312
313
                    // src:  reg/imm/mem
                    // dest: reg/mem
                    // we dont care if src/dest is mem
qinsoon's avatar
qinsoon committed
314
                    if cf.mc().is_using_mem_op(i) {
315
                        None
qinsoon's avatar
qinsoon committed
316
317
318
319
                    } else {
                        if src.len() == 1 {
                            let node1 = ig.get_node(src[0]);
                            let node2 = ig.get_node(dst[0]);
qinsoon's avatar
qinsoon committed
320
321
322
                            trace!("add move between {} and {}",
                                   func.context.get_temp_display(src[0]),
                                   func.context.get_temp_display(dst[0]));
qinsoon's avatar
qinsoon committed
323
324
325
326
327
328
                            ig.add_move(node1, node2);
                            
                            Some(src[0])
                        } else {
                            None
                        }
329
330
331
332
333
                    }
                } else {
                    None
                }
            };
qinsoon's avatar
qinsoon committed
334
            trace!("Block{}: Inst{}: src={:?}", block, i, src);
335
336
            
            // for every definition D in I
qinsoon's avatar
qinsoon committed
337
            for d in cf.mc().get_inst_reg_defines(i) {
qinsoon's avatar
qinsoon committed
338
                trace!("Block{}: Inst{}: for definition {}", block, i, func.context.get_temp_display(d));
339
340
341
                // add an interference from D to every element E in Current_Live - {D}
                // creating nodes if necessary
                for e in current_live.iter() {
qinsoon's avatar
qinsoon committed
342
343
344
                    trace!("Block{}: Inst{}: for each live {}",
                           block, i,
                           func.context.get_temp_display(*e));
345
                    if src.is_none() || (src.is_some() && *e != src.unwrap()) {
qinsoon's avatar
qinsoon committed
346
                        let from = ig.get_node(d);
347
348
                        let to = ig.get_node(*e);
                        
qinsoon's avatar
qinsoon committed
349
                        if !ig.is_same_node(from, to) &&ig.is_same_group(from, to) && !ig.is_adj(from, to) {
350
                            if !ig.is_colored(from) {
qinsoon's avatar
qinsoon committed
351
352
353
354
                                trace!("Block{}: Inst{}: add interference between {} and {}",
                                       block, i,
                                       func.context.get_temp_display(d),
                                       func.context.get_temp_display(*e));
355
356
357
                                ig.add_interference_edge(from, to);
                            }
                            if !ig.is_colored(to) {
qinsoon's avatar
qinsoon committed
358
359
360
361
                                trace!("Block{}: Inst{}: add interference between {} and {}",
                                       block, i,
                                       func.context.get_temp_display(*e),
                                       func.context.get_temp_display(d));
362
363
364
365
366
367
368
369
                                ig.add_interference_edge(to, from);
                            }
                        }
                    }
                }
            }
            
            // for every definition D in I
qinsoon's avatar
qinsoon committed
370
            for d in cf.mc().get_inst_reg_defines(i) {
qinsoon's avatar
qinsoon committed
371
372
373
                trace!("Block{}: Inst{}: remove define {} from current_live",
                       block, i,
                       func.context.get_temp_display(d));
374
                // remove D from Current_Live
qinsoon's avatar
qinsoon committed
375
                current_live.remove(&d);
376
377
378
            }
            
            // for every use U in I
qinsoon's avatar
qinsoon committed
379
            for u in cf.mc().get_inst_reg_uses(i) {
qinsoon's avatar
qinsoon committed
380
381
382
                trace!("Block{}: Inst{}: add use {} to current_live",
                       block, i,
                       func.context.get_temp_display(u));
383
                // add U to Current_live
qinsoon's avatar
qinsoon committed
384
                current_live.insert(u);
385
            }
qinsoon's avatar
qinsoon committed
386
387
388
389
390
391
392

            if cfg!(debug_assertions) {
                trace!("Block{}: Inst{}: done. current_live:", block, i);
                for ele in current_live.iter() {
                    trace!("{}", func.context.get_temp_display(*ele));
                }
            }
393
394
395
396
397
398
        }
    }
    
    ig
}

399
// from tony's code src/RegAlloc/Liveness.java
400
// this function is no longer used
qinsoon's avatar
qinsoon committed
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
//#[allow(dead_code)]
//pub fn build (cf: &CompiledFunction, func: &MuFunctionVersion) -> InterferenceGraph {
//    let mut ig = InterferenceGraph::new();
//
//    // precolor machine register nodes
//    for reg in backend::all_regs().values() {
//        let reg_id = reg.extract_ssa_id().unwrap();
//        let node = ig.new_node(reg_id, &func.context);
//        ig.color_node(node, reg_id);
//    }
//
//    // Liveness Analysis
//    let n_insts = cf.mc().number_of_insts();
//    let mut live_in : Vec<Vec<MuID>> = vec![vec![]; n_insts];
//    let mut live_out : Vec<Vec<MuID>> = vec![vec![]; n_insts];
//    let mut work_list : LinkedList<usize> = LinkedList::new();
//
//    // Initialize 'in' sets for each node in the flow graph
//    // and creates nodes for all the involved temps/regs
//    for i in 0..n_insts {
//        let ref mut in_set = live_in[i];
//
//        for reg_id in cf.mc().get_inst_reg_defines(i) {
//            ig.new_node(reg_id, &func.context);
//        }
//
//        for reg_id in cf.mc().get_inst_reg_uses(i) {
//            ig.new_node(reg_id, &func.context);
//
//            in_set.push(reg_id);
//        }
//
//        work_list.push_front(i);
//    }
//
//    // all nodes has been added, we init graph (create adjacency matrix)
//    ig.init_graph();
//
//    // compute liveIn and liveOut iteratively
//    trace!("build live outs");
//    while !work_list.is_empty() {
//        let n = work_list.pop_front().unwrap();
//        trace!("build liveout for #{}", n);
//        let ref mut out_set = live_out[n];
//
//        // out = union(in[succ]) for all succs
//        for succ in cf.mc().get_succs(n) {
//            trace!("add successor's livein {:?} to #{}", &live_in[*succ], n);
//            vec_utils::add_all(out_set, &live_in[*succ]);
//        }
//
//        // in = use(i.e. live_in) + (out - def)
//        let mut diff = out_set.clone();
//        for def in cf.mc().get_inst_reg_defines(n) {
//            vec_utils::remove_value(&mut diff, def);
//            trace!("removing def: {}", def);
//            trace!("diff = {:?}", diff);
//        }
//        trace!("out - def = {:?}", diff);
//
//        if !diff.is_empty() {
//            let ref mut in_set = live_in[n];
//            trace!("in = (use) {:?}", in_set);
//
//            if vec_utils::add_all(in_set, &diff) {
//                for p in cf.mc().get_preds(n) {
//                    work_list.push_front(*p);
//                }
//            }
//        }
//        trace!("in = use + (out - def) = {:?}", live_in[n]);
//    }
//
//    // debug live-outs
//    if cfg!(debug_assertions) {
//        trace!("check live-outs");
//        for n in 0..n_insts {
//            let ref mut live = live_out[n];
//            trace!("#{}\t{:?}", n, live);
//        }
//    }
//
//    // build interference graph
//    for n in 0..n_insts {
//        let ref mut live = live_out[n];
//
//        let src : Option<MuID> = {
//            if cf.mc().is_move(n) {
//                let src = cf.mc().get_inst_reg_uses(n);
//                let dst = cf.mc().get_inst_reg_defines(n);
//
//                // src may be an immediate number
//                // but dest is definitly a register
//                debug_assert!(dst.len() == 1);
//
//                if src.len() == 1 {
//                    let node1 = ig.get_node(src[0]);
//                    let node2 = ig.get_node(dst[0]);
//                    ig.add_move(node1, node2);
//
//                    Some(src[0])
//                } else {
//                    None
//                }
//            } else {
//                None
//            }
//        };
//
//        for d in cf.mc().get_inst_reg_defines(n) {
//            for t in live.iter() {
//                if src.is_none() || (src.is_some() && *t != src.unwrap()) {
//                    let from = ig.get_node(d);
//                    let to = ig.get_node(*t);
//
//                    if !ig.is_same_node(from, to) && !ig.is_adj(from, to) {
//                        if !ig.is_colored(from) {
//                            ig.add_interference_edge(from, to);
//                        }
//                        if !ig.is_colored(to) {
//                            ig.add_interference_edge(to, from);
//                        }
//                    }
//                }
//            }
//        }
//
//        for d in cf.mc().get_inst_reg_defines(n) {
//            vec_utils::remove_value(live, d);
//        }
//
//        for u in cf.mc().get_inst_reg_uses(n) {
//            live.push(u);
//        }
//    }
//
//    ig
//}