Not complete yet. I still need to dig out all example programs.

Some functions, like fac, use additional variables for having the C version close to an assembler version to reveal the number of actually used stack slots.

divide

original

int divide (int m, int n) {
  if (m<n) {
    return 0;
  } else {
    return 1 + divide(m-n, n-1);}
}

basic

int n, m;

int divide_basic (void) {
  int scratch;
  if (m<n) {
    return 0;
    } else {
      m=m-n; n=n-1;
      scratch=divide_basic();
      return 1 + scratch;
    }
}

splitting

nothing to split.

iteratisation

int divide_it (int m, int n) {
  int _depth=0;
  int _result;
  int scratch;
top:

  if (m<n) {
    if(_depth==0){return 0;} else {_depth--; _result=0; goto caller;}
    } else {
      m=m-n; n=n-1;

      _depth++;
      goto top;
    caller:
      scratch=_result;

      if(_depth==0){return scratch+1;} else {_depth--; _result=scratch+1; goto caller;}
    }
}

remainder

original

int reminder (int m, int n) {
  if (m<n) {
    return m;
  } else {
    return reminder(m-n, n);}
}

basic

int n, m;

int reminder_basic (void) {
  if (m<n) {
    return m;
  } else {
    m=m-n; /* n=n; */
    return reminder_basic();}
}

splitting

nothing to split.

iteratisation

int reminder_it (int m, int n) {
  int _depth=0;
  int _result;
  int scratch;
top:

  if (m<n) {
    if(_depth==0){return m;} else {_depth--; _result=m; goto caller;}
  } else {
    m=m-n; /* n=n; */
    _depth++;
    goto top;
  caller:
    scratch=_result;
    
    if(_depth==0){return scratch;} else {_depth--; _result=scratch; goto caller;
}
  }
}

fac

original

int fac(int n){

  if(n>0){
    return n*fac(n-1);
  } else {
    return 1;
  }
}

basic

nothing to optimize.

splitting

to come

iteratisation

int fac_it(int n){

  int res, _result, _depth=0;

top:

  if(n>0){
    n=n-1;
    _depth++;
    goto top;
  caller:
    res=_result;
    n=n+1;
    if (_depth==0){
      return n*res;
    } else {
      _result=n*res;
      _depth--;
      goto caller;
    }
  } else {
    if (_depth==0){
      return 1;
    } else {
      _result=1;
      _depth--;
      goto caller;
    }
  }
}

fib

original

basic

splitting

iteratisation

fib_fast

original

basic

splitting

iteratisation

exp_2

original

int power(int n) {
  if (n==0) {
    return 1;
  } else {
    return 2*power(n-1);
  }
}

basic

int power_basic(void) {
  if (n==0) {
    return 1;
  } else {
    n=n-1;
    return 2*power_basic();
  }
}

splitting

nothing left to split.

iteratisation

int power_it(int n) {
  int _depth=0;
  int _result;
  int scratch;
top:

  if (n==0) {

    if(_depth==0){return 1;} else {_depth--; _result=1; goto caller;}

  } else {
    n=n-1;
    
    _depth++;
    goto top;
  caller:
    scratch=_result;
    
    if(_depth==0){return 2*scratch;} else {_depth--; _result=2*scratch; goto caller;}

  }
}

exp

original

int power(int n, int m) {
  if (n==0) {
    return 1;
  } else {
    return m*power(n-1, m);
  }
}

basic

int n;

int power_basic(int m) {
  if (n==0) {
    return 1;
  } else {
    n=n-1;
    return m*power_basic(m);
  }
}

splitting

int m, n;

int power_split(void) {
  if (n==0) {
    return 1;
  } else {
    n=n-1;
    return m*power_split();
  }
}

iteratisation

int power_it(int n, int m) {
  int _depth=0;
  int _result;
  int scratch;
top:

 if (n==0) {
    if(_depth==0){return 1;} else {_depth--; _result=1; goto caller;}

  } else {
    n=n-1;

    _depth++;
    goto top;
  caller:
    scratch=_result;
    
    if(_depth==0){return m*scratch;} else {_depth--; _result=m*scratch; goto caller;}


  }
}

exp_fast

original

int fast_exp (int m, int n) {
  int res;

  if (n==0)
    return 1;
  else if (even (n)){
    res=fast_exp (m, n/2);
    return res*res;}
  else
    return m*fast_exp (m, n-1);
}

basic

int n;

int fast_exp_basic (int m) {
  int res;

  if (n==0)
    return 1;
  else if (even (n)){
    n=n/2;
    res=fast_exp_basic (m);
    return res*res;}
  else {
    n=n-1;
    return m*fast_exp_basic (m);
  }
}

splitting

int n, m;

int fast_exp_split (void) {
  if (n==0){
    return 1;
  } else if (even (n)) {
    n=n/2;
    return square(fast_exp_split ());
  } else {
    n=n-1;
    return      m*fast_exp_split ();}
}

iteratisation

not possible b/c two recursive calls.

gcd

original

int gcd (int m, int n) {

  if (n==0) {
    return m;
  } else {
    return gcd (n, reminder(m, n));
  }
}

basic

not possible.

splitting

int scratchy; /* we need a scratch variable for "swaping" */

int gcd_split () {
  
  if (n==0) {
    return m;
  } else {
    scratchy=n;
    n=reminder(m,n);
    m=scratchy;
    return gcd_split ();
  }
}

iteratisation

int gcd_it (int m, int n) {

  int _depth=0;
  int _result;
  int scratch;
top:
  
  if (n==0) {
      if(_depth==0){return m;} else {_depth--; _result=m; goto caller;}
  } else {
    scratchy=n;
    n=reminder(m,n);
    m=scratchy;

    _depth++;
    goto top;
  caller:
    scratch=_result;
    
    if(_depth==0){return scratch;} else {_depth--; _result=scratch; goto caller;
}


  }
}

hanoi

original

basic

splitting

iteratisation