Skip to content

Commit c84d88f

Browse files
MathiasVPMathiasVP
authored
Merge pull request #12429 from MathiasVP/actually-implement-language-specific-flow-into-call-node-cand1
C++: Implement `getAdditionalFlowIntoCallNodeTerm`
2 parents 8308c66 + 5a6b94e commit c84d88f

2 files changed

Lines changed: 89 additions & 20 deletions

File tree

‎cpp/ql/lib/semmle/code/cpp/ir/dataflow/internal/DataFlowPrivate.qll‎

Lines changed: 73 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,8 @@ private import DataFlowDispatch
55
private import DataFlowImplConsistency
66
private import semmle.code.cpp.ir.internal.IRCppLanguage
77
private import SsaInternals as Ssa
8+
private import DataFlowImplCommon
9+
private import semmle.code.cpp.ir.ValueNumbering
810

911
cached
1012
private module Cached {
@@ -890,11 +892,81 @@ private class MyConsistencyConfiguration extends Consistency::ConsistencyConfigu
890892
}
891893
}
892894

895+
/**
896+
* Gets the basic block of `node`.
897+
*/
898+
IRBlock getBasicBlock(Node node) {
899+
node.asInstruction().getBlock() = result
900+
or
901+
node.asOperand().getUse().getBlock() = result
902+
or
903+
node.(SsaPhiNode).getPhiNode().getBasicBlock() = result
904+
or
905+
node.(RawIndirectOperand).getOperand().getUse().getBlock() = result
906+
or
907+
node.(RawIndirectInstruction).getInstruction().getBlock() = result
908+
or
909+
result = getBasicBlock(node.(PostUpdateNode).getPreUpdateNode())
910+
}
911+
893912
/**
894913
* Gets an additional term that is added to the `join` and `branch` computations to reflect
895914
* an additional forward or backwards branching factor that is not taken into account
896915
* when calculating the (virtual) dispatch cost.
897916
*
898917
* Argument `arg` is part of a path from a source to a sink, and `p` is the target parameter.
899918
*/
900-
int getAdditionalFlowIntoCallNodeTerm(ArgumentNode arg, ParameterNode p) { none() }
919+
pragma[nomagic]
920+
int getAdditionalFlowIntoCallNodeTerm(ArgumentNode arg, ParameterNode p) {
921+
exists(ParameterNode switchee, SwitchInstruction switch, ConditionOperand op, DataFlowCall call |
922+
viableParamArg(call, p, arg) and
923+
viableParamArg(call, switchee, _) and
924+
switch.getExpressionOperand() = op and
925+
valueNumber(switchee.asInstruction()).getAUse() = op and
926+
result = countNumberOfBranchesUsingParameter(switch, p)
927+
)
928+
}
929+
930+
/** Gets the `IRVariable` associated with the parameter node `p`. */
931+
pragma[nomagic]
932+
private IRVariable getIRVariableForParameterNode(ParameterNode p) {
933+
result = p.(DirectParameterNode).getIRVariable()
934+
or
935+
result.getAst() = p.(IndirectParameterNode).getParameter()
936+
}
937+
938+
/** Holds if `v` is the source variable corresponding to the parameter represented by `p`. */
939+
pragma[nomagic]
940+
private predicate parameterNodeHasSourceVariable(ParameterNode p, Ssa::SourceIRVariable v) {
941+
v.getIRVariable() = getIRVariableForParameterNode(p) and
942+
exists(Position pos | p.isParameterOf(_, pos) |
943+
pos instanceof DirectPosition and
944+
v.getIndirection() = 1
945+
or
946+
pos.(IndirectionPosition).getIndirectionIndex() + 1 = v.getIndirection()
947+
)
948+
}
949+
950+
private EdgeKind caseOrDefaultEdge() {
951+
result instanceof CaseEdge or
952+
result instanceof DefaultEdge
953+
}
954+
955+
/**
956+
* Gets the number of switch branches that that read from (or write to) the parameter `p`.
957+
*/
958+
int countNumberOfBranchesUsingParameter(SwitchInstruction switch, ParameterNode p) {
959+
exists(Ssa::SourceVariable sv |
960+
parameterNodeHasSourceVariable(p, sv) and
961+
// Count the number of cases that use the parameter. We do this by finding the phi node
962+
// that merges the uses/defs of the parameter. There might be multiple such phi nodes, so
963+
// we pick the one with the highest edge count.
964+
result =
965+
max(SsaPhiNode phi |
966+
switch.getSuccessor(caseOrDefaultEdge()).getBlock().dominanceFrontier() = getBasicBlock(phi) and
967+
phi.getSourceVariable() = sv
968+
|
969+
strictcount(phi.getAnInput())
970+
)
971+
)
972+
}

