[apple/javascriptcore.git] / offlineasm / risc.rb

# Copyright (C) 2011, 2012 Apple Inc. All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
# 1. Redistributions of source code must retain the above copyright
#    notice, this list of conditions and the following disclaimer.
# 2. Redistributions in binary form must reproduce the above copyright
#    notice, this list of conditions and the following disclaimer in the
#    documentation and/or other materials provided with the distribution.
#
# THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
# THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
# PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
# BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
# THE POSSIBILITY OF SUCH DAMAGE.

require 'config'
require 'ast'
require 'opt'

# This file contains utilities that are useful for implementing a backend
# for RISC-like processors (ARM, MIPS, etc).

#
# Lowering of simple branch ops. For example:
#
# baddiz foo, bar, baz
#
# will become:
#
# addi foo, bar
# bz baz
#

def riscLowerSimpleBranchOps(list)
    newList = []
    list.each {
        | node |
        if node.is_a? Instruction
            annotation = node.annotation
            case node.opcode
            when /^b(addi|subi|ori|addp)/
                op = $1
                branch = "b" + $~.post_match
                
                case op
                when "addi"
                    op = "addis"
                when "addp"
                    op = "addps"
                when "subi"
                    op = "subis"
                when "ori"
                    op = "oris"
                end
                
                newList << Instruction.new(node.codeOrigin, op, node.operands[0..-2], annotation)
                newList << Instruction.new(node.codeOrigin, branch, [node.operands[-1]])
            when 'bmulis', 'bmulz', 'bmulnz'
                condition = $~.post_match
                newList << Instruction.new(node.codeOrigin, "muli", node.operands[0..-2], annotation)
                newList << Instruction.new(node.codeOrigin, "bti" + condition, [node.operands[-2], node.operands[-1]])
            else
                newList << node
            end
        else
            newList << node
        end
    }
    newList
end

#
# Lowing of complex branch ops. For example:
#
# bmulio foo, bar, baz
#
# becomes:
#
# smulli foo, bar, bar, tmp1
# rshifti bar, 31, tmp2
# bineq tmp1, tmp2, baz
#

def riscLowerHardBranchOps(list)
    newList = []
    list.each {
        | node |
        if node.is_a? Instruction and node.opcode == "bmulio"
            tmp1 = Tmp.new(node.codeOrigin, :gpr)
            tmp2 = Tmp.new(node.codeOrigin, :gpr)
            newList << Instruction.new(node.codeOrigin, "smulli", [node.operands[0], node.operands[1], node.operands[1], tmp1], node.annotation)
            newList << Instruction.new(node.codeOrigin, "rshifti", [node.operands[-2], Immediate.new(node.codeOrigin, 31), tmp2])
            newList << Instruction.new(node.codeOrigin, "bineq", [tmp1, tmp2, node.operands[-1]])
        else
            newList << node
        end
    }
    newList
end

#
# Lowering of shift ops. For example:
#
# lshifti foo, bar
#
# will become:
#
# andi foo, 31, tmp
# lshifti tmp, bar
#

def riscSanitizeShift(operand, list)
    return operand if operand.immediate?
    
    tmp = Tmp.new(operand.codeOrigin, :gpr)
    list << Instruction.new(operand.codeOrigin, "andi", [operand, Immediate.new(operand.codeOrigin, 31), tmp])
    tmp
end

def riscLowerShiftOps(list)
    newList = []
    list.each {
        | node |
        if node.is_a? Instruction
            case node.opcode
            when "lshifti", "rshifti", "urshifti", "lshiftp", "rshiftp", "urshiftp"
                if node.operands.size == 2
                    newList << Instruction.new(node.codeOrigin, node.opcode, [riscSanitizeShift(node.operands[0], newList), node.operands[1]], node.annotation)
                else
                    newList << Instruction.new(node.codeOrigin, node.opcode, [node.operands[0], riscSanitizeShift(node.operands[1], newList), node.operands[2]], node.annotation)
                    raise "Wrong number of operands for shift at #{node.codeOriginString}" unless node.operands.size == 3
                end
            else
                newList << node
            end
        else
            newList << node
        end
    }
    newList
end

#
# Lowering of malformed addresses. For example:
#
# loadp 10000[foo], bar
#
# will become:
#
# move 10000, tmp
# addp foo, tmp
# loadp 0[tmp], bar
#
# Note that you use this lowering phase by passing it a block that returns true
# if you don't want to lower the address, or false if you do. For example to get
# the effect of the example above, the block would have to say something like:
#
# riscLowerMalformedAddresses(thingy) {
#     | node, address |
#     if address.is_a? Address
#         address.offset.value > 1000
#     else
#         true # don't lower anything else, in this example
#     end
# }
#
# See arm.rb for a different example, in which we lower all BaseIndex addresses
# that have non-zero offset, all Address addresses that have large offsets, and
# all other addresses (like AbsoluteAddress).
#

class Node
    def riscLowerMalformedAddressesRecurse(list, topLevelNode, &block)
        mapChildren {
            | subNode |
            subNode.riscLowerMalformedAddressesRecurse(list, topLevelNode, &block)
        }
    end
end

class Address
    def riscLowerMalformedAddressesRecurse(list, node, &block)
        return self if yield node, self

        tmp = Tmp.new(codeOrigin, :gpr)
        list << Instruction.new(codeOrigin, "move", [offset, tmp])
        list << Instruction.new(codeOrigin, "addp", [base, tmp])
        Address.new(codeOrigin, tmp, Immediate.new(codeOrigin, 0))
    end
end

class BaseIndex
    def riscLowerMalformedAddressesRecurse(list, node, &block)
        return self if yield node, self
        
        tmp = Tmp.new(codeOrigin, :gpr)
        list << Instruction.new(codeOrigin, "leap", [BaseIndex.new(codeOrigin, base, index, scale, Immediate.new(codeOrigin, 0)), tmp])
        Address.new(codeOrigin, tmp, offset).riscLowerMalformedAddressesRecurse(list, node, &block)
    end
