How to accelerate QL compilation?

[whj0401]

I am currently using CodeQL to detect some specific code patterns, and I suffer from large overhead for compiling QL code.
The following is a modified AllocMultiplicationOverflow.ql
As noted in the code, 4 lines that check the target variables result in extremely slow compilation.
It takes about 30s to compile the QL code without those 4 lines, but it takes over 6 minutes to compile the QL code with those 4 lines.
The query merely costs about 30s.

import cpp
import semmle.code.cpp.models.interfaces.Allocation
import semmle.code.cpp.ir.dataflow.DataFlow
import MultToAlloc::PathGraph

import MultToAlloc::PathGraph
module MultToAllocConfig implements DataFlow::ConfigSig {
  predicate isSource(DataFlow::Node node) {
    // a multiplication of two non-constant expressions
    exists(MulExpr me |
      me = node.asExpr() and
      forall(Expr e | e = me.getAnOperand() | not exists(e.getValue()))
    )
  }

  predicate isSink(DataFlow::Node node) {
    // something that affects an allocation size
    node.asExpr() = any(HeuristicAllocationExpr ae).getSizeExpr().getAChild*()
  }
}

module MultToAlloc = DataFlow::Global<MultToAllocConfig>;

// pragma[noinline]
// language[monotonicAggregates]
predicate isTheTargetRelation(AssignExpr expr_2425435, LogicalAndExpr expr_2425477, AssignExpr expr_2425495, IfStmt stmt_2425438, Expr source, Expr sink) {
  postDominates(expr_2425477, source) and
  dominates(expr_2425477, expr_2425495) and
  postDominates(stmt_2425438, expr_2425435) and
  postDominates(stmt_2425438, source) and
  stmt_2425438.getCondition() = expr_2425477.getParentWithConversions*() and
  dominates(expr_2425435, expr_2425477) and
  dominates(expr_2425435, expr_2425495) and
  dominates(expr_2425435, stmt_2425438) and
  postDominates(expr_2425477, expr_2425435) and
  // The following lines cause extremely slow compilation
  // ================ The 4 lines =======================
  expr_2425435.getLValue().(VariableAccess).getTarget() = expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getRightOperand().(DivExpr).getLeftOperand().(VariableAccess).getTarget() and
  expr_2425435.getLValue().(VariableAccess).getTarget() = expr_2425495.getLValue().(VariableAccess).getTarget() and
  expr_2425435.getRValue().(MulExpr).getLeftOperand().(VariableAccess).getTarget() = expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getLeftOperand().(VariableAccess).getTarget() and
  expr_2425435.getRValue().(MulExpr).getRightOperand().(VariableAccess).getTarget() = expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getRightOperand().(DivExpr).getRightOperand().(VariableAccess).getTarget()
}

from MultToAlloc::PathNode n_source, Expr source, MultToAlloc::PathNode n_sink, Expr sink,
  AssignExpr expr_2425435, LogicalAndExpr expr_2425477, AssignExpr expr_2425495, IfStmt stmt_2425438
where
MultToAlloc::flowPath(n_source, n_sink) and source = n_source.getNode().asExpr() and sink = n_sink.getNode().asExpr()
 and
  isTheTargetRelation(expr_2425435, expr_2425477, expr_2425495, stmt_2425438, source, sink)
select sink, source, sink,
  "Potentially overflowing value from $@ is used in the size of this allocation.", source,
  "multiplication"

Basing on this page, https://codeql.github.com/docs/ql-language-reference/annotations/
I tried to improve the efficiency but failed...

noopt seems to be a suitable choice. I tried to group the 4 lines into a new predicate with noopt. However, I met the following errors

ERROR: The inferred type for 'expr_2425435' is @assign_expr, which is not contained within its declared type @assignexpr (...)
ERROR: The inferred type for 'expr_2425495' is @assign_expr, which is not contained within its declared type @assignexpr (...)
ERROR: The inferred type for 'a' is Access::Access, which is not contained within its declared type Access::VariableAccess (...)
...

