rat/src/backend/codegen/reg_alloc.h at main · hexratcc/rat · GitHub

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#ifndef RAT_CODEGEN_REGALLOC_H
#define RAT_CODEGEN_REGALLOC_H

#include "core.h"

#include "codegen/machine_function.h"
#include "pass/pass.h"

namespace rat {
	namespace detail {
		PhysReg firstFree(const List<PhysReg>& regs, U64 blocked);
		U32 loopWeight(I32 depth, U32& level);
		void groupBy(const List<Pair<U32, U32>>& in, U32 nk, List<U32>& first, List<U32>& out);
	} // namespace detail

	struct RegAllocPass : MachinePass {
		explicit RegAllocPass(B32 local = false)
		: local(local) {}

		const C8* name() const override { return "regalloc"; }
		B32 run(Module& module, const Function& fn, MachineFunc& mf, const TargetInfo& target) override;
	private:
		using Seg = Pair<I32, I32>;

		struct Interval {
			List<Seg> segs;
			F32 weight = 0;
			VReg root = kNoVReg;
			PhysReg hint = kNoReg;
			PhysReg reg = kNoReg;
			I32 slot = 0;

			void reset(VReg self); // keeps the segment storage
		};

		void setup(const TargetInfo& target);
		void allocate(MachineFunc& f);
		// intervals
		void number();
		void pinFixed(const MachineInstr& in, U64 u, B32 copy, U64& live);
		void liveness();
		void buildIntervals();
		void addSeg(VReg v, I32 start, I32 end);
		void noteCopy(const MachineInstr& in, U32 level);
		// assignment
		void coalesce();
		VReg find(VReg v);
		B32 overlaps(VReg a, VReg b) const;
		void merge(VReg a, VReg b);
		void assignRegs();
		void assignSlots(List<Pair<I32, VReg>>& spilled);
		I32 newSlot(U32 cls);
		PhysReg pick(VReg v) const;
		// debug records
		B32 covers(VReg v, I32 pos) const;
		MachineOperand home(const MachineOperand& o) const;
		void checkDebugLive();
		void rewriteDebug();
		// rewrite
		void rewrite();
		B32 rewriteCopy(List<MachineInstr>& out, const MachineInstr& in, U32 i);
		PhysReg regOf(const MachineOperand& o) const;
		void rewriteInstr(List<MachineInstr>& out, MachineInstr& in, U32 i);
		PhysReg spillReg(List<MachineInstr>& out, const MachineOperand& o, U32 i, B32 use);
		PhysReg pickTemp(U32 cls, U64 hard, U64 soft);
		// queries
		B32 isCopy(const MachineInstr& in) const;
		const Interval& bundle(VReg v) const;
		B32 sameBundle(const MachineOperand& a, const MachineOperand& b) const;
	private:
		B32 local = false;
		MachineFunc* fn = nullptr;
		const RegisterInfo* ri = nullptr;
		RegAllocHooks hooks;
		U32 nv = 0;
		U64 allocMask[kMaxRegClasses] = {};
		U64 calleeMask = 0;
		// numbering
		List<U32> blockFirst; // block -> first instruction
		List<U64> busy;				// slot -> busy physical registers
		List<U8> copyAt;			// instruction -> is a coalescable copy
		List<U64> chunk;			// 64 slots -> busy anywhere in them
		U64 usedCallee = 0;
		// liveness and bundles
		List<U32> outFirst; // block -> first of its live-out vregs
		List<VReg> outVRegs;
		List<U8> cross;		 // vreg -> lives on the stack (local mode)
		List<Interval> iv; // grows only, the first nv are live
		List<Seg> merged;	 // merge scratch
		List<U64> copies;	 // (kMaxLevel - level, def, source)
		// rewrite of the current instruction
		List<Pair<VReg, PhysReg>> temps; // spilled bundle -> its temp
		U64 taken = 0;									 // temps
		U64 own = 0;										 // clobbers
		List<MachineInstr> stores;
	};
} // namespace rat

#endif