end

class AbsoluteAddress
    def riscLowerMalformedAddressesRecurse(list, node, &block)
        return self if yield node, self
        
        tmp = Tmp.new(codeOrigin, :gpr)
        list << Instruction.new(codeOrigin, "move", [address, tmp])
        Address.new(codeOrigin, tmp, Immediate.new(codeOrigin, 0))
    end
end

def riscLowerMalformedAddresses(list, &block)
    newList = []
    list.each {
        | node |
        newList << node.riscLowerMalformedAddressesRecurse(newList, node, &block)
    }
    newList
end

#
# Lowering of malformed addresses in double loads and stores. For example:
#
# loadd [foo, bar, 8], baz
#
# becomes:
#
# leap [foo, bar, 8], tmp
# loadd [tmp], baz
#

class Node
    def riscDoubleAddress(list)
        self
    end
end

class BaseIndex
    def riscDoubleAddress(list)
        tmp = Tmp.new(codeOrigin, :gpr)
        list << Instruction.new(codeOrigin, "leap", [self, tmp])
        Address.new(codeOrigin, tmp, Immediate.new(codeOrigin, 0))
    end
end

def riscLowerMalformedAddressesDouble(list)
    newList = []
    list.each {
        | node |
        if node.is_a? Instruction
            case node.opcode
            when "loadd"
                newList << Instruction.new(node.codeOrigin, "loadd", [node.operands[0].riscDoubleAddress(newList), node.operands[1]], node.annotation)
            when "stored"
                newList << Instruction.new(node.codeOrigin, "stored", [node.operands[0], node.operands[1].riscDoubleAddress(newList)], node.annotation)
            else
                newList << node
            end
        else
            newList << node
        end
    }
    newList
end

#
# Lowering of misplaced immediates for opcodes in opcodeList. For example, if storei is in opcodeList:
#
# storei 0, [foo]
#
# will become:
#
# move 0, tmp
# storei tmp, [foo]
#

def riscLowerMisplacedImmediates(list, opcodeList)
    newList = []
    list.each {
        | node |
        if node.is_a? Instruction
            if opcodeList.include? node.opcode
                operands = node.operands
                newOperands = []
                operands.each {
                    | operand |
                    if operand.is_a? Immediate
                        tmp = Tmp.new(operand.codeOrigin, :gpr)
                        newList << Instruction.new(operand.codeOrigin, "move", [operand, tmp])
                        newOperands << tmp
                    else
                        newOperands << operand
                    end
                }
                newList << Instruction.new(node.codeOrigin, node.opcode, newOperands, node.annotation)
            else
                newList << node
            end
        else
            newList << node
        end
    }
    newList
end

#
# Lowering of malformed immediates except when used in a "move" instruction.
# For example:
#
# addp 642641, foo
#
# will become:
#
# move 642641, tmp
# addp tmp, foo
#

class Node
    def riscLowerMalformedImmediatesRecurse(list, validImmediates)
        mapChildren {
            | node |
            node.riscLowerMalformedImmediatesRecurse(list, validImmediates)
        }
    end
end

class Address
    def riscLowerMalformedImmediatesRecurse(list, validImmediates)
        self
    end
end

class BaseIndex
    def riscLowerMalformedImmediatesRecurse(list, validImmediates)
        self
    end
end

class AbsoluteAddress
    def riscLowerMalformedImmediatesRecurse(list, validImmediates)
        self
    end
end

class Immediate
    def riscLowerMalformedImmediatesRecurse(list, validImmediates)
        unless validImmediates.include? value
            tmp = Tmp.new(codeOrigin, :gpr)
            list << Instruction.new(codeOrigin, "move", [self, tmp])
            tmp
        else
            self
        end
    end
end

def riscLowerMalformedImmediates(list, validImmediates)
    newList = []
    list.each {
        | node |
        if node.is_a? Instruction
            annotation = node.annotation
            case node.opcode
            when "move"
                newList << node
            when "addi", "addp", "addq", "addis", "subi", "subp", "subq", "subis"
                if node.operands[0].is_a? Immediate and
                        (not validImmediates.include? node.operands[0].value) and
                        validImmediates.include? -node.operands[0].value
                        node.operands.size == 2
                    if node.opcode =~ /add/
                        newOpcode = "sub" + $~.post_match
                    else
                        newOpcode = "add" + $~.post_match
                    end
                    newList << Instruction.new(node.codeOrigin, newOpcode,
                                               [Immediate.new(node.codeOrigin, -node.operands[0].value)] + node.operands[1..-1],
                                               annotation)
                else
                    newList << node.riscLowerMalformedImmediatesRecurse(newList, validImmediates)
                end
            when "muli", "mulp", "mulq"
                if node.operands[0].is_a? Immediate
                    tmp = Tmp.new(codeOrigin, :gpr)
                    newList << Instruction.new(node.codeOrigin, "move", [node.operands[0], tmp], annotation)
                    newList << Instruction.new(node.codeOrigin, node.opcode, [tmp] + node.operands[1..-1])
                else
                    newList << node.riscLowerMalformedImmediatesRecurse(newList, validImmediates)
                end
            else
                newList << node.riscLowerMalformedImmediatesRecurse(newList, validImmediates)
            end
        else
            newList << node
        end
    }
    newList
end

#
# Lowering of misplaced addresses. For example:
#
# addi foo, [bar]
#
# will become:
#
# loadi [bar], tmp
# addi foo, tmp
# storei tmp, [bar]
#
# Another example:
#
# addi [foo], bar
#
# will become:
#
# loadi [foo], tmp
# addi tmp, bar
#

def riscAsRegister(preList, postList, operand, suffix, needStore)
    return operand unless operand.address?
    
    tmp = Tmp.new(operand.codeOrigin, if suffix == "d" then :fpr else :gpr end)
    preList << Instruction.new(operand.codeOrigin, "load" + suffix, [operand, tmp])
    if needStore
        postList << Instruction.new(operand.codeOrigin, "store" + suffix, [tmp, operand])
    end
    tmp
