File: cyclic-redundancy-check.ll

package info (click to toggle)
llvm-toolchain-21 1%3A21.1.6-3
links: PTS, VCS
area: main
in suites: forky, sid
size: 2,245,028 kB
sloc: cpp: 7,619,726; ansic: 1,434,018; asm: 1,058,748; python: 252,740; f90: 94,671; objc: 70,685; lisp: 42,813; pascal: 18,401; sh: 8,601; ml: 5,111; perl: 4,720; makefile: 3,675; awk: 3,523; javascript: 2,409; xml: 892; fortran: 770
file content (1191 lines) | stat: -rw-r--r-- 52,616 bytes
; 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

define i16 @crc16.le.tc8(i8 %msg, i16 %checksum) {
; CHECK-LABEL: 'crc16.le.tc8'
; CHECK-NEXT:  Found little-endian CRC-16 loop with trip count 8
; CHECK-NEXT:    Initial CRC: i16 %checksum
; CHECK-NEXT:    Generating polynomial: 40961
; CHECK-NEXT:    Computed CRC: %crc.next = select i1 %check.sb, i16 %crc.lshr, i16 %xor
; CHECK-NEXT:    Auxiliary data: i8 %msg
; CHECK-NEXT:    Computed CRC lookup table:
; CHECK-NEXT:  0 49345 49537 320 49921 960 640 49729 50689 1728 1920 51009 1280 50625 50305 1088
; CHECK-NEXT:  52225 3264 3456 52545 3840 53185 52865 3648 2560 51905 52097 2880 51457 2496 2176 51265
; CHECK-NEXT:  55297 6336 6528 55617 6912 56257 55937 6720 7680 57025 57217 8000 56577 7616 7296 56385
; CHECK-NEXT:  5120 54465 54657 5440 55041 6080 5760 54849 53761 4800 4992 54081 4352 53697 53377 4160
; CHECK-NEXT:  61441 12480 12672 61761 13056 62401 62081 12864 13824 63169 63361 14144 62721 13760 13440 62529
; CHECK-NEXT:  15360 64705 64897 15680 65281 16320 16000 65089 64001 15040 15232 64321 14592 63937 63617 14400
; CHECK-NEXT:  10240 59585 59777 10560 60161 11200 10880 59969 60929 11968 12160 61249 11520 60865 60545 11328
; CHECK-NEXT:  58369 9408 9600 58689 9984 59329 59009 9792 8704 58049 58241 9024 57601 8640 8320 57409
; CHECK-NEXT:  40961 24768 24960 41281 25344 41921 41601 25152 26112 42689 42881 26432 42241 26048 25728 42049
; CHECK-NEXT:  27648 44225 44417 27968 44801 28608 28288 44609 43521 27328 27520 43841 26880 43457 43137 26688
; CHECK-NEXT:  30720 47297 47489 31040 47873 31680 31360 47681 48641 32448 32640 48961 32000 48577 48257 31808
; CHECK-NEXT:  46081 29888 30080 46401 30464 47041 46721 30272 29184 45761 45953 29504 45313 29120 28800 45121
; CHECK-NEXT:  20480 37057 37249 20800 37633 21440 21120 37441 38401 22208 22400 38721 21760 38337 38017 21568
; CHECK-NEXT:  39937 23744 23936 40257 24320 40897 40577 24128 23040 39617 39809 23360 39169 22976 22656 38977
; CHECK-NEXT:  34817 18624 18816 35137 19200 35777 35457 19008 19968 36545 36737 20288 36097 19904 19584 35905
; CHECK-NEXT:  17408 33985 34177 17728 34561 18368 18048 34369 33281 17088 17280 33601 16640 33217 32897 16448
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %crc = phi i16 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data = phi i8 [ %msg, %entry ], [ %data.next, %loop ]
  %crc.trunc = trunc i16 %crc to i8
  %xor.data.crc = xor i8 %data, %crc.trunc
  %and.data.crc = and i8 %xor.data.crc, 1
  %data.next = lshr i8 %data, 1
  %check.sb = icmp eq i8 %and.data.crc, 0
  %crc.lshr = lshr i16 %crc, 1
  %xor = xor i16 %crc.lshr, -24575
  %crc.next = select i1 %check.sb, i16 %crc.lshr, i16 %xor
  %iv.next = add nuw nsw i8 %iv, 1
  %exit.cond = icmp samesign ult i8 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @crc16.le.tc8.udiv(i8 %msg, i16 %checksum) {
; CHECK-LABEL: 'crc16.le.tc8.udiv'
; CHECK-NEXT:  Found little-endian CRC-16 loop with trip count 8
; CHECK-NEXT:    Initial CRC: i16 %checksum
; CHECK-NEXT:    Generating polynomial: 40961
; CHECK-NEXT:    Computed CRC: %crc.next = select i1 %check.sb, i16 %crc.lshr, i16 %xor
; CHECK-NEXT:    Auxiliary data: i8 %msg
; CHECK-NEXT:    Computed CRC lookup table:
; CHECK-NEXT:  0 49345 49537 320 49921 960 640 49729 50689 1728 1920 51009 1280 50625 50305 1088
; CHECK-NEXT:  52225 3264 3456 52545 3840 53185 52865 3648 2560 51905 52097 2880 51457 2496 2176 51265
; CHECK-NEXT:  55297 6336 6528 55617 6912 56257 55937 6720 7680 57025 57217 8000 56577 7616 7296 56385
; CHECK-NEXT:  5120 54465 54657 5440 55041 6080 5760 54849 53761 4800 4992 54081 4352 53697 53377 4160
; CHECK-NEXT:  61441 12480 12672 61761 13056 62401 62081 12864 13824 63169 63361 14144 62721 13760 13440 62529
; CHECK-NEXT:  15360 64705 64897 15680 65281 16320 16000 65089 64001 15040 15232 64321 14592 63937 63617 14400
; CHECK-NEXT:  10240 59585 59777 10560 60161 11200 10880 59969 60929 11968 12160 61249 11520 60865 60545 11328
; CHECK-NEXT:  58369 9408 9600 58689 9984 59329 59009 9792 8704 58049 58241 9024 57601 8640 8320 57409
; CHECK-NEXT:  40961 24768 24960 41281 25344 41921 41601 25152 26112 42689 42881 26432 42241 26048 25728 42049
; CHECK-NEXT:  27648 44225 44417 27968 44801 28608 28288 44609 43521 27328 27520 43841 26880 43457 43137 26688
; CHECK-NEXT:  30720 47297 47489 31040 47873 31680 31360 47681 48641 32448 32640 48961 32000 48577 48257 31808
; CHECK-NEXT:  46081 29888 30080 46401 30464 47041 46721 30272 29184 45761 45953 29504 45313 29120 28800 45121
; CHECK-NEXT:  20480 37057 37249 20800 37633 21440 21120 37441 38401 22208 22400 38721 21760 38337 38017 21568
; CHECK-NEXT:  39937 23744 23936 40257 24320 40897 40577 24128 23040 39617 39809 23360 39169 22976 22656 38977
; CHECK-NEXT:  34817 18624 18816 35137 19200 35777 35457 19008 19968 36545 36737 20288 36097 19904 19584 35905
; CHECK-NEXT:  17408 33985 34177 17728 34561 18368 18048 34369 33281 17088 17280 33601 16640 33217 32897 16448
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %crc = phi i16 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data = phi i8 [ %msg, %entry ], [ %data.next, %loop ]
  %crc.trunc = trunc i16 %crc to i8
  %xor.data.crc = xor i8 %data, %crc.trunc
  %and.data.crc = and i8 %xor.data.crc, 1
  %data.next = udiv i8 %data, 2
  %check.sb = icmp eq i8 %and.data.crc, 0
  %crc.lshr = udiv i16 %crc, 2
  %xor = xor i16 %crc.lshr, -24575
  %crc.next = select i1 %check.sb, i16 %crc.lshr, i16 %xor
  %iv.next = add nuw nsw i8 %iv, 1
  %exit.cond = icmp samesign ult i8 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @crc16.le.tc16(i16 %msg, i16 %checksum) {
; CHECK-LABEL: 'crc16.le.tc16'
; CHECK-NEXT:  Found little-endian CRC-16 loop with trip count 16
; CHECK-NEXT:    Initial CRC: i16 %checksum
; CHECK-NEXT:    Generating polynomial: 40961
; CHECK-NEXT:    Computed CRC: %crc.next = select i1 %check.sb, i16 %crc.lshr, i16 %crc.xor
; CHECK-NEXT:    Auxiliary data: i16 %msg
; CHECK-NEXT:    Computed CRC lookup table:
; CHECK-NEXT:  0 49345 49537 320 49921 960 640 49729 50689 1728 1920 51009 1280 50625 50305 1088
; CHECK-NEXT:  52225 3264 3456 52545 3840 53185 52865 3648 2560 51905 52097 2880 51457 2496 2176 51265
; CHECK-NEXT:  55297 6336 6528 55617 6912 56257 55937 6720 7680 57025 57217 8000 56577 7616 7296 56385
; CHECK-NEXT:  5120 54465 54657 5440 55041 6080 5760 54849 53761 4800 4992 54081 4352 53697 53377 4160
; CHECK-NEXT:  61441 12480 12672 61761 13056 62401 62081 12864 13824 63169 63361 14144 62721 13760 13440 62529
; CHECK-NEXT:  15360 64705 64897 15680 65281 16320 16000 65089 64001 15040 15232 64321 14592 63937 63617 14400
; CHECK-NEXT:  10240 59585 59777 10560 60161 11200 10880 59969 60929 11968 12160 61249 11520 60865 60545 11328
; CHECK-NEXT:  58369 9408 9600 58689 9984 59329 59009 9792 8704 58049 58241 9024 57601 8640 8320 57409
; CHECK-NEXT:  40961 24768 24960 41281 25344 41921 41601 25152 26112 42689 42881 26432 42241 26048 25728 42049
; CHECK-NEXT:  27648 44225 44417 27968 44801 28608 28288 44609 43521 27328 27520 43841 26880 43457 43137 26688
; CHECK-NEXT:  30720 47297 47489 31040 47873 31680 31360 47681 48641 32448 32640 48961 32000 48577 48257 31808
; CHECK-NEXT:  46081 29888 30080 46401 30464 47041 46721 30272 29184 45761 45953 29504 45313 29120 28800 45121
; CHECK-NEXT:  20480 37057 37249 20800 37633 21440 21120 37441 38401 22208 22400 38721 21760 38337 38017 21568
; CHECK-NEXT:  39937 23744 23936 40257 24320 40897 40577 24128 23040 39617 39809 23360 39169 22976 22656 38977
; CHECK-NEXT:  34817 18624 18816 35137 19200 35777 35457 19008 19968 36545 36737 20288 36097 19904 19584 35905
; CHECK-NEXT:  17408 33985 34177 17728 34561 18368 18048 34369 33281 17088 17280 33601 16640 33217 32897 16448
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %crc = phi i16 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data = phi i16 [ %msg, %entry ], [ %data.next, %loop ]
  %xor.crc.data = xor i16 %crc, %data
  %and.crc.data = and i16 %xor.crc.data, 1
  %data.next = lshr i16 %data, 1
  %check.sb = icmp eq i16 %and.crc.data, 0
  %crc.lshr = lshr i16 %crc, 1
  %crc.xor = xor i16 %crc.lshr, -24575
  %crc.next = select i1 %check.sb, i16 %crc.lshr, i16 %crc.xor
  %iv.next = add nuw nsw i8 %iv, 1
  %exit.cond = icmp samesign ult i8 %iv, 15
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i8 @crc8.le.tc16(i16 %msg, i8 %checksum) {
; CHECK-LABEL: 'crc8.le.tc16'
; CHECK-NEXT:  Found little-endian CRC-8 loop with trip count 16
; CHECK-NEXT:    Initial CRC: i8 %checksum
; CHECK-NEXT:    Generating polynomial: 29
; CHECK-NEXT:    Computed CRC: %crc.next = select i1 %check.sb, i8 %crc.lshr, i8 %crc.xor
; CHECK-NEXT:    Auxiliary data: i16 %msg
; CHECK-NEXT:    Computed CRC lookup table:
; CHECK-NEXT:  0 9 18 27 31 22 13 4 5 12 23 30 26 19 8 1
; CHECK-NEXT:  10 3 24 17 21 28 7 14 15 6 29 20 16 25 2 11
; CHECK-NEXT:  20 29 6 15 11 2 25 16 17 24 3 10 14 7 28 21
; CHECK-NEXT:  30 23 12 5 1 8 19 26 27 18 9 0 4 13 22 31
; CHECK-NEXT:  19 26 1 8 12 5 30 23 22 31 4 13 9 0 27 18
; CHECK-NEXT:  25 16 11 2 6 15 20 29 28 21 14 7 3 10 17 24
; CHECK-NEXT:  7 14 21 28 24 17 10 3 2 11 16 25 29 20 15 6
; CHECK-NEXT:  13 4 31 22 18 27 0 9 8 1 26 19 23 30 5 12
; CHECK-NEXT:  29 20 15 6 2 11 16 25 24 17 10 3 7 14 21 28
; CHECK-NEXT:  23 30 5 12 8 1 26 19 18 27 0 9 13 4 31 22
; CHECK-NEXT:  9 0 27 18 22 31 4 13 12 5 30 23 19 26 1 8
; CHECK-NEXT:  3 10 17 24 28 21 14 7 6 15 20 29 25 16 11 2
; CHECK-NEXT:  14 7 28 21 17 24 3 10 11 2 25 16 20 29 6 15
; CHECK-NEXT:  4 13 22 31 27 18 9 0 1 8 19 26 30 23 12 5
; CHECK-NEXT:  26 19 8 1 5 12 23 30 31 22 13 4 0 9 18 27
; CHECK-NEXT:  16 25 2 11 15 6 29 20 21 28 7 14 10 3 24 17
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %crc = phi i8 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data = phi i16 [ %msg, %entry ], [ %data.next, %loop ]
  %data.trunc = trunc i16 %data to i8
  %xor.crc.data = xor i8 %crc, %data.trunc
  %and.crc.data = and i8 %xor.crc.data, 1
  %data.next = lshr i16 %data, 1
  %check.sb = icmp eq i8 %and.crc.data, 0
  %crc.lshr = lshr i8 %crc, 1
  %crc.xor = xor i8 %crc.lshr, 29
  %crc.next = select i1 %check.sb, i8 %crc.lshr, i8 %crc.xor
  %iv.next = add nuw nsw i8 %iv, 1
  %exit.cond = icmp samesign ult i8 %iv, 15
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i8 %crc.next
}

define i16 @crc16.be.tc8.crc.init.li(i16 %checksum, i8 %msg) {
; CHECK-LABEL: 'crc16.be.tc8.crc.init.li'
; CHECK-NEXT:  Found big-endian CRC-16 loop with trip count 8
; CHECK-NEXT:    Initial CRC: %crc.init = xor i16 %msg.shl, %checksum
; 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
;
entry:
  %msg.ext = zext i8 %msg to i16
  %msg.shl = shl nuw i16 %msg.ext, 8
  %crc.init = xor i16 %msg.shl, %checksum
  br label %loop

loop:                                              ; preds = %loop, %entry
  %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
  %exit.cond = icmp samesign ult i32 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @crc16.be.tc8.crc.init.arg(i16 %crc.init) {
; CHECK-LABEL: 'crc16.be.tc8.crc.init.arg'
; 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
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %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
  %exit.cond = icmp samesign ult i32 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @crc16.be.tc8.crc.init.arg.flipped.sb.check(i16 %crc.init) {
; CHECK-LABEL: 'crc16.be.tc8.crc.init.arg.flipped.sb.check'
; 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.shl, i16 %crc.xor
; 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
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %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 sge i16 %crc, 0
  %crc.next = select i1 %check.sb, i16 %crc.shl, i16 %crc.xor
  %iv.next = add nuw nsw i32 %iv, 1
  %exit.cond = icmp samesign ult i32 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i8 @crc8.be.tc8.ptr.nested.loop(ptr %msg, i32 %loop.limit) {
; CHECK-LABEL: 'crc8.be.tc8.ptr.nested.loop'
; CHECK-NEXT:  Found big-endian CRC-8 loop with trip count 8
; CHECK-NEXT:    Initial CRC: %crc.init = xor i8 %msg.load, %crc.outer
; CHECK-NEXT:    Generating polynomial: 29
; CHECK-NEXT:    Computed CRC: %crc.next = select i1 %check.sb, i8 %crc.xor, i8 %crc.shl
; CHECK-NEXT:    Computed CRC lookup table:
; CHECK-NEXT:  0 29 58 39 116 105 78 83 232 245 210 207 156 129 166 187
; CHECK-NEXT:  205 208 247 234 185 164 131 158 37 56 31 2 81 76 107 118
; CHECK-NEXT:  135 154 189 160 243 238 201 212 111 114 85 72 27 6 33 60
; CHECK-NEXT:  74 87 112 109 62 35 4 25 162 191 152 133 214 203 236 241
; CHECK-NEXT:  19 14 41 52 103 122 93 64 251 230 193 220 143 146 181 168
; CHECK-NEXT:  222 195 228 249 170 183 144 141 54 43 12 17 66 95 120 101
; CHECK-NEXT:  148 137 174 179 224 253 218 199 124 97 70 91 8 21 50 47
; CHECK-NEXT:  89 68 99 126 45 48 23 10 177 172 139 150 197 216 255 226
; CHECK-NEXT:  38 59 28 1 82 79 104 117 206 211 244 233 186 167 128 157
; CHECK-NEXT:  235 246 209 204 159 130 165 184 3 30 57 36 119 106 77 80
; CHECK-NEXT:  161 188 155 134 213 200 239 242 73 84 115 110 61 32 7 26
; CHECK-NEXT:  108 113 86 75 24 5 34 63 132 153 190 163 240 237 202 215
; CHECK-NEXT:  53 40 15 18 65 92 123 102 221 192 231 250 169 180 147 142
; CHECK-NEXT:  248 229 194 223 140 145 182 171 16 13 42 55 100 121 94 67
; CHECK-NEXT:  178 175 136 149 198 219 252 225 90 71 96 125 46 51 20 9
; CHECK-NEXT:  127 98 69 88 11 22 49 44 151 138 173 176 227 254 217 196
;
entry:
  br label %outer.loop

outer.loop:                                        ; preds = %inner.exit, %entry
  %crc.outer = phi i8 [ 0, %entry ], [ %crc.next, %inner.exit ]
  %outer.iv = phi i32 [ 0, %entry ], [ %outer.iv.next, %inner.exit ]
  %outer.exit.cond = icmp ult i32 %outer.iv, %loop.limit
  br i1 %outer.exit.cond, label %ph, label %exit

ph:                                                ; preds = %outer.loop
  %outer.iv.ext = sext i32 %outer.iv to i64
  %msg.outer.iv = getelementptr inbounds i8, ptr %msg, i64 %outer.iv.ext
  %msg.load = load i8, ptr %msg.outer.iv, align 1
  %crc.init = xor i8 %msg.load, %crc.outer
  br label %inner.loop

inner.loop:                                        ; preds = %inner.loop, %ph
  %inner.iv = phi i32 [ 0, %ph ], [ %inner.iv.next, %inner.loop ]
  %crc = phi i8 [ %crc.init, %ph ], [ %crc.next, %inner.loop ]
  %crc.shl = shl i8 %crc, 1
  %crc.xor = xor i8 %crc.shl, 29
  %check.sb = icmp slt i8 %crc, 0
  %crc.next = select i1 %check.sb, i8 %crc.xor, i8 %crc.shl
  %inner.iv.next = add nuw nsw i32 %inner.iv, 1
  %exit.cond = icmp samesign ult i32 %inner.iv, 7
  br i1 %exit.cond, label %inner.loop, label %inner.exit

inner.exit:                                        ; preds = %inner.loop
  %outer.iv.next = add i32 %outer.iv, 1
  br label %outer.loop

exit:                                              ; preds = %outer.loop
  ret i8 %crc.outer
}

define i32 @crc32.le.tc8.data32(i32 %checksum, i32 %msg) {
; CHECK-LABEL: 'crc32.le.tc8.data32'
; CHECK-NEXT:  Found little-endian CRC-32 loop with trip count 8
; CHECK-NEXT:    Initial CRC: i32 %checksum
; CHECK-NEXT:    Generating polynomial: 33800
; CHECK-NEXT:    Computed CRC: %crc.next = select i1 %check.sb, i32 %crc.lshr, i32 %crc.xor
; CHECK-NEXT:    Auxiliary data: i32 %msg
; CHECK-NEXT:    Computed CRC lookup table:
; CHECK-NEXT:  0 4489 8978 12955 17956 22445 25910 29887 35912 40385 44890 48851 51820 56293 59774 63735
; CHECK-NEXT:  4225 264 13203 8730 22181 18220 30135 25662 40137 36160 49115 44626 56045 52068 63999 59510
; CHECK-NEXT:  8450 12427 528 5017 26406 30383 17460 21949 44362 48323 36440 40913 60270 64231 51324 55797
; CHECK-NEXT:  12675 8202 4753 792 30631 26158 21685 17724 48587 44098 40665 36688 64495 60006 55549 51572
; CHECK-NEXT:  16900 21389 24854 28831 1056 5545 10034 14011 52812 57285 60766 64727 34920 39393 43898 47859
; CHECK-NEXT:  21125 17164 29079 24606 5281 1320 14259 9786 57037 53060 64991 60502 39145 35168 48123 43634
; CHECK-NEXT:  25350 29327 16404 20893 9506 13483 1584 6073 61262 65223 52316 56789 43370 47331 35448 39921
; CHECK-NEXT:  29575 25102 20629 16668 13731 9258 5809 1848 65487 60998 56541 52564 47595 43106 39673 35696
; CHECK-NEXT:  33800 38273 42778 46739 49708 54181 57662 61623 2112 6601 11090 15067 20068 24557 28022 31999
; CHECK-NEXT:  38025 34048 47003 42514 53933 49956 61887 57398 6337 2376 15315 10842 24293 20332 32247 27774
; CHECK-NEXT:  42250 46211 34328 38801 58158 62119 49212 53685 10562 14539 2640 7129 28518 32495 19572 24061
; CHECK-NEXT:  46475 41986 38553 34576 62383 57894 53437 49460 14787 10314 6865 2904 32743 28270 23797 19836
; CHECK-NEXT:  50700 55173 58654 62615 32808 37281 41786 45747 19012 23501 26966 30943 3168 7657 12146 16123
; CHECK-NEXT:  54925 50948 62879 58390 37033 33056 46011 41522 23237 19276 31191 26718 7393 3432 16371 11898
; CHECK-NEXT:  59150 63111 50204 54677 41258 45219 33336 37809 27462 31439 18516 23005 11618 15595 3696 8185
; CHECK-NEXT:  63375 58886 54429 50452 45483 40994 37561 33584 31687 27214 22741 18780 15843 11370 7921 3960
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %crc = phi i32 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data = phi i32 [ %msg, %entry ], [ %data.next, %loop ]
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %xor.crc.data = xor i32 %crc, %data
  %sb.crc.data = and i32 %xor.crc.data, 1
  %check.sb = icmp eq i32 %sb.crc.data, 0
  %crc.lshr = lshr i32 %crc, 1
  %crc.xor = xor i32 %crc.lshr, 33800
  %crc.next = select i1 %check.sb, i32 %crc.lshr, i32 %crc.xor
  %iv.next = add nuw nsw i8 %iv, 1
  %data.next = lshr i32 %data, 1
  %exit.cond = icmp samesign ult i8 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i32 %crc.next
}

; Negative tests

define i16 @not.crc.non.const.tc(i16 %crc.init, i32 %loop.limit) {
; CHECK-LABEL: 'not.crc.non.const.tc'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Unable to find a small constant byte-multiple trip count
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %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 sge i16 %crc, 0
  %crc.next = select i1 %check.sb, i16 %crc.shl, i16 %crc.xor
  %iv.next = add nuw nsw i32 %iv, 1
  %exit.cond = icmp samesign ult i32 %iv, %loop.limit
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @not.crc.non.canonical.not.multiple.8(i16 %crc.init) {
; CHECK-LABEL: 'not.crc.non.canonical.not.multiple.8'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Unable to find a small constant byte-multiple trip count
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %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
  %exit.cond = icmp samesign eq i32 %iv, 3
  br i1 %exit.cond, label %exit, label %loop

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @not.crc.non.canonical.loop.countdown(i16 %crc.init) {
; CHECK-LABEL: 'not.crc.non.canonical.loop.countdown'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Loop not in canonical form
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i32 [ 7, %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 = sub nuw nsw i32 %iv, 1
  %exit.cond = icmp samesign eq i32 %iv, 0
  br i1 %exit.cond, label %exit, label %loop

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @not.crc.non.canonical.loop.multiple.blocks(i16 %crc.init) {
; CHECK-LABEL: 'not.crc.non.canonical.loop.multiple.blocks'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Loop not in canonical form
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %continue ]
  %crc = phi i16 [ %crc.init, %entry ], [ %crc.next, %continue ]
  %check.sb = icmp slt i16 %crc, 0
  %crc.shl = shl i16 %crc, 1
  br i1 %check.sb, label %xor, label %continue

xor:
  %crc.xor = xor i16 %crc.shl, 4129
  br label %continue

continue:
  %crc.next = phi i16 [ %crc.xor, %xor ], [ %crc.shl, %loop ]
  %iv.next = add nuw nsw i32 %iv, 1
  %exit.cond = icmp samesign eq i32 %iv, 7
  br i1 %exit.cond, label %exit, label %loop

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @not.crc.tc.limit(i16 %crc.init) {
; CHECK-LABEL: 'not.crc.tc.limit'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Unable to find a small constant byte-multiple trip count
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %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
  %exit.cond = icmp samesign ult i32 %iv, 512
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @not.crc.no.conditional.recurrence(i16 %crc.init) {
; CHECK-LABEL: 'not.crc.no.conditional.recurrence'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Unable to find conditional recurrence
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %crc = phi i16 [ %crc.init, %entry ], [ %crc.next, %loop ]
  %shl = shl i16 %crc, 1
  %crc.next = xor i16 %shl, 258
  %iv.next = add nuw nsw i8 %iv, 1
  %exit.cond = icmp samesign ult i8 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}


define i16 @not.crc.bad.shift.recurrence(i16 %checksum, i8 %msg) {
; CHECK-LABEL: 'not.crc.bad.shift.recurrence'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Loop with non-unit bitshifts
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %data = phi i8 [ %msg, %entry ], [ %data.next, %loop ]
  %crc = phi i16 [ %checksum, %entry ], [ %crc.next, %loop ]
  %crc.lshr = lshr i16 %crc, 8
  %data.ext = zext i8 %data to i16
  %xor.crc.data = xor i16 %crc.lshr, %data.ext
  %check.sb = icmp samesign ult i16 %xor.crc.data, 128
  %crc.and = and i16 %crc, 32767
  %crc.xor = xor i16 %crc.and, 258
  %crc.next = select i1 %check.sb, i16 %crc.and, i16 %crc.xor
  %data.next = shl i8 %data, 1
  %iv.next = add nuw nsw i8 %iv, 1
  %exit.cond = icmp samesign ult i8 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @not.crc.nonunit.shifts(i16 %crc.init) {
; CHECK-LABEL: 'not.crc.nonunit.shifts'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Loop with non-unit bitshifts
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
  %crc = phi i16 [ %crc.init, %entry ], [ %crc.next, %loop ]
  %crc.shl = shl i16 %crc, 2
  %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
  %exit.cond = icmp samesign ult i32 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @not.crc.result.unused(i16 %crc.init) {
; CHECK-LABEL: 'not.crc.result.unused'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Unable to find use of computed value in loop exit block
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %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
  %exit.cond = icmp samesign ult i32 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc
}

define i16 @not.crc.wrong.sb.check.const(i8 %msg, i16 %checksum) {
; CHECK-LABEL: 'not.crc.wrong.sb.check.const'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Bad RHS of significant-bit-check
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %data = phi i8 [ %msg, %entry ], [ %data.next, %loop ]
  %crc = phi i16 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data.ext = zext i8 %data to i16
  %xor.crc.data = xor i16 %crc, %data.ext
  %check.sb = icmp samesign ult i16 %xor.crc.data, 128
  %crc.shl = shl i16 %crc, 1
  %crc.xor = xor i16 %crc.shl, 258
  %crc.next = select i1 %check.sb, i16 %crc.shl, i16 %crc.xor
  %data.next = shl i8 %data, 1
  %iv.next = add nuw nsw i8 %iv, 1
  %exit.cond = icmp samesign ult i8 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @not.crc.wrong.sb.check.pred(i16 %crc.init) {
; CHECK-LABEL: 'not.crc.wrong.sb.check.pred'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Bad RHS of significant-bit-check
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %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 sgt i16 %crc, 0
  %crc.next = select i1 %check.sb, i16 %crc.shl, i16 %crc.xor
  %iv.next = add nuw nsw i32 %iv, 1
  %exit.cond = icmp samesign ult i32 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @not.crc.excess.tc(i8 %msg, i16 %checksum) {
; CHECK-LABEL: 'not.crc.excess.tc'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Loop iterations exceed bitwidth of data
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %crc = phi i16 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data = phi i8 [ %msg, %entry ], [ %data.next, %loop ]
  %crc.trunc = trunc i16 %crc to i8
  %xor.crc.data = xor i8 %crc.trunc, %data
  %and.crc.data = and i8 %xor.crc.data, 1
  %data.next = lshr i8 %data, 1
  %check.sb = icmp eq i8 %and.crc.data, 0
  %crc.lshr = lshr i16 %crc, 1
  %crc.xor = xor i16 %crc.lshr, -24575
  %crc.next = select i1 %check.sb, i16 %crc.lshr, i16 %crc.xor
  %iv.next = add nuw nsw i8 %iv, 1
  %exit.cond = icmp samesign ult i8 %iv, 15
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @not.crc.init.arg.excess.tc(i16 %crc.init) {
; CHECK-LABEL: 'not.crc.init.arg.excess.tc'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Loop iterations exceed bitwidth of data
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %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
  %exit.cond = icmp samesign ult i32 %iv, 31
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i32 @not.crc.unknown.icmp.rhs(i32 %checksum, i32 %msg, i32 %unknown) {
; CHECK-LABEL: 'not.crc.unknown.icmp.rhs'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Bad LHS of significant-bit-check
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %crc = phi i32 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data = phi i32 [ %msg, %entry ], [ %data.next, %loop ]
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %xor.crc.data = xor i32 %crc, %data
  %sb.crc.data = or i32 %xor.crc.data, 1
  %check.sb = icmp eq i32 %sb.crc.data, %unknown
  %crc.lshr = lshr i32 %crc, 1
  %crc.xor = xor i32 %crc.lshr, 33800
  %crc.next = select i1 %check.sb, i32 %crc.lshr, i32 %crc.xor
  %iv.next = add nuw nsw i8 %iv, 1
  %data.next = lshr i32 %data, 1
  %exit.cond = icmp samesign ult i8 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i32 %crc.next
}

define i32 @not.crc.unknown.icmp.lhs(i32 %checksum, i32 %msg, i32 %unknown) {
; CHECK-LABEL: 'not.crc.unknown.icmp.lhs'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Bad LHS of significant-bit-check
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %crc = phi i32 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data = phi i32 [ %msg, %entry ], [ %data.next, %loop ]
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %xor.crc.data = xor i32 %crc, %data
  %sb.crc.data = or i32 %xor.crc.data, %unknown
  %check.sb = icmp eq i32 %sb.crc.data, 0
  %crc.lshr = lshr i32 %crc, 1
  %crc.xor = xor i32 %crc.lshr, 33800
  %crc.next = select i1 %check.sb, i32 %crc.lshr, i32 %crc.xor
  %iv.next = add nuw nsw i8 %iv, 1
  %data.next = lshr i32 %data, 1
  %exit.cond = icmp samesign ult i8 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i32 %crc.next
}


define i16 @not.crc.stray.or(i16 %msg, i16 %checksum) {
; CHECK-LABEL: 'not.crc.stray.or'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Bad LHS of significant-bit-check
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %crc = phi i16 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data = phi i16 [ %msg, %entry ], [ %data.next, %loop ]
  %xor.crc.data = xor i16 %crc, %data
  %and.crc.data = and i16 %xor.crc.data, 1
  %crc.corrupt = or i16 %and.crc.data, 1
  %data.next = lshr i16 %data, 1
  %check.sb = icmp ne i16 %crc.corrupt, 0
  %crc.lshr = lshr i16 %crc, 1
  %crc.xor = xor i16 %crc.lshr, -24575
  %crc.next = select i1 %check.sb, i16 %crc.lshr, i16 %crc.xor
  %iv.next = add nuw nsw i8 %iv, 1
  %exit.cond = icmp samesign ult i8 %iv, 15
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @not.crc.inverse.sb.check(i16 %msg, i16 %checksum) {
; CHECK-LABEL: 'not.crc.inverse.sb.check'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Expected top 16 bits zero (1100000000000001)
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %crc = phi i16 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data = phi i16 [ %msg, %entry ], [ %data.next, %loop ]
  %xor.crc.data = xor i16 %crc, %data
  %and.crc.data = and i16 %xor.crc.data, 1
  %data.next = lshr i16 %data, 1
  %check.sb = icmp ne i16 %and.crc.data, 0
  %crc.lshr = lshr i16 %crc, 1
  %crc.xor = xor i16 %crc.lshr, -24575
  %crc.next = select i1 %check.sb, i16 %crc.lshr, i16 %crc.xor
  %iv.next = add nuw nsw i8 %iv, 1
  %exit.cond = icmp samesign ult i8 %iv, 15
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @crc1.tc8.sb.check.endian.mismatch(i8 %msg, i16 %checksum) {
; CHECK-LABEL: 'crc1.tc8.sb.check.endian.mismatch'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Bad RHS of significant-bit-check
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %crc = phi i16 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data = phi i8 [ %msg, %entry ], [ %data.next, %loop ]
  %crc.trunc = trunc i16 %crc to i8
  %xor.data.crc = xor i8 %data, %crc.trunc
  %and.data.crc = and i8 %xor.data.crc, 1
  %data.next = mul i8 %data, 2
  %check.sb = icmp eq i8 %and.data.crc, 0
  %crc.lshr = mul i16 %crc, 2
  %xor = xor i16 %crc.lshr, 0
  %crc.next = select i1 %check.sb, i16 %crc.lshr, i16 %xor
  %iv.next = add nuw nsw i8 %iv, 1
  %exit.cond = icmp samesign ult i8 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @not.crc.init.arg.inverted.select(i16 %crc.init) {
; CHECK-LABEL: 'not.crc.init.arg.inverted.select'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Expected top 8 bits zero (11000000????????)
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %crc = phi i16 [ %crc.init, %entry ], [ %crc.next, %loop ]
  %sb.crc = and i16 %crc, 1
  %check.sb = icmp eq i16 %sb.crc, 0
  %crc.lshr = lshr i16 %crc, 1
  %crc.xor = xor i16 %crc.lshr, -24575
  %crc.next = select i1 %check.sb, i16 %crc.xor, i16 %crc.lshr
  %iv.next = add nuw nsw i8 %iv, 1
  %exit.cond = icmp samesign ult i8 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @not.crc.bad.cast(i8 %msg, i16 %checksum) {
; CHECK-LABEL: 'not.crc.bad.cast'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Expected bottom 8 bits zero (????????00001011)
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %data = phi i8 [ %msg, %entry ], [ %data.next, %loop ]
  %crc = phi i16 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data.ext = zext i8 %data to i16
  %xor.crc.data = xor i16 %crc, %data.ext
  %check.sb = icmp slt i16 %xor.crc.data, 0
  %crc.shl = shl i16 %crc, 1
  %crc.xor = xor i16 %crc.shl, 29
  %crc.next = select i1 %check.sb, i16 %crc.shl, i16 %crc.xor
  %data.next = shl i8 %data, 1
  %iv.next = add nuw nsw i8 %iv, 1
  %exit.cond = icmp samesign ult i8 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i32 @not.crc.dead.msg.bad.use(i32 %checksum, i32 %msg) {
; CHECK-LABEL: 'not.crc.dead.msg.bad.use'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Recurrences not intertwined with XOR
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %crc = phi i32 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data = phi i32 [ %msg, %entry ], [ %data.next, %loop ]
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %data.or = or i32 %data, -1
  %xor.crc.data = xor i32 %crc, %data.or
  %sb.crc.data = and i32 %xor.crc.data, 1
  %check.sb = icmp eq i32 %sb.crc.data, 0
  %crc.lshr = lshr i32 %crc, 1
  %crc.xor = xor i32 %crc.lshr, 33800
  %crc.next = select i1 %check.sb, i32 %crc.lshr, i32 %crc.xor
  %iv.next = add nuw nsw i8 %iv, 1
  %data.next = lshr i32 %data, 1
  %exit.cond = icmp samesign ult i8 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i32 %crc.next
}

define i16 @not.crc.dead.msg.no.use(i8 %msg, i16 %checksum) {
; CHECK-LABEL: 'not.crc.dead.msg.no.use'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Recurrences have stray uses
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %crc = phi i16 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data = phi i8 [ %msg, %entry ], [ %data.next, %loop ]
  %crc.trunc = trunc i16 %crc to i8
  %and.crc = and i8 %crc.trunc, 1
  %data.next = lshr i8 %data, 1
  %check.sb = icmp eq i8 %and.crc, 0
  %crc.lshr = lshr i16 %crc, 1
  %xor = xor i16 %crc.lshr, -24575
  %crc.next = select i1 %check.sb, i16 %crc.lshr, i16 %xor
  %iv.next = add nuw nsw i8 %iv, 1
  %exit.cond = icmp samesign ult i8 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  %data.zext = zext i8 %data.next to i16
  %ret = xor i16 %crc.next, %data.zext
  ret i16 %ret
}

define i32 @not.crc.dead.msg.wrong.op(i32 %checksum, i32 %msg) {
; CHECK-LABEL: 'not.crc.dead.msg.wrong.op'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Recurrences not intertwined with XOR
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %crc = phi i32 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data = phi i32 [ %msg, %entry ], [ %data.next, %loop ]
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %or.crc.data = or i32 %crc, %data
  %sb.crc.data = and i32 %or.crc.data, 1
  %check.sb = icmp eq i32 %sb.crc.data, 0
  %crc.lshr = lshr i32 %crc, 1
  %crc.xor = xor i32 %crc.lshr, 33800
  %crc.next = select i1 %check.sb, i32 %crc.lshr, i32 %crc.xor
  %iv.next = add nuw nsw i8 %iv, 1
  %data.next = lshr i32 %data, 1
  %exit.cond = icmp samesign ult i8 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i32 %crc.next
}

define i16 @not.crc.dead.msg.xor.notin.select.chain(i16 %msg, i16 %checksum) {
; CHECK-LABEL: 'not.crc.dead.msg.xor.notin.select.chain'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Recurrences have stray uses
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %crc = phi i16 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data = phi i16 [ %msg, %entry ], [ %data.next, %loop ]
  %xor.crc.data = xor i16 %crc, %data
  %or.crc.data = or i16 %crc, %data
  %and.crc.data = and i16 %or.crc.data, 1
  %data.next = lshr i16 %data, 1
  %check.sb = icmp eq i16 %and.crc.data, 0
  %crc.lshr = lshr i16 %crc, 1
  %crc.xor = xor i16 %crc.lshr, -24575
  %crc.next = select i1 %check.sb, i16 %crc.lshr, i16 %crc.xor
  %iv.next = add nuw nsw i8 %iv, 1
  %exit.cond = icmp samesign ult i8 %iv, 15
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @not.crc.bad.xor.crc.data(i16 %msg, i16 %checksum) {
; CHECK-LABEL: 'not.crc.bad.xor.crc.data'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Recurrences have stray uses
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %crc = phi i16 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data = phi i16 [ %msg, %entry ], [ %data.next, %loop ]
  %xor.crc.data = xor i16 %crc, %data
  %mul.corrupt = mul i16 %xor.crc.data, 0
  %xor.crc.data.corrupt = xor i16 %mul.corrupt, %crc
  %and.crc.data = and i16 %xor.crc.data.corrupt, 1
  %data.next = lshr i16 %data, 1
  %check.sb = icmp eq i16 %and.crc.data, 0
  %crc.lshr = lshr i16 %crc, 1
  %crc.xor = xor i16 %crc.lshr, -24575
  %crc.next = select i1 %check.sb, i16 %crc.lshr, i16 %crc.xor
  %iv.next = add nuw nsw i8 %iv, 1
  %exit.cond = icmp samesign ult i8 %iv, 15
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @not.crc.dead.msg.or.zero(i16 %msg, i16 %checksum) {
; CHECK-LABEL: 'not.crc.dead.msg.or.zero'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Recurrences have stray uses
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %crc = phi i16 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data = phi i16 [ %msg, %entry ], [ %data.next, %loop ]
  %xor.crc.data = xor i16 %crc, %data
  %mul.corrupt = mul i16 %xor.crc.data, 0
  %or.crc.data.corrupt = or i16 %mul.corrupt, %crc
  %and.crc.data = and i16 %or.crc.data.corrupt, 1
  %data.next = lshr i16 %data, 1
  %check.sb = icmp eq i16 %and.crc.data, 0
  %crc.lshr = lshr i16 %crc, 1
  %crc.xor = xor i16 %crc.lshr, -24575
  %crc.next = select i1 %check.sb, i16 %crc.lshr, i16 %crc.xor
  %iv.next = add nuw nsw i8 %iv, 1
  %exit.cond = icmp samesign ult i8 %iv, 15
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @not.crc.unknown.value(i16 %msg, i16 %checksum, i16 %corrupt) {
; CHECK-LABEL: 'not.crc.unknown.value'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Unknown Value
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %crc = phi i16 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data = phi i16 [ %msg, %entry ], [ %data.next, %loop ]
  %xor.crc.data = xor i16 %crc, %data
  %xor.crc.data.corrupt = mul i16 %xor.crc.data, %corrupt
  %and.crc.data = and i16 %xor.crc.data.corrupt, 1
  %data.next = lshr i16 %data, 1
  %check.sb = icmp eq i16 %and.crc.data, 0
  %crc.lshr = lshr i16 %crc, 1
  %crc.xor = xor i16 %crc.lshr, -24575
  %crc.next = select i1 %check.sb, i16 %crc.lshr, i16 %crc.xor
  %iv.next = add nuw nsw i8 %iv, 1
  %exit.cond = icmp samesign ult i8 %iv, 15
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @not.crc.float.simple.recurrence(float %msg, i16 %checksum) {
; CHECK-LABEL: 'not.crc.float.simple.recurrence'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Loop with non-unit bitshifts
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %crc = phi i16 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data = phi float [ %msg, %entry ], [ %data.next, %loop ]
  %crc.conv = sitofp i16 %crc to float
  %frem.data.crc = frem float %data, %crc.conv
  %and.data.crc = fdiv float %frem.data.crc, 2.0
  %data.next = fdiv float %data, 2.0
  %check.sb = fcmp oeq float %and.data.crc, 0.0
  %crc.lshr = lshr i16 %crc, 1
  %xor = xor i16 %crc.lshr, -24575
  %crc.next = select i1 %check.sb, i16 %crc.lshr, i16 %xor
  %iv.next = add nuw nsw i8 %iv, 1
  %exit.cond = icmp samesign ult i8 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}

define i16 @not.crc.stray.phi(i8 %msg, i16 %checksum, i1 %c) {
; CHECK-LABEL: 'not.crc.stray.phi'
; CHECK-NEXT:  Did not find a hash algorithm
; CHECK-NEXT:  Reason: Found stray PHI
;
entry:
  br label %loop

loop:                                              ; preds = %loop, %entry
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
  %crc = phi i16 [ %checksum, %entry ], [ %crc.next, %loop ]
  %data = phi i8 [ %msg, %entry ], [ %data.next, %loop ]
  %crc.trunc = trunc i16 %crc to i8
  %xor.data.crc = xor i8 %data, %crc.trunc
  %and.data.crc = and i8 %xor.data.crc, 1
  %data.next = select i1 %c, i8 %data, i8 1
  %check.sb = icmp eq i8 %and.data.crc, 0
  %crc.lshr = lshr i16 %crc, 1
  %xor = xor i16 %crc.lshr, -24575
  %crc.next = select i1 %check.sb, i16 %crc.lshr, i16 %xor
  %iv.next = add nuw nsw i8 %iv, 1
  %exit.cond = icmp samesign ult i8 %iv, 7
  br i1 %exit.cond, label %loop, label %exit

exit:                                              ; preds = %loop
  ret i16 %crc.next
}