Patch: eliminate 32 KiB bytecode limit from MTASC

[Tristan Schmelcher-3]

Hello fellow MTASC users and developers,

I work in a team at Google on one of our Flash-based products, and we use MTASC for building it. Occasionally though we run up against the infamous 32 KiB limit on class bytecode. Recently I took it upon myself to fix it. The patch is attached.

As many of you probably know, the 32 KiB limit stems from the fact that jump offsets in the AS2 bytecode format are only 16-bit, which means that a jump instruction and its destination cannot be separated by more than about 32 KiB of bytecode. Since every class definition requires a jump that crosses the entire class's code, no class can currently be larger than 32 KiB.

Our solution is to repeatedly split any overlength jumps by inserting "jump islands" between them. A "jump island" consists of two unconditional jump instructions; one that jumps the rest of the way and one right before it that jumps over that one. All locations are considered viable candidates for a jump island (which testing thus far shows to be safe), but we avoid placing jump islands inside nested functions whenever possible (because that would be slightly less efficient); if we were forced to, we note that in the output.

The changes are highly self-contained and very well-commented. There is also a new "-32k-limit" option to force the old behaviour. The patch was created against yesterday's CVS snapshot. You apply it the usual way (patch -p1 < FILE).

Example compiler output:

Warning: Class <your class name here> has 32 KiB or more of bytecode, which is not supported by older MTASC versions.

Note: Bytecode sequence contains one or more overlength jumps; attempting jump island insertion.
Note: Jump island insertion successful with 1 island(s) created.

If you find the patch acceptable, we would be happy if you would accept it into the official MTASC codebase.

Regards,

Tristan Schmelcher

[mtasc-no32klimit.patch]

---

diff -urN -x CVS ocaml.orig/mtasc/genSwf.ml ocaml/mtasc/genSwf.ml
--- ocaml.orig/mtasc/genSwf.ml 2008-01-07 18:04:23.929159000 -0800
+++ ocaml/mtasc/genSwf.ml 2008-01-08 10:15:28.385705000 -0800
@@ -1291,6 +1291,261 @@
  in
  loop (List.rev path)
 