end

def riscAsRegisters(preList, postList, operands, suffix)
    newOperands = []
    operands.each_with_index {
        | operand, index |
        newOperands << riscAsRegister(preList, postList, operand, suffix, index == operands.size - 1)
    }
    newOperands
end

def riscLowerMisplacedAddresses(list)
    newList = []
    list.each {
        | node |
        if node.is_a? Instruction
            postInstructions = []
            annotation = node.annotation
            case node.opcode
            when "addi", "addis", "andi", "lshifti", "muli", "negi", "noti", "ori", "oris",
                "rshifti", "urshifti", "subi", "subis", "xori", /^bi/, /^bti/, /^ci/, /^ti/
                newList << Instruction.new(node.codeOrigin,
                                           node.opcode,
                                           riscAsRegisters(newList, postInstructions, node.operands, "i"),
                                           annotation)
            when "addp", "andp", "lshiftp", "mulp", "negp", "orp", "rshiftp", "urshiftp",
                "subp", "xorp", /^bp/, /^btp/, /^cp/
                newList << Instruction.new(node.codeOrigin,
                                           node.opcode,
                                           riscAsRegisters(newList, postInstructions, node.operands, "p"),
                                           annotation)
            when "addq", "andq", "lshiftq", "mulq", "negq", "orq", "rshiftq", "urshiftq",
                "subq", "xorq", /^bq/, /^btq/, /^cq/
                newList << Instruction.new(node.codeOrigin,
                                           node.opcode,
                                           riscAsRegisters(newList, postInstructions, node.operands, "q"),
                                           annotation)
            when "bbeq", "bbneq", "bba", "bbaeq", "bbb", "bbbeq", "btbz", "btbnz", "tbz", "tbnz",
                "cbeq", "cbneq", "cba", "cbaeq", "cbb", "cbbeq"
                newList << Instruction.new(node.codeOrigin,
                                           node.opcode,
                                           riscAsRegisters(newList, postInstructions, node.operands, "b"),
                                           annotation)
            when "bbgt", "bbgteq", "bblt", "bblteq", "btbs", "tbs", "cbgt", "cbgteq", "cblt", "cblteq"
                newList << Instruction.new(node.codeOrigin,
                                           node.opcode,
                                           riscAsRegisters(newList, postInstructions, node.operands, "bs"),
                                           annotation)
            when "addd", "divd", "subd", "muld", "sqrtd", /^bd/
                newList << Instruction.new(node.codeOrigin,
                                           node.opcode,
                                           riscAsRegisters(newList, postInstructions, node.operands, "d"),
                                           annotation)
            when "jmp", "call"
                newList << Instruction.new(node.codeOrigin,
                                           node.opcode,
                                           [riscAsRegister(newList, postInstructions, node.operands[0], "p", false)],
                                           annotation)
            else
                newList << node
            end
            newList += postInstructions
        else
            newList << node
        end
    }
    newList
end

#
# Lowering of register reuse in compare instructions. For example:
#
# cieq t0, t1, t0
#
# will become:
#
# mov tmp, t0
# cieq tmp, t1, t0
#

def riscLowerRegisterReuse(list)
    newList = []
    list.each {
        | node |
        if node.is_a? Instruction
            annotation = node.annotation
            case node.opcode
            when "cieq", "cineq", "cia", "ciaeq", "cib", "cibeq", "cigt", "cigteq", "cilt", "cilteq",
                "cpeq", "cpneq", "cpa", "cpaeq", "cpb", "cpbeq", "cpgt", "cpgteq", "cplt", "cplteq",
                "tis", "tiz", "tinz", "tbs", "tbz", "tbnz", "tps", "tpz", "tpnz", "cbeq", "cbneq",
                "cba", "cbaeq", "cbb", "cbbeq", "cbgt", "cbgteq", "cblt", "cblteq"
                if node.operands.size == 2
                    if node.operands[0] == node.operands[1]
                        tmp = Tmp.new(node.codeOrigin, :gpr)
                        newList << Instruction.new(node.codeOrigin, "move", [node.operands[0], tmp], annotation)
                        newList << Instruction.new(node.codeOrigin, node.opcode, [tmp, node.operands[1]])
                    else
                        newList << node
                    end
                else
                    raise "Wrong number of arguments at #{node.codeOriginString}" unless node.operands.size == 3
                    if node.operands[0] == node.operands[2]
                        tmp = Tmp.new(node.codeOrigin, :gpr)
                        newList << Instruction.new(node.codeOrigin, "move", [node.operands[0], tmp], annotation)
                        newList << Instruction.new(node.codeOrigin, node.opcode, [tmp, node.operands[1], node.operands[2]])
                    elsif node.operands[1] == node.operands[2]
                        tmp = Tmp.new(node.codeOrigin, :gpr)
                        newList << Instruction.new(node.codeOrigin, "move", [node.operands[1], tmp], annotation)
                        newList << Instruction.new(node.codeOrigin, node.opcode, [node.operands[0], tmp, node.operands[2]])
                    else
                        newList << node
                    end
                end
            else
                newList << node
            end
        else
            newList << node
        end
    }
    newList
end

#
# Lowering of the not instruction. The following:
#
# noti t0
#
# becomes:
#
# xori -1, t0
#

def riscLowerNot(list)
    newList = []
    list.each {
        | node |
        if node.is_a? Instruction
            case node.opcode
            when "noti", "notp"
                raise "Wrong nubmer of operands at #{node.codeOriginString}" unless node.operands.size == 1
                suffix = node.opcode[-1..-1]
                newList << Instruction.new(node.codeOrigin, "xor" + suffix,
                                           [Immediate.new(node.codeOrigin, -1), node.operands[0]])
            else
                newList << node
            end
        else
            newList << node
        end
    }
    return newList
end

