docs/opcode-decomp.txt

   1
   2 * How to handle complex IL opcodes in an arch-independent way
   3
   4         Many IL opcodes are very simple: add, ldind etc.
   5         Such opcodes can be implemented with a single cpu instruction
   6         in most architectures (on some, a group of IL instructions
   7         can be converted to a single cpu op).
   8         There are many IL opcodes, though, that are more complex, but
   9         can be expressed as a series of trees or a single tree of
  10         simple operations. Such simple operations are architecture-independent.
  11         It makes sense to decompose such complex IL instructions in their
  12         simpler equivalent so that we gain in several ways:
  13         *) porting effort is easier, because only the simple instructions
  14                 need to be implemented in arch-specific code
  15         *) we could apply BURG rules to the trees and do pattern matching
  16                 on them to optimize the expressions according to the host cpu
  17
  18         The issue is: where do we do such conversion from coarse opcodes to
  19         simple expressions?
  20
  21 * Doing the conversion in method_to_ir ()
  22
  23         Some of these conversions can certainly be done in method_to_ir (),
  24         but it's not always easy to decide which are better done there and
  25         which in a different pass.
  26         For example, let's take ldlen: in the mono implementation, ldlen
  27         can be simply implemented with a load from a fixed position in the
  28         array object:
  29
  30                 len = [reg + maxlen_offset]
  31
  32         However, ldlen carries also semantics information: the result is the
  33         length of the array, and since in the CLR arrays are of fixed size,
  34         this information can be useful to later do bounds check removal.
  35         If we convert this opcode in method_to_ir () we lost some useful
  36         information for further optimizations.
  37
  38         In some other ways, decomposing an opcode in method_to_ir() may
  39         allow for better optimizations later on (need to come up with an
  40         example here ...).
  41
  42 * Doing the conversion in inssel.brg
  43
  44         Some conversion may be done inside the burg rules: this has the
  45         disadvantage that the instruction selector is not run again on
  46         the resulting expression tree and we could miss some optimization
  47         (this is what effectively happens with the coarse opcodes in the old
  48         jit). This may also interfere with an efficient local register allocator.
  49         It may be possible to add an extension in monoburg that allows a rule
  50         such as:
  51
  52                 recheck: LDLEN (reg) {
  53                         create an expression tree representing LDLEN
  54                         and return it
  55                 }
  56
  57         When the monoburg label process gets back a recheck, it will run
  58         the labeling again on the resulting expression tree.
  59         If this is possible at all (and in an efficient way) is a
  60         question for dietmar:-)
  61         It should be noted, though, that this may not always work, since
  62         some complex IL opcodes may require a series of expression trees
  63         and handling such cases in monoburg could become quite hairy.
  64         For example, think of opcode that need to do multiple actions on the
  65         same object: this basically means a DUP...
  66         On the other end, if a complex opcode needs a DUP, monoburg doesn't
  67         actually need to create trees if it emits the instructions in
  68         the correct sequence and maintains the right values in the registers
  69         (usually the values that need a DUP are not changed...). How
  70         this integrates with the current register allocator is not clear, since
  71         that assigns registers based on the rule, but the instructions emitted
  72         by the rules may be different (this already happens with the current JIT
  73         where a MULT is replaced with lea etc...).
  74
  75 * Doing it in a separate pass.
  76
  77         Doing the conversion in a separate pass over the instructions
  78         is another alternative. This can be done right after method_to_ir ()
  79         or after the SSA pass (since the IR after the SSA pass should look
  80         almost like the IR we get back from method_to_ir ()).
  81
  82         This has the following advantages:
  83         *) monoburg will handle only the simple opcodes (makes porting easier)
  84         *) the instruction selection will be run on all the additional trees
  85         *) it's easier to support coarse opcodes that produce multiple expression
  86                 trees (and apply the monoburg selector on all of them)
  87         *) the SSA optimizer will see the original opcodes and will be able to use
  88                 the semantic info associated with them
  89
  90         The disadvantage is that this is a separate pass on the code and
  91         it takes time (how much has not been measured yet, though).
  92
  93         With this approach, we may also be able to have C implementations
  94         of some of the opcodes: this pass would insert a function call to
  95         the C implementation (for example in the cases when first porting
  96         to a new arch and implemenating some stuff may be too hard in asm).
  97
  98 * Extended basic blocks
  99
 100         IL code needs a lot of checks, bounds checks, overflow checks,
 101         type checks and so on. This potentially increases by a lot
 102         the number of basic blocks in a control flow graph. However,
 103         all such blocks end up with a throw opcode that gives control to the
 104         exception handling mechanism.
 105         After method_to_ir () a MonoBasicBlock can be considered a sort
 106         of extended basic block where the additional exits don't point
 107         to basic blocks in the same procedure (at least when the method
 108         doesn't have exception tables).
 109         We need to make sure the passes following method_to_ir () can cope
 110         with such kinds of extended basic blocks (especially the passes
 111         that we need to apply to all the methods: as a start, we could
 112         skip SSA optimizations for methods with exception clauses...)
 113