llvm/test/Analysis/HashRecognize/def-use-chains-visited.ll

; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 5
; RUN: opt -passes='print<hash-recognize>' -disable-output %s 2>&1 | FileCheck %s

; This loop hangs if digRecurrence doesn't keep track of previously visited
; instructions since most instructions have multiple uses.
define float @digRecurrence_visited(float %a, float %b) {
; CHECK-LABEL: 'digRecurrence_visited'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Unable to find conditional recurrence
;
entry:
  ; %f must be the result of an instruction in order for digRecurrence to be
  ; called from matchConditionalRecurrence.
  %f = fneg float %a
  br label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
  %ind = phi float [ %b, %entry ], [ %ind.next, %loop ]
  %fcmp = fcmp une float %ind, 0.0
  %select = select i1 %fcmp, float %f, float %ind
  %fcmp3 = fcmp une float %select, 0.0
  %select4 = select i1 %fcmp3, float %f, float %select
  %fcmp5 = fcmp une float %select4, 0.0
  %select6 = select i1 %fcmp5, float %f, float %select4
  %fcmp7 = fcmp une float %select6, 0.0
  %select8 = select i1 %fcmp7, float %f, float %select6
  %fcmp9 = fcmp une float %select8, 0.0
  %select10 = select i1 %fcmp9, float %f, float %select8
  %fcmp11 = fcmp une float %select10, 0.0
  %select12 = select i1 %fcmp11, float %f, float %select10
  %fcmp13 = fcmp une float %select12, 0.0
  %select14 = select i1 %fcmp13, float %f, float %select12
  %fcmp15 = fcmp une float %select14, 0.0
  %select16 = select i1 %fcmp15, float %f, float %select14
  %fcmp17 = fcmp une float %select16, 0.0
  %select18 = select i1 %fcmp17, float %f, float %select16
  %fcmp19 = fcmp une float %select18, 0.0
  %select20 = select i1 %fcmp19, float %f, float %select18
  %fcmp21 = fcmp une float %select20, 0.0
  %select22 = select i1 %fcmp21, float %f, float %select20
  %fcmp23 = fcmp une float %select22, 0.0
  %select24 = select i1 %fcmp23, float %f, float %select22
  %fcmp25 = fcmp une float %select24, 0.0
  %select26 = select i1 %fcmp25, float %f, float %select24
  %fcmp27 = fcmp une float %select26, 0.0
  %select28 = select i1 %fcmp27, float %f, float %select26
  %fcmp29 = fcmp une float %select28, 0.0
  %select30 = select i1 %fcmp29, float %f, float %select28
  %fcmp31 = fcmp une float %select30, 0.0
  %select32 = select i1 %fcmp31, float %f, float %select30
  %fcmp33 = fcmp une float %select32, 0.0
  %select34 = select i1 %fcmp33, float %f, float %select32
  %fcmp35 = fcmp une float %select34, 0.0
  %select36 = select i1 %fcmp35, float %f, float %select34
  %fcmp37 = fcmp une float %select36, 0.0
  %select38 = select i1 %fcmp37, float %f, float %select36
  %fcmp39 = fcmp une float %select38, 0.0
  %select40 = select i1 %fcmp39, float %f, float %select38
  %fcmp41 = fcmp une float %select40, 0.0
  %select42 = select i1 %fcmp41, float %f, float %select40
  %fcmp43 = fcmp une float %select42, 0.0
  %select44 = select i1 %fcmp43, float %f, float %select42
  %fcmp45 = fcmp une float %select44, 0.0
  %select46 = select i1 %fcmp45, float %f, float %select44
  %fcmp47 = fcmp une float %select46, 0.0
  %select48 = select i1 %fcmp47, float %f, float %select46
  %fcmp49 = fcmp une float %select48, 0.0
  %select50 = select i1 %fcmp49, float %f, float %select48
  %fcmp51 = fcmp une float %select50, 0.0
  %select52 = select i1 %fcmp51, float %f, float %select50
  %fcmp53 = fcmp une float %select52, 0.0
  %select54 = select i1 %fcmp53, float %f, float %select52
  %fcmp55 = fcmp une float %select54, 0.0
  %select56 = select i1 %fcmp55, float %f, float %select54
  %fcmp57 = fcmp une float %select56, 0.0
  %select58 = select i1 %fcmp57, float %f, float %select56
  %fcmp59 = fcmp une float %select58, 0.0
  %select60 = select i1 %fcmp59, float %f, float %select58
  %fcmp61 = fcmp une float %select60, 0.0
  %select62 = select i1 %fcmp61, float %f, float %select60
  %fcmp63 = fcmp une float %select62, 0.0
  %select64 = select i1 %fcmp63, float %f, float %select62
  %fcmp65 = fcmp une float %select64, 0.0
  %select66 = select i1 %fcmp65, float %f, float %select64
  %fcmp67 = fcmp une float %select66, 0.0
  %select68 = select i1 %fcmp67, float %f, float %select66
  %fcmp69 = fcmp une float %select68, 0.0
  %select70 = select i1 %fcmp69, float %f, float %select68
  %fcmp71 = fcmp une float %select70, 0.0
  %select72 = select i1 %fcmp71, float %f, float %select70
  %fcmp73 = fcmp une float %select72, 0.0
  %select74 = select i1 %fcmp73, float %f, float %select72
  %fcmp75 = fcmp une float %select74, 0.0
  %select76 = select i1 %fcmp75, float %f, float %select74
  %fcmp77 = fcmp une float %select76, 0.0
  %select78 = select i1 %fcmp77, float %f, float %select76
  %fcmp79 = fcmp une float %select78, 0.0
  %select80 = select i1 %fcmp79, float %f, float %select78
  %fcmp81 = fcmp une float %select80, 0.0
  %select82 = select i1 %fcmp81, float %f, float %select80
  %fcmp83 = fcmp une float %select82, 0.0
  %select84 = select i1 %fcmp83, float %f, float %select82
  %fcmp85 = fcmp une float %select84, 0.0
  %select86 = select i1 %fcmp85, float %f, float %select84
  %fcmp87 = fcmp une float %select86, 0.0
  %select88 = select i1 %fcmp87, float %f, float %select86
  %fcmp89 = fcmp une float %select88, 0.0
  %select90 = select i1 %fcmp89, float %f, float %select88
  %fcmp91 = fcmp une float %select90, 0.0
  %select92 = select i1 %fcmp91, float %f, float %select90
  %fcmp93 = fcmp une float %select92, 0.0
  %select94 = select i1 %fcmp93, float %f, float %select92
  %fcmp95 = fcmp une float %select94, 0.0
  %select96 = select i1 %fcmp95, float %f, float %select94
  %fcmp97 = fcmp une float %select96, 0.0
  %select98 = select i1 %fcmp97, float %f, float %select96
  %fcmp99 = fcmp une float %select98, 0.0
  %select100 = select i1 %fcmp99, float %f, float %select98
  %fcmp101 = fcmp une float %select100, 0.0
  %select102 = select i1 %fcmp101, float %f, float %select100
  %fcmp103 = fcmp une float %select102, 0.0
  %select104 = select i1 %fcmp103, float %f, float %select102
  %fcmp105 = fcmp une float %select104, 0.0
  %select106 = select i1 %fcmp105, float %f, float %select104
  %fcmp107 = fcmp une float %select106, 0.0
  %select108 = select i1 %fcmp107, float %f, float %select106
  %fcmp109 = fcmp une float %select108, 0.0
  %select110 = select i1 %fcmp109, float %f, float %select108
  %fcmp111 = fcmp une float %select110, 0.0
  %select112 = select i1 %fcmp111, float %f, float %select110
  %fcmp113 = fcmp une float %select112, 0.0
  %select114 = select i1 %fcmp113, float %f, float %select112
  %fcmp115 = fcmp une float %select114, 0.0
  %select116 = select i1 %fcmp115, float %f, float %select114
  %fcmp117 = fcmp une float %select116, 0.0
  %select118 = select i1 %fcmp117, float %f, float %select116
  %fcmp119 = fcmp une float %select118, 0.0
  %select120 = select i1 %fcmp119, float %f, float %select118
  %fcmp121 = fcmp une float %select120, 0.0
  %select122 = select i1 %fcmp121, float %f, float %select120
  %fcmp123 = fcmp une float %select122, 0.0
  %select124 = select i1 %fcmp123, float %f, float %select122
  %fcmp125 = fcmp une float %select124, 0.0
  %select126 = select i1 %fcmp125, float %f, float %select124
  %fcmp127 = fcmp une float %select126, 0.0
  %select128 = select i1 %fcmp127, float %f, float %select126
  %fcmp129 = fcmp une float %select128, 0.0
  %select130 = select i1 %fcmp129, float %f, float %select128
  %fcmp131 = fcmp une float %select130, 0.0
  %select132 = select i1 %fcmp131, float %f, float %select130
  %fcmp133 = fcmp une float %select132, 0.0
  %select134 = select i1 %fcmp133, float %f, float %select132
  %fcmp135 = fcmp une float %select134, 0.0
  %select136 = select i1 %fcmp135, float %f, float %select134
  %fcmp137 = fcmp une float %select136, 0.0
  %select138 = select i1 %fcmp137, float %f, float %select136
  %fcmp139 = fcmp une float %select138, 0.0
  %select140 = select i1 %fcmp139, float %f, float %select138
  %fcmp141 = fcmp une float %select140, 0.0
  %select142 = select i1 %fcmp141, float %f, float %select140
  %fcmp143 = fcmp une float %select142, 0.0
  %ind.next = select i1 %fcmp143, float %f, float %select142
  %iv.next = add nuw nsw i32 %iv, 1
  %exit.cond = icmp eq i32 %iv.next, 8
  br i1 %exit.cond, label %exit, label %loop

exit:
  %lcssa.phi = phi float [ %ind.next, %loop ]
  ret float %lcssa.phi
}