#
# Lowing of complex branch ops on 64-bit. For example:
#
# bmulio foo, bar, baz
#
# becomes:
#
# smulli foo, bar, bar
# rshiftp bar, 32, tmp1
# rshifti bar, 31, tmp2
# zxi2p bar, bar 
# bineq tmp1, tmp2, baz
#

def riscLowerHardBranchOps64(list)
    newList = []
    list.each {
        | node |
        if node.is_a? Instruction and node.opcode == "bmulio"
            tmp1 = Tmp.new(node.codeOrigin, :gpr)
            tmp2 = Tmp.new(node.codeOrigin, :gpr)
            newList << Instruction.new(node.codeOrigin, "smulli", [node.operands[0], node.operands[1], node.operands[1]])
            newList << Instruction.new(node.codeOrigin, "rshiftp", [node.operands[1], Immediate.new(node.codeOrigin, 32), tmp1])
            newList << Instruction.new(node.codeOrigin, "rshifti", [node.operands[1], Immediate.new(node.codeOrigin, 31), tmp2])
            newList << Instruction.new(node.codeOrigin, "zxi2p", [node.operands[1], node.operands[1]])
            newList << Instruction.new(node.codeOrigin, "bineq", [tmp1, tmp2, node.operands[2]])
        else
            newList << node
        end
    }
    newList
end

#
# Lowering of test instructions. For example:
#
# btiz t0, t1, .foo
#
# becomes:
#
# andi t0, t1, tmp
# bieq tmp, 0, .foo
#
# and another example:
#
# tiz t0, t1, t2
#
# becomes:
#
# andi t0, t1, tmp
# cieq tmp, 0, t2
#

def riscLowerTest(list)
    def emit(newList, andOpcode, branchOpcode, node)
        if node.operands.size == 2
            newList << Instruction.new(node.codeOrigin, branchOpcode, [node.operands[0], Immediate.new(node.codeOrigin, 0), node.operands[1]])
            return
        end

        raise "Incorrect number of operands at #{codeOriginString}" unless node.operands.size == 3

        if node.operands[0].immediate? and node.operands[0].value == -1
            newList << Instruction.new(node.codeOrigin, branchOpcode, [node.operands[1], Immediate.new(node.codeOrigin, 0), node.operands[2]])
            return
        end

        if node.operands[1].immediate? and node.operands[1].value == -1
            newList << Instruction.new(node.codeOrigin, branchOpcode, [node.operands[0], Immediate.new(node.codeOrigin, 0), node.operands[2]])
            return
        end
        
        tmp = Tmp.new(node.codeOrigin, :gpr)
        newList << Instruction.new(node.codeOrigin, andOpcode, [node.operands[0], node.operands[1], tmp])
        newList << Instruction.new(node.codeOrigin, branchOpcode, [tmp, Immediate.new(node.codeOrigin, 0), node.operands[2]])
    end

    newList = []
    list.each {
        | node |
        if node.is_a? Instruction
            case node.opcode
            when "btis"
                emit(newList, "andi", "bilt", node)
            when "btiz"
                emit(newList, "andi", "bieq", node)
            when "btinz"
                emit(newList, "andi", "bineq", node)
            when "btps"
                emit(newList, "andp", "bplt", node)
            when "btpz"
                emit(newList, "andp", "bpeq", node)
            when "btpnz"
                emit(newList, "andp", "bpneq", node)
            when "btqs"
                emit(newList, "andq", "bqlt", node)
            when "btqz"
                emit(newList, "andq", "bqeq", node)
            when "btqnz"
                emit(newList, "andq", "bqneq", node)
            when "btbs"
                emit(newList, "andi", "bblt", node)
            when "btbz"
                emit(newList, "andi", "bbeq", node)
            when "btbnz"
                emit(newList, "andi", "bbneq", node)
            when "tis"
                emit(newList, "andi", "cilt", node)
            when "tiz"
                emit(newList, "andi", "cieq", node)
            when "tinz"
                emit(newList, "andi", "cineq", node)
            when "tps"
                emit(newList, "andp", "cplt", node)
            when "tpz"
                emit(newList, "andp", "cpeq", node)
            when "tpnz"
                emit(newList, "andp", "cpneq", node)
            when "tqs"
                emit(newList, "andq", "cqlt", node)
            when "tqz"
                emit(newList, "andq", "cqeq", node)
            when "tqnz"
                emit(newList, "andq", "cqneq", node)
            when "tbs"
                emit(newList, "andi", "cblt", node)
            when "tbz"
                emit(newList, "andi", "cbeq", node)
            when "tbnz"
                emit(newList, "andi", "cbneq", node)
            else
                newList << node
            end
        else
            newList << node
        end
    }
    return newList
