tac

package
v0.0.0-...-209b98f Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 12, 2019 License: MIT Imports: 12 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	// Variables which are dead have their next-use set to MaxInt.
	MaxInt = int(^uint(0) >> 1)
	MinInt = -MaxInt - 1
)
View Source 
const (
	// arithmetic operators
	ADD = "+"
	SUB = "-"
	MUL = "*"
	DIV = "/"
	REM = "%"
	EQ  = "="

	// branch operators
	BGT = "bgt"
	BGE = "bge"
	BLT = "blt"
	BLE = "ble"
	BEQ = "beq"
	BNE = "bne"
	JMP = "jmp"

	// array operators
	FROM = "from"
	INTO = "into"

	// binary operators
	OR  = "or"
	AND = "and"
	NOR = "nor"
	XOR = "xor"
	NOT = "not"

	// shift operators
	RST = ">>"
	LST = "<<"

	// function operators
	FUNC  = "func"
	LABEL = "label"
	RET   = "ret"
	CALL  = "call"
	STORE = "store"

	CMT = "#" // comments

	// declaration operators
	DECL    = "decl"
	DECLInt = "declInt"
	DECLSTR = "declStr"

	// I/O operators
	SCANINT  = "scanInt"
	PRINTINT = "printInt"
	PRINTSTR = "printStr"
)
View Source 
const (
	NIL   = iota
	FALSE // cannot be dropped
	MAYBE // might be dropped
	TRUE  // will be dropped
)

The following constant declarations determine the confidence in dropping a basic block from the three-address code data structure.

View Source 
const RegLimit = 32

RegLimit determines the upper bound on the number of free registers at any given instant supported by the concerned architecture (MIPS in this case).

Variables

This section is empty.

Functions

func IsBranchOp 

func IsBranchOp(op string) bool

IsBranchOp verifies whether the given operator is jump/branch.

Types

type Addr 

type Addr struct {
	Reg int
	Mem int
}

type Blk 

type Blk struct {
	Stmts []Stmt
	// Address descriptor
	//	* Keeps track of location where current value of the
	//	  name can be found at compile time.
	//	* The location can be either one or a set of -
	//		- register
	//		- memory address
	//		- stack (TODO)
	Adesc map[string]Addr
	// Register descriptor
	//	* Keeps track of what is currently in each register.
	//	* Initially all registers are empty.
	Rdesc      map[int]RegDesc
	NextUseTab [][]UseInfo
	Pq         PriorityQueue
	// contains filtered or unexported fields
}

Blk represents the structure of a basic block.

func InitBlock 

func InitBlock() *Blk

InitBlock initializes the basic block data structure.

func (Blk) EvalNextUseInfo 

func (blk Blk) EvalNextUseInfo()

Next-use allocation heuristic ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Traverse the statements in a basic block from bottom-up, while updating the next-use symbol table using the following algorithm (x = y op z) - 

Step 1: attach to i'th line in NextUseTab information currently
	in symbol table (nuSymTab) about variables x, y and z.
Step 2: mark x as dead and no next-use in nuSymTab.
Step 3: mark y and z to be live and set their next-use to i in nuSymTab.

func (Blk) FindNextUse 

func (blk Blk) FindNextUse(line int, name string) int

FindNextUse returns the next-use information corresponding to a variable "name" available in line number "line" of the table.

func (Blk) GetReg 

func (blk Blk) GetReg(stmt *Stmt, ts *TextSec, typeInfo map[string]types.RegType)

Register allocation ~~~~~~~~~~~~~~~~~~~ Arguments:

  • stmt: The allocator ensures that all the variables available in Stmt object have been allocated a register.
  • ts: If a register had to be spilled when GetReg() was called, the text segment should be updated with an equivalent "sw" instruction.

GetReg handles all the side-effects induced due to register allocation -

  • Updating lookup tables.
  • Generating additional instructions resulting due to register spilling.