It seems noopt does not work nowadays.

Why the compilation process for those 4 lines can be so slow? Is there any guidance? How to solve the problem?
I am looking forward to any suggestions. Thanks.

[jketema]

Hi @whj0401 ,

Which version of CodeQL are you running? The query with the 4 lines compiles within seconds for me with the latest version. I do see the noopt problem, but it's different from the one you report.

[whj0401]

Thanks for your reply. I tested the QL code with v2.15.3 and v2.17.0.
Sorry for the confusion; I removed some lines in the previously posted code.

I just tried the code again with v2.17.0, with -j 32

• The following full code takes around 3 minutes to compile
• When I removed the 4 lines, it costs 48 seconds
• When I additionally removed the "previously removed code", it takes 12 seconds to compile.
• When I removed the "previous removed code", but kept the 4 lines, it takes 20 seconds to compile.

The combination effect results in the slow compilation.

When tested with v2.15.3 with -j 1:

• The full code takes 403 seconds to finish the compilation,
• Removing the 4 lines costs about 50 seconds.

The server with codeql-v2.15.3 is also used by others, so only one thread is used.

Still, my question is how to accelerate the compilation process.
The predicate isTheTargetRelation is an extra constraint, it is expected to be executed after all other code, and the efficiency of this predicate is really not essential.

Thank you in advance.

import cpp
import semmle.code.cpp.models.interfaces.Allocation
import semmle.code.cpp.ir.dataflow.DataFlow
import MultToAlloc::PathGraph


module MultToAllocConfig implements DataFlow::ConfigSig {
  predicate isSource(DataFlow::Node node) {
    // a multiplication of two non-constant expressions
    exists(MulExpr me |
      me = node.asExpr() and
      forall(Expr e | e = me.getAnOperand() | not exists(e.getValue()))
    )
  }

  predicate isSink(DataFlow::Node node) {
    // something that affects an allocation size
    node.asExpr() = any(HeuristicAllocationExpr ae).getSizeExpr().getAChild*()
  }
}

module MultToAlloc = DataFlow::Global<MultToAllocConfig>;

// pragma[noinline]
// language[monotonicAggregates]
predicate isTheTargetRelation(AssignExpr expr_2425435, LogicalAndExpr expr_2425477, AssignExpr expr_2425495, IfStmt stmt_2425438, Expr source, Expr sink) {
  postDominates(expr_2425477, source) and
  dominates(expr_2425477, expr_2425495) and
  postDominates(stmt_2425438, expr_2425435) and
  postDominates(stmt_2425438, source) and
  stmt_2425438.getCondition() = expr_2425477.getParentWithConversions*() and
  dominates(expr_2425435, expr_2425477) and
  dominates(expr_2425435, expr_2425495) and
  dominates(expr_2425435, stmt_2425438) and
  postDominates(expr_2425477, expr_2425435) and
  // ================= previously removed code ====================
  expr_2425435 = source.getParentWithConversions*() and
  expr_2425435.getUnderlyingType().hasName("unsigned long") and
  expr_2425435 instanceof AssignExpr and
  expr_2425435.getRValue().getConversion*().getUnderlyingType().hasName("unsigned long") and
  expr_2425435.getRValue().getConversion*().getUnderlyingType().hasName("unsigned long") and
  expr_2425435.getRValue() instanceof MulExpr and
  expr_2425435.getRValue().(MulExpr).getLeftOperand().getConversion*().getUnderlyingType().hasName("unsigned long") and
  expr_2425435.getRValue().(MulExpr).getRightOperand().getConversion*().getUnderlyingType().hasName("unsigned long") and
  expr_2425477.getUnderlyingType().hasName("int") and
  expr_2425477 instanceof LogicalAndExpr and
  expr_2425477.(LogicalAndExpr).getLeftOperand().getConversion*().getUnderlyingType().hasName("int") and
  expr_2425477.(LogicalAndExpr).getRightOperand().getConversion*().getUnderlyingType().hasName("int") and
  expr_2425477.(LogicalAndExpr).getRightOperand().getConversion*().getUnderlyingType().hasName("int") and
  expr_2425477.(LogicalAndExpr).getRightOperand().getUnderlyingType().hasName("int") and
  expr_2425477.(LogicalAndExpr).getRightOperand() instanceof NEExpr and
  expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getLeftOperand().getConversion*().getUnderlyingType().hasName("unsigned long") and
  expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getRightOperand().getConversion*().getUnderlyingType().hasName("unsigned long") and
  expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getRightOperand().getConversion*().getUnderlyingType().hasName("unsigned long") and
  expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getRightOperand() instanceof DivExpr and
  expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getRightOperand().(DivExpr).getLeftOperand().getConversion*().getUnderlyingType().hasName("unsigned long") and
  expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getRightOperand().(DivExpr).getRightOperand().getConversion*().getUnderlyingType().hasName("unsigned long") and
  expr_2425495.getUnderlyingType().hasName("unsigned long") and
  expr_2425495 instanceof AssignExpr and
  expr_2425495.getRValue().getConversion*().getUnderlyingType().hasName("unsigned long") and
  expr_2425495.getRValue().getValue().toString() = "0" and
  // ================= The 4 lines =========================
  expr_2425435.getLValue().(VariableAccess).getTarget() = expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getRightOperand().(DivExpr).getLeftOperand().(VariableAccess).getTarget() and
  expr_2425435.getLValue().(VariableAccess).getTarget() = expr_2425495.getLValue().(VariableAccess).getTarget() and
  expr_2425435.getRValue().(MulExpr).getLeftOperand().(VariableAccess).getTarget() = expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getLeftOperand().(VariableAccess).getTarget() and
  expr_2425435.getRValue().(MulExpr).getRightOperand().(VariableAccess).getTarget() = expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getRightOperand().(DivExpr).getRightOperand().(VariableAccess).getTarget()
}