end
Commit	Line	Data
93a37866 A	1	# Copyright (C) 2011, 2012 Apple Inc. All rights reserved.
	2	#
	3	# Redistribution and use in source and binary forms, with or without
	4	# modification, are permitted provided that the following conditions
	5	# are met:
	6	# 1. Redistributions of source code must retain the above copyright
	7	# notice, this list of conditions and the following disclaimer.
	8	# 2. Redistributions in binary form must reproduce the above copyright
	9	# notice, this list of conditions and the following disclaimer in the
	10	# documentation and/or other materials provided with the distribution.
	11	#
	12	# THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
	13	# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
	14	# THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
	15	# PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
	16	# BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
	17	# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
	18	# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
	19	# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
	20	# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
	21	# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
	22	# THE POSSIBILITY OF SUCH DAMAGE.
	23
	24	require 'config'
	25	require 'ast'
	26	require 'opt'
	27
	28	# This file contains utilities that are useful for implementing a backend
	29	# for RISC-like processors (ARM, MIPS, etc).
	30
	31	#
	32	# Lowering of simple branch ops. For example:
	33	#
	34	# baddiz foo, bar, baz
	35	#
	36	# will become:
	37	#
	38	# addi foo, bar
	39	# bz baz
	40	#
	41
	42	def riscLowerSimpleBranchOps(list)
	43	newList = []
	44	list.each {
	45	\| node \|
	46	if node.is_a? Instruction
	47	annotation = node.annotation
	48	case node.opcode
	49	when /^b(addi\|subi\|ori\|addp)/
	50	op = $1
	51	branch = "b" + $~.post_match
	52
	53	case op
	54	when "addi"
	55	op = "addis"
	56	when "addp"
	57	op = "addps"
	58	when "subi"
	59	op = "subis"
	60	when "ori"
	61	op = "oris"
	62	end
	63
	64	newList << Instruction.new(node.codeOrigin, op, node.operands[0..-2], annotation)
65	newList << Instruction.new(node.codeOrigin, branch, [node.operands[-1]])
66	when 'bmulis', 'bmulz', 'bmulnz'
67	condition = $~.post_match
68	newList << Instruction.new(node.codeOrigin, "muli", node.operands[0..-2], annotation)
69	newList << Instruction.new(node.codeOrigin, "bti" + condition, [node.operands[-2], node.operands[-1]])
70	else
71	newList << node
72	end
73	else
74	newList << node
75	end
76	}
77	newList
78	end
79
80	#
81	# Lowing of complex branch ops. For example:
82	#
83	# bmulio foo, bar, baz
84	#
85	# becomes:
86	#
87	# smulli foo, bar, bar, tmp1
88	# rshifti bar, 31, tmp2
89	# bineq tmp1, tmp2, baz
90	#
91
92	def riscLowerHardBranchOps(list)
93	newList = []
94	list.each {
95	\| node \|
96	if node.is_a? Instruction and node.opcode == "bmulio"
97	tmp1 = Tmp.new(node.codeOrigin, :gpr)
98	tmp2 = Tmp.new(node.codeOrigin, :gpr)
99	newList << Instruction.new(node.codeOrigin, "smulli", [node.operands[0], node.operands[1], node.operands[1], tmp1], node.annotation)
100	newList << Instruction.new(node.codeOrigin, "rshifti", [node.operands[-2], Immediate.new(node.codeOrigin, 31), tmp2])
101	newList << Instruction.new(node.codeOrigin, "bineq", [tmp1, tmp2, node.operands[-1]])
102	else
103	newList << node
104	end
105	}
106	newList
107	end
108
109	#
110	# Lowering of shift ops. For example:
111	#
112	# lshifti foo, bar
113	#
114	# will become:
115	#
116	# andi foo, 31, tmp
117	# lshifti tmp, bar
118	#
119
120	def riscSanitizeShift(operand, list)
121	return operand if operand.immediate?
122
123	tmp = Tmp.new(operand.codeOrigin, :gpr)
124	list << Instruction.new(operand.codeOrigin, "andi", [operand, Immediate.new(operand.codeOrigin, 31), tmp])
125	tmp
126	end
127
128	def riscLowerShiftOps(list)
129	newList = []
130	list.each {
131	\| node \|
132	if node.is_a? Instruction
133	case node.opcode
134	when "lshifti", "rshifti", "urshifti", "lshiftp", "rshiftp", "urshiftp"
135	if node.operands.size == 2
136	newList << Instruction.new(node.codeOrigin, node.opcode, [riscSanitizeShift(node.operands[0], newList), node.operands[1]], node.annotation)
137	else
138	newList << Instruction.new(node.codeOrigin, node.opcode, [node.operands[0], riscSanitizeShift(node.operands[1], newList), node.operands[2]], node.annotation)
139	raise "Wrong number of operands for shift at #{node.codeOriginString}" unless node.operands.size == 3
140	end
141	else
142	newList << node
143	end
144	else
145	newList << node
146	end
147	}
148	newList
149	end
150
151	#
152	# Lowering of malformed addresses. For example:
153	#
154	# loadp 10000[foo], bar
155	#
156	# will become:
157	#
158	# move 10000, tmp
159	# addp foo, tmp
160	# loadp 0[tmp], bar
161	#
162	# Note that you use this lowering phase by passing it a block that returns true
163	# if you don't want to lower the address, or false if you do. For example to get
164	# the effect of the example above, the block would have to say something like:
165	#
166	# riscLowerMalformedAddresses(thingy) {
167	# \| node, address \|
168	# if address.is_a? Address
169	# address.offset.value > 1000
170	# else
171	# true # don't lower anything else, in this example
172	# end
173	# }
174	#
175	# See arm.rb for a different example, in which we lower all BaseIndex addresses
176	# that have non-zero offset, all Address addresses that have large offsets, and
177	# all other addresses (like AbsoluteAddress).
178	#
179
180	class Node
181	def riscLowerMalformedAddressesRecurse(list, topLevelNode, &block)
182	mapChildren {
183	\| subNode \|
184	subNode.riscLowerMalformedAddressesRecurse(list, topLevelNode, &block)
185	}
186	end
187	end
188
189	class Address
190	def riscLowerMalformedAddressesRecurse(list, node, &block)
191	return self if yield node, self
192
193	tmp = Tmp.new(codeOrigin, :gpr)
194	list << Instruction.new(codeOrigin, "move", [offset, tmp])
195	list << Instruction.new(codeOrigin, "addp", [base, tmp])
196	Address.new(codeOrigin, tmp, Immediate.new(codeOrigin, 0))
197	end
198	end
199
200	class BaseIndex
201	def riscLowerMalformedAddressesRecurse(list, node, &block)
202	return self if yield node, self
203
204	tmp = Tmp.new(codeOrigin, :gpr)
205	list << Instruction.new(codeOrigin, "leap", [BaseIndex.new(codeOrigin, base, index, scale, Immediate.new(codeOrigin, 0)), tmp])
206	Address.new(codeOrigin, tmp, offset).riscLowerMalformedAddressesRecurse(list, node, &block)
207	end
208	end
209
210	class AbsoluteAddress
211	def riscLowerMalformedAddressesRecurse(list, node, &block)
212	return self if yield node, self
213
214	tmp = Tmp.new(codeOrigin, :gpr)
215	list << Instruction.new(codeOrigin, "move", [address, tmp])
216	Address.new(codeOrigin, tmp, Immediate.new(codeOrigin, 0))
217	end
218	end
219
220	def riscLowerMalformedAddresses(list, &block)
221	newList = []
222	list.each {
223	\| node \|
224	newList << node.riscLowerMalformedAddressesRecurse(newList, node, &block)
225	}
226	newList
227	end
228
229	#
230	# Lowering of malformed addresses in double loads and stores. For example:
231	#
232	# loadd [foo, bar, 8], baz
233	#
234	# becomes:
235	#
236	# leap [foo, bar, 8], tmp
237	# loadd [tmp], baz
238	#
239
240	class Node
241	def riscDoubleAddress(list)
242	self
243	end
244	end
245
246	class BaseIndex
247	def riscDoubleAddress(list)
248	tmp = Tmp.new(codeOrigin, :gpr)
249	list << Instruction.new(codeOrigin, "leap", [self, tmp])
250	Address.new(codeOrigin, tmp, Immediate.new(codeOrigin, 0))
251	end
252	end
253
254	def riscLowerMalformedAddressesDouble(list)
255	newList = []
256	list.each {
257	\| node \|
258	if node.is_a? Instruction
259	case node.opcode
260	when "loadd"
261	newList << Instruction.new(node.codeOrigin, "loadd", [node.operands[0].riscDoubleAddress(newList), node.operands[1]], node.annotation)
262	when "stored"
263	newList << Instruction.new(node.codeOrigin, "stored", [node.operands[0], node.operands[1].riscDoubleAddress(newList)], node.annotation)
264	else
265	newList << node
266	end
267	else
268	newList << node
269	end
270	}
271	newList
272	end
273
274	#
275	# Lowering of misplaced immediates for opcodes in opcodeList. For example, if storei is in opcodeList:
276	#
277	# storei 0, [foo]
278	#
279	# will become:
280	#
281	# move 0, tmp
282	# storei tmp, [foo]
283	#
284
285	def riscLowerMisplacedImmediates(list, opcodeList)
286	newList = []
287	list.each {
288	\| node \|
289	if node.is_a? Instruction
290	if opcodeList.include? node.opcode
291	operands = node.operands
292	newOperands = []
293	operands.each {
294	\| operand \|
295	if operand.is_a? Immediate
296	tmp = Tmp.new(operand.codeOrigin, :gpr)
297	newList << Instruction.new(operand.codeOrigin, "move", [operand, tmp])
298	newOperands << tmp
299	else
300	newOperands << operand
301	end
302	}
303	newList << Instruction.new(node.codeOrigin, node.opcode, newOperands, node.annotation)
304	else
305	newList << node
306	end
307	else
308	newList << node
309	end
310	}
311	newList
312	end
313
314	#
315	# Lowering of malformed immediates except when used in a "move" instruction.
316	# For example:
317	#
318	# addp 642641, foo
319	#
320	# will become:
321	#
322	# move 642641, tmp
323	# addp tmp, foo
324	#
325
326	class Node
327	def riscLowerMalformedImmediatesRecurse(list, validImmediates)
328	mapChildren {
329	\| node \|
330	node.riscLowerMalformedImmediatesRecurse(list, validImmediates)
331	}
332	end
333	end
334
335	class Address
336	def riscLowerMalformedImmediatesRecurse(list, validImmediates)
337	self
338	end
339	end
340
341	class BaseIndex
342	def riscLowerMalformedImmediatesRecurse(list, validImmediates)
343	self
344	end
345	end
346
347	class AbsoluteAddress
348	def riscLowerMalformedImmediatesRecurse(list, validImmediates)
349	self
350	end
351	end
352
353	class Immediate
354	def riscLowerMalformedImmediatesRecurse(list, validImmediates)
355	unless validImmediates.include? value
356	tmp = Tmp.new(codeOrigin, :gpr)
357	list << Instruction.new(codeOrigin, "move", [self, tmp])
358	tmp
359	else
360	self
361	end
362	end
363	end
364
365	def riscLowerMalformedImmediates(list, validImmediates)
366	newList = []
367	list.each {
368	\| node \|
369	if node.is_a? Instruction
370	annotation = node.annotation
371	case node.opcode
372	when "move"
373	newList << node
374	when "addi", "addp", "addq", "addis", "subi", "subp", "subq", "subis"
375	if node.operands[0].is_a? Immediate and
376	(not validImmediates.include? node.operands[0].value) and
377	validImmediates.include? -node.operands[0].value
378	node.operands.size == 2
379	if node.opcode =~ /add/
380	newOpcode = "sub" + $~.post_match
381	else
382	newOpcode = "add" + $~.post_match
383	end
384	newList << Instruction.new(node.codeOrigin, newOpcode,
385	[Immediate.new(node.codeOrigin, -node.operands[0].value)] + node.operands[1..-1],
386	annotation)
387	else
388	newList << node.riscLowerMalformedImmediatesRecurse(newList, validImmediates)
389	end
390	when "muli", "mulp", "mulq"
391	if node.operands[0].is_a? Immediate
392	tmp = Tmp.new(codeOrigin, :gpr)
393	newList << Instruction.new(node.codeOrigin, "move", [node.operands[0], tmp], annotation)
394	newList << Instruction.new(node.codeOrigin, node.opcode, [tmp] + node.operands[1..-1])
395	else
396	newList << node.riscLowerMalformedImmediatesRecurse(newList, validImmediates)
397	end
398	else
399	newList << node.riscLowerMalformedImmediatesRecurse(newList, validImmediates)
400	end
401	else
402	newList << node
403	end
404	}
405	newList
406	end
407
408	#
409	# Lowering of misplaced addresses. For example:
410	#
411	# addi foo, [bar]
412	#
413	# will become:
414	#
415	# loadi [bar], tmp
416	# addi foo, tmp
417	# storei tmp, [bar]
418	#
419	# Another example:
420	#
421	# addi [foo], bar
422	#
423	# will become:
424	#
425	# loadi [foo], tmp
426	# addi tmp, bar
427	#
428
429	def riscAsRegister(preList, postList, operand, suffix, needStore)
430	return operand unless operand.address?
431
432	tmp = Tmp.new(operand.codeOrigin, if suffix == "d" then :fpr else :gpr end)
433	preList << Instruction.new(operand.codeOrigin, "load" + suffix, [operand, tmp])
434	if needStore
435	postList << Instruction.new(operand.codeOrigin, "store" + suffix, [tmp, operand])
436	end
437	tmp
438	end
439
440	def riscAsRegisters(preList, postList, operands, suffix)
441	newOperands = []
442	operands.each_with_index {
443	\| operand, index \|
444	newOperands << riscAsRegister(preList, postList, operand, suffix, index == operands.size - 1)
445	}
446	newOperands
447	end
448
449	def riscLowerMisplacedAddresses(list)
450	newList = []
451	list.each {
452	\| node \|
453	if node.is_a? Instruction
454	postInstructions = []
455	annotation = node.annotation
456	case node.opcode
457	when "addi", "addis", "andi", "lshifti", "muli", "negi", "noti", "ori", "oris",
458	"rshifti", "urshifti", "subi", "subis", "xori", /^bi/, /^bti/, /^ci/, /^ti/
459	newList << Instruction.new(node.codeOrigin,
460	node.opcode,
461	riscAsRegisters(newList, postInstructions, node.operands, "i"),
462	annotation)
463	when "addp", "andp", "lshiftp", "mulp", "negp", "orp", "rshiftp", "urshiftp",
464	"subp", "xorp", /^bp/, /^btp/, /^cp/
465	newList << Instruction.new(node.codeOrigin,
466	node.opcode,
467	riscAsRegisters(newList, postInstructions, node.operands, "p"),
468	annotation)
469	when "addq", "andq", "lshiftq", "mulq", "negq", "orq", "rshiftq", "urshiftq",
470	"subq", "xorq", /^bq/, /^btq/, /^cq/
471	newList << Instruction.new(node.codeOrigin,
472	node.opcode,
473	riscAsRegisters(newList, postInstructions, node.operands, "q"),
474	annotation)
475	when "bbeq", "bbneq", "bba", "bbaeq", "bbb", "bbbeq", "btbz", "btbnz", "tbz", "tbnz",
476	"cbeq", "cbneq", "cba", "cbaeq", "cbb", "cbbeq"
477	newList << Instruction.new(node.codeOrigin,
478	node.opcode,
479	riscAsRegisters(newList, postInstructions, node.operands, "b"),
480	annotation)
481	when "bbgt", "bbgteq", "bblt", "bblteq", "btbs", "tbs", "cbgt", "cbgteq", "cblt", "cblteq"
482	newList << Instruction.new(node.codeOrigin,
483	node.opcode,
484	riscAsRegisters(newList, postInstructions, node.operands, "bs"),
485	annotation)
486	when "addd", "divd", "subd", "muld", "sqrtd", /^bd/
487	newList << Instruction.new(node.codeOrigin,
488	node.opcode,
489	riscAsRegisters(newList, postInstructions, node.operands, "d"),
490	annotation)
491	when "jmp", "call"
492	newList << Instruction.new(node.codeOrigin,
493	node.opcode,
494	[riscAsRegister(newList, postInstructions, node.operands[0], "p", false)],
495	annotation)
496	else
497	newList << node
498	end
499	newList += postInstructions
500	else
501	newList << node
502	end
503	}
504	newList
505	end
506
507	#
508	# Lowering of register reuse in compare instructions. For example:
509	#
510	# cieq t0, t1, t0
511	#
512	# will become:
513	#
514	# mov tmp, t0
515	# cieq tmp, t1, t0
516	#
517
518	def riscLowerRegisterReuse(list)
519	newList = []
520	list.each {
521	\| node \|
522	if node.is_a? Instruction
523	annotation = node.annotation
524	case node.opcode
525	when "cieq", "cineq", "cia", "ciaeq", "cib", "cibeq", "cigt", "cigteq", "cilt", "cilteq",
526	"cpeq", "cpneq", "cpa", "cpaeq", "cpb", "cpbeq", "cpgt", "cpgteq", "cplt", "cplteq",
527	"tis", "tiz", "tinz", "tbs", "tbz", "tbnz", "tps", "tpz", "tpnz", "cbeq", "cbneq",
528	"cba", "cbaeq", "cbb", "cbbeq", "cbgt", "cbgteq", "cblt", "cblteq"
529	if node.operands.size == 2
530	if node.operands[0] == node.operands[1]
531	tmp = Tmp.new(node.codeOrigin, :gpr)
532	newList << Instruction.new(node.codeOrigin, "move", [node.operands[0], tmp], annotation)
533	newList << Instruction.new(node.codeOrigin, node.opcode, [tmp, node.operands[1]])
534	else
535	newList << node
536	end
537	else
538	raise "Wrong number of arguments at #{node.codeOriginString}" unless node.operands.size == 3
539	if node.operands[0] == node.operands[2]
540	tmp = Tmp.new(node.codeOrigin, :gpr)
541	newList << Instruction.new(node.codeOrigin, "move", [node.operands[0], tmp], annotation)
542	newList << Instruction.new(node.codeOrigin, node.opcode, [tmp, node.operands[1], node.operands[2]])
543	elsif node.operands[1] == node.operands[2]
544	tmp = Tmp.new(node.codeOrigin, :gpr)
545	newList << Instruction.new(node.codeOrigin, "move", [node.operands[1], tmp], annotation)
546	newList << Instruction.new(node.codeOrigin, node.opcode, [node.operands[0], tmp, node.operands[2]])
547	else
548	newList << node
549	end
550	end
551	else
552	newList << node
553	end
554	else
555	newList << node
556	end
557	}
558	newList
559	end
560
81345200 A	561	#
	562	# Lowering of the not instruction. The following:
	563	#
	564	# noti t0
	565	#
	566	# becomes:
	567	#
	568	# xori -1, t0
	569	#
	570
	571	def riscLowerNot(list)
	572	newList = []
	573	list.each {
	574	\| node \|
	575	if node.is_a? Instruction
	576	case node.opcode
	577	when "noti", "notp"
	578	raise "Wrong nubmer of operands at #{node.codeOriginString}" unless node.operands.size == 1
	579	suffix = node.opcode[-1..-1]
	580	newList << Instruction.new(node.codeOrigin, "xor" + suffix,
	581	[Immediate.new(node.codeOrigin, -1), node.operands[0]])
	582	else
	583	newList << node
	584	end
	585	else
	586	newList << node
	587	end
	588	}
	589	return newList
	590	end
	591
	592	#
	593	# Lowing of complex branch ops on 64-bit. For example:
	594	#
	595	# bmulio foo, bar, baz
	596	#
	597	# becomes:
	598	#
	599	# smulli foo, bar, bar
	600	# rshiftp bar, 32, tmp1
	601	# rshifti bar, 31, tmp2
	602	# zxi2p bar, bar
	603	# bineq tmp1, tmp2, baz
	604	#
	605
	606	def riscLowerHardBranchOps64(list)
	607	newList = []
	608	list.each {
	609	\| node \|
	610	if node.is_a? Instruction and node.opcode == "bmulio"
	611	tmp1 = Tmp.new(node.codeOrigin, :gpr)
	612	tmp2 = Tmp.new(node.codeOrigin, :gpr)
	613	newList << Instruction.new(node.codeOrigin, "smulli", [node.operands[0], node.operands[1], node.operands[1]])
	614	newList << Instruction.new(node.codeOrigin, "rshiftp", [node.operands[1], Immediate.new(node.codeOrigin, 32), tmp1])
	615	newList << Instruction.new(node.codeOrigin, "rshifti", [node.operands[1], Immediate.new(node.codeOrigin, 31), tmp2])
	616	newList << Instruction.new(node.codeOrigin, "zxi2p", [node.operands[1], node.operands[1]])
	617	newList << Instruction.new(node.codeOrigin, "bineq", [tmp1, tmp2, node.operands[2]])
	618	else
	619	newList << node
	620	end
	621	}
	622	newList
	623	end
	624
