# Copyright (C) 2011 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"

#

# "Optimization" passes. These are used to lower the representation for

# backends that cannot handle some of our higher-level instructions.

#

#

# A temporary - a variable that will be allocated to a register after we're

# done.

#

class Node

def replaceTemporariesWithRegisters(kind)

mapChildren {

| node |

node.replaceTemporariesWithRegisters(kind)

}

end

end

class Tmp < NoChildren

attr_reader :firstMention, :lastMention

attr_reader :kind

attr_accessor :register

def initialize(codeOrigin, kind)

super(codeOrigin)

@kind = kind

end

def dump

"$tmp#{object_id}"

end

def mention!(position)

if not @firstMention or position < @firstMention

@firstMention = position

end

if not @lastMention or position > @lastMention

@lastMention = position

end

end

def replaceTemporariesWithRegisters(kind)

if @kind == kind

raise "Did not allocate register to temporary at #{codeOriginString}" unless @register

@register

else

self

end

end

def address?

false

end

def label?

false

end

def immediate?

false

end

def register?

true

end

end

# Assign registers to temporaries, by finding which temporaries interfere

# with each other. Note that this relies on temporary live ranges not crossing

# basic block boundaries.

def assignRegistersToTemporaries(list, kind, registers)

list.each_with_index {

| node, index |

node.filter(Tmp).uniq.each {

| tmp |

if tmp.kind == kind

tmp.mention! index

end

}

}

freeRegisters = registers.dup

list.each_with_index {

| node, index |

tmpList = node.filter(Tmp).uniq

tmpList.each {

| tmp |

if tmp.kind == kind and tmp.firstMention == index

raise "Could not allocate register to temporary at #{node.codeOriginString}" if freeRegisters.empty?

tmp.register = freeRegisters.pop

end

}

tmpList.each {

| tmp |

if tmp.kind == kind and tmp.lastMention == index

freeRegisters.push tmp.register

raise "Register allocation inconsistency at #{node.codeOriginString}" if freeRegisters.size > registers.size

end

}

}

list.map {

| node |

node.replaceTemporariesWithRegisters(kind)

}

end