offlineasm/opt.rb

   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
  24 require "config"
  25 require "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
  37 class Node
  38     def replaceTemporariesWithRegisters(kind)
  39         mapChildren {
  40             | node |
  41             node.replaceTemporariesWithRegisters(kind)
  42         }
  43     end
  44 end
  45
  46 class 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
  93 end
  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
  99 def 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     }
 134 end
 135