1
2
3
4
5 package ssa
6
7 import (
8 "cmd/internal/src"
9 "fmt"
10 "math"
11 "math/bits"
12 )
13
14 type branch int
15
16 const (
17 unknown branch = iota
18 positive
19 negative
20
21
22
23 jumpTable0
24 )
25
26 func (b branch) String() string {
27 switch b {
28 case unknown:
29 return "unk"
30 case positive:
31 return "pos"
32 case negative:
33 return "neg"
34 default:
35 return fmt.Sprintf("jmp%d", b-jumpTable0)
36 }
37 }
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59 type relation uint
60
61 const (
62 lt relation = 1 << iota
63 eq
64 gt
65 )
66
67 var relationStrings = [...]string{
68 0: "none", lt: "<", eq: "==", lt | eq: "<=",
69 gt: ">", gt | lt: "!=", gt | eq: ">=", gt | eq | lt: "any",
70 }
71
72 func (r relation) String() string {
73 if r < relation(len(relationStrings)) {
74 return relationStrings[r]
75 }
76 return fmt.Sprintf("relation(%d)", uint(r))
77 }
78
79
80
81
82
83 type domain uint
84
85 const (
86 signed domain = 1 << iota
87 unsigned
88 pointer
89 boolean
90 )
91
92 var domainStrings = [...]string{
93 "signed", "unsigned", "pointer", "boolean",
94 }
95
96 func (d domain) String() string {
97 s := ""
98 for i, ds := range domainStrings {
99 if d&(1<<uint(i)) != 0 {
100 if len(s) != 0 {
101 s += "|"
102 }
103 s += ds
104 d &^= 1 << uint(i)
105 }
106 }
107 if d != 0 {
108 if len(s) != 0 {
109 s += "|"
110 }
111 s += fmt.Sprintf("0x%x", uint(d))
112 }
113 return s
114 }
115
116
117
118
119
120
121
122
123
124 type limit struct {
125 min, max int64
126 umin, umax uint64
127
128
129 }
130
131 func (l limit) String() string {
132 return fmt.Sprintf("sm,SM,um,UM=%d,%d,%d,%d", l.min, l.max, l.umin, l.umax)
133 }
134
135 func (l limit) intersect(l2 limit) limit {
136 l.min = max(l.min, l2.min)
137 l.umin = max(l.umin, l2.umin)
138 l.max = min(l.max, l2.max)
139 l.umax = min(l.umax, l2.umax)
140 return l
141 }
142
143 func (l limit) signedMin(m int64) limit {
144 l.min = max(l.min, m)
145 return l
146 }
147 func (l limit) signedMax(m int64) limit {
148 l.max = min(l.max, m)
149 return l
150 }
151 func (l limit) signedMinMax(minimum, maximum int64) limit {
152 l.min = max(l.min, minimum)
153 l.max = min(l.max, maximum)
154 return l
155 }
156
157 func (l limit) unsignedMin(m uint64) limit {
158 l.umin = max(l.umin, m)
159 return l
160 }
161 func (l limit) unsignedMax(m uint64) limit {
162 l.umax = min(l.umax, m)
163 return l
164 }
165 func (l limit) unsignedMinMax(minimum, maximum uint64) limit {
166 l.umin = max(l.umin, minimum)
167 l.umax = min(l.umax, maximum)
168 return l
169 }
170
171 func (l limit) nonzero() bool {
172 return l.min > 0 || l.umin > 0 || l.max < 0
173 }
174 func (l limit) nonnegative() bool {
175 return l.min >= 0
176 }
177 func (l limit) unsat() bool {
178 return l.min > l.max || l.umin > l.umax
179 }
180
181
182
183
184 func safeAdd(x, y int64, b uint) (int64, bool) {
185 s := x + y
186 if x >= 0 && y >= 0 && s < 0 {
187 return 0, false
188 }
189 if x < 0 && y < 0 && s >= 0 {
190 return 0, false
191 }
192 if !fitsInBits(s, b) {
193 return 0, false
194 }
195 return s, true
196 }
197
198
199 func safeAddU(x, y uint64, b uint) (uint64, bool) {
200 s := x + y
201 if s < x || s < y {
202 return 0, false
203 }
204 if !fitsInBitsU(s, b) {
205 return 0, false
206 }
207 return s, true
208 }
209
210
211 func safeSub(x, y int64, b uint) (int64, bool) {
212 if y == math.MinInt64 {
213 if x == math.MaxInt64 {
214 return 0, false
215 }
216 x++
217 y++
218 }
219 return safeAdd(x, -y, b)
220 }
221
222
223 func safeSubU(x, y uint64, b uint) (uint64, bool) {
224 if x < y {
225 return 0, false
226 }
227 s := x - y
228 if !fitsInBitsU(s, b) {
229 return 0, false
230 }
231 return s, true
232 }
233
234
235 func fitsInBits(x int64, b uint) bool {
236 if b == 64 {
237 return true
238 }
239 m := int64(-1) << (b - 1)
240 M := -m - 1
241 return x >= m && x <= M
242 }
243
244
245 func fitsInBitsU(x uint64, b uint) bool {
246 return x>>b == 0
247 }
248
249
250
251 func (l limit) add(l2 limit, b uint) limit {
252 r := noLimit
253 min, minOk := safeAdd(l.min, l2.min, b)
254 max, maxOk := safeAdd(l.max, l2.max, b)
255 if minOk && maxOk {
256 r.min = min
257 r.max = max
258 }
259 umin, uminOk := safeAddU(l.umin, l2.umin, b)
260 umax, umaxOk := safeAddU(l.umax, l2.umax, b)
261 if uminOk && umaxOk {
262 r.umin = umin
263 r.umax = umax
264 }
265 return r
266 }
267
268
269 func (l limit) sub(l2 limit, b uint) limit {
270 r := noLimit
271 min, minOk := safeSub(l.min, l2.max, b)
272 max, maxOk := safeSub(l.max, l2.min, b)
273 if minOk && maxOk {
274 r.min = min
275 r.max = max
276 }
277 umin, uminOk := safeSubU(l.umin, l2.umax, b)
278 umax, umaxOk := safeSubU(l.umax, l2.umin, b)
279 if uminOk && umaxOk {
280 r.umin = umin
281 r.umax = umax
282 }
283 return r
284 }
285
286
287 func (l limit) mul(l2 limit, b uint) limit {
288 r := noLimit
289 umaxhi, umaxlo := bits.Mul64(l.umax, l2.umax)
290 if umaxhi == 0 && fitsInBitsU(umaxlo, b) {
291 r.umax = umaxlo
292 r.umin = l.umin * l2.umin
293
294
295
296
297
298
299 }
300
301
302
303
304
305 return r
306 }
307
308
309 func (l limit) exp2(b uint) limit {
310 r := noLimit
311 if l.umax < uint64(b) {
312 r.umin = 1 << l.umin
313 r.umax = 1 << l.umax
314
315
316 }
317 return r
318 }
319
320
321 func (l limit) com(b uint) limit {
322 switch b {
323 case 64:
324 return limit{
325 min: ^l.max,
326 max: ^l.min,
327 umin: ^l.umax,
328 umax: ^l.umin,
329 }
330 case 32:
331 return limit{
332 min: int64(^int32(l.max)),
333 max: int64(^int32(l.min)),
334 umin: uint64(^uint32(l.umax)),
335 umax: uint64(^uint32(l.umin)),
336 }
337 case 16:
338 return limit{
339 min: int64(^int16(l.max)),
340 max: int64(^int16(l.min)),
341 umin: uint64(^uint16(l.umax)),
342 umax: uint64(^uint16(l.umin)),
343 }
344 case 8:
345 return limit{
346 min: int64(^int8(l.max)),
347 max: int64(^int8(l.min)),
348 umin: uint64(^uint8(l.umax)),
349 umax: uint64(^uint8(l.umin)),
350 }
351 default:
352 panic("unreachable")
353 }
354 }
355
356 var noLimit = limit{math.MinInt64, math.MaxInt64, 0, math.MaxUint64}
357
358
359 type limitFact struct {
360 vid ID
361 limit limit
362 }
363
364
365 type ordering struct {
366 next *ordering
367
368 w *Value
369 d domain
370 r relation
371
372 }
373
374
375
376
377
378
379
380
381 type factsTable struct {
382
383
384
385
386
387 unsat bool
388 unsatDepth int
389
390
391
392
393 orderS *poset
394 orderU *poset
395
396
397
398
399
400
401 orderings map[ID]*ordering
402
403
404 orderingsStack []ID
405 orderingCache *ordering
406
407
408 limits []limit
409 limitStack []limitFact
410 recurseCheck []bool
411
412
413
414
415 lens map[ID]*Value
416 caps map[ID]*Value
417 }
418
419
420
421 var checkpointBound = limitFact{}
422
423 func newFactsTable(f *Func) *factsTable {
424 ft := &factsTable{}
425 ft.orderS = f.newPoset()
426 ft.orderU = f.newPoset()
427 ft.orderS.SetUnsigned(false)
428 ft.orderU.SetUnsigned(true)
429 ft.orderings = make(map[ID]*ordering)
430 ft.limits = f.Cache.allocLimitSlice(f.NumValues())
431 for _, b := range f.Blocks {
432 for _, v := range b.Values {
433 ft.limits[v.ID] = initLimit(v)
434 }
435 }
436 ft.limitStack = make([]limitFact, 4)
437 ft.recurseCheck = f.Cache.allocBoolSlice(f.NumValues())
438 return ft
439 }
440
441
442
443
444 func (ft *factsTable) initLimitForNewValue(v *Value) {
445 if int(v.ID) >= len(ft.limits) {
446 f := v.Block.Func
447 n := f.NumValues()
448 if cap(ft.limits) >= n {
449 ft.limits = ft.limits[:n]
450 } else {
451 old := ft.limits
452 ft.limits = f.Cache.allocLimitSlice(n)
453 copy(ft.limits, old)
454 f.Cache.freeLimitSlice(old)
455 }
456 }
457 ft.limits[v.ID] = initLimit(v)
458 }
459
460
461
462 func (ft *factsTable) signedMin(v *Value, min int64) bool {
463 return ft.newLimit(v, limit{min: min, max: math.MaxInt64, umin: 0, umax: math.MaxUint64})
464 }
465
466
467
468 func (ft *factsTable) signedMax(v *Value, max int64) bool {
469 return ft.newLimit(v, limit{min: math.MinInt64, max: max, umin: 0, umax: math.MaxUint64})
470 }
471 func (ft *factsTable) signedMinMax(v *Value, min, max int64) bool {
472 return ft.newLimit(v, limit{min: min, max: max, umin: 0, umax: math.MaxUint64})
473 }
474
475
476 func (ft *factsTable) setNonNegative(v *Value) bool {
477 return ft.signedMin(v, 0)
478 }
479
480
481
482 func (ft *factsTable) unsignedMin(v *Value, min uint64) bool {
483 return ft.newLimit(v, limit{min: math.MinInt64, max: math.MaxInt64, umin: min, umax: math.MaxUint64})
484 }
485
486
487
488 func (ft *factsTable) unsignedMax(v *Value, max uint64) bool {
489 return ft.newLimit(v, limit{min: math.MinInt64, max: math.MaxInt64, umin: 0, umax: max})
490 }
491 func (ft *factsTable) unsignedMinMax(v *Value, min, max uint64) bool {
492 return ft.newLimit(v, limit{min: math.MinInt64, max: math.MaxInt64, umin: min, umax: max})
493 }
494
495 func (ft *factsTable) booleanFalse(v *Value) bool {
496 return ft.newLimit(v, limit{min: 0, max: 0, umin: 0, umax: 0})
497 }
498 func (ft *factsTable) booleanTrue(v *Value) bool {
499 return ft.newLimit(v, limit{min: 1, max: 1, umin: 1, umax: 1})
500 }
501 func (ft *factsTable) pointerNil(v *Value) bool {
502 return ft.newLimit(v, limit{min: 0, max: 0, umin: 0, umax: 0})
503 }
504 func (ft *factsTable) pointerNonNil(v *Value) bool {
505 l := noLimit
506 l.umin = 1
507 return ft.newLimit(v, l)
508 }
509
510
511
512 func (ft *factsTable) newLimit(v *Value, newLim limit) bool {
513 oldLim := ft.limits[v.ID]
514
515
516 lim := oldLim.intersect(newLim)
517
518
519 if lim.min >= 0 {
520 lim = lim.unsignedMinMax(uint64(lim.min), uint64(lim.max))
521 }
522 if fitsInBitsU(lim.umax, uint(8*v.Type.Size()-1)) {
523 lim = lim.signedMinMax(int64(lim.umin), int64(lim.umax))
524 }
525
526 if lim == oldLim {
527 return false
528 }
529
530 if lim.unsat() {
531 r := !ft.unsat
532 ft.unsat = true
533 return r
534 }
535
536
537
538
539
540
541
542 if ft.recurseCheck[v.ID] {
543
544 return false
545 }
546 ft.recurseCheck[v.ID] = true
547 defer func() {
548 ft.recurseCheck[v.ID] = false
549 }()
550
551
552 ft.limitStack = append(ft.limitStack, limitFact{v.ID, oldLim})
553
554 ft.limits[v.ID] = lim
555 if v.Block.Func.pass.debug > 2 {
556
557
558
559 v.Block.Func.Warnl(v.Pos, "new limit %s %s unsat=%v", v, lim.String(), ft.unsat)
560 }
561
562
563
564
565
566 for o := ft.orderings[v.ID]; o != nil; o = o.next {
567 switch o.d {
568 case signed:
569 switch o.r {
570 case eq:
571 ft.signedMinMax(o.w, lim.min, lim.max)
572 case lt | eq:
573 ft.signedMin(o.w, lim.min)
574 case lt:
575 ft.signedMin(o.w, lim.min+1)
576 case gt | eq:
577 ft.signedMax(o.w, lim.max)
578 case gt:
579 ft.signedMax(o.w, lim.max-1)
580 case lt | gt:
581 if lim.min == lim.max {
582 c := lim.min
583 if ft.limits[o.w.ID].min == c {
584 ft.signedMin(o.w, c+1)
585 }
586 if ft.limits[o.w.ID].max == c {
587 ft.signedMax(o.w, c-1)
588 }
589 }
590 }
591 case unsigned:
592 switch o.r {
593 case eq:
594 ft.unsignedMinMax(o.w, lim.umin, lim.umax)
595 case lt | eq:
596 ft.unsignedMin(o.w, lim.umin)
597 case lt:
598 ft.unsignedMin(o.w, lim.umin+1)
599 case gt | eq:
600 ft.unsignedMax(o.w, lim.umax)
601 case gt:
602 ft.unsignedMax(o.w, lim.umax-1)
603 case lt | gt:
604 if lim.umin == lim.umax {
605 c := lim.umin
606 if ft.limits[o.w.ID].umin == c {
607 ft.unsignedMin(o.w, c+1)
608 }
609 if ft.limits[o.w.ID].umax == c {
610 ft.unsignedMax(o.w, c-1)
611 }
612 }
613 }
614 case boolean:
615 switch o.r {
616 case eq:
617 if lim.min == 0 && lim.max == 0 {
618 ft.booleanFalse(o.w)
619 }
620 if lim.min == 1 && lim.max == 1 {
621 ft.booleanTrue(o.w)
622 }
623 case lt | gt:
624 if lim.min == 0 && lim.max == 0 {
625 ft.booleanTrue(o.w)
626 }
627 if lim.min == 1 && lim.max == 1 {
628 ft.booleanFalse(o.w)
629 }
630 }
631 case pointer:
632 switch o.r {
633 case eq:
634 if lim.umax == 0 {
635 ft.pointerNil(o.w)
636 }
637 if lim.umin > 0 {
638 ft.pointerNonNil(o.w)
639 }
640 case lt | gt:
641 if lim.umax == 0 {
642 ft.pointerNonNil(o.w)
643 }
644
645 }
646 }
647 }
648
649
650
651
652 if v.Type.IsBoolean() {
653
654
655
656 if lim.min != lim.max {
657 v.Block.Func.Fatalf("boolean not constant %v", v)
658 }
659 isTrue := lim.min == 1
660 if dr, ok := domainRelationTable[v.Op]; ok && v.Op != OpIsInBounds && v.Op != OpIsSliceInBounds {
661 d := dr.d
662 r := dr.r
663 if d == signed && ft.isNonNegative(v.Args[0]) && ft.isNonNegative(v.Args[1]) {
664 d |= unsigned
665 }
666 if !isTrue {
667 r ^= lt | gt | eq
668 }
669
670 addRestrictions(v.Block, ft, d, v.Args[0], v.Args[1], r)
671 }
672 switch v.Op {
673 case OpIsNonNil:
674 if isTrue {
675 ft.pointerNonNil(v.Args[0])
676 } else {
677 ft.pointerNil(v.Args[0])
678 }
679 case OpIsInBounds, OpIsSliceInBounds:
680
681 r := lt
682 if v.Op == OpIsSliceInBounds {
683 r |= eq
684 }
685 if isTrue {
686
687
688
689 ft.setNonNegative(v.Args[0])
690 ft.update(v.Block, v.Args[0], v.Args[1], signed, r)
691 ft.update(v.Block, v.Args[0], v.Args[1], unsigned, r)
692 } else {
693
694
695
696
697
698
699
700 r ^= lt | gt | eq
701 if ft.isNonNegative(v.Args[0]) {
702 ft.update(v.Block, v.Args[0], v.Args[1], signed, r)
703 }
704 ft.update(v.Block, v.Args[0], v.Args[1], unsigned, r)
705
706 }
707 }
708 }
709
710 return true
711 }
712
713 func (ft *factsTable) addOrdering(v, w *Value, d domain, r relation) {
714 o := ft.orderingCache
715 if o == nil {
716 o = &ordering{}
717 } else {
718 ft.orderingCache = o.next
719 }
720 o.w = w
721 o.d = d
722 o.r = r
723 o.next = ft.orderings[v.ID]
724 ft.orderings[v.ID] = o
725 ft.orderingsStack = append(ft.orderingsStack, v.ID)
726 }
727
728
729
730 func (ft *factsTable) update(parent *Block, v, w *Value, d domain, r relation) {
731 if parent.Func.pass.debug > 2 {
732 parent.Func.Warnl(parent.Pos, "parent=%s, update %s %s %s", parent, v, w, r)
733 }
734
735 if ft.unsat {
736 return
737 }
738
739
740
741 if v == w {
742 if r&eq == 0 {
743 ft.unsat = true
744 }
745 return
746 }
747
748 if d == signed || d == unsigned {
749 var ok bool
750 order := ft.orderS
751 if d == unsigned {
752 order = ft.orderU
753 }
754 switch r {
755 case lt:
756 ok = order.SetOrder(v, w)
757 case gt:
758 ok = order.SetOrder(w, v)
759 case lt | eq:
760 ok = order.SetOrderOrEqual(v, w)
761 case gt | eq:
762 ok = order.SetOrderOrEqual(w, v)
763 case eq:
764 ok = order.SetEqual(v, w)
765 case lt | gt:
766 ok = order.SetNonEqual(v, w)
767 default:
768 panic("unknown relation")
769 }
770 ft.addOrdering(v, w, d, r)
771 ft.addOrdering(w, v, d, reverseBits[r])
772
773 if !ok {
774 if parent.Func.pass.debug > 2 {
775 parent.Func.Warnl(parent.Pos, "unsat %s %s %s", v, w, r)
776 }
777 ft.unsat = true
778 return
779 }
780 }
781 if d == boolean || d == pointer {
782 for o := ft.orderings[v.ID]; o != nil; o = o.next {
783 if o.d == d && o.w == w {
784
785
786
787 if o.r != r {
788 ft.unsat = true
789 }
790 return
791 }
792 }
793
794
795 ft.addOrdering(v, w, d, r)
796 ft.addOrdering(w, v, d, r)
797 }
798
799
800 vLimit := ft.limits[v.ID]
801 wLimit := ft.limits[w.ID]
802
803
804
805
806
807 switch d {
808 case signed:
809 switch r {
810 case eq:
811 ft.signedMinMax(v, wLimit.min, wLimit.max)
812 ft.signedMinMax(w, vLimit.min, vLimit.max)
813 case lt:
814 ft.signedMax(v, wLimit.max-1)
815 ft.signedMin(w, vLimit.min+1)
816 case lt | eq:
817 ft.signedMax(v, wLimit.max)
818 ft.signedMin(w, vLimit.min)
819 case gt:
820 ft.signedMin(v, wLimit.min+1)
821 ft.signedMax(w, vLimit.max-1)
822 case gt | eq:
823 ft.signedMin(v, wLimit.min)
824 ft.signedMax(w, vLimit.max)
825 case lt | gt:
826 if vLimit.min == vLimit.max {
827 c := vLimit.min
828 if wLimit.min == c {
829 ft.signedMin(w, c+1)
830 }
831 if wLimit.max == c {
832 ft.signedMax(w, c-1)
833 }
834 }
835 if wLimit.min == wLimit.max {
836 c := wLimit.min
837 if vLimit.min == c {
838 ft.signedMin(v, c+1)
839 }
840 if vLimit.max == c {
841 ft.signedMax(v, c-1)
842 }
843 }
844 }
845 case unsigned:
846 switch r {
847 case eq:
848 ft.unsignedMinMax(v, wLimit.umin, wLimit.umax)
849 ft.unsignedMinMax(w, vLimit.umin, vLimit.umax)
850 case lt:
851 ft.unsignedMax(v, wLimit.umax-1)
852 ft.unsignedMin(w, vLimit.umin+1)
853 case lt | eq:
854 ft.unsignedMax(v, wLimit.umax)
855 ft.unsignedMin(w, vLimit.umin)
856 case gt:
857 ft.unsignedMin(v, wLimit.umin+1)
858 ft.unsignedMax(w, vLimit.umax-1)
859 case gt | eq:
860 ft.unsignedMin(v, wLimit.umin)
861 ft.unsignedMax(w, vLimit.umax)
862 case lt | gt:
863 if vLimit.umin == vLimit.umax {
864 c := vLimit.umin
865 if wLimit.umin == c {
866 ft.unsignedMin(w, c+1)
867 }
868 if wLimit.umax == c {
869 ft.unsignedMax(w, c-1)
870 }
871 }
872 if wLimit.umin == wLimit.umax {
873 c := wLimit.umin
874 if vLimit.umin == c {
875 ft.unsignedMin(v, c+1)
876 }
877 if vLimit.umax == c {
878 ft.unsignedMax(v, c-1)
879 }
880 }
881 }
882 case boolean:
883 switch r {
884 case eq:
885 if vLimit.min == 1 {
886 ft.booleanTrue(w)
887 }
888 if vLimit.max == 0 {
889 ft.booleanFalse(w)
890 }
891 if wLimit.min == 1 {
892 ft.booleanTrue(v)
893 }
894 if wLimit.max == 0 {
895 ft.booleanFalse(v)
896 }
897 case lt | gt:
898 if vLimit.min == 1 {
899 ft.booleanFalse(w)
900 }
901 if vLimit.max == 0 {
902 ft.booleanTrue(w)
903 }
904 if wLimit.min == 1 {
905 ft.booleanFalse(v)
906 }
907 if wLimit.max == 0 {
908 ft.booleanTrue(v)
909 }
910 }
911 case pointer:
912 switch r {
913 case eq:
914 if vLimit.umax == 0 {
915 ft.pointerNil(w)
916 }
917 if vLimit.umin > 0 {
918 ft.pointerNonNil(w)
919 }
920 if wLimit.umax == 0 {
921 ft.pointerNil(v)
922 }
923 if wLimit.umin > 0 {
924 ft.pointerNonNil(v)
925 }
926 case lt | gt:
927 if vLimit.umax == 0 {
928 ft.pointerNonNil(w)
929 }
930 if wLimit.umax == 0 {
931 ft.pointerNonNil(v)
932 }
933
934
935
936 }
937 }
938
939
940 if d != signed && d != unsigned {
941 return
942 }
943
944
945
946
947
948
949 if v.Op == OpSliceLen && r< == 0 && ft.caps[v.Args[0].ID] != nil {
950
951
952
953 ft.update(parent, ft.caps[v.Args[0].ID], w, d, r|gt)
954 }
955 if w.Op == OpSliceLen && r> == 0 && ft.caps[w.Args[0].ID] != nil {
956
957 ft.update(parent, v, ft.caps[w.Args[0].ID], d, r|lt)
958 }
959 if v.Op == OpSliceCap && r> == 0 && ft.lens[v.Args[0].ID] != nil {
960
961
962
963 ft.update(parent, ft.lens[v.Args[0].ID], w, d, r|lt)
964 }
965 if w.Op == OpSliceCap && r< == 0 && ft.lens[w.Args[0].ID] != nil {
966
967 ft.update(parent, v, ft.lens[w.Args[0].ID], d, r|gt)
968 }
969
970
971
972
973 if r == lt || r == lt|eq {
974 v, w = w, v
975 r = reverseBits[r]
976 }
977 switch r {
978 case gt:
979 if x, delta := isConstDelta(v); x != nil && delta == 1 {
980
981
982
983
984 ft.update(parent, x, w, d, gt|eq)
985 } else if x, delta := isConstDelta(w); x != nil && delta == -1 {
986
987 ft.update(parent, v, x, d, gt|eq)
988 }
989 case gt | eq:
990 if x, delta := isConstDelta(v); x != nil && delta == -1 {
991
992
993
994 lim := ft.limits[x.ID]
995 if (d == signed && lim.min > opMin[v.Op]) || (d == unsigned && lim.umin > 0) {
996 ft.update(parent, x, w, d, gt)
997 }
998 } else if x, delta := isConstDelta(w); x != nil && delta == 1 {
999
1000 lim := ft.limits[x.ID]
1001 if (d == signed && lim.max < opMax[w.Op]) || (d == unsigned && lim.umax < opUMax[w.Op]) {
1002 ft.update(parent, v, x, d, gt)
1003 }
1004 }
1005 }
1006
1007
1008
1009 if r == gt || r == gt|eq {
1010 if x, delta := isConstDelta(v); x != nil && d == signed {
1011 if parent.Func.pass.debug > 1 {
1012 parent.Func.Warnl(parent.Pos, "x+d %s w; x:%v %v delta:%v w:%v d:%v", r, x, parent.String(), delta, w.AuxInt, d)
1013 }
1014 underflow := true
1015 if delta < 0 {
1016 l := ft.limits[x.ID]
1017 if (x.Type.Size() == 8 && l.min >= math.MinInt64-delta) ||
1018 (x.Type.Size() == 4 && l.min >= math.MinInt32-delta) {
1019 underflow = false
1020 }
1021 }
1022 if delta < 0 && !underflow {
1023
1024 ft.update(parent, x, v, signed, gt)
1025 }
1026 if !w.isGenericIntConst() {
1027
1028
1029
1030 if delta < 0 && !underflow {
1031 ft.update(parent, x, w, signed, r)
1032 }
1033 } else {
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051 var min, max int64
1052 switch x.Type.Size() {
1053 case 8:
1054 min = w.AuxInt - delta
1055 max = int64(^uint64(0)>>1) - delta
1056 case 4:
1057 min = int64(int32(w.AuxInt) - int32(delta))
1058 max = int64(int32(^uint32(0)>>1) - int32(delta))
1059 case 2:
1060 min = int64(int16(w.AuxInt) - int16(delta))
1061 max = int64(int16(^uint16(0)>>1) - int16(delta))
1062 case 1:
1063 min = int64(int8(w.AuxInt) - int8(delta))
1064 max = int64(int8(^uint8(0)>>1) - int8(delta))
1065 default:
1066 panic("unimplemented")
1067 }
1068
1069 if min < max {
1070
1071 if r == gt {
1072 min++
1073 }
1074 ft.signedMinMax(x, min, max)
1075 } else {
1076
1077
1078
1079 l := ft.limits[x.ID]
1080 if l.max <= min {
1081 if r&eq == 0 || l.max < min {
1082
1083 ft.signedMax(x, max)
1084 }
1085 } else if l.min > max {
1086
1087 if r == gt {
1088 min++
1089 }
1090 ft.signedMin(x, min)
1091 }
1092 }
1093 }
1094 }
1095 }
1096
1097
1098
1099
1100 if isCleanExt(v) {
1101 switch {
1102 case d == signed && v.Args[0].Type.IsSigned():
1103 fallthrough
1104 case d == unsigned && !v.Args[0].Type.IsSigned():
1105 ft.update(parent, v.Args[0], w, d, r)
1106 }
1107 }
1108 if isCleanExt(w) {
1109 switch {
1110 case d == signed && w.Args[0].Type.IsSigned():
1111 fallthrough
1112 case d == unsigned && !w.Args[0].Type.IsSigned():
1113 ft.update(parent, v, w.Args[0], d, r)
1114 }
1115 }
1116 }
1117
1118 var opMin = map[Op]int64{
1119 OpAdd64: math.MinInt64, OpSub64: math.MinInt64,
1120 OpAdd32: math.MinInt32, OpSub32: math.MinInt32,
1121 }
1122
1123 var opMax = map[Op]int64{
1124 OpAdd64: math.MaxInt64, OpSub64: math.MaxInt64,
1125 OpAdd32: math.MaxInt32, OpSub32: math.MaxInt32,
1126 }
1127
1128 var opUMax = map[Op]uint64{
1129 OpAdd64: math.MaxUint64, OpSub64: math.MaxUint64,
1130 OpAdd32: math.MaxUint32, OpSub32: math.MaxUint32,
1131 }
1132
1133
1134 func (ft *factsTable) isNonNegative(v *Value) bool {
1135 return ft.limits[v.ID].min >= 0
1136 }
1137
1138
1139
1140 func (ft *factsTable) checkpoint() {
1141 if ft.unsat {
1142 ft.unsatDepth++
1143 }
1144 ft.limitStack = append(ft.limitStack, checkpointBound)
1145 ft.orderS.Checkpoint()
1146 ft.orderU.Checkpoint()
1147 ft.orderingsStack = append(ft.orderingsStack, 0)
1148 }
1149
1150
1151
1152
1153 func (ft *factsTable) restore() {
1154 if ft.unsatDepth > 0 {
1155 ft.unsatDepth--
1156 } else {
1157 ft.unsat = false
1158 }
1159 for {
1160 old := ft.limitStack[len(ft.limitStack)-1]
1161 ft.limitStack = ft.limitStack[:len(ft.limitStack)-1]
1162 if old.vid == 0 {
1163 break
1164 }
1165 ft.limits[old.vid] = old.limit
1166 }
1167 ft.orderS.Undo()
1168 ft.orderU.Undo()
1169 for {
1170 id := ft.orderingsStack[len(ft.orderingsStack)-1]
1171 ft.orderingsStack = ft.orderingsStack[:len(ft.orderingsStack)-1]
1172 if id == 0 {
1173 break
1174 }
1175 o := ft.orderings[id]
1176 ft.orderings[id] = o.next
1177 o.next = ft.orderingCache
1178 ft.orderingCache = o
1179 }
1180 }
1181
1182 var (
1183 reverseBits = [...]relation{0, 4, 2, 6, 1, 5, 3, 7}
1184
1185
1186
1187
1188
1189
1190
1191 domainRelationTable = map[Op]struct {
1192 d domain
1193 r relation
1194 }{
1195 OpEq8: {signed | unsigned, eq},
1196 OpEq16: {signed | unsigned, eq},
1197 OpEq32: {signed | unsigned, eq},
1198 OpEq64: {signed | unsigned, eq},
1199 OpEqPtr: {pointer, eq},
1200 OpEqB: {boolean, eq},
1201
1202 OpNeq8: {signed | unsigned, lt | gt},
1203 OpNeq16: {signed | unsigned, lt | gt},
1204 OpNeq32: {signed | unsigned, lt | gt},
1205 OpNeq64: {signed | unsigned, lt | gt},
1206 OpNeqPtr: {pointer, lt | gt},
1207 OpNeqB: {boolean, lt | gt},
1208
1209 OpLess8: {signed, lt},
1210 OpLess8U: {unsigned, lt},
1211 OpLess16: {signed, lt},
1212 OpLess16U: {unsigned, lt},
1213 OpLess32: {signed, lt},
1214 OpLess32U: {unsigned, lt},
1215 OpLess64: {signed, lt},
1216 OpLess64U: {unsigned, lt},
1217
1218 OpLeq8: {signed, lt | eq},
1219 OpLeq8U: {unsigned, lt | eq},
1220 OpLeq16: {signed, lt | eq},
1221 OpLeq16U: {unsigned, lt | eq},
1222 OpLeq32: {signed, lt | eq},
1223 OpLeq32U: {unsigned, lt | eq},
1224 OpLeq64: {signed, lt | eq},
1225 OpLeq64U: {unsigned, lt | eq},
1226 }
1227 )
1228
1229
1230 func (ft *factsTable) cleanup(f *Func) {
1231 for _, po := range []*poset{ft.orderS, ft.orderU} {
1232
1233
1234 if checkEnabled {
1235 if err := po.CheckEmpty(); err != nil {
1236 f.Fatalf("poset not empty after function %s: %v", f.Name, err)
1237 }
1238 }
1239 f.retPoset(po)
1240 }
1241 f.Cache.freeLimitSlice(ft.limits)
1242 f.Cache.freeBoolSlice(ft.recurseCheck)
1243 }
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276 func prove(f *Func) {
1277
1278
1279 var indVars map[*Block]indVar
1280 for _, v := range findIndVar(f) {
1281 ind := v.ind
1282 if len(ind.Args) != 2 {
1283
1284 panic("unexpected induction with too many parents")
1285 }
1286
1287 nxt := v.nxt
1288 if !(ind.Uses == 2 &&
1289 nxt.Uses == 1) {
1290
1291 if indVars == nil {
1292 indVars = make(map[*Block]indVar)
1293 }
1294 indVars[v.entry] = v
1295 continue
1296 } else {
1297
1298
1299 }
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337 start, end := v.min, v.max
1338 if v.flags&indVarCountDown != 0 {
1339 start, end = end, start
1340 }
1341
1342 if !start.isGenericIntConst() {
1343
1344 continue
1345 }
1346 if end.isGenericIntConst() {
1347
1348
1349
1350
1351
1352
1353 continue
1354 }
1355
1356 if end.Block == ind.Block {
1357
1358
1359 continue
1360 }
1361
1362 check := ind.Block.Controls[0]
1363
1364 check.Args[0], check.Args[1] = check.Args[1], check.Args[0]
1365
1366
1367 for i, v := range check.Args {
1368 if v != end {
1369 continue
1370 }
1371
1372 check.SetArg(i, start)
1373 goto replacedEnd
1374 }
1375 panic(fmt.Sprintf("unreachable, ind: %v, start: %v, end: %v", ind, start, end))
1376 replacedEnd:
1377
1378 for i, v := range ind.Args {
1379 if v != start {
1380 continue
1381 }
1382
1383 ind.SetArg(i, end)
1384 goto replacedStart
1385 }
1386 panic(fmt.Sprintf("unreachable, ind: %v, start: %v, end: %v", ind, start, end))
1387 replacedStart:
1388
1389 if nxt.Args[0] != ind {
1390
1391 nxt.Args[0], nxt.Args[1] = nxt.Args[1], nxt.Args[0]
1392 }
1393
1394 switch nxt.Op {
1395 case OpAdd8:
1396 nxt.Op = OpSub8
1397 case OpAdd16:
1398 nxt.Op = OpSub16
1399 case OpAdd32:
1400 nxt.Op = OpSub32
1401 case OpAdd64:
1402 nxt.Op = OpSub64
1403 case OpSub8:
1404 nxt.Op = OpAdd8
1405 case OpSub16:
1406 nxt.Op = OpAdd16
1407 case OpSub32:
1408 nxt.Op = OpAdd32
1409 case OpSub64:
1410 nxt.Op = OpAdd64
1411 default:
1412 panic("unreachable")
1413 }
1414
1415 if f.pass.debug > 0 {
1416 f.Warnl(ind.Pos, "Inverted loop iteration")
1417 }
1418 }
1419
1420 ft := newFactsTable(f)
1421 ft.checkpoint()
1422
1423
1424 for _, b := range f.Blocks {
1425 for _, v := range b.Values {
1426 if v.Uses == 0 {
1427
1428
1429 continue
1430 }
1431 switch v.Op {
1432 case OpSliceLen:
1433 if ft.lens == nil {
1434 ft.lens = map[ID]*Value{}
1435 }
1436
1437
1438
1439 if l, ok := ft.lens[v.Args[0].ID]; ok {
1440 ft.update(b, v, l, signed, eq)
1441 } else {
1442 ft.lens[v.Args[0].ID] = v
1443 }
1444 case OpSliceCap:
1445 if ft.caps == nil {
1446 ft.caps = map[ID]*Value{}
1447 }
1448
1449 if c, ok := ft.caps[v.Args[0].ID]; ok {
1450 ft.update(b, v, c, signed, eq)
1451 } else {
1452 ft.caps[v.Args[0].ID] = v
1453 }
1454 }
1455 }
1456 }
1457
1458
1459 type walkState int
1460 const (
1461 descend walkState = iota
1462 simplify
1463 )
1464
1465 type bp struct {
1466 block *Block
1467 state walkState
1468 }
1469 work := make([]bp, 0, 256)
1470 work = append(work, bp{
1471 block: f.Entry,
1472 state: descend,
1473 })
1474
1475 idom := f.Idom()
1476 sdom := f.Sdom()
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488 for len(work) > 0 {
1489 node := work[len(work)-1]
1490 work = work[:len(work)-1]
1491 parent := idom[node.block.ID]
1492 branch := getBranch(sdom, parent, node.block)
1493
1494 switch node.state {
1495 case descend:
1496 ft.checkpoint()
1497
1498
1499
1500 if iv, ok := indVars[node.block]; ok {
1501 addIndVarRestrictions(ft, parent, iv)
1502 }
1503
1504
1505
1506 if branch != unknown {
1507 addBranchRestrictions(ft, parent, branch)
1508 }
1509
1510 if ft.unsat {
1511
1512
1513
1514 removeBranch(parent, branch)
1515 ft.restore()
1516 break
1517 }
1518
1519
1520
1521
1522
1523 addLocalFacts(ft, node.block)
1524
1525 work = append(work, bp{
1526 block: node.block,
1527 state: simplify,
1528 })
1529 for s := sdom.Child(node.block); s != nil; s = sdom.Sibling(s) {
1530 work = append(work, bp{
1531 block: s,
1532 state: descend,
1533 })
1534 }
1535
1536 case simplify:
1537 simplifyBlock(sdom, ft, node.block)
1538 ft.restore()
1539 }
1540 }
1541
1542 ft.restore()
1543
1544 ft.cleanup(f)
1545 }
1546
1547
1548
1549
1550
1551
1552
1553 func initLimit(v *Value) limit {
1554 if v.Type.IsBoolean() {
1555 switch v.Op {
1556 case OpConstBool:
1557 b := v.AuxInt
1558 return limit{min: b, max: b, umin: uint64(b), umax: uint64(b)}
1559 default:
1560 return limit{min: 0, max: 1, umin: 0, umax: 1}
1561 }
1562 }
1563 if v.Type.IsPtrShaped() {
1564 switch v.Op {
1565 case OpConstNil:
1566 return limit{min: 0, max: 0, umin: 0, umax: 0}
1567 case OpAddr, OpLocalAddr:
1568 l := noLimit
1569 l.umin = 1
1570 return l
1571 default:
1572 return noLimit
1573 }
1574 }
1575 if !v.Type.IsInteger() {
1576 return noLimit
1577 }
1578
1579
1580 bitsize := v.Type.Size() * 8
1581 lim := limit{min: -(1 << (bitsize - 1)), max: 1<<(bitsize-1) - 1, umin: 0, umax: 1<<bitsize - 1}
1582
1583
1584 switch v.Op {
1585
1586 case OpConst64:
1587 lim = limit{min: v.AuxInt, max: v.AuxInt, umin: uint64(v.AuxInt), umax: uint64(v.AuxInt)}
1588 case OpConst32:
1589 lim = limit{min: v.AuxInt, max: v.AuxInt, umin: uint64(uint32(v.AuxInt)), umax: uint64(uint32(v.AuxInt))}
1590 case OpConst16:
1591 lim = limit{min: v.AuxInt, max: v.AuxInt, umin: uint64(uint16(v.AuxInt)), umax: uint64(uint16(v.AuxInt))}
1592 case OpConst8:
1593 lim = limit{min: v.AuxInt, max: v.AuxInt, umin: uint64(uint8(v.AuxInt)), umax: uint64(uint8(v.AuxInt))}
1594
1595
1596 case OpZeroExt8to64, OpZeroExt8to32, OpZeroExt8to16:
1597 lim = lim.signedMinMax(0, 1<<8-1)
1598 lim = lim.unsignedMax(1<<8 - 1)
1599 case OpZeroExt16to64, OpZeroExt16to32:
1600 lim = lim.signedMinMax(0, 1<<16-1)
1601 lim = lim.unsignedMax(1<<16 - 1)
1602 case OpZeroExt32to64:
1603 lim = lim.signedMinMax(0, 1<<32-1)
1604 lim = lim.unsignedMax(1<<32 - 1)
1605 case OpSignExt8to64, OpSignExt8to32, OpSignExt8to16:
1606 lim = lim.signedMinMax(math.MinInt8, math.MaxInt8)
1607 case OpSignExt16to64, OpSignExt16to32:
1608 lim = lim.signedMinMax(math.MinInt16, math.MaxInt16)
1609 case OpSignExt32to64:
1610 lim = lim.signedMinMax(math.MinInt32, math.MaxInt32)
1611
1612
1613 case OpCtz64, OpBitLen64, OpPopCount64,
1614 OpCtz32, OpBitLen32, OpPopCount32,
1615 OpCtz16, OpBitLen16, OpPopCount16,
1616 OpCtz8, OpBitLen8, OpPopCount8:
1617 lim = lim.unsignedMax(uint64(v.Args[0].Type.Size() * 8))
1618
1619
1620 case OpCvtBoolToUint8:
1621 lim = lim.unsignedMax(1)
1622
1623
1624 case OpStringLen, OpSliceLen, OpSliceCap:
1625 lim = lim.signedMin(0)
1626 }
1627
1628
1629 if lim.min >= 0 {
1630 lim = lim.unsignedMinMax(uint64(lim.min), uint64(lim.max))
1631 }
1632 if fitsInBitsU(lim.umax, uint(8*v.Type.Size()-1)) {
1633 lim = lim.signedMinMax(int64(lim.umin), int64(lim.umax))
1634 }
1635
1636 return lim
1637 }
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652 func (ft *factsTable) flowLimit(v *Value) bool {
1653 if !v.Type.IsInteger() {
1654
1655 return false
1656 }
1657
1658
1659
1660 switch v.Op {
1661
1662
1663 case OpZeroExt8to64, OpZeroExt8to32, OpZeroExt8to16, OpZeroExt16to64, OpZeroExt16to32, OpZeroExt32to64:
1664 a := ft.limits[v.Args[0].ID]
1665 return ft.unsignedMinMax(v, a.umin, a.umax)
1666 case OpSignExt8to64, OpSignExt8to32, OpSignExt8to16, OpSignExt16to64, OpSignExt16to32, OpSignExt32to64:
1667 a := ft.limits[v.Args[0].ID]
1668 return ft.signedMinMax(v, a.min, a.max)
1669 case OpTrunc64to8, OpTrunc64to16, OpTrunc64to32, OpTrunc32to8, OpTrunc32to16, OpTrunc16to8:
1670 a := ft.limits[v.Args[0].ID]
1671 if a.umax <= 1<<(uint64(v.Type.Size())*8)-1 {
1672 return ft.unsignedMinMax(v, a.umin, a.umax)
1673 }
1674
1675
1676 case OpCtz64:
1677 a := ft.limits[v.Args[0].ID]
1678 if a.nonzero() {
1679 return ft.unsignedMax(v, uint64(bits.Len64(a.umax)-1))
1680 }
1681 case OpCtz32:
1682 a := ft.limits[v.Args[0].ID]
1683 if a.nonzero() {
1684 return ft.unsignedMax(v, uint64(bits.Len32(uint32(a.umax))-1))
1685 }
1686 case OpCtz16:
1687 a := ft.limits[v.Args[0].ID]
1688 if a.nonzero() {
1689 return ft.unsignedMax(v, uint64(bits.Len16(uint16(a.umax))-1))
1690 }
1691 case OpCtz8:
1692 a := ft.limits[v.Args[0].ID]
1693 if a.nonzero() {
1694 return ft.unsignedMax(v, uint64(bits.Len8(uint8(a.umax))-1))
1695 }
1696
1697 case OpPopCount64, OpPopCount32, OpPopCount16, OpPopCount8:
1698 a := ft.limits[v.Args[0].ID]
1699 changingBitsCount := uint64(bits.Len64(a.umax ^ a.umin))
1700 sharedLeadingMask := ^(uint64(1)<<changingBitsCount - 1)
1701 fixedBits := a.umax & sharedLeadingMask
1702 min := uint64(bits.OnesCount64(fixedBits))
1703 return ft.unsignedMinMax(v, min, min+changingBitsCount)
1704
1705 case OpBitLen64:
1706 a := ft.limits[v.Args[0].ID]
1707 return ft.unsignedMinMax(v,
1708 uint64(bits.Len64(a.umin)),
1709 uint64(bits.Len64(a.umax)))
1710 case OpBitLen32:
1711 a := ft.limits[v.Args[0].ID]
1712 return ft.unsignedMinMax(v,
1713 uint64(bits.Len32(uint32(a.umin))),
1714 uint64(bits.Len32(uint32(a.umax))))
1715 case OpBitLen16:
1716 a := ft.limits[v.Args[0].ID]
1717 return ft.unsignedMinMax(v,
1718 uint64(bits.Len16(uint16(a.umin))),
1719 uint64(bits.Len16(uint16(a.umax))))
1720 case OpBitLen8:
1721 a := ft.limits[v.Args[0].ID]
1722 return ft.unsignedMinMax(v,
1723 uint64(bits.Len8(uint8(a.umin))),
1724 uint64(bits.Len8(uint8(a.umax))))
1725
1726
1727
1728
1729
1730
1731 case OpAnd64, OpAnd32, OpAnd16, OpAnd8:
1732
1733 a := ft.limits[v.Args[0].ID]
1734 b := ft.limits[v.Args[1].ID]
1735 return ft.unsignedMax(v, min(a.umax, b.umax))
1736 case OpOr64, OpOr32, OpOr16, OpOr8:
1737
1738 a := ft.limits[v.Args[0].ID]
1739 b := ft.limits[v.Args[1].ID]
1740 return ft.unsignedMinMax(v,
1741 max(a.umin, b.umin),
1742 1<<bits.Len64(a.umax|b.umax)-1)
1743 case OpXor64, OpXor32, OpXor16, OpXor8:
1744
1745 a := ft.limits[v.Args[0].ID]
1746 b := ft.limits[v.Args[1].ID]
1747 return ft.unsignedMax(v, 1<<bits.Len64(a.umax|b.umax)-1)
1748 case OpCom64, OpCom32, OpCom16, OpCom8:
1749 a := ft.limits[v.Args[0].ID]
1750 return ft.newLimit(v, a.com(uint(v.Type.Size())*8))
1751
1752
1753 case OpAdd64, OpAdd32, OpAdd16, OpAdd8:
1754 a := ft.limits[v.Args[0].ID]
1755 b := ft.limits[v.Args[1].ID]
1756 return ft.newLimit(v, a.add(b, uint(v.Type.Size())*8))
1757 case OpSub64, OpSub32, OpSub16, OpSub8:
1758 a := ft.limits[v.Args[0].ID]
1759 b := ft.limits[v.Args[1].ID]
1760 sub := ft.newLimit(v, a.sub(b, uint(v.Type.Size())*8))
1761 mod := ft.detectSignedMod(v)
1762 return sub || mod
1763 case OpNeg64, OpNeg32, OpNeg16, OpNeg8:
1764 a := ft.limits[v.Args[0].ID]
1765 bitsize := uint(v.Type.Size()) * 8
1766 return ft.newLimit(v, a.com(bitsize).add(limit{min: 1, max: 1, umin: 1, umax: 1}, bitsize))
1767 case OpMul64, OpMul32, OpMul16, OpMul8:
1768 a := ft.limits[v.Args[0].ID]
1769 b := ft.limits[v.Args[1].ID]
1770 return ft.newLimit(v, a.mul(b, uint(v.Type.Size())*8))
1771 case OpLsh64x64, OpLsh64x32, OpLsh64x16, OpLsh64x8,
1772 OpLsh32x64, OpLsh32x32, OpLsh32x16, OpLsh32x8,
1773 OpLsh16x64, OpLsh16x32, OpLsh16x16, OpLsh16x8,
1774 OpLsh8x64, OpLsh8x32, OpLsh8x16, OpLsh8x8:
1775 a := ft.limits[v.Args[0].ID]
1776 b := ft.limits[v.Args[1].ID]
1777 bitsize := uint(v.Type.Size()) * 8
1778 return ft.newLimit(v, a.mul(b.exp2(bitsize), bitsize))
1779 case OpMod64, OpMod32, OpMod16, OpMod8:
1780 a := ft.limits[v.Args[0].ID]
1781 b := ft.limits[v.Args[1].ID]
1782 if !(a.nonnegative() && b.nonnegative()) {
1783
1784 break
1785 }
1786 fallthrough
1787 case OpMod64u, OpMod32u, OpMod16u, OpMod8u:
1788 a := ft.limits[v.Args[0].ID]
1789 b := ft.limits[v.Args[1].ID]
1790
1791 return ft.unsignedMax(v, min(a.umax, b.umax-1))
1792 case OpDiv64, OpDiv32, OpDiv16, OpDiv8:
1793 a := ft.limits[v.Args[0].ID]
1794 b := ft.limits[v.Args[1].ID]
1795 if !(a.nonnegative() && b.nonnegative()) {
1796
1797 break
1798 }
1799 fallthrough
1800 case OpDiv64u, OpDiv32u, OpDiv16u, OpDiv8u:
1801 a := ft.limits[v.Args[0].ID]
1802 b := ft.limits[v.Args[1].ID]
1803 lim := noLimit
1804 if b.umax > 0 {
1805 lim = lim.unsignedMin(a.umin / b.umax)
1806 }
1807 if b.umin > 0 {
1808 lim = lim.unsignedMax(a.umax / b.umin)
1809 }
1810 return ft.newLimit(v, lim)
1811
1812 case OpPhi:
1813 {
1814
1815 b := v.Block
1816 if len(b.Preds) != 2 {
1817 goto notMinNorMax
1818 }
1819
1820
1821
1822
1823
1824
1825
1826
1827 firstBlock, secondBlock := b.Preds[0].b, b.Preds[1].b
1828 if firstBlock.Kind != BlockPlain || secondBlock.Kind != BlockPlain {
1829 goto notMinNorMax
1830 }
1831 if len(firstBlock.Preds) != 1 || len(secondBlock.Preds) != 1 {
1832 goto notMinNorMax
1833 }
1834 conditionBlock := firstBlock.Preds[0].b
1835 if conditionBlock != secondBlock.Preds[0].b {
1836 goto notMinNorMax
1837 }
1838 if conditionBlock.Kind != BlockIf {
1839 goto notMinNorMax
1840 }
1841
1842 less := conditionBlock.Controls[0]
1843 var unsigned bool
1844 switch less.Op {
1845 case OpLess64U, OpLess32U, OpLess16U, OpLess8U,
1846 OpLeq64U, OpLeq32U, OpLeq16U, OpLeq8U:
1847 unsigned = true
1848 case OpLess64, OpLess32, OpLess16, OpLess8,
1849 OpLeq64, OpLeq32, OpLeq16, OpLeq8:
1850 default:
1851 goto notMinNorMax
1852 }
1853 small, big := less.Args[0], less.Args[1]
1854 truev, falsev := v.Args[0], v.Args[1]
1855 if conditionBlock.Succs[0].b == secondBlock {
1856 truev, falsev = falsev, truev
1857 }
1858
1859 bigl, smalll := ft.limits[big.ID], ft.limits[small.ID]
1860 if truev == big {
1861 if falsev == small {
1862
1863 if unsigned {
1864 maximum := max(bigl.umax, smalll.umax)
1865 minimum := max(bigl.umin, smalll.umin)
1866 return ft.unsignedMinMax(v, minimum, maximum)
1867 } else {
1868 maximum := max(bigl.max, smalll.max)
1869 minimum := max(bigl.min, smalll.min)
1870 return ft.signedMinMax(v, minimum, maximum)
1871 }
1872 } else {
1873 goto notMinNorMax
1874 }
1875 } else if truev == small {
1876 if falsev == big {
1877
1878 if unsigned {
1879 maximum := min(bigl.umax, smalll.umax)
1880 minimum := min(bigl.umin, smalll.umin)
1881 return ft.unsignedMinMax(v, minimum, maximum)
1882 } else {
1883 maximum := min(bigl.max, smalll.max)
1884 minimum := min(bigl.min, smalll.min)
1885 return ft.signedMinMax(v, minimum, maximum)
1886 }
1887 } else {
1888 goto notMinNorMax
1889 }
1890 } else {
1891 goto notMinNorMax
1892 }
1893 }
1894 notMinNorMax:
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905 l := ft.limits[v.Args[0].ID]
1906 for _, a := range v.Args[1:] {
1907 l2 := ft.limits[a.ID]
1908 l.min = min(l.min, l2.min)
1909 l.max = max(l.max, l2.max)
1910 l.umin = min(l.umin, l2.umin)
1911 l.umax = max(l.umax, l2.umax)
1912 }
1913 return ft.newLimit(v, l)
1914 }
1915 return false
1916 }
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936 func (ft *factsTable) detectSignedMod(v *Value) bool {
1937 if ft.detectSignedModByPowerOfTwo(v) {
1938 return true
1939 }
1940
1941 return false
1942 }
1943 func (ft *factsTable) detectSignedModByPowerOfTwo(v *Value) bool {
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957 var w int64
1958 var addOp, andOp, constOp, sshiftOp, ushiftOp Op
1959 switch v.Op {
1960 case OpSub64:
1961 w = 64
1962 addOp = OpAdd64
1963 andOp = OpAnd64
1964 constOp = OpConst64
1965 sshiftOp = OpRsh64x64
1966 ushiftOp = OpRsh64Ux64
1967 case OpSub32:
1968 w = 32
1969 addOp = OpAdd32
1970 andOp = OpAnd32
1971 constOp = OpConst32
1972 sshiftOp = OpRsh32x64
1973 ushiftOp = OpRsh32Ux64
1974 case OpSub16:
1975 w = 16
1976 addOp = OpAdd16
1977 andOp = OpAnd16
1978 constOp = OpConst16
1979 sshiftOp = OpRsh16x64
1980 ushiftOp = OpRsh16Ux64
1981 case OpSub8:
1982 w = 8
1983 addOp = OpAdd8
1984 andOp = OpAnd8
1985 constOp = OpConst8
1986 sshiftOp = OpRsh8x64
1987 ushiftOp = OpRsh8Ux64
1988 default:
1989 return false
1990 }
1991
1992 x := v.Args[0]
1993 and := v.Args[1]
1994 if and.Op != andOp {
1995 return false
1996 }
1997 var add, mask *Value
1998 if and.Args[0].Op == addOp && and.Args[1].Op == constOp {
1999 add = and.Args[0]
2000 mask = and.Args[1]
2001 } else if and.Args[1].Op == addOp && and.Args[0].Op == constOp {
2002 add = and.Args[1]
2003 mask = and.Args[0]
2004 } else {
2005 return false
2006 }
2007 var ushift *Value
2008 if add.Args[0] == x {
2009 ushift = add.Args[1]
2010 } else if add.Args[1] == x {
2011 ushift = add.Args[0]
2012 } else {
2013 return false
2014 }
2015 if ushift.Op != ushiftOp {
2016 return false
2017 }
2018 if ushift.Args[1].Op != OpConst64 {
2019 return false
2020 }
2021 k := w - ushift.Args[1].AuxInt
2022 d := int64(1) << k
2023 sshift := ushift.Args[0]
2024 if sshift.Op != sshiftOp {
2025 return false
2026 }
2027 if sshift.Args[0] != x {
2028 return false
2029 }
2030 if sshift.Args[1].Op != OpConst64 || sshift.Args[1].AuxInt != w-1 {
2031 return false
2032 }
2033 if mask.AuxInt != -d {
2034 return false
2035 }
2036
2037
2038 return ft.signedMinMax(v, -d+1, d-1)
2039 }
2040
2041
2042
2043 func getBranch(sdom SparseTree, p *Block, b *Block) branch {
2044 if p == nil {
2045 return unknown
2046 }
2047 switch p.Kind {
2048 case BlockIf:
2049
2050
2051
2052
2053
2054
2055 if sdom.IsAncestorEq(p.Succs[0].b, b) && len(p.Succs[0].b.Preds) == 1 {
2056 return positive
2057 }
2058 if sdom.IsAncestorEq(p.Succs[1].b, b) && len(p.Succs[1].b.Preds) == 1 {
2059 return negative
2060 }
2061 case BlockJumpTable:
2062
2063
2064 for i, e := range p.Succs {
2065 if sdom.IsAncestorEq(e.b, b) && len(e.b.Preds) == 1 {
2066 return jumpTable0 + branch(i)
2067 }
2068 }
2069 }
2070 return unknown
2071 }
2072
2073
2074
2075
2076 func addIndVarRestrictions(ft *factsTable, b *Block, iv indVar) {
2077 d := signed
2078 if ft.isNonNegative(iv.min) && ft.isNonNegative(iv.max) {
2079 d |= unsigned
2080 }
2081
2082 if iv.flags&indVarMinExc == 0 {
2083 addRestrictions(b, ft, d, iv.min, iv.ind, lt|eq)
2084 } else {
2085 addRestrictions(b, ft, d, iv.min, iv.ind, lt)
2086 }
2087
2088 if iv.flags&indVarMaxInc == 0 {
2089 addRestrictions(b, ft, d, iv.ind, iv.max, lt)
2090 } else {
2091 addRestrictions(b, ft, d, iv.ind, iv.max, lt|eq)
2092 }
2093 }
2094
2095
2096
2097 func addBranchRestrictions(ft *factsTable, b *Block, br branch) {
2098 c := b.Controls[0]
2099 switch {
2100 case br == negative:
2101 ft.booleanFalse(c)
2102 case br == positive:
2103 ft.booleanTrue(c)
2104 case br >= jumpTable0:
2105 idx := br - jumpTable0
2106 val := int64(idx)
2107 if v, off := isConstDelta(c); v != nil {
2108
2109
2110 c = v
2111 val -= off
2112 }
2113 ft.newLimit(c, limit{min: val, max: val, umin: uint64(val), umax: uint64(val)})
2114 default:
2115 panic("unknown branch")
2116 }
2117 }
2118
2119
2120
2121 func addRestrictions(parent *Block, ft *factsTable, t domain, v, w *Value, r relation) {
2122 if t == 0 {
2123
2124
2125 return
2126 }
2127 for i := domain(1); i <= t; i <<= 1 {
2128 if t&i == 0 {
2129 continue
2130 }
2131 ft.update(parent, v, w, i, r)
2132 }
2133 }
2134
2135 func addLocalFacts(ft *factsTable, b *Block) {
2136
2137
2138
2139 for {
2140 changed := false
2141 for _, v := range b.Values {
2142 changed = ft.flowLimit(v) || changed
2143 }
2144 if !changed {
2145 break
2146 }
2147 }
2148
2149
2150 for _, v := range b.Values {
2151
2152
2153 switch v.Op {
2154 case OpAnd64, OpAnd32, OpAnd16, OpAnd8:
2155 ft.update(b, v, v.Args[0], unsigned, lt|eq)
2156 ft.update(b, v, v.Args[1], unsigned, lt|eq)
2157 if ft.isNonNegative(v.Args[0]) {
2158 ft.update(b, v, v.Args[0], signed, lt|eq)
2159 }
2160 if ft.isNonNegative(v.Args[1]) {
2161 ft.update(b, v, v.Args[1], signed, lt|eq)
2162 }
2163 case OpOr64, OpOr32, OpOr16, OpOr8:
2164
2165
2166
2167 case OpDiv64u, OpDiv32u, OpDiv16u, OpDiv8u,
2168 OpRsh8Ux64, OpRsh8Ux32, OpRsh8Ux16, OpRsh8Ux8,
2169 OpRsh16Ux64, OpRsh16Ux32, OpRsh16Ux16, OpRsh16Ux8,
2170 OpRsh32Ux64, OpRsh32Ux32, OpRsh32Ux16, OpRsh32Ux8,
2171 OpRsh64Ux64, OpRsh64Ux32, OpRsh64Ux16, OpRsh64Ux8:
2172 ft.update(b, v, v.Args[0], unsigned, lt|eq)
2173 case OpMod64u, OpMod32u, OpMod16u, OpMod8u:
2174 ft.update(b, v, v.Args[0], unsigned, lt|eq)
2175
2176
2177
2178
2179 ft.update(b, v, v.Args[1], unsigned, lt)
2180 case OpSliceLen:
2181 if v.Args[0].Op == OpSliceMake {
2182 ft.update(b, v, v.Args[0].Args[1], signed, eq)
2183 }
2184 case OpSliceCap:
2185 if v.Args[0].Op == OpSliceMake {
2186 ft.update(b, v, v.Args[0].Args[2], signed, eq)
2187 }
2188 case OpPhi:
2189 addLocalFactsPhi(ft, v)
2190 }
2191 }
2192 }
2193
2194 func addLocalFactsPhi(ft *factsTable, v *Value) {
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209 if len(v.Args) != 2 {
2210 return
2211 }
2212 b := v.Block
2213 x := v.Args[0]
2214 y := v.Args[1]
2215 bx := b.Preds[0].b
2216 by := b.Preds[1].b
2217 var z *Block
2218 switch {
2219 case bx == by:
2220 z = bx
2221 case by.uniquePred() == bx:
2222 z = bx
2223 case bx.uniquePred() == by:
2224 z = by
2225 case bx.uniquePred() == by.uniquePred():
2226 z = bx.uniquePred()
2227 }
2228 if z == nil || z.Kind != BlockIf {
2229 return
2230 }
2231 c := z.Controls[0]
2232 if len(c.Args) != 2 {
2233 return
2234 }
2235 var isMin bool
2236 if bx == z {
2237 isMin = b.Preds[0].i == 0
2238 } else {
2239 isMin = bx.Preds[0].i == 0
2240 }
2241 if c.Args[0] == x && c.Args[1] == y {
2242
2243 } else if c.Args[0] == y && c.Args[1] == x {
2244
2245 isMin = !isMin
2246 } else {
2247
2248 return
2249 }
2250 var dom domain
2251 switch c.Op {
2252 case OpLess64, OpLess32, OpLess16, OpLess8, OpLeq64, OpLeq32, OpLeq16, OpLeq8:
2253 dom = signed
2254 case OpLess64U, OpLess32U, OpLess16U, OpLess8U, OpLeq64U, OpLeq32U, OpLeq16U, OpLeq8U:
2255 dom = unsigned
2256 default:
2257 return
2258 }
2259 var rel relation
2260 if isMin {
2261 rel = lt | eq
2262 } else {
2263 rel = gt | eq
2264 }
2265 ft.update(b, v, x, dom, rel)
2266 ft.update(b, v, y, dom, rel)
2267 }
2268
2269 var ctzNonZeroOp = map[Op]Op{OpCtz8: OpCtz8NonZero, OpCtz16: OpCtz16NonZero, OpCtz32: OpCtz32NonZero, OpCtz64: OpCtz64NonZero}
2270 var mostNegativeDividend = map[Op]int64{
2271 OpDiv16: -1 << 15,
2272 OpMod16: -1 << 15,
2273 OpDiv32: -1 << 31,
2274 OpMod32: -1 << 31,
2275 OpDiv64: -1 << 63,
2276 OpMod64: -1 << 63}
2277
2278
2279
2280 func simplifyBlock(sdom SparseTree, ft *factsTable, b *Block) {
2281 for _, v := range b.Values {
2282 switch v.Op {
2283 case OpSlicemask:
2284
2285 x, delta := isConstDelta(v.Args[0])
2286 if x == nil {
2287 break
2288 }
2289
2290
2291 lim := ft.limits[x.ID]
2292 if lim.umin > uint64(-delta) {
2293 if v.Args[0].Op == OpAdd64 {
2294 v.reset(OpConst64)
2295 } else {
2296 v.reset(OpConst32)
2297 }
2298 if b.Func.pass.debug > 0 {
2299 b.Func.Warnl(v.Pos, "Proved slicemask not needed")
2300 }
2301 v.AuxInt = -1
2302 }
2303 case OpCtz8, OpCtz16, OpCtz32, OpCtz64:
2304
2305
2306
2307 x := v.Args[0]
2308 lim := ft.limits[x.ID]
2309 if lim.umin > 0 || lim.min > 0 || lim.max < 0 {
2310 if b.Func.pass.debug > 0 {
2311 b.Func.Warnl(v.Pos, "Proved %v non-zero", v.Op)
2312 }
2313 v.Op = ctzNonZeroOp[v.Op]
2314 }
2315 case OpRsh8x8, OpRsh8x16, OpRsh8x32, OpRsh8x64,
2316 OpRsh16x8, OpRsh16x16, OpRsh16x32, OpRsh16x64,
2317 OpRsh32x8, OpRsh32x16, OpRsh32x32, OpRsh32x64,
2318 OpRsh64x8, OpRsh64x16, OpRsh64x32, OpRsh64x64:
2319
2320
2321 bits := 8 * v.Args[0].Type.Size()
2322 if v.Args[1].isGenericIntConst() && v.Args[1].AuxInt >= bits-1 && ft.isNonNegative(v.Args[0]) {
2323 if b.Func.pass.debug > 0 {
2324 b.Func.Warnl(v.Pos, "Proved %v shifts to zero", v.Op)
2325 }
2326 switch bits {
2327 case 64:
2328 v.reset(OpConst64)
2329 case 32:
2330 v.reset(OpConst32)
2331 case 16:
2332 v.reset(OpConst16)
2333 case 8:
2334 v.reset(OpConst8)
2335 default:
2336 panic("unexpected integer size")
2337 }
2338 v.AuxInt = 0
2339 break
2340 }
2341
2342 fallthrough
2343 case OpLsh8x8, OpLsh8x16, OpLsh8x32, OpLsh8x64,
2344 OpLsh16x8, OpLsh16x16, OpLsh16x32, OpLsh16x64,
2345 OpLsh32x8, OpLsh32x16, OpLsh32x32, OpLsh32x64,
2346 OpLsh64x8, OpLsh64x16, OpLsh64x32, OpLsh64x64,
2347 OpRsh8Ux8, OpRsh8Ux16, OpRsh8Ux32, OpRsh8Ux64,
2348 OpRsh16Ux8, OpRsh16Ux16, OpRsh16Ux32, OpRsh16Ux64,
2349 OpRsh32Ux8, OpRsh32Ux16, OpRsh32Ux32, OpRsh32Ux64,
2350 OpRsh64Ux8, OpRsh64Ux16, OpRsh64Ux32, OpRsh64Ux64:
2351
2352
2353 by := v.Args[1]
2354 lim := ft.limits[by.ID]
2355 bits := 8 * v.Args[0].Type.Size()
2356 if lim.umax < uint64(bits) || (lim.max < bits && ft.isNonNegative(by)) {
2357 v.AuxInt = 1
2358 if b.Func.pass.debug > 0 && !by.isGenericIntConst() {
2359 b.Func.Warnl(v.Pos, "Proved %v bounded", v.Op)
2360 }
2361 }
2362 case OpDiv16, OpDiv32, OpDiv64, OpMod16, OpMod32, OpMod64:
2363
2364
2365
2366
2367
2368 if b.Func.Config.arch != "386" && b.Func.Config.arch != "amd64" {
2369 break
2370 }
2371 divr := v.Args[1]
2372 divrLim := ft.limits[divr.ID]
2373 divd := v.Args[0]
2374 divdLim := ft.limits[divd.ID]
2375 if divrLim.max < -1 || divrLim.min > -1 || divdLim.min > mostNegativeDividend[v.Op] {
2376
2377
2378
2379
2380 v.AuxInt = 1
2381 if b.Func.pass.debug > 0 {
2382 b.Func.Warnl(v.Pos, "Proved %v does not need fix-up", v.Op)
2383 }
2384 }
2385 }
2386
2387
2388 for i, arg := range v.Args {
2389 lim := ft.limits[arg.ID]
2390 var constValue int64
2391 switch {
2392 case lim.min == lim.max:
2393 constValue = lim.min
2394 case lim.umin == lim.umax:
2395 constValue = int64(lim.umin)
2396 default:
2397 continue
2398 }
2399 switch arg.Op {
2400 case OpConst64, OpConst32, OpConst16, OpConst8, OpConstBool, OpConstNil:
2401 continue
2402 }
2403 typ := arg.Type
2404 f := b.Func
2405 var c *Value
2406 switch {
2407 case typ.IsBoolean():
2408 c = f.ConstBool(typ, constValue != 0)
2409 case typ.IsInteger() && typ.Size() == 1:
2410 c = f.ConstInt8(typ, int8(constValue))
2411 case typ.IsInteger() && typ.Size() == 2:
2412 c = f.ConstInt16(typ, int16(constValue))
2413 case typ.IsInteger() && typ.Size() == 4:
2414 c = f.ConstInt32(typ, int32(constValue))
2415 case typ.IsInteger() && typ.Size() == 8:
2416 c = f.ConstInt64(typ, constValue)
2417 case typ.IsPtrShaped():
2418 if constValue == 0 {
2419 c = f.ConstNil(typ)
2420 } else {
2421
2422
2423 continue
2424 }
2425 default:
2426
2427
2428 continue
2429 }
2430 v.SetArg(i, c)
2431 ft.initLimitForNewValue(c)
2432 if b.Func.pass.debug > 1 {
2433 b.Func.Warnl(v.Pos, "Proved %v's arg %d (%v) is constant %d", v, i, arg, constValue)
2434 }
2435 }
2436 }
2437
2438 if b.Kind != BlockIf {
2439 return
2440 }
2441
2442
2443 parent := b
2444 for i, branch := range [...]branch{positive, negative} {
2445 child := parent.Succs[i].b
2446 if getBranch(sdom, parent, child) != unknown {
2447
2448
2449 continue
2450 }
2451
2452
2453 ft.checkpoint()
2454 addBranchRestrictions(ft, parent, branch)
2455 unsat := ft.unsat
2456 ft.restore()
2457 if unsat {
2458
2459
2460 removeBranch(parent, branch)
2461
2462
2463
2464
2465
2466 break
2467 }
2468 }
2469 }
2470
2471 func removeBranch(b *Block, branch branch) {
2472 c := b.Controls[0]
2473 if b.Func.pass.debug > 0 {
2474 verb := "Proved"
2475 if branch == positive {
2476 verb = "Disproved"
2477 }
2478 if b.Func.pass.debug > 1 {
2479 b.Func.Warnl(b.Pos, "%s %s (%s)", verb, c.Op, c)
2480 } else {
2481 b.Func.Warnl(b.Pos, "%s %s", verb, c.Op)
2482 }
2483 }
2484 if c != nil && c.Pos.IsStmt() == src.PosIsStmt && c.Pos.SameFileAndLine(b.Pos) {
2485
2486 b.Pos = b.Pos.WithIsStmt()
2487 }
2488 if branch == positive || branch == negative {
2489 b.Kind = BlockFirst
2490 b.ResetControls()
2491 if branch == positive {
2492 b.swapSuccessors()
2493 }
2494 } else {
2495
2496 }
2497 }
2498
2499
2500 func isConstDelta(v *Value) (w *Value, delta int64) {
2501 cop := OpConst64
2502 switch v.Op {
2503 case OpAdd32, OpSub32:
2504 cop = OpConst32
2505 case OpAdd16, OpSub16:
2506 cop = OpConst16
2507 case OpAdd8, OpSub8:
2508 cop = OpConst8
2509 }
2510 switch v.Op {
2511 case OpAdd64, OpAdd32, OpAdd16, OpAdd8:
2512 if v.Args[0].Op == cop {
2513 return v.Args[1], v.Args[0].AuxInt
2514 }
2515 if v.Args[1].Op == cop {
2516 return v.Args[0], v.Args[1].AuxInt
2517 }
2518 case OpSub64, OpSub32, OpSub16, OpSub8:
2519 if v.Args[1].Op == cop {
2520 aux := v.Args[1].AuxInt
2521 if aux != -aux {
2522 return v.Args[0], -aux
2523 }
2524 }
2525 }
2526 return nil, 0
2527 }
2528
2529
2530
2531 func isCleanExt(v *Value) bool {
2532 switch v.Op {
2533 case OpSignExt8to16, OpSignExt8to32, OpSignExt8to64,
2534 OpSignExt16to32, OpSignExt16to64, OpSignExt32to64:
2535
2536 return v.Args[0].Type.IsSigned() && v.Type.IsSigned()
2537
2538 case OpZeroExt8to16, OpZeroExt8to32, OpZeroExt8to64,
2539 OpZeroExt16to32, OpZeroExt16to64, OpZeroExt32to64:
2540
2541 return !v.Args[0].Type.IsSigned()
2542 }
2543 return false
2544 }
2545
View as plain text