Module ASTValueNumbering

Provides an implementation of Global Value Numbering. See https://en.wikipedia.org/wiki/Global_value_numbering

The predicate globalValueNumber converts an expression into a GVN, which is an abstract type representing the value of the expression. If two expressions have the same GVN then they compute the same value. For example:

void f(int x, int y) {
  g(x+y, x+y);
}

In this example, both arguments in the call to g compute the same value, so both arguments have the same GVN. In other words, we can find this call with the following query:

from FunctionCall call, GVN v
where v = globalValueNumber(call.getArgument(0))
  and v = globalValueNumber(call.getArgument(1))
select call

The analysis is conservative, so two expressions might have different GVNs even though the actually always compute the same value. The most common reason for this is that the analysis cannot prove that there are no side-effects that might cause the computed value to change.

Import path

import semmle.code.cpp.ir.internal.ASTValueNumbering

Imports

cpp	Provides classes and predicates for working with C/C++ code.

Predicates

globalValueNumber

Gets the global value number of expression e.

Classes

GVN

A Global Value Number. A GVN is an abstract representation of the value computed by an expression. The relationship between Expr and GVN is many-to-one: every Expr has exactly one GVN, but multiple expressions can have the same GVN. If two expressions have the same GVN, it means that they compute the same value at run time. The GVN is an opaque value, so you cannot deduce what the run-time value of an expression will be from its GVN. The only use for the GVN of an expression is to find other expressions that compute the same value. Use the predicate globalValueNumber to get the GVN for an Expr.