# HG changeset patch # User Mike Pavone # Date 1377571996 25200 # Node ID 4293c725394c68516c2aeeede75d24a4dc17a5b1 # Parent a868a2aec9302c1d737ed68dd63f930e081c5d87 Mostly complete register allocation in il module with a register source in the x86 module diff -r a868a2aec930 -r 4293c725394c modules/il.tp --- 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 { diff -r a868a2aec930 -r 4293c725394c modules/x86.tp --- 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: