Compare commits

...

3 Commits

Author SHA1 Message Date
Chris Smowton
75881ace7e Fix 2025-01-15 18:02:24 +00:00
Chris Smowton
b83e35c3ad Filter revFlowParamToReturn using flowThroughIntoCall 2025-01-10 18:49:50 +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 |
@@ -2408,16 +2405,20 @@ module MakeImpl<LocationSig Location, InputSig<Location> Lang> {
revFlow(pragma[only_bind_into](p), state, TReturnCtxMaybeFlowThrough(pos),
apSome(returnAp), pragma[only_bind_into](ap)) and
parameterFlowThroughAllowed(p, pos.getKind()) and
PrevStage::parameterMayFlowThrough(p, isNil(ap))
PrevStage::parameterMayFlowThrough(p, isNil(ap)) and
flowThroughIntoCall(_, _, p, ap, returnAp)
}
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 |
flowThroughIntoCall(call, arg, p, ap, innerReturnAp) and
revFlowParamToReturn(p, state, pos, innerReturnAp, ap) and
revFlowIsReturned(call, returnCtx, returnAp, pos, innerReturnAp)
)
}
/**
@@ -2543,22 +2544,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)
)
}