Suboptimal code generation for simple loop

[mskvortsov]

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 | - }

[mskvortsov]

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

[mskvortsov]

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

[mskvortsov]

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

[mskvortsov]

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

[mskvortsov]

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.

[mskvortsov]

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