A note on register spilling ~~~~~~~~~~~~~~~~~~~~~~~~~~~ A variable which doesn't have a next-use in the current basic block is spilled right away even if there are free registers available, resulting in one "sw" instruction. In case spilling was avoided and one of the free registers was used instead, that too would have resulted in one "sw" instruction at the end of the basic block.

func (*Blk) InitHeap 

func (blk *Blk) InitHeap()

InitHeap initializes the heap used during register allocation.

func (*Blk) InitRegDS 

func (blk *Blk) InitRegDS()

InitRegDS initializes the basic block data structures relevant to registers.

func (*Blk) IsDirty 

func (blk *Blk) IsDirty(reg int) bool

IsDirty determines if the given register is dirty.

func (*Blk) IsLoaded 

func (blk *Blk) IsLoaded(reg int, varName string) bool

IsLoaded determines whether the given register stores the value of the given variable and the value has been loaded from memory.

func (*Blk) MarkDirty 

func (blk *Blk) MarkDirty(reg int)

MarkDirty marks the given register as dirty. A register whose contents have been modified after being loaded from memory is marked dirty.

func (*Blk) MarkLoaded 

func (blk *Blk) MarkLoaded(reg int)

MarkLoaded is invoked after loading a variable from memory, and it marks the corresponding register's entry as loaded.

func (*Blk) NewBlock 

func (blk *Blk) NewBlock(tac *Tac) (*Blk, int)

NewBlock creates a new basic block and initializes its line number to 0.

func (*Blk) UnmarkDirty 

func (blk *Blk) UnmarkDirty(reg int)

UnmarkDirty marks the given register as free.

func (*Blk) UnmarkLoaded 

func (blk *Blk) UnmarkLoaded(reg int)

UnmarkLoaded unmarks the register entry as loaded.

type Child 

type Child struct {
	// contains filtered or unexported fields
}

Child determines the index of the left and right child of a basic block in a flow graph.

type DataFlowInfo 

type DataFlowInfo struct {
	Gen  set
	Kill set
	In   set
	Out  set
}

DataFlowInfo represents the data structures used in the data-flow analysis.

type DataSec 

type DataSec struct {
	// Stmts is a slice of statements which will be flushed into the data
	// section of the generated assembly file.
	Stmts bytes.Buffer
	// Lookup keeps track of all the variables currently available in the
	// the data section.
	Lookup map[string]bool
}

Data section

type I32 

type I32 int

func (I32) IntVal 

func (U I32) IntVal() int

func (I32) StrVal 

func (U I32) StrVal() string

type Label 

type Label struct {
	// contains filtered or unexported fields
}

type PriorityQueue 

type PriorityQueue []*UseInfo

func (PriorityQueue) Len 

func (pq PriorityQueue) Len() int

func (PriorityQueue) Less 

func (pq PriorityQueue) Less(i, j int) bool

func (*PriorityQueue) Pop 

func (pq *PriorityQueue) Pop() interface{}

func (*PriorityQueue) Push 

func (pq *PriorityQueue) Push(x interface{})

func (PriorityQueue) Swap 

func (pq PriorityQueue) Swap(i, j int)

type RegDesc 

type RegDesc struct {
	// Name determines the variable name whose value the register stores.
	Name string
	// Dirty determines whether the value of the variable stored by the
	// register has changed after loading from memory.
	Dirty bool
	// Loaded determines whether the variable whose value the register is
	// supposed to store has been loaded from memory.
	Loaded bool
}

type SrcVar 

type SrcVar interface {
	IntVal() int
	StrVal() string
}

SrcVar defines the properties of a source variable.

type Stmt 

type Stmt struct {
	Line int      // line number where the statement is available
	Op   string   // operator
	Dst  string   // destination variable
	Src  []SrcVar // source variables
}

Stmt defines the structure of a single statement in three-address code form.

type Str 

type Str string

func (Str) IntVal 

func (U Str) IntVal() (i int)

