diff options
Diffstat (limited to 'notes')
| -rw-r--r-- | notes/primop-inference.txt | 73 |
1 files changed, 73 insertions, 0 deletions
diff --git a/notes/primop-inference.txt b/notes/primop-inference.txt new file mode 100644 index 00000000..ec704ba6 --- /dev/null +++ b/notes/primop-inference.txt @@ -0,0 +1,73 @@ +The design of the primitive operations follows the following principles: +(1) if operand types are known (i.e. FIRRTL front-end), primops whose return type is statically known (no future type introspection needed) are available +(2) if operand types are not known (i.e. hand-writing FIRRTL pass), generic primops can be used, and a future pass will perform type introspection to replace the generic with the specific primop +(3) the FIRRTL's lowered form will never contain any generic primops +(4) resultant widths are always large enough to represent any possible output +(5) specific primops do not grow widths (e.g. add-wrap, sub-wrap) and should be used if that behavior is desired +(6) except for mux, mux-u, and mux-s, all primops can accept operands of differing width to enable optimizations in the backend +(7) autopadding on connect is not allowed, and one should use the pad!/-u/-s expression to autopad + +TODO: +rederive div,mod,quo,rem widths. +Write explanations in terms of formulas. +Reread all explanations. +Finish adding primops. + +add + adduu(a,b) -> u, max(a.w,b.w) + 1 + addus(a,b) -> s, max(a.w,b.w) + 1 + addsu(a,b) -> s, max(a.w,b.w) + 1 + addss(a,b) -> s, max(a.w,b.w) + 1 + +sub + subuu(a,b) -> s, max(a.w,b.w) + 1 ; 0@<UInt,3> - 7@<UInt,3> = -7@<SInt,4> + subus(a,b) -> s, max(a.w,b.w) + 1 ; 7@<UInt,3> - -8@<SInt,4> = 15@<SInt,5> + subsu(a,b) -> s, max(a.w,b.w) + 1 ; -8@<SInt,4> - 7@<UInt,3> = -15@<SInt,5> + subss(a,b) -> s, max(a.w,b.w) + 1 ; -8@<UInt,4> - 7@<SInt,4> = -15@<SInt,5> + +mul + muluu(a,b) -> u,a.w+b.w + mulus(a,b) -> s,a.w+b.w + mulsu(a,b) -> s,a.w+b.w + mulss(a,b) -> s,a.w+b.w + +div + divuu(a,b) -> u,a.w ; if divide by 1 + divus(a,b) -> s,a.w+1 ; if divide by -1 + divsu(a,b) -> s,a.w ; if divide by 1 + divss(a,b) -> s,a.w+1 ; if divide by -1 + +mod + moduu(a,d) -> u,d.w + modus(a,d) -> u,d.w-1 + modsu(a,d) -> u,d.w + modss(a,d) -> u,d.w-1 + +rem + remuu(a,b) -> u,min(a.w,b.w) ; 15 % 16 = 15. All remainders must be less than b or a. + remus(a,b) -> u,b.w ; -1 % 32 = 31. Remainder can be larger than abs(a), but not larger than b. + remsu(a,b) -> s,b.w ; 1 % -32 = -31. abs(rem) can be larger than abs(a), but not larger than abs(b). + remss(a,b) -> s,b.w ; strictly superset of us and su. + +add-mod + add-moduu(a,b) -> u, a.w + add-modus(a,b) -> u, a.w + add-modsu(a,b) -> s, a.w + add-modss(a,b) -> s, a.w + +sub-mod + sub-moduu(a,b) -> u, a.w + sub-modus(a,b) -> u, a.w + sub-modsu(a,b) -> s, a.w + sub-modss(a,b) -> s, a.w + + +Proof: +add-moduu -> u +take inverse: +sub-moduu -> u +add-modus -> u +add-modsu -> s with width of first operand + +add-mod and sub-mod always return the type and width of the first operand. + |