Look through array definition used to implement "recursive functions"
- Dominant language
- C++
- Stars
- 1.9k
- Forks
- 283
- Avg merge
- 2d 10h
- Merged PRs (30d)
- 135
Description
Currently DSLX does not support specification of recursive functions -- https://github.com/google/xls/issues/510
Many logic functions such as reduce_or, clz, etc... can be implemented via a tree of reduction logic. One way currently supported is to have that reduction tree be constructed in a for loop
```
pub fn or_tree_impl(v: bits[N]) -> u1[N_minus_1] {
let N_minus_2 = N-u32:2;
let init_tree = u1[N_minus_1]:[0, ...] ++ v as u1[N];
let tree = for(i, or_tree): (u32, u1[u32:2*N-u32:1]) in u32:0..N_minus_1 {
let index = N_minus_2 - i;
let v = or_tree[2*index+1] || or_tree[2*index+2];
let next = update(or_tree, index, v);
next
}(init_tree);
slice(tree, u32:0, u1[N_minus_1]:[0,...])
}
```
During optimization, the array_updates should be looked-through and each bit's logic cone should be constructed
Ex
```
top fn __or_tree__or_tree(v: bits[8]) -> bits[1][7] {
bit_slice.51: bits[1] = bit_slice(v, start=7, width=1, id=51, pos=[(0,38,16)])
bit_slice.52: bits[1] = bit_slice(v, start=6, width=1, id=52, pos=[(0,38,28)])
bit_slice.53: bits[1] = bit_slice(v, start=5, width=1, id=53, pos=[(0,39,16)])
bit_slice.54: bits[1] = bit_slice(v, start=4, width=1, id=54, pos=[(0,39,28)])
bit_slice.55: bits[1] = bit_slice(v, start=3, width=1, id=55, pos=[(0,40,16)])
bit_slice.56: bits[1] = bit_slice(v, start=2, width=1, id=56, pos=[(0,40,28)])
bit_slice.57: bits[1] = bit_slice(v, start=1, width=1, id=57, pos=[(0,41,16)])
bit_slice.58: bits[1] = bit_slice(v, start=0, width=1, id=58, pos=[(0,41,28)])
or_7_6: bits[1] = or(bit_slice.51, bit_slice.52, id=6, pos=[(0,38,24)])
or_5_4: bits[1] = or(bit_slice.53, bit_slice.54, id=11, pos=[(0,39,24)])
or_3_2: bits[1] = or(bit_slice.55, bit_slice.56, id=16, pos=[(0,40,24)])
or_1_0: bits[1] = or(bit_slice.57, bit_slice.58, id=21, pos=[(0,41,24)])
or_7_4: bits[1] = or(or_7_6, or_5_4, id=22, pos=[(0,43,22)])
or_3_0: bits[1] = or(or_3_2, or_1_0, id=23, pos=[(0,44,22)])
or_7_0: bits[1] = or(or_7_4, or_3_0, id=24, pos=[(0,45,22)])
ret array.40: bits[1][7] = array(or_1_0, or_3_2, or_5_4, or_7_6, or_3_0, or_7_4, or_7_0, id=40, pos=[(0,47,11)])
}
```
and not (as it is)
```
bits[1] = bit_slice(v, start=7, width=1, id=180, pos=[(0,34,14)])
bit_slice.181: bits[1] = bit_slice(v, start=6, width=1, id=181, pos=[(0,34,14)])
bit_slice.182: bits[1] = bit_slice(v, start=5, width=1, id=182, pos=[(0,34,14)])
bit_slice.183: bits[1] = bit_slice(v, start=4, width=1, id=183, pos=[(0,34,14)])
bit_slice.184: bits[1] = bit_slice(v, start=3, width=1, id=184, pos=[(0,34,14)])
bit_slice.185: bits[1] = bit_slice(v, start=2, width=1, id=185, pos=[(0,34,14)])
bit_slice.186: bits[1] = bit_slice(v, start=1, width=1, id=186, pos=[(0,34,14)])
bit_slice.187: bits[1] = bit_slice(v, start=0, width=1, id=187, pos=[(0,34,14)])
literal.190: bits[1][7] = literal(value=[0, 0, 0, 0, 0, 0, 0], id=190, pos=[(0,21,32)])
array.191: bits[1][8] = array(bit_slice.180, bit_slice.181, bit_slice.182, bit_slice.183, bit_slice.184, bit_slice.185, bit_slice.186, bit_slice.187, id=191, pos=[(0,21,44)])
init_tree: bits[1][15] = array_concat(literal.190, array.191, id=196, pos=[(0,21,41)])
v__8: bits[1] = or(bit_slice.186, bit_slice.187, id=204, pos=[(0,25,30)])
index: bits[32] = literal(value=6, id=282, pos=[(0,24,25)])
_next: bits[1][15] = array_update(init_tree, v__8, indices=[index], id=209, pos=[(0,26,20)])
v__9: bits[1] = or(bit_slice.184, bit_slice.185, id=217, pos=[(0,25,30)])
index__1: bits[32] = literal(value=5, id=287, pos=[(0,24,25)])
_next__1: bits[1][15] = array_update(_next, v__9, indices=[index__1], id=222, pos=[(0,26,20)])
v__10: bits[1] = or(bit_slice.182, bit_slice.183, id=230, pos=[(0,25,30)])
index__2: bits[32] = literal(value=4, id=292, pos=[(0,24,25)])
_next__2: bits[1][15] = array_update(_next__1, v__10, indices=[index__2], id=235, pos=[(0,26,20)])
v__11: bits[1] = or(bit_slice.180, bit_slice.181, id=243, pos=[(0,25,30)])
index__3: bits[32] = literal(value=3, id=297, pos=[(0,24,25)])
_next__3: bits[1][15] = array_update(_next__2, v__11, indices=[index__3], id=248, pos=[(0,26,20)])
v__12: bits[1] = or(bit_slice.184, bit_slice.185, v__8, id=385, pos=[(0,25,30)])
index__4: bits[32] = literal(value=2, id=302, pos=[(0,24,25)])
_next__4: bits[1][15] = array_update(_next__3, v__12, indices=[index__4], id=261, pos=[(0,26,20)])
v__13: bits[1] = or(bit_slice.180, bit_slice.181, v__10, id=373, pos=[(0,25,30)])
index__5: bits[32] = literal(value=1, id=307, pos=[(0,24,25)])
_next__5: bits[1][15] = array_update(_next__4, v__13, indices=[index__5], id=273, pos=[(0,26,20)])
v__14: bits[1] = or(v__11, v__10, v__12, id=360, pos=[(0,25,30)])
index__6: bits[32] = literal(value=0, id=312, pos=[(0,24,25)])
tree: bits[1][15] = array_update(_next__5, v__14, indices=[index__6], id=279, pos=[(0,26,20)])
index__7: bits[32] = literal(value=0, id=388, pos=[(0,24,25)])
ret array_slice.281: bits[1][7] = array_slice(tree, index__7, width=7, id=281, pos=[(0,30,7)])
}
```
Contributor guide
Assessment
This issue has not been assessed yet.