In-progress, working on inferring types pass

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.
+