1# Copyright (C) 2011 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 24require "config" 25require "ast" 26 27# 28# "Optimization" passes. These are used to lower the representation for 29# backends that cannot handle some of our higher-level instructions. 30# 31 32# 33# A temporary - a variable that will be allocated to a register after we're 34# done. 35# 36 37class Node 38 def replaceTemporariesWithRegisters(kind) 39 mapChildren { 40 | node | 41 node.replaceTemporariesWithRegisters(kind) 42 } 43 end 44end 45 46class Tmp < NoChildren 47 attr_reader :firstMention, :lastMention 48 attr_reader :kind 49 attr_accessor :register 50 51 def initialize(codeOrigin, kind) 52 super(codeOrigin) 53 @kind = kind 54 end 55 56 def dump 57 "$tmp#{object_id}" 58 end 59 60 def mention!(position) 61 if not @firstMention or position < @firstMention 62 @firstMention = position 63 end 64 if not @lastMention or position > @lastMention 65 @lastMention = position 66 end 67 end 68 69 def replaceTemporariesWithRegisters(kind) 70 if @kind == kind 71 raise "Did not allocate register to temporary at #{codeOriginString}" unless @register 72 @register 73 else 74 self 75 end 76 end 77 78 def address? 79 false 80 end 81 82 def label? 83 false 84 end 85 86 def immediate? 87 false 88 end 89 90 def register? 91 true 92 end 93end 94 95# Assign registers to temporaries, by finding which temporaries interfere 96# with each other. Note that this relies on temporary live ranges not crossing 97# basic block boundaries. 98 99def assignRegistersToTemporaries(list, kind, registers) 100 list.each_with_index { 101 | node, index | 102 node.filter(Tmp).uniq.each { 103 | tmp | 104 if tmp.kind == kind 105 tmp.mention! index 106 end 107 } 108 } 109 110 freeRegisters = registers.dup 111 list.each_with_index { 112 | node, index | 113 tmpList = node.filter(Tmp).uniq 114 tmpList.each { 115 | tmp | 116 if tmp.kind == kind and tmp.firstMention == index 117 raise "Could not allocate register to temporary at #{node.codeOriginString}" if freeRegisters.empty? 118 tmp.register = freeRegisters.pop 119 end 120 } 121 tmpList.each { 122 | tmp | 123 if tmp.kind == kind and tmp.lastMention == index 124 freeRegisters.push tmp.register 125 raise "Register allocation inconsistency at #{node.codeOriginString}" if freeRegisters.size > registers.size 126 end 127 } 128 } 129 130 list.map { 131 | node | 132 node.replaceTemporariesWithRegisters(kind) 133 } 134end 135 136