qbe

Internal scc patchset buffer for QBE
Log | Files | Refs | README | LICENSE

collatz.ssa (1255B)


      1 # a solution for N=1000 to
      2 # https://projecteuler.net/problem=14
      3 # we use a fast local array to
      4 # memoize small collatz numbers
      5 
      6 export
      7 function $test() {
      8 @start
      9 	%mem =l alloc4 4000
     10 @loop
     11 	%n =w phi @start 1, @newm %n9, @oldm %n9
     12 	%cmax =w phi @start 0, @newm %c, @oldm %cmax
     13 	%fin =w csltw %n, 1000
     14 	jnz %fin, @cloop, @end
     15 @cloop
     16 	%n0 =w phi @loop %n, @odd %n2, @even %n3
     17 	%c0 =w phi @loop 0, @odd %c1, @even %c1
     18 	%no1 =w cnew %n0, 1
     19 	jnz %no1, @iter0, @endcl
     20 @iter0
     21 	%ism =w csltw %n0, %n
     22 	jnz %ism, @getmemo, @iter1
     23 @iter1
     24 	%c1 =w add %c0, 1
     25 	%p =w and %n0, 1
     26 	jnz %p, @odd, @even
     27 @odd
     28 	%n1 =w mul 3, %n0
     29 	%n2 =w add %n1, 1
     30 	jmp @cloop
     31 @even
     32 	%n3 =w shr %n0, 1
     33 	jmp @cloop
     34 @getmemo                     # get the count for n0 in mem
     35 	%n0l =l extsw %n0
     36 	%idx0 =l mul %n0l, 4
     37 	%loc0 =l add %idx0, %mem
     38 	%cn0 =w loadw %loc0
     39 	%c2 =w add %c0, %cn0
     40 @endcl                       # store the count for n in mem
     41 	%c =w phi @getmemo %c2, @cloop %c0
     42 	%nl =l extsw %n
     43 	%idx1 =l mul %nl, 4
     44 	%loc1 =l add %idx1, %mem
     45 	storew %c, %loc1
     46 	%n9 =w add 1, %n
     47 	%big =w cslew %cmax, %c
     48 	jnz %big, @newm, @oldm
     49 @newm
     50 	jmp @loop
     51 @oldm
     52 	jmp @loop
     53 @end
     54 	storew %cmax, $a
     55 	ret
     56 }
     57 
     58 # >>> driver
     59 # extern void test(void);
     60 # int a;
     61 # int main() { test(); return !(a == 178); }
     62 # <<<