xref: /illumos-gate/usr/src/tools/smatch/src/Documentation/IR.rst (revision c85f09cc92abd00c84e58ec9f0f5d942906cb713)
1.. default-domain:: ir
2
3Sparse's Intermediate Representation
4====================================
5
6Instructions
7~~~~~~~~~~~~
8
9This document briefly describes which field of struct instruction is
10used by which operation.
11
12Some of those fields are used by almost all instructions,
13some others are specific to only one or a few instructions.
14The common ones are:
15
16* .src1, .src2, .src3: (pseudo_t) operands of binops or ternary ops.
17* .src: (pseudo_t) operand of unary ops (alias for .src1).
18* .target: (pseudo_t) result of unary, binary & ternary ops, is
19  sometimes used otherwise by some others instructions.
20* .cond: (pseudo_t) input operands for condition (alias .src/.src1)
21* .type: (symbol*) usually the type of .result, sometimes of the operands
22
23Terminators
24-----------
25.. op:: OP_RET
26	Return from subroutine.
27
28	* .src : returned value (NULL if void)
29	* .type: type of .src
30
31.. op:: OP_BR
32	Unconditional branch
33
34	* .bb_true: destination basic block
35
36.. op:: OP_CBR
37	Conditional branch
38
39	* .cond: condition
40	* .type: type of .cond, must be an integral type
41	* .bb_true, .bb_false: destination basic blocks
42
43.. op:: OP_SWITCH
44	Switch / multi-branch
45
46	* .cond: condition
47	* .type: type of .cond, must be an integral type
48	* .multijmp_list: pairs of case-value - destination basic block
49
50.. op:: OP_COMPUTEDGOTO
51	Computed goto / branch to register
52
53	* .src: address to branch to (void*)
54	* .multijmp_list: list of possible destination basic blocks
55
56Arithmetic binops
57-----------------
58They all follow the same signature:
59	* .src1, .src1: operands (types must be compatible with .target)
60	* .target: result of the operation (must be an integral type)
61	* .type: type of .target
62
63.. op:: OP_ADD
64	Integer addition.
65
66.. op:: OP_SUB
67	Integer subtraction.
68
69.. op:: OP_MUL
70	Integer multiplication.
71
72.. op:: OP_DIVU
73	Integer unsigned division.
74
75.. op:: OP_DIVS
76	Integer signed division.
77
78.. op:: OP_MODU
79	Integer unsigned remainder.
80
81.. op:: OP_MODS
82	Integer signed remainder.
83
84.. op:: OP_SHL
85	Shift left (integer only)
86
87.. op:: OP_LSR
88	Logical Shift right (integer only)
89
90.. op:: OP_ASR
91	Arithmetic Shift right (integer only)
92
93Floating-point binops
94---------------------
95They all follow the same signature:
96	* .src1, .src1: operands (types must be compatible with .target)
97	* .target: result of the operation (must be a floating-point type)
98	* .type: type of .target
99
100.. op:: OP_FADD
101	Floating-point addition.
102
103.. op:: OP_FSUB
104	Floating-point subtraction.
105
106.. op:: OP_FMUL
107	Floating-point multiplication.
108
109.. op:: OP_FDIV
110	Floating-point division.
111
112Logical ops
113-----------
114They all follow the same signature:
115	* .src1, .src2: operands (types must be compatible with .target)
116	* .target: result of the operation
117	* .type: type of .target, must be an integral type
118
119.. op:: OP_AND
120	Logical AND
121
122.. op:: OP_OR
123	Logical OR
124
125.. op:: OP_XOR
126	Logical XOR
127
128Integer compares
129----------------
130They all have the following signature:
131	* .src1, .src2: operands (types must be compatible)
132	* .target: result of the operation (0/1 valued integer)
133	* .type: type of .target, must be an integral type
134
135.. op:: OP_SET_EQ
136	Compare equal.
137
138.. op:: OP_SET_NE
139	Compare not-equal.
140
141.. op:: OP_SET_LE
142	Compare less-than-or-equal (signed).
143
144.. op:: OP_SET_GE
145	Compare greater-than-or-equal (signed).
146
147.. op:: OP_SET_LT
148	Compare less-than (signed).
149
150.. op:: OP_SET_GT
151	Compare greater-than (signed).
152
153.. op:: OP_SET_B
154	Compare less-than (unsigned).
155
156.. op:: OP_SET_A
157	Compare greater-than (unsigned).
158
159.. op:: OP_SET_BE
160	Compare less-than-or-equal (unsigned).
161
162.. op:: OP_SET_AE
163	Compare greater-than-or-equal (unsigned).
164
165Floating-point compares
166-----------------------
167They all have the same signature as the integer compares.
168
169The usual 6 operations exist in two versions: 'ordered' and
170'unordered'. These operations first check if any operand is a
171NaN and if it is the case the ordered compares return false
172and then unordered return true, otherwise the result of the
173comparison, now guaranteed to be done on non-NaNs, is returned.
174
175.. op:: OP_FCMP_OEQ
176	Floating-point compare ordered equal
177
178.. op:: OP_FCMP_ONE
179	Floating-point compare ordered not-equal
180
181.. op:: OP_FCMP_OLE
182	Floating-point compare ordered less-than-or-equal
183
184.. op:: OP_FCMP_OGE
185	Floating-point compare ordered greater-or-equal
186
187.. op:: OP_FCMP_OLT
188	Floating-point compare ordered less-than
189
190.. op:: OP_FCMP_OGT
191	Floating-point compare ordered greater-than
192
193
194.. op:: OP_FCMP_UEQ
195	Floating-point compare unordered equal
196
197.. op:: OP_FCMP_UNE
198	Floating-point compare unordered not-equal
199
200.. op:: OP_FCMP_ULE
201	Floating-point compare unordered less-than-or-equal
202
203.. op:: OP_FCMP_UGE
204	Floating-point compare unordered greater-or-equal
205
206.. op:: OP_FCMP_ULT
207	Floating-point compare unordered less-than
208
209.. op:: OP_FCMP_UGT
210	Floating-point compare unordered greater-than
211
212
213.. op:: OP_FCMP_ORD
214	Floating-point compare ordered: return true if both operands are ordered
215	(none of the operands are a NaN) and false otherwise.
216
217.. op:: OP_FCMP_UNO
218	Floating-point compare unordered: return false if no operands is ordered
219	and true otherwise.
220
221Unary ops
222---------
223.. op:: OP_NOT
224	Logical not.
225
226	* .src: operand (type must be compatible with .target)
227	* .target: result of the operation
228	* .type: type of .target, must be an integral type
229
230.. op:: OP_NEG
231	Integer negation.
232
233	* .src: operand (type must be compatible with .target)
234	* .target: result of the operation (must be an integral type)
235	* .type: type of .target
236
237.. op:: OP_FNEG
238	Floating-point negation.
239
240	* .src: operand (type must be compatible with .target)
241	* .target: result of the operation (must be a floating-point type)
242	* .type: type of .target
243
244.. op:: OP_SYMADDR
245	Create a pseudo corresponding to the address of a symbol.
246
247	* .src: input symbol (must be a PSEUDO_SYM)
248	* .target: symbol's address
249
250.. op:: OP_COPY
251	Copy (only needed after out-of-SSA).
252
253	* .src: operand (type must be compatible with .target)
254	* .target: result of the operation
255	* .type: type of .target
256
257Type conversions
258----------------
259They all have the following signature:
260	* .src: source value
261	* .orig_type: type of .src
262	* .target: result value
263	* .type: type of .target
264
265Currently, a cast to a void pointer is treated like a cast to
266an unsigned integer of the same size.
267
268.. op:: OP_TRUNC
269	Cast from integer to an integer of a smaller size.
270
271.. op:: OP_SEXT
272	Cast from integer to an integer of a bigger size with sign extension.
273
274.. op:: OP_ZEXT
275	Cast from integer to an integer of a bigger size with zero extension.
276
277.. op:: OP_UTPTR
278	Cast from pointer-sized unsigned integer to pointer type.
279
280.. op:: OP_PTRTU
281	Cast from pointer type to pointer-sized unsigned integer.
282
283.. op:: OP_PTRCAST
284	Cast between pointers.
285
286.. op:: OP_FCVTU
287	Conversion from float type to unsigned integer.
288
289.. op:: OP_FCVTS
290	Conversion from float type to signed integer.
291
292.. op:: OP_UCVTF
293	Conversion from unsigned integer to float type.
294
295.. op:: OP_SCVTF
296	Conversion from signed integer to float type.
297
298.. op:: OP_FCVTF
299	Conversion between float types.
300
301Ternary ops
302-----------
303.. op:: OP_SEL
304	* .src1: condition, must be of integral type
305	* .src2, .src3: operands (types must be compatible with .target)
306	* .target: result of the operation
307	* .type: type of .target
308
309.. op:: OP_RANGE
310	Range/bounds checking (only used for an unused sparse extension).
311
312	* .src1: value to be checked
313	* .src2, src3: bound of the value (must be constants?)
314	* .type: type of .src[123]?
315
316Memory ops
317----------
318.. op:: OP_LOAD
319	Load.
320
321	* .src: base address to load from
322	* .offset: address offset
323	* .target: loaded value
324	* .type: type of .target
325
326.. op:: OP_STORE
327	Store.
328
329	* .src: base address to store to
330	* .offset: address offset
331	* .target: value to be stored
332	* .type: type of .target
333
334Others
335------
336.. op:: OP_SETFVAL
337	Create a pseudo corresponding to a floating-point literal.
338
339	* .fvalue: the literal's value (long double)
340	* .target: the corresponding pseudo
341	* .type: type of the literal & .target
342
343.. op:: OP_SETVAL
344	Create a pseudo corresponding to a string literal or a label-as-value.
345	The value is given as an expression EXPR_STRING or EXPR_LABEL.
346
347	* .val: (expression) input expression
348	* .target: the resulting value
349	* .type: type of .target, the value
350
351.. op:: OP_PHI
352	Phi-node (for SSA form).
353
354	* .phi_list: phi-operands (type must be compatible with .target)
355	* .target: "result"
356	* .type: type of .target
357
358.. op:: OP_PHISOURCE
359	Phi-node source.
360	Like OP_COPY but exclusively used to give a defining instructions
361	(and thus also a type) to *all* OP_PHI operands.
362
363	* .phi_src: operand (type must be compatible with .target, alias .src)
364	* .target: the "result" PSEUDO_PHI
365	* .type: type of .target
366	* .phi_users: list of phi instructions using the target pseudo
367
368.. op:: OP_CALL
369	Function call.
370
371	* .func: (pseudo_t) the function (can be a symbol or a "register",
372	  alias .src))
373	* .arguments: (pseudo_list) list of the associated arguments
374	* .target: function return value (if any)
375	* .type: type of .target
376	* .fntypes: (symbol_list) list of the function's types: the first
377	  entry is the full function type, the next ones are the type of
378	  each arguments
379
380.. op:: OP_INLINED_CALL
381	Only used as an annotation to show that the instructions just above
382	correspond to a function that have been inlined.
383
384	* .func: (pseudo_t) the function (must be a symbol, alias .src))
385	* .arguments: list of pseudos that where the function's arguments
386	* .target: function return value (if any)
387	* .type: type of .target
388
389.. op:: OP_SLICE
390	Extract a "slice" from an aggregate.
391
392	* .base: (pseudo_t) aggregate (alias .src)
393	* .from, .len: offet & size of the "slice" within the aggregate
394	* .target: result
395	* .type: type of .target
396
397.. op:: OP_ASM
398	Inlined assembly code.
399
400	* .string: asm template
401	* .asm_rules: asm constraints, rules
402
403Sparse tagging (line numbers, context, whatever)
404------------------------------------------------
405.. op:: OP_CONTEXT
406	Currently only used for lock/unlock tracking.
407
408	* .context_expr: unused
409	* .increment: (1 for locking, -1 for unlocking)
410	* .check: (ignore the instruction if 0)
411
412Misc ops
413--------
414.. op:: OP_ENTRY
415	Function entry point (no associated semantic).
416
417.. op:: OP_BADOP
418	Invalid operation (should never be generated).
419
420.. op:: OP_NOP
421	No-op (should never be generated).
422
423.. op:: OP_DEATHNOTE
424	Annotation telling the pseudo will be death after the next
425	instruction (other than some other annotation, that is).
426
427.. # vim: tabstop=4
428