‎cpp/ql/lib/semmle/code/cpp/ir/dataflow/internal/DataFlowUtil.qll‎

Lines changed: 16 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -525,6 +525,9 @@ class SsaPhiNode extends Node, TSsaPhiNode {
525525

526526
/** Gets a node that is used as input to this phi node. */
527527
final Node getAnInput() { result = this.getAnInput(_) }
528+
529+
/** Gets the source variable underlying this phi node. */
530+
Ssa::SourceVariable getSourceVariable() { result = phi.getSourceVariable() }
528531
}
529532

530533
/**
@@ -1202,10 +1205,20 @@ class ParameterNode extends Node {
12021205
predicate isParameterOf(Function f, ParameterPosition pos) { none() } // overridden by subclasses
12031206
}
12041207

1205-
/** An explicit positional parameter, not including `this` or `...`. */
1206-
private class ExplicitParameterNode extends ParameterNode, InstructionNode {
1208+
/** An explicit positional parameter, including `this`, but not `...`. */
1209+
class DirectParameterNode extends InstructionNode {
12071210
override InitializeParameterInstruction instr;
12081211

1212+
/**
1213+
* INTERNAL: Do not use.
1214+
*
1215+
* Gets the `IRVariable` that this parameter references.
1216+
*/
1217+
IRVariable getIRVariable() { result = instr.getIRVariable() }
1218+
}
1219+
1220+
/** An explicit positional parameter, not including `this` or `...`. */
1221+
private class ExplicitParameterNode extends ParameterNode, DirectParameterNode {
12091222
ExplicitParameterNode() { exists(instr.getParameter()) }
12101223

12111224
override predicate isParameterOf(Function f, ParameterPosition pos) {
@@ -1219,9 +1232,7 @@ private class ExplicitParameterNode extends ParameterNode, InstructionNode {
12191232
}
12201233

12211234
/** An implicit `this` parameter. */
1222-
class ThisParameterNode extends ParameterNode, InstructionNode {
1223-
override InitializeParameterInstruction instr;
1224-
1235+
class ThisParameterNode extends ParameterNode, DirectParameterNode {
12251236
ThisParameterNode() { instr.getIRVariable() instanceof IRThisVariable }
12261237

12271238
override predicate isParameterOf(Function f, ParameterPosition pos) {
@@ -1774,20 +1785,6 @@ class ContentSet instanceof Content {
17741785
}
17751786
}
17761787

1777-
private IRBlock getBasicBlock(Node node) {
1778-
node.asInstruction().getBlock() = result
1779-
or
1780-
node.asOperand().getUse().getBlock() = result
1781-
or
1782-
node.(SsaPhiNode).getPhiNode().getBasicBlock() = result
1783-
or
1784-
node.(RawIndirectOperand).getOperand().getUse().getBlock() = result
1785-
or
1786-
node.(RawIndirectInstruction).getInstruction().getBlock() = result
1787-
or
1788-
result = getBasicBlock(node.(PostUpdateNode).getPreUpdateNode())
1789-
}
1790-
17911788
/**
17921789
* Holds if the guard `g` validates the expression `e` upon evaluating to `branch`.
17931790
*

0 commit comments

Comments
 (0)