Create a super rough prototype of B3
[WebKit-https.git] / Source / JavaScriptCore / b3 / generate_pattern_matcher.rb
1 #!/usr/bin/env ruby
2
3 # Copyright (C) 2015 Apple Inc. All rights reserved.
4 #
5 # Redistribution and use in source and binary forms, with or without
6 # modification, are permitted provided that the following conditions
7 # are met:
8 # 1. Redistributions of source code must retain the above copyright
9 #    notice, this list of conditions and the following disclaimer.
10 # 2. Redistributions in binary form must reproduce the above copyright
11 #    notice, this list of conditions and the following disclaimer in the
12 #    documentation and/or other materials provided with the distribution.
13 #
14 # THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
15 # AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
16 # THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17 # PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
18 # BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
19 # CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
20 # SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
21 # INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
22 # CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
23 # ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
24 # THE POSSIBILITY OF SUCH DAMAGE.
25
26 require "pathname"
27
28 $varIndex = 0
29 def newVar
30     $varIndex += 1
31     "_tmp#{$varIndex}"
32 end
33
34 class Production
35     attr_reader :origin, :name, :varName, :anonymous, :opcode, :children
36
37     def initialize(origin, name, opcode, children)
38         @origin = origin
39         @name = name
40         @anonymous = (name == nil or name =~ /\A\$([0-9]+)\Z/)
41         @varName = @anonymous ? newVar : name =~ /\A\$/ ? $' : name
42         @opcode = opcode
43         @children = children ? children : []
44     end
45
46     def hasOpcode
47         opcode != nil
48     end
49
50     def eachVariable(&proc)
51         children.each_with_index {
52             | child, index |
53             yield varName,
54                   child.name,
55                   child.varName,
56                   child.anonymous ? (child.opcode ? :anonInternal : :anonOperand) : (child.opcode ? :internal : :operand),
57                   index
58             child.eachVariable(&proc)
59         }
60     end
61 end
62
63 class Matcher
64     attr_reader :name, :productions
65
66     def initialize(name, productions)
67         @name = name
68         @productions = productions
69     end
70 end
71
72 class Origin
73     attr_reader :fileName, :lineNumber
74     
75     def initialize(fileName, lineNumber)
76         @fileName = fileName
77         @lineNumber = lineNumber
78     end
79     
80     def to_s
81         "#{fileName}:#{lineNumber}"
82     end
83 end
84
85 class Token
86     attr_reader :origin, :string
87     
88     def initialize(origin, string)
89         @origin = origin
90         @string = string
91     end
92     
93     def ==(other)
94         if other.is_a? Token
95             @string == other.string
96         else
97             @string == other
98         end
99     end
100     
101     def =~(other)
102         @string =~ other
103     end
104     
105     def to_s
106         "#{@string.inspect} at #{origin}"
107     end
108     
109     def parseError(*comment)
110         if comment.empty?
111             raise "Parse error: #{to_s}"
112         else
113             raise "Parse error: #{to_s}: #{comment[0]}"
114         end
115     end
116 end
117
118 def lex(str, fileName)
119     fileName = Pathname.new(fileName)
120     result = []
121     lineNumber = 1
122     while not str.empty?
123         case str
124         when /\A\#([^\n]*)/
125             # comment, ignore
126         when /\A\n/
127             # newline, ignore
128             lineNumber += 1
129         when /\A[a-zA-Z0-9$]([a-zA-Z0-9_]*)/
130             result << Token.new(Origin.new(fileName, lineNumber), $&)
131         when /\A([ \t\r]+)/
132             # whitespace, ignore
133         when /\A[=(),]/
134             result << Token.new(Origin.new(fileName, lineNumber), $&)
135         else
136             raise "Lexer error at #{Origin.new(fileName, lineNumber).to_s}, unexpected sequence #{str[0..20].inspect}"
137         end
138         str = $~.post_match
139     end
140     result
141 end
142
143 def isKeyword(token)
144     # We can extend this as we add more keywords. Like, we might want "include" eventually.
145     token =~ /\A((matcher)|(include))\Z/
146 end
147
148 def isIdentifier(token)
149     token =~ /\A[a-zA-Z0-9$]([a-zA-Z0-9_]*)\Z/ and not isKeyword(token)
150 end
151
152 class Parser
153     def initialize(data, fileName)
154         @tokens = lex(data, fileName)
155         @idx = 0
156     end
157
158     def token
159         @tokens[@idx]
160     end
161
162     def advance
163         @idx += 1
164     end
165
166     def parseError(*comment)
167         if token
168             token.parseError(*comment)
169         else
170             if comment.empty?
171                 raise "Parse error at end of file"
172             else
173                 raise "Parse error at end of file: #{comment[0]}"
174             end
175         end
176     end
177
178     def consume(string)
179         parseError("Expected #{string}") unless token == string
180         advance
181     end
182
183     def consumeIdentifier
184         result = token.string
185         parseError("Expected identifier") unless isIdentifier(result)
186         advance
187         result
188     end
189
190     def addUnique(name, productions, production)
191         if name == production.varName
192             parseError("Child production has same name as parent production")
193         end
194         if productions.detect { | entry | entry.name == production.name }
195             parseError("Duplicate production")
196         end
197         productions << production
198     end
199
200     def parse
201         consume("matcher")
202
203         matcherName = consumeIdentifier
204
205         productions = []
206
207         loop {
208             break if @idx >= @tokens.length
209
210             # We might want to support "include". If we did that, it would go here.
211             production = parseProduction
212             
213             if productions.detect { | entry | entry.name == production.name }
214                 parseError("Duplicate production")
215             end
216
217             productions << production
218         }
219
220         Matcher.new(matcherName, productions)
221     end
222
223     def parseProduction
224         origin = token.origin
225         name = consumeIdentifier
226
227         if token == "="
228             consume("=")
229             opcode = consumeIdentifier
230             consume("(")
231         elsif token == "("
232             consume("(")
233             opcode = name
234             name = nil
235         else
236             return Production.new(origin, name, nil, nil)
237         end
238         
239         productions = []
240         loop {
241             break if token == ")"
242
243             addUnique(name, productions, parseProduction)
244
245             break if token == ")"
246             consume(",")
247         }
248
249         # Advance after the ")"
250         advance
251
252         Production.new(origin, name, opcode, productions)
253     end
254 end
255
256 fileName = ARGV[0]
257
258 parser = Parser.new(IO::read(fileName), fileName)
259 matcher = parser.parse
260
261 class SubMatch
262     attr_reader :indexMap, :productions
263     
264     def initialize(indexList, productions)
265         @indexMap = []
266         @productions = []
267         indexList.each {
268             | index |
269             @indexMap << index
270             @productions << productions[index]
271         }
272     end
273
274     def mapIndexList(indexList)
275         indexList.map {
276             | index |
277             @indexMap[index]
278         }
279     end
280 end
281
282 $stderr.puts "Generating code for #{fileName}."
283
284 File.open("B3" + matcher.name + ".h", "w") {
285     | outp |
286
287     outp.puts "// Generated by generate_pattern_matcher.rb from #{fileName} -- do not edit!"
288
289     outp.puts "#ifndef B3#{matcher.name}_h"
290     outp.puts "#define B3#{matcher.name}_h"
291     
292     outp.puts "#include \"B3Value.h\""
293     
294     outp.puts "namespace JSC { namespace B3 {"
295
296     outp.puts "template<typename Adaptor>"
297     outp.puts "bool run#{matcher.name}(Value* _value, Adaptor& adaptor)"
298     outp.puts "{"
299
300     # Note that this does not emit properly indented code, because it's a recursive emitter. If you
301     # want to see the code nicely formatted, open it in a good text editor and ask it to format it
302     # for you.
303
304     # In odd situations, we may not use the input value. Tell the compiler to chill out about it.
305     outp.puts "UNUSED_PARAM(_value);"
306         
307     # This just protects the caller from having to worry about productions having different lengths.
308     def matchLength(outp, valueName, productions)
309         indexLists = []
310         productions.each_with_index {
311             | production, index |
312             if indexLists[-1] and productions[indexLists[-1][0]].children.length == production.children.length
313                 indexLists[-1] << index
314             else
315                 indexLists << [index]
316             end
317         }
318
319         indexLists.each {
320             | indexList |
321             length = productions[indexList[0]].children.length
322             if length > 0
323                 outp.puts "if (#{valueName}->children().size() >= #{length}) {"
324                 yield indexList
325                 outp.puts "}"
326             else
327                 yield indexList
328             end
329         }
330     end
331
332     # This efficiently selects from the given set of productions. It assumes that productions
333     # are not duplicated. It yields the index of the found production, and the coroutine is
334     # responsible for emitting specific code for that production. The coroutine is given lists of
335     # indices of possibly-matching productions.
336     def matchProductions(outp, valueName, productions)
337         # First, split the productions list into runs of productions with an opcode and productions
338         # without one.
339         indexLists = []
340         productions.each_with_index {
341             | production, index |
342             if indexLists[-1] and productions[indexLists[-1][0]].hasOpcode == production.hasOpcode
343                 indexLists[-1] << index
344             else
345                 indexLists << [index]
346             end
347         }
348         
349         # Now, emit pattern matching code. We do it differently for lists with an opcode than for
350         # lists without one.
351         indexLists.each {
352             | indexList |
353             if productions[indexList[0]].hasOpcode
354                 # Now, we split this index list into groups for each opcode.
355                 groups = {}
356                 indexList.each {
357                     | index |
358                     production = productions[index]
359                     if groups[production.opcode]
360                         groups[production.opcode] << index
361                     else
362                         groups[production.opcode] = [index]
363                     end
364                 }
365
366                 # Emit a switch statement.
367                 outp.puts "switch (#{valueName}->opcode()) {"
368                 groups.each_pair {
369                     | opcode, subIndexList |
370                     outp.puts "case #{opcode}:"
371                     subMatch = SubMatch.new(subIndexList, productions)
372                     matchLength(outp, valueName, subMatch.productions) {
373                         | indexList |
374                         yield subMatch.mapIndexList(indexList)
375                     }
376                     outp.puts "break;"
377                 }
378                 outp.puts "default:"
379                 outp.puts "break;"
380                 outp.puts "}"
381             else
382                 subMatch = SubMatch.new(indexList, productions)
383                 matchLength(outp, valueName, subMatch.productions) {
384                     | indexList |
385                     yield subMatch.mapIndexList(indexList)
386                 }
387             end
388         }
389     end
390
391     # Takes productions that have the same opcode and the same length and selects from them based on
392     # the productions at the given column.
393     def matchColumn(outp, valueName, productions, columnIndex)
394         if columnIndex >= productions[0].children.length
395             yield (0...(productions.size)).to_a
396             return
397         end
398
399         subValue = newVar
400         
401         outp.puts "{"
402         outp.puts "Value* #{subValue} = #{valueName}->child(#{columnIndex});"
403
404         # We may not use this value. Tell the compiler to chill out about it.
405         outp.puts "UNUSED_PARAM(#{subValue});"
406         
407         subProductions = productions.map {
408             | production |
409             production.children[columnIndex]
410         }
411
412         matchRecursively(outp, subValue, subProductions) {
413             | indexList |
414             subMatch = SubMatch.new(indexList, productions)
415             matchColumn(outp, valueName, subMatch.productions, columnIndex + 1) {
416                 | indexList |
417                 yield subMatch.mapIndexList(indexList)
418             }
419         }
420
421         outp.puts "}"
422     end
423
424     def matchRecursively(outp, valueName, productions)
425         matchProductions(outp, valueName, productions) {
426             | indexList |
427             # We are guaranteed that this index list contains productions with the same opcode and
428             # the same length.
429             subMatch = SubMatch.new(indexList, productions)
430             matchColumn(outp, valueName, subMatch.productions, 0) {
431                 | indexList |
432                 yield subMatch.mapIndexList(indexList)
433             }
434         }
435     end
436
437     matchRecursively(outp, "_value", matcher.productions) {
438         | indexList |
439         indexList.each {
440             | index |
441             production = matcher.productions[index]
442             outp.puts "{"
443             outp.puts "Value* #{production.varName} = _value;"
444             outp.puts "UNUSED_PARAM(#{production.varName});"
445             internalArguments = []
446             operandArguments = []
447             tryArguments = []
448             numScopes = 0
449             seen = {}
450
451             # FIXME: We want to be able to combine pattern matchers, like have the pattern match rule
452             # for Branch in the lowering patcher delegate to a matcher that can deduce the kind of
453             # comparison that we're doing. We could then reuse that latter matcher for Check and
454             # unfused compare. The key to making such a delegation work is to have the inner matcher
455             # (the comparison matcher in this case) keep cascading if it encounters a rule that
456             # produces something that the outer matcher cannot handle. It's not obvious that the
457             # comparison matcher would need this, but the address matcher probably will. For example,
458             # we may have a StoreAddLoad rule that delegates to the address matcher, and the address
459             # matcher may produce an address that the lowering matcher cannot use because while the
460             # Add form does accept addresses it may not accept the particular address that the
461             # address matcher produced. In that case, instead of giving up on the StoreAddLoad rule,
462             # we want the address matcher to just try a different address. The comparison matcher
463             # might want this just for better controlling when to pin variables. Currently, if it
464             # constructed some code, it would also pin the variables that it used. If the lowering
465             # matcher then decided to reject the code created by the comparison matcher, it would
466             # have a hard time "unpinning" those variables. But if we had some kind of delegation, we
467             # could have the pinning of the comparison matcher happen only if the lowering matcher
468             # accepted.
469             #
470             # This could all be accomplished by having tryBlah() return something, and have the
471             # matcher also take a functor argument that accepts what tryBlah() returns. So instead of
472             #
473             # if (tryBlah()) ok;
474             #
475             # We would have:
476             #
477             # if (functor(tryBlah()) ok;
478             #
479             # When lowering decided to delegate to the address or comparison matcher, it could supply
480             # a functor that decides whether the thing that the sub-matcher selected is indeed
481             # useful.
482             #
483             # In the near term, we probably won't need this. But we will definitely need it as we
484             # expand to efficiently support more platforms. On X86_64, any branching instruction is
485             # usable in any context, and any address should be usable in any context (and the only
486             # cases where it wouldn't be is if we have holes in the MacroAssembler).
487             #
488             # https://bugs.webkit.org/show_bug.cgi?id=150559
489             
490             production.eachVariable {
491                 | parentVarName, childName, childVarName, kind, index |
492                 loadExpr = "#{parentVarName}->child(#{index})"
493                 
494                 if seen[childVarName]
495                     tmp = newVar
496                     outp.puts "Value* #{tmp} = #{loadExpr};"
497                     outp.puts "if (#{tmp} == #{childVarName}) {"
498                     numScopes += 1
499                 else
500                     seen[childVarName] = true
501                     
502                     outp.puts "Value* #{childVarName} = #{loadExpr};"
503
504                     # FIXME: Consider getting rid of the $ prefix.
505                     # https://bugs.webkit.org/show_bug.cgi?id=150527
506                     if childName =~ /\A\$/
507                         if childName =~ /\A\$([0-9]+)\Z/
508                             outp.puts "if (#{childVarName}->isInt(#{$1})) {"
509                         else
510                             outp.puts "if (#{childVarName}->hasInt()) {"
511                         end
512                         numScopes += 1
513                     end
514                     
515                     internalArguments << childVarName if kind == :internal or kind == :anonInternal
516                     operandArguments << childVarName if kind == :operand or kind == :anonOperand
517                     tryArguments << childVarName if kind == :internal or kind == :operand
518                 end
519             }
520             outp.puts "if (adaptor.acceptRoot(_value)"
521             unless internalArguments.empty?
522                 outp.puts("&& adaptor.acceptInternals(" + internalArguments.join(", ") + ")")
523             end
524             unless operandArguments.empty?
525                 outp.puts("&& adaptor.acceptOperands(" + operandArguments.join(", ") + ")")
526             end
527             outp.puts("&& adaptor.try#{production.name}(" + tryArguments.join(", ") + ")) {")
528             outp.puts "adaptor.acceptRootLate(_value);"
529             unless internalArguments.empty?
530                 outp.puts "adaptor.acceptInternalsLate(" + internalArguments.join(", ") + ");"
531             end
532             unless operandArguments.empty?
533                 outp.puts "adaptor.acceptOperandsLate(" + operandArguments.join(", ") + ");"
534             end
535             outp.puts "return true;"
536             outp.puts "}"
537             numScopes.times {
538                 outp.puts "}"
539             }
540             outp.puts "}"
541         }
542     }
543     
544     outp.puts "    return false;"
545     outp.puts "}"
546     
547     outp.puts "} } // namespace JSC::B3"
548
549     outp.puts "#endif // B3#{matcher.name}_h"
550 }