js/src/doc/HazardAnalysis/CFG.md

   1 # sixgill CFG format
   2
   3 The main output of the sixgill plugin is what is loosely labeled a control flow graph (CFG) associated with each function compiled.
   4 These are stored in the file src_body.xdb, which contains a mapping from function names ("mangled\$unmangled") to function data.
   5
   6 The graph is really a set of directed acyclic data flow graphs, stitched together via "loops" that imply back edges in the control flow graph.
   7
   8 Function data is an array of "bodies", one body for the toplevel code in the function, and another body for each loop. A body is _not_ a basic block, since they can contain interior branches. (The nodes in a body do not necessarily dominate the following nodes.) A body is a DAG, and thus has no back edges or cross edges. Flow starts only at the entry point and ends only at the exit point, though (1) a loop body's entry point implicitly follows its exit point and (2) `Call` nodes will cause the actual program counter to go to another (possibly recursive) body. A body really describes data flow, not dynamic control flow.
   9
  10 ## Function Body
  11
  12 A body (whether toplevel or loop) contains:
  13
  14 - .BlockId
  15   - `.Kind`: "Function" for the toplevel function or "Loop" for a (possibly nested) loop within it.
  16   - `.Loop`: if .Kind == "Loop", then a string identifier distinguishing the loop, in the format "loop#n" where n is the index of the loop in the body. Nested loops will extend this to "loop#n#m".
  17   - `.Variable`:
  18     - `.Kind`: "Func"
  19     - `.Name[]`: the function `Name` (see below)
  20 - `.Version`: always zero
  21 - `.Command`: the command used to compile this function, if recorded. This command will _not_ include the -fplugin parameters.
  22 - `.Location[]`: a length-2 array of the source positions of the first and last line of the function definition. Hopefully it will be in the same file. Note that this Location is different from a `PPoint.Location` (see below), which will have a single source position. Each source position is:
  23   - `.CacheString`: the filename
  24   - `.Line`: the line number
  25 - `.DefineVariable[]`: a list of variables defined in the body. The first one is for the function itself. Each variable has:
  26   - `.Type`: the type of the variable. See `Type`, below.
  27   - `.Variable`:
  28     - `.Kind`: one of
  29       - "Func" for the function itself
  30       - "This" for the C++ `this` parameter
  31       - "Arg" for parameters
  32       - "Temp" for temporaries
  33     - `.Name[]`: the variable `Name` (see below)
  34 - `.Index[]`: a 2-tuple of the first and last index in the body.
  35 - `.PPoint[]`: the filename and line number of each point in the body
  36   - `.Location`: a single source point (see above).
  37 - `.PEdge[]`: the bulk of the body. See Edges, below.
  38 - `.LoopIsomorphic[]`: a list of `{"Index": point}` points in the body that are cloned in loop bodies. See the edge Kind `Loop`, below.
  39
  40 A loop body (a body with BlockId.Kind == "Loop") will additionally have:
  41
  42 - `.BlockPPoint`: an array of full references to points within parent bodies that represent the entry point of this loop. Each has:
  43   - `.BlockId`: the BlockId of the parent body
  44   - `.Index`: the index of the point within the parent body
  45   - `.Version`: the value zero, intended for incremental analyses but unused in the GC hazard analysis.
  46
  47 Note that a loop may appear in more than one parent body. I believe this will not be used for regular structured code, but could be necessary to properly disentangle loops when using `goto`.
  48
  49 `Name`: a 2-tuple containing a variable or function name. For non-functions, both elements are the same. For functions, .Name[0] is the full name of the function (in format "mangled\$unmangled") and .Name[1] is the base name of the function (unqualified, with no type or parameters):
  50
  51     "Variable": {
  52       "Kind": "Func",
  53       "Name": [
  54         "_Z12refptr_test9v$Cell* refptr_test9()",
  55         "refptr_test9"
  56       ]
  57     }
  58
  59 Bodies are an array of "edges" between "points". All behavior is described as happening on these edges. `body.Index[0]` gives the first point in the body. Each edge has a source and destination point. So eg if `body.Index[0]` is 1, then (unless the body is empty) there will be at least one edge with `edge.Index = [1, 2]`. The code `if (C) { x = 1; } else { x = 2; }; f();`, will have two edges sharing a common destination:
  60
  61     Assume(1,2, C*, true)
  62     Assign(2,4, x := 1)
  63     Assume(1,3, C*, false)
  64     Assign(3,4, x := 2)
  65     Call(4,5, f())
  66
  67 Note that the above syntax is part of the default output of `xdbfind src_body.xdb <functionName>`. It is a much-simplified version of the full JSON output from `xdbfind -json src_body.xdb <functionName>`. It will be used in this document to describe examples because the JSON output is much too verbose.
  68
  69 Every body is a directed acyclic graph (DAG), stored as a set of edges with source,destination point tuples. Any cycles in the original flow graph are replaced with Loop edges (see below).
  70
  71 ## Edges
  72
  73 The edges are stored in an array named `PEdge`, with properties:
  74
  75 - `.Index[]`: a 2-tuple giving the source and destination points.
  76 - `.Kind`: One of 7 different Kinds. The rest of the attributes will depend on this Kind.
  77
  78 Sixgill boils the control flow graph down to a small set of edge Kinds:
  79
  80 ### Assign
  81
  82 - `.Exp[]`: a 2-tuple of [lhs, rhs] of the assignment, each an expression (see `Expressions`, below.)
  83 - `.Type`: the overall type of the expression, which I believe is the type of the lhs? (See `Types`, below.)
  84
  85 Note that `Call` is also used for assignments, when the result of the function call is being assigned to a variable.
  86
  87 ### Call
  88
  89 - `.Exp[0]`: an expression representing the function being called (the "callee"). The callee might be a simple function, in which case `exp.Kind == "Var"`. Or it could be a computed function pointer or whatever. The expression evaluates to the function being called.
  90 - `.Exp[1]` (optional): where to assign the return value.
  91 - `.PEdgeCallArguments[]`: an array of expressions, one for each argument being passed. This does not include the `this` argument.
  92 - `.PEdgeCallInstance`: the expression for the object to call the method on, which will be passed as the `this` argument.
  93
  94 ### Assume
  95
  96 The destination of an `Assume` node can rely on the given value assumption, eg `Assume(1,2, __temp_1* == 7)` means that `__temp_1` will be 7 at point 2.
  97
  98 A conditional branch will be represented as a pair of `Assume` edges coming off of the expression for the branch condition. These edges produce a data flow graph where you can know the value of a variable if it has passed through an `Assume` edge (at least, until it reaches an `Assign` or `Call` edge.)
  99
 100 - `.Exp`: the expression being tested.
 101 - `.PEdgeAssumeNonZero`: if present, this will be set to true, and means we are on the edge where `Exp` is `!= 0`. If this is not present, then `Exp` is `0`.
 102
 103 Example: the C++ function body
 104
 105     SomeRAIIType raii;
 106     if (flipcoin()) {
 107       return 1;
 108     } else {
 109       return 2;
 110     }
 111
 112 could produce something like:
 113
 114     Call(3,4, __temp_1 := flipcoin())
 115     Assume(4,5, __temp_1*, true)
 116     Assume(4,6, __temp_1*, false)
 117     Assign(5,7, return := 1)
 118     Assign(6,7, return := 2)
 119     Call(7,8, raii.~__dt_comp ())
 120
 121 ### Loop
 122
 123 The edge corresponds to an entire loop. The meaning of a "loop" is subtle. It is mainly what is required to convert a general graph into a set of acyclic DAGs by finding back edges, and creating a "loop body" from the subgraph between the entry point (the destination of the back edge) and the source of the back edge. (Multiple back edges with a common destination will be a single loop.) Only the main body nodes that are necessary for (postdominated by) one of the back edges will be removed. Shared nodes will be cloned and will appear in both the main body and the loop body. The cloned nodes are described as "isomorphic".
 124
 125 - `.BlockId` : the `BlockId` of the loop body.
 126 - `.Loop` : an id like "loop#0" that will match up with the .BlockId.Loop property of the corresponding loop body.
 127
 128 Example: consider the C++ code
 129
 130     float testfunc(int val) {
 131       int x = val;
 132       x++;
 133     loophead:
 134       int y = x + 2;
 135       if (y == 8) goto loophead;
 136       y++;
 137       if (y == 10) return 2.4;
 138       if (y == 12) goto loophead;
 139       return 3.6;
 140     }
 141
 142 This will produce the loop body:
 143
 144     block: float32 testfunc(int32):loop#0
 145     parent: float32 testfunc(int32):3
 146     pentry: 1
 147     pexit:  6
 148     Assign(1,2, y := (x* + 2))
 149     Assume(2,6, (y* == 8), true)  /* 6 is the exit point, so loops back to the entry point 1 */
 150     Assume(2,3, (y* == 8), false)
 151     Assign(3,4, y := (y* + 1))
 152     Assume(4,5, (y* == 10), false)
 153     Assume(5,6, (y* == 12), true) /* 6 is the exit point, so loops back to the entry point 1 */
 154
 155 and the main body:
 156
 157     block: float32 testfunc(int32)
 158     pentry: 1
 159     pexit:  11
 160     isomorphic: [4,5,6,7,9]
 161     Assign(1,2, x := val*)
 162     Assign(2,3, x := (x* + 1))
 163     Loop(3,4, loop#0)
 164     Assign(4,5, y := (x* + 2))       /* edge is also in the loop */
 165     Assume(5,6, (y* == 8), false)    /* edge is also in the loop */
 166     Assign(6,7, y := (y* + 1))       /* edge is also in the loop */
 167     Assume(7,8, (y* == 10), true)
 168     Assume(7,9, (y* == 10), false)   /* edge is also in the loop */
 169     Assign(8,11, return := 2.4)
 170     Assume(9,10, (y* == 12), false)
 171     Assign(10,11, return := 3.6)
 172
 173 The isomorphic points correspond to the C++ code:
 174
 175     y = x + 2;
 176     if (y == 8) /* when y != 8 */
 177     y++;
 178     if (y == 10) /* when y != 10 */
 179
 180 which is the code that will execute in order to reach the post-loop edge `Assume(9,10, (y* == 12), false)`. (If point 9 in the main body is reached and y _is_ equal to 12, then the `Assume(9,10,...)` edge will not be taken. Point 9 in the main body corresponds to point 5 in the loop body, so the edge `Assume(5,6, (y* == 12), true)` will be taken instead.) When "control flow" is at an isomorphic point, it can be considered to be at all "instantiations" of that point at the same time. Really, though, these are acyclic data flow graphs where a loop's exit point is externally known to flow into the entry point, and the main body lacks any `Assume` or other back edges that would make it cyclic.
 181
 182 For a `while` loop, the isomorphic points will evaluate the conditional expression.
 183
 184 Another example: the C++ code
 185
 186     void testfunc() {
 187       static Cell cell;
 188       RefPtr<float> v10;
 189       v10.assign_with_AddRef(&somefloat);
 190       while (flipcoin()) {
 191         v10.forget();
 192       }
 193     }
 194
 195 generates
 196
 197     block: void testfunc():loop#0
 198     parent: void testfunc():3
 199     pentry: 1
 200     pexit:  4
 201     Call(1,2, __temp_1 := flipcoin())
 202     Assume(2,3, __temp_1*, true)
 203     Call(3,4, v10.forget())
 204
 205     block: void testfunc()
 206     pentry: 1
 207     pexit:  7
 208     isomorphic: [3,4]
 209     Call(1,2, v10.assign_with_AddRef(somefloat))
 210     Loop(2,3, loop#0)
 211     Call(3,4, __temp_1 := flipcoin())
 212     Assume(4,5, __temp_1*, false)
 213     Call(5,6, v10.~__dt_comp ())
 214
 215 The first block is the loop body, the second is the main body. Points 3 and 4 of the main body are equivalent to points 1 and 2 of the loop body. Notice the "parent" field of the loop body, which gives the equivalent point (3) of the loop's entry point in the body main.
 216
 217 ### Assembly
 218
 219 An opaque wad of assembly code.
 220
 221 ### Annotation
 222
 223 I'm not sure if I've seen these? They might be for the old annotation mechanism.
 224
 225 ### Skip
 226
 227 These appear to be internal "epsilon" edges to simplify graph building and loop splitting. They are removed before the final CFG is emitted.
 228
 229 ## Expressions
 230
 231 Expressions are the bulk of the CFG.
 232
 233 - `.Width` (optional) : width in bits. I'm not sure when this is used. It is much more common for a Type to have a width.
 234 - `.Unsigned` (optional) : boolean saying that this expression is unsigned.
 235 - `.Kind` : one of the following values
 236
 237 ### Program lvalues
 238
 239 - "Empty" : used in limited contexts when nothing is needed.
 240 - "Var" : expression referring to a variable
 241   - `.Type`
 242 - "Drf" : dereference (as in, \*foo or foo->... or something implicit)
 243   - `.Exp[0]` : target being dereferenced
 244   - `.Type`
 245 - "Fld"
 246   - `.Exp[0]` : target object containing the field
 247   - `.Field`
 248     - `.Name[]` : 2-tuple of [qualified name, unqualified name]
 249       - can be unnamed, in which case the name will be "field:<number>". This is used for base classes.
 250     - `.FieldCSU` : type of the CSU that the field is a member of
 251     - `.Type` : type of the field
 252     - `.FieldInstanceFunction` : "whether this is a virtual instance function rather than data field of the containing CSU". Presence or absence is what matters. All examples I have seen are for pure virtual functions (`virtual void foo() = 0`).
 253     - `.Annotation[]` : any annotations on the specific field
 254 - "Rfld" : ? some kind of "reverse" field access
 255   - same children as Fld
 256 - "Index" : array element access
 257   - `.Exp[0]` : the target array
 258   - `.Index` : the index being accessed (an Exp)
 259   - `.Type` : the type of the element
 260 - "String" : string constant
 261   - `.Type` : the type of the string
 262   - `.Count` : number of elements (chars) in the string
 263   - `.String` : the actual data in the string
 264 - "Clobber" : "additional lvalue generated by the memory model" (?)
 265   - callee
 266   - overwrite
 267   - optional value kind
 268   - point
 269   - optional location
 270
 271 ### Program rvalues
 272
 273 - "Int", "Float" : constant values
 274   - `.String` : the string form of the value (this is the only way the value is stored)
 275 - "Unop", "Binop" : operators
 276   - `.OpCode` : the various opcodes
 277   - `.Exp[0]` and `.Exp[1]` (the latter for Binop only) : parameters
 278   - stride type (optional)
 279
 280 ### Expression modifiers
 281
 282 - "Exit", "Initial" : ?
 283   - `.Exp[0]` : target expression
 284   - value kind (optional)
 285 - "Val" : ?
 286   - lvalue
 287   - value kind (optional)
 288   - index (body point)
 289   - boolean saying whether it is relative (?)
 290 - "Frame" : (unused)
 291
 292 ### Immutable properties
 293
 294 These appear to be synthetic properties intended for the built-in analyses that we are not using.
 295
 296 - "NullTest" : ?
 297   - `.Exp[0]` : target being tested
 298 - "Bound" : ? appears to be bounds-checked index access
 299   - bound kind
 300   - stride type
 301   - `.Exp[0]` (optional) : target that the bound applies to
 302 - "Directive" : ?
 303   - directive kind
 304
 305 ### Mutable properties
 306
 307 These appear to be synthetic properties intended for the built-in analyses that we are not using.
 308
 309 - "Terminate"
 310   - stride type
 311   - terminate test (Exp)
 312   - terminate int (Exp)
 313   - `.Exp[0]` (optional) : target
 314 - "GCSafe" : (unused)
 315   - `.Exp[0]` (optional) : target
 316
 317 ## Types
 318
 319 - `.Kind` : the kind of type being described, one of:
 320
 321 Possible Type Kinds:
 322
 323 - "Void" : the C/C++ void type
 324 - "Int"
 325   - `.Width` : width in bits
 326   - `.Sign` (optional) : whether the type is signed
 327   - `.Variant` (optional) : ?
 328 - "Float"
 329   - `.Width` : width in bits
 330 - "Pointer" : pointer or reference type
 331   - `.Width` : width in bits
 332   - `.Reference` : 0 for pointer, 1 for regular reference, 2 for rvalue reference
 333   - `.Type` : type of the target
 334 - "Array"
 335   - `.Type` : type of the elements
 336   - `.Count` : number of elements, given as a plain constant integer
 337 - "CSU" : class, structured, or union
 338   - `.Name` : qualified name, as a plain string
 339 - "Function"
 340   - `.TypeFunctionCSU` (optional) : if present, the type of the CSU containing the function
 341   - `.FunctionVarArgs` (?) (optional) : if this is present, the function is varargs (eg f(...))
 342   - `.TypeFunctionArgument` : array of argument types. Present if at least one parameter.
 343     - `.Type` : type of argument
 344     - `.Annotation` (optional) : any explicit annotations (**attribute**((foo))) for this parameter
 345   - `.Variable` : the variable representing the function
 346   - `.Annotation` (optional) : any explicit annotation for this function
 347 - "Error" : there was an error handling this type in sixgill. Probably something unimplemented.