; This loop hangs if isConditionalOnXorOfPHIs doesn't keep track of previously
; visited instructions since most instructions have multiple uses.
define i16 @isConditionalOnXorOfPHIs_visited(i16 %crc.init, i16 %data.init) {
; CHECK-LABEL: 'isConditionalOnXorOfPHIs_visited'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Recurrences not intertwined with XOR
;
entry:
  br label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
  %crc = phi i16 [ %crc.init, %entry ], [ %crc.next, %loop ]
  %data = phi i16 [ %data.init, %entry ], [ %data.shl, %loop ]
  %data.shl = shl i16 %data, 1
  %crc.shl = shl i16 %crc, 1
  %crc.xor = xor i16 %crc.shl, 4129
  %d0 = and i16 %crc, %data
  %e1 = add i16 %d0, 1
  %d1 = mul i16 %e1, %d0
  %e2 = add i16 %d1, 1
  %d2 = mul i16 %e2, %d1
  %e3 = add i16 %d2, 1
  %d3 = mul i16 %e3, %d2
  %e4 = add i16 %d3, 1
  %d4 = mul i16 %e4, %d3
  %e5 = add i16 %d4, 1
  %d5 = mul i16 %e5, %d4
  %e6 = add i16 %d5, 1
  %d6 = mul i16 %e6, %d5
  %e7 = add i16 %d6, 1
  %d7 = mul i16 %e7, %d6
  %e8 = add i16 %d7, 1
  %d8 = mul i16 %e8, %d7
  %e9 = add i16 %d8, 1
  %d9 = mul i16 %e9, %d8
  %e10 = add i16 %d9, 1
  %d10 = mul i16 %e10, %d9
  %e11 = add i16 %d10, 1
  %d11 = mul i16 %e11, %d10
  %e12 = add i16 %d11, 1
  %d12 = mul i16 %e12, %d11
  %e13 = add i16 %d12, 1
  %d13 = mul i16 %e13, %d12
  %e14 = add i16 %d13, 1
  %d14 = mul i16 %e14, %d13
  %e15 = add i16 %d14, 1
  %d15 = mul i16 %e15, %d14
  %e16 = add i16 %d15, 1
  %d16 = mul i16 %e16, %d15
  %e17 = add i16 %d16, 1
  %d17 = mul i16 %e17, %d16
  %e18 = add i16 %d17, 1
  %d18 = mul i16 %e18, %d17
  %e19 = add i16 %d18, 1
  %d19 = mul i16 %e19, %d18
  %e20 = add i16 %d19, 1
  %d20 = mul i16 %e20, %d19
  %e21 = add i16 %d20, 1
  %d21 = mul i16 %e21, %d20
  %e22 = add i16 %d21, 1
  %d22 = mul i16 %e22, %d21
  %e23 = add i16 %d22, 1
  %d23 = mul i16 %e23, %d22
  %e24 = add i16 %d23, 1
  %d24 = mul i16 %e24, %d23
  %e25 = add i16 %d24, 1
  %d25 = mul i16 %e25, %d24
  %e26 = add i16 %d25, 1
  %d26 = mul i16 %e26, %d25
  %e27 = add i16 %d26, 1
  %d27 = mul i16 %e27, %d26
  %e28 = add i16 %d27, 1
  %d28 = mul i16 %e28, %d27
  %e29 = add i16 %d28, 1
  %d29 = mul i16 %e29, %d28
  %e30 = add i16 %d29, 1
  %d30 = mul i16 %e30, %d29
  %e31 = add i16 %d30, 1
  %d31 = mul i16 %e31, %d30
  %e32 = add i16 %d31, 1
  %d32 = mul i16 %e32, %d31
  %e33 = add i16 %d32, 1
  %d33 = mul i16 %e33, %d32
  %e34 = add i16 %d33, 1
  %d34 = mul i16 %e34, %d33
  %e35 = add i16 %d34, 1
  %d35 = mul i16 %e35, %d34
  %e36 = add i16 %d35, 1
  %d36 = mul i16 %e36, %d35
  %e37 = add i16 %d36, 1
  %d37 = mul i16 %e37, %d36
  %e38 = add i16 %d37, 1
  %d38 = mul i16 %e38, %d37
  %e39 = add i16 %d38, 1
  %d39 = mul i16 %e39, %d38
  %e40 = add i16 %d39, 1
  %d40 = mul i16 %e40, %d39
  %check.sb = icmp eq i16 %d40, 0
  %crc.next = select i1 %check.sb, i16 %crc.xor, i16 %crc.shl
  %iv.next = add nuw nsw i32 %iv, 1
  %exit.cond = icmp eq i32 %iv.next, 8
  br i1 %exit.cond, label %exit, label %loop

exit:
  ret i16 %crc.next
}

