Dead code elimination

[ZimM-LostPolygon]

Lately, I was working on dead code elimination in JSIL to decrease the enormouse size of core libraries. Right now, it allows to strip out unused classes, methods, and fields. Of course, it breakes the reflection for everything that was stripped out, but it is possible to avoid that by whitelisting class/member in cofiguration. For a simple console "hello world" app Mono corlib is reduced from 5 MB to 300 kB, and MS corlib reduced from 9.7 MB to 1.3 MB (that's still way too large for a hello-world, have to investigate that further).

It works fairly well for a prototype, but I was thinking - is this really a job JSIL must do itself? Maybe it would make more sense to make stripper in a separate project and just use it as external tool from JSIL. What do you think?

[kg]

If it's possible to do it as an external tool, that's reasonable. I do think dead code elimination probably relies on having a lot of information about the code, though, and extracting that through parsing JSIL output might be difficult. In that case you probably need full access to JSIL's type information and the AST trees for the function bodies.

A middle ground would be for JSIL to have an 'analyzer' API that lets you write your dead code eliminator as some sort of plugin.

[kg]

P.S. one option I've considered in the past is the idea of doing on-demand loading of the actual bodies of type definitions and methods. To loosely describe this:

Right now, you've got a big JS file and each type definition is one big function, and inside that one big function are method definitions, etc.

The new approach would store all those functions as individual strings, perhaps in some sort of compressed or uncompressed archive. At the first moment one of them is needed, it'd be pulled out of the archive and evaluated.

Under normal circumstances, an approach like this would probably only reduce memory usage (and perhaps improve startup times, since the whole file isn't getting parsed), but you could probably also use it for DCE.

Once an app is fully started, you could look at which particular function bodies had been loaded, and combine that with information from static compile-time analysis to get a pretty good picture of what types and methods are actually needed - i.e. this would pick up on type and method usage via reflection, etc. I don't know if you could actually handle reflection automatically, but this would be able to generate warnings about all the call sites where you use reflection APIs.

(Actually, that reminds me - if DCE is implemented, we should set a flag on DCE'd output so any reflection APIs you use generate a warning.)

[ZimM-LostPolygon]

At the moment, the stripper starts at assembly entrypoint method, and then recursively loops through IL instructions searching for references of types, methods, fields etc. When a method is encountered it starts the process again until there are no more new references to anything (I was actually afraid of overflowing the stack that way, but it actually works even on huge core libraries)

The result is a plain list of classes and class members that are somehow referenced in the current application. Only information this process needs is provided by Mono.Cecil already. AST would probably come in handy for removing dead code inside methods, but I'm not sure it's worth even bothering about it for two reasons: 1) the compilers already do quite a good job on removing dead code inside methods 2) modern JS optimizers like UglifyJS and Google Closure can do dead code elimination as well, so maybe it makes sense to support these kind of tools and get free minification + some additional DCE (optimizing JSIL-generated JS code is probably not a great idea, however).

Thinking about the external tool: seems like the only way to make it fully external is to save the stripped assemblies and then feed them to JSIL instead of original ones. This sounds quite a lot of overhead for the saving process, though. API sounds great, but I can't really think about any other usecase for it except for DCE :) A more simple alternative is to make JSIL consume a XML/JSON file with a list of non-stripped classes and members, and then just skip all the others during the JS output process.

On-demand loading sounds like a good idea to me, but I'm really not sure about possible performance of this. If the archive is something like a custom bytecode, then decoding and evaluating a new piece of code might actually take some really small, but noticeable time. For a typical GUI application this would still be perfect, but from my gamedev background, personally, I think it's better to wait a second or two instead of random hiccups when something new is being loaded mid-game.

The reflection APIs already throw or return null when they fail to retrieve type information, so probably it would be enough to produce a warning during the compilation process. Generating a warning in output doesn't makes a lot of sense, as user may actually whitelist a class that'd be otherwise stripped out (but it'd be a good thing to have this as an option, indeed).

[iskiselev]

Stripping dead code sounds as must have feature (I already thought about it and planned to work on it in next month or two). On demand loading is also good. But how particular can be on demand loading that doesn't hit performance? Will it be able to load only part of class (only some methods/fields) and doesn't load even signatures of all other? Currently my ported app with fully translated mscorlib+System.Core use ~250 MB of RAM on PC Chrome and about 600 MB on iPhone. If we will be able not load unused parts of assembly - it will be very good for memory consumption.

[kg]

Language/VM improvements will reduce memory usage a lot, but on-demand loading will definitely help too. Part of the problem is how most modern JS runtimes handle closures; all of the method bodies tend to retain the outer closure (and thus, each other), so we leak a lot more state than we should (there's no reason for that to actually happen, VMs just do it because it's simpler)

On-demand loading shouldn't be that bad; we'll be doing it on first use of the function, at which point the code won't have been JITted anyway. You might get tiny stalls when it happens, but it should largely happen during app/game initialization, and in exchange your startup time should be much shorter.

[ZimM-LostPolygon]

Just commited what I have now: https://github.com/BurntOfferings/JSIL/commit/25a4027e6e9ce98d4ae929e647ec230fd483f50a It's not thoroughly tested yet, but that's a start. If you want to try it, you have to add something like this to the config:

  "AnalyzerSettings": {
    "DeadCodeAnalyzer": {
      "DeadCodeElimination": true,
      "WhiteList": [
        "System\\.Void Foo\\.SomeClass::\\WhiteListedMethod()",
        "Bar\\.Whitelisted\\.Class",
      ]
    }
  }

[kg]

I see you're leveraging logic from Mono.Linker's dead code eliminator, is that right? I think the approach is reasonable, but I dislike the amount of duplication. It would be nice if this could work without doing another complete pass over the whole set of assemblies, and if it could use the JSIL AST instead of consuming raw IL. The ILSpy/Cecil stage of JSIL compiles is already a big, impossible-to-optimize timesink so I would be very unhappy to double the size of it in order to add DCE.

What information do you need on a per-method basis, and a per-type basis, in order to do DCE? Could I provide you an interface that lets you consume that information directly in order to do DCE?

I like the general approach of asking the compiler extensions whether to translate given methods, and I could probably trivially give them the option to do other things too (name mangling/minification seems like one obvious use for these same hooks), so I'm a fan of how you did that (even if I end up making some minor changes there).

[ZimM-LostPolygon]

At the moment I only use the type hierarchy mapper from Mono.Linker. Compile time hit on DCE isn't currently actually that bad - I've just measured it to take 300-400 ms for processing mscorlib+System on my machine. But I agree it would be much nicer to work with the same AST that JSIL itself uses, instead of partially recreating it again inside the plugin.

The information I make use of now is this; Per-type:

1. Inheritance tree.
2. Custom attributes.
3. Static constructor reference. Per-method:
4. List of all references to other types, methods, and fields inside the method (and the types of arguments that are passed to methods).
5. If a method is virtual/override, I need references to all base methods and to all the overrides.
6. Custom attributes. This is of course may (and I'm sure it will) change, but that's it for now. Yes, an interface totally makes sense, so I'll make DCE use it if there will be one.

Also, just a thought - is there any purpose in properties info in the output JS except for reflection? They seem to occupy quite a lot of space, so probably a flag that will just skip all property info from outputing will make some sense.

[kg]

The property info is honored by the runtime implementation, such that if a type T has a property Foo, an instance of T exposes a property named Foo in JS. Generated JS rarely uses the properties, but they're there (primarily for interop at this point, but also to ease debugging)

[Rohansi]

The DCE can eliminate a lot more if it handled static constructors properly. Right now it basically treats all of them as an entry point, even if the type isn't used.

I implemented most if not all of the cases where static constructors are called and the .NET mscorlib was reduced from 3 MB (current DCE) to 12.6 KB for a console application that prints "hello".

[ZimM-LostPolygon]

Does it? As far as I remember, static constructors are only analyzed when the type is encountered the first time, so definitely not treating every static constructor as an entry point.

[Rohansi]

Sorry, I wasn't handling attributes properly. Some static constructors on attributes bring in a ton of stuff.

It might be worth having flags to disable stuff like this. If you aren't going to be reading attributes at runtime there's no point having that extra 3 MB.

[kg]

Ah, the problem is that a method's attributes pull stuff in?

Maybe you could special-case it to only do the attribute analysis if the function uses the reflection APIs?

[iskiselev]

Probably we should check, if JSIgnore could be used with attributes and then provide some config that will strip all BCL attributes?

[Rohansi]

Stripping attributes could work but it doesn't fit into the analyzer API.

More specific proxies would help without causing problems, though. I just added a JSIgnore static constructor to ConsoleProxy and it's back down to 13 KB. Looks like I was wrong about the attributes.

[iskiselev]

If JSIgnore doesn't work correct with attributes in DCE it sounds strange, as I definitely had checked it. I'll look on it.

[iskiselev]

I've tested. Looks like marking Attribute with JSIgnore strip it from output. Here is test case:

using System;
using System.IO;
using System.Linq;
using System.Text.RegularExpressions;
using System.Threading.Tasks;

using JSIL.Meta;

[TestAttribute]
public static class Program
{

    public static void Main(string[] args)
    {

    }

}

[JSIgnore]
public class TestAttribute : Attribute
{
    public TestClass TestValue;

    public TestAttribute()
    {
        TestValue = new TestClass();
    }
}

public class TestClass
{
    public string TestValue;
    public TestClass()
    {
        TestValue = "tt";
    }

}

It even hides another JSIL problem - attributes, marked with JSIgnore are stripped from output, but points where they are applied to another members - are not stripped.

Also, while testing this case, I've found another bug. In next example, TestAttribute is stripped with DCE:

[TestAttribute]
public static class Program
{

    public static void Main(string[] args)
    {

    }

}

public class TestAttribute : Attribute
{
}

Probably it is even good behavior - if only usage of attribute is marking with it, and never type token is loaded - we may strip it or user should add it to white list. On other hand, if we add constructor to the same attribute that will set some filed - it is not stripped. We should check why behavior is different and discuss which is correct.

[Rohansi]

It even hides another JSIL problem - attributes, marked with JSIgnore are stripped from output, but points where they are applied to another members - are not stripped.

This is what I was talking about. The analyzer API only lets you say types/methods/fields are not used, it doesn't let you remove attributes from definitions. JSIL could call MemberCanBeSkipped on them to check if the attribute type was removed, which should fix that. (looks like it does already)

In next example, TestAttribute is stripped with DCE:

This is because entry points start directly at the method and since Main doesn't refer to Program, AddType is never called for it, so no attributes are seen.

[Rohansi]

What was the reasoning behind always including static constructors? It doesn't really cause problems but shouldn't that be the analyzer's decision?

[ZimM-LostPolygon]

Hm, that indeed looks strange as we have that in the analyzer as well: https://github.com/sq/JSIL/blob/master/Compiler/Analyzers/DeadCodeAnalyzer/DeadCodeInfoProvider.cs#L195

[iskiselev]

As far as I remember, JSIL always generate fake .cctor instead of original one to initialize static fields. That's why, DCE check that accepts MemberReference will always return false.

But, we definitely know, that if type is not excluded fully, we must generate its static constructor. It won't affect possibility to exclude full type if there is no reference to it in all other on-excluded parts of program.

Check inside DCE force DCE to include every member, that is referenced inside static constructor of type if there is any reference to that type (as otherwise there will be no reference to static constructor - it is called be environment, not by user).

[Rohansi]

But if nothing references the static fields they don't need to be initialized. It's probably there for correctness because it should be called when accessing members on type and it could have side effects. But this means you can't make an analyzer drop some static constructors because they will still be generated and could access members that were removed.

[iskiselev]

The problem here is that current implementation of DCE doesn't analyze side effects. If anybody will implement it, we may improve DCE by stripping on which we only set values - not only in static constructor, but everywhere in our application. So, I think on current implementation, such work with static constructors is correct. Really, there is no difference with case when instance constructor initialize some members, but we've stripped any method that read from this members.

[iskiselev]

As I know, JSIL itself has some logic for detection side-effect free methods. If it can be used (or updated so that it can be used) in such way, that it will provide information if any method free of side effects (really, we should understand which we mean under side-effect here - is instance method on class that modify only that class side effect free?) - we could try to improve our very simple DCE logic.

[Rohansi]

There's nothing really wrong with how the current DCE handles static constructors, it may be too generous but that's fine. The problem is that the choice can't be made by a DCE because it never asks.

[iskiselev]

@Rohansi, we could simply change AssemblyTranslator.ShouldSkipMember (but DCE in that case should process .cctor members in a little bit different way - as it will be non-original Member, or we could tweak some other part of JSIL so that it will use correct MemberInfo to ask ShouldSkipMember), but I still don't see how can you improve DCE to strip static constructor more aggressive.

[Rohansi]

Does the DCE depend on that behavior right now? It looks like it works properly without it. I really don't see the point in JSIL forcing static constructors to be generated, that should be the DCE's decision.

[iskiselev]

So, here is a sample of current DCE behavior. Let's look on next sample:

using System;
public static class Program
{

    public static void Main(string[] args)
    {
        Console.WriteLine("main");
        //new SampleClass();
    }

}

public class SampleClass
{
    static SampleClass()
    {
        Console.WriteLine("SampleClass cctor");
        new SampleClass2();
    }
}

public class SampleClass2
{
    public SampleClass2()
    {
        Console.WriteLine("SampleClass2 cctor");
    }
}

In above example, both SampleClass and SampleClass2 will be totally stripped. You will not see any declarations of this classes - nor their static/instance constructor.

If you will uncomment second line in Main, both SampleClass and SampleClass2 will be preserved in output - as we use SampleClass, we must translate its static constructor. As static constructor has reference to SampleClass2 (and its instance constructor), we need preserve SampleClass2 instance constructor in output.

[Rohansi]

Yes, I know how it works right now. But why shouldn't we be allowed to eliminate static constructors? I understand that it's not an easy thing to do and I'm not saying the DCE needs to do it, but for some reason JSIL doesn't allow analyzers to do it.

[iskiselev]

We may change AssemblyTranslator.ShouldSkipMember as soon, as anybody will implement some logic in DCE that will have any benefits of checking for static constructor eliminating. We still need modify AssemblyTranslator (see TranslateTypeStaticConstructor), that inject some special logic inside class .cctor. As this is not so easy work and nobody yet suggested any DCE implementation, that achieve any benefits from it - nobody yet done it and I've only inserted simplest hack-implementation for it.