Writing a pass in MELT

Prerequisites

You should have compiled the MELT branch or plugin and be able to say hello world in MELT. This has been covered in MELT tutorial. You should be somehow familiar with GCC and be able to write (or at least read & understand) a simple plugin or a trivial pass in C.

Defining where your pass should go

You should first define where your pass should go. In practice, MELT uses the generic plugin framework for passes, so you need to register a MELT pass, before, after, or in replacement of an existing pass. Choosing where to insert your MELT pass (or passes) is important. You probably have few MELT passes (e.g. one pass, or perhaps a few dozens passes in a monster project).

It is possible to register a MELT pass, but it is not possible to unregister it. However, in some circumstances, your pass could do nothing (and that is like removing it).

Each MELT pass is a stub to some MELT code which by default don't do anything. Once you have chosen the MELT passes you want to implement in MELT code, you just have to fill the stub.

You could look inside the gcc/melt/xtramelt-ana-simple.melt source file and also gcc/melt/xtramelt-ana-base.melt source file for examples. Warning, currently (july 2009) the passes in ana-simple.melt are incomplete or buggy.

Therefore, you have to define a MELT mode (i.e. the word after -fmelt-mode= in the GCC MELT invocation). Let's suppose your command is named green_pass so you would run gcc-melt -fmelt-mode=green_pass ....

We first define a function which implements this command. This function should at least register your pass, or perhaps even create a pass, and it should return non-nil (otherwise the compilation stops).

(defun green_pass_docmd (cmd module_data)
  (let ((green_pass (instance class_gcc_gimple_pass
                 :named_name '"melt_green_pass"
                 :gccpass_gate green_pass_gate
                 :gccpass_exec green_pass_exec
                 :gccpass_data (make_maptree discr_map_trees 100)
                 :gccpass_properties_required ())))
    (install_melt_gcc_pass green_pass "after" "cfg" 0)
    (return green_pass)))

This example shows that you can create an instance of a class with its fields using the instance keyword and that fields inside classes and their objects in MELT have a (globally unique) name starting with a colon. You could also fill an existing instance using put_fields1.

Take care that the :named_name field is set to a quoted string  '"melt_greenpass"  which is a boxed string value. In contrast to other Lisps  '"melt_greenpass"  is not the same as the unquoted  "melt_greenpass"  which is a raw string stuff (so could not be put as a field in a MELT object, since it is not a value.). Likewise a quoted integer e.g.  '12  denotes a boxed integer value, which is very different of a raw integer stuff  12  .

Once your greenpass instance is created, you register its as a pass using the install_melt_gcc_pass primitive and specifying its position relatively to an existing GCC pass. Here our pass is positioned after 2 the pta pass (the pass_ipa_pta structure in file gcc/tree-ssa-structalias.c).

The gccpass_properties_required  gccpass_properties_provided gccpass_properties_destroyed gccpass_todo_flags_start gccpass_todo_flags_finish fields of a MELT pass are translated at install_melt_gcc_pass time. Their value can be a boxed string, a quoted symbol -of the same name as the equivalent flags in C file gcc/tree-pass.h eg PROP_ssa or TODO_verify_stmts (case is not significant, so it could be Todo_Verify_StMts) etc. To indicate a union of such flags, use a MELT list or tuple. Don't change the value of these fields after the pass is installed3

We also show that debug printing is done thru the debug_msg keyword, which takes a value and a message as arguments. Debug printing is enabled only if GCC MELT has been configured with --enable-check at MELT build time, and if gcc-melt has been run with the -fmelt-debug flag.

At last a command function should return a non-nil value unless the compilation should be terminated. We use the return keyword, which in this case is silly, since like in most lisps a function returns the value of its last computed expression.

We still have to code in MELT the gate and execute functions of the pass, which are green_pass_gate and green_pass_exec here. They should be defined in the same MELT module installing the mode.

We have to define an instance of CLASS_MELT_MODE and install it for implementing our mode. This instance refers to the function implementing the mode, and also contains some help string, which are useful for the -fmelt-mode=help mode.

(definstance green_pass_mode class_melt_mode
  :named_name '"green_pass"
  :meltmode_help '"Finding all fprintf(stdout,...) calls"
  :meltmode_fun green_pass_docmd)
(install_melt_mode green_pass_mode)