625	#
626	# Lowering of test instructions. For example:
627	#
628	# btiz t0, t1, .foo
629	#
630	# becomes:
631	#
632	# andi t0, t1, tmp
633	# bieq tmp, 0, .foo
634	#
635	# and another example:
636	#
637	# tiz t0, t1, t2
638	#
639	# becomes:
640	#
641	# andi t0, t1, tmp
642	# cieq tmp, 0, t2
643	#
644
645	def riscLowerTest(list)
646	def emit(newList, andOpcode, branchOpcode, node)
647	if node.operands.size == 2
648	newList << Instruction.new(node.codeOrigin, branchOpcode, [node.operands[0], Immediate.new(node.codeOrigin, 0), node.operands[1]])
649	return
650	end
651
652	raise "Incorrect number of operands at #{codeOriginString}" unless node.operands.size == 3
653
654	if node.operands[0].immediate? and node.operands[0].value == -1
655	newList << Instruction.new(node.codeOrigin, branchOpcode, [node.operands[1], Immediate.new(node.codeOrigin, 0), node.operands[2]])
656	return
657	end
658
659	if node.operands[1].immediate? and node.operands[1].value == -1
660	newList << Instruction.new(node.codeOrigin, branchOpcode, [node.operands[0], Immediate.new(node.codeOrigin, 0), node.operands[2]])
661	return
662	end
663
664	tmp = Tmp.new(node.codeOrigin, :gpr)
665	newList << Instruction.new(node.codeOrigin, andOpcode, [node.operands[0], node.operands[1], tmp])
666	newList << Instruction.new(node.codeOrigin, branchOpcode, [tmp, Immediate.new(node.codeOrigin, 0), node.operands[2]])
667	end
668
669	newList = []
670	list.each {
671	\| node \|
672	if node.is_a? Instruction
673	case node.opcode
674	when "btis"
675	emit(newList, "andi", "bilt", node)
676	when "btiz"
677	emit(newList, "andi", "bieq", node)
678	when "btinz"
679	emit(newList, "andi", "bineq", node)
680	when "btps"
681	emit(newList, "andp", "bplt", node)
682	when "btpz"
683	emit(newList, "andp", "bpeq", node)
684	when "btpnz"
685	emit(newList, "andp", "bpneq", node)
686	when "btqs"
687	emit(newList, "andq", "bqlt", node)
688	when "btqz"
689	emit(newList, "andq", "bqeq", node)
690	when "btqnz"
691	emit(newList, "andq", "bqneq", node)
692	when "btbs"
693	emit(newList, "andi", "bblt", node)
694	when "btbz"
695	emit(newList, "andi", "bbeq", node)
696	when "btbnz"
697	emit(newList, "andi", "bbneq", node)
698	when "tis"
699	emit(newList, "andi", "cilt", node)
700	when "tiz"
701	emit(newList, "andi", "cieq", node)
702	when "tinz"
703	emit(newList, "andi", "cineq", node)
704	when "tps"
705	emit(newList, "andp", "cplt", node)
706	when "tpz"
707	emit(newList, "andp", "cpeq", node)
708	when "tpnz"
709	emit(newList, "andp", "cpneq", node)
710	when "tqs"
711	emit(newList, "andq", "cqlt", node)
712	when "tqz"
713	emit(newList, "andq", "cqeq", node)
714	when "tqnz"
715	emit(newList, "andq", "cqneq", node)
716	when "tbs"
717	emit(newList, "andi", "cblt", node)
718	when "tbz"
719	emit(newList, "andi", "cbeq", node)
720	when "tbnz"
721	emit(newList, "andi", "cbneq", node)
722	else
723	newList << node
724	end
725	else
726	newList << node
727	end
728	}
729	return newList
730	end