Re: [Yhc] Still shrinking YHI for ARM7...question

24 Jul 2007

      Alexis Morris wrote:
...
Hi Tom,
Thanks alot for the information. Those are great places to start. As far 
as loading the bytecode goes, for now I am still looking into that, but 
will have to load directly from memory, as you mentioned.
Cheers,
</Alexis>
Hmm yes the bytecode loading is going to be tricky I suspect ...

You could just convert the bytecode files into C source code 
representations and then load them using the module loader as usual. The 
disadvantage of this is it's a bit space inefficient. You use the static 
memory for the bytecode files and then the bytecode loader will load 
those into dynamic memory.

The method I would recommend would be to split yhi into two parts: the 
part that loads the bytecode from the file and the part that runs the 
bytecode. Essentially your 'loader' program would load the bytecode from 
the file into memory and then output that data as C source code. That C 
source code could then be compiled and linked in with the main 
interpreter (this is actually similar to how nhc98 does it).

This is rather involved and it depends on quite a bit of knowledge of 
how Yhc works internally, so I'll describe how I'd do it in detail. 
You'll have to bear with me if I go over stuff you're already familiar 
with. Also if you have your own ideas and don't want to do it this way 
that's great too :-)

I suggest you read http://haskell.org/haskellwiki/Yhc/RTS/Heap if you 
haven't already as that describes the heap layout of Yhc. Essentially 
the idea is to take the nodes loaded into the heap by the loader and 
convert them into C source code that does the same thing.

Ok lets start in main.c:init

/* initialize program */
void init(char* mainMod, Node** mainFunc, Node** _toplevel,
	  FInfo** _driver){
   /* inits */
   sanity_init();
   heap_init(G_options.heapSize);
#ifdef HAT
   hgm_init(mainMod);
#endif
   mod_init();

   /* load all globals */
   initGlobals(mainMod, mainFunc, _toplevel, _driver);

   /* initialize the threads system */
   yhi_thread_init();
   hsffi_init();

   /* finished with the module system now */
   /* mod_exit(); ... not any more, now we still need it! */
}

After calling 'initGlobals' all the modules are stored in the G_modules 
hashtable in modules.c. You can walk over this hashtable to get a list 
of all module objects, with something like:

   void process_modules(){
     for (int i = 0; i < G_modules->size; i++){
       for (HashLink* p = G_modules->table[i]; p; p = p->next){
         Module* mod = (Module*)p->value;
         process_module(mod);
       }
     }
   }

Then you need to process the Objects in each module. The code to do this 
might be something like:

   void process_module(Module* mod){
     for (int i = 0; i < mod->lookup->size; i++){
       for (HashLink* p = mod->lookup->table[i]; p; p = p->next){
          ObjectRef* ref = (ObjectRef*)p->value;
          Object* obj = ref->object;
          if (!obj){
	    // then this object was known about but never actually
             // used so skip it
             continue;
          }
          process_object(mod, p->key, obj);
       }
     }

Each Object has an Info, or a Node or both.

   void process_object(Module* mod, Char* name, Object* obj){
     if (obj->info){
       process_info(mod, name, obj->info);
     }
     if (obj->node){
       process_node(mod, name, obj->node);
     }
   }

Looking in node.h we can see that an Info has a tag, this tag says what 
kind of Info this is. There are three sensible values that you will 
actually see: I_FINFO, I_XINFO and I_CINFO.

   void process_info(Module* mod, Char* name, Info* info){
     switch(info->tag){
     case I_FINFO: process_finfo(mod, name, (FInfo*)info); break;
     case I_XINFO: process_xinfo(mod, name, (XInfo*)info); break;
     case I_CINFO: process_cinfo(mod, name, (CInfo*)info); break;
     default: abort();
     }
   }

Okay so FInfo and XInfo are very similar, so much of what applies to one 
applies to the other. If we look at 
http://haskell.org/haskellwiki/Yhc/RTS/Heap we can see that an FInfo (or 
XInfo) is laid out in memory exactly as:

    +-----------------+
    | PInfo   0 / n   |            size 0, need n
    +-----------------+
    | PInfo   1 / n-1 |            size 1, need n-1
    +-----------------+
            ...
    +-----------------+
    | PInfo   n / 0   |            size n-1, need 0
    +-----------------+
    | FInfo   ....    |            function info table

i.e. The PInfos associated with that FInfo, directly followed by the 
FInfo itself. We need to generate C source code that does the same 
thing. For example for the C source code for the PInfos and FInfo for 
the Prelude.sum function might look like:

PInfo  pinfo_Prelude_sum[] = {
	(PInfo){ { P_INFO }, 0, 1 },
	(PInfo){ { P_INFO }, 1, 0 }
};
FInfo  finfo_Prelude_sum = ...

If my memory of C serves me correctly if we compiled and linked that 
source code it it would load them into memory consecutively (and without 
gaps).