; This loop hangs if containsUnreachable doesn't keep track of previously
; visited instructions since most instructions have multiple uses.
define i16 @containsUnreachable_visited(i16 %crc.init) {
; CHECK-LABEL: 'containsUnreachable_visited'
; CHECK-NEXT:  Found big-endian CRC-16 loop with trip count 8
; CHECK-NEXT:    Initial CRC: i16 %crc.init
; CHECK-NEXT:    Generating polynomial: 4129
; CHECK-NEXT:    Computed CRC: %crc.next = select i1 %check.sb, i16 %crc.xor, i16 %crc.shl
; CHECK-NEXT:    Computed CRC lookup table:
; CHECK-NEXT:  0 4129 8258 12387 16516 20645 24774 28903 33032 37161 41290 45419 49548 53677 57806 61935
; CHECK-NEXT:  4657 528 12915 8786 21173 17044 29431 25302 37689 33560 45947 41818 54205 50076 62463 58334
; CHECK-NEXT:  9314 13379 1056 5121 25830 29895 17572 21637 42346 46411 34088 38153 58862 62927 50604 54669
; CHECK-NEXT:  13907 9842 5649 1584 30423 26358 22165 18100 46939 42874 38681 34616 63455 59390 55197 51132
; CHECK-NEXT:  18628 22757 26758 30887 2112 6241 10242 14371 51660 55789 59790 63919 35144 39273 43274 47403
; CHECK-NEXT:  23285 19156 31415 27286 6769 2640 14899 10770 56317 52188 64447 60318 39801 35672 47931 43802
; CHECK-NEXT:  27814 31879 19684 23749 11298 15363 3168 7233 60846 64911 52716 56781 44330 48395 36200 40265
; CHECK-NEXT:  32407 28342 24277 20212 15891 11826 7761 3696 65439 61374 57309 53244 48923 44858 40793 36728
; CHECK-NEXT:  37256 33193 45514 41451 53516 49453 61774 57711 4224 161 12482 8419 20484 16421 28742 24679
; CHECK-NEXT:  33721 37784 41979 46042 49981 54044 58239 62302 689 4752 8947 13010 16949 21012 25207 29270
; CHECK-NEXT:  46570 42443 38312 34185 62830 58703 54572 50445 13538 9411 5280 1153 29798 25671 21540 17413
; CHECK-NEXT:  42971 47098 34713 38840 59231 63358 50973 55100 9939 14066 1681 5808 26199 30326 17941 22068
; CHECK-NEXT:  55628 51565 63758 59695 39368 35305 47498 43435 22596 18533 30726 26663 6336 2273 14466 10403
; CHECK-NEXT:  52093 56156 60223 64286 35833 39896 43963 48026 19061 23124 27191 31254 2801 6864 10931 14994
; CHECK-NEXT:  64814 60687 56684 52557 48554 44427 40424 36297 31782 27655 23652 19525 15522 11395 7392 3265
; CHECK-NEXT:  61215 65342 53085 57212 44955 49082 36825 40952 28183 32310 20053 24180 11923 16050 3793 7920
; CHECK-NEXT:    Computed CRC Barrett constants:
; CHECK-NEXT:  Mu = 273, FullGenPoly = 69665
;
entry:
  br label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
  %crc = phi i16 [ %crc.init, %entry ], [ %crc.next, %loop ]
  %crc.shl = shl i16 %crc, 1
  %crc.xor = xor i16 %crc.shl, 4129
  %check.sb = icmp slt i16 %crc, 0
  %crc.next = select i1 %check.sb, i16 %crc.xor, i16 %crc.shl
  %iv.next = add nuw nsw i32 %iv, 1
  %d0 = mul i32 %iv, 1
  %e1 = mul i32 %d0, 1
  %f1 = sub i32 %d0, %d0
  %d1 = add i32 %e1, %f1
  %e2 = mul i32 %d1, 1
  %f2 = sub i32 %d1, %d1
  %d2 = add i32 %e2, %f2
  %e3 = mul i32 %d2, 1
  %f3 = sub i32 %d2, %d2
  %d3 = add i32 %e3, %f3
  %e4 = mul i32 %d3, 1
  %f4 = sub i32 %d3, %d3
  %d4 = add i32 %e4, %f4
  %e5 = mul i32 %d4, 1
  %f5 = sub i32 %d4, %d4
  %d5 = add i32 %e5, %f5
  %e6 = mul i32 %d5, 1
  %f6 = sub i32 %d5, %d5
  %d6 = add i32 %e6, %f6
  %e7 = mul i32 %d6, 1
  %f7 = sub i32 %d6, %d6
  %d7 = add i32 %e7, %f7
  %e8 = mul i32 %d7, 1
  %f8 = sub i32 %d7, %d7
  %d8 = add i32 %e8, %f8
  %e9 = mul i32 %d8, 1
  %f9 = sub i32 %d8, %d8
  %d9 = add i32 %e9, %f9
  %e10 = mul i32 %d9, 1
  %f10 = sub i32 %d9, %d9
  %d10 = add i32 %e10, %f10
  %e11 = mul i32 %d10, 1
  %f11 = sub i32 %d10, %d10
  %d11 = add i32 %e11, %f11
  %e12 = mul i32 %d11, 1
  %f12 = sub i32 %d11, %d11
  %d12 = add i32 %e12, %f12
  %e13 = mul i32 %d12, 1
  %f13 = sub i32 %d12, %d12
  %d13 = add i32 %e13, %f13
  %e14 = mul i32 %d13, 1
  %f14 = sub i32 %d13, %d13
  %d14 = add i32 %e14, %f14
  %e15 = mul i32 %d14, 1
  %f15 = sub i32 %d14, %d14
  %d15 = add i32 %e15, %f15
  %e16 = mul i32 %d15, 1
  %f16 = sub i32 %d15, %d15
  %d16 = add i32 %e16, %f16
  %e17 = mul i32 %d16, 1
  %f17 = sub i32 %d16, %d16
  %d17 = add i32 %e17, %f17
  %e18 = mul i32 %d17, 1
  %f18 = sub i32 %d17, %d17
  %d18 = add i32 %e18, %f18
  %e19 = mul i32 %d18, 1
  %f19 = sub i32 %d18, %d18
  %d19 = add i32 %e19, %f19
  %e20 = mul i32 %d19, 1
  %f20 = sub i32 %d19, %d19
  %d20 = add i32 %e20, %f20
  %e21 = mul i32 %d20, 1
  %f21 = sub i32 %d20, %d20
  %d21 = add i32 %e21, %f21
  %e22 = mul i32 %d21, 1
  %f22 = sub i32 %d21, %d21
  %d22 = add i32 %e22, %f22
  %e23 = mul i32 %d22, 1
  %f23 = sub i32 %d22, %d22
  %d23 = add i32 %e23, %f23
  %e24 = mul i32 %d23, 1
  %f24 = sub i32 %d23, %d23
  %d24 = add i32 %e24, %f24
  %e25 = mul i32 %d24, 1
  %f25 = sub i32 %d24, %d24
  %d25 = add i32 %e25, %f25
  %e26 = mul i32 %d25, 1
  %f26 = sub i32 %d25, %d25
  %d26 = add i32 %e26, %f26
  %e27 = mul i32 %d26, 1
  %f27 = sub i32 %d26, %d26
  %d27 = add i32 %e27, %f27
  %e28 = mul i32 %d27, 1
  %f28 = sub i32 %d27, %d27
  %d28 = add i32 %e28, %f28
  %e29 = mul i32 %d28, 1
  %f29 = sub i32 %d28, %d28
  %d29 = add i32 %e29, %f29
  %e30 = mul i32 %d29, 1
  %f30 = sub i32 %d29, %d29
  %d30 = add i32 %e30, %f30
  %exit.cond = icmp samesign ult i32 %d30, 7
  br i1 %exit.cond, label %loop, label %exit

exit:
  ret i16 %crc.next
}