diff options
Diffstat (limited to 'Documentation')
| -rw-r--r-- | Documentation/IR.md | 356 | ||||
| -rw-r--r-- | Documentation/IR.rst | 411 | ||||
| -rw-r--r-- | Documentation/api.rst | 1 | ||||
| -rw-r--r-- | Documentation/conf.py | 1 | ||||
| -rw-r--r-- | Documentation/doc-guide.rst | 4 | ||||
| -rw-r--r-- | Documentation/index.rst | 2 | ||||
| -rwxr-xr-x | Documentation/sphinx/ir.py | 75 |
7 files changed, 493 insertions, 357 deletions
diff --git a/Documentation/IR.md b/Documentation/IR.md deleted file mode 100644 index 03fa3f80..00000000 --- a/Documentation/IR.md +++ /dev/null @@ -1,356 +0,0 @@ -# Sparse's Intermediate Representation - - -## Instruction -This document briefly describes which field of struct instruction is -used by which operation. - -Some of those fields are used by almost all instructions, -some others are specific to only one or a few instructions. -The common ones are: -- .src1, .src2, .src3: (pseudo_t) operands of binops or ternary ops. -- .src: (pseudo_t) operand of unary ops (alias for .src1). -- .target: (pseudo_t) result of unary, binary & ternary ops, is sometimes used - otherwise by some others instructions. -- .cond: (pseudo_t) input operands for condition (alias .src/.src1) -- .type: (symbol*) usually the type of .result, sometimes of the operands - -### Terminators -#### OP_RET -Return from subroutine. -- .src : returned value (NULL if void) -- .type: type of .src - -#### OP_BR -Unconditional branch -- .bb_true: destination basic block - -#### OP_CBR -Conditional branch -- .cond: condition -- .type: type of .cond, must be an integral type -- .bb_true, .bb_false: destination basic blocks - -#### OP_SWITCH -Switch / multi-branch -- .cond: condition -- .type: type of .cond, must be an integral type -- .multijmp_list: pairs of case-value - destination basic block - -#### OP_COMPUTEDGOTO -Computed goto / branch to register -- .src: address to branch to (void*) -- .multijmp_list: list of possible destination basic blocks - -### Arithmetic binops -They all follow the same signature: -- .src1, .src1: operands (types must be compatible with .target) -- .target: result of the operation (must be an integral type) -- .type: type of .target - -#### OP_ADD -Integer addition. - -#### OP_SUB -Integer subtraction. - -#### OP_MUL -Integer multiplication. - -#### OP_DIVU -Integer unsigned division. - -#### OP_DIVS -Integer signed division. - -#### OP_MODU -Integer unsigned remainder. - -#### OP_MODS -Integer signed remainder. - -#### OP_SHL -Shift left (integer only) - -#### OP_LSR -Logical Shift right (integer only) - -#### OP_ASR -Arithmetic Shift right (integer only) - -### Floating-point binops -They all follow the same signature: -- .src1, .src1: operands (types must be compatible with .target) -- .target: result of the operation (must be a floating-point type) -- .type: type of .target - -#### OP_FADD -Floating-point addition. - -#### OP_FSUB -Floating-point subtraction. - -#### OP_FMUL -Floating-point multiplication. - -#### OP_FDIV -Floating-point division. - -### Logical ops -They all follow the same signature: -- .src1, .src2: operands (types must be compatible with .target) -- .target: result of the operation -- .type: type of .target, must be an integral type - -#### OP_AND -#### OP_OR -#### OP_XOR - -### Boolean ops -#### OP_AND_BOOL -#### OP_OR_BOOL - -### Integer compares -They all have the following signature: -- .src1, .src2: operands (types must be compatible) -- .target: result of the operation (0/1 valued integer) -- .type: type of .target, must be an integral type - -#### OP_SET_EQ -Compare equal. - -#### OP_SET_NE -Compare not-equal. - -#### OP_SET_LE -Compare less-than-or-equal (signed). - -#### OP_SET_GE -Compare greater-than-or-equal (signed). - -#### OP_SET_LT -Compare less-than (signed). - -#### OP_SET_GT -Compare greater-than (signed). - -#### OP_SET_B -Compare less-than (unsigned). - -#### OP_SET_A -Compare greater-than (unsigned). - -#### OP_SET_BE -Compare less-than-or-equal (unsigned). - -#### OP_SET_AE -Compare greater-than-or-equal (unsigned). - -### Floating-point compares -They all have the same signature as the integer compares. -The usual 6 operations exist in two versions: 'ordered' and -'unordered'. Theses operations first check if any operand is a -NaN and if it is the case the ordered compares return false -and then unordered return true, otherwise the result of the -comparison, now garanted to be done on non-NaNs, is returned. - -#### OP_FCMP_OEQ -Floating-point compare ordered equal - -#### OP_FCMP_ONE -Floating-point compare ordered not-equal - -#### OP_FCMP_OLE -Floating-point compare ordered less-than-or-equal - -#### OP_FCMP_OGE -Floating-point compare ordered greater-or-equal - -#### OP_FCMP_OLT -Floating-point compare ordered less-than - -#### OP_FCMP_OGT -Floating-point compare ordered greater-than - - -#### OP_FCMP_UEQ -Floating-point compare unordered equal - -#### OP_FCMP_UNE -Floating-point compare unordered not-equal - -#### OP_FCMP_ULE -Floating-point compare unordered less-than-or-equal - -#### OP_FCMP_UGE -Floating-point compare unordered greater-or-equal - -#### OP_FCMP_ULT -Floating-point compare unordered less-than - -#### OP_FCMP_UGT -Floating-point compare unordered greater-than - - -#### OP_FCMP_ORD -Floating-point compare ordered: return true if both operands are ordered -(none of the operands are a NaN) and false otherwise. - -#### OP_FCMP_UNO -Floating-point compare unordered: return false if no operands is ordered -and true otherwise. - -### Unary ops -#### OP_NOT -Logical not. -- .src: operand (type must be compatible with .target) -- .target: result of the operation -- .type: type of .target, must be an integral type - -#### OP_NEG -Integer negation. -- .src: operand (type must be compatible with .target) -- .target: result of the operation (must be an integral type) -- .type: type of .target - -#### OP_FNEG -Floating-point negation. -- .src: operand (type must be compatible with .target) -- .target: result of the operation (must be a floating-point type) -- .type: type of .target - -#### OP_COPY -Copy (only needed after out-of-SSA). -- .src: operand (type must be compatible with .target) -- .target: result of the operation -- .type: type of .target - -### Type conversions -They all have the following signature: -- .src: source value -- .orig_type: type of .src -- .target: result value -- .type: type of .target - -#### OP_CAST -Cast to unsigned integer (and to void pointer). - -#### OP_SCAST -Cast to signed integer. - -#### OP_FPCAST -Cast to floating-point. - -#### OP_PTRCAST -Cast to pointer. - -### Ternary ops -#### OP_SEL -- .src1: condition, must be of integral type -- .src2, .src3: operands (types must be compatible with .target) -- .target: result of the operation -- .type: type of .target - -#### OP_RANGE -Range/bounds checking (only used for an unused sparse extension). -- .src1: value to be checked -- .src2, src3: bound of the value (must be constants?) -- .type: type of .src[123]? - -### Memory ops -#### OP_LOAD -Load. -- .src: base address to load from -- .offset: address offset -- .target: loaded value -- .type: type of .target - -#### OP_STORE -Store. -- .src: base address to store to -- .offset: address offset -- .target: value to be stored -- .type: type of .target - -### Others -#### OP_SYMADDR -Create a pseudo corresponding to the address of a symbol. -- .symbol: (pseudo_t) input symbol (alias .src) -- .target: symbol's address - -#### OP_SETFVAL -Create a pseudo corresponding to a floating-point literal. -- .fvalue: the literal's value (long double) -- .target: the corresponding pseudo -- .type: type of the literal & .target - -#### OP_SETVAL -Create a pseudo corresponding to a string literal or a label-as-value. -The value is given as an expression EXPR_STRING or EXPR_LABEL. -- .val: (expression) input expression -- .target: the resulting value -- .type: type of .target, the value - -#### OP_PHI -Phi-node (for SSA form). -- .phi_list: phi-operands (type must be compatible with .target) -- .target: "result" -- .type: type of .target - -#### OP_PHISOURCE -Phi-node source. -Like OP_COPY but exclusively used to give a defining instructions -(and thus also a type) to *all* OP_PHI operands. -- .phi_src: operand (type must be compatible with .target, alias .src) -- .target: the "result" PSEUDO_PHI -- .type: type of .target -- .phi_users: list of phi instructions using the target pseudo - -#### OP_CALL -Function call. -- .func: (pseudo_t) the function (can be a symbol or a "register", alias .src)) -- .arguments: (pseudo_list) list of the associated arguments -- .target: function return value (if any) -- .type: type of .target -- .fntypes: (symbol_list) list of the function's types: the first enrty is the full function type, the next ones are the type of each arguments - -#### OP_INLINED_CALL -Only used as an annotation to show that the instructions just above -correspond to a function that have been inlined. -- .func: (pseudo_t) the function (must be a symbol, alias .src)) -- .arguments: list of pseudos that where the function's arguments -- .target: function return value (if any) -- .type: type of .target - -#### OP_SLICE -Extract a "slice" from an aggregate. -- .base: (pseudo_t) aggregate (alias .src) -- .from, .len: offet & size of the "slice" within the aggregate -- .target: result -- .type: type of .target - -#### OP_ASM -Inlined assembly code. -- .string: asm template -- .asm_rules: asm constraints, rules - -### Sparse tagging (line numbers, context, whatever) -#### OP_CONTEXT -Currently only used for lock/unlock tracking. -- .context_expr: unused -- .increment: (1 for locking, -1 for unlocking) -- .check: (ignore the instruction if 0) - -### Misc ops -#### OP_ENTRY -Function entry point (no associated semantic). - -#### OP_BADOP -Invalid operation (should never be generated). - -#### OP_NOP -No-op (should never be generated). - -#### OP_DEATHNOTE -Annotation telling the pseudo will be death after the next -instruction (other than some other annotation, that is). diff --git a/Documentation/IR.rst b/Documentation/IR.rst new file mode 100644 index 00000000..67ef06a5 --- /dev/null +++ b/Documentation/IR.rst @@ -0,0 +1,411 @@ +.. default-domain:: ir + +Sparse's Intermediate Representation +==================================== + +Instructions +~~~~~~~~~~~~ + +This document briefly describes which field of struct instruction is +used by which operation. + +Some of those fields are used by almost all instructions, +some others are specific to only one or a few instructions. +The common ones are: + +* .src1, .src2, .src3: (pseudo_t) operands of binops or ternary ops. +* .src: (pseudo_t) operand of unary ops (alias for .src1). +* .target: (pseudo_t) result of unary, binary & ternary ops, is + sometimes used otherwise by some others instructions. +* .cond: (pseudo_t) input operands for condition (alias .src/.src1) +* .type: (symbol*) usually the type of .result, sometimes of the operands + +Terminators +----------- +.. op:: OP_RET + Return from subroutine. + + * .src : returned value (NULL if void) + * .type: type of .src + +.. op:: OP_BR + Unconditional branch + + * .bb_true: destination basic block + +.. op:: OP_CBR + Conditional branch + + * .cond: condition + * .type: type of .cond, must be an integral type + * .bb_true, .bb_false: destination basic blocks + +.. op:: OP_SWITCH + Switch / multi-branch + + * .cond: condition + * .type: type of .cond, must be an integral type + * .multijmp_list: pairs of case-value - destination basic block + +.. op:: OP_COMPUTEDGOTO + Computed goto / branch to register + + * .src: address to branch to (void*) + * .multijmp_list: list of possible destination basic blocks + +Arithmetic binops +----------------- +They all follow the same signature: + * .src1, .src1: operands (types must be compatible with .target) + * .target: result of the operation (must be an integral type) + * .type: type of .target + +.. op:: OP_ADD + Integer addition. + +.. op:: OP_SUB + Integer subtraction. + +.. op:: OP_MUL + Integer multiplication. + +.. op:: OP_DIVU + Integer unsigned division. + +.. op:: OP_DIVS + Integer signed division. + +.. op:: OP_MODU + Integer unsigned remainder. + +.. op:: OP_MODS + Integer signed remainder. + +.. op:: OP_SHL + Shift left (integer only) + +.. op:: OP_LSR + Logical Shift right (integer only) + +.. op:: OP_ASR + Arithmetic Shift right (integer only) + +Floating-point binops +--------------------- +They all follow the same signature: + * .src1, .src1: operands (types must be compatible with .target) + * .target: result of the operation (must be a floating-point type) + * .type: type of .target + +.. op:: OP_FADD + Floating-point addition. + +.. op:: OP_FSUB + Floating-point subtraction. + +.. op:: OP_FMUL + Floating-point multiplication. + +.. op:: OP_FDIV + Floating-point division. + +Logical ops +----------- +They all follow the same signature: + * .src1, .src2: operands (types must be compatible with .target) + * .target: result of the operation + * .type: type of .target, must be an integral type + +.. op:: OP_AND + Logical AND + +.. op:: OP_OR + Logical OR + +.. op:: OP_XOR + Logical XOR + +Boolean ops +----------- +.. op:: OP_AND_BOOL + Boolean AND + +.. op:: OP_OR_BOOL + Boolean OR + +Integer compares +---------------- +They all have the following signature: + * .src1, .src2: operands (types must be compatible) + * .target: result of the operation (0/1 valued integer) + * .type: type of .target, must be an integral type + +.. op:: OP_SET_EQ + Compare equal. + +.. op:: OP_SET_NE + Compare not-equal. + +.. op:: OP_SET_LE + Compare less-than-or-equal (signed). + +.. op:: OP_SET_GE + Compare greater-than-or-equal (signed). + +.. op:: OP_SET_LT + Compare less-than (signed). + +.. op:: OP_SET_GT + Compare greater-than (signed). + +.. op:: OP_SET_B + Compare less-than (unsigned). + +.. op:: OP_SET_A + Compare greater-than (unsigned). + +.. op:: OP_SET_BE + Compare less-than-or-equal (unsigned). + +.. op:: OP_SET_AE + Compare greater-than-or-equal (unsigned). + +Floating-point compares +----------------------- +They all have the same signature as the integer compares. + +The usual 6 operations exist in two versions: 'ordered' and +'unordered'. These operations first check if any operand is a +NaN and if it is the case the ordered compares return false +and then unordered return true, otherwise the result of the +comparison, now guaranteed to be done on non-NaNs, is returned. + +.. op:: OP_FCMP_OEQ + Floating-point compare ordered equal + +.. op:: OP_FCMP_ONE + Floating-point compare ordered not-equal + +.. op:: OP_FCMP_OLE + Floating-point compare ordered less-than-or-equal + +.. op:: OP_FCMP_OGE + Floating-point compare ordered greater-or-equal + +.. op:: OP_FCMP_OLT + Floating-point compare ordered less-than + +.. op:: OP_FCMP_OGT + Floating-point compare ordered greater-than + + +.. op:: OP_FCMP_UEQ + Floating-point compare unordered equal + +.. op:: OP_FCMP_UNE + Floating-point compare unordered not-equal + +.. op:: OP_FCMP_ULE + Floating-point compare unordered less-than-or-equal + +.. op:: OP_FCMP_UGE + Floating-point compare unordered greater-or-equal + +.. op:: OP_FCMP_ULT + Floating-point compare unordered less-than + +.. op:: OP_FCMP_UGT + Floating-point compare unordered greater-than + + +.. op:: OP_FCMP_ORD + Floating-point compare ordered: return true if both operands are ordered + (none of the operands are a NaN) and false otherwise. + +.. op:: OP_FCMP_UNO + Floating-point compare unordered: return false if no operands is ordered + and true otherwise. + +Unary ops +--------- +.. op:: OP_NOT + Logical not. + + * .src: operand (type must be compatible with .target) + * .target: result of the operation + * .type: type of .target, must be an integral type + +.. op:: OP_NEG + Integer negation. + + * .src: operand (type must be compatible with .target) + * .target: result of the operation (must be an integral type) + * .type: type of .target + +.. op:: OP_FNEG + Floating-point negation. + + * .src: operand (type must be compatible with .target) + * .target: result of the operation (must be a floating-point type) + * .type: type of .target + +.. op:: OP_COPY + Copy (only needed after out-of-SSA). + + * .src: operand (type must be compatible with .target) + * .target: result of the operation + * .type: type of .target + +Type conversions +---------------- +They all have the following signature: + * .src: source value + * .orig_type: type of .src + * .target: result value + * .type: type of .target + +.. op:: OP_CAST + Cast to unsigned integer (and to void pointer). + +.. op:: OP_SCAST + Cast to signed integer. + +.. op:: OP_FPCAST + Cast to floating-point. + +.. op:: OP_PTRCAST + Cast to pointer. + +Ternary ops +----------- +.. op:: OP_SEL + * .src1: condition, must be of integral type + * .src2, .src3: operands (types must be compatible with .target) + * .target: result of the operation + * .type: type of .target + +.. op:: OP_RANGE + Range/bounds checking (only used for an unused sparse extension). + + * .src1: value to be checked + * .src2, src3: bound of the value (must be constants?) + * .type: type of .src[123]? + +Memory ops +---------- +.. op:: OP_LOAD + Load. + + * .src: base address to load from + * .offset: address offset + * .target: loaded value + * .type: type of .target + +.. op:: OP_STORE + Store. + + * .src: base address to store to + * .offset: address offset + * .target: value to be stored + * .type: type of .target + +Others +------ +.. op:: OP_SYMADDR + Create a pseudo corresponding to the address of a symbol. + + * .symbol: (pseudo_t) input symbol (alias .src) + * .target: symbol's address + +.. op:: OP_SETFVAL + Create a pseudo corresponding to a floating-point literal. + + * .fvalue: the literal's value (long double) + * .target: the corresponding pseudo + * .type: type of the literal & .target + +.. op:: OP_SETVAL + Create a pseudo corresponding to a string literal or a label-as-value. + The value is given as an expression EXPR_STRING or EXPR_LABEL. + + * .val: (expression) input expression + * .target: the resulting value + * .type: type of .target, the value + +.. op:: OP_PHI + Phi-node (for SSA form). + + * .phi_list: phi-operands (type must be compatible with .target) + * .target: "result" + * .type: type of .target + +.. op:: OP_PHISOURCE + Phi-node source. + Like OP_COPY but exclusively used to give a defining instructions + (and thus also a type) to *all* OP_PHI operands. + + * .phi_src: operand (type must be compatible with .target, alias .src) + * .target: the "result" PSEUDO_PHI + * .type: type of .target + * .phi_users: list of phi instructions using the target pseudo + +.. op:: OP_CALL + Function call. + + * .func: (pseudo_t) the function (can be a symbol or a "register", + alias .src)) + * .arguments: (pseudo_list) list of the associated arguments + * .target: function return value (if any) + * .type: type of .target + * .fntypes: (symbol_list) list of the function's types: the first + entry is the full function type, the next ones are the type of + each arguments + +.. op:: OP_INLINED_CALL + Only used as an annotation to show that the instructions just above + correspond to a function that have been inlined. + + * .func: (pseudo_t) the function (must be a symbol, alias .src)) + * .arguments: list of pseudos that where the function's arguments + * .target: function return value (if any) + * .type: type of .target + +.. op:: OP_SLICE + Extract a "slice" from an aggregate. + + * .base: (pseudo_t) aggregate (alias .src) + * .from, .len: offet & size of the "slice" within the aggregate + * .target: result + * .type: type of .target + +.. op:: OP_ASM + Inlined assembly code. + + * .string: asm template + * .asm_rules: asm constraints, rules + +Sparse tagging (line numbers, context, whatever) +------------------------------------------------ +.. op:: OP_CONTEXT + Currently only used for lock/unlock tracking. + + * .context_expr: unused + * .increment: (1 for locking, -1 for unlocking) + * .check: (ignore the instruction if 0) + +Misc ops +-------- +.. op:: OP_ENTRY + Function entry point (no associated semantic). + +.. op:: OP_BADOP + Invalid operation (should never be generated). + +.. op:: OP_NOP + No-op (should never be generated). + +.. op:: OP_DEATHNOTE + Annotation telling the pseudo will be death after the next + instruction (other than some other annotation, that is). + +.. # vim: tabstop=4 diff --git a/Documentation/api.rst b/Documentation/api.rst index d1a1d3ca..1270551c 100644 --- a/Documentation/api.rst +++ b/Documentation/api.rst @@ -9,6 +9,7 @@ Utilities ~~~~~~~~~ .. c:autodoc:: ptrlist.c +.. c:autodoc:: utils.h Parsing ~~~~~~~ diff --git a/Documentation/conf.py b/Documentation/conf.py index f7a68014..aae9d39b 100644 --- a/Documentation/conf.py +++ b/Documentation/conf.py @@ -29,6 +29,7 @@ needs_sphinx = '1.3' sys.path.insert(0, os.path.abspath('sphinx')) extensions = [ 'cdoc' + , 'ir' ] # support .md with python2 & python3 diff --git a/Documentation/doc-guide.rst b/Documentation/doc-guide.rst index 80ec82c2..8133cb3a 100644 --- a/Documentation/doc-guide.rst +++ b/Documentation/doc-guide.rst @@ -149,3 +149,7 @@ will be displayed like this: It's strongly encouraged to use this function instead of open coding a simple ``++``. + +Intermediate Representation +--------------------------- +.. c:autodoc:: Documentation/sphinx/ir.py diff --git a/Documentation/index.rst b/Documentation/index.rst index da006710..9825c8cd 100644 --- a/Documentation/index.rst +++ b/Documentation/index.rst @@ -20,8 +20,8 @@ Developer documentation test-suite dev-options - IR api + IR doc-guide How to contribute diff --git a/Documentation/sphinx/ir.py b/Documentation/sphinx/ir.py new file mode 100755 index 00000000..3028200a --- /dev/null +++ b/Documentation/sphinx/ir.py @@ -0,0 +1,75 @@ +#!/usr/bin/env python +# SPDX_License-Identifier: MIT +# +# Copyright (C) 2018 Luc Van Oostenryck <luc.vanoostenryck@gmail.com> +# + +""" +/// +// To document the instructions used in the intermediate representation +// a new domain is defined: 'ir' with a directive:: +// +// .. op: <OP_NAME> +// <description of OP_NAME> +// ... +// +// This is equivalent to using a definition list but with the name +// also placed in the index (with 'IR instruction' as descriptions). + +""" + +import docutils +import sphinx + +class IROpDirective(docutils.parsers.rst.Directive): + + # use the first line of content as the argument, this allow + # to not have to write a blanck line after the directive + final_argument_whitespace = True + required_argument = 0 + #optional_arguments = 0 + has_content = True + + objtype = None + + def run(self): + self.env = self.state.document.settings.env + + source = self.state.document + lineno = self.lineno + text = self.content + name = text[0] + + node = docutils.nodes.section() + node['ids'].append(name) + node.document = source + + index = '.. index:: pair: %s; IR instruction' % name + content = docutils.statemachine.ViewList() + content.append(index, source, lineno) + content.append('' , source, lineno) + content.append(name , source, lineno) + content.append('' , source, lineno) + self.state.nested_parse(content, self.content_offset, node) + + defnode = docutils.nodes.definition() + self.state.nested_parse(text[1:], self.content_offset, defnode) + node.append(defnode) + + return [node] + +class IRDomain(sphinx.domains.Domain): + + """IR domain.""" + name = 'ir' + +def setup(app): + app.add_domain(IRDomain) + app.add_directive_to_domain('ir', 'op', IROpDirective) + + return { + 'version': '1.0', + 'parallel_read_safe': True, + } + +# vim: tabstop=4 |