flux_refineck/
queue.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
use std::collections::BinaryHeap;

use rustc_index::{bit_set::BitSet, IndexVec};
use rustc_middle::mir::BasicBlock;

struct Item<'a> {
    bb: BasicBlock,
    dominator_order_rank: &'a IndexVec<BasicBlock, u32>,
}

pub(crate) struct WorkQueue<'a> {
    heap: BinaryHeap<Item<'a>>,
    set: BitSet<BasicBlock>,
    dominator_order_rank: &'a IndexVec<BasicBlock, u32>,
}

impl<'a> WorkQueue<'a> {
    pub(crate) fn empty(len: usize, dominator_order_rank: &'a IndexVec<BasicBlock, u32>) -> Self {
        Self {
            heap: BinaryHeap::with_capacity(len),
            set: BitSet::new_empty(len),
            dominator_order_rank,
        }
    }

    pub(crate) fn insert(&mut self, bb: BasicBlock) -> bool {
        if self.set.insert(bb) {
            self.heap
                .push(Item { bb, dominator_order_rank: self.dominator_order_rank });
            true
        } else {
            false
        }
    }

    pub(crate) fn pop(&mut self) -> Option<BasicBlock> {
        if let Some(Item { bb, .. }) = self.heap.pop() {
            self.set.remove(bb);
            Some(bb)
        } else {
            None
        }
    }
}

impl PartialEq for Item<'_> {
    fn eq(&self, other: &Self) -> bool {
        self.bb == other.bb
    }
}

impl PartialOrd for Item<'_> {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Eq for Item<'_> {}

impl Ord for Item<'_> {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.dominator_order_rank[other.bb].cmp(&self.dominator_order_rank[self.bb])
    }
}