90 lines
3.5 KiB
C++
90 lines
3.5 KiB
C++
#pragma once
|
||
#include "pass_base.h"
|
||
|
||
namespace CompSysY
|
||
{
|
||
class PassRegAlloc final : public MCPass
|
||
{
|
||
public:
|
||
PassRegAlloc() : MCPass("regalloc") {}
|
||
virtual void run(const MCModule &module) override;
|
||
const static int K = 32 - 5; // Not Allocate-able: x0, gp, tp; Reserve: sp, ra
|
||
// exclude: x0, ra, sp, gp, tp (0, 1, 2, 3, 4)
|
||
static inline std::unordered_set<int> _ok_colors = {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};
|
||
|
||
private:
|
||
// 可以按照指令内容(而不是指针地址)来给Move排序,使得算法具有更好的确定性,便于调试
|
||
struct MvCmp
|
||
{
|
||
bool operator()(MInstMove *const &lhs, const MInstMove *const &rhs) const
|
||
{
|
||
if (lhs->dst != rhs->dst) return lhs->dst < rhs->dst;
|
||
if (lhs->src != rhs->src) return lhs->src < rhs->src;
|
||
return false;
|
||
}
|
||
};
|
||
/*以下这些集合**各不相交**
|
||
precolored：机器寄存器集合，每个寄存器都预先指派了一种颜色
|
||
initial：临时寄存器集合，其中的元素既没有预着色，也没有被处理
|
||
simplifyWorklist:低度数的传送无关的结点表。
|
||
freezeWorklist：低度数的传送有关的结点表。
|
||
spillWorklist:高度数的结点表。
|
||
spilledNodes：在本轮中要被溢出的结点集合，初始为空。
|
||
coalescedNodes：已合并的寄存器集合。当合并u,v时，将v加人到这个集合中，u则被放回到某个工作表中（或反之）。
|
||
coloredNodes ：已成功着色的结点集合。
|
||
selectstack：一个包含从图中删除的临时变量的栈
|
||
*/
|
||
void reg_alloc(MFunction *);
|
||
void build(MFunction *);
|
||
void add_edge(const MOperand &u, const MOperand &v);
|
||
void make_work_list(MFunction *func);
|
||
bool move_related(const MOperand &n);
|
||
std::set<MInstMove *, MvCmp> node_moves(const MOperand &n);
|
||
std::set<MOperand> adjacent(const MOperand &n);
|
||
void decrement_degree(const MOperand &m);
|
||
void enable_moves(const MOperand &n);
|
||
void simplify();
|
||
void coalesce();
|
||
void add_work_list(const MOperand &u);
|
||
bool OK(const MOperand &t, const MOperand &r);
|
||
bool conservative(const std::set<MOperand> &nodes);
|
||
MOperand get_alias(const MOperand &n);
|
||
void combine(const MOperand &u, const MOperand &v);
|
||
void freeze();
|
||
void freeze_moves(const MOperand &u);
|
||
void select_spill();
|
||
void assign_colors(MFunction *func);
|
||
void rewrite_program(MFunction *func);
|
||
void clear();
|
||
void set_color(MFunction *);
|
||
void apply_coalesced(MFunction *);
|
||
std::map<MOperand, std::set<MOperand>> adj_list;
|
||
std::set<std::pair<MOperand, MOperand>> adj_set;
|
||
std::map<MOperand, unsigned> degree;
|
||
std::map<MOperand, std::set<MInstMove *, MvCmp>> move_list;
|
||
std::map<MOperand, MOperand> color;
|
||
std::map<MOperand, MOperand> alias;
|
||
std::set<MOperand> initial;
|
||
std::set<MOperand> simplify_worklist;
|
||
std::set<MOperand> freeze_worklist;
|
||
std::set<MOperand> spill_worklist;
|
||
std::set<MOperand> spilled_nodes;
|
||
std::set<MOperand> coalesced_nodes;
|
||
std::set<MOperand> colored_nodes;
|
||
std::vector<MOperand> select_stack;
|
||
std::set<MInstMove *, MvCmp> coalesced_moves;
|
||
std::set<MInstMove *, MvCmp> constrained_moves;
|
||
std::set<MInstMove *, MvCmp> frozen_moves;
|
||
std::set<MInstMove *, MvCmp> worklist_moves;
|
||
std::set<MInstMove *, MvCmp> active_moves;
|
||
};
|
||
|
||
class PassPeepHole final : public MCPass
|
||
{
|
||
public:
|
||
PassPeepHole() : MCPass("peep hole") {}
|
||
void run(const MCModule &module) override;
|
||
};
|
||
|
||
} // namespace CompSysY
|