Skip to content

Instantly share code, notes, and snippets.

@loredanacirstea

loredanacirstea/YulRecursionMemoryManagement.md

Created August 14, 2020 10:52
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save loredanacirstea/92d2dd1127fb95ea05d4cec671d02a91 to your computer and use it in GitHub Desktop.
Save loredanacirstea/92d2dd1127fb95ea05d4cec671d02a91 to your computer and use it in GitHub Desktop.
Download ZIP
YulRecursionMemoryManagement
Raw
YulRecursionMemoryManagement.md

Recursion with Frames in Memory

See ethereum/solidity#9622 (comment)

Code Used

object "RecursionStackOverflow" {
    code {
        datacopy(0, dataoffset("Runtime"), datasize("Runtime"))
        return(0, datasize("Runtime"))
    }
    object "Runtime" {
    code {

        let currentMemoryFrame := 4096 // or whatever memory offset is beyond what the rest of the code uses
        // in more complex cases this will have to use some full-blown memory management mechanism
        // set call arguments:
        mstore(add(currentMemoryFrame, 0x20), 0) // first argument
        mstore(add(currentMemoryFrame, 0x40), 0) // second argument
        // MEMORY_FRAME_POINTER
        mstore(0x20, currentMemoryFrame)

        eval()

        // fetch return values
        let end := mload(add(currentMemoryFrame,  0x60))
        let response := mload(add(currentMemoryFrame,  0x80))
        
        function eval() {
            {
                // fetch current memory frame
                let _currentMemoryFrame := mload(0x20)
                // fetch arguments
                let data_ptr := mload(add(_currentMemoryFrame, 0x20))
                let env_ptr := mload(add(_currentMemoryFrame, 0x40))

                let stepcount := mload(0)
                if gt(stepcount, 169) { mstore(0, stepcount) return(0, 32) }
                mstore(0, add(stepcount, 1))
                
                let rootid := 3

                switch rootid
                
                // number
                case 1 {

                }
                
                // function
                case 3 {

                }
                
                default {

                }

                // prepare memory frame for the next recursive call
                let nextMemoryFrame := add(_currentMemoryFrame, 0xa0)
                // save the current memory frame pointer in the next memory frame
                mstore(nextMemoryFrame, _currentMemoryFrame)
                // set arguments for the next recursive call
                mstore(add(nextMemoryFrame, 0x20), data_ptr)
                mstore(add(nextMemoryFrame, 0x40), env_ptr)
                // update memory frame for recursive call
                mstore(0x20, nextMemoryFrame)
            } // The entire stack should be popped at the end of the block. Note that the Yul optimizer must be enabled for that to work.
            // it's important that there is not a single local variable in scope here, but everything is stored in memory instead
            eval()
            {
                // fetch memory frame of the recursive call
                let recursiveCallMemoryFramePointer := mload(0x20)
                // fetch our own memory frame
                let currentMemoryFramePointer := mload(recursiveCallMemoryFramePointer)
                // fetch the return values of the recursive call
                let ee := mload(add(recursiveCallMemoryFramePointer, 0x60))
                let rr := mload(add(recursiveCallMemoryFramePointer, 0x80))
                // restore to original memory frame pointer
                mstore(0x20, currentMemoryFramePointer)

                let end_ptr, result_ptr
                /// ... further computation calculating end_ptr and result_ptr
                
                // store our return values
                mstore(add(currentMemoryFramePointer, 0x60), end_ptr)
                mstore(add(currentMemoryFramePointer, 0x80), result_ptr)
            }
        }
    
    }}
}

Solc.js 0.7.0

607c8061000f600039806000f350fe6000611020526000611040526110006020526017601b565b607b565b602080518181015160408201516000805160a9811115603b578082528582f35b6001810182525060a084018481528360c08601528260e086015280865250605f601b565b845151935083855280606085015280608085015250505050505b565b

Solc 0.7.0

solc --strict-assembly --optimize --optimize-runs=200 contracts/recursive_test.sol

With out without the unnamed blocks {} there was no compilation difference.

======= contracts/taylor_v2_tay.sol (EVM) =======

