const (
	VRegIDNonReservedBegin = vRegIDReservedForRealNum

	VRegInvalid = VReg(vRegIDInvalid)
)

type Allocator[I Instr, B Block[I], F Function[I, B]] struct {
	// contains filtered or unexported fields
}

type Block[I Instr] interface {
	comparable
	// ID returns the unique identifier of this block which is ordered in the reverse post-order traversal of the CFG.
	ID() int32
	// InstrIteratorBegin returns the first instruction in this block. Instructions added after lowering must be skipped.
	// Note: multiple Instr(s) will not be held at the same time, so it's safe to use the same impl for the return Instr.
	InstrIteratorBegin() I
	// InstrIteratorNext returns the next instruction in this block. Instructions added after lowering must be skipped.
	// Note: multiple Instr(s) will not be held at the same time, so it's safe to use the same impl for the return Instr.
	InstrIteratorNext() I
	// InstrRevIteratorBegin is the same as InstrIteratorBegin, but in the reverse order.
	InstrRevIteratorBegin() I
	// InstrRevIteratorNext is the same as InstrIteratorNext, but in the reverse order.
	InstrRevIteratorNext() I
	// FirstInstr returns the fist instruction in this block where instructions will be inserted after it.
	FirstInstr() I
	// LastInstrForInsertion returns the last instruction in this block where instructions will be inserted before it.
	// Such insertions only happen when we need to insert spill/reload instructions to adjust the merge edges.
	// At the time of register allocation, all the critical edges are already split, so there is no need
	// to worry about the case where branching instruction has multiple successors.
	// Therefore, usually, it is the nop instruction, but if the block ends with an unconditional branching, then it returns
	// the unconditional branch, not the nop. In other words it is either nop or unconditional branch.
	LastInstrForInsertion() I
	// Preds returns the number of predecessors of this block in the CFG.
	Preds() int
	// Entry returns true if the block is for the entry block.
	Entry() bool
	// Succs returns the number of successors of this block in the CFG.
	Succs() int
	// LoopHeader returns true if this block is a loop header.
	LoopHeader() bool
	// LoopNestingForestChildren returns the number of children of this block in the loop nesting forest.
	LoopNestingForestChildren() int
}

type Function[I Instr, B Block[I]] interface {
	// PostOrderBlockIteratorBegin returns the first block in the post-order traversal of the CFG.
	// In other words, the last blocks in the CFG will be returned first.
	PostOrderBlockIteratorBegin() B
	// PostOrderBlockIteratorNext returns the next block in the post-order traversal of the CFG.
	PostOrderBlockIteratorNext() B
	// ReversePostOrderBlockIteratorBegin returns the first block in the reverse post-order traversal of the CFG.
	// In other words, the first blocks in the CFG will be returned first.
	ReversePostOrderBlockIteratorBegin() B
	// ReversePostOrderBlockIteratorNext returns the next block in the reverse post-order traversal of the CFG.
	ReversePostOrderBlockIteratorNext() B
	// ClobberedRegisters tell the clobbered registers by this function.
	ClobberedRegisters([]VReg)
	// LoopNestingForestRoots returns the number of roots of the loop nesting forest in a function.
	LoopNestingForestRoots() int
	// LoopNestingForestRoot returns the i-th root of the loop nesting forest in a function.
	LoopNestingForestRoot(i int) B
	// LowestCommonAncestor returns the lowest common ancestor of two blocks in the dominator tree.
	LowestCommonAncestor(blk1, blk2 B) B
	// Idom returns the immediate dominator of the given block.
	Idom(blk B) B

	// LoopNestingForestChild returns the i-th child of the block in the loop nesting forest.
	LoopNestingForestChild(b B, i int) B
	// Pred returns the i-th predecessor of the block in the CFG.
	Pred(b B, i int) B
	// Succ returns the i-th successor of the block in the CFG.
	Succ(b B, i int) B
	// BlockParams returns the virtual registers used as the parameters of this block.
	BlockParams(B, *[]VReg) []VReg

	// SwapBefore swaps the two virtual registers at the end of the given block.
	SwapBefore(x1, x2, tmp VReg, instr I)
	// StoreRegisterBefore inserts store instruction(s) before the given instruction for the given virtual register.
	StoreRegisterBefore(v VReg, instr I)
	// StoreRegisterAfter inserts store instruction(s) after the given instruction for the given virtual register.
	StoreRegisterAfter(v VReg, instr I)
	// ReloadRegisterBefore inserts reload instruction(s) before the given instruction for the given virtual register.
	ReloadRegisterBefore(v VReg, instr I)
	// ReloadRegisterAfter inserts reload instruction(s) after the given instruction for the given virtual register.
	ReloadRegisterAfter(v VReg, instr I)
	// InsertMoveBefore inserts move instruction(s) before the given instruction for the given virtual registers.
	InsertMoveBefore(dst, src VReg, instr I)
}

type Instr interface {
	comparable
	fmt.Stringer
	// Defs returns the virtual registers defined by this instruction.
	Defs(*[]VReg) []VReg
	// Uses returns the virtual registers used by this instruction.
	// Note: multiple returned []VReg will not be held at the same time, so it's safe to use the same slice for this.
	Uses(*[]VReg) []VReg
	// AssignUse assigns the RealReg-allocated virtual register used by this instruction at the given index.
	AssignUse(index int, v VReg)
	// AssignDef assigns a RealReg-allocated virtual register defined by this instruction.
	// This only accepts one register because we don't allocate registers for multi-def instructions (i.e. call instruction)
	AssignDef(VReg)
	// IsCopy returns true if this instruction is a move instruction between two registers.
	// If true, the instruction is of the form of dst = src, and if the src and dst do not interfere with each other,
	// we could coalesce them, and hence the copy can be eliminated from the final code.
	IsCopy() bool
	// IsCall returns true if this instruction is a call instruction. The result is used to insert
	// caller saved register spills and restores.
	IsCall() bool
	// IsIndirectCall returns true if this instruction is an indirect call instruction which calls a function pointer.
	//  The result is used to insert caller saved register spills and restores.
	IsIndirectCall() bool
	// IsReturn returns true if this instruction is a return instruction.
	IsReturn() bool
}

type RealReg byte

const RealRegInvalid RealReg = 0

type RegSet uint64

type RegType byte

const (
	RegTypeInvalid RegType = iota
	RegTypeInt
	RegTypeFloat
	NumRegType
)

type RegisterInfo struct {
	// AllocatableRegisters is a 2D array of allocatable RealReg, indexed by regTypeNum and regNum.
	// The order matters: the first element is the most preferred one when allocating.
	AllocatableRegisters [NumRegType][]RealReg
	CalleeSavedRegisters RegSet
	CallerSavedRegisters RegSet
	RealRegToVReg        []VReg
	// RealRegName returns the name of the given RealReg for debugging.
	RealRegName func(r RealReg) string
	RealRegType func(r RealReg) RegType
}

type VReg uint64

type VRegID uint32