changeset 193:4293c725394c

Mostly complete register allocation in il module with a register source in the x86 module
author Mike Pavone <pavone@retrodev.com>
date Mon, 26 Aug 2013 19:53:16 -0700
parents a868a2aec930
children 30bed95cbb18
files modules/il.tp modules/x86.tp
diffstat 2 files changed, 222 insertions(+), 20 deletions(-) [+]
line wrap: on
line diff
--- a/modules/il.tp	Mon Aug 26 19:50:17 2013 -0700
+++ b/modules/il.tp	Mon Aug 26 19:53:16 2013 -0700
@@ -91,31 +91,34 @@
 	}
 
 	_sizenames <- #["b" "w" "l" "q"]
-	_size <- :_num {
+	_size <- :_bytes {
 		#{
-			num <- { _num }
-			string <- { _sizenames get: _num }
+			bytes <- { _bytes }
+			string <- {
+				idx <- if: _bytes = 8 { 3 } else: { _bytes / 2}
+				_sizenames get: idx
+			}
 			= <- :other {
-				_num = (other num)
+				_bytes = (other bytes)
 			}
 			<= <- :other {
-				_num <= (other num)
+				_bytes <= (other bytes)
 			}
 			>= <- :other {
-				_num >= (other num)
+				_bytes >= (other bytes)
 			}
 			> <- :other {
-				_num > (other num)
+				_bytes > (other bytes)
 			}
 			< <- :other {
-				_num < (other num)
+				_bytes < (other bytes)
 			}
 		}
 	}
-	byte <- _size: 0
-	word <- _size: 1
-	long <- _size: 2
-	quad <- _size: 3
+	byte <- _size: 1
+	word <- _size: 2
+	long <- _size: 4
+	quad <- _size: 8
 
 	_retr <- #{
 		isInteger? <- { false }
@@ -367,23 +370,23 @@
 			}
 
 			_maxUses <- 0
-			_maxUseReg <- false
 			regUsage <- #{
 				reg:usedAt:withSize <- :reg :address :size {
+					raddress <- address reverse
 					usage <- _regMap get: reg elseSet: {
-						_usageTracker: address
+						_usageTracker: raddress
 					}
-					usage usedAt: address withSize: size
+					usage usedAt: raddress withSize: size
 					if: (usage useCount) > _maxUses {
 						_maxUses <- usage useCount
-						_maxUseReg <- reg
 					}
 				}
 				arg:usedAt:withSize <- :arg :address :size {
+					raddress <- address reverse
 					usage <- _argMap get: arg elseSet: {
 						_usageTracker: [0 0]
 					}
-					usage usedAt: address withSize: size
+					usage usedAt: raddress withSize: size
 				}
 				print <- {
 					foreach: _regMap :reg usage {
@@ -398,6 +401,79 @@
 				inst recordUsage: regUsage at: [idx]
 			}
 			print: regUsage
+
+			addrLessEq <- :left :right {
+				lesseq <- true
+				while: { lesseq && (not: (left empty?)) && (not: (right empty?)) } do: {
+					if: (left value) > (right value) {
+						lesseq <- false
+					} else: {
+						if:  (left value) < (right value) {
+							left <- []
+						} else: {
+							left <- left tail
+							right <- right tail
+						}
+					}
+				}
+				lesseq
+			}
+
+			addrGreatEq <- :left :right {
+				greateq <- true
+				while: { greateq && (not: (left empty?)) && (not: (right empty?)) } do: {
+					if: (left value) < (right value) {
+						greateq <- false
+					} else: {
+						if:  (left value) > (right value) {
+							left <- []
+						} else: {
+							left <- left tail
+							right <- right tail
+						}
+					}
+				}
+				greateq
+			}
+
+			liveFrom:to <- :regs :from :to {
+				live <- #[]
+				foreach: regs :reg usage {
+					if: ((usage lastUsage) addrGreatEq: from) && ((usage firstUsage) addrLessEq: to) {
+						live append: reg
+					}
+				}
+				live
+			}
+
+			_assignments <- dict linear
+			curuses <- _maxUses
+			while: { curuses > 0 && (_assignments length) < (_regMap length) } do: {
+				foreach: _regMap  :reg usage {
+					if: (usage useCount) = curuses {
+						liveArgs <- _argMap liveFrom: (usage firstUsage) to: (usage lastUsage)
+						foreach: liveArgs :_ arg {
+							regSrc allocArg: (arg num)
+						}
+
+						liveRegs <- _regMap liveFrom: (usage firstUsage) to: (usage lastUsage)
+						print: (string: reg) . " | Live: " . (liveRegs join: ", ") . ", Live Args: " . (liveArgs join: ", ") . "\n"
+						foreach: liveRegs :_ reg {
+							if: (_assignments contains?: reg) {
+								regSrc allocSpecific: (_assignments get: reg)
+							}
+						}
+						_assignments set: reg (regSrc alloc: (usage maxSize))
+
+						regSrc returnAll
+					}
+				}
+				curuses <- curuses - 1
+			}
+			print: "\n\nAssignments:\n\n"
+			foreach: _assignments :reg assign {
+				print: (string: reg) . " = " . assign . "\n"
+			}
 		}
 
 		//used to convert IL to a format suitable for a 2-operand architecture
