search

everx-labs / TVM-Compiler

Clang compiler for TVM
Apache License 2.0
59 stars 16 forks source link

Suboptimal code generation for simple loop #86

Open mskvortsov opened 4 years ago

mskvortsov commented 4 years ago 
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 commented 4 years ago

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 commented 4 years ago

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 commented 4 years ago

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 commented 4 years ago

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 commented 4 years ago
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 commented 4 years ago

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