+(* The AS2 bytecode language requires jump offsets to be 16-bit. As a result,
+   we have to eliminate overlength jumps. We do this by inserting "islands";
+   i.e., the offending jump gets redirected to a new jump that we insert
+   partway to the destination, and that jump goes the rest of the way (or to
+   another jump, etc.). A second additional jump is inserted immediately before
+   the island, which skips to the next instruction. Naturally, all other jump
+   indices must then be adjusted. We endeavour to place jump islands at somewhat
+   efficient locations (specifically, outside of nested function definitions),
+   though there is no guarantee that we accomplish this with a minimal number of
+   islands.
+
+   Note that jump island insertion is not always possible. In such cases this
+   algorithm will run forever. However, this basically never happens in
+   practice. *)
+(* This function requires tons of helper functions which are all very different
+   from the rest of the code for class generation, so we stick them all inside
+   this definition to keep it self-contained. *)
+let eliminate_overlength_jumps =
+ let maybe_get_jump_target act =
+ match act with
+ AJump target -> Some target
+ | ACondJump target -> Some target
+ | _ -> None
+ in let get_jump_target act =
+ match (maybe_get_jump_target act) with
+ Some target -> target
+ | None -> raise (Error "Not a jump instruction")
+ in let set_jump_target acts i target =
+ match (DynArray.get acts i) with
+ AJump _ -> DynArray.set acts i (AJump target)
+ | ACondJump _ -> DynArray.set acts i (ACondJump target)
+ | _ -> raise (Error "Not a jump instruction")
+ in let find_overlength_jump acts =
+ (* Returns the index in "acts" of the first overlength jump, if any. *)
+ (* We tail-recursively iterate over the actions and check each jump's size. *)
+ let rec helper acts i =
+ if i == (DynArray.length acts) - 1 then None (* end of array; no overlength jumps *)
+ else
+ let maybe_target = maybe_get_jump_target (DynArray.get acts i)
+ in match maybe_target with
+ None -> helper acts (i + 1) (* not a jump; continue *)
+ | Some target ->
+ let size = ActionScript.jump_index_to_size acts i target in
+ if size < -0x8000 || size > 0x7FFF
+ (* Uncomment to stick jump islands all over the place for testing.
+   (Must be larger than the largest instruction in the code.) *)
+ (* if size < -0x106 || size > 0x100 *)
+ then Some i (* overlength jump *)
+ else helper acts (i + 1) (* not overlength; continue *)
+ in helper acts 0
+ in let fixup_target i target island_index island_length =
+ (* Adjusts the instruction offset "target" for the instruction at index "i" to
+   account for an island having been inserted at "island_index" of length
+   "island_length". Note: given the choice, we jump to the beginning of
+   the island instead of the end, since we want to avoid putting islands inside
+   of nested functions. *)
+ if i < island_index && (i + target + 1) > island_index then
+ (* Jump goes forwards from before the island to after/into it; increase
+   by length of island. *)
+ target + island_length
+ else if i >= (island_index + island_length) && (i + target + 1) < (island_index + island_length) then
+ (* Jump goes backwards from after the island to before/into it; decrease
+   by length of island (i.e., increase magnitude). *)
+ target - island_length
+ else
+ (* Jump does not intersect with island; no change. *)
+ target
+ in let fixup_instruction_targets acts island_index island_length exempt_index =
+ (* Iterates through an action sequence and fixes all instruction offsets
+   to account for new code having been inserted at island_index and of length
+   island_length, except for instructions inside it or at exempt_index. *)
+ let helper i =
+ if (i >= island_index && i < island_index + island_length) || i == exempt_index then function _ -> ()
+ else function
+ | AJump target ->
+ DynArray.set acts i (AJump (fixup_target i target island_index island_length))
+ | ACondJump target ->
+ DynArray.set acts i (ACondJump (fixup_target i target island_index island_length))
+ | AFunction f ->
+ DynArray.set acts i (AFunction { f with f_codelen = fixup_target i f.f_codelen island_index island_length })
+ | AFunction2 f ->
+ DynArray.set acts i (AFunction2 { f with f2_codelen = fixup_target i f.f2_codelen island_index island_length })
+ | AWith size ->
+ DynArray.set acts i (AWith (fixup_target i size island_index island_length))
+ | ATry t ->
+ let fixed_trylen = fixup_target i t.tr_trylen island_index island_length in
+ let fixed_catchlen =
+ match t.tr_catchlen with
+ None -> None
+ | Some catchlen -> Some (fixup_target (i + fixed_trylen) catchlen island_index island_length) in
+ let fixed_finallylen =
+ match t.tr_finallylen with
+ None -> None
+ | Some finallylen -> Some (fixup_target (i + fixed_trylen + (match fixed_catchlen with None -> 0 | Some i -> i)) finallylen island_index island_length) in
+ DynArray.set acts i (ATry { t with tr_trylen = fixed_trylen; tr_catchlen = fixed_catchlen; tr_finallylen = fixed_finallylen })
+ | _ ->
+ ()
+ in
+ DynArray.iteri helper acts
+ in let get_function_target act =
+ (* Returns the jump index needed to get to the end of the given function
+   instruction's definition, or 0 if not a function instruction. *)
+ match act with
+ AFunction f -> f.f_codelen
+ | AFunction2 f -> f.f2_codelen
+ | _ -> 0
+ in let jump_instruction_size =
+ (* Constant value equal to the size of an unconditional jump instruction in
+   bytes. *)
+ ActionScript.action_length (AJump 0)
+ in let insert_jump_island acts i orig_target island_index =
+ (* Inserts a jump island at "island_index" for the jump at "i" of length
+   "orig_target". *)
+ (* "target" is relative to the instruction after "i", and "insert" inserts
+   _before_ the given index, so that's -1, but the hop jump has to come first,
+   so that's +1, so this is just island_index - i. *)
+ let target = island_index - i in (* new target for the jump *)
+ (* Compute the target value for the island's main jump. We will have gone
+   "target" instructions worth so far (so -target), but the number of
+   instructions to cover will have increased by 2 (so +2 if forward, -2 if
+   back). However, the target is relative to the instruction _after_ the new
+   jump (so -1). *)
+ let island_target = orig_target - target - 1 + if orig_target > 0 then 2 else -2 in
+ (* Now actually insert the jump island. *)
+ DynArray.insert acts island_index (AJump 1); (* hop jump *)
+ DynArray.insert acts (island_index + 1) (AJump island_target); (* main jump *)
+ (* Now change the original jump. Note that if the jump goes backwards then
+   we've put the island before it so the index has changed. *)
+ let new_i = if orig_target > 0 then i else i+2 in
+ set_jump_target acts new_i target;
+ (* Now iterate through the code and fix the targets of all other
+   instructions. *)
+ fixup_instruction_targets acts island_index 2 new_i
+ in let is_region_larger_than acts start stop compare_to =
+ (* Checks whether or not the sum of action lengths in indices [start, end) is
+   greater than the given number. *)
+ let rec helper acts curr stop acc compare_to =
+ if acc > compare_to then true (* already larger *)
+ else if curr >= stop then false (* done. never became larger so must not be *)
+ else helper acts (curr+1) stop (acc+(ActionScript.action_length (DynArray.get acts curr))) compare_to
+ in helper acts start stop 0 compare_to
+ in let choose_nice_jump_island_index_in_range acts start stop is_forward_not_backward =
+ (* Chooses an index (if any) in the range (start, end] where we can usefully
+   insert a jump island for a jump between "start" and "end" (in either
+   direction) without putting the island inside a nested function definition,
+   which would typically be mildly inefficient.
+
+   Specifically, this considers locations that are not inside a nested
+   function block and which would decrease the largest jump size involved.
+   From among those such points, it chooses the one closest to the halfway
+   point. This will not always result in a minimal number of jumps, but no
+   one will really care.
+
+   It is _not_ a requirement that "start" and "end" are in the same function,
+   and indeed there are cases where that property will not hold, b/c even
+   if we give up on a nice island we will still call this for future island
+   insertion, yet at that point some jumps in the code will span
+   function definitions. *)
+ (* Note: curr here is the index to examine as a potential place _after_ which
+   to insert an island, which is different from the semantics above. *)
+ let rec helper acts start stop curr best =
+ if curr >= stop then best
+ else
+ (* Check if this index is the start of a function. If so, we skip past
+   it. *)
+ let skip = get_function_target (DynArray.get acts curr) in
+ if skip > 0 then
+ (* This is a function. Skip to the end. *)
+ helper acts start stop (curr + skip) best
+ else
+ (* Else we could safely insert an island here. See if that will actually
+   decrease the jump sizes. If we didn't bother with this, we'd get
+   into an infinite loop whenever there's a function that we can't
+   jump over, because we can always add useless jump islands at the
+   edges. *)
+ let useful = if is_forward_not_backward then
+ (* Jump goes from start to end. Redirecting it to the island's main
+   jump will leave out the instructions after the island but add in
+   the island's hop jump. Thus the jump size decreases iff the former
+   is larger than the latter. Further, the island's main jump gets to
+   leave out all instructions before the island and does not add in
+   any, so that decreases iff there is at least one instruction before
+   the island. *)
+ (is_region_larger_than acts (curr+1) stop jump_instruction_size)
+ && (curr > start)
+ else
+ (* Jump goes from end to start. Redirecting it to the island's main
+   jump will leave out the instructions before the island but add in
+   the island's main jump. Thus the jump size decreases iff the
+   former is larger than the latter. Further, the island's main jump
+   gets to leave out all instructions after the island, but adds in
+   itself and the hop jump before it, so that decreases iff the
+   former is larger than the latter. *)
+ (is_region_larger_than acts start (curr+1) jump_instruction_size) &&
+ (is_region_larger_than acts (curr+1) (stop+1)
+ (2*jump_instruction_size))
+ in let best =
+ if not useful then
+ best
+ else
+ Some (match best with
+ None -> curr+1
+ | Some best ->
+ if (abs ((stop + start)/2 - best)) >
+ (abs ((stop + start)/2 - (curr+1)))
+ then curr+1 else best)
+ in helper acts start stop (curr+1) best
+ in helper acts start stop start None
+ in let choose_nice_jump_island_index acts i orig_target =
+ (* Like choose_island_index_in_range, but specified in terms of the jump and its
+   target. *)
+ if orig_target > 0 then
+ choose_nice_jump_island_index_in_range acts i (i+orig_target+1) true
+ else
+ choose_nice_jump_island_index_in_range acts (i+orig_target+1) i false
+ in let split_jump acts i =
+ (* Splits the jump in "acts" at index "i" by inserting a jump island partway to
+   the destination. Returns true if it was able to place it outside of any
+   nested functions, or false if it had to place it within one or more. *)
+ let orig_target = get_jump_target (DynArray.get acts i) in (* original jump target *)
+ let (nice, island_index) = match choose_nice_jump_island_index acts i orig_target with
+ None ->
+ (* There is no nice spot to put an island, so just put it in the middle.
+   (This happens if the jump goes across a function of size greater than
+   about 32 KiB.) *)
+ (false, (i + (i + orig_target + 1))/2)
+ | Some i ->
+ (* Use that. *)
+ (true, i)
+ (* For simplicity, we only insert one jump island--regardless of how many are
+   necessary--and leave insertion of additional ones up to the later
+   iterations (since the one we insert will itself be an overlength jump of
+   smaller size). *)
+ in insert_jump_island acts i orig_target island_index;
+ nice
+ in function acts ->
+ (* This is now the actual definition of eliminate_overlength_jumps. *)
+ let rec helper acts count bad_count =
+ let index = find_overlength_jump acts
+ in match index with
+ None ->
+ if count != 0 then prerr_endline ("Note: Jump island insertion successful with " ^ (string_of_int count) ^ " island(s) created" ^ (if bad_count = 0 then "." else " (at least " ^ (string_of_int bad_count) ^ " of them inefficient)."));
+ | Some i ->
+ if count = 0 then begin
+ prerr_endline ("Note: Bytecode sequence contains one or more overlength jumps; attempting jump island insertion.");
+ (* Flush stderr so that the user will always see the above message even if jump island insertion runs forever,
+   which can happen for pathological cases. *)
+ flush stderr
+ end;
+ let nice = split_jump acts i in
+ helper acts (count + 1) (if nice then bad_count else bad_count + 1)
+ in helper acts 0 0
+
+let support_overlength_classes = ref true
+
 let generate file out ~compress exprs =
  let file , linkage =
  (try
@@ -1331,9 +1586,21 @@
  generate_class_code ctx clctx (if !separate then Hashtbl.create 0 else hpackages);
  if !separate then tags := ("__Packages." ^ s_type_path (Class.path clctx),ctx.idents,ctx.ops) :: !tags;
  let size = ActionScript.actions_length ctx.ops in
- if size - ssize >= 1 lsl 15 then failwith ("Class " ^ s_type_path (Class.path clctx) ^ " excess 32K bytecode limit, please split it");
+ if size - ssize >= 1 lsl 15 then
+ begin
+ if !support_overlength_classes then
+ prerr_endline ("Warning: Class " ^ s_type_path (Class.path clctx) ^ " has 32 KiB or more of bytecode, which is not supported by older MTASC versions.")
+ else
+ failwith ("Error: Class " ^ s_type_path (Class.path clctx) ^ " has 32 KiB or more of bytecode; please refactor it or recompile without -32k-limit.");
+ eliminate_overlength_jumps ctx.ops
+ (* Note: It is possible here for the UInt16 parameters in (for example) function/try/catch/finally/with instructions to be overlength too.
+   However, we don't support dealing with that, since it should be way less common in real-world code than even overlength
+   classes, which are already very uncommon. For that same reason, we also don't bother to output nice error messages
+   in such a case; the user will just see an Overflow exception from IO.write_ui16. If we ever do want to check for overlength
+   UInt16's, though, this would be the spot to do it. *)
+ end;
  end;
- ) exprs;
+ ) exprs;
  if not !separate then tags := ("__Packages.MTASC",ctx.idents,ctx.ops) :: !tags;
  (match !(ctx.main) with
  | None ->
@@ -1558,6 +1825,7 @@
  ("-exclude",Arg.String (fun f -> exclude_file f),"<file> : exclude classes listed in file");
  ("-version",Arg.Int (fun n -> version := Some n),": change SWF version (6,7,8,...)");
  ("-trace",Arg.String (fun t -> ftrace := Some t),"<function> : specify a TRACE function");
+ ("-32k-limit",Arg.Unit (fun () -> support_overlength_classes := false),": treat overlength classes (>= 32 KiB of bytecode) as an error");
 ]
 (fun t ->
  if !keep && !header <> None then failwith "-keep cannot be used together with -header";

---

--
MTASC : no more coffee break while compiling

[Scott Hyndman]

wow...thanks!

On 08/01/2008, Tristan Schmelcher <tschmelcher@...> wrote:

Hello fellow MTASC users and developers,

I work in a team at Google on one of our Flash-based products, and we use MTASC for building it. Occasionally though we run up against the infamous 32 KiB limit on class bytecode. Recently I took it upon myself to fix it. The patch is attached.

As many of you probably know, the 32 KiB limit stems from the fact that jump offsets in the AS2 bytecode format are only 16-bit, which means that a jump instruction and its destination cannot be separated by more than about 32 KiB of bytecode. Since every class definition requires a jump that crosses the entire class's code, no class can currently be larger than 32 KiB.

Our solution is to repeatedly split any overlength jumps by inserting "jump islands" between them. A "jump island" consists of two unconditional jump instructions; one that jumps the rest of the way and one right before it that jumps over that one. All locations are considered viable candidates for a jump island (which testing thus far shows to be safe), but we avoid placing jump islands inside nested functions whenever possible (because that would be slightly less efficient); if we were forced to, we note that in the output.

The changes are highly self-contained and very well-commented. There is also a new "-32k-limit" option to force the old behaviour. The patch was created against yesterday's CVS snapshot. You apply it the usual way (patch -p1 < FILE).

Example compiler output:

Warning: Class <your class name here> has 32 KiB or more of bytecode, which is not supported by older MTASC versions.

Note: Bytecode sequence contains one or more overlength jumps; attempting jump island insertion.
Note: Jump island insertion successful with 1 island(s) created.

If you find the patch acceptable, we would be happy if you would accept it into the official MTASC codebase.

Regards,

Tristan Schmelcher

--
MTASC : no more coffee break while compiling

--
MTASC : no more coffee break while compiling

[Nicolas Cannasse]

Tristan Schmelcher a écrit :
> Hello fellow MTASC users and developers,
>
> I work in a team at Google on one of our Flash-based products, and we
> use MTASC for building it. Occasionally though we run up against the
> infamous 32 KiB limit on class bytecode. Recently I took it upon myself
> to fix it. The patch is attached.

Hi Tristan,

Thanks for contributing.

There's also another limit which is the 64KB max. size for all used
identifiers. This a lot more complex to handle since it requires
separating the class(es) into several code blocks, each block with its
own pool of identifiers.

Actually, both limits are already handled correctly by haXe
(http://haxe.org) which is improving several things upon MTASC.

Best,
Nicolas

--
MTASC : no more coffee break while compiling

[Tristan Schmelcher-3]

On Jan 9, 2008 2:10 AM, Nicolas Cannasse <ncannasse@...> wrote:

Tristan Schmelcher a écrit :

> Hello fellow MTASC users and developers,
>
> I work in a team at Google on one of our Flash-based products, and we
> use MTASC for building it. Occasionally though we run up against the
> infamous 32 KiB limit on class bytecode. Recently I took it upon myself
> to fix it. The patch is attached.

Hi Tristan,

Thanks for contributing.

 

My pleasure.

There's also another limit which is the 64KB max. size for all used
identifiers. This a lot more complex to handle since it requires
separating the class(es) into several code blocks, each block with its
own pool of identifiers.

There's also the 64 KiB limit on function/try/catch/finally/with blocks, and maybe more for all I know. My patch doesn't support handling any of that; we'd just get an overflow exception when we go to write out the SWF. I figure that if 32 KiB classes were already rare, then 64 KiB _pieces_ of classes should be astronomically rarer.
 

Actually, both limits are already handled correctly by haXe
( http://haxe.org) which is improving several things upon MTASC.

Interesting. Are there any plans to support AS2 as a front-end to haXe, sort of like how the AS2 bytecode is a possible choice for the compiler output?
 

Best,
Nicolas

--

MTASC : no more coffee break while compiling

--
MTASC : no more coffee break while compiling

[Nicolas Cannasse]

> There's also the 64 KiB limit on function/try/catch/finally/with blocks,
> and maybe more for all I know. My patch doesn't support handling any of
> that; we'd just get an overflow exception when we go to write out the
> SWF. I figure that if 32 KiB classes were already rare, then 64 KiB
> _pieces_ of classes should be astronomically rarer.

Yes, as far as I know nobody has hit the other limits.

But for identifiers, haXe groups all classes into one single swf
actionscript tag. This way it can produce smaller swf. If you have a lot
of code, it's then possible to hit the 64KB identifiers+strings size limit.

>     Actually, both limits are already handled correctly by haXe
>     ( http://haxe.org) which is improving several things upon MTASC.
>
>
> Interesting. Are there any plans to support AS2 as a front-end to haXe,
> sort of like how the AS2 bytecode is a possible choice for the compiler
> output?

That would not make a lot of sense. AS2 is not a very good programming
language, and haXe adds a lot of useful features such as typed arrays,
type inference and automatic delegates creation.

Best,
Nicolas


--
MTASC : no more coffee break while compiling

[Tristan Schmelcher-3]

On Jan 10, 2008 4:13 AM, Nicolas Cannasse <ncannasse@...> wrote:

> There's also the 64 KiB limit on function/try/catch/finally/with blocks,
> and maybe more for all I know. My patch doesn't support handling any of
> that; we'd just get an overflow exception when we go to write out the
> SWF. I figure that if 32 KiB classes were already rare, then 64 KiB
> _pieces_ of classes should be astronomically rarer.

Yes, as far as I know nobody has hit the other limits.

But for identifiers, haXe groups all classes into one single swf
actionscript tag. This way it can produce smaller swf. If you have a lot
of code, it's then possible to hit the 64KB identifiers+strings size limit.

>     Actually, both limits are already handled correctly by haXe
>     ( http://haxe.org) which is improving several things upon MTASC.
>
>
> Interesting. Are there any plans to support AS2 as a front-end to haXe,
> sort of like how the AS2 bytecode is a possible choice for the compiler
> output?

That would not make a lot of sense. AS2 is not a very good programming
language, and haXe adds a lot of useful features such as typed arrays,
type inference and automatic delegates creation.

Looking at the haXe language reference, I agree. It's a much nicer language. I was just hoping it might provide a simple upgrade path for people with existing AS2 projects that are currently on MTASC, that's all. But I suppose that if we'd just be compiling to AS2 bytecode, then there wouldn't be any point in switching anyways.

Best,
Nicolas


--
MTASC : no more coffee break while compiling

--
MTASC : no more coffee break while compiling

[Tristan Schmelcher-3]

I've recently had several inquiries off-list from MTASC users that were asking if I could give them a build of MTASC with my patch applied. So I decided to save myself some time and I started a fork of MTASC on SourceForge at http://sourceforge.net/projects/mtasc/. If anyone needs support for classes with more than 32 KB, you can download my builds from there. Currently I have only uploaded Linux builds, but if there's demand for other platforms then I'll build more.

2008/1/10 Tristan Schmelcher <tschmelcher@...>

On Jan 10, 2008 4:13 AM, Nicolas Cannasse <ncannasse@...> wrote:

> There's also the 64 KiB limit on function/try/catch/finally/with blocks,
> and maybe more for all I know. My patch doesn't support handling any of
> that; we'd just get an overflow exception when we go to write out the
> SWF. I figure that if 32 KiB classes were already rare, then 64 KiB
> _pieces_ of classes should be astronomically rarer.

Yes, as far as I know nobody has hit the other limits.

But for identifiers, haXe groups all classes into one single swf
actionscript tag. This way it can produce smaller swf. If you have a lot
of code, it's then possible to hit the 64KB identifiers+strings size limit.

>     Actually, both limits are already handled correctly by haXe
>     ( http://haxe.org) which is improving several things upon MTASC.
>
>
> Interesting. Are there any plans to support AS2 as a front-end to haXe,
> sort of like how the AS2 bytecode is a possible choice for the compiler
> output?

That would not make a lot of sense. AS2 is not a very good programming
language, and haXe adds a lot of useful features such as typed arrays,
type inference and automatic delegates creation.

Looking at the haXe language reference, I agree. It's a much nicer language. I was just hoping it might provide a simple upgrade path for people with existing AS2 projects that are currently on MTASC, that's all. But I suppose that if we'd just be compiling to AS2 bytecode, then there wouldn't be any point in switching anyways.

Best,
Nicolas


--
MTASC : no more coffee break while compiling

--




--
MTASC : no more coffee break while compiling