Our function to process finfos  would thus look like

   void process_finfo(Module* mod, Char* name, FInfo* finfo){
      // process pinfos
      process_pinfos(mod, name, finfo->arity, finfo->papTable);

      // write finfo structure
      fprintf(cSrcFile, "FInfo finfo_%s_2E%s = (FInfo){\n",
		mod->name, name);

      ... write all the finfo fields
   }

Now here I've just printed the mod->name and name, but in actual fact 
you'd need to escape them first to ensure they were valid C identifiers. 
This is because the module names could contain '.' and ';'(another 
separator) and object names could refer to operators (like '+').
The escaping system used by nhc was that any non-alpha-numeric was 
converted to _XX where XX was the hexadecimal of the ASCII. 'Prelude.+' 
would thus be: Prelude__2B. I've used this system in my examples but any 
non-clashing system would do.

process_finfo would write out the FInfo structure to the C source file. 
This would mostly just follow the definition in node.h, but there are a 
few tricky items in the structure.
    - papTable: this always points to the first pinfo associated with the
                finfo (i.e. PInfo 0 / n).
    - link: just use NULL it's only used inside the GC
    - module: again use NULL, only used in the reflection API
    - name: NULL is fine again, only needed for debugging etc.
    - code: you'll need to allocate a block with the instructions in it
            like

            static Byte bytecode_Prelude_2Esum[] = { 0xA4, 0x43, ... };

            then output the pointer as &bytecode_Prelude_2Esum
    - constTable: described below

The constant table is used to allow a FInfo to access other constants 
and functions. Each item in the table is a ConstItem and has an 
associated const type, you might process the constants as

    void process_constants(Module* mod, Char* name, FInfo* finfo){
      for (int i = 0; i < finfo->numConsts; i++){
        ConstType type = finfo->constTypes[i];
        ConstItem item = finfo->constItem[i];
        if (type == CI_INFO){
          process_info_constant(mod, name, (Info*)item);
        }else if (type == CI_NODE){
          process_node_constant(mod, name, (Node*)node);
        }
      }
    }

A CI_INFO links to an Info structure of some sort, and a CI_NODE links 
to a heap node. The constant table needs to contain *links* to the 
structures in memory so you'll want your generated constant table to 
look something like:

    ConstItem consttable_Prelude_2Esum = {
       &finfo_Prelude_2E_2B, &finfo_Prelude_2Esum
    };

Fortunately you can do this because every Info that the constant will 
point to will be a FInfo, XInfo or CInfo. These all store their parent 
module and their name so you can work out what the reference to them is 
called.

Okay so that does with process_finfo. process_pinfos would be something like

    void process_pinfos(Module* mod, Char* name, Int num, PInfo* pinfos){
       fprintf(cSrcFile, "PInfo pinfo_%s_2E%s[] = {\n",
		mod->name, name);
       for (int i = 0; i < num; i++){
         fprintf(cSrcFile, "(PInfo){ { I_PINFO }, %d, %d },\n",
           pinfos[i].size, pinfos[i].need);
       }
       fprintf(cSrcFile, "};\n");
    }

process_cinfo should be easy, but process_xinfo will be hard. The 
trickiest point is the ffiFunc field.
Creating a FFIFunction structure is okay but the 'funcPtr' field in
FFIFunction (see hsffi.h) is tricky. You can't output a function pointer 
as C source so you need the name of the function as it appears in the 
runtime source code. Your best option is probably to use 
primitive.c:G_primFuncs, this maps names to function pointers. Using 
this you could do a reverse lookup from pointers to function names. In 
the vast majority of cases the name of the function in the source code 
is the same as the one in G_primFuncs. If it isn't you can change the C 
function name so it is named the same, you can just use compiler errors 
from your generated C code to get it to tell you when the names are 
different.

Okay Nodes are the next tricky point, the problem with them is that the 
garbage collector expects them to be in it's malloced heap area so if 
you allocate them in static memory it'll have a tantrum. Fortunately the 
changes to stop it having a tantrum are (I think) fairly small. In 
mark.c:mrk_isMarked, change

   if (!(p >= (Node*)G_hpStart && p < (Node*)G_hp)){
     ASSERT(p >= (Node*)G_hpStart && p < (Node*)G_hp);
   }

to

   if (!(p >= (Node*)G_hpStart && p < (Node*)G_hp)){
     return true;
   }

in mark.c:mrk_mark

   ASSERT(p >= (Node*)G_hpStart && p < (Node*)G_hp);

to

   if (!(p >= (Node*)G_hpStart && p < (Node*)G_hp)){
     return true;
   }

These two changes make the mark process ignore nodes outside the heap, 
the final one is:

jonkers.c:jonk_thread, change

   ASSERT(*p >= (Node*)G_hpStart && *p <= (Node*)G_hp);

to

  if (!(*p >= (Node*)G_hpStart && *p <= (Node*)G_hp)){
    return;
  }

Now hopefully that should work but the GC is a bit temperamental, so if 
you can't get it to work then you could try loading the nodes into the 
heap in a pre-processing pass.

As for how to name the generated nodes, I would suggest just using the 
printed hexadecimal of the pointer. i.e. a Node* might be

   Node node_0x34a82b = ...

The extra complication is 'unusual nodes' such as INode, LongNode,
FloatNode, DoubleNode, StringNode. Fortunately you can tell when you've 
got one of these by looking at the infos in primitive.h. INode's always 
have the info &G_infoInt, FloatNodes always &G_infoFloat, etc. You can 
test the info of the node you've got an generate the right one.

   void process_node(Node* node){
      Info* info = NODE_INFO(node);
      if (info == &G_nodeInt){
        process_int_node((INode*)node);
      }else if (info == &G_nodeFloat){
        process_float_node((FloatNode*)node);
      }
      ...
      }else{
        // normal zero arg node case
        fprintf(cSrcFile, ...);
      }
   }

The only 'special' nodes you'll see are: G_infoInt, G_infoString, 
G_infoDouble, G_infoFloat and G_infoInteger.

So that's pretty evil, but I believe if you do that then you can load 
bytecode, in very small amounts of memory. I've included a little 
example of the generated C source code for two simple functions (one 
FInfo and one XInfo) ...

Enjoy ;-)

Tom

/*

this is the C code code that might be generated for the Haskell source

sum :: [Int] -> Int
sum []     = 0
sum (x:xs) = x + sum xs

Of course you'd also need a header file declaring all these items (to allow cyclic definitions)

*/

// the PInfo and FInfos
PInfo pinfo_Prelude_2Esum[] = {
    (PInfo){ { I_PINFO }, 0, 1 },           // 0 arguments present, 1 remaining
    (PInfo){ { I_PINFO }, 1, 0 },           // 1 arguments present, 0 remaining
};

FInfo finfo_Prelude_2Esum = (FInfo){
        { I_FINFO },
        pinfo_Prelude_2Esum,                    // papTable
        NULL,                                   // link
        2,                                      // arity
        0,                                      // stack (unused)
        0x00,                                   // flags (FFL_NONE, unused for your application)
        NULL,                                   // module name (ignored)
        NULL,                                   // function name (ignored)
        23,                                     // code size in bytes
        &bytecode_Prelude_2Esum,                // pointer to code
        3,                                      // number of constants in the const table
        &ctypes_Prelude_2Esum,                  // pointer to constant types
        &ctable_Prelude_2Esum                   // constant table items
    };

// The bytecode for the function
UInt8 bytecode_Prelude_2Esum[] = { 
    0x43, 0xA2, 0x49 .... 
};

// the constant types
UByte ctypes_Prelude_2Esum[] = { C_INFO, C_INFO, C_NODE };

// the constant table
ConstItem ctable_Prelude_2Esum[] = {
    (ConstItem)&finfo_Prelude_2E_2B,          // Prelude.+
    (ConstItem)&finfo_Prelude_2Esum,          // Prelude.sum
    (ConstItem)&node_0x43A22917,            // a node representing the Int '0'
};

// the application of sum to zero arguments, this is shared since
// it is always the same.
Word node_0x45BB1934[] = { (Word)&pinfo_Prelude_2Esum[0] };

// a node representing the Int '0'
INode node_0x43A22917[] = (INode){ 
    { (Word)&G_infoInt },       // node info
    0                           // node value
};

/*

This is the C code for a primitive function, like Yhc.Primitive.primExitWith 

*/
PInfo pinfo_Yhc_2EPrimitive_2EprimExitWith[] = {
    (PInfo){ { I_PINFO }, 1, 0 },
    (PInfo){ { I_PINFO }, 0, 1 }
};

XInfo xinfo_Yhc_2EPrimitive_2EprimExitWith[] = {
    { I_XINFO },                                    // info tag
    pinfo_Yhc_2EPrimitive_2EprimExitWith,             // pap table
    NULL, 1, 0, NULL, NULL,                         // link, arity, stack, module, name
    &ffi_Yhc_2EPrimitive_2EprimExitWith
};

FFIFunction ffi_Yhc_2EPrimitive_2EprimExitWith[] = {
    CC_PRIMITIVE,                                          // calling convention (CC_PRIMITIVE for primitive)
    1,                                                     // arity
    { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,      // arg types (can be ignored)
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, },  
    0,                                                     // ret type (can also be ignored)
    &primExitWith,                                         // pointer to C function in builtin/System.c   
};  
// note you could save space here by trimming the FFIFunction to be the bare minimum that you need
// in particular the arg types are especially wasteful.

// indeed you could even trim the FInfo structure to remove the unneeded items: stack, flags, module and name
// (link is necessary however).

Re: [Yhc] Still shrinking YHI for ARM7...question

Thomas Shackell