TVM-Compiler
TVM-Compiler copied to clipboard
Published
20 hours ago •
everx-labs
everx-labs
Suboptimal code generation for simple loop
int gcd(int a, int b)
{
int r;
while (b > 0)
{
r = a % b;
a = b;
b = r;
}
return a;
}
→
define dso_local i257 @gcd(i257 %a, i257 %b) {
entry:
%cmp3 = icmp sgt i257 %b, 0
br i1 %cmp3, label %while.body, label %while.end
while.body: ; preds = %entry, %while.body
%a.addr.05 = phi i257 [ %b.addr.04, %while.body ], [ %a, %entry ]
%b.addr.04 = phi i257 [ %rem, %while.body ], [ %b, %entry ]
%rem = srem i257 %a.addr.05, %b.addr.04
%cmp = icmp sgt i257 %rem, 0
br i1 %cmp, label %while.body, label %while.end
while.end: ; preds = %while.body, %entry
%a.addr.0.lcssa = phi i257 [ %a, %entry ], [ %b.addr.04, %while.body ]
ret i257 %a.addr.0.lcssa
}
→
gcd: ; @gcd
; %bb.0: ; %entry
; { %20 | %1 | - }
PUSH c0 ; >%4 = PUSHC i257 0
; { %20 | %1 | %4 | - }
PUSHINT 0 ; >%27 = CONST_I257 i257 0
; { %20 | %1 | %4 | %27 | - }
PUSH s2 ; { %20 | %1 | %4 | %27 | %1 | - }
SWAP ; { %20 | %1 | %4 | %1 | %27 | - }
GREATER ; >%8 = SGT %1, %27
; { %20 | %1 | %4 | %8 | - }
PUSHCONT ; >%19 = PUSHCONT_MBB %bb.2, 0
; { %20 | %1 | %4 | %8 | %19 | - }
{
; %bb.2: ; %while.end
; { %1 | x | %4 | x | x | - }
BLKDROP 2 ; { %1 | x | %4 | - }
POP c0 ; { %1 | x | - }
DROP ; { %1 | - }
; fallthrough return
}
PUSHCONT ; >%24 = PUSHCONT_MBB %bb.5, 0
; { %20 | %1 | %4 | %8 | %19 | %24 | - }
{
; %bb.5: ; %entry.while.end.cleanup
; { x | %4 | %19 | %20 | - }
; >%1 = REG_TO_REG_COPY %20
; { x | %4 | %19 | %1 | - }
ZERO ; { x | %4 | %19 | %1 | x | - }
ZERO ; { x | %4 | %19 | %1 | x | x | - }
ROLLREV 2 ; { x | %4 | %19 | x | %1 | x | - }
BLKSWAP 2, 4 ; { %19 | x | %1 | x | x | %4 | - }
SWAP ; { %19 | x | %1 | x | %4 | x | - }
ROLL 4 ; { %19 | %1 | x | %4 | x | x | - }
ROLL 5 ; { %1 | x | %4 | x | x | %19 | - }
JMPX ; { %1 | x | %4 | x | x | %19 | - } => { %1 | x | %4 | x | x | - }
}
BLKSWAP 2, 3 ; { %20 | %8 | %19 | %24 | %1 | %4 | - }
ROLL 3 ; { %20 | %8 | %24 | %1 | %4 | %19 | - }
ROLL 5 ; { %8 | %24 | %1 | %4 | %19 | %20 | - }
ROLL 5 ; { %24 | %1 | %4 | %19 | %20 | %8 | - }
ROLL 5 ; { %1 | %4 | %19 | %20 | %8 | %24 | - }
IFNOTJMP ; { %1 | %4 | %19 | %20 | %8 | %24 | - } => { %1 | %4 | %19 | %20 | - }
; %bb.1: ; %entry.while.body.cleanup
; { %1 | %4 | %19 | %20 | - }
PUSHCONT ; >%12 = PUSHCONT_MBB %bb.3, i257 0
; { %1 | %4 | %19 | %20 | %12 | - }
{
; %bb.3: ; %while.body
; { %1 | %4 | %12 | %19 | %20 | - }
PUSH s4 ; { %1 | %4 | %12 | %19 | %20 | %1 | - }
MOD ; >%2 = MOD %20, %1
; { %1 | %4 | %12 | %19 | %2 | - }
PUSHINT 0 ; >%28 = CONST_I257 i257 0
; { %1 | %4 | %12 | %19 | %2 | %28 | - }
PUSH s1 ; { %1 | %4 | %12 | %19 | %2 | %28 | %2 | - }
SWAP ; { %1 | %4 | %12 | %19 | %2 | %2 | %28 | - }
GREATER ; >%14 = SGT %2, %28
; { %1 | %4 | %12 | %19 | %2 | %14 | - }
PUSHCONT
{
; %bb.4: ; %while.body.while.body.cleanup
; { %1 | %2 | %4 | %12 | %19 | - }
XCHG s0, s4 ; { %19 | %2 | %4 | %12 | %1 | - }
; >%20 = REG_TO_REG_COPY %1
; { %19 | %2 | %4 | %12 | %20 | - }
XCHG s0, s3 ; { %19 | %20 | %4 | %12 | %2 | - }
; >%1 = REG_TO_REG_COPY %2
; { %19 | %20 | %4 | %12 | %1 | - }
PUSH s1 ; { %19 | %20 | %4 | %12 | %1 | %12 | - }
SWAP ; { %19 | %20 | %4 | %12 | %12 | %1 | - }
BLKSWAP 2, 2 ; { %19 | %20 | %12 | %1 | %4 | %12 | - }
BLKSWAP 2, 4 ; { %12 | %1 | %4 | %12 | %19 | %20 | - }
ROLL 5 ; { %1 | %4 | %12 | %19 | %20 | %12 | - }
JMPX ; { %1 | %4 | %12 | %19 | %20 | %12 | - } => { %1 | %4 | %12 | %19 | %20 | - }
} ; >%26 = PUSHCONT_MBB %bb.4, 0
; { %1 | %4 | %12 | %19 | %2 | %14 | %26 | - }
PUSH s3 ; { %1 | %4 | %12 | %19 | %2 | %14 | %26 | %19 | - }
ROLL 3 ; { %1 | %4 | %12 | %19 | %14 | %26 | %19 | %2 | - }
BLKSWAP 3, 4 ; { %1 | %14 | %26 | %19 | %2 | %4 | %12 | %19 | - }
BLKSWAP 3, 4 ; { %1 | %2 | %4 | %12 | %19 | %14 | %26 | %19 | - }
IFELSE ; { %1 | %2 | %4 | %12 | %19 | %14 | %26 | %19 | - } => { %1 | %2 | %4 | %12 | %19 | - }
}
DUP ; { %1 | %4 | %19 | %20 | %12 | %12 | - }
SWAP ; { %1 | %4 | %19 | %20 | %12 | %12 | - }
BLKSWAP 2, 2 ; { %1 | %4 | %12 | %12 | %19 | %20 | - }
ROLL 3 ; { %1 | %4 | %12 | %19 | %20 | %12 | - }
JMPX ; { %1 | %4 | %12 | %19 | %20 | %12 | - } => { %1 | %4 | %12 | %19 | %20 | - }
Manually written code utilizing WHILE primitive:
gcd: ; (a b -- gcd)
PUSHCONT {
DUP ; ( -- a b b)
ISPOS ; ( -- a b s)
}
PUSHCONT {
SWAP ; ( -- b a)
OVER ; ( -- b a b)
MOD ; ( -- b r)
}
WHILE
DROP
An experimental version with cfg as state machine
gcd:
;; static cfg description
NIL ; placeholder, zero bb
PUSHCONT { ; bb 1, entry
DUP ISPOS ; branch condition
PUSHINT 2 PUSHINT 3 CONDSEL ; branch
}
PUSHCONT { ; bb 2, loop
SWAP OVER MOD ; computation
DUP ISPOS ; branch condition
PUSHINT 2 PUSHINT 3 CONDSEL ; branch
}
PUSHCONT { ; bb 3, exit
DROP ; computation
PUSHINT 0 ; branch, zero means exit
}
;; pack basic blocks into tuple at c13
TUPLE 4
POPCTR c13
;; execute cfg
PUSHINT 1 ; label of entry block
PUSHCONT { DUP }
PUSHCONT { PUSHCTR c13 SWAP INDEXVAR EXECUTE }
WHILE
;; drop zero bb label
DROP
The c13 global register used in the code above must be saved and restored around a call to any functions generated in such a manner. So here is a version without using c13:
gcd:
PUSHINT 1 ; entry block label
PUSHCONT { DUP } ; while condition
PUSHCONT { ; while body
PUSHCONT { ; bb 1, entry
DUP ISPOS ; branch condition
PUSHINT 2 PUSHINT 3 CONDSEL ; branch
}
PUSHCONT { ; bb 2, loop
SWAP OVER MOD ; computation
DUP ISPOS ; branch condition
PUSHINT 2 PUSHINT 3 CONDSEL ; branch
}
PUSHCONT { ; bb 3, exit
DROP ; computation
PUSHINT 0 ; branch, zero implies exit
}
TUPLE 3 SWAP DEC INDEXVAR ; select next bb
EXECUTE
}
WHILE
DROP ; drop zero bb label
Results of measuring gas consumption for all gcd variants.
#include "ton-sdk/tvm.h"
extern int gcd(int, int);
TVM_CUSTOM_EXCEPTION(FAILED, 101);
void bench_Impl() {
ACCEPT();
tvm_assert(gcd(20988936657440586486151264256610222593863921,
67280421310721) == 1, FAILED);
}
| Variant | Gas |
|---|---|
| baseline | 6780 |
| clang | 12468 |
| structured cf | 8238 |
| state machine w/ c13 | 10904 |
| state machine w/o c13 | 11901 |
Baseline gcd:
gcd:
DROP2
ONE
Update:
| Variant | Gas |
|---|---|
| baseline | 4547 |
| clang | 10235 |
| structured cf | 6005 |
| state machine w/ c13 | 8671 |
| state machine w/o c13 | 9668 |
Note: for the input given, gcd makes 15 iterations.
Keeping basic blocks on the stack right before arguments, 6875 units of gas:
gcd:
PUSHCONT { ; entry
DUP ISPOS
PUSH s4 ; {loop}
PUSH s4 ; {exit}
IFELSE
}
PUSHCONT { ; loop
SWAP OVER MOD
DUP ISPOS
PUSH s4 ; {loop}
PUSH s4 ; {exit}
IFELSE
}
PUSHCONT { ; exit
DROP
}
BLKSWAP 2, 3 ; 2 arguments, 3 BBs
PUSH s4 ; {entry}
EXECUTE
BLKSWAP 3, 1 ; 3 BBs, 1 return value
BLKDROP 3