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