from MultToAlloc::PathNode n_source, Expr source, MultToAlloc::PathNode n_sink, Expr sink,
  AssignExpr expr_2425435, LogicalAndExpr expr_2425477, AssignExpr expr_2425495, IfStmt stmt_2425438
where
MultToAlloc::flowPath(n_source, n_sink) and source = n_source.getNode().asExpr() and sink = n_sink.getNode().asExpr()
 and
  isTheTargetRelation(expr_2425435, expr_2425477, expr_2425495, stmt_2425438, source, sink)
select sink, source, sink,
  "Potentially overflowing value from $@ is used in the size of this allocation.", source,
  "multiplication"

[jketema]

Thanks I can reproduce the problem now.

[jketema]

Instead of having everything in one predicate, split the predicate in a number of different predicates that make logical sense. That is likely to improve both compilation performance and evaluation performance.

[whj0401]

Thanks for your suggestion, I just tried to separate the large predicate into pieces and the compilation is much faster with bindingset and pragma[inline_late]. However, running query stuck.

Using pragma[noinline] can also compile the QL fast, but it will run my added predicates before getting sink and source, resulting in an extremely slow query.

The following is the QL code and running output.
Sincerely thank you again. Is there any other suggestions?

The follow code was tested with v2.17.0

import cpp
import semmle.code.cpp.models.interfaces.Allocation
import semmle.code.cpp.ir.dataflow.DataFlow
import MultToAlloc::PathGraph


module MultToAllocConfig implements DataFlow::ConfigSig {
  predicate isSource(DataFlow::Node node) {
    // a multiplication of two non-constant expressions
    exists(MulExpr me |
      me = node.asExpr() and
      forall(Expr e | e = me.getAnOperand() | not exists(e.getValue()))
    )
  }

  predicate isSink(DataFlow::Node node) {
    // something that affects an allocation size
    node.asExpr() = any(HeuristicAllocationExpr ae).getSizeExpr().getAChild*()
  }
}

module MultToAlloc = DataFlow::Global<MultToAllocConfig>;