Pretty printed source:
object "RecursionStackOverflow" {
    code {
        {
            let _1 := datasize("Runtime")
            datacopy(0, dataoffset("Runtime"), _1)
            return(0, _1)
        }
    }
    object "Runtime" {
        code {
            {
                mstore(4128, 0)
                mstore(4160, 0)
                mstore(0x20, 4096)
                eval()
            }
            function eval()
            {
                let _1 := 0x20
                let _currentMemoryFrame := mload(_1)
                let data_ptr := mload(add(_currentMemoryFrame, _1))
                let env_ptr := mload(add(_currentMemoryFrame, 0x40))
                let _2 := 0
                let stepcount := mload(_2)
                if gt(stepcount, 169)
                {
                    mstore(_2, stepcount)
                    return(_2, _1)
                }
                mstore(_2, add(stepcount, 1))
                let nextMemoryFrame := add(_currentMemoryFrame, 0xa0)
                mstore(nextMemoryFrame, _currentMemoryFrame)
                mstore(add(_currentMemoryFrame, 192), data_ptr)
                mstore(add(_currentMemoryFrame, 224), env_ptr)
                mstore(_1, nextMemoryFrame)
                eval()
                let currentMemoryFramePointer := mload(mload(_1))
                mstore(_1, currentMemoryFramePointer)
                mstore(add(currentMemoryFramePointer, 0x60), _2)
                mstore(add(currentMemoryFramePointer, 0x80), _2)
            }
        }
    }
}


Binary representation:
607c8061000f600039806000f350fe6000611020526000611040526110006020526017601b565b607b565b602080518181015160408201516000805160a9811115603b578082528582f35b6001810182525060a084018481528360c08601528260e086015280865250605f601b565b845151935083855280606085015280608085015250505050505b565b

Text representation:
  dataSize(sub_0)
    /* "contracts/taylor_v2_tay.sol":88:107   */
  dup1
  dataOffset(sub_0)
    /* "contracts/taylor_v2_tay.sol":62:63   */
  0x00
    /* "contracts/taylor_v2_tay.sol":53:108   */
  codecopy
    /* "contracts/taylor_v2_tay.sol":127:146   */
  dup1
    /* "contracts/taylor_v2_tay.sol":62:63   */
  0x00
    /* "contracts/taylor_v2_tay.sol":117:147   */
  return
  pop
stop

