shenghsi / compiler Goto Github PK

1. Create an array of jump targets
2. Load the entry indexed by the variable two bits
3. Jump to that address using the jump register, or jr, instruction

MIPS uses the jump-and-link instruction jal to call functions.
1. The jal saves the return address (the address of the next instruction) 
in the dedicated register $ra, before jumping to the function.
2. jal is the only MIPS instruction that can access the value of the
program counter, so it can store the return address PC+4 in $ra.

SPIM supports a subset of the assembler directives provided by the actual MIPS assembler:

.align n	
Align the next datum on a 2n byte boundary.

For example, .align 2 aligns the next value on a word boundary. .align 0 turns off automatic alignment of .half, .word, .float, and .double directives until the next .data or .kdata directive.

.ascii str	Store the string in memory, but do not null-terminate it.
.asciiz str	Store the string in memory and null-terminate it.
.byte b1,..., bn	Store the n values in successive bytes of memory.
.data <addr>	
The following data items should be stored in the data segment. If the optional argument addr is present, the items are stored beginning at address addr.

.double d1,..., dn	
Store the n floating point double precision numbers in successive memory locations.

.extern sym size	
Declare that the datum stored at sym is size bytes large and is a global symbol. This directive enables the assembler to store the datum in a portion of the data segment that is efficiently accessed via register $gp.

.float f1,..., fn	
Store the n floating point single precision numbers in successive memory locations.

.globl sym	
Declare that symbol sym is global and can be referenced from other files.

.half h1,..., hn	Store the n 16-bit quantities in successive memory halfwords.
.kdata <addr>	
The following data items should be stored in the kernel data segment. If the optional argument addr is present, the items are stored beginning at address addr.

.ktext <addr>	
The next items are put in the kernel text segment. In SPIM, these items may only be instructions or words (see the .word directive below). If the optional argument addr is present, the items are stored beginning at address addr.

.space n	
Allocate n bytes of space in the current segment (which must be the data segment in SPIM).

.text <addr>	
The next items are put in the user text segment. In SPIM, these items may only be instructions or words (see the .word directive below). If the optional argument addr is present, the items are stored beginning at address addr.

.word w1,..., wn	
Store the n 32-bit quantities in successive memory words. SPIM does not distinguish various parts of the data segment (.data, .rdata and .sdata).

Rule 1: The first statement in the program is the leader
Rule 2: Any statement that is the target of a branch statement is a leader
Rule 3: Any statement that immediately follows a branch or return statement is a leader

1 Until there are nodes with degree < k:
 choose such node and push it into the stack;
 delete the node and all its edges from the graph.
2 If the graph is non-empty (and all nodes have degree >= k), then:
 choose a node (using some heuristics) and spill it to the memory;
 delete the node and all its edges from the graph.
 if this results to some nodes with degree < k, then go to the step 1;  
 otherwise continue with the step 2.
3 Successively pop nodes off the stack and color them in the lowest color not used by some neighbor.

If all nodes have a degree >= k, then instead of spilling order the nodes and push them into stack.
 When taking nodes back from the stack they may still be colorable!

1 Until there are nodes with degree < k:
 choose such node and push it into the stack;
 delete the node and all its edges from the graph.
2 If the graph is non-empty (and all nodes have degree >= k), then:
 choose a node, push it into the stack, and delete it (together with edges) from the graph;
 if this results to some nodes with degree < k, then go to the step 1;
 otherwise continue with the step 2.
3 Pop a node from the stack and color it by the least free color.
 If the is no free colors, then choose an uncolored node, spill it into the memory, and go to the step 1.

 Choosing a node for spilling is a critical for efficiency.
 Chaitin's heuristics:
  to minimize the value of cost/degree , where cost is a spilling cost and degree is a current degree of the node;
  ie. choose for spilling a "cheapest" possible node which decreases the degree of most other nodes.
 Alternative popular metrics: cost/degree^2.                                                                                                                                      
 Variations:
  spilling of interference regions;
  partitioning of live ranges;
  rematerialization.

 Cost of extra load and store-instructions

Data and Memory Operations
Arithmetic and Logic operations
Control Flow operations
Coprocessor Operations (if there is a co processor)

Deterministic: Machine is in a state. Upon receipt of a symbol will go to a unique state.
Finite: Have a finite number of states
Automata: (pl. of automaton) Self operating machine

# generate parse tree
antlr4 tiger.g4
antjc *.java
grun tiger tigerprogram -gui ../test1.tiger