The gate function takes the pass object as argument and returns non nil to permit execution of the pass. It can be as simple as

(defun green_pass_gate (pass)
  pass)

The exec function of a pass also gets the pass as argument.

Implementing utility code

We want to keep together all values relevant to our pass, so we need a data structure. The way to define new data structures in MELT is to define a new class.

(defclass class_green_data
  :super class_proped
  :fields (green_data_pass
           green_data_map))

A MELT class is defined by giving (using the :super keyword) its super-class and the sequence of field names. Here, we use class_proped for the super-class4, a system class containing only one field, named prop_table which conventionally could be an hash-table mapping some user properties to some values.

Conventionally, class names start with class_ prefix. Field names have to be globally unique (we cannot have another class providing the mkgreen_data) and by convention most classes have all their field starting by a common class-specific prefix (here green_data_). Field names should be unique, because the MELT translator uses them. When translating (get_field :green_pass_map d) -that is, when accessing the :green_pass_map field of value d the translator generates a test for the appropriate class; the previous expression is indeed translated almost as (if (is_instance d class_green_data) (unsafe_get_field :green_data_map d) ()) so that safe field access gives null if the accessed value is not an object of class_green_data. If we could have two fields named green_datain two unrelated classes, that transformation would be impossible.

The fields of our class_green_data include the (MELTified) gcc pass, and a map (hash-tables) associating trees to values. We keep here the SSA names assigned to stdout and the boxed gimple assignement.

Notice that MELT classes do not declare explicitly the methods selectors. These are declared separately, and methods can be installed very dynamically in classes. Classes are themselves objects (of class_class).

The core of our pass is a function (which we call look_for). This function shows a significant and powerful MELT feature: pattern matching5. This function is called with a green data (that is, an instance of class_green_data) and an unboxed gimple.

(defun look_for (green_data :gimple g)
  (match g
     (?(gimple_assign_single ?lhs
                 ?(and ?rhs
                       ?(tree_var_decl
                     ?(cstring_same "stdout"))))
       (maptree_put (get_field :green_data_map green_data)
            lhs (make_gimple discr_gimple g)))
     (?(gimple_assign_cast ?lhs ?rhs)
       (let ((g_match (maptree_get (get_field :green_data_map green_data) rhs)))
         (cond (g_match
                (maptree_put (get_field :green_data_map green_data)
                             lhs (make_gimple discr_gimple g))))))
     (?(gimple_call_2_more ?lhs
                           ?(and ?function
                                 ?(tree_function_decl
                                   ?(cstring_same "fprintf")
                                   ?_)
                                 ?_)
                           ?arg0
                           ?_
                           ?_)
       (let ((g_match (maptree_get (get_field :green_data_map green_data) arg0)))
         (cond (g_match
                (inform_at_gimple g "fprintf (stdout, ...); detected !\n")))))
     (?_ )))

Here we have our match operator (much more powerful than the switch operator of C); it takes a thing to be matched (here the unboxed gimple g but it could be anything else.) and a sequence of match cases. Each match-case is a pattern followed by case-expressions, which are evaluated if the matched thing g matches that pattern. A pattern usually contain pattern variables which are instanciated when the pattern matches, and the case expressions are evaluated in an environment knowing these pattern variables.

The first match case is

