| FazBrowse GitHub Viewer | Trending | | Home |
| Tools: [Download Repo ZIP] [Original HTTPS Page] |
This specification focuses on the PDG model definition only, the representation syntaxes for portable exchange and visualization will be addressed in a separate document.
Companion files containing C source code and LLVM IR code are included to provide a running example that will be referenced throughout this document. The example.ll is generated by issuing the following command: clang -c -emit-llvm -g example.c
The Program Dependency Graph (PDG) is a graphical representation of a salient portion of the LLVM IR of a program; it is composed of PDG nodes and PDG edges. We use a TYPE_SUBTYPE naming convention for PDG nodes and PDG edges. We define two properties that we will use below:
The different types/subtypes of PDG nodes are listed below.
INST_FUNCALL,
INST_RET,
INST_BR,
INST_OTHER, // In the future, we may break out INST_INDBR and INST_SWITCH to capture the other types of branching instructions in LLVM
VAR_STATICALLOCGLOBALSCOPE, // C: global variable LLVM: global with common linkage
VAR_STATICALLOCMODULESCOPE, // C: static global variable LLVM: global with internal linkage
VAR_STATICALLOCFUNCTIONSCOPE, // C: static function variable LLVM: global with internal linkage, variable name is prefixed by function name
VAR_OTHER // In the future we may also call out VAR_STACK and VAR_HEAP
FUNCTIONENTRY,
PARAM_FORMALIN,
PARAM_FORMALOUT,
PARAM_ACTUALIN,
PARAM_ACTUALOUT
ANNOTATION_VAR,
ANNOTATION_GLOBAL, // PL propose splitting global annotation into variables and functions so we would have ANNOTATION_GLOBAL_FUNC and ANNOTATION_GLOBAL_VAR
ANNOTATION_OTHER, We define each node type/sub-type below and provide an example for each.
Description: The PDG nodes representing LLVM instructions have the type <INST>_. For convenience, we create separate subtypes for some instructions, and the rest are included in other. Each type of instruction node is disjoint and the union of each type is the universe of possible instruction nodes.
INST_FUNCALL Description: Represents an LLVM call instruction.
INST_RET Description: Represents an LLVM ret instruction.
INST_BR Description: Represents an LLVM br instruction that contains a condition.
INST_OTHER Description: Represents all other LLVM instructions not specified above. Future versions of this specification may call out instructions for switch and indirect branches as separate subtypes.
VAR_STATICGLOBAL Description: Represents the allocation site for a global variable.
VAR_STATICMODULE Description: Represents the allocation site for a static global variable.
VAR_STATICFUNCTION Description: Represents the allocation site for a static function variable.
VAR_OTHER Description: Represents a variable allocation site not captured by VAR_STATICGLOBAL, VAR_STATICMODULE, or VAR_STATICFUNCTION.
FUNCTIONENTRY Description: Defines an entry point to a function.
PARAM_FORMALIN Description: Associated with every formal parameter in a function is a tree of PARAM_FORMALIN node(s).
PARAM_FORMALOUT Description: Associated with every formal parameter in a function that is modified in the function body is a tree of PARAM_FORMALOUT node(s).
PARAM_ACTUALIN Description: Associated with every actual parameter of a function call is a tree of PARAM_ACTUALIN node(s).
PARAM_ACTUALOUT Description: Associated with every actual parameter received by the caller after the corresponding argument has been modified during the function call is a tree of PARAM_ACTUALOUT node(s).
ANNOTATION_VAR Description: Represents the annotation of a variable.
ANNOTATION_GLOBAL Description: Contains the annotations for exactly one function or global variable.
ANNOTATION_OTHER Description: Represents an annotation not captured by ANNOTATION_VAR or ANNOTATION_GLOBAL.
Listed below are some useful properties of PDG node types and subtypes. Recall that AllDisjoint(<set1>, <set2>, ..., <setn>) indicates the set(s) specified are disjoint, meaning their intersection is empty. Universe(<set1>, <set2>, ..., <setn>) results in the union of the specified set(s).
We summaizee the PDG edge types below.
CONTROLDEP_CALLINV,
CONTROLDEP_CALLRET,
CONTROLDEP_ENTRY,
CONTROLDEP_BR,
CONTROLDEP_OTHER,
DATADEP_DEFUSE,
DATADEP_RAW,
DATADEP_RET,
DATADEP_ALIAS,
PARAMETER_IN,
PARAMETER_OUT,
PARAMETER_FIELD,
ANNO_GLOBAL, // PL propose splitting global annotation edges into variables and functions so we would have ANNO_GLOBAL_FUNC and ANNO_GLOBAL_VAR
ANNO_VAR,
ANNO_OTHER,CONTROLDEP_CALLINV Description: CONTROLDEP_CALLINV edge connects an INST_FUNCALL node with the FUNCTIONENTRY node of callee. It indicates the control flow transition from the caller to callee.
CONTROLDEP_CALLRET Description: CONTROLDEP_CALLRET edge connects an INST_RET node with the corresponding INST_FUNCALL of the caller. It indicates the control flow transition from the callee back to the caller. If there are multiple INST_RET instructions, they will map to the same INST_FUNCALL node.
CONTROLDEP_ENTRY Description: Connects the FUNCTIONENTRY node with every INST_[TYPE] node that would be unconditionally executed inside a function body.
CONTROLDEP_BR Description: Connects an INST_BR node to every INST_[TYPE] node of the control-dependent basic block(s)'s.
CONTROLDEP_OTHER Description: Captures control dependencies not captured by the above.
DATADEP_DEFUSE Description: DATADEP_DEFUSE edge connects a def node (Either an INST_[Type] or VAR_[Type]) and use node (INST_[Type]). It is directly computed from the LLVM def-use chain.
DATADEP_RAW Description: DATA_RAW connects two INST_[Type] nodes with read-after-write dependence. This is flow-sensitive. We use memory dependency LLVM pass to compute this information.
DATADEP_RET Description: DATA_RET edge connects the return value from an Inst_RET node to the corresponding INST_FUNCALL node in the caller function. It indicates the data flow from the return instruction to the call instruction
DATADEP_ALIAS Description: DATA_ALIAS edge connects two nodes that have may-alias relations, meaning the source and destination node might (not must) refer to the same memory location. Note that if two nodes n1 and n2 have may-alias relation, then there are two DATA_ALIAS edges exist between them, one from n1 to n2 and one from n2 to n1. This is because the alias relation is bidirectional.
PARAMETER_IN Description: PARAMETER_IN edge represents interprocedural data flow from caller to the callee. It connects
actual_parameter_in_tree node and formal_in tree nodes
formal_in_tree node and the IR variables that correspond to these formal_in_tree nodes in the callee.
PARAMETER_OUT Description: edge represents data flow from callee to caller. It connects
arguments modified in callee to formal_out_tree node.
formal_out_tree node to actual_out_tree node.
actual_out_tree node to the modified variable in the caller.
PARAMETER_FIELD Description: PARAMETER_FIELD edge connects a parent parameter tree node to a child parameter tree node.
ANNO_GLOBAL Description: Connects FUNCTIONENTRY nodes or VAR_STATIC* nodes to ANNOTATION_GLOBAL nodes.
ANNO_VAR Description: Connects INST nodes or VAR_OTHER nodes to ANNOTATION_VAR nodes.
ANNO_OTHER Description: Connects a PDG node to an annotation type not captured by the above.
Listed below are useful properties of PDG edge types and subtypes.
| Version | Date | Comments |
|---|---|---|
| 1.0.2 | 4/14/2021 | Revised dcument based on discussion on 4/13/21. See requests from 4/13 for a complete list of changes. |
| 1.0.1 | 4/8/2021 | Added node and PDG definitions/properties and updated edge definitions/properties. Included example illustrating most nodes/edges. |
| 1.0.0 | 3/26/2021 | Initial Version |
| Request | Date | Description | Status | |
|---|---|---|---|---|
| Update DefUse example | 4/16/2021 | Pending | ||
| Update example to have multiple annotation labels | 4/14/2021 | Resolved | ||
| Update edge properties to include functions reachable from main | 4/13/2021 | Resolved | ||
| Update annotation node definition to include multiple labels | 4/13/2021 | Resolved | ||
| Remove VAR_DEP edges | 4/13/2021 | Resolved | ||
| Update def use to include static variables | 4/13/2021 | Resolved | ||
| Connect IR line 33 to line 35 in the alias example | 4/13/2021 | Resolved | ||
| Update control edges destinations | 4/13/2021 | Resolved | ||
| Update annotation global such that it can be broken into separate entities. | 4/13/2021 | Resolved | ||
| Define Control Edges | 4/5/2021 | Resolved | ||
| Define a PDG (a graph with nodes and edges) | 4/1/2021 | Resolved | ||
| Define all nodes | 4/1/2021 | Resolved | ||
| Try Structure the nodes such that node types are disjoint | 4/1/2021 | Resolved | ||
| Add an example for CONTROLDEP_IND_BR | 3/26/2021 | Not needed at this time | N/A | |
| PDG capture C at the moment. Need more changes on handling C++ in future. | 3/17/2021 | Unresolved | ||
| In C program, add function pointer (invoke) and indirect branch examples. | 3/17/2021 | Not needed at this time | N/A | |
| In C program, add two level pointer example. | 3/17/2021 | Unresolved | ||
| if an attributes can apply to more than one subtypes, make it an attribute of the type (a field). | 3/17/2021 | Unresolved | ||
| SUBTYPEs are disjointed; union of SUBTYPES is TYPE. | 3/17/2021 | Resolved | ||
| Use TYPE_SUBTYPE for node and edges. | 3/17/2021 | Resolved | ||
| create nodes for annotation instruction (must be a sink node). | 3/17/2021 | INST_ANNO_LOCAL INST_ANNO_GLOBAL | Resolved | |
| Create edges for ANNO_FUNC and ANNO_VAR. | 3/17/2021 | ANNO_FUNC: from function entry node to annotation node. ANNO_VAR: from variable node to annotation node. | Resolved | |
| Rename CONTROLDEP Edges | 3/17/2021 | CONTROLDEP_CALLINV CONTROLDEP_CALLRET CONTROLDEP_ENTRY CONTROLDEP_BR CONTROLDEP_IND_BR | Resolved | |
| For unhandled nodes and edges, label them with TYPE_OTHERNODE, TYPE_OTHEREDGE. | 3/17/2021 | Resolved | ||
| Add GLOBALVAR_GLOBAL / GLOBALVAR_LOCAL to represent global/static variables | 3/17/2021 | Resolved | ||
| Remove "sensitive" info from the annotation node. | 3/17/2021 | Resolved |
| Back | FazBrowse Home | New Git URL |