Compare commits

...

2 Commits

Author SHA1 Message Date
Chris Smowton
0ced36a482 Push flowThroughIntoCall into revFlowIsReturned 2025-01-10 19:23:42 +00:00
Chris Smowton
547dc22a6c Simplify revFlowThrough
Observations:
* revFlowThrough can be much larger than the other reverse-flow predicates, presumably when there are many different innerReturnAps.
* It is only ever used in conjunction with flowThroughIntoCall, which can therefore be pushed in, and several of its parameters can thereby be dropped in exchange for exposing `arg`.
* `revFlowThroughArg` can then be trivially inlined.

Result: on repository `go-gitea/gitea` with PR https://github.com/github/codeql/pull/17701 producing a wider selection of access paths than are seen on `main`, `revFlowThrough` drops in size from ~120m tuples to ~4m, and the runtime of the reverse-flow computation for dataflow stage 4 goes from dominating the forward-flow cost to relatively insignificant. Overall runtime falls from 3 minutes to 2 with substantial ram available, and presumably falls much more under GHA-style memory pressure.
2024-12-20 19:20:23 +00:00

View File

@@ -2261,10 +2261,7 @@ module MakeImpl<LocationSig Location, InputSig<Location> Lang> {
returnAp = apNone()
or
// flow through a callable
exists(DataFlowCall call, ParamNodeEx p, Ap innerReturnAp |
revFlowThrough(call, returnCtx, p, state, _, returnAp, ap, innerReturnAp) and
flowThroughIntoCall(call, node, p, ap, innerReturnAp)
)
revFlowThrough(_, returnCtx, state, returnAp, ap, node)
or
// flow out of a callable
exists(ReturnPosition pos |
@@ -2413,11 +2410,13 @@ module MakeImpl<LocationSig Location, InputSig<Location> Lang> {
pragma[nomagic]
private predicate revFlowThrough(
DataFlowCall call, ReturnCtx returnCtx, ParamNodeEx p, FlowState state,
ReturnPosition pos, ApOption returnAp, Ap ap, Ap innerReturnAp
DataFlowCall call, ReturnCtx returnCtx, FlowState state, ApOption returnAp, Ap ap,
ArgNodeEx arg
) {
revFlowParamToReturn(p, state, pos, innerReturnAp, ap) and
revFlowIsReturned(call, returnCtx, returnAp, pos, innerReturnAp)
exists(ParamNodeEx p, ReturnPosition pos, Ap innerReturnAp |
revFlowParamToReturn(p, state, pos, innerReturnAp, ap) and
revFlowIsReturned(call, returnCtx, returnAp, pos, innerReturnAp, arg, p, ap)
)
}
/**
@@ -2427,13 +2426,14 @@ module MakeImpl<LocationSig Location, InputSig<Location> Lang> {
*/
pragma[nomagic]
private predicate revFlowIsReturned(
DataFlowCall call, ReturnCtx returnCtx, ApOption returnAp, ReturnPosition pos, Ap ap
DataFlowCall call, ReturnCtx returnCtx, ApOption returnAp, ReturnPosition pos, Ap ap, ArgNodeEx arg, ParamNodeEx p, Ap argAp
) {
exists(RetNodeEx ret, FlowState state, CcCall ccc |
revFlowOut(call, ret, pos, state, returnCtx, _, returnAp, ap) and
returnFlowsThrough(ret, pos, state, ccc, _, _, _, _, ap) and
returnFlowsThrough(ret, pos, state, ccc, p, _, argAp, _, ap) and
matchesCall(ccc, call)
)
) and
flowThroughIntoCall(call, arg, p, argAp, ap)
}
pragma[nomagic]
@@ -2543,22 +2543,11 @@ module MakeImpl<LocationSig Location, InputSig<Location> Lang> {
)
}
pragma[nomagic]
private predicate revFlowThroughArg(
DataFlowCall call, ArgNodeEx arg, FlowState state, ReturnCtx returnCtx, ApOption returnAp,
Ap ap
) {
exists(ParamNodeEx p, Ap innerReturnAp |
revFlowThrough(call, returnCtx, p, state, _, returnAp, ap, innerReturnAp) and
flowThroughIntoCall(call, arg, p, ap, innerReturnAp)
)
}
pragma[nomagic]
predicate callMayFlowThroughRev(DataFlowCall call) {
exists(ArgNodeEx arg, FlowState state, ReturnCtx returnCtx, ApOption returnAp, Ap ap |
revFlow(arg, state, returnCtx, returnAp, ap) and
revFlowThroughArg(call, arg, state, returnCtx, returnAp, ap)
revFlowThrough(call, returnCtx, state, returnAp, ap, arg)
)
}