(?(gimple_assign_single ?lhs
                        ?(and ?rhs
                              ?(tree_var_decl
                                 ?(cstring_same "stdout"))))

Question marks ? are prefixing pattern expressions (or pattern variables), so the pattern of our first match case is ?(gimple_assign_single ...) and it contains a pattern variable ?lhs and a sub-pattern more complex which test if we assign a variable represented by the "stdout" string. This pattern is matched, when simple assignment happens. For instance, i = 1;. If we want to remember this event to detect fprintf (stdout, ...) forms, we have to memorize it. For this, we use a map which associates a tree and a MELT value.

The others work in the same way. This is the code of look_for function :

(defun look_for (green_data :gimple g)
  (match g
     (?(gimple_assign_single ?lhs
                 ?(and ?rhs
                       ?(tree_var_decl
                     ?(cstring_same "stdout"))))
       (maptree_put (get_field :green_data_map green_data)
            lhs (make_gimple discr_gimple g)))
     (?(gimple_assign_cast ?lhs ?rhs)
       (let ((g_match (maptree_get (get_field :green_data_map green_data) rhs)))
         (cond (g_match
                (maptree_put (get_field :green_data_map green_data)
                             lhs (make_gimple discr_gimple g))))))
     (?(gimple_call_2_more ?lhs
                           ?(and ?function
                                 ?(tree_function_decl
                                   ?(cstring_same "fprintf")
                                   ?_)
                                 ?_)
                           ?arg0
                           ?_
                           ?_)
       (let ((g_match (maptree_get (get_field :green_data_map green_data) arg0)))
         (cond (g_match
                (code_chunk detection_printf #{
                            printf("fprintf (stdout,...); detected !\n");
                                             }#)))))
     (?_ )))

The following function allows us to traverse a GIMPLE representation thanks to MELT iterators. The main idea is to apply a function which contains matchers on each gimple.

(defun traverse (green_data)
  (each_bb_cfun
   ()
   (:basic_block body :tree declaration)
   (let ((:gimple_seq sequence (gimple_seq_of_basic_block body)))
     (each_in_gimpleseq
      (sequence)
      (:gimple g)
      (look_for green_data g)))))

To understand the traverse function, you need to know what gimple looks like.

The pass execute function

The execute function of our pass has just to invoke our traverse (which does not transform gimple code yet, only detects fprintf(stdout,...) and needs to make an instance of our class_green_data appropriately initialized with an empty tree map.

(defun green_pass_exec (pass)
  (let ((green_data
     (instance class_green_data
           :green_data_pass pass
           :green_data_map (make_maptree discr_map_trees 10))))
    (traverse green_data)))

Now, we would like to build our module. To do this, you have to use the translatetomodule mode of gcc-melt like this :

gcc-melt -fmelt-mode=translatetomodule -fmelt-arg=green.melt -c empty.c

Currently, we have to give to gcc an empty file.

Then we can launch it with the following command :

gcc-melt -fmelt-mode=green_pass -fmelt-init=@@:green -fmelt-module-path=. -c yourfile.c

With the following c file :

#include <stdio.h>

int
main (void)
{
    int i = 5;

    fprintf(stdout, "Value of i = %d\n", i);

    return 0;
}

You should get this :

main.c: In function 'main':
main.c:8:12: note: fprintf (stdout, ...); detected !

Coding and debugging hints

The translation of MELT code to C code is quick; most of the CPU time of the MELT translation process happens in the compilation of the generated C code into a dynamically loadable shared object.

In practice, make sure your MELT code don't produce any warnings or errors when it is translated to C. Only accept warnings you fully understand.

When you code in MELT, try to get inspiration from existing code. Notice that MELT core language features have been progressively designed, and are (sadly) not used in all interesting occasions -because they have not been available at the time some of the MELT code has been written6.

Use frequently the debug facilities (enabled only in checking mode 7), like debug_msg and assert_msg. When an assert_msg is violated, you get a nice MELT backtrace (without needing any debugger like GDB) which is often enough to correct the bug.

Debug printing happens only when you use the -fmelt-debug program option. Debug (& assert_msg violation) messages have a counter (and a call depth). You can use the -fmelt-debugskip=12000 program option to skip the first 12000 debug messages.


  1. The put_fields operator checks that the updated value is indeed an object of the right class. It has a faster but dangerous unsafe variant unsafe_put_fields that you should better not use, since it could crash gcc when used wrongly, e.g. when the first argument is not a MELT object of the right class. (1)

  2. You could position it  "before"  it, or  "replace"  it. We use string instead of the enum used in plugins.h. (2)

  3. However, you could change at any time the most important fields in MELT passes - gccpass_gate & gccpass_exec which are closures [ie MELT functions], and gccpass_data which is arbitrary. If you set the gccpass_gate & gccpass_exec to nil, you have effectively cleared the pass, as if you have removed it. (3)

  4. We could have just given class_root as the super-class of class_green_data because we probably don't need or care about properties. (4)

  5. The pattern matching of MELT is strongly inspired by OCAML, SML, Haskell, CLIPS (5)

  6. In particular pattern matching and iteration abilities are powerful, but have been added only lately, so are sparingly used in the MELT translator. (6)

  7. So debugging features are compiled only when MELT has been configured with --enable-check (7)

None: writing a pass in MELT (last edited 2010-10-01 05:53:31 by BasileStarynkevitch)