@@ -446,7 +522,7 @@
 				print: (string: inst) . "\n"
 			}
 			print: "\n\nUsage:\n\n"
-			allocRegs: fib withSource: false
+			allocRegs: fib withSource: (x86 regSource)
 			fib2 <- to2Op: fib
 			print: "\n\n2-Operand:\n\n"
 			foreach: fib2 :idx inst {
--- a/modules/x86.tp	Mon Aug 26 19:50:17 2013 -0700
+++ b/modules/x86.tp	Mon Aug 26 19:53:16 2013 -0700
@@ -128,8 +128,8 @@
 	}
 
 	mod_rm:withTail <- :register regmem :end {
-		l <- regmem rm: end
-		(l value) or ( lshift: (register reg) by: 3u8) | (l tail)
+		list <- regmem rm: end
+		(list value) or ( lshift: (register reg) by: 3u8) | (list tail)
 	}
 
 	mod_rm <- :reg rm {
@@ -190,6 +190,30 @@
 	_dh <- upper: 6u8
 	_bh <- upper: 7u8
 
+	//AMD64 convention
+	_argregs <- #[
+		_rdi
+		_rsi
+		_rdx
+		_rcx
+		_r8
+		_r9
+	]
+	_calleesave <- #[
+		_rbx
+		_rbp
+		_r12
+		_r13
+		_r14
+		_r15
+	]
+	_tempregs <- #[
+		_r10
+		_r11
+		_rax
+	]
+
+
 	inst <- :ilist {
 		#{
 			length <- { ilist length }
@@ -477,6 +501,108 @@
 			inst: (prefix: fakesrc dst d withInstruction: base)
 		}
 
+		//TODO: support multiple calling conventions
+		regSource <- {
+			_used <- 0
+			_usedAllTime <- 0
+			_nextStackOff <- 0
+			_findUnused <- :size reglists{
+				found <- -1
+				foundlist <- -1
+				curlist <- 0
+				ll <- reglists length
+				while: { found < 0 && curlist < ll } do: {
+					cur <- 0
+					regs <- reglists get: curlist
+					len <- regs length
+					while: { found < 0 && cur < len } do: {
+						bit <- lshift: 1 by: cur
+						if: (_used and bit) = 0 {
+							found <- cur
+							foundlist <- regs
+							_used <- _used or bit
+							_usedAllTime <- _usedAllTime or bit
+						}
+						cur <- cur + 1
+					}
+					curlist <- curlist + 1
+				}
+				if: found >= 0 {
+					foundlist get: found
+				} else: {
+					myoff <- _nextStackOff
+					_nextStackOff <- _nextStackOff + size
+					il base: _rsp offset: myoff
+				}
+			}
+			#{
+				alloc <- :size {
+					_findUnused: size #[
+						_calleesave
+						_tempregs
+						_argregs
+					]
+				}
+				//used to allocate a register
+				//that will be returned before a call
+				allocTemp <- :size {
+					_findUnused: size #[
+						_tempregs
+						_argregs
+						_calleesave
+					]
+				}
+				//allocated the return register
+				allocRet <- :size {
+					bit <- (lshift: 1 by: (_rax num))
+					_used <- _used or bit
+					_usedAllTime <- _usedAllTime or bit
+					_rax
+				}
+				allocArg <- :argnum {
+					if: argnum < (_argregs length) {
+						reg <- _argregs get: argnum
+						bit <- (lshift: 1 by: (reg num))
+						_used <- _used or bit
+						_usedAllTime <- _usedAllTime or bit
+					} else: {
+						il base: _rsp offset: _nextStackOff + 8 * (argnum - (_argregs length))
+					}
+				}
+				allocSpecific <- :reg {
+					if: (reg register?) {
+						bit <- (lshift: 1 by: (reg num))
+						_used <- _used or bit
+					}
+				}
+				stackSize <- { _nextStackOff }
+				return <- :reg {
+					_used <- _used and (0xF xor (lshift: 1 by: (reg num)))
+				}
+				returnAll <- { _used = 0 }
+				needSaveProlog <- {
+					retval <- #[]
+					foreach: _calleesave :idx reg {
+						if: (_usedAllTime and (lshift: 1 by: (reg num))) != 0 {
+							retval append: reg
+						}
+					}
+					retval
+				}
+				needSaveForCall <- {
+					retval <- #[]
+					foreach: #[_tempregs _argregs] :_ regs {
+						foreach: regs :_ reg {
+							if: (_used and (lshift: 1 by: (reg num))) != 0 {
+								retval append: reg
+							}
+						}
+					}
+					retval
+				}
+			}
+		}
+
 		main <- {
 			fib <- label:
 			notbase <- label: