check.py

def decode_instruction(code, PC):
  pass

def next_pc(instruction):
  pass

class Subroutine:
  begin
  end
  blocks = {}
  
class Block:
  begin
  end
  jumpdest = False
  
def find_subroutines(code):
  subs = {}
  current_sub = Subroutine()
  current_sub.begin = -1
  PC = 0
  while PC < len(code):
    instr = decode_instruction(code, PC)
    if instr is BEGINSUB:
      current_sub.end = PC - 1
      subs[current_sub.begin] = current_sub
      current_sub = Subroutine()
      current_sub.begin = PC
    PC += 1
  current_sub.end = PC - 1
  subs[current_sub.begin] = current_sub
  return subs

def construct_blocks(code, sub):
  current_block = None
  PC = sub.begin
  while PC <= sub.end:
    current_instr = decode_instruction(code, PC)
    next_PC = next_pc(current_instr)
    next_instr = decode_instruction(code, next_PC)
    if current_block is None:
      current_block = Block()
      current_block.begin = PC
    if instr is JUMPDEST:
      if PC == current_block.begin:
        # Mark the block as a valid jump destination.
        current_block.jumpdest = True
      else:
        # Create new block.
        current_block.end = PC - 1
        sub.blocks[current_block.begin] = current_block
        current_block = Block()
        current_block.begin = PC
        current_block.jumpdest = True
    if current_instr in (JUMP, JUMPI, JUMPV) or next_instr is JUMPDEST:
      current_block.end = PC
      sub.blocks[current_block.begin] = current_block
      current_block = Block()
      current_block.begin = next_PC
      
     
      


Split the code into subroutines
This pass will need to create a list of all subroutines by saving theirs ENTRYSUB code location.
The main entry point will create uncallable main subroutine.
For each subroutine:
Split the subroutine code into blocks
This pass creates code blocks (also called basic blocks) by creating a list of basic blocks’ locations of first and last instruction. The split points are: JUMPDEST (first instruction of a block), JUMPTO, JUMPIF, JUMPV (last instructions of a block).
A block can start with: JUMPDEST, ENTRYSUB, instruction directly after JUMPIF.
A block can end with: JUMPTO, JUMPIF, RETURNSUB, instruction directly before JUMPDEST.
For each block:
Calculate block’s min (Min), max (Max), diff (D) stack size.
This pass iterates over the block’s instructions and remembers max and min stack size. The diff stack size is the size of the stack after the last instruction. The pass assumes that the stack size at the block entry is 0 so all the values calculates are relative.
Create block jump graph edges.
Save the possible jumps from the given basic block by analysing the last instruction of a basic block.
ossible jumps from the given basic block by analysing the last iCreate block jump graph edges.
Save the pnstruction of a basic block.
Visit each block jump graph node
Set the frame size FS = 0, max frame size FSMax = 0
Set first visiting block B = entry block
Visit B:
If visiting the block for the first time save the frame size.
If visiting the block not the first time compare the frame size with the saved one. If different - subroutine is invalid.
If FS + Min < 0 => subroutine invalid.
If FS + Max > 1024 => subroutine invalid.
FSMax = max(FSMax, FS + Max)
FS += D
For each connected block B:
	Visit B
At this point we visited all accessible blocks and we know that is the max frame size for the subroutine.
(Optional) Analysis of subroutine call graph