]> gitweb.factorcode.org Git - factor.git/blob - basis/compiler/cfg/value-numbering/rewrite/rewrite.factor
Factor source files should not be executable
[factor.git] / basis / compiler / cfg / value-numbering / rewrite / rewrite.factor
1 ! Copyright (C) 2008, 2009 Slava Pestov, Doug Coleman, Daniel Ehrenberg.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: accessors combinators combinators.short-circuit arrays
4 fry kernel layouts math namespaces sequences cpu.architecture
5 math.bitwise math.order math.vectors.simd.intrinsics classes
6 vectors locals make alien.c-types io.binary grouping
7 compiler.cfg
8 compiler.cfg.registers
9 compiler.cfg.comparisons
10 compiler.cfg.instructions
11 compiler.cfg.value-numbering.expressions
12 compiler.cfg.value-numbering.graph
13 compiler.cfg.value-numbering.simplify ;
14 IN: compiler.cfg.value-numbering.rewrite
15
16 : vreg-immediate-arithmetic? ( vreg -- ? )
17     vreg>expr {
18         [ constant-expr? ]
19         [ value>> fixnum? ]
20         [ value>> immediate-arithmetic? ]
21     } 1&& ;
22
23 : vreg-immediate-bitwise? ( vreg -- ? )
24     vreg>expr {
25         [ constant-expr? ]
26         [ value>> fixnum? ]
27         [ value>> immediate-bitwise? ]
28     } 1&& ;
29
30 ! Outputs f to mean no change
31
32 GENERIC: rewrite ( insn -- insn/f )
33
34 M: insn rewrite drop f ;
35
36 : ##branch-t? ( insn -- ? )
37     dup ##compare-imm-branch? [
38         {
39             [ cc>> cc/= eq? ]
40             [ src2>> \ f type-number eq? ]
41         } 1&&
42     ] [ drop f ] if ; inline
43
44 : general-compare-expr? ( insn -- ? )
45     {
46         [ compare-expr? ]
47         [ compare-imm-expr? ]
48         [ compare-float-unordered-expr? ]
49         [ compare-float-ordered-expr? ]
50         [ test-vector-expr? ]
51     } 1|| ;
52
53 : rewrite-boolean-comparison? ( insn -- ? )
54     dup ##branch-t? [
55         src1>> vreg>expr general-compare-expr?
56     ] [ drop f ] if ; inline
57  
58 : >compare-expr< ( expr -- in1 in2 cc )
59     [ src1>> vn>vreg ] [ src2>> vn>vreg ] [ cc>> ] tri ; inline
60
61 : >compare-imm-expr< ( expr -- in1 in2 cc )
62     [ src1>> vn>vreg ] [ src2>> vn>constant ] [ cc>> ] tri ; inline
63
64 : >test-vector-expr< ( expr -- src1 temp rep vcc )
65     {
66         [ src1>> vn>vreg ]
67         [ drop next-vreg ]
68         [ rep>> ]
69         [ vcc>> ]
70     } cleave ; inline
71
72 : rewrite-boolean-comparison ( expr -- insn )
73     src1>> vreg>expr {
74         { [ dup compare-expr? ] [ >compare-expr< \ ##compare-branch new-insn ] }
75         { [ dup compare-imm-expr? ] [ >compare-imm-expr< \ ##compare-imm-branch new-insn ] }
76         { [ dup compare-float-unordered-expr? ] [ >compare-expr< \ ##compare-float-unordered-branch new-insn ] }
77         { [ dup compare-float-ordered-expr? ] [ >compare-expr< \ ##compare-float-ordered-branch new-insn ] }
78         { [ dup test-vector-expr? ] [ >test-vector-expr< \ ##test-vector-branch new-insn ] }
79     } cond ;
80
81 : tag-fixnum-expr? ( expr -- ? )
82     dup shl-imm-expr?
83     [ src2>> vn>constant tag-bits get = ] [ drop f ] if ;
84
85 : rewrite-tagged-comparison? ( insn -- ? )
86     #! Are we comparing two tagged fixnums? Then untag them.
87     {
88         [ src1>> vreg>expr tag-fixnum-expr? ]
89         [ src2>> tag-mask get bitand 0 = ]
90     } 1&& ; inline
91
92 : tagged>constant ( n -- n' )
93     tag-bits get neg shift ; inline
94
95 : (rewrite-tagged-comparison) ( insn -- src1 src2 cc )
96     [ src1>> vreg>expr src1>> vn>vreg ]
97     [ src2>> tagged>constant ]
98     [ cc>> ]
99     tri ; inline
100
101 GENERIC: rewrite-tagged-comparison ( insn -- insn/f )
102
103 M: ##compare-imm-branch rewrite-tagged-comparison
104     (rewrite-tagged-comparison) \ ##compare-imm-branch new-insn ;
105
106 M: ##compare-imm rewrite-tagged-comparison
107     [ dst>> ] [ (rewrite-tagged-comparison) ] bi
108     next-vreg \ ##compare-imm new-insn ;
109
110 : rewrite-redundant-comparison? ( insn -- ? )
111     {
112         [ src1>> vreg>expr general-compare-expr? ]
113         [ src2>> \ f type-number = ]
114         [ cc>> { cc= cc/= } member-eq? ]
115     } 1&& ; inline
116
117 : rewrite-redundant-comparison ( insn -- insn' )
118     [ cc>> ] [ dst>> ] [ src1>> vreg>expr ] tri {
119         { [ dup compare-expr? ] [ >compare-expr< next-vreg \ ##compare new-insn ] }
120         { [ dup compare-imm-expr? ] [ >compare-imm-expr< next-vreg \ ##compare-imm new-insn ] }
121         { [ dup compare-float-unordered-expr? ] [ >compare-expr< next-vreg \ ##compare-float-unordered new-insn ] }
122         { [ dup compare-float-ordered-expr? ] [ >compare-expr< next-vreg \ ##compare-float-ordered new-insn ] }
123     } cond
124     swap cc= eq? [ [ negate-cc ] change-cc ] when ;
125
126 ERROR: bad-comparison ;
127
128 : (fold-compare-imm) ( insn -- ? )
129     [ [ src1>> vreg>constant ] [ src2>> ] bi ] [ cc>> ] bi
130     pick integer?
131     [ [ <=> ] dip evaluate-cc ]
132     [
133         2nip {
134             { cc= [ f ] }
135             { cc/= [ t ] }
136             [ bad-comparison ]
137         } case
138     ] if ;
139
140 : fold-compare-imm? ( insn -- ? )
141     src1>> vreg>expr [ constant-expr? ] [ reference-expr? ] bi or ;
142
143 : fold-branch ( ? -- insn )
144     0 1 ?
145     basic-block get [ nth 1vector ] change-successors drop
146     \ ##branch new-insn ;
147
148 : fold-compare-imm-branch ( insn -- insn/f )
149     (fold-compare-imm) fold-branch ;
150
151 M: ##compare-imm-branch rewrite
152     {
153         { [ dup rewrite-boolean-comparison? ] [ rewrite-boolean-comparison ] }
154         { [ dup rewrite-tagged-comparison? ] [ rewrite-tagged-comparison ] }
155         { [ dup fold-compare-imm? ] [ fold-compare-imm-branch ] }
156         [ drop f ]
157     } cond ;
158
159 : swap-compare ( src1 src2 cc swap? -- src1 src2 cc )
160     [ [ swap ] dip swap-cc ] when ; inline
161
162 : >compare-imm-branch ( insn swap? -- insn' )
163     [
164         [ src1>> ]
165         [ src2>> ]
166         [ cc>> ]
167         tri
168     ] dip
169     swap-compare
170     [ vreg>constant ] dip
171     \ ##compare-imm-branch new-insn ; inline
172
173 : self-compare? ( insn -- ? )
174     [ src1>> ] [ src2>> ] bi [ vreg>vn ] bi@ = ; inline
175
176 : (rewrite-self-compare) ( insn -- ? )
177     cc>> { cc= cc<= cc>= } member-eq? ;
178
179 : rewrite-self-compare-branch ( insn -- insn' )
180     (rewrite-self-compare) fold-branch ;
181
182 M: ##compare-branch rewrite
183     {
184         { [ dup src1>> vreg-immediate-arithmetic? ] [ t >compare-imm-branch ] }
185         { [ dup src2>> vreg-immediate-arithmetic? ] [ f >compare-imm-branch ] }
186         { [ dup self-compare? ] [ rewrite-self-compare-branch ] }
187         [ drop f ]
188     } cond ;
189
190 : >compare-imm ( insn swap? -- insn' )
191     [
192         {
193             [ dst>> ]
194             [ src1>> ]
195             [ src2>> ]
196             [ cc>> ]
197         } cleave
198     ] dip
199     swap-compare
200     [ vreg>constant ] dip
201     next-vreg \ ##compare-imm new-insn ; inline
202
203 : >boolean-insn ( insn ? -- insn' )
204     [ dst>> ] dip
205     {
206         { t [ t \ ##load-constant new-insn ] }
207         { f [ \ f type-number \ ##load-immediate new-insn ] }
208     } case ;
209
210 : rewrite-self-compare ( insn -- insn' )
211     dup (rewrite-self-compare) >boolean-insn ;
212
213 M: ##compare rewrite
214     {
215         { [ dup src1>> vreg-immediate-arithmetic? ] [ t >compare-imm ] }
216         { [ dup src2>> vreg-immediate-arithmetic? ] [ f >compare-imm ] }
217         { [ dup self-compare? ] [ rewrite-self-compare ] }
218         [ drop f ]
219     } cond ;
220
221 : fold-compare-imm ( insn -- insn' )
222     dup (fold-compare-imm) >boolean-insn ;
223
224 M: ##compare-imm rewrite
225     {
226         { [ dup rewrite-redundant-comparison? ] [ rewrite-redundant-comparison ] }
227         { [ dup rewrite-tagged-comparison? ] [ rewrite-tagged-comparison ] }
228         { [ dup fold-compare-imm? ] [ fold-compare-imm ] }
229         [ drop f ]
230     } cond ;
231
232 : constant-fold? ( insn -- ? )
233     src1>> vreg>expr constant-expr? ; inline
234
235 GENERIC: constant-fold* ( x y insn -- z )
236
237 M: ##add-imm constant-fold* drop + ;
238 M: ##sub-imm constant-fold* drop - ;
239 M: ##mul-imm constant-fold* drop * ;
240 M: ##and-imm constant-fold* drop bitand ;
241 M: ##or-imm constant-fold* drop bitor ;
242 M: ##xor-imm constant-fold* drop bitxor ;
243 M: ##shr-imm constant-fold* drop [ cell-bits 2^ wrap ] dip neg shift ;
244 M: ##sar-imm constant-fold* drop neg shift ;
245 M: ##shl-imm constant-fold* drop shift ;
246
247 : constant-fold ( insn -- insn' )
248     [ dst>> ]
249     [ [ src1>> vreg>constant ] [ src2>> ] [ ] tri constant-fold* ] bi
250     \ ##load-immediate new-insn ; inline
251
252 : unary-constant-fold? ( insn -- ? )
253     src>> vreg>expr constant-expr? ; inline
254
255 GENERIC: unary-constant-fold* ( x insn -- y )
256
257 M: ##not unary-constant-fold* drop bitnot ;
258 M: ##neg unary-constant-fold* drop neg ;
259
260 : unary-constant-fold ( insn -- insn' )
261     [ dst>> ]
262     [ [ src>> vreg>constant ] [ ] bi unary-constant-fold* ] bi
263     \ ##load-immediate new-insn ; inline
264
265 : maybe-unary-constant-fold ( insn -- insn' )
266     dup unary-constant-fold? [ unary-constant-fold ] [ drop f ] if ;
267
268 M: ##neg rewrite
269     maybe-unary-constant-fold ;
270
271 M: ##not rewrite
272     maybe-unary-constant-fold ;
273
274 : arithmetic-op? ( op -- ? )
275     {
276         ##add
277         ##add-imm
278         ##sub
279         ##sub-imm
280         ##mul
281         ##mul-imm
282     } member-eq? ;
283
284 : immediate? ( value op -- ? )
285     arithmetic-op? [ immediate-arithmetic? ] [ immediate-bitwise? ] if ;
286
287 : reassociate ( insn op -- insn )
288     [
289         {
290             [ dst>> ]
291             [ src1>> vreg>expr [ src1>> vn>vreg ] [ src2>> vn>constant ] bi ]
292             [ src2>> ]
293             [ ]
294         } cleave constant-fold*
295     ] dip
296     2dup immediate? [ new-insn ] [ 2drop 2drop f ] if ; inline
297
298 M: ##add-imm rewrite
299     {
300         { [ dup constant-fold? ] [ constant-fold ] }
301         { [ dup src1>> vreg>expr add-imm-expr? ] [ \ ##add-imm reassociate ] }
302         [ drop f ]
303     } cond ;
304
305 : sub-imm>add-imm ( insn -- insn' )
306     [ dst>> ] [ src1>> ] [ src2>> neg ] tri dup immediate-arithmetic?
307     [ \ ##add-imm new-insn ] [ 3drop f ] if ;
308
309 M: ##sub-imm rewrite
310     {
311         { [ dup constant-fold? ] [ constant-fold ] }
312         [ sub-imm>add-imm ]
313     } cond ;
314
315 : mul-to-neg? ( insn -- ? )
316     src2>> -1 = ;
317
318 : mul-to-neg ( insn -- insn' )
319     [ dst>> ] [ src1>> ] bi \ ##neg new-insn ;
320
321 : mul-to-shl? ( insn -- ? )
322     src2>> power-of-2? ;
323
324 : mul-to-shl ( insn -- insn' )
325     [ [ dst>> ] [ src1>> ] bi ] [ src2>> log2 ] bi \ ##shl-imm new-insn ;
326
327 M: ##mul-imm rewrite
328     {
329         { [ dup constant-fold? ] [ constant-fold ] }
330         { [ dup mul-to-neg? ] [ mul-to-neg ] }
331         { [ dup mul-to-shl? ] [ mul-to-shl ] }
332         { [ dup src1>> vreg>expr mul-imm-expr? ] [ \ ##mul-imm reassociate ] }
333         [ drop f ]
334     } cond ;
335
336 M: ##and-imm rewrite
337     {
338         { [ dup constant-fold? ] [ constant-fold ] }
339         { [ dup src1>> vreg>expr and-imm-expr? ] [ \ ##and-imm reassociate ] }
340         [ drop f ]
341     } cond ;
342
343 M: ##or-imm rewrite
344     {
345         { [ dup constant-fold? ] [ constant-fold ] }
346         { [ dup src1>> vreg>expr or-imm-expr? ] [ \ ##or-imm reassociate ] }
347         [ drop f ]
348     } cond ;
349
350 M: ##xor-imm rewrite
351     {
352         { [ dup constant-fold? ] [ constant-fold ] }
353         { [ dup src1>> vreg>expr xor-imm-expr? ] [ \ ##xor-imm reassociate ] }
354         [ drop f ]
355     } cond ;
356
357 M: ##shl-imm rewrite
358     {
359         { [ dup constant-fold? ] [ constant-fold ] }
360         [ drop f ]
361     } cond ;
362
363 M: ##shr-imm rewrite
364     {
365         { [ dup constant-fold? ] [ constant-fold ] }
366         [ drop f ]
367     } cond ;
368
369 M: ##sar-imm rewrite
370     {
371         { [ dup constant-fold? ] [ constant-fold ] }
372         [ drop f ]
373     } cond ;
374
375 : insn>imm-insn ( insn op swap? -- )
376     swap [
377         [ [ dst>> ] [ src1>> ] [ src2>> ] tri ] dip
378         [ swap ] when vreg>constant
379     ] dip new-insn ; inline
380
381 : vreg-immediate? ( vreg op -- ? )
382     arithmetic-op?
383     [ vreg-immediate-arithmetic? ] [ vreg-immediate-bitwise? ] if ;
384
385 : rewrite-arithmetic ( insn op -- ? )
386     {
387         { [ over src2>> over vreg-immediate? ] [ f insn>imm-insn ] }
388         [ 2drop f ]
389     } cond ; inline
390
391 : rewrite-arithmetic-commutative ( insn op -- ? )
392     {
393         { [ over src2>> over vreg-immediate? ] [ f insn>imm-insn ] }
394         { [ over src1>> over vreg-immediate? ] [ t insn>imm-insn ] }
395         [ 2drop f ]
396     } cond ; inline
397
398 M: ##add rewrite \ ##add-imm rewrite-arithmetic-commutative ;
399
400 : subtraction-identity? ( insn -- ? )
401     [ src1>> ] [ src2>> ] bi [ vreg>vn ] bi@ eq?  ;
402
403 : rewrite-subtraction-identity ( insn -- insn' )
404     dst>> 0 \ ##load-immediate new-insn ;
405
406 : sub-to-neg? ( ##sub -- ? )
407     src1>> vn>expr expr-zero? ;
408
409 : sub-to-neg ( ##sub -- insn )
410     [ dst>> ] [ src2>> ] bi \ ##neg new-insn ;
411
412 M: ##sub rewrite
413     {
414         { [ dup sub-to-neg? ] [ sub-to-neg ] }
415         { [ dup subtraction-identity? ] [ rewrite-subtraction-identity ] }
416         [ \ ##sub-imm rewrite-arithmetic ]
417     } cond ;
418
419 M: ##mul rewrite \ ##mul-imm rewrite-arithmetic-commutative ;
420
421 M: ##and rewrite \ ##and-imm rewrite-arithmetic-commutative ;
422
423 M: ##or rewrite \ ##or-imm rewrite-arithmetic-commutative ;
424
425 M: ##xor rewrite \ ##xor-imm rewrite-arithmetic-commutative ;
426
427 M: ##shl rewrite \ ##shl-imm rewrite-arithmetic ;
428
429 M: ##shr rewrite \ ##shr-imm rewrite-arithmetic ;
430
431 M: ##sar rewrite \ ##sar-imm rewrite-arithmetic ;
432
433 ! ##box-displaced-alien f 1 2 3 <class>
434 ! ##unbox-c-ptr 4 1 <class>
435 ! =>
436 ! ##box-displaced-alien f 1 2 3 <class>
437 ! ##unbox-c-ptr 5 3 <class>
438 ! ##add 4 5 2
439
440 :: rewrite-unbox-displaced-alien ( insn expr -- insns )
441     [
442         next-vreg :> temp
443         temp expr base>> vn>vreg expr base-class>> ##unbox-c-ptr
444         insn dst>> temp expr displacement>> vn>vreg ##add
445     ] { } make ;
446
447 M: ##unbox-any-c-ptr rewrite
448     dup src>> vreg>expr dup box-displaced-alien-expr?
449     [ rewrite-unbox-displaced-alien ] [ 2drop f ] if ;
450
451 ! More efficient addressing for alien intrinsics
452 : rewrite-alien-addressing ( insn -- insn' )
453     dup src>> vreg>expr dup add-imm-expr? [
454         [ src1>> vn>vreg ] [ src2>> vn>constant ] bi
455         [ >>src ] [ '[ _ + ] change-offset ] bi*
456     ] [ 2drop f ] if ;
457
458 M: ##alien-unsigned-1 rewrite rewrite-alien-addressing ;
459 M: ##alien-unsigned-2 rewrite rewrite-alien-addressing ;
460 M: ##alien-unsigned-4 rewrite rewrite-alien-addressing ;
461 M: ##alien-signed-1 rewrite rewrite-alien-addressing ;
462 M: ##alien-signed-2 rewrite rewrite-alien-addressing ;
463 M: ##alien-signed-4 rewrite rewrite-alien-addressing ;
464 M: ##alien-float rewrite rewrite-alien-addressing ;
465 M: ##alien-double rewrite rewrite-alien-addressing ;
466 M: ##alien-vector rewrite rewrite-alien-addressing ;
467 M: ##set-alien-integer-1 rewrite rewrite-alien-addressing ;
468 M: ##set-alien-integer-2 rewrite rewrite-alien-addressing ;
469 M: ##set-alien-integer-4 rewrite rewrite-alien-addressing ;
470 M: ##set-alien-float rewrite rewrite-alien-addressing ;
471 M: ##set-alien-double rewrite rewrite-alien-addressing ;
472 M: ##set-alien-vector rewrite rewrite-alien-addressing ;
473
474 ! Some lame constant folding for SIMD intrinsics. Eventually this
475 ! should be redone completely.
476
477 : rewrite-shuffle-vector-imm ( insn expr -- insn' )
478     2dup [ rep>> ] bi@ eq? [
479         [ [ dst>> ] [ src>> vn>vreg ] bi* ]
480         [ [ shuffle>> ] bi@ nths ]
481         [ drop rep>> ]
482         2tri \ ##shuffle-vector-imm new-insn
483     ] [ 2drop f ] if ;
484
485 : (fold-shuffle-vector-imm) ( shuffle bytes -- bytes' )
486     2dup length swap length /i group nths concat ;
487
488 : fold-shuffle-vector-imm ( insn expr -- insn' )
489     [ [ dst>> ] [ shuffle>> ] bi ] dip value>>
490     (fold-shuffle-vector-imm) \ ##load-constant new-insn ;
491
492 M: ##shuffle-vector-imm rewrite
493     dup src>> vreg>expr {
494         { [ dup shuffle-vector-imm-expr? ] [ rewrite-shuffle-vector-imm ] }
495         { [ dup reference-expr? ] [ fold-shuffle-vector-imm ] }
496         { [ dup constant-expr? ] [ fold-shuffle-vector-imm ] }
497         [ 2drop f ]
498     } cond ;
499
500 : (fold-scalar>vector) ( insn bytes -- insn' )
501     [ [ dst>> ] [ rep>> rep-components ] bi ] dip <repetition> concat
502     \ ##load-constant new-insn ;
503
504 : fold-scalar>vector ( insn expr -- insn' )
505     value>> over rep>> {
506         { float-4-rep [ float>bits 4 >le (fold-scalar>vector) ] }
507         { double-2-rep [ double>bits 8 >le (fold-scalar>vector) ] }
508         [ [ untag-fixnum ] dip rep-component-type heap-size >le (fold-scalar>vector) ]
509     } case ;
510
511 M: ##scalar>vector rewrite
512     dup src>> vreg>expr dup constant-expr?
513     [ fold-scalar>vector ] [ 2drop f ] if ;
514
515 M: ##xor-vector rewrite
516     dup [ src1>> vreg>vn ] [ src2>> vreg>vn ] bi eq?
517     [ [ dst>> ] [ rep>> ] bi \ ##zero-vector new-insn ] [ drop f ] if ;
518
519 : vector-not? ( expr -- ? )
520     {
521         [ not-vector-expr? ]
522         [ {
523             [ xor-vector-expr? ]
524             [ [ src1>> ] [ src2>> ] bi [ vn>expr fill-vector-expr? ] either? ]
525         } 1&& ]
526     } 1|| ;
527
528 GENERIC: vector-not-src ( expr -- vreg )
529 M: not-vector-expr vector-not-src src>> vn>vreg ;
530 M: xor-vector-expr vector-not-src
531     dup src1>> vn>expr fill-vector-expr? [ src2>> ] [ src1>> ] if vn>vreg ;
532
533 M: ##and-vector rewrite 
534     {
535         { [ dup src1>> vreg>expr vector-not? ] [
536             {
537                 [ dst>> ]
538                 [ src1>> vreg>expr vector-not-src ]
539                 [ src2>> ]
540                 [ rep>> ]
541             } cleave \ ##andn-vector new-insn
542         ] }
543         { [ dup src2>> vreg>expr vector-not? ] [
544             {
545                 [ dst>> ]
546                 [ src2>> vreg>expr vector-not-src ]
547                 [ src1>> ]
548                 [ rep>> ]
549             } cleave \ ##andn-vector new-insn
550         ] }
551         [ drop f ]
552     } cond ;
553
554 M: ##andn-vector rewrite
555     dup src1>> vreg>expr vector-not? [
556         {
557             [ dst>> ]
558             [ src1>> vreg>expr vector-not-src ]
559             [ src2>> ]
560             [ rep>> ]
561         } cleave \ ##and-vector new-insn
562     ] [ drop f ] if ;