sub_0: assembly {
        /* "contracts/taylor_v2_tay.sol":474:475   */
      0x00
        /* "contracts/taylor_v2_tay.sol":443:472   */
      0x1020
        /* "contracts/taylor_v2_tay.sol":436:476   */
      mstore
        /* "contracts/taylor_v2_tay.sol":474:475   */
      0x00
        /* "contracts/taylor_v2_tay.sol":510:539   */
      0x1040
        /* "contracts/taylor_v2_tay.sol":503:543   */
      mstore
        /* "contracts/taylor_v2_tay.sol":223:227   */
      0x1000
        /* "contracts/taylor_v2_tay.sol":467:471   */
      0x20
        /* "contracts/taylor_v2_tay.sol":603:635   */
      mstore
        /* "contracts/taylor_v2_tay.sol":645:651   */
      tag_1
      tag_2
      jump	// in
    tag_1:
        /* "contracts/taylor_v2_tay.sol":820:3431   */
      jump(tag_3)
    tag_2:
        /* "contracts/taylor_v2_tay.sol":950:954   */
      0x20
      dup1
        /* "contracts/taylor_v2_tay.sol":944:955   */
      mload
        /* "contracts/taylor_v2_tay.sol":950:954   */
      dup2
        /* "contracts/taylor_v2_tay.sol":1033:1052   */
      dup2
        /* "contracts/taylor_v2_tay.sol":1029:1059   */
      add
        /* "contracts/taylor_v2_tay.sol":1023:1060   */
      mload
        /* "contracts/taylor_v2_tay.sol":1123:1127   */
      0x40
        /* "contracts/taylor_v2_tay.sol":1102:1121   */
      dup3
        /* "contracts/taylor_v2_tay.sol":1098:1128   */
      add
        /* "contracts/taylor_v2_tay.sol":1092:1129   */
      mload
        /* "contracts/taylor_v2_tay.sol":1170:1171   */
      0x00
      dup1
        /* "contracts/taylor_v2_tay.sol":1164:1172   */
      mload
        /* "contracts/taylor_v2_tay.sol":1206:1209   */
      0xa9
        /* "contracts/taylor_v2_tay.sol":1195:1204   */
      dup2
        /* "contracts/taylor_v2_tay.sol":1192:1210   */
      gt
        /* "contracts/taylor_v2_tay.sol":1189:1191   */
      iszero
      tag_5
      jumpi
        /* "contracts/taylor_v2_tay.sol":1223:1232   */
      dup1
        /* "contracts/taylor_v2_tay.sol":1170:1171   */
      dup3
        /* "contracts/taylor_v2_tay.sol":1213:1233   */
      mstore
        /* "contracts/taylor_v2_tay.sol":950:954   */
      dup6
        /* "contracts/taylor_v2_tay.sol":1170:1171   */
      dup3
        /* "contracts/taylor_v2_tay.sol":1234:1247   */
      return
        /* "contracts/taylor_v2_tay.sol":1189:1191   */
    tag_5:
        /* "contracts/taylor_v2_tay.sol":1291:1292   */
      0x01
        /* "contracts/taylor_v2_tay.sol":1280:1289   */
      dup2
        /* "contracts/taylor_v2_tay.sol":1276:1293   */
      add
        /* "contracts/taylor_v2_tay.sol":1170:1171   */
      dup3
        /* "contracts/taylor_v2_tay.sol":1266:1294   */
      mstore
      pop
        /* "contracts/taylor_v2_tay.sol":1746:1750   */
      0xa0
        /* "contracts/taylor_v2_tay.sol":1725:1744   */
      dup5
        /* "contracts/taylor_v2_tay.sol":1721:1751   */
      add
        /* "contracts/taylor_v2_tay.sol":1874:1893   */
      dup5
        /* "contracts/taylor_v2_tay.sol":1857:1872   */
      dup2
        /* "contracts/taylor_v2_tay.sol":1850:1894   */
      mstore
        /* "contracts/taylor_v2_tay.sol":2007:2015   */
      dup4
        /* "contracts/taylor_v2_tay.sol":1979:2005   */
      0xc0
        /* "contracts/taylor_v2_tay.sol":1725:1744   */
      dup7
        /* "contracts/taylor_v2_tay.sol":1979:2005   */
      add
        /* "contracts/taylor_v2_tay.sol":1972:2016   */
      mstore
        /* "contracts/taylor_v2_tay.sol":2068:2075   */
      dup3
        /* "contracts/taylor_v2_tay.sol":2040:2066   */
      0xe0
        /* "contracts/taylor_v2_tay.sol":1725:1744   */
      dup7
        /* "contracts/taylor_v2_tay.sol":2040:2066   */
      add
        /* "contracts/taylor_v2_tay.sol":2033:2076   */
      mstore
        /* "contracts/taylor_v2_tay.sol":2164:2179   */
      dup1
        /* "contracts/taylor_v2_tay.sol":950:954   */
      dup7
        /* "contracts/taylor_v2_tay.sol":2151:2180   */
      mstore
      pop
        /* "contracts/taylor_v2_tay.sol":2464:2470   */
      tag_6
      tag_2
      jump	// in
    tag_6:
        /* "contracts/taylor_v2_tay.sol":950:954   */
      dup5
        /* "contracts/taylor_v2_tay.sol":2603:2614   */
      mload
        /* "contracts/taylor_v2_tay.sol":2710:2748   */
      mload
        /* "contracts/taylor_v2_tay.sol":2677:2748   */
      swap4
      pop
        /* "contracts/taylor_v2_tay.sol":3055:3080   */
      dup4
        /* "contracts/taylor_v2_tay.sol":950:954   */
      dup6
        /* "contracts/taylor_v2_tay.sol":3042:3081   */
      mstore
        /* "contracts/taylor_v2_tay.sol":1170:1171   */
      dup1
        /* "contracts/taylor_v2_tay.sol":3316:3320   */
      0x60
        /* "contracts/taylor_v2_tay.sol":3289:3314   */
      dup6
        /* "contracts/taylor_v2_tay.sol":3285:3321   */
      add
        /* "contracts/taylor_v2_tay.sol":3278:3331   */
      mstore
        /* "contracts/taylor_v2_tay.sol":1170:1171   */
      dup1
        /* "contracts/taylor_v2_tay.sol":3386:3390   */
      0x80
        /* "contracts/taylor_v2_tay.sol":3359:3384   */
      dup6
        /* "contracts/taylor_v2_tay.sol":3355:3391   */
      add
        /* "contracts/taylor_v2_tay.sol":3348:3404   */
      mstore
      pop
      pop
      pop
      pop
      pop
        /* "contracts/taylor_v2_tay.sol":836:3431   */
    tag_4:
      jump	// out
    tag_3:
}

solc --optimize --optimize-runs=200 -o build --bin --ast-json --asm contracts/recursive_test_wrap.sol

  • with Yul code wrapped in a Solidity contract, in the fallback function.
608060405234801561001057600080fd5b5060c18061001f6000396000f3fe6080604052348015600f57600080fd5b506000611020526000611040526110006020526028602c565b6089565b602080518181015160408201516000805160a9811115604c578082528582f35b600101815260a0840184815260c0850184905260e085018390528552606e602c565b84515193508385528060608501528060808501525050505050565b00fea26469706673582212204a97976767bb51b7d75b1a59cc55a38a63ce7595a31ea94f0b5e78dbe00a3e4f64736f6c63430007000033

    /* "contracts/taylor_recursion.sol":263:3592  contract RecursionStackOverflow {... */
  mstore(0x40, 0x80)
  callvalue
  dup1
  iszero
  tag_1
  jumpi
  0x00
  dup1
  revert
tag_1:
  pop
  dataSize(sub_0)
  dup1
  dataOffset(sub_0)
  0x00
  codecopy
  0x00
  return
stop

sub_0: assembly {
        /* "contracts/taylor_recursion.sol":263:3592  contract RecursionStackOverflow {... */
      mstore(0x40, 0x80)
      callvalue
      dup1
      iszero
      tag_3
      jumpi
      0x00
      dup1
      revert
    tag_3:
      pop
        /* "contracts/taylor_recursion.sol":633:634  0 */
      0x00
        /* "contracts/taylor_recursion.sol":602:631  add(currentMemoryFrame, 0x20) */
      0x1020
        /* "contracts/taylor_recursion.sol":595:635  mstore(add(currentMemoryFrame, 0x20), 0) */
      mstore
        /* "contracts/taylor_recursion.sol":633:634  0 */
      0x00
        /* "contracts/taylor_recursion.sol":669:698  add(currentMemoryFrame, 0x40) */
      0x1040
        /* "contracts/taylor_recursion.sol":662:702  mstore(add(currentMemoryFrame, 0x40), 0) */
      mstore
        /* "contracts/taylor_recursion.sol":382:386  4096 */
      0x1000
        /* "contracts/taylor_recursion.sol":626:630  0x20 */
      0x20
        /* "contracts/taylor_recursion.sol":762:794  mstore(0x20, currentMemoryFrame) */
      mstore
        /* "contracts/taylor_recursion.sol":804:810  eval() */
      tag_6
      tag_7
      jump	// in
    tag_6:
        /* "contracts/taylor_recursion.sol":979:3578  function eval() {... */
      jump(tag_8)
    tag_7:
        /* "contracts/taylor_recursion.sol":1106:1110  0x20 */
      0x20
      dup1
        /* "contracts/taylor_recursion.sol":1100:1111  mload(0x20) */
      mload
        /* "contracts/taylor_recursion.sol":1106:1110  0x20 */
      dup2
        /* "contracts/taylor_recursion.sol":1189:1208  _currentMemoryFrame */
      dup2
        /* "contracts/taylor_recursion.sol":1185:1215  add(_currentMemoryFrame, 0x20) */
      add
        /* "contracts/taylor_recursion.sol":1179:1216  mload(add(_currentMemoryFrame, 0x20)) */
      mload
        /* "contracts/taylor_recursion.sol":1279:1283  0x40 */
      0x40
        /* "contracts/taylor_recursion.sol":1258:1277  _currentMemoryFrame */
      dup3
        /* "contracts/taylor_recursion.sol":1254:1284  add(_currentMemoryFrame, 0x40) */
      add
        /* "contracts/taylor_recursion.sol":1248:1285  mload(add(_currentMemoryFrame, 0x40)) */
      mload
        /* "contracts/taylor_recursion.sol":1326:1327  0 */
      0x00
      dup1
        /* "contracts/taylor_recursion.sol":1320:1328  mload(0) */
      mload
        /* "contracts/taylor_recursion.sol":1362:1365  169 */
      0xa9
        /* "contracts/taylor_recursion.sol":1351:1360  stepcount */
      dup2
        /* "contracts/taylor_recursion.sol":1348:1366  gt(stepcount, 169) */
      gt
        /* "contracts/taylor_recursion.sol":1345:1347  if */
      iszero
      tag_10
      jumpi
        /* "contracts/taylor_recursion.sol":1379:1388  stepcount */
      dup1
        /* "contracts/taylor_recursion.sol":1326:1327  0 */
      dup3
        /* "contracts/taylor_recursion.sol":1369:1389  mstore(0, stepcount) */
      mstore
        /* "contracts/taylor_recursion.sol":1106:1110  0x20 */
      dup6
        /* "contracts/taylor_recursion.sol":1326:1327  0 */
      dup3
        /* "contracts/taylor_recursion.sol":1390:1403  return(0, 32) */
      return
        /* "contracts/taylor_recursion.sol":1345:1347  if */
    tag_10:
        /* "contracts/taylor_recursion.sol":1447:1448  1 */
      0x01
        /* "contracts/taylor_recursion.sol":1432:1449  add(stepcount, 1) */
      add
        /* "contracts/taylor_recursion.sol":1422:1450  mstore(0, add(stepcount, 1)) */
      dup2
      mstore
        /* "contracts/taylor_recursion.sol":1902:1906  0xa0 */
      0xa0
        /* "contracts/taylor_recursion.sol":1877:1907  add(_currentMemoryFrame, 0xa0) */
      dup5
      add
        /* "contracts/taylor_recursion.sol":2006:2050  mstore(nextMemoryFrame, _currentMemoryFrame) */
      dup5
      dup2
      mstore
        /* "contracts/taylor_recursion.sol":2135:2161  add(nextMemoryFrame, 0x20) */
      0xc0
      dup6
      add
        /* "contracts/taylor_recursion.sol":2128:2172  mstore(add(nextMemoryFrame, 0x20), data_ptr) */
      dup5
      swap1
      mstore
        /* "contracts/taylor_recursion.sol":2196:2222  add(nextMemoryFrame, 0x40) */
      0xe0
      dup6
      add
        /* "contracts/taylor_recursion.sol":2189:2232  mstore(add(nextMemoryFrame, 0x40), env_ptr) */
      dup4
      swap1
      mstore
        /* "contracts/taylor_recursion.sol":2307:2336  mstore(0x20, nextMemoryFrame) */
      dup6
      mstore
        /* "contracts/taylor_recursion.sol":2617:2623  eval() */
      tag_11
      tag_7
      jump	// in
    tag_11:
        /* "contracts/taylor_recursion.sol":1106:1110  0x20 */
      dup5
        /* "contracts/taylor_recursion.sol":2753:2764  mload(0x20) */
      mload
        /* "contracts/taylor_recursion.sol":2860:2898  mload(recursiveCallMemoryFramePointer) */
      mload
        /* "contracts/taylor_recursion.sol":2827:2898  let currentMemoryFramePointer := mload(recursiveCallMemoryFramePointer) */
      swap4
      pop
        /* "contracts/taylor_recursion.sol":3205:3230  currentMemoryFramePointer */
      dup4
        /* "contracts/taylor_recursion.sol":1106:1110  0x20 */
      dup6
        /* "contracts/taylor_recursion.sol":3192:3231  mstore(0x20, currentMemoryFramePointer) */
      mstore
        /* "contracts/taylor_recursion.sol":1326:1327  0 */
      dup1
        /* "contracts/taylor_recursion.sol":3466:3470  0x60 */
      0x60
        /* "contracts/taylor_recursion.sol":3439:3464  currentMemoryFramePointer */
      dup6
        /* "contracts/taylor_recursion.sol":3435:3471  add(currentMemoryFramePointer, 0x60) */
      add
        /* "contracts/taylor_recursion.sol":3428:3481  mstore(add(currentMemoryFramePointer, 0x60), end_ptr) */
      mstore
        /* "contracts/taylor_recursion.sol":1326:1327  0 */
      dup1
        /* "contracts/taylor_recursion.sol":3536:3540  0x80 */
      0x80
        /* "contracts/taylor_recursion.sol":3509:3534  currentMemoryFramePointer */
      dup6
        /* "contracts/taylor_recursion.sol":3505:3541  add(currentMemoryFramePointer, 0x80) */
      add
        /* "contracts/taylor_recursion.sol":3498:3554  mstore(add(currentMemoryFramePointer, 0x80), result_ptr) */
      mstore
      pop
      pop
      pop
      pop
      pop
        /* "contracts/taylor_recursion.sol":995:3578  {... */
      jump	// out
    tag_8:
        /* "contracts/taylor_recursion.sol":263:3592  contract RecursionStackOverflow {... */
      stop

    auxdata: 0xa26469706673582212204a97976767bb51b7d75b1a59cc55a38a63ce7595a31ea94f0b5e78dbe00a3e4f64736f6c63430007000033
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment