changeset 189:a45e535f7742

Determine live ranges for logical registers as part of initial work on register allocator
author Mike Pavone <pavone@retrodev.com>
date Mon, 26 Aug 2013 18:23:05 -0700
parents 7e313849ab41
children 372cbd2cd243
files modules/il.tp
diffstat 1 files changed, 124 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- a/modules/il.tp	Mon Aug 26 18:21:57 2013 -0700
+++ b/modules/il.tp	Mon Aug 26 18:23:05 2013 -0700
@@ -48,6 +48,13 @@
 			numops <- { 3 }
 			name <- { _names get: _opcode }
 			string <- { name . " " . (string: _ina) . " " . (string: _inb) . " " . (string: _out) . " " . (string: _size) }
+			recordUsage:at <- :tracker :address {
+				if: (not: (_ina isInteger?)) {
+					_ina recordUsage: tracker at: 0 | address withSize: _size
+				}
+				_inb recordUsage: tracker at: 0 | address withSize: _size
+				_out recordUsage: tracker at: 1 | address withSize: _size
+			}
 		}
 	}
 	op2:in:out:size <- :_opcode :_in :_out :_size {
@@ -59,6 +66,12 @@
 			numops <- { 2 }
 			name <- { _names get: _opcode }
 			string <- { name . " " . (string: _in) . " " . (string: _out) . " " . (string: _size) }
+			recordUsage:at <- :tracker :address {
+				if: (not: (_in isInteger?)) {
+					_in recordUsage: tracker at: 0 | address withSize: _size
+				}
+				_out recordUsage: tracker at: 1 | address withSize: _size
+			}
 		}
 	}
 	op1:arg:size <- :_opcode :_arg :_size {
@@ -69,6 +82,11 @@
 			numops <- { 1 }
 			name <- { _names get: _opcode }
 			string <- { name . " " . (string: _arg) . " " . (string: _size) }
+			recordUsage:at <- :tracker :address {
+				if: (not: (_arg isInteger?)) {
+					_arg recordUsage: tracker at: address withSize: _size
+				}
+			}
 		}
 	}
 
@@ -108,6 +126,12 @@
 		= <- :other {
 			(not: (other isInteger?)) && (other register?) && (other return?)
 		}
+		!= <- :other {
+			not: self = other
+		}
+		recordUsage:at:withSize <- :tracker :address :size {
+			//TODO: Figure out what tracking is necessary here
+		}
 	}
 
 	_condnames <- #[
@@ -173,6 +197,12 @@
 				= <- :other {
 					(not: (other isInteger?)) && (other register?) && (not: (other argument?)) && (not: (other return?)) && num = (other regnum)
 				}
+				!= <- :other {
+					not: self = other
+				}
+				recordUsage:at:withSize <- :tracker :address :size {
+					tracker reg: self usedAt: address withSize: size
+				}
 			}
 		}
 		arg <- :num {
@@ -186,10 +216,30 @@
 				= <- :other {
 					(not: (other isInteger?)) && (other register?) && (other argument?)  && num = (other regnum)
 				}
+				!= <- :other {
+					not: self = other
+				}
+				recordUsage:at:withSize <- :tracker :address :size {
+					tracker arg: self usedAt: address withSize: size
+				}
 			}
 		}
 		retr <- { _retr }
 
+		base:offset <- :_base :_offset {
+			#{
+				base <- { _base }
+				offset <- { _offset }
+				string <- {
+					start <- if: _offset = 0 { "" } else: { (string: _offset) }
+					start . "[" . (string: _base) . "]"
+				}
+				recordUsage:at:withSize <- :tracker :address :size {
+					_base recordUsage: tracker at: address withSize: size
+				}
+			}
+		}
+
 		add <- :ina inb out size {
 			op3: _add a: ina b: inb out: out size: size
 		}
@@ -255,6 +305,16 @@
 					}
 					name . " " . (string: _target) . " " . (argstr join: " ")
 				}
+				recordUsage:at <- :tracker :address {
+					if: (not: (_target isString?)) {
+						//TODO: use size l for 32-bit targets or an abstract pointer size
+						_target recordUsage: tracker at: address withSize: q
+					}
+					foreach: _args :_ arg {
+						//TODO: have some mechanism for properly expressing sizes of arguments
+						arg recordUsage: tracker at: address withSize: q
+					}
+				}
 			}
 		}
 
@@ -275,9 +335,71 @@
 					}
 					name . " " . (string: _cond) . " {" . block .  "}"
 				}
+				recordUsage:at <- :tracker :address {
+					foreach: _toskip :idx inst {
+						inst recordUsage: tracker at: idx | address
+					}
+				}
 			}
 		}
 
+		allocRegs:withSource <- :instarr:regSrc {
+			_regMap <- dict linear
+			_argMap <- dict linear
+
+			_usageTracker <- :_firstUsage {
+				#{
+					firstUsage <- _firstUsage
+					lastUsage <- _firstUsage
+					useCount <- 0
+					maxSize <- byte
+					usedAt:withSize <- :address :size {
+						useCount <- useCount + 1
+						lastUsage <- address
+						if: size > maxSize {
+							maxSize <- size
+						}
+					}
+					string <- {
+						"Uses: " . useCount . ", FirstUse: " . (firstUsage join: ":") . ", Last Use: " . (lastUsage join: ":") . ", Max Size: " . maxSize
+					}
+				}
+			}
+
+			_maxUses <- 0
+			_maxUseReg <- false
+			regUsage <- #{
+				reg:usedAt:withSize <- :reg :address :size {
+					usage <- _regMap get: reg elseSet: {
+						_usageTracker: address
+					}
+					usage usedAt: address withSize: size
+					if: (usage useCount) > _maxUses {
+						_maxUses <- usage useCount
+						_maxUseReg <- reg
+					}
+				}
+				arg:usedAt:withSize <- :arg :address :size {
+					usage <- _argMap get: arg elseSet: {
+						_usageTracker: [0 0]
+					}
+					usage usedAt: address withSize: size
+				}
+				print <- {
+					foreach: _regMap :reg usage {
+						print: (string: reg) . " | " . (string: usage) . "\n"
+					}
+					foreach: _argMap :arg usage {
+						print: (string: arg) . " | " . (string: usage) . "\n"
+					}
+				}
+			}
+			foreach: instarr :idx inst {
+				inst recordUsage: regUsage at: [idx]
+			}
+			print: regUsage
+		}
+
 		//used to convert IL to a format suitable for a 2-operand architecture
 		//should be run after register allocation (I think....)
 		to2Op <- :instarr {
@@ -323,6 +445,8 @@
 			foreach: fib :idx inst {
 				print: (string: inst) . "\n"
 			}
+			print: "\n\nUsage:\n\n"
+			allocRegs: fib withSource: false
 			fib2 <- to2Op: fib
 			print: "\n\n2-Operand:\n\n"
 			foreach: fib2 :idx inst {