func (Str) StrVal 

func (U Str) StrVal() string

type Tac 

type Tac []Blk

Tac represents the three-address code for the entire source program.

func GenTAC 

func GenTAC(file string) (tac Tac)

GenTAC generates the three-address code (in-memory) data structure from the input file. The format of each statement in the input file is a tuple of the form - 

<line-number, operation, destination-variable, source-variable(s)>

The three-address code is a collection of basic block data structures, which are identified while reading the IR file as per following rules - 

A basic block starts:
	* at label instruction
	* after jump instruction
and ends:
	* before label instruction
	* at jump instruction

func (Tac) ControlFlow 

func (tac Tac) ControlFlow() Tac

--- [ Flow-of-Control Optimizations ] --------------------------------------- Consider the following code sequence - 

goto L1
...
L1: goto L2

The unnecessary jump to L1 can be eliminated as follows - 

goto L2
...
L1: goto L2

If there are no more jumps to L1, the entire label can be dropped provided that it is immediately preceded by an unconditional jump. Similar logic can be extended to branch statements.

A notation which is used in the following segment is a "fallthrough label". Fallthrough labels are the blocks which are not preceded by an unconditional jump. Consider the following code - 

a = 0
L1: a = 1

In the above code, L1 is a fallthrough label.

ControlFlow performs flow of control optimizations.

func (Tac) EvalDataFlowSets 

func (tac Tac) EvalDataFlowSets()

EvalDataFlowSets computes the data-flow sets GEN and KILL.

func (Tac) EvalFlowGraph 

func (tac Tac) EvalFlowGraph(labelMap labelinfotype)

EvalFlowGraph generates a flow graph from a three-address code DS. When a jump/branch is encountered, the target and the next basic block is marked as the right and left child respectively. The immediate predecessors of all the basic blocks are also updated.

func (Tac) EvalTransferFuncs 

func (tac Tac) EvalTransferFuncs()

Transfer functions evaluation ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The following equations are used for evaluating the transfer functions -

  • IN[n] = ∪ p∈pred(n) OUT[p]
  • OUT[n] = GEN[n] ∪ (IN[n] − KILL[n])

These transfer functions are evaluated using a fixpoint computation.

func (Tac) FixLineNumbers 

func (tac Tac) FixLineNumbers()

FixLineNumbers fixes the line numbers in each basic block in case they get disturbed after the optimization passes finish. Correctness of line numbers is essential to ensure proper calculation of next-use information.

func (Tac) JumpsOverJumps 

func (tac Tac) JumpsOverJumps() Tac

--- [ Eliminating jumps over jumps ] ---------------------------------------- Consider the following code sequence - 

if debug == 1 goto L1
goto L2
L1: print debugging information
L2:

After eliminating jumps over jumps, the transformed code looks as - 

if debug != 1 goto L2
print debugging information
L2:

JumpsOverJumps performs jump-over-jump peephole optimization.

func (Tac) LabelInfo 

func (tac Tac) LabelInfo() labelinfotype

LabelInfo traverses across the tac DS and collects details about label statements.

func (Tac) PeepHole 

func (tac Tac) PeepHole() Tac

PeepHole performs peephole optimizations on the generated three-address code data structure.

func (Tac) PrintTAC 

func (tac Tac) PrintTAC()

PrintTAC pretty-prints the three-address code IR.

type TextSec 

type TextSec struct {
	// Stmts is a slice of statements which will be flushed into the text
	// section of the generated assembly file.
	Stmts bytes.Buffer
}

type UseInfo 

type UseInfo struct {
	// The Name field is used in two different contexts -
	//	- when dealing with priority queue of registers, it is the name
	//	  of a register
	//	- when dealing with lookup tables, it is the name of a variable
	Name string
	// Nextuse determines the next usage (line number) of a varible. If the
	// variable is dead, its Nextuse is set to MaxInt.
	Nextuse int
}

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.