C++: Implement 'getAdditionalFlowIntoCallNodeTerm'.

github · MathiasVP · Mar 8, 2023 · Mar 7, 2023 · Mar 8, 2023 · Mar 7, 2023
commit 0d1e061f5a1c42b1e63766515ddb61e8d064fa1e
diff --git a/cpp/ql/lib/semmle/code/cpp/ir/dataflow/internal/DataFlowPrivate.qll b/cpp/ql/lib/semmle/code/cpp/ir/dataflow/internal/DataFlowPrivate.qll
@@ -5,6 +5,8 @@ private import DataFlowDispatch
 private import DataFlowImplConsistency
 private import semmle.code.cpp.ir.internal.IRCppLanguage
 private import SsaInternals as Ssa
+private import DataFlowImplCommon
+private import semmle.code.cpp.ir.ValueNumbering

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

+/**
+ * Gets the basic block of `node`.
+ */
+IRBlock getBasicBlock(Node node) {
+  node.asInstruction().getBlock() = result
+  or
+  node.asOperand().getUse().getBlock() = result
+  or
+  node.(SsaPhiNode).getPhiNode().getBasicBlock() = result
+  or
+  node.(RawIndirectOperand).getOperand().getUse().getBlock() = result
+  or
+  node.(RawIndirectInstruction).getInstruction().getBlock() = result
+  or
+  result = getBasicBlock(node.(PostUpdateNode).getPreUpdateNode())
+}
+
 /**
 * Gets an additional term that is added to the `join` and `branch` computations to reflect
 * an additional forward or backwards branching factor that is not taken into account
 * when calculating the (virtual) dispatch cost.
 *
 * Argument `arg` is part of a path from a source to a sink, and `p` is the target parameter.
 */
-int getAdditionalFlowIntoCallNodeTerm(ArgumentNode arg, ParameterNode p) { none() }
+pragma[nomagic]
+int getAdditionalFlowIntoCallNodeTerm(ArgumentNode arg, ParameterNode p) {
+  exists(ParameterNode switchee, ConditionOperand op, DataFlowCall call |
+    viableParamArg(call, p, arg) and
+    viableParamArg(call, switchee, _) and
+    valueNumber(switchee.asInstruction()).getAUse() = op and
+    result = countNumberOfBranchesUsingParameter(op, p)
+  )
+}
+
+/** Gets the `IRVariable` associated with the parameter node `p`. */
+pragma[nomagic]
+private IRVariable getIRVariableForParameterNode(ParameterNode p) {
+  result = p.(DirectParameterNode).getIRVariable()
+  or
+  result.getAst() = p.(IndirectParameterNode).getParameter()
+}
+
+/** Holds if `v` is the source variable corresponding to the parameter represented by `p`. */
+pragma[nomagic]
+private predicate parameterNodeHasSourceVariable(ParameterNode p, Ssa::SourceIRVariable v) {
+  v.getIRVariable() = getIRVariableForParameterNode(p) and
+  exists(Position pos | p.isParameterOf(_, pos) |
+    pos instanceof DirectPosition and
+    v.getIndirection() = 1
+    or
+    pos.(IndirectionPosition).getIndirectionIndex() + 1 = v.getIndirection()
+  )
+}
+
+private EdgeKind caseOrDefaultEdge() {
+  result instanceof CaseEdge or
+  result instanceof DefaultEdge
+}
+
+/**
+ * Gets the number of switch branches that that read from (or write to) the parameter `p`.
+ */
+int countNumberOfBranchesUsingParameter(ConditionOperand op, ParameterNode p) {
+  exists(SwitchInstruction switch, Ssa::SourceVariable sv |
+    switch.getExpressionOperand() = op and
+    parameterNodeHasSourceVariable(p, sv) and
+    // Count the number of cases that use the parameter. We do this by finding the phi node
+    // that merges the uses/defs of the parameter. There might be multiple such phi nodes, so
+    // we pick the one with the highest edge count.
+    result =
+      max(SsaPhiNode phi |
+        switch.getSuccessor(caseOrDefaultEdge()).getBlock().dominanceFrontier() = getBasicBlock(phi) and
+        phi.getSourceVariable() = sv
+      |
+        strictcount(phi.getAnInput())
+      )
+  )
+}
diff --git a/cpp/ql/lib/semmle/code/cpp/ir/dataflow/internal/DataFlowUtil.qll b/cpp/ql/lib/semmle/code/cpp/ir/dataflow/internal/DataFlowUtil.qll
@@ -525,6 +525,9 @@ class SsaPhiNode extends Node, TSsaPhiNode {

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

 /**
@@ -1201,10 +1204,20 @@ class ParameterNode extends Node {
  predicate isParameterOf(Function f, ParameterPosition pos) { none() } // overridden by subclasses
 }

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

+  /**
+   * INTERNAL: Do not use.
+   *
+   * Gets the `IRVariable` that this parameter references.
+   */
+  IRVariable getIRVariable() { result = instr.getIRVariable() }
+}
+
+/** An explicit positional parameter, not including `this` or `...`. */
+private class ExplicitParameterNode extends ParameterNode, DirectParameterNode {
  ExplicitParameterNode() { exists(instr.getParameter()) }

  override predicate isParameterOf(Function f, ParameterPosition pos) {
@@ -1218,9 +1231,7 @@ private class ExplicitParameterNode extends ParameterNode, InstructionNode {
 }

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

  override predicate isParameterOf(Function f, ParameterPosition pos) {
@@ -1773,20 +1784,6 @@ class ContentSet instanceof Content {
  }
 }

-private IRBlock getBasicBlock(Node node) {
-  node.asInstruction().getBlock() = result
-  or
-  node.asOperand().getUse().getBlock() = result
-  or
-  node.(SsaPhiNode).getPhiNode().getBasicBlock() = result
-  or
-  node.(RawIndirectOperand).getOperand().getUse().getBlock() = result
-  or
-  node.(RawIndirectInstruction).getInstruction().getBlock() = result
-  or
-  result = getBasicBlock(node.(PostUpdateNode).getPreUpdateNode())
-}
-
 /**
 * Holds if the guard `g` validates the expression `e` upon evaluating to `branch`.
 *