API tools faq
paste
Guest User

HVM runtime translation

a guest
Feb 5th, 2022
1,080
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Go 27.18 KB | None | 0 0
raw download clone embed print report
  1. package main
  2.  
  3. import (
  4.     "fmt"
  5.     "math"
  6.     "os"
  7.     "strconv"
  8.     "sync"
  9.     "sync/atomic"
  10.     "time"
  11.     "unsafe"
  12. )
  13.  
  14. type u8 uint8
  15. type u32 uint32
  16. type u64 uint64
  17. type Lnk u64
  18.  
  19. const (
  20.     U64_PER_KB u64 = 0x80
  21.     U64_PER_MB u64 = 0x20000
  22.     U64_PER_GB u64 = 0x8000000
  23.  
  24.     HEAP_SIZE        u64 = 8 * U64_PER_GB * u64(unsafe.Sizeof(u64(0)))
  25.     MEM_SPACE        u64 = HEAP_SIZE / MAX_WORKERS / u64(unsafe.Sizeof(u64(0)))
  26.     NORMAL_SEEN_MCAP u64 = HEAP_SIZE / u64(unsafe.Sizeof(u64(0))) / (u64(unsafe.Sizeof(u64(0))) * 8)
  27. )
  28.  
  29. // stubs for testing
  30. const (
  31.     GENERATED_NUM_THREADS_CONTENT = 8
  32.     MAX_ARITY                     = 16
  33.     MAX_WORKERS                   = 8
  34. )
  35.  
  36. // constants
  37. const (
  38.     // MAX_WORKERS u64 = GENERATED_NUM_THREADS_CONTENT
  39.     MAX_DYNFUNS       u64 = 65536
  40.     stk_growth_factor     = 16
  41. )
  42.  
  43. const (
  44.     VAL u64 = 1
  45.     EXT u64 = 0x100000000
  46.     ARI u64 = 0x100000000000000
  47.     TAG u64 = 0x1000000000000000
  48.  
  49.     DP0 u64 = 0x0 // points to the dup node that binds this variable (left side)
  50.     DP1 u64 = 0x1 // points to the dup node that binds this variable (right side)
  51.     VAR u64 = 0x2 // points to the λ that binds this variable
  52.     ARG u64 = 0x3 // points to the occurrence of a bound variable a linear argument
  53.     ERA u64 = 0x4 // signals that a binder doesn't use its bound variable
  54.     LAM u64 = 0x5 // arity = 2
  55.     APP u64 = 0x6 // arity = 2
  56.     PAR u64 = 0x7 // arity = 2 // TODO: rename to SUP
  57.     CTR u64 = 0x8 // arity = user defined
  58.     CAL u64 = 0x9 // arity = user defined
  59.     OP2 u64 = 0xA // arity = 2
  60.     U32 u64 = 0xB // arity = 0 (unboxed)
  61.     F32 u64 = 0xC // arity = 0 (unboxed)
  62.     NIL u64 = 0xF // not used
  63.  
  64.     ADD u64 = 0x0
  65.     SUB u64 = 0x1
  66.     MUL u64 = 0x2
  67.     DIV u64 = 0x3
  68.     MOD u64 = 0x4
  69.     AND u64 = 0x5
  70.     OR  u64 = 0x6
  71.     XOR u64 = 0x7
  72.     SHL u64 = 0x8
  73.     SHR u64 = 0x9
  74.     LTN u64 = 0xA
  75.     LTE u64 = 0xB
  76.     EQL u64 = 0xC
  77.     GTE u64 = 0xD
  78.     GTN u64 = 0xE
  79.     NEQ u64 = 0xF
  80. )
  81.  
  82. //GENERATED_CONSTRUCTOR_IDS_START//
  83. /* GENERATED_CONSTRUCTOR_IDS_CONTENT */
  84. //GENERATED_CONSTRUCTOR_IDS_END//
  85.  
  86. type Arr []u64
  87. type Stk []u64
  88.  
  89. type Worker struct {
  90.     tid               u64
  91.     cost              u64
  92.     has_work          u64
  93.     has_work_mutex    sync.Mutex
  94.     has_work_signal   sync.Cond
  95.     has_result        u64
  96.     has_result_mutex  sync.Mutex
  97.     has_result_signal sync.Cond
  98.     free              [MAX_ARITY]Stk
  99.     node              []Lnk
  100. }
  101.  
  102. var (
  103.     workers [MAX_WORKERS]Worker
  104. )
  105.  
  106. func array_write(arr Arr, idx, value u64) {
  107.     arr = append(arr, value)
  108. }
  109. func array_read(arr Arr, idx u64) u64 {
  110.     return arr[idx]
  111. }
  112.  
  113. func stk_init(stack Stk) {
  114.     stack = make(Stk, stk_growth_factor)
  115.     return
  116. }
  117. func stk_push(stack Stk, value u64) {
  118.     stack = append(stack, value)
  119.     return
  120. }
  121. func stk_pop(stack Stk) u64 {
  122.     if len(stack) == 0 {
  123.         return u64(math.MaxUint64)
  124.     }
  125.     value := stack[len(stack)-1]
  126.     stack = stack[:len(stack)-1]
  127.     return value
  128. }
  129.  
  130. func stk_find(stack Stk, val u64) u64 {
  131.     for i := range stack {
  132.         if stack[i] == val {
  133.             return u64(i)
  134.         }
  135.     }
  136.     return u64(math.MaxUint64)
  137. }
  138.  
  139. func Var(pos u64) Lnk {
  140.     return Lnk((VAR * TAG) | pos)
  141. }
  142.  
  143. func Dp0(col, pos u64) Lnk {
  144.     return Lnk((DP0 * TAG) | (col * EXT) | pos)
  145. }
  146.  
  147. func Dp1(col, pos u64) Lnk {
  148.     return Lnk((DP1 * TAG) | (col * EXT) | pos)
  149. }
  150.  
  151. func Arg(pos u64) Lnk {
  152.     return Lnk((ARG * TAG) | pos)
  153. }
  154.  
  155. func Era() Lnk {
  156.     return Lnk(ERA * TAG)
  157. }
  158.  
  159. func Lam(pos u64) Lnk {
  160.     return Lnk((LAM * TAG) | pos)
  161. }
  162.  
  163. func App(pos u64) Lnk {
  164.     return Lnk((APP * TAG) | pos)
  165. }
  166.  
  167. func Par(col, pos u64) Lnk {
  168.     return Lnk((PAR * TAG) | (col * EXT) | pos)
  169. }
  170.  
  171. func Op2(ope, pos u64) Lnk {
  172.     return Lnk((OP2 * TAG) | (ope * EXT) | pos)
  173. }
  174.  
  175. func U_32(val u64) Lnk {
  176.     return Lnk((U32 * TAG) | val)
  177. }
  178.  
  179. func Nil() Lnk {
  180.     return Lnk(NIL * TAG)
  181. }
  182.  
  183. func Ctr(ari, fun, pos u64) Lnk {
  184.     return Lnk((CTR * TAG) | (ari * ARI) | (fun * EXT) | pos)
  185. }
  186.  
  187. func Cal(ari, fun, pos u64) Lnk {
  188.     return Lnk((CAL * TAG) | (ari * ARI) | (fun * EXT) | pos)
  189. }
  190.  
  191. func get_tag(lnk Lnk) u64 {
  192.     return u64(lnk) / TAG
  193. }
  194.  
  195. func get_ext(lnk Lnk) u64 {
  196.     return u64(lnk) / EXT & 0xFFFFFF
  197. }
  198.  
  199. func get_val(lnk Lnk) u64 {
  200.     return u64(lnk) & 0xFFFFFF
  201. }
  202.  
  203. func get_ari(lnk Lnk) u64 {
  204.     return u64(lnk) / ARI & 0xFFFFFF
  205. }
  206.  
  207. func get_loc(lnk Lnk, arg u64) u64 {
  208.     return get_val(lnk) + arg
  209. }
  210.  
  211. func ask_lnk(mem *Worker, loc u64) Lnk {
  212.     return mem.node[loc]
  213. }
  214.  
  215. func ask_arg(mem *Worker, term Lnk, arg u64) u64 {
  216.     return u64(ask_lnk(mem, get_loc(term, arg)))
  217. }
  218.  
  219. func link(mem *Worker, loc u64, lnk Lnk) u64 {
  220.     mem.node[loc] = lnk
  221.     if get_tag(lnk) <= VAR {
  222.         if get_tag(lnk) == DP1 {
  223.             mem.node[get_loc(lnk, 1)] = Arg(loc)
  224.         } else {
  225.             mem.node[get_loc(lnk, 0)] = Arg(loc)
  226.  
  227.         }
  228.     }
  229.     return u64(lnk)
  230. }
  231.  
  232. func alloc(mem *Worker, size u64) u64 {
  233.     if size == 0 {
  234.         return 0
  235.     }
  236.     reuse := stk_pop(mem.free[size])
  237.     if reuse != u64(math.MaxUint64) {
  238.         return reuse
  239.     }
  240.     loc := mem.size
  241.     mem.size += size
  242.     return mem.tid*MEM_SPACE + loc
  243. }
  244.  
  245. func clear(mem *Worker, loc u64, size u64) {
  246.     stk_push(mem.free[size], loc)
  247. }
  248.  
  249. func collect(mem *Worker, term Lnk) {
  250.     switch get_tag(term) {
  251.     case DP0:
  252.         link(mem, get_loc(term, 0), Era())
  253.     case DP1:
  254.         link(mem, get_loc(term, 1), Era())
  255.     case VAR:
  256.         link(mem, get_loc(term, 0), Era())
  257.     case LAM:
  258.         if get_tag(Lnk(ask_arg(mem, term, 0))) != ERA {
  259.             link(mem, get_loc(Lnk(ask_arg(mem, term, 0)), 0), Era())
  260.         }
  261.         collect(mem, Lnk(ask_arg(mem, term, 1)))
  262.         clear(mem, get_loc(term, 0), 2)
  263.     case APP:
  264.         collect(mem, Lnk(ask_arg(mem, term, 0)))
  265.         collect(mem, Lnk(ask_arg(mem, term, 1)))
  266.         clear(mem, get_loc(term, 0), 2)
  267.     case PAR:
  268.         collect(mem, Lnk(ask_arg(mem, term, 0)))
  269.         collect(mem, Lnk(ask_arg(mem, term, 1)))
  270.         clear(mem, get_loc(term, 0), 1)
  271.     case OP2:
  272.         collect(mem, Lnk(ask_arg(mem, term, 0)))
  273.         collect(mem, Lnk(ask_arg(mem, term, 1)))
  274.     case U32:
  275.         break
  276.     case CTR:
  277.     case CAL:
  278.         arity := get_ari(term)
  279.         for i := u64(0); i < arity; i++ {
  280.             collect(mem, Lnk(ask_arg(mem, term, i)))
  281.         }
  282.         clear(mem, get_loc(term, 0), arity)
  283.     }
  284. }
  285.  
  286. func inc_cost(mem *Worker) {
  287.     mem.cost++
  288. }
  289.  
  290. func subst(mem *Worker, lnk, val Lnk) {
  291.     if get_tag(lnk) != ERA {
  292.         link(mem, get_loc(lnk, 0), val)
  293.     } else {
  294.         collect(mem, val)
  295.     }
  296. }
  297.  
  298. func cal_par(mem *Worker, host u64, term, argn Lnk, n u64) Lnk {
  299.     inc_cost(mem)
  300.     var (
  301.         arity u64 = get_ari(term)
  302.         fun   u64 = get_ext(term)
  303.         fun0      = get_loc(term, 0)
  304.         fun1      = get_loc(term, 1)
  305.         par0      = get_loc(argn, 0)
  306.     )
  307.     for i := u64(0); i < arity; i++ {
  308.         if i != n {
  309.             var (
  310.                 leti u64 = alloc(mem, 3)
  311.                 argi u64 = ask_arg(mem, term, i)
  312.             )
  313.             link(mem, fun0+i, Dp0(get_ext(argn), leti))
  314.             link(mem, fun1+i, Dp1(get_ext(argn), leti+1))
  315.             link(mem, leti+2, Lnk(argi))
  316.         } else {
  317.             link(mem, fun0+i, Lnk(ask_arg(mem, argn, 0)))
  318.             link(mem, fun1+i, Lnk(ask_arg(mem, argn, 1)))
  319.         }
  320.     }
  321.     link(mem, par0+0, Cal(arity, fun, fun0))
  322.     link(mem, par0+1, Cal(arity, fun, fun1))
  323.     done := Par(get_ext(argn), par0)
  324.     link(mem, host, done)
  325.     return done
  326. }
  327.  
  328. func reduce(mem *Worker, root, slen u64) Lnk {
  329.     stack := Stk{}
  330.     stk_init(stack)
  331.  
  332.     var (
  333.         init u64 = 1
  334.         host u32 = u32(root)
  335.     )
  336.  
  337.     for {
  338.         term := ask_lnk(mem, u64(host))
  339.  
  340.         if init == 1 {
  341.             switch get_tag(term) {
  342.             case APP:
  343.                 stk_push(stack, u64(host))
  344.                 init = 1
  345.                 host = u32(get_loc(term, 0))
  346.                 continue
  347.             case DP0:
  348.             case DP1:
  349.                 flag := atomic.Value{}
  350.                 flag.Store((mem.node[get_loc(term, 0)] + 6))
  351.                 flag1 := atomic.Value{}
  352.                 flag1.Store((mem.node[get_loc(term, 0)]))
  353.                 if !flag.CompareAndSwap(flag, flag1) {
  354.                     continue
  355.                 }
  356.                 stk_push(stack, u64(host))
  357.                 host = u32(get_loc(term, 2))
  358.                 continue
  359.             case OP2:
  360.                 if slen == 1 || len(stack) > 0 {
  361.                     stk_push(stack, u64(host))
  362.                     stk_push(stack, get_loc(term, 0)|0x80000000)
  363.                     host = u32(get_loc(term, 1))
  364.                     continue
  365.                 }
  366.             case CAL:
  367.                 fun := get_ext(term)
  368.                 ari := get_ari(term)
  369.                 _ = ari
  370.                 switch fun {
  371.                 //GENERATED_REWRITE_RULES_STEP_0_START//
  372.                 /* GENERATED_REWRITE_RULES_STEP_0_CONTENT */
  373.                 //GENERATED_REWRITE_RULES_STEP_0_END//
  374.                 }
  375.             }
  376.         } else {
  377.             switch get_tag(term) {
  378.             case APP:
  379.                 arg0 := ask_arg(mem, term, 0)
  380.                 switch get_tag(Lnk(arg0)) {
  381.                 case LAM:
  382.                     inc_cost(mem)
  383.                     subst(mem, Lnk(ask_arg(mem, Lnk(arg0), 0)), Lnk(ask_arg(mem, term, 1)))
  384.                     done := link(mem, u64(host), Lnk(ask_arg(mem, Lnk(arg0), 1)))
  385.                     _ = done
  386.                     clear(mem, get_loc(term, 0), 2)
  387.                     clear(mem, get_loc(Lnk(arg0), 0), 2)
  388.                     init = 1
  389.                     continue
  390.                 case PAR:
  391.                     inc_cost(mem)
  392.                     app0 := get_loc(term, 0)
  393.                     app1 := get_loc(term, 1)
  394.                     let0 := alloc(mem, 3)
  395.                     par0 := alloc(mem, 2)
  396.                     link(mem, let0+2, Lnk(ask_arg(mem, term, 1)))
  397.                     link(mem, app0+1, Dp0(get_ext(Lnk(arg0)), let0))
  398.                     link(mem, app0+0, Lnk(ask_arg(mem, Lnk(arg0), 0)))
  399.                     link(mem, app1+0, Lnk(ask_arg(mem, Lnk(arg0), 1)))
  400.                     link(mem, app1+1, Dp1(get_ext(Lnk(arg0)), let0+1))
  401.                     link(mem, par0+0, App(app0))
  402.                     link(mem, par0+1, App(app1))
  403.                     done := Par(get_ext(Lnk(arg0)), par0)
  404.                     link(mem, u64(host), done)
  405.                 } //switch arg0
  406.             case DP0:
  407.             case DP1:
  408.                 arg0 := ask_arg(mem, term, 2)
  409.                 switch get_tag(Lnk(arg0)) {
  410.                 case LAM:
  411.                     inc_cost(mem)
  412.                     let0 := get_loc(term, 0)
  413.                     par0 := get_loc(Lnk(arg0), 0)
  414.                     lam0 := alloc(mem, 2)
  415.                     lam1 := alloc(mem, 2)
  416.                     link(mem, let0+2, Lnk(ask_arg(mem, Lnk(arg0), 1)))
  417.                     link(mem, par0+1, Var(lam1))
  418.                     arg0_arg_0 := ask_arg(mem, Lnk(arg0), 0)
  419.                     link(mem, par0+0, Var(lam0))
  420.                     subst(mem, Lnk(arg0_arg_0), Par(get_ext(term), par0))
  421.                     term_arg_0 := ask_arg(mem, term, 0)
  422.                     link(mem, lam0+1, Dp0(get_ext(term), let0))
  423.                     subst(mem, Lnk(term_arg_0), Lam(lam0))
  424.                     term_arg_1 := ask_arg(mem, term, 1)
  425.                     link(mem, lam1+1, Dp1(get_ext(term), let0))
  426.                     subst(mem, Lnk(term_arg_1), Lam(lam1))
  427.                     if get_tag(term) == DP0 {
  428.                         done := Lam(lam0)
  429.                         link(mem, u64(host), done)
  430.                     } else {
  431.                         done := Lam(lam1)
  432.                         link(mem, u64(host), done)
  433.                     }
  434.                     init = 1
  435.                     continue
  436.                 case PAR:
  437.                     if get_ext(term) == get_ext(Lnk(arg0)) {
  438.                         inc_cost(mem)
  439.                         subst(mem, Lnk(ask_arg(mem, term, 0)), Lnk(ask_arg(mem, Lnk(arg0), 0)))
  440.                         subst(mem, Lnk(ask_arg(mem, term, 1)), Lnk(ask_arg(mem, Lnk(arg0), 1)))
  441.                         done := u64(0)
  442.                         _ = done
  443.                         if get_tag(term) == DP0 {
  444.                             done = link(mem, u64(host), Lnk(ask_arg(mem, Lnk(arg0), 0)))
  445.                         } else {
  446.                             done = link(mem, u64(host), Lnk(ask_arg(mem, Lnk(arg0), 0)))
  447.                         }
  448.                         clear(mem, get_loc(term, 0), 3)
  449.                         clear(mem, get_loc(Lnk(arg0), 0), 2)
  450.                         init = 1
  451.                         continue
  452.                     } else {
  453.                         inc_cost(mem)
  454.                         par0 := alloc(mem, 2)
  455.                         let0 := get_loc(term, 0)
  456.                         par1 := get_loc(Lnk(arg0), 0)
  457.                         let1 := alloc(mem, 3)
  458.                         link(mem, let0+2, Lnk(ask_arg(mem, Lnk(arg0), 0)))
  459.                         link(mem, let0+2, Lnk(ask_arg(mem, Lnk(arg0), 1)))
  460.                         term_arg_0 := ask_arg(mem, term, 0)
  461.                         term_arg_1 := ask_arg(mem, term, 1)
  462.                         link(mem, par0+0, Dp1(get_ext(term), let0))
  463.                         link(mem, par0+1, Dp1(get_ext(term), let1))
  464.                         link(mem, par0+0, Dp0(get_ext(term), let0))
  465.                         link(mem, par0+1, Dp0(get_ext(term), let1))
  466.                         subst(mem, Lnk(term_arg_0), Par(get_ext(Lnk(arg0)), par0))
  467.                         subst(mem, Lnk(term_arg_1), Par(get_ext(Lnk(arg0)), par1))
  468.                         done := Lnk(0)
  469.                         if get_tag(term) == DP0 {
  470.                             done = Par(u64(get_ext(term)), par0)
  471.                         } else {
  472.                             done = Par(u64(get_ext(term)), par1)
  473.                         }
  474.                         link(mem, u64(host), done)
  475.                     }
  476.                 case U32:
  477.                     inc_cost(mem)
  478.                     subst(mem, Lnk(ask_arg(mem, term, 0)), Lnk(arg0))
  479.                     subst(mem, Lnk(ask_arg(mem, term, 1)), Lnk(arg0))
  480.                     // done := u64(arg0) //wut
  481.                     link(mem, u64(host), Lnk(arg0))
  482.  
  483.                 case CTR:
  484.                     inc_cost(mem)
  485.                     fun := get_ext(Lnk(arg0))
  486.                     arit := get_ari(Lnk(arg0))
  487.                     if arit == 0 {
  488.                         subst(mem, Lnk(ask_arg(mem, term, 0)), Ctr(0, fun, 0))
  489.                         subst(mem, Lnk(ask_arg(mem, term, 1)), Ctr(0, fun, 0))
  490.                         clear(mem, get_loc(term, 0), 3)
  491.                         done := link(mem, u64(host), Ctr(0, fun, 0))
  492.                         _ = done
  493.                     } else {
  494.                         ctr0 := get_loc(Lnk(arg0), 0)
  495.                         ctr1 := alloc(mem, arit)
  496.                         for i := u64(0); i < arit; i++ {
  497.                             leti := alloc(mem, 3)
  498.                             link(mem, ctr0+i, Dp0(get_ext(term), leti))
  499.                             link(mem, ctr1+i, Dp1(get_ext(term), leti))
  500.                         }
  501.                         leti := get_loc(term, 0)
  502.                         link(mem, leti+2, Lnk(ask_arg(mem, Lnk(arg0), arit-1)))
  503.                         term_arg_0 := ask_arg(mem, term, 0)
  504.                         link(mem, ctr0+arit-1, Dp0(get_ext(term), leti))
  505.                         subst(mem, Lnk(term_arg_0), Ctr(arit, fun, ctr0))
  506.                         term_arg_1 := ask_arg(mem, term, 1)
  507.                         link(mem, ctr0+arit-1, Dp1(get_ext(term), leti))
  508.                         subst(mem, Lnk(term_arg_1), Ctr(arit, fun, ctr1))
  509.                         done := Lnk(0)
  510.                         if get_tag(term) == DP0 {
  511.                             done = Ctr(arit, fun, ctr0)
  512.                         } else {
  513.                             done = Ctr(arit, fun, ctr1)
  514.                         }
  515.                         link(mem, u64(host), done)
  516.                     }
  517.  
  518.                 } //switch arg0
  519.                 // flag := atomic.Value{}
  520.                 // flag.Store((mem.node[get_loc(term, 0)] + 6))
  521.             case OP2:
  522.                 arg0 := ask_arg(mem, term, 0)
  523.                 arg1 := ask_arg(mem, term, 1)
  524.  
  525.                 if get_tag(Lnk(arg0)) == U32 && get_tag(Lnk(arg1)) == U32 {
  526.                     inc_cost(mem)
  527.                     a := get_val(Lnk(arg0))
  528.                     b := get_val(Lnk(arg1))
  529.                     c := u64(0)
  530.                     switch get_ext(term) {
  531.                     case ADD:
  532.                         c = (a + b) & 0xFFFFFFFF
  533.                     case SUB:
  534.                         c = (a - b) & 0xFFFFFFFF
  535.                     case MUL:
  536.                         c = (a * b) & 0xFFFFFFFF
  537.                     case DIV:
  538.                         c = (a / b) & 0xFFFFFFFF
  539.                     case MOD:
  540.                         c = (a % b) & 0xFFFFFFFF
  541.                     case AND:
  542.                         c = (a & b) & 0xFFFFFFFF
  543.                     case OR:
  544.                         c = (a | b) & 0xFFFFFFFF
  545.                     case XOR:
  546.                         c = (a ^ b) & 0xFFFFFFFF
  547.                     case SHL:
  548.                         c = (a << b) & 0xFFFFFFFF
  549.                     case SHR:
  550.                         c = (a >> b) & 0xFFFFFFFF
  551.                     case LTN:
  552.                         if a < b {
  553.                             c = 1
  554.                         }
  555.                     case LTE:
  556.                         if a <= b {
  557.                             c = 1
  558.                         }
  559.                     case EQL:
  560.                         if a == b {
  561.                             c = 1
  562.                         }
  563.                     case GTE:
  564.                         if a >= b {
  565.                             c = 1
  566.                         }
  567.                     case GTN:
  568.                         if a > b {
  569.                             c = 1
  570.                         }
  571.                     case NEQ:
  572.                         if a != b {
  573.                             c = 1
  574.                         }
  575.                     }
  576.                     done := U_32(c)
  577.                     clear(mem, get_loc(term, 0), 2)
  578.                     link(mem, u64(host), done)
  579.                 } else if get_tag(Lnk(arg0)) == PAR {
  580.                     inc_cost(mem)
  581.                     op20 := get_loc(term, 0)
  582.                     op21 := get_loc(Lnk(arg0), 0)
  583.                     let0 := alloc(mem, 3)
  584.                     par0 := alloc(mem, 2)
  585.                     link(mem, let0+2, Lnk(arg1))
  586.                     link(mem, op20+1, Dp0(get_ext(Lnk(arg0)), let0))
  587.                     link(mem, op20+0, Lnk(ask_arg(mem, Lnk(arg0), 0)))
  588.                     link(mem, op20+0, Lnk(ask_arg(mem, Lnk(arg0), 1)))
  589.                     link(mem, op21+1, Dp1(get_ext(Lnk(arg0)), let0))
  590.                     link(mem, par0+0, Op2(get_ext(Lnk(arg0)), op20))
  591.                     link(mem, par0+1, Op2(get_ext(Lnk(arg0)), op21))
  592.                     done := Par(get_ext(Lnk(arg0)), par0)
  593.                     link(mem, u64(host), done)
  594.                 } else if get_tag(Lnk(arg1)) == PAR {
  595.                     inc_cost(mem)
  596.                     op20 := get_loc(term, 0)
  597.                     op21 := get_loc(Lnk(arg1), 0)
  598.                     let0 := alloc(mem, 3)
  599.                     par0 := alloc(mem, 2)
  600.                     link(mem, let0+2, Lnk(arg0))
  601.                     link(mem, op20+0, Dp0(get_ext(Lnk(arg1)), let0))
  602.                     link(mem, op20+1, Lnk(ask_arg(mem, Lnk(arg1), 0)))
  603.                     link(mem, op21+1, Lnk(ask_arg(mem, Lnk(arg1), 1)))
  604.                     link(mem, par0+0, Op2(get_ext(Lnk(arg1)), op20))
  605.                     link(mem, par0+1, Op2(get_ext(Lnk(arg1)), op21))
  606.                     done := Par(get_ext(Lnk(arg1)), par0)
  607.                     link(mem, u64(host), done)
  608.                 }
  609.             case CAL:
  610.                 fun := get_ext(term)
  611.                 ari := get_ari(term)
  612.                 _ = ari
  613.                 switch fun {
  614.                 //GENERATED_REWRITE_RULES_STEP_1_START//
  615.                 /* GENERATED_REWRITE_RULES_STEP_1_CONTENT */
  616.                 //GENERATED_REWRITE_RULES_STEP_1_END//
  617.                 }
  618.             } //switch term
  619.  
  620.         }
  621.         item := stk_pop(stack)
  622.         if item == u64(math.MaxUint64) {
  623.             break
  624.         } else {
  625.             item = item >> 31
  626.             host = u32(item & 0x7FFFFFFF)
  627.         }
  628.     }
  629.     return ask_lnk(mem, root)
  630. }
  631.  
  632. func set_bit(bits []u64, bit u64) {
  633.     bits[bit>>6] |= 1 << (bit & 0x3F)
  634. }
  635.  
  636. func get_bit(bits []u64, bit u64) u8 {
  637.     return u8(bits[bit>>6] >> (1 << (bit & 0x3F)) & 1)
  638. }
  639.  
  640. func normal_init() {
  641.     for i := 0; i < len(normal_seen_data); i++ {
  642.         normal_seen_data[i] = 0
  643.     }
  644. }
  645.  
  646. func normal(mem *Worker, host, sidx, slen u64) Lnk {
  647.     normal_init()
  648.     normal_go(mem, host, sidx, slen)
  649.     normal_init()
  650.     return normal_go(mem, host, 0, 1)
  651. }
  652.  
  653. func normal_fork(tid, host, sidx, slen u64) {
  654.     // todo
  655.     workers[tid].has_work_mutex.Lock()
  656.     workers[tid].has_work = (sidx << 48) | (slen << 32) | host
  657.     workers[tid].has_work_signal.Broadcast()
  658.     workers[tid].has_work_mutex.Unlock()
  659. }
  660. func normal_join(tid u64) u64 {
  661.     // todo
  662.     for {
  663.         workers[tid].has_result_mutex.Lock()
  664.         for workers[tid].has_result == math.MaxUint64 {
  665.             workers[tid].has_result_signal.Wait()
  666.         }
  667.         done := workers[tid].has_result
  668.         workers[tid].has_result = math.MaxUint64
  669.         workers[tid].has_result_mutex.Unlock()
  670.         return done
  671.     }
  672. }
  673.  
  674. var (
  675.     ffi_cost u64
  676.     ffi_size u64
  677.     WG       sync.WaitGroup
  678. )
  679.  
  680. func worker_stop(tid u64) {
  681.     workers[tid].has_work_mutex.Lock()
  682.     workers[tid].has_work = math.MaxUint64 - 1
  683.     workers[tid].has_work_signal.Broadcast()
  684.     workers[tid].has_work_mutex.Unlock()
  685. }
  686.  
  687. func worker(tid u64) {
  688.     for {
  689.         workers[tid].has_work_mutex.Lock()
  690.         for workers[tid].has_work == math.MaxUint64 {
  691.             workers[tid].has_work_signal.Wait()
  692.         }
  693.         work := workers[tid].has_work
  694.         if work == math.MaxUint64-1 {
  695.             break
  696.         }
  697.         sidx := (work >> 48) & 0xFFFF
  698.         slen := (work >> 32) & 0xFFFF
  699.         host := (work >> 0) & 0xFFFFFFFF
  700.         workers[tid].has_result = u64(normal_go(&workers[tid], host, sidx, slen))
  701.         workers[tid].has_work = math.MaxUint64
  702.         workers[tid].has_work_signal.Signal()
  703.         workers[tid].has_work_mutex.Unlock()
  704.     }
  705.     WG.Done()
  706. }
  707.  
  708. func ffi_normal(mem_data []Lnk, host u32) {
  709.     for t := u64(0); t < MAX_WORKERS; t++ {
  710.         workers[t].tid = t
  711.         workers[t].node = mem_data
  712.         for a := u64(0); a < MAX_ARITY; a++ {
  713.             stk_init(workers[t].free[a])
  714.         }
  715.         workers[t].has_work = math.MaxUint64
  716.         workers[t].has_work_mutex = sync.Mutex{}
  717.         workers[t].has_work_signal = sync.Cond{}
  718.         workers[t].has_result = math.MaxUint64
  719.         workers[t].has_result_mutex = sync.Mutex{}
  720.         workers[t].has_result_signal = sync.Cond{}
  721.         WG.Add(1)
  722.         go worker(t)
  723.     }
  724.     normal(&workers[0], host, 0, MAX_WORKERS)
  725.     ffi_cost = 0
  726.     ffi_size = 0
  727.     for i := u64(0); i < MAX_WORKERS; i++ {
  728.         ffi_cost += workers[i].cost
  729.         ffi_size += u64(len(workers[i].node))
  730.     }
  731.     for t := u64(0); t < MAX_WORKERS; t++ {
  732.         worker_stop(t)
  733.     }
  734.     WG.Wait()
  735.     for t := u64(0); t < MAX_WORKERS; t++ {
  736.         for a := u64(0); a < MAX_ARITY; a++ {
  737.             stk_free(workers[t].free[a])
  738.         }
  739.         workers[t].node = nil
  740.     }
  741. }
  742.  
  743. var normal_seen_data []u64 = make([]u64, NORMAL_SEEN_MCAP)
  744.  
  745. func normal_go(mem *Worker, host, sidx, slen u64) Lnk {
  746.     term := ask_lnk(mem, host)
  747.     if get_bit(normal_seen_data, host) != 0 {
  748.         return term
  749.     }
  750.     term = reduce(mem, host, slen)
  751.     set_bit(normal_seen_data, host)
  752.     rec_size := u64(0)
  753.     rec_locs := [16]u64{}
  754.     switch get_tag(term) {
  755.     case LAM:
  756.         rec_locs[rec_size] = get_loc(term, 1)
  757.         rec_size++
  758.     case APP:
  759.         rec_locs[rec_size] = get_loc(term, 0)
  760.         rec_size++
  761.         rec_locs[rec_size] = get_loc(term, 1)
  762.         rec_size++
  763.     case PAR:
  764.         rec_locs[rec_size] = get_loc(term, 0)
  765.         rec_size++
  766.         rec_locs[rec_size] = get_loc(term, 1)
  767.         rec_size++
  768.     case DP0:
  769.         rec_locs[rec_size] = get_loc(term, 2)
  770.         rec_size++
  771.     case DP1:
  772.         rec_locs[rec_size] = get_loc(term, 2)
  773.         rec_size++
  774.     case OP2:
  775.         if slen > 1 {
  776.             rec_locs[rec_size] = get_loc(term, 1)
  777.             rec_size++
  778.         }
  779.     case CTR:
  780.     case CAL:
  781.         ari := get_ari(term)
  782.         for i := u64(0); i < ari; i++ {
  783.             rec_locs[rec_size] = get_loc(term, i)
  784.             rec_size++
  785.         }
  786.     }
  787.  
  788.     if rec_size > 2 && slen >= rec_size {
  789.         space := slen / rec_size
  790.         for i := u64(0); i < rec_size; i++ {
  791.             normal_fork(sidx+i*space, rec_locs[i], sidx+i*space, space)
  792.         }
  793.         link(mem, rec_locs[0], normal_go(mem, rec_locs[0], sidx, space))
  794.         for i := u64(1); i < rec_size; i++ {
  795.             link(mem, get_loc(term, i), Lnk(normal_join(sidx+i*space)))
  796.         }
  797.     } else {
  798.         for i := u64(0); i < rec_size; i++ {
  799.             link(mem, rec_locs[i], normal_go(mem, rec_locs[i], sidx, slen))
  800.         }
  801.     }
  802.  
  803.     return term
  804. }
  805.  
  806. func readback_vars(vars Stk, mem *Worker, term Lnk, seen Stk) {
  807.     if stk_find(seen, u64(term)) != math.MaxUint64 {
  808.         return
  809.     }
  810.     stk_push(seen, u64(term))
  811.     switch get_tag(term) {
  812.     case LAM:
  813.         argm := ask_arg(mem, term, 0)
  814.         body := ask_arg(mem, term, 1)
  815.         if get_tag(argm) != ERA {
  816.             stk_push(vars, u64(Var(get_loc(term, 0))))
  817.         }
  818.         readback_vars(vars, mem, Lnk(body), seen)
  819.     case APP:
  820.         lam := ask_arg(mem, term, 0)
  821.         arg := ask_arg(mem, term, 1)
  822.         readback_vars(vars, mem, Lnk(lam), seen)
  823.         readback_vars(vars, mem, Lnk(arg), seen)
  824.     case PAR:
  825.         arg0 := ask_arg(mem, term, 0)
  826.         arg1 := ask_arg(mem, term, 1)
  827.         readback_vars(vars, mem, Lnk(arg0), seen)
  828.         readback_vars(vars, mem, Lnk(arg1), seen)
  829.     case DP0:
  830.         arg := ask_arg(mem, term, 2)
  831.         readback_vars(vars, mem, Lnk(arg), seen)
  832.     case DP1:
  833.         arg := ask_arg(mem, term, 2)
  834.         readback_vars(vars, mem, Lnk(arg), seen)
  835.     case OP2:
  836.         arg0 := ask_arg(mem, term, 0)
  837.         arg1 := ask_arg(mem, term, 1)
  838.         readback_vars(vars, mem, Lnk(arg0), seen)
  839.         readback_vars(vars, mem, Lnk(arg1), seen)
  840.     case CTR:
  841.     case CAL:
  842.         arity := get_ari(term)
  843.         for i := u64(0); i < arity; i++ {
  844.             readback_vars(vars, mem, Lnk(ask_arg(mem, term, i)), seen)
  845.         }
  846.     }
  847. }
  848.  
  849. func readback_decimal_go(chrs Stk, n u64) {
  850.     if n > 0 {
  851.         readback_decimal_go(chrs, n/10)
  852.         stk_push(chrs, '0'+n%10)
  853.     }
  854. }
  855.  
  856. func readback_decimal(chrs Stk, n u64) {
  857.     if n == 0 {
  858.         stk_push(chrs, 0)
  859.     } else {
  860.         readback_decimal_go(chrs, n)
  861.     }
  862. }
  863.  
  864. func readback_term(chrs Stk, mem *Worker, term Lnk, vars Stk, dirs []Stk, id_to_name_data []string) {
  865.     switch get_tag(term) {
  866.     case LAM:
  867.         stk_push(chrs, '%')
  868.         if get_tag(Lnk(ask_arg(mem, term, 0))) == ERA {
  869.             stk_push(chrs, '_')
  870.         } else {
  871.             stk_push(chrs, 'x')
  872.             readback_decimal(chrs, stk_find(vars, u64(Var(get_loc(term, 0)))))
  873.         }
  874.         stk_push(chrs, ' ')
  875.         readback_term(chrs, mem, Lnk(ask_arg(mem, term, 1)), vars, dirs, id_to_name_data)
  876.         break
  877.     case APP:
  878.         stk_push(chrs, '(')
  879.         readback_term(chrs, mem, Lnk(ask_arg(mem, term, 0)), vars, dirs, id_to_name_data)
  880.         stk_push(chrs, ' ')
  881.         readback_term(chrs, mem, Lnk(ask_arg(mem, term, 1)), vars, dirs, id_to_name_data)
  882.         stk_push(chrs, ')')
  883.         break
  884.     case PAR:
  885.         col := get_ext(term)
  886.         if len(dirs[col]) > 0 {
  887.             head := stk_pop(dirs[col])
  888.             if head == 0 {
  889.                 readback_term(chrs, mem, Lnk(ask_arg(mem, term, 0)), vars, dirs, id_to_name_data)
  890.                 stk_push(dirs[col], head)
  891.             } else {
  892.                 readback_term(chrs, mem, Lnk(ask_arg(mem, term, 1)), vars, dirs, id_to_name_data)
  893.                 stk_push(dirs[col], head)
  894.             }
  895.         } else {
  896.             stk_push(chrs, '<')
  897.             readback_term(chrs, mem, Lnk(ask_arg(mem, term, 0)), vars, dirs, id_to_name_data)
  898.             stk_push(chrs, ' ')
  899.             readback_term(chrs, mem, Lnk(ask_arg(mem, term, 1)), vars, dirs, id_to_name_data)
  900.             stk_push(chrs, '>')
  901.         }
  902.         break
  903.     case DP0:
  904.     case DP1:
  905.         col := get_ext(term)
  906.         val := ask_arg(mem, term, 2)
  907.         pushVal := 0
  908.         if get_tag(term) != DP0 {
  909.             pushVal = 1
  910.         }
  911.         stk_push(dirs[col], u64(pushVal))
  912.         readback_term(chrs, mem, Lnk(ask_arg(mem, term, 2)), vars, dirs, id_to_name_data)
  913.         stk_pop(dirs[col])
  914.         break
  915.     case OP2:
  916.         stk_push(chrs, '(')
  917.         readback_term(chrs, mem, Lnk(ask_arg(mem, term, 0)), vars, dirs, id_to_name_data)
  918.         switch get_ext(term) {
  919.         case ADD:
  920.             stk_push(chrs, '+')
  921.         case SUB:
  922.             stk_push(chrs, '-')
  923.         case MUL:
  924.             stk_push(chrs, '*')
  925.         case DIV:
  926.             stk_push(chrs, '/')
  927.         case MOD:
  928.             stk_push(chrs, '%')
  929.         case AND:
  930.             stk_push(chrs, '&')
  931.         case OR:
  932.             stk_push(chrs, '|')
  933.         case XOR:
  934.             stk_push(chrs, '^')
  935.         case SHL:
  936.             stk_push(chrs, '<')
  937.             stk_push(chrs, '<')
  938.         case SHR:
  939.             stk_push(chrs, '>')
  940.             stk_push(chrs, '>')
  941.         case LTN:
  942.             stk_push(chrs, '<')
  943.         case LTE:
  944.             stk_push(chrs, '<')
  945.             stk_push(chrs, '=')
  946.         case EQL:
  947.             stk_push(chrs, '=')
  948.             stk_push(chrs, '=')
  949.         case GTE:
  950.             stk_push(chrs, '>')
  951.             stk_push(chrs, '=')
  952.         case GTN:
  953.             stk_push(chrs, '>')
  954.         case NEQ:
  955.             stk_push(chrs, '!')
  956.             stk_push(chrs, '=')
  957.         }
  958.         readback_term(chrs, mem, Lnk(ask_arg(mem, term, 1)), vars, dirs, id_to_name_data)
  959.     case U32:
  960.         readback_decimal(chrs, get_val(term))
  961.     case CTR:
  962.     case CAL:
  963.         fun := get_ext(term)
  964.         ari := get_ari(term)
  965.         stk_push(chrs, '(')
  966.         if fun < len(id_to_name_data) && id_to_name_data[fun] != "" {
  967.             for _, v := range id_to_name_data[fun] {
  968.                 stk_push(chrs, u64(v))
  969.             }
  970.         } else {
  971.             stk_push(chrs, '$')
  972.             readback_decimal(chrs, fun)
  973.         }
  974.         for i := u64(0); i < ari; i++ {
  975.             stk_push(chrs, ' ')
  976.             readback_term(chrs, mem, Lnk(ask_arg(mem, term, i)), vars, dirs, id_to_name_data)
  977.         }
  978.         stk_push(chrs, ')')
  979.     case VAR:
  980.         stk_push(chrs, 'x')
  981.         readback_decimal(chrs, stk_find(vars, u64(term)))
  982.     default:
  983.         stk_push(chrs, '?')
  984.     }
  985. }
  986.  
  987. func readback(code_data string, code_mcap u64, mem *Worker, term Lnk, id_to_name_data []string) string {
  988.     const dirs_mcap u64 = 65536
  989.     var (
  990.         seen = Stk{}
  991.         chrs = Stk{}
  992.         vars = Stk{}
  993.         dirs = []Stk{}
  994.     )
  995.     stk_init(seen)
  996.     stk_init(chrs)
  997.     stk_init(vars)
  998.     for i := 0; i < int(dirs_mcap); i++ {
  999.         dirs = append(dirs, Stk{})
  1000.         stk_init(dirs[i])
  1001.     }
  1002.  
  1003.     readback_vars(vars, mem, term, seen)
  1004.     readback_term(chrs, mem, term, vars, dirs, id_to_name_data)
  1005.  
  1006.     for i := 0; i < len(chrs); i++ {
  1007.         code_data += string(chrs[i])
  1008.     }
  1009.     return code_data
  1010. }
  1011.  
  1012. func debug_print_lnk(lnk Lnk) {
  1013.     tag := get_tag(lnk)
  1014.     ext := get_ext(lnk)
  1015.     val := get_val(lnk)
  1016.     str := ""
  1017.     switch tag {
  1018.     case DP0:
  1019.         str = "DP0"
  1020.     case DP1:
  1021.         str = "DP1"
  1022.     case VAR:
  1023.         str = "VAR"
  1024.     case ARG:
  1025.         str = "ARG"
  1026.     case ERA:
  1027.         str = "ERA"
  1028.     case LAM:
  1029.         str = "LAM"
  1030.     case APP:
  1031.         str = "APP"
  1032.     case PAR:
  1033.         str = "PAR"
  1034.     case CTR:
  1035.         str = "CTR"
  1036.     case CAL:
  1037.         str = "CAL"
  1038.     case OP2:
  1039.         str = "OP2"
  1040.     case U32:
  1041.         str = "U32"
  1042.     case F32:
  1043.         str = "F32"
  1044.     case NIL:
  1045.         str = "NIL"
  1046.     default:
  1047.         str = "???"
  1048.     }
  1049.     fmt.Printf("%s %x %x %x\n", str, ext, val, lnk)
  1050. }
  1051.  
  1052. func parse_arg(code string, id_to_name_data []string) Lnk {
  1053.     if code[0] >= '0' && code[0] <= '9' {
  1054.         i, _ := strconv.Atoi(code)
  1055.         return U_32(u64(i))
  1056.     }
  1057.     return U_32(0)
  1058. }
  1059.  
  1060. func main() {
  1061.     //  fmt.Println("HEAP_SIZE:", HEAP_SIZE, u64(unsafe.Sizeof(u64(0))))
  1062.     mem := Worker{}
  1063.     var (
  1064.         start time.Time
  1065.         stop  time.Time
  1066.     )
  1067.  
  1068.     // const u64 id_to_name_size = /* GENERATED_NAME_COUNT_CONTENT */
  1069.     // char* id_to_name_data[id_to_name_size];
  1070.     id_to_name_data = []string{
  1071.         /* GENERATED_ID_TO_NAME_DATA_CONTENT */
  1072.     }
  1073.     // builds main term
  1074.     mem.node = make([]Lnk, HEAP_SIZE)
  1075.     if len(os.Args) <= 1 {
  1076.         mem.node = append(mem.node, Cal(0, _MAIN_, 0))
  1077.     } else {
  1078.         mem.node = append(mem.node, Cal(len(os.Args)-1, _MAIN_, 1))
  1079.         for _, arg := range os.Args[1:] {
  1080.             mem.node = append(mem.node, parse_arg(arg, id_to_name_data))
  1081.         }
  1082.     }
  1083.     // reduces and benchmarks
  1084.     start = time.Now()
  1085.     ffi_normal(mem.node, 0)
  1086.     stop = time.Now()
  1087.  
  1088.     // Prints result statistics
  1089.     // u64 delta_time = (stop.tv_sec - start.tv_sec) * 1000000 + stop.tv_usec - start.tv_usec;
  1090.     // double rwt_per_sec = (double)ffi_cost / (double)delta_time;
  1091.     fmt.Printf("Rewrites: %v (%.2f MR/s).\n", ffi_cost, ffi.cost/float64(stop.Sub(start).Seconds()))
  1092.     fmt.Printf("Mem.Size: %v words.\n", ffi_size)
  1093.  
  1094.     // Prints result normal form
  1095.     const code_mcap = u64(256 * 256 * 256) // max code size = 16 MB
  1096.     // char* code_data = (char*)malloc(code_mcap * sizeof(char));
  1097.     code_data := readback(code_data, code_mcap, &mem, mem.node[0], id_to_name_data)
  1098.     fmt.Println(code_data)
  1099. }
  1100.  
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!