Documentation/design-docs/jit-call-morphing.md

   1 Morphing of call nodes in RyuJIT
   2 =========================
   3
   4 Overview
   5 --------
   6
   7 In C# and IL, and unlike C/C++, the evaluation order of the arguments for calls is strictly defined.
   8 Basically this is left to right in C# or the IL instruction ordering for IL.
   9
  10
  11 One issue that must be addressed is the problem of nested calls.  Consider `Foo(x[i], Bar(y))`.
  12 We first must evaluate `x[i]` and possibly set up the first argument for `Foo()`.  But immediately
  13 after that, we must set up `y` as first argument of `Bar()`.  Thus, when we evaluate `x[i]` we will
  14 need to hold that value someplace while we set up and call `Bar().`  Arguments that contain an
  15 assignment are another issue that we need to address.  Most cases of this are rare except for
  16 post/pre increment, perhaps like this: `Foo(j, a[j++])`.  Here `j` is updated via assignment
  17 when the second arg is evaluated, so the earlier uses of `j` would need to be evaluated and
  18 saved in a new LclVar.
  19
  20
  21 One simple approach would be to create new single definition, single use LclVars for every argument
  22 that is passed.  This would preserve the evaluation order.  However, it would potentially create
  23 hundreds of LclVar for moderately sized methods and that would overflow the limited number of
  24 tracked local variables in the JIT.  One observation is that many arguments to methods are
  25 either constants or LclVars and can be set up anytime we want. They usually will not need a
  26 new LclVar to preserve the order of evaluation rule.
  27
  28
  29 Each argument is an arbitrary expression tree.  The JIT tracks a summary of observable side-effects
  30 using a set of five bit flags in every GenTree node: `GTF_ASG`, `GTF_CALL`, `GTF_EXCEPT`, `GTF_GLOB_REF`,
  31 and `GTF_ORDER_SIDEEFF`.  These flags are propagated up the tree so that the top node has a particular
  32 flag set if any of its child nodes has the flag set.  Decisions about whether to evaluate arguments
  33 into temp LclVars are made by examining these flags on each of the arguments.
  34
  35
  36 *Our design goal for call sites is to create a few temp LclVars as possible, while preserving the
  37 order of evaluation rules of IL and C#.*
  38
  39
  40 Data Structures
  41 ------------
  42
  43 The most important data structure is the `GenTreeCall` node which represents a single
  44 call site and is created by the Importer when it sees a call in the IL.  It is also
  45 used for internal calls that the JIT needs such as helper calls.  Every `GT_CALL` node
  46 should have a `GTF_CALL` flag set on it.  Nodes that may be implemented using a function
  47 call also should have the `GTF_CALL` flag set on them. The arguments for a single call
  48 site are held by three fields in the `GenTreeCall`: `gtCallObjp`, `gtCallArgs`, and
  49 `gtCallLateArgs`.  The first one, `gtCallObjp`, contains the instance pointer ("this"
  50 pointer) when you are calling a method that takes an instance pointer, otherwise it is
  51 null.  The `gtCallArgs` contains all of the normal arguments in a null terminated `GT_LIST`
  52 format.  When the `GenTreeCall` is first created the `gtCallLateArgs` is null and is
  53 set up later when we call `fgMorphArgs()` during the global Morph of all nodes. To
  54 accurately record and track all of the information about call site arguments we create
  55 a `fgArgInfo` that records information and decisions that we make about how each argument
  56 for this call site is handled.  It has a dynamically sized array member `argTable` that
  57 contains details about each argument. This per-argument information is contained in the
  58 `fgArgTabEntry` struct.
  59
  60
  61 `FEATURE_FIXED_OUT_ARGS`
  62 -----------------
  63
  64 All architectures support passing a limited number of arguments in registers and the
  65 additional arguments must be passed on the stack. There are two distinctly different
  66 approaches for passing arguments of the stack.  For the x86 architecture a push
  67 instruction is typically used to pass a stack based argument.  For all other architectures
  68 that we support we allocate the `lvaOutgoingArgSpaceVar`, which is a variable-sized
  69 stack based LclVar.  Its size is determined by the call site that has the largest
  70 requirement for stack based arguments.  The define `FEATURE_FIXED_OUT_ARGS` is 1 for
  71 architectures that use the outgoing arg space to pass their stack based arguments.
  72 There is only one outgoing argument space and any values stored there are considered
  73 to be killed by the very next call even if the next call doesn't take any stack based
  74 arguments. For x86, we can push some arguments on the stack for one call and leave
  75 them there while pushing some new arguments for a nested call.  Thus we allow nested
  76 calls for x86 but do not allow them for the other architectures.
  77
  78
  79 Rules for when Arguments must be evaluated into temp LclVars
  80 -----------------
  81
  82 During the first Morph phase known as global Morph we call `fgArgInfo::ArgsComplete()`
  83 after we have completed building the `argTable` for `fgArgInfo` struct. This method
  84 applies the following rules:
  85
  86 1. When an argument is marked as containing an assignment using `GTF_ASG`, then we
  87 force all previous non-constant arguments to be evaluated into temps.  This is very
  88 conservative, but at this phase of the JIT it is rare to have an assignment subtree
  89 as part of an argument.
  90 2. When an argument is marked as containing a call using the `GTF_CALL` flag, then
  91 we force that argument and any previous argument that is marked with any of the
  92 `GTF_ALL_EFFECT` flags into temps.
  93         * Additionally, for `FEATURE_FIXED_OUT_ARGS`, any previous stack based args that
  94     we haven't marked as needing a temp but still need to store in the outgoing args
  95     area is marked as needing a placeholder temp using `needPlace`.
  96 3. We force any arguments that use `localloc` to be evaluated into temps.
  97 4. We mark any address taken locals with the `GTF_GLOB_REF` flag. For two special
  98 cases we call `EvalToTmp()` and set up the temp in `fgMorphArgs`.  `EvalToTmp`
  99 records the tmpNum used and sets `isTmp` so that we handle it like the other temps.
 100 The special cases are for `GT_MKREFANY` and for a `TYP_STRUCT` argument passed by
 101 value when we can't optimize away the extra copy.
 102
 103
 104 Rules use to determine the order of argument evaluation
 105 -----------------
 106
 107 After calling `ArgsComplete()` the `SortArgs()` method is called to determine the
 108 optimal way to evaluate the arguments.  This sorting controls the order that we place
 109 the nodes in the `gtCallLateArgs` list.
 110
 111 1. We iterate over the arguments and move any constant arguments to be evaluated
 112 last and remove them from further consideration by marking them as processed.
 113 2. We iterate over the arguments and move any arguments that contain calls to be evaluated first and remove them from further consideration by marking them as processed.
 114 3. We iterate over the arguments and move arguments that must be evaluated into
 115 temp LclVars to be after the ones that contain calls.
 116 4. We iterate over the arguments and move arguments that are simple LclVar or
 117 LclFlds and put them before the constant args.
 118 5. If there are any remaining arguments, we evaluate them from the most complex
 119 to the least complex.
 120
 121
 122 Evaluating Args into new LclVar temps and the creation of the LateArgs
 123 -----------------
 124
 125 After calling `SortArgs()`, the `EvalArgsToTemps()` method is called to create
 126 the temp assignments and to populate the LateArgs list.
 127
 128 Arguments that are marked with `needTmp == true`.
 129 -----------------
 130
 131 1. We create an assignment using `gtNewTempAssign`. This assignment replaces
 132 the original argument in the `gtCallArgs` list.  After we create the assignment
 133 the argument is marked as `isTmp`.  The new assignment is marked with the
 134 `GTF_LATE_ARG` flag.
 135 2. Arguments that are already marked with `isTmp` are treated similarly as
 136 above except we don't create an assignment for them.
 137 3. A `TYP_STRUCT` argument passed by value will have `isTmp` set to true
 138 and will use a `GT_COPYBLK` or a `GT_COPYOBJ` to perform the assignment of the temp.
 139 4. The assignment node or the CopyBlock node is referred to as `arg1 SETUP` in the JitDump.
 140
 141
 142 Argument that are marked with `needTmp == false`.
 143 -----------------
 144
 145 1. If this is an argument that is passed in a register, then the existing
 146 node is moved to the `gtCallLateArgs` list and a new `GT_ARGPLACE` (placeholder)
 147 node replaces it in the `gtArgList` list.
 148 2. Additionally, if `needPlace` is true (only for `FEATURE_FIXED_OUT_ARGS`)
 149 then the existing node is moved to the `gtCallLateArgs` list and a new
 150 `GT_ARGPLACE` (placeholder) node replaces it in the `gtArgList` list.
 151 3. Otherwise the argument is left in the `gtCallArgs` and it will be
 152 evaluated into the outgoing arg area or pushed on the stack.
 153
 154 After the Call node is fully morphed the LateArgs list will contain the arguments
 155 passed in registers as well as additional ones for `needPlace` marked
 156 arguments whenever we have a nested call for a stack based argument.
 157 When `needTmp` is true the LateArg will be a LclVar that was created
 158 to evaluate the arg (single-def/single-use).  When `needTmp` is false
 159 the LateArg can be an arbitrary expression tree.