// pragma[noinline]
bindingset[expr_2425435, expr_2425477, expr_2425495, stmt_2425438, source, sink]
pragma[inline_late]
predicate isTheTargetRelation_1(AssignExpr expr_2425435, LogicalAndExpr expr_2425477, AssignExpr expr_2425495, IfStmt stmt_2425438, Expr source, Expr sink) {
  postDominates(expr_2425477, source) and
  dominates(expr_2425477, expr_2425495) and
  postDominates(stmt_2425438, expr_2425435) and
  postDominates(stmt_2425438, source) and
  stmt_2425438.getCondition() = expr_2425477.getParentWithConversions*() and
  dominates(expr_2425435, expr_2425477) and
  dominates(expr_2425435, expr_2425495) and
  dominates(expr_2425435, stmt_2425438) and
  postDominates(expr_2425477, expr_2425435)
}

bindingset[expr_2425435, source, sink]
pragma[inline_late]
predicate isTheTargetRelation_2(AssignExpr expr_2425435, Expr source, Expr sink) {
  expr_2425435 = source.getParentWithConversions*() and
  expr_2425435.getUnderlyingType().hasName("unsigned long") and
  expr_2425435 instanceof AssignExpr and
  expr_2425435.getRValue().getConversion*().getUnderlyingType().hasName("unsigned long") and
  expr_2425435.getRValue().getConversion*().getUnderlyingType().hasName("unsigned long") and
  expr_2425435.getRValue().getConversion*() instanceof MulExpr and
  expr_2425435.getRValue().(MulExpr).getLeftOperand().getConversion*().getUnderlyingType().hasName("unsigned long") and
  expr_2425435.getRValue().(MulExpr).getRightOperand().getConversion*().getUnderlyingType().hasName("unsigned long")
}


bindingset[expr_2425477, source, sink]
pragma[inline_late]
predicate isTheTargetRelation_3(LogicalAndExpr expr_2425477, Expr source, Expr sink) {
  expr_2425477.getUnderlyingType().hasName("int") and
  expr_2425477 instanceof LogicalAndExpr and
  expr_2425477.(LogicalAndExpr).getLeftOperand().getConversion*().getUnderlyingType().hasName("int") and
  expr_2425477.(LogicalAndExpr).getRightOperand().getConversion*().getUnderlyingType().hasName("int") and
  expr_2425477.(LogicalAndExpr).getRightOperand().getConversion*().getUnderlyingType().hasName("int") and
  expr_2425477.(LogicalAndExpr).getRightOperand().getUnderlyingType().hasName("int") and
  expr_2425477.(LogicalAndExpr).getRightOperand() instanceof NEExpr and
  expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getLeftOperand().getConversion*().getUnderlyingType().hasName("unsigned long") and
  expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getRightOperand().getConversion*().getUnderlyingType().hasName("unsigned long") and
  expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getRightOperand().getConversion*().getUnderlyingType().hasName("unsigned long") and
  expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getRightOperand() instanceof DivExpr and
  expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getRightOperand().(DivExpr).getLeftOperand().getConversion*().getUnderlyingType().hasName("unsigned long") and
  expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getRightOperand().(DivExpr).getRightOperand().getConversion*().getUnderlyingType().hasName("unsigned long")
}


bindingset[expr_2425495, source, sink]
pragma[inline_late]
predicate isTheTargetRelation_4(AssignExpr expr_2425495, Expr source, Expr sink) {
  expr_2425495.getUnderlyingType().hasName("unsigned long") and
  expr_2425495 instanceof AssignExpr and
  expr_2425495.getRValue().getConversion*().getUnderlyingType().hasName("unsigned long") and
  expr_2425495.getRValue().getValue().toString() = "0"
}


// pragma[noinline]
// language[monotonicAggregates]
// pragma[noinline]
bindingset[expr_2425435, expr_2425477, expr_2425495, source, sink]
pragma[inline_late]
predicate isTheTargetRelation_5(AssignExpr expr_2425435, LogicalAndExpr expr_2425477, AssignExpr expr_2425495, Expr source, Expr sink) {
  expr_2425435.getLValue().(VariableAccess).getTarget() = expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getRightOperand().(DivExpr).getLeftOperand().(VariableAccess).getTarget() and
  expr_2425435.getLValue().(VariableAccess).getTarget() = expr_2425495.getLValue().(VariableAccess).getTarget() and
  expr_2425435.getRValue().(MulExpr).getLeftOperand().(VariableAccess).getTarget() = expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getLeftOperand().(VariableAccess).getTarget() and
  expr_2425435.getRValue().(MulExpr).getRightOperand().(VariableAccess).getTarget() = expr_2425477.(LogicalAndExpr).getRightOperand().(NEExpr).getRightOperand().(DivExpr).getRightOperand().(VariableAccess).getTarget()
}


from MultToAlloc::PathNode n_source, Expr source, MultToAlloc::PathNode n_sink, Expr sink,
  AssignExpr expr_2425435, LogicalAndExpr expr_2425477, AssignExpr expr_2425495, IfStmt stmt_2425438
where
MultToAlloc::flowPath(n_source, n_sink) and source = n_source.getNode().asExpr() and sink = n_sink.getNode().asExpr()
 and
  isTheTargetRelation_1(expr_2425435, expr_2425477, expr_2425495, stmt_2425438, source, sink) and
  isTheTargetRelation_2(expr_2425435, source, sink) and
  isTheTargetRelation_3(expr_2425477, source, sink) and
  isTheTargetRelation_4(expr_2425495, source, sink) and
  isTheTargetRelation_5(expr_2425435, expr_2425477, expr_2425495, source, sink)
select sink, source, sink,
  "Potentially overflowing value from $@ is used in the size of this allocation.", source,
  "multiplication"

Output message
The last line is where the query stuck. I have to press Crtl+C.

codeql query run -j 1 test_5.ql -d <path/to/db> -o test_5.bqrs
Compiling query plan for test_5.ql.
WARNING: test is always true, as AssignExpr is a supertype of the expression type Assignment::AssignExpr. (./test_5.ql:46,27-37)
WARNING: test is always true, as the expression already has type Assignment::AssignExpr. (./test_5.ql:46,27-37)
WARNING: test is always true, as LogicalAndExpr is a supertype of the expression type LogicalOperation::LogicalAndExpr. (./test_5.ql:59,27-41)
WARNING: test is always true, as the expression already has type LogicalOperation::LogicalAndExpr. (./test_5.ql:59,27-41)
WARNING: test is always true, as AssignExpr is a supertype of the expression type Assignment::AssignExpr. (./test_5.ql:78,27-37)
WARNING: test is always true, as the expression already has type Assignment::AssignExpr. (./test_5.ql:78,27-37)
WARNING: Unused variable sink (./test_5.ql:28,151-155)
WARNING: Unused variable sink (./test_5.ql:43,76-80)
WARNING: Unused variable source (./test_5.ql:57,67-73)
WARNING: Unused variable sink (./test_5.ql:57,80-84)
WARNING: Unused variable source (./test_5.ql:76,63-69)
WARNING: Unused variable sink (./test_5.ql:76,76-80)
WARNING: Unused variable source (./test_5.ql:89,117-123)
WARNING: Unused variable sink (./test_5.ql:89,130-134)
[1/1 comp 19.3s] Compiled ./test_5.ql.
test_5.ql: let1            

[jketema]

It's not clear to me why you use bindingset and pragma[inline_late]. All the unused arguments are best omitted, and expr_2425435 = source.getParentWithConversions*() should probably not occur in the predicate it's currently appearing in.

[whj0401]

Thanks for your note. It really seems bindingset and pragma[inline_late] can be omitted in this case. Separating the whole predicate into pieces really help.

I added bindingset and pragma[inline_late] since I hope to force the predicates to be executed after those variables are prepared. I first tried bindingset only, and it takes about 4 minutes to finish the compilation.
You are right. I guess I should remove the added annotations, and the compilation can be finished in a minute.

Thank you again.