C++/C#: Sync identical files.

This leverages the existing alias analysis to identify functions which
have no reads or writes of the AllAliasedMemory virtual variable, and
therefore have no global side effects. A recursion over the call graph
identifies functions which have no indirect global side effects, and
calls to those functions have their global side effect instructions
removed.

cpp/ql/lib/change-notes/2022-08-01-gvn-functions.md

@@ -0,0 +1,4 @@
+---
+category: minorAnalysis
+---
+* Multiple function calls made in the same function may now receive the same global value number when the analysis can show they produce the same results.

cpp/ql/lib/semmle/code/cpp/ir/implementation/aliased_ssa/Instruction.qll

@@ -1712,6 +1712,11 @@ class SideEffectInstruction extends Instruction {
  */
 class CallSideEffectInstruction extends SideEffectInstruction {
   CallSideEffectInstruction() { this.getOpcode() instanceof Opcode::CallSideEffect }
+
+  /** Gets the operand for the value that will be read by this instruction */
+  final SideEffectOperand getSideEffectOperand() { result = this.getAnOperand() }
+
+  final Instruction getSideEffect() { result = this.getAnOperand().getDef() }
 }
 
 /**
@@ -1723,6 +1728,11 @@ class CallSideEffectInstruction extends SideEffectInstruction {
  */
 class CallReadSideEffectInstruction extends SideEffectInstruction {
   CallReadSideEffectInstruction() { this.getOpcode() instanceof Opcode::CallReadSideEffect }
+
+  /** Gets the operand for the value that will be read by this instruction */
+  final SideEffectOperand getSideEffectOperand() { result = this.getAnOperand() }
+
+  final Instruction getSideEffect() { result = this.getAnOperand().getDef() }
 }
 
 /**

cpp/ql/lib/semmle/code/cpp/ir/implementation/aliased_ssa/gvn/internal/ValueNumberingImports.qll

@@ -1,3 +1,4 @@
 import semmle.code.cpp.ir.implementation.aliased_ssa.IR
 import semmle.code.cpp.ir.internal.Overlap
 import semmle.code.cpp.ir.internal.IRCppLanguage as Language
+import semmle.code.cpp.models.interfaces.SideEffect as SideEffect

cpp/ql/lib/semmle/code/cpp/ir/implementation/aliased_ssa/gvn/internal/ValueNumberingInternal.qll

@@ -41,8 +41,92 @@ newtype TValueNumber =
   ) {
     loadTotalOverlapValueNumber(_, irFunc, type, memOperand, operand)
   } or
+  TCallValueNumber(TCallPartialValueNumber vn) { callValueNumber(_, _, vn) } or
   TUniqueValueNumber(IRFunction irFunc, Instruction instr) { uniqueValueNumber(instr, irFunc) }
 
+private class NumberableCallInstruction extends CallInstruction {
+  NumberableCallInstruction() {
+    not this.getResultIRType() instanceof IRVoidType and
+    exists(SideEffect::SideEffectFunction sideEffectFunc |
+      sideEffectFunc = this.getStaticCallTarget()
+    |
+      sideEffectFunc.hasOnlySpecificReadSideEffects() and
+      sideEffectFunc.hasOnlySpecificWriteSideEffects()
+    )
+  }
+}
+
+private newtype TCallPartialValueNumber =
+  TNilArgument() or
+  TArgument(TCallPartialValueNumber head, TValueNumber arg) {
+    exists(NumberableCallInstruction call, int index |
+      callArgValueNumber(call, index, arg) and
+      callPartialValueNumber(call, index, head)
+    )
+  }
+
+private predicate callValueNumber(
+  NumberableCallInstruction call, int index, TCallPartialValueNumber vn
+) {
+  index = max(int n | callArgRank(call, n, _) | n) and
+  exists(TCallPartialValueNumber head, TValueNumber arg |
+    callPartialValueNumber(call, index, pragma[only_bind_out](head)) and
+    callArgValueNumber(call, index, pragma[only_bind_into](arg)) and
+    vn = TArgument(head, arg)
+  )
+  or
+  not exists(int n | callArgRank(call, n, _)) and
+  index = -1 and
+  vn = TNilArgument()
+}
+
+private predicate callPartialValueNumber(
+  NumberableCallInstruction call, int index, TCallPartialValueNumber head
+) {
+  exists(call) and
+  index = 1 and
+  head = TNilArgument()
+  or
+  exists(TCallPartialValueNumber prev, TValueNumber prevVN |
+    callPartialValueNumber(call, index - 1, pragma[only_bind_out](prev)) and
+    callArgValueNumber(call, index - 1, pragma[only_bind_into](prevVN)) and
+    head = TArgument(prev, prevVN)
+  )
+}
+
+/**
+ */
+private predicate callArgValueNumber(NumberableCallInstruction call, int index, TValueNumber arg) {
+  exists(Instruction instr |
+    callArgRank(call, index, instr) and
+    arg = tvalueNumber(instr)
+  )
+}
+
+/**
+ * Holds if `arg` is the `index`th element in `call`'s extended argument list, including the `this`
+ * argument and side-effect reads.
+ */
+private predicate callArgRank(NumberableCallInstruction call, int index, Instruction arg) {
+  arg =
+    rank[index](int argIndex, boolean isEffect, Instruction instr |
+      // There is no need to include the call's read and write side effects on
+      // all-aliased-memory as `NumberableCallInstruction`s do not read or write
+      // to all-aliased-memory.
+      instr = call.getArgument(argIndex) and
+      isEffect = false
+      or
+      exists(ReadSideEffectInstruction read |
+        read.getPrimaryInstruction() = call and
+        read.getSideEffectOperand().getAnyDef() = instr and
+        read.getIndex() = argIndex and
+        isEffect = true
+      )
+    |
+      instr order by argIndex, isEffect
+    )
+}
+
 /**
  * A `CopyInstruction` whose source operand's value is congruent to the definition of that source
  * operand.
@@ -93,6 +177,8 @@ private predicate numberableInstruction(Instruction instr) {
   instr instanceof CongruentCopyInstruction
   or
   instr instanceof LoadTotalOverlapInstruction
+  or
+  instr instanceof NumberableCallInstruction
 }
 
 private predicate filteredNumberableInstruction(Instruction instr) {
@@ -309,6 +395,11 @@ private TValueNumber nonUniqueValueNumber(Instruction instr) {
       or
       // The value number of a copy is just the value number of its source value.
       result = tvalueNumber(instr.(CongruentCopyInstruction).getSourceValue())
+      or
+      exists(TCallPartialValueNumber pvn |
+        callValueNumber(instr, _, pvn) and
+        result = TCallValueNumber(pvn)
+      )
     )
   )
 }

cpp/ql/lib/semmle/code/cpp/ir/implementation/aliased_ssa/internal/SSAConstruction.qll

@@ -8,11 +8,6 @@ private import Imports::RawIR as RawIR
 private import SsaInstructions
 private import SsaOperands
 private import NewIR
-
-private class OldBlock = Reachability::ReachableBlock;
-
-private class OldInstruction = Reachability::ReachableInstruction;
-
 import Cached
 
 cached
@@ -58,7 +53,9 @@ private module Cached {
 
   cached
   predicate hasInstruction(TStageInstruction instr) {
-    instr instanceof TRawInstruction and instr instanceof OldInstruction
+    instr instanceof TRawInstruction and
+    instr instanceof OldInstruction and
+    not removedInstruction(instr)
     or
     instr = phiInstruction(_, _)
     or
@@ -382,7 +379,14 @@ private module Cached {
         (
           if Reachability::isInfeasibleInstructionSuccessor(oldInstruction, kind)
           then result = unreachedInstruction(instruction.getEnclosingIRFunction())
-          else result = getNewInstruction(oldInstruction.getSuccessor(kind))
+          else
+            if removedInstruction(oldInstruction.getSuccessor(kind))
+            then
+              // the only removed nodes are side-effect writes, but those may have Chi nodes
+              // skip to the following instruction in the old IR, which won't be removed
+              // if we start skipping specific side effects, this may no longer hold
+              result = getNewInstruction(oldInstruction.getSuccessor(kind).getSuccessor(kind))
+            else result = getNewInstruction(oldInstruction.getSuccessor(kind))
         )
       )
       or

cpp/ql/lib/semmle/code/cpp/ir/implementation/aliased_ssa/internal/SSAConstructionInternal.qll

@@ -13,3 +13,15 @@ import semmle.code.cpp.ir.implementation.internal.TOperand::AliasedSsaOperands a
 
 /** DEPRECATED: Alias for SsaOperands */
 deprecated module SSAOperands = SsaOperands;
+
+private import SideEffectElimination as Elim
+
+predicate removedInstruction(Reachability::ReachableInstruction instr) {
+  Elim::removeableSideEffect(instr)
+}
+
+class OldBlock = Reachability::ReachableBlock;
+
+class OldInstruction extends Reachability::ReachableInstruction {
+  OldInstruction() { not Elim::removeableSideEffect(this) }
+}

cpp/ql/lib/semmle/code/cpp/ir/implementation/aliased_ssa/internal/SideEffectElimination.qll

@@ -0,0 +1,42 @@
+import cpp as CPP
+import semmle.code.cpp.ir.implementation.unaliased_ssa.IR as Unaliased
+import AliasAnalysis as Alias
+import AliasConfiguration as Conf
+import semmle.code.cpp.models.interfaces.SideEffect as SideEffect
+
+private predicate noLocalSideEffectWrite(CPP::Function func) {
+  forall(Unaliased::AddressOperand addr | addr.getUse().getEnclosingFunction() = func |
+    not (
+      Alias::getAddressOperandAllocation(addr) instanceof Conf::VariableAllocation and
+      Alias::getAddressOperandAllocation(addr).(Conf::VariableAllocation).alwaysEscapes()
+    )
+  )
+}
+
+language[monotonicAggregates]
+private predicate noTransitiveSideEffectWrite(CPP::Function func) {
+  exists(Unaliased::IRFunction irFunc | irFunc.getFunction() = func) and
+  noLocalSideEffectWrite(func) and
+  forall(Unaliased::CallInstruction call | call.getEnclosingFunction() = func |
+    exists(call.getStaticCallTarget())
+  ) and
+  forall(Unaliased::CallInstruction call, CPP::Function callee |
+    call.getStaticCallTarget() = callee and
+    call.getEnclosingFunction() = func
+  |
+    noTransitiveSideEffectWrite(callee)
+    or
+    callee.(SideEffect::SideEffectFunction).hasOnlySpecificWriteSideEffects()
+  )
+}
+
+predicate removeableSideEffect(Unaliased::SideEffectInstruction instr) {
+  (
+    instr instanceof Unaliased::CallSideEffectInstruction or
+    instr instanceof Unaliased::CallReadSideEffectInstruction
+  ) and
+  noTransitiveSideEffectWrite(instr
+        .getPrimaryInstruction()
+        .(Unaliased::CallInstruction)
+        .getStaticCallTarget())
+}

cpp/ql/lib/semmle/code/cpp/ir/implementation/internal/TInstruction.qll

@@ -34,6 +34,7 @@ newtype TInstruction =
     AliasedSsa::SSA::hasPhiInstruction(blockStartInstr, memoryLocation)
   } or
   TAliasedSsaChiInstruction(TRawInstruction primaryInstruction) {
+    not AliasedSsa::removedInstruction(primaryInstruction) and
     AliasedSsa::SSA::hasChiInstruction(primaryInstruction)
   } or
   TAliasedSsaUnreachedInstruction(IRFunctionBase irFunc) {

cpp/ql/lib/semmle/code/cpp/ir/implementation/internal/TInstructionInternal.qll

@@ -5,3 +5,5 @@ import semmle.code.cpp.ir.implementation.aliased_ssa.internal.SSAConstruction as
 
 /** DEPRECATED: Alias for AliasedSsa */
 deprecated module AliasedSSA = AliasedSsa;
+
+import semmle.code.cpp.ir.implementation.aliased_ssa.internal.SideEffectElimination as Elim

cpp/ql/lib/semmle/code/cpp/ir/implementation/raw/Instruction.qll

@@ -1712,6 +1712,11 @@ class SideEffectInstruction extends Instruction {
  */
 class CallSideEffectInstruction extends SideEffectInstruction {
   CallSideEffectInstruction() { this.getOpcode() instanceof Opcode::CallSideEffect }
+
+  /** Gets the operand for the value that will be read by this instruction */
+  final SideEffectOperand getSideEffectOperand() { result = this.getAnOperand() }
+
+  final Instruction getSideEffect() { result = this.getAnOperand().getDef() }
 }
 
 /**
@@ -1723,6 +1728,11 @@ class CallSideEffectInstruction extends SideEffectInstruction {
  */
 class CallReadSideEffectInstruction extends SideEffectInstruction {
   CallReadSideEffectInstruction() { this.getOpcode() instanceof Opcode::CallReadSideEffect }
+
+  /** Gets the operand for the value that will be read by this instruction */
+  final SideEffectOperand getSideEffectOperand() { result = this.getAnOperand() }
+
+  final Instruction getSideEffect() { result = this.getAnOperand().getDef() }
 }
 
 /**

cpp/ql/lib/semmle/code/cpp/ir/implementation/raw/gvn/internal/ValueNumberingImports.qll

@@ -1,3 +1,4 @@
 import semmle.code.cpp.ir.implementation.aliased_ssa.IR
 import semmle.code.cpp.ir.internal.Overlap
 import semmle.code.cpp.ir.internal.IRCppLanguage as Language
+import semmle.code.cpp.models.interfaces.SideEffect as SideEffect

cpp/ql/lib/semmle/code/cpp/ir/implementation/raw/gvn/internal/ValueNumberingInternal.qll

@@ -41,8 +41,92 @@ newtype TValueNumber =
   ) {
     loadTotalOverlapValueNumber(_, irFunc, type, memOperand, operand)
   } or
+  TCallValueNumber(TCallPartialValueNumber vn) { callValueNumber(_, _, vn) } or
   TUniqueValueNumber(IRFunction irFunc, Instruction instr) { uniqueValueNumber(instr, irFunc) }
 
+private class NumberableCallInstruction extends CallInstruction {
+  NumberableCallInstruction() {
+    not this.getResultIRType() instanceof IRVoidType and
+    exists(SideEffect::SideEffectFunction sideEffectFunc |
+      sideEffectFunc = this.getStaticCallTarget()
+    |
+      sideEffectFunc.hasOnlySpecificReadSideEffects() and
+      sideEffectFunc.hasOnlySpecificWriteSideEffects()
+    )
+  }
+}
+
+private newtype TCallPartialValueNumber =
+  TNilArgument() or
+  TArgument(TCallPartialValueNumber head, TValueNumber arg) {
+    exists(NumberableCallInstruction call, int index |
+      callArgValueNumber(call, index, arg) and
+      callPartialValueNumber(call, index, head)
+    )
+  }
+
+private predicate callValueNumber(
+  NumberableCallInstruction call, int index, TCallPartialValueNumber vn
+) {
+  index = max(int n | callArgRank(call, n, _) | n) and
+  exists(TCallPartialValueNumber head, TValueNumber arg |
+    callPartialValueNumber(call, index, pragma[only_bind_out](head)) and
+    callArgValueNumber(call, index, pragma[only_bind_into](arg)) and
+    vn = TArgument(head, arg)
+  )
+  or
+  not exists(int n | callArgRank(call, n, _)) and
+  index = -1 and
+  vn = TNilArgument()
+}
+
+private predicate callPartialValueNumber(
+  NumberableCallInstruction call, int index, TCallPartialValueNumber head
+) {
+  exists(call) and
+  index = 1 and
+  head = TNilArgument()
+  or
+  exists(TCallPartialValueNumber prev, TValueNumber prevVN |
+    callPartialValueNumber(call, index - 1, pragma[only_bind_out](prev)) and
+    callArgValueNumber(call, index - 1, pragma[only_bind_into](prevVN)) and
+    head = TArgument(prev, prevVN)
+  )
+}
+
+/**
+ */
+private predicate callArgValueNumber(NumberableCallInstruction call, int index, TValueNumber arg) {
+  exists(Instruction instr |
+    callArgRank(call, index, instr) and
+    arg = tvalueNumber(instr)
+  )
+}
+
+/**
+ * Holds if `arg` is the `index`th element in `call`'s extended argument list, including the `this`
+ * argument and side-effect reads.
+ */
+private predicate callArgRank(NumberableCallInstruction call, int index, Instruction arg) {
+  arg =
+    rank[index](int argIndex, boolean isEffect, Instruction instr |
+      // There is no need to include the call's read and write side effects on
+      // all-aliased-memory as `NumberableCallInstruction`s do not read or write
+      // to all-aliased-memory.
+      instr = call.getArgument(argIndex) and
+      isEffect = false
+      or
+      exists(ReadSideEffectInstruction read |
+        read.getPrimaryInstruction() = call and
+        read.getSideEffectOperand().getAnyDef() = instr and
+        read.getIndex() = argIndex and
+        isEffect = true
+      )
+    |
+      instr order by argIndex, isEffect
+    )
+}
+
 /**
  * A `CopyInstruction` whose source operand's value is congruent to the definition of that source
  * operand.
@@ -93,6 +177,8 @@ private predicate numberableInstruction(Instruction instr) {
   instr instanceof CongruentCopyInstruction
   or
   instr instanceof LoadTotalOverlapInstruction
+  or
+  instr instanceof NumberableCallInstruction
 }
 
 private predicate filteredNumberableInstruction(Instruction instr) {
@@ -309,6 +395,11 @@ private TValueNumber nonUniqueValueNumber(Instruction instr) {
       or
       // The value number of a copy is just the value number of its source value.
       result = tvalueNumber(instr.(CongruentCopyInstruction).getSourceValue())
+      or
+      exists(TCallPartialValueNumber pvn |
+        callValueNumber(instr, _, pvn) and
+        result = TCallValueNumber(pvn)
+      )
     )
   )
 }

cpp/ql/lib/semmle/code/cpp/ir/implementation/unaliased_ssa/Instruction.qll

@@ -1712,6 +1712,11 @@ class SideEffectInstruction extends Instruction {
  */
 class CallSideEffectInstruction extends SideEffectInstruction {
   CallSideEffectInstruction() { this.getOpcode() instanceof Opcode::CallSideEffect }
+
+  /** Gets the operand for the value that will be read by this instruction */
+  final SideEffectOperand getSideEffectOperand() { result = this.getAnOperand() }
+
+  final Instruction getSideEffect() { result = this.getAnOperand().getDef() }
 }
 
 /**
@@ -1723,6 +1728,11 @@ class CallSideEffectInstruction extends SideEffectInstruction {
  */
 class CallReadSideEffectInstruction extends SideEffectInstruction {
   CallReadSideEffectInstruction() { this.getOpcode() instanceof Opcode::CallReadSideEffect }
+
+  /** Gets the operand for the value that will be read by this instruction */
+  final SideEffectOperand getSideEffectOperand() { result = this.getAnOperand() }
+
+  final Instruction getSideEffect() { result = this.getAnOperand().getDef() }
 }
 
 /**

cpp/ql/lib/semmle/code/cpp/ir/implementation/unaliased_ssa/gvn/internal/ValueNumberingImports.qll

@@ -1,3 +1,4 @@
 import semmle.code.cpp.ir.implementation.aliased_ssa.IR
 import semmle.code.cpp.ir.internal.Overlap
 import semmle.code.cpp.ir.internal.IRCppLanguage as Language
+import semmle.code.cpp.models.interfaces.SideEffect as SideEffect

cpp/ql/lib/semmle/code/cpp/ir/implementation/unaliased_ssa/gvn/internal/ValueNumberingInternal.qll

@@ -41,8 +41,92 @@ newtype TValueNumber =
   ) {
     loadTotalOverlapValueNumber(_, irFunc, type, memOperand, operand)
   } or
+  TCallValueNumber(TCallPartialValueNumber vn) { callValueNumber(_, _, vn) } or
   TUniqueValueNumber(IRFunction irFunc, Instruction instr) { uniqueValueNumber(instr, irFunc) }
 
+private class NumberableCallInstruction extends CallInstruction {
+  NumberableCallInstruction() {
+    not this.getResultIRType() instanceof IRVoidType and
+    exists(SideEffect::SideEffectFunction sideEffectFunc |
+      sideEffectFunc = this.getStaticCallTarget()
+    |
+      sideEffectFunc.hasOnlySpecificReadSideEffects() and
+      sideEffectFunc.hasOnlySpecificWriteSideEffects()
+    )
+  }
+}
+
+private newtype TCallPartialValueNumber =
+  TNilArgument() or
+  TArgument(TCallPartialValueNumber head, TValueNumber arg) {
+    exists(NumberableCallInstruction call, int index |
+      callArgValueNumber(call, index, arg) and
+      callPartialValueNumber(call, index, head)
+    )
+  }
+
+private predicate callValueNumber(
+  NumberableCallInstruction call, int index, TCallPartialValueNumber vn
+) {
+  index = max(int n | callArgRank(call, n, _) | n) and
+  exists(TCallPartialValueNumber head, TValueNumber arg |
+    callPartialValueNumber(call, index, pragma[only_bind_out](head)) and
+    callArgValueNumber(call, index, pragma[only_bind_into](arg)) and
+    vn = TArgument(head, arg)
+  )
+  or
+  not exists(int n | callArgRank(call, n, _)) and
+  index = -1 and
+  vn = TNilArgument()
+}
+
+private predicate callPartialValueNumber(
+  NumberableCallInstruction call, int index, TCallPartialValueNumber head
+) {
+  exists(call) and
+  index = 1 and
+  head = TNilArgument()
+  or
+  exists(TCallPartialValueNumber prev, TValueNumber prevVN |
+    callPartialValueNumber(call, index - 1, pragma[only_bind_out](prev)) and
+    callArgValueNumber(call, index - 1, pragma[only_bind_into](prevVN)) and
+    head = TArgument(prev, prevVN)
+  )
+}
+
+/**
+ */
+private predicate callArgValueNumber(NumberableCallInstruction call, int index, TValueNumber arg) {
+  exists(Instruction instr |
+    callArgRank(call, index, instr) and
+    arg = tvalueNumber(instr)
+  )
+}
+
+/**
+ * Holds if `arg` is the `index`th element in `call`'s extended argument list, including the `this`
+ * argument and side-effect reads.
+ */
+private predicate callArgRank(NumberableCallInstruction call, int index, Instruction arg) {
+  arg =
+    rank[index](int argIndex, boolean isEffect, Instruction instr |
+      // There is no need to include the call's read and write side effects on
+      // all-aliased-memory as `NumberableCallInstruction`s do not read or write
+      // to all-aliased-memory.
+      instr = call.getArgument(argIndex) and
+      isEffect = false
+      or
+      exists(ReadSideEffectInstruction read |
+        read.getPrimaryInstruction() = call and
+        read.getSideEffectOperand().getAnyDef() = instr and
+        read.getIndex() = argIndex and
+        isEffect = true
+      )
+    |
+      instr order by argIndex, isEffect
+    )
+}
+
 /**
  * A `CopyInstruction` whose source operand's value is congruent to the definition of that source
  * operand.
@@ -93,6 +177,8 @@ private predicate numberableInstruction(Instruction instr) {
   instr instanceof CongruentCopyInstruction
   or
   instr instanceof LoadTotalOverlapInstruction
+  or
+  instr instanceof NumberableCallInstruction
 }
 
 private predicate filteredNumberableInstruction(Instruction instr) {
@@ -309,6 +395,11 @@ private TValueNumber nonUniqueValueNumber(Instruction instr) {
       or
       // The value number of a copy is just the value number of its source value.
       result = tvalueNumber(instr.(CongruentCopyInstruction).getSourceValue())
+      or
+      exists(TCallPartialValueNumber pvn |
+        callValueNumber(instr, _, pvn) and
+        result = TCallValueNumber(pvn)
+      )
     )
   )
 }

cpp/ql/lib/semmle/code/cpp/ir/implementation/unaliased_ssa/internal/SSAConstruction.qll

@@ -8,11 +8,6 @@ private import Imports::RawIR as RawIR
 private import SsaInstructions
 private import SsaOperands
 private import NewIR
-
-private class OldBlock = Reachability::ReachableBlock;
-
-private class OldInstruction = Reachability::ReachableInstruction;
-
 import Cached
 
 cached
@@ -58,7 +53,9 @@ private module Cached {
 
   cached
   predicate hasInstruction(TStageInstruction instr) {
-    instr instanceof TRawInstruction and instr instanceof OldInstruction
+    instr instanceof TRawInstruction and
+    instr instanceof OldInstruction and
+    not removedInstruction(instr)
     or
     instr = phiInstruction(_, _)
     or
@@ -382,7 +379,14 @@ private module Cached {
         (
           if Reachability::isInfeasibleInstructionSuccessor(oldInstruction, kind)
           then result = unreachedInstruction(instruction.getEnclosingIRFunction())
-          else result = getNewInstruction(oldInstruction.getSuccessor(kind))
+          else
+            if removedInstruction(oldInstruction.getSuccessor(kind))
+            then
+              // the only removed nodes are side-effect writes, but those may have Chi nodes
+              // skip to the following instruction in the old IR, which won't be removed
+              // if we start skipping specific side effects, this may no longer hold
+              result = getNewInstruction(oldInstruction.getSuccessor(kind).getSuccessor(kind))
+            else result = getNewInstruction(oldInstruction.getSuccessor(kind))
         )
       )
       or

cpp/ql/lib/semmle/code/cpp/ir/implementation/unaliased_ssa/internal/SSAConstructionInternal.qll

@@ -14,3 +14,9 @@ import semmle.code.cpp.ir.implementation.internal.TOperand::UnaliasedSsaOperands
 
 /** DEPRECATED: Alias for SsaOperands */
 deprecated module SSAOperands = SsaOperands;
+
+predicate removedInstruction(Reachability::ReachableInstruction instr) { none() }
+
+class OldBlock = Reachability::ReachableBlock;
+
+class OldInstruction = Reachability::ReachableInstruction;

cpp/ql/test/library-tests/ir/ssa/aliased_ssa_ir.expected

@@ -1050,46 +1050,36 @@ ssa.cpp:
 #  240|     r240_3(glval<unknown>)       = FunctionAddress[Constructible]  : 
 #  240|     r240_4(int)                  = Constant[1]                     : 
 #  240|     v240_5(void)                 = Call[Constructible]             : func:r240_3, this:r240_1, 0:r240_4
-#  240|     m240_6(unknown)              = ^CallSideEffect                 : ~m239_4
-#  240|     m240_7(unknown)              = Chi                             : total:m239_4, partial:m240_6
-#  240|     m240_8(Constructible)        = ^IndirectMayWriteSideEffect[-1] : &:r240_1
-#  240|     m240_9(Constructible)        = Chi                             : total:m240_2, partial:m240_8
+#  240|     m240_6(Constructible)        = ^IndirectMayWriteSideEffect[-1] : &:r240_1
+#  240|     m240_7(Constructible)        = Chi                             : total:m240_2, partial:m240_6
 #  241|     r241_1(glval<Constructible>) = VariableAddress[c]              : 
 #  241|     r241_2(glval<unknown>)       = FunctionAddress[g]              : 
 #  241|     v241_3(void)                 = Call[g]                         : func:r241_2, this:r241_1
-#  241|     m241_4(unknown)              = ^CallSideEffect                 : ~m240_7
-#  241|     m241_5(unknown)              = Chi                             : total:m240_7, partial:m241_4
-#  241|     v241_6(void)                 = ^IndirectReadSideEffect[-1]     : &:r241_1, m240_9
-#  241|     m241_7(Constructible)        = ^IndirectMayWriteSideEffect[-1] : &:r241_1
-#  241|     m241_8(Constructible)        = Chi                             : total:m240_9, partial:m241_7
+#  241|     v241_4(void)                 = ^IndirectReadSideEffect[-1]     : &:r241_1, m240_7
+#  241|     m241_5(Constructible)        = ^IndirectMayWriteSideEffect[-1] : &:r241_1
+#  241|     m241_6(Constructible)        = Chi                             : total:m240_7, partial:m241_5
 #  242|     r242_1(glval<Constructible>) = VariableAddress[c]              : 
 #  242|     r242_2(glval<unknown>)       = FunctionAddress[g]              : 
 #  242|     v242_3(void)                 = Call[g]                         : func:r242_2, this:r242_1
-#  242|     m242_4(unknown)              = ^CallSideEffect                 : ~m241_5
-#  242|     m242_5(unknown)              = Chi                             : total:m241_5, partial:m242_4
-#  242|     v242_6(void)                 = ^IndirectReadSideEffect[-1]     : &:r242_1, m241_8
-#  242|     m242_7(Constructible)        = ^IndirectMayWriteSideEffect[-1] : &:r242_1
-#  242|     m242_8(Constructible)        = Chi                             : total:m241_8, partial:m242_7
+#  242|     v242_4(void)                 = ^IndirectReadSideEffect[-1]     : &:r242_1, m241_6
+#  242|     m242_5(Constructible)        = ^IndirectMayWriteSideEffect[-1] : &:r242_1
+#  242|     m242_6(Constructible)        = Chi                             : total:m241_6, partial:m242_5
 #  243|     r243_1(glval<Constructible>) = VariableAddress[c2]             : 
 #  243|     m243_2(Constructible)        = Uninitialized[c2]               : &:r243_1
 #  243|     r243_3(glval<unknown>)       = FunctionAddress[Constructible]  : 
 #  243|     r243_4(int)                  = Constant[2]                     : 
 #  243|     v243_5(void)                 = Call[Constructible]             : func:r243_3, this:r243_1, 0:r243_4
-#  243|     m243_6(unknown)              = ^CallSideEffect                 : ~m242_5
-#  243|     m243_7(unknown)              = Chi                             : total:m242_5, partial:m243_6
-#  243|     m243_8(Constructible)        = ^IndirectMayWriteSideEffect[-1] : &:r243_1
-#  243|     m243_9(Constructible)        = Chi                             : total:m243_2, partial:m243_8
+#  243|     m243_6(Constructible)        = ^IndirectMayWriteSideEffect[-1] : &:r243_1
+#  243|     m243_7(Constructible)        = Chi                             : total:m243_2, partial:m243_6
 #  244|     r244_1(glval<Constructible>) = VariableAddress[c2]             : 
 #  244|     r244_2(glval<unknown>)       = FunctionAddress[g]              : 
 #  244|     v244_3(void)                 = Call[g]                         : func:r244_2, this:r244_1
-#  244|     m244_4(unknown)              = ^CallSideEffect                 : ~m243_7
-#  244|     m244_5(unknown)              = Chi                             : total:m243_7, partial:m244_4
-#  244|     v244_6(void)                 = ^IndirectReadSideEffect[-1]     : &:r244_1, m243_9
-#  244|     m244_7(Constructible)        = ^IndirectMayWriteSideEffect[-1] : &:r244_1
-#  244|     m244_8(Constructible)        = Chi                             : total:m243_9, partial:m244_7
+#  244|     v244_4(void)                 = ^IndirectReadSideEffect[-1]     : &:r244_1, m243_7
+#  244|     m244_5(Constructible)        = ^IndirectMayWriteSideEffect[-1] : &:r244_1
+#  244|     m244_6(Constructible)        = Chi                             : total:m243_7, partial:m244_5
 #  245|     v245_1(void)                 = NoOp                            : 
 #  239|     v239_5(void)                 = ReturnVoid                      : 
-#  239|     v239_6(void)                 = AliasedUse                      : ~m244_5
+#  239|     v239_6(void)                 = AliasedUse                      : m239_3
 #  239|     v239_7(void)                 = ExitFunction                    : 
 
 #  247| char* VoidStarIndirectParameters(char*, int)
@@ -1391,43 +1381,37 @@ ssa.cpp:
 #  294|     r294_18(glval<int>)     = VariableAddress[x]              : 
 #  294|     r294_19(int)            = Load[x]                         : &:r294_18, m291_6
 #  294|     v294_20(void)           = Call[A]                         : func:r294_17, this:r294_16, 0:r294_19
-#  294|     m294_21(unknown)        = ^CallSideEffect                 : ~m294_14
-#  294|     m294_22(unknown)        = Chi                             : total:m294_14, partial:m294_21
-#  294|     m294_23(A)              = ^IndirectMayWriteSideEffect[-1] : &:r294_16
-#  294|     m294_24(unknown)        = Chi                             : total:m294_15, partial:m294_23
-#  294|     v294_25(void)           = Call[A]                         : func:r294_9, this:r294_8, 0:r294_16
-#  294|     m294_26(unknown)        = ^CallSideEffect                 : ~m294_22
-#  294|     m294_27(unknown)        = Chi                             : total:m294_22, partial:m294_26
-#  294|     v294_28(void)           = ^BufferReadSideEffect[0]        : &:r294_16, ~m294_24
-#  294|     m294_29(A)              = ^IndirectMayWriteSideEffect[-1] : &:r294_8
-#  294|     m294_30(unknown)        = Chi                             : total:m294_7, partial:m294_29
-#  294|     m294_31(unknown)        = ^BufferMayWriteSideEffect[0]    : &:r294_16
-#  294|     m294_32(unknown)        = Chi                             : total:m294_24, partial:m294_31
-#  294|     r294_33(glval<int>)     = FieldAddress[i]                 : r294_8
-#  294|     r294_34(int)            = Load[?]                         : &:r294_33, ~m294_30
-#  294|     m294_35(int)            = Store[j]                        : &:r294_1, r294_34
+#  294|     m294_21(A)              = ^IndirectMayWriteSideEffect[-1] : &:r294_16
+#  294|     m294_22(unknown)        = Chi                             : total:m294_15, partial:m294_21
+#  294|     v294_23(void)           = Call[A]                         : func:r294_9, this:r294_8, 0:r294_16
+#  294|     v294_24(void)           = ^BufferReadSideEffect[0]        : &:r294_16, ~m294_22
+#  294|     m294_25(A)              = ^IndirectMayWriteSideEffect[-1] : &:r294_8
+#  294|     m294_26(unknown)        = Chi                             : total:m294_7, partial:m294_25
+#  294|     m294_27(unknown)        = ^BufferMayWriteSideEffect[0]    : &:r294_16
+#  294|     m294_28(unknown)        = Chi                             : total:m294_22, partial:m294_27
+#  294|     r294_29(glval<int>)     = FieldAddress[i]                 : r294_8
+#  294|     r294_30(int)            = Load[?]                         : &:r294_29, ~m294_26
+#  294|     m294_31(int)            = Store[j]                        : &:r294_1, r294_30
 #  295|     r295_1(glval<A *>)      = VariableAddress[a]              : 
 #  295|     r295_2(glval<unknown>)  = FunctionAddress[operator new]   : 
 #  295|     r295_3(unsigned long)   = Constant[4]                     : 
 #  295|     r295_4(void *)          = Call[operator new]              : func:r295_2, 0:r295_3
-#  295|     m295_5(unknown)         = ^CallSideEffect                 : ~m294_27
-#  295|     m295_6(unknown)         = Chi                             : total:m294_27, partial:m295_5
+#  295|     m295_5(unknown)         = ^CallSideEffect                 : ~m294_14
+#  295|     m295_6(unknown)         = Chi                             : total:m294_14, partial:m295_5
 #  295|     m295_7(unknown)         = ^InitializeDynamicAllocation    : &:r295_4
 #  295|     r295_8(A *)             = Convert                         : r295_4
 #  295|     r295_9(glval<unknown>)  = FunctionAddress[A]              : 
 #  295|     v295_10(void)           = Call[A]                         : func:r295_9, this:r295_8
-#  295|     m295_11(unknown)        = ^CallSideEffect                 : ~m295_6
-#  295|     m295_12(unknown)        = Chi                             : total:m295_6, partial:m295_11
-#  295|     m295_13(A)              = ^IndirectMayWriteSideEffect[-1] : &:r295_8
-#  295|     m295_14(unknown)        = Chi                             : total:m295_7, partial:m295_13
-#  295|     m295_15(A *)            = Store[a]                        : &:r295_1, r295_8
+#  295|     m295_11(A)              = ^IndirectMayWriteSideEffect[-1] : &:r295_8
+#  295|     m295_12(unknown)        = Chi                             : total:m295_7, partial:m295_11
+#  295|     m295_13(A *)            = Store[a]                        : &:r295_1, r295_8
 #  296|     r296_1(glval<Point *>)  = VariableAddress[#return]        : 
 #  296|     r296_2(glval<Point *>)  = VariableAddress[p]              : 
 #  296|     r296_3(Point *)         = Load[p]                         : &:r296_2, m292_9
 #  296|     m296_4(Point *)         = Store[#return]                  : &:r296_1, r296_3
 #  291|     r291_7(glval<Point *>)  = VariableAddress[#return]        : 
 #  291|     v291_8(void)            = ReturnValue                     : &:r291_7, m296_4
-#  291|     v291_9(void)            = AliasedUse                      : ~m295_12
+#  291|     v291_9(void)            = AliasedUse                      : ~m295_6
 #  291|     v291_10(void)           = ExitFunction                    : 
 
 #  301| int main(int, char**)

cpp/ql/test/library-tests/ir/ssa/aliased_ssa_ir_unsound.expected

@@ -1045,46 +1045,36 @@ ssa.cpp:
 #  240|     r240_3(glval<unknown>)       = FunctionAddress[Constructible]  : 
 #  240|     r240_4(int)                  = Constant[1]                     : 
 #  240|     v240_5(void)                 = Call[Constructible]             : func:r240_3, this:r240_1, 0:r240_4
-#  240|     m240_6(unknown)              = ^CallSideEffect                 : ~m239_4
-#  240|     m240_7(unknown)              = Chi                             : total:m239_4, partial:m240_6
-#  240|     m240_8(Constructible)        = ^IndirectMayWriteSideEffect[-1] : &:r240_1
-#  240|     m240_9(Constructible)        = Chi                             : total:m240_2, partial:m240_8
+#  240|     m240_6(Constructible)        = ^IndirectMayWriteSideEffect[-1] : &:r240_1
+#  240|     m240_7(Constructible)        = Chi                             : total:m240_2, partial:m240_6
 #  241|     r241_1(glval<Constructible>) = VariableAddress[c]              : 
 #  241|     r241_2(glval<unknown>)       = FunctionAddress[g]              : 
 #  241|     v241_3(void)                 = Call[g]                         : func:r241_2, this:r241_1
-#  241|     m241_4(unknown)              = ^CallSideEffect                 : ~m240_7
-#  241|     m241_5(unknown)              = Chi                             : total:m240_7, partial:m241_4
-#  241|     v241_6(void)                 = ^IndirectReadSideEffect[-1]     : &:r241_1, m240_9
-#  241|     m241_7(Constructible)        = ^IndirectMayWriteSideEffect[-1] : &:r241_1
-#  241|     m241_8(Constructible)        = Chi                             : total:m240_9, partial:m241_7
+#  241|     v241_4(void)                 = ^IndirectReadSideEffect[-1]     : &:r241_1, m240_7
+#  241|     m241_5(Constructible)        = ^IndirectMayWriteSideEffect[-1] : &:r241_1
+#  241|     m241_6(Constructible)        = Chi                             : total:m240_7, partial:m241_5
 #  242|     r242_1(glval<Constructible>) = VariableAddress[c]              : 
 #  242|     r242_2(glval<unknown>)       = FunctionAddress[g]              : 
 #  242|     v242_3(void)                 = Call[g]                         : func:r242_2, this:r242_1
-#  242|     m242_4(unknown)              = ^CallSideEffect                 : ~m241_5
-#  242|     m242_5(unknown)              = Chi                             : total:m241_5, partial:m242_4
-#  242|     v242_6(void)                 = ^IndirectReadSideEffect[-1]     : &:r242_1, m241_8
-#  242|     m242_7(Constructible)        = ^IndirectMayWriteSideEffect[-1] : &:r242_1
-#  242|     m242_8(Constructible)        = Chi                             : total:m241_8, partial:m242_7
+#  242|     v242_4(void)                 = ^IndirectReadSideEffect[-1]     : &:r242_1, m241_6
+#  242|     m242_5(Constructible)        = ^IndirectMayWriteSideEffect[-1] : &:r242_1
+#  242|     m242_6(Constructible)        = Chi                             : total:m241_6, partial:m242_5
 #  243|     r243_1(glval<Constructible>) = VariableAddress[c2]             : 
 #  243|     m243_2(Constructible)        = Uninitialized[c2]               : &:r243_1
 #  243|     r243_3(glval<unknown>)       = FunctionAddress[Constructible]  : 
 #  243|     r243_4(int)                  = Constant[2]                     : 
 #  243|     v243_5(void)                 = Call[Constructible]             : func:r243_3, this:r243_1, 0:r243_4
-#  243|     m243_6(unknown)              = ^CallSideEffect                 : ~m242_5
-#  243|     m243_7(unknown)              = Chi                             : total:m242_5, partial:m243_6
-#  243|     m243_8(Constructible)        = ^IndirectMayWriteSideEffect[-1] : &:r243_1
-#  243|     m243_9(Constructible)        = Chi                             : total:m243_2, partial:m243_8
+#  243|     m243_6(Constructible)        = ^IndirectMayWriteSideEffect[-1] : &:r243_1
+#  243|     m243_7(Constructible)        = Chi                             : total:m243_2, partial:m243_6
 #  244|     r244_1(glval<Constructible>) = VariableAddress[c2]             : 
 #  244|     r244_2(glval<unknown>)       = FunctionAddress[g]              : 
 #  244|     v244_3(void)                 = Call[g]                         : func:r244_2, this:r244_1
-#  244|     m244_4(unknown)              = ^CallSideEffect                 : ~m243_7
-#  244|     m244_5(unknown)              = Chi                             : total:m243_7, partial:m244_4
-#  244|     v244_6(void)                 = ^IndirectReadSideEffect[-1]     : &:r244_1, m243_9
-#  244|     m244_7(Constructible)        = ^IndirectMayWriteSideEffect[-1] : &:r244_1
-#  244|     m244_8(Constructible)        = Chi                             : total:m243_9, partial:m244_7
+#  244|     v244_4(void)                 = ^IndirectReadSideEffect[-1]     : &:r244_1, m243_7
+#  244|     m244_5(Constructible)        = ^IndirectMayWriteSideEffect[-1] : &:r244_1
+#  244|     m244_6(Constructible)        = Chi                             : total:m243_7, partial:m244_5
 #  245|     v245_1(void)                 = NoOp                            : 
 #  239|     v239_5(void)                 = ReturnVoid                      : 
-#  239|     v239_6(void)                 = AliasedUse                      : ~m244_5
+#  239|     v239_6(void)                 = AliasedUse                      : m239_3
 #  239|     v239_7(void)                 = ExitFunction                    : 
 
 #  247| char* VoidStarIndirectParameters(char*, int)
@@ -1385,43 +1375,37 @@ ssa.cpp:
 #  294|     r294_18(glval<int>)     = VariableAddress[x]              : 
 #  294|     r294_19(int)            = Load[x]                         : &:r294_18, m291_6
 #  294|     v294_20(void)           = Call[A]                         : func:r294_17, this:r294_16, 0:r294_19
-#  294|     m294_21(unknown)        = ^CallSideEffect                 : ~m294_14
-#  294|     m294_22(unknown)        = Chi                             : total:m294_14, partial:m294_21
-#  294|     m294_23(A)              = ^IndirectMayWriteSideEffect[-1] : &:r294_16
-#  294|     m294_24(unknown)        = Chi                             : total:m294_15, partial:m294_23
-#  294|     v294_25(void)           = Call[A]                         : func:r294_9, this:r294_8, 0:r294_16
-#  294|     m294_26(unknown)        = ^CallSideEffect                 : ~m294_22
-#  294|     m294_27(unknown)        = Chi                             : total:m294_22, partial:m294_26
-#  294|     v294_28(void)           = ^BufferReadSideEffect[0]        : &:r294_16, ~m294_24
-#  294|     m294_29(A)              = ^IndirectMayWriteSideEffect[-1] : &:r294_8
-#  294|     m294_30(unknown)        = Chi                             : total:m294_7, partial:m294_29
-#  294|     m294_31(unknown)        = ^BufferMayWriteSideEffect[0]    : &:r294_16
-#  294|     m294_32(unknown)        = Chi                             : total:m294_24, partial:m294_31
-#  294|     r294_33(glval<int>)     = FieldAddress[i]                 : r294_8
-#  294|     r294_34(int)            = Load[?]                         : &:r294_33, ~m294_30
-#  294|     m294_35(int)            = Store[j]                        : &:r294_1, r294_34
+#  294|     m294_21(A)              = ^IndirectMayWriteSideEffect[-1] : &:r294_16
+#  294|     m294_22(unknown)        = Chi                             : total:m294_15, partial:m294_21
+#  294|     v294_23(void)           = Call[A]                         : func:r294_9, this:r294_8, 0:r294_16
+#  294|     v294_24(void)           = ^BufferReadSideEffect[0]        : &:r294_16, ~m294_22
+#  294|     m294_25(A)              = ^IndirectMayWriteSideEffect[-1] : &:r294_8
+#  294|     m294_26(unknown)        = Chi                             : total:m294_7, partial:m294_25
+#  294|     m294_27(unknown)        = ^BufferMayWriteSideEffect[0]    : &:r294_16
+#  294|     m294_28(unknown)        = Chi                             : total:m294_22, partial:m294_27
+#  294|     r294_29(glval<int>)     = FieldAddress[i]                 : r294_8
+#  294|     r294_30(int)            = Load[?]                         : &:r294_29, ~m294_26
+#  294|     m294_31(int)            = Store[j]                        : &:r294_1, r294_30
 #  295|     r295_1(glval<A *>)      = VariableAddress[a]              : 
 #  295|     r295_2(glval<unknown>)  = FunctionAddress[operator new]   : 
 #  295|     r295_3(unsigned long)   = Constant[4]                     : 
 #  295|     r295_4(void *)          = Call[operator new]              : func:r295_2, 0:r295_3
-#  295|     m295_5(unknown)         = ^CallSideEffect                 : ~m294_27
-#  295|     m295_6(unknown)         = Chi                             : total:m294_27, partial:m295_5
+#  295|     m295_5(unknown)         = ^CallSideEffect                 : ~m294_14
+#  295|     m295_6(unknown)         = Chi                             : total:m294_14, partial:m295_5
 #  295|     m295_7(unknown)         = ^InitializeDynamicAllocation    : &:r295_4
 #  295|     r295_8(A *)             = Convert                         : r295_4
 #  295|     r295_9(glval<unknown>)  = FunctionAddress[A]              : 
 #  295|     v295_10(void)           = Call[A]                         : func:r295_9, this:r295_8
-#  295|     m295_11(unknown)        = ^CallSideEffect                 : ~m295_6
-#  295|     m295_12(unknown)        = Chi                             : total:m295_6, partial:m295_11
-#  295|     m295_13(A)              = ^IndirectMayWriteSideEffect[-1] : &:r295_8
-#  295|     m295_14(unknown)        = Chi                             : total:m295_7, partial:m295_13
-#  295|     m295_15(A *)            = Store[a]                        : &:r295_1, r295_8
+#  295|     m295_11(A)              = ^IndirectMayWriteSideEffect[-1] : &:r295_8
+#  295|     m295_12(unknown)        = Chi                             : total:m295_7, partial:m295_11
+#  295|     m295_13(A *)            = Store[a]                        : &:r295_1, r295_8
 #  296|     r296_1(glval<Point *>)  = VariableAddress[#return]        : 
 #  296|     r296_2(glval<Point *>)  = VariableAddress[p]              : 
 #  296|     r296_3(Point *)         = Load[p]                         : &:r296_2, m292_9
 #  296|     m296_4(Point *)         = Store[#return]                  : &:r296_1, r296_3
 #  291|     r291_7(glval<Point *>)  = VariableAddress[#return]        : 
 #  291|     v291_8(void)            = ReturnValue                     : &:r291_7, m296_4
-#  291|     v291_9(void)            = AliasedUse                      : ~m295_12
+#  291|     v291_9(void)            = AliasedUse                      : ~m295_6
 #  291|     v291_10(void)           = ExitFunction                    : 
 
 #  301| int main(int, char**)

cpp/ql/test/library-tests/syntax-zoo/dataflow-ir-consistency.expected

@@ -149,9 +149,6 @@ uniqueNodeLocation
 | conditional_destructors.cpp:29:6:29:7 | EnterFunction | Node should have one location but has 2. |
 | conditional_destructors.cpp:29:6:29:7 | ExitFunction | Node should have one location but has 2. |
 | conditional_destructors.cpp:29:6:29:7 | InitializeNonLocal | Node should have one location but has 2. |
-| conditional_destructors.cpp:29:6:29:7 | Phi | Node should have one location but has 2. |
-| conditional_destructors.cpp:29:6:29:7 | Phi | Node should have one location but has 2. |
-| conditional_destructors.cpp:29:6:29:7 | Phi | Node should have one location but has 2. |
 | conditional_destructors.cpp:29:6:29:7 | ReturnVoid | Node should have one location but has 2. |
 | conditional_destructors.cpp:29:6:29:7 | SideEffect | Node should have one location but has 2. |
 | conditional_destructors.cpp:38:6:38:7 | AliasedDefinition | Node should have one location but has 2. |
@@ -162,9 +159,6 @@ uniqueNodeLocation
 | conditional_destructors.cpp:38:6:38:7 | EnterFunction | Node should have one location but has 2. |
 | conditional_destructors.cpp:38:6:38:7 | ExitFunction | Node should have one location but has 2. |
 | conditional_destructors.cpp:38:6:38:7 | InitializeNonLocal | Node should have one location but has 2. |
-| conditional_destructors.cpp:38:6:38:7 | Phi | Node should have one location but has 2. |
-| conditional_destructors.cpp:38:6:38:7 | Phi | Node should have one location but has 2. |
-| conditional_destructors.cpp:38:6:38:7 | Phi | Node should have one location but has 2. |
 | conditional_destructors.cpp:38:6:38:7 | ReturnVoid | Node should have one location but has 2. |
 | conditional_destructors.cpp:38:6:38:7 | SideEffect | Node should have one location but has 2. |
 | conditional_destructors.cpp:38:6:38:7 | Unreached | Node should have one location but has 2. |
@@ -561,9 +555,6 @@ uniqueNodeLocation
 | forstmt.cpp:1:6:1:7 | EnterFunction | Node should have one location but has 2. |
 | forstmt.cpp:1:6:1:7 | ExitFunction | Node should have one location but has 2. |
 | forstmt.cpp:1:6:1:7 | InitializeNonLocal | Node should have one location but has 2. |
-| forstmt.cpp:1:6:1:7 | Phi | Node should have one location but has 2. |
-| forstmt.cpp:1:6:1:7 | Phi | Node should have one location but has 2. |
-| forstmt.cpp:1:6:1:7 | Phi | Node should have one location but has 2. |
 | forstmt.cpp:1:6:1:7 | ReturnVoid | Node should have one location but has 2. |
 | forstmt.cpp:1:6:1:7 | SideEffect | Node should have one location but has 2. |
 | forstmt.cpp:8:6:8:7 | AliasedDefinition | Node should have one location but has 2. |
@@ -574,9 +565,6 @@ uniqueNodeLocation
 | forstmt.cpp:8:6:8:7 | EnterFunction | Node should have one location but has 2. |
 | forstmt.cpp:8:6:8:7 | ExitFunction | Node should have one location but has 2. |
 | forstmt.cpp:8:6:8:7 | InitializeNonLocal | Node should have one location but has 2. |
-| forstmt.cpp:8:6:8:7 | Phi | Node should have one location but has 2. |
-| forstmt.cpp:8:6:8:7 | Phi | Node should have one location but has 2. |
-| forstmt.cpp:8:6:8:7 | Phi | Node should have one location but has 2. |
 | forstmt.cpp:8:6:8:7 | ReturnVoid | Node should have one location but has 2. |
 | forstmt.cpp:8:6:8:7 | SideEffect | Node should have one location but has 2. |
 | forstmt.cpp:8:6:8:7 | Unreached | Node should have one location but has 2. |

cpp/ql/test/library-tests/valuenumbering/GlobalValueNumbering/ast_gvn.expected

@@ -2,6 +2,7 @@
 | test.cpp:5:7:5:8 | p0 | 5:c7-c8 6:c7-c8 |
 | test.cpp:5:7:5:13 | ... + ... | 5:c7-c13 6:c7-c13 7:c7-c7 |
 | test.cpp:5:12:5:13 | p1 | 5:c12-c13 6:c12-c13 |
+| test.cpp:10:16:10:16 | 1 | 10:c16-c16 176:c7-c7 178:c7-c7 |
 | test.cpp:16:3:16:3 | x | 16:c3-c3 17:c3-c3 |
 | test.cpp:16:7:16:8 | p0 | 16:c7-c8 17:c7-c8 |
 | test.cpp:16:7:16:13 | ... + ... | 16:c7-c13 17:c7-c13 |
@@ -38,3 +39,9 @@
 | test.cpp:145:15:145:15 | y | 145:c15-c15 147:c7-c7 |
 | test.cpp:153:11:153:18 | global_a | 153:c11-c18 154:c11-c18 156:c3-c10 |
 | test.cpp:153:21:153:21 | x | 153:c21-c21 154:c21-c21 |
+| test.cpp:166:18:166:20 | (const char *)... | 166:c18-c20 167:c18-c20 173:c18-c20 |
+| test.cpp:166:18:166:20 | dst | 166:c18-c20 167:c18-c20 171:c10-c12 173:c18-c20 |
+| test.cpp:168:18:168:20 | (const char *)... | 168:c18-c20 169:c18-c20 171:c15-c17 174:c18-c20 |
+| test.cpp:168:18:168:20 | src | 168:c18-c20 169:c18-c20 171:c15-c17 174:c18-c20 |
+| test.cpp:176:10:176:10 | 2 | 176:c10-c10 178:c10-c10 21:c16-c16 |
+| test.cpp:177:7:177:7 | 3 | 177:c7-c7 35:c16-c16 |

cpp/ql/test/library-tests/valuenumbering/GlobalValueNumbering/ast_ir_gvn.expected

@@ -44,3 +44,11 @@
 | test.cpp:144:15:144:15 | GVN | 144:c15-c15 149:c15-c15 |
 | test.cpp:153:11:153:18 | GVN | 153:c11-c18 154:c11-c18 156:c3-c10 |
 | test.cpp:153:21:153:21 | GVN | 153:c21-c21 154:c21-c21 |
+| test.cpp:166:11:166:16 | GVN | 166:c11-c16 167:c11-c16 |
+| test.cpp:166:18:166:20 | GVN | 166:c18-c20 167:c18-c20 171:c10-c12 173:c18-c20 |
+| test.cpp:166:18:166:20 | GVN | 166:c18-c20 167:c18-c20 173:c18-c20 |
+| test.cpp:168:11:168:16 | GVN | 168:c11-c16 169:c11-c16 174:c11-c16 |
+| test.cpp:168:18:168:20 | GVN | 168:c18-c20 169:c18-c20 171:c15-c17 174:c18-c20 |
+| test.cpp:168:18:168:20 | GVN | 168:c18-c20 169:c18-c20 171:c15-c17 174:c18-c20 |
+| test.cpp:176:7:176:7 | GVN | 176:c7-c7 178:c7-c7 |
+| test.cpp:176:10:176:10 | GVN | 176:c10-c10 178:c10-c10 |

cpp/ql/test/library-tests/valuenumbering/GlobalValueNumbering/diff_ir_expr.expected

@@ -1,15 +1,20 @@
 | test.cpp:5:3:5:13 | ... = ... | test.cpp:5:3:5:13 | ... = ... | AST only |
 | test.cpp:6:3:6:13 | ... = ... | test.cpp:6:3:6:13 | ... = ... | AST only |
 | test.cpp:7:3:7:7 | ... = ... | test.cpp:7:3:7:7 | ... = ... | AST only |
+| test.cpp:10:16:10:16 | 1 | test.cpp:176:7:176:7 | 1 | AST only |
+| test.cpp:10:16:10:16 | 1 | test.cpp:178:7:178:7 | 1 | AST only |
 | test.cpp:16:3:16:24 | ... = ... | test.cpp:16:3:16:24 | ... = ... | AST only |
 | test.cpp:17:3:17:24 | ... = ... | test.cpp:17:3:17:24 | ... = ... | AST only |
 | test.cpp:18:3:18:7 | ... = ... | test.cpp:18:3:18:7 | ... = ... | AST only |
+| test.cpp:21:16:21:16 | 2 | test.cpp:176:10:176:10 | 2 | AST only |
+| test.cpp:21:16:21:16 | 2 | test.cpp:178:10:178:10 | 2 | AST only |
 | test.cpp:29:3:29:3 | x | test.cpp:31:3:31:3 | x | IR only |
 | test.cpp:29:3:29:24 | ... = ... | test.cpp:29:3:29:24 | ... = ... | AST only |
 | test.cpp:30:3:30:17 | call to change_global02 | test.cpp:30:3:30:17 | call to change_global02 | AST only |
 | test.cpp:31:3:31:3 | x | test.cpp:29:3:29:3 | x | IR only |
 | test.cpp:31:3:31:24 | ... = ... | test.cpp:31:3:31:24 | ... = ... | AST only |
 | test.cpp:32:3:32:7 | ... = ... | test.cpp:32:3:32:7 | ... = ... | AST only |
+| test.cpp:35:16:35:16 | 3 | test.cpp:177:7:177:7 | 3 | AST only |
 | test.cpp:43:3:43:3 | x | test.cpp:45:3:45:3 | x | IR only |
 | test.cpp:43:3:43:24 | ... = ... | test.cpp:43:3:43:24 | ... = ... | AST only |
 | test.cpp:43:7:43:24 | ... + ... | test.cpp:45:7:45:24 | ... + ... | IR only |
@@ -127,3 +132,41 @@
 | test.cpp:147:7:147:7 | y | test.cpp:145:15:145:15 | y | AST only |
 | test.cpp:149:15:149:15 | x | test.cpp:144:15:144:15 | x | IR only |
 | test.cpp:156:3:156:17 | ... = ... | test.cpp:156:3:156:17 | ... = ... | AST only |
+| test.cpp:166:11:166:16 | call to strlen | test.cpp:167:11:167:16 | call to strlen | IR only |
+| test.cpp:166:18:166:20 | (const char *)... | test.cpp:166:18:166:20 | (const char *)... | AST only |
+| test.cpp:166:18:166:20 | (const char *)... | test.cpp:167:18:167:20 | (const char *)... | AST only |
+| test.cpp:166:18:166:20 | (const char *)... | test.cpp:173:18:173:20 | (const char *)... | AST only |
+| test.cpp:167:11:167:16 | call to strlen | test.cpp:166:11:166:16 | call to strlen | IR only |
+| test.cpp:167:18:167:20 | (const char *)... | test.cpp:166:18:166:20 | (const char *)... | AST only |
+| test.cpp:167:18:167:20 | (const char *)... | test.cpp:167:18:167:20 | (const char *)... | AST only |
+| test.cpp:167:18:167:20 | (const char *)... | test.cpp:173:18:173:20 | (const char *)... | AST only |
+| test.cpp:168:11:168:16 | call to strlen | test.cpp:169:11:169:16 | call to strlen | IR only |
+| test.cpp:168:11:168:16 | call to strlen | test.cpp:174:11:174:16 | call to strlen | IR only |
+| test.cpp:168:18:168:20 | (const char *)... | test.cpp:168:18:168:20 | (const char *)... | AST only |
+| test.cpp:168:18:168:20 | (const char *)... | test.cpp:169:18:169:20 | (const char *)... | AST only |
+| test.cpp:168:18:168:20 | (const char *)... | test.cpp:171:15:171:17 | (const char *)... | AST only |
+| test.cpp:168:18:168:20 | (const char *)... | test.cpp:174:18:174:20 | (const char *)... | AST only |
+| test.cpp:169:11:169:16 | call to strlen | test.cpp:168:11:168:16 | call to strlen | IR only |
+| test.cpp:169:11:169:16 | call to strlen | test.cpp:174:11:174:16 | call to strlen | IR only |
+| test.cpp:169:18:169:20 | (const char *)... | test.cpp:168:18:168:20 | (const char *)... | AST only |
+| test.cpp:169:18:169:20 | (const char *)... | test.cpp:169:18:169:20 | (const char *)... | AST only |
+| test.cpp:169:18:169:20 | (const char *)... | test.cpp:171:15:171:17 | (const char *)... | AST only |
+| test.cpp:169:18:169:20 | (const char *)... | test.cpp:174:18:174:20 | (const char *)... | AST only |
+| test.cpp:171:15:171:17 | (const char *)... | test.cpp:168:18:168:20 | (const char *)... | AST only |
+| test.cpp:171:15:171:17 | (const char *)... | test.cpp:169:18:169:20 | (const char *)... | AST only |
+| test.cpp:171:15:171:17 | (const char *)... | test.cpp:171:15:171:17 | (const char *)... | AST only |
+| test.cpp:171:15:171:17 | (const char *)... | test.cpp:174:18:174:20 | (const char *)... | AST only |
+| test.cpp:173:18:173:20 | (const char *)... | test.cpp:166:18:166:20 | (const char *)... | AST only |
+| test.cpp:173:18:173:20 | (const char *)... | test.cpp:167:18:167:20 | (const char *)... | AST only |
+| test.cpp:173:18:173:20 | (const char *)... | test.cpp:173:18:173:20 | (const char *)... | AST only |
+| test.cpp:174:11:174:16 | call to strlen | test.cpp:168:11:168:16 | call to strlen | IR only |
+| test.cpp:174:11:174:16 | call to strlen | test.cpp:169:11:169:16 | call to strlen | IR only |
+| test.cpp:174:18:174:20 | (const char *)... | test.cpp:168:18:168:20 | (const char *)... | AST only |
+| test.cpp:174:18:174:20 | (const char *)... | test.cpp:169:18:169:20 | (const char *)... | AST only |
+| test.cpp:174:18:174:20 | (const char *)... | test.cpp:171:15:171:17 | (const char *)... | AST only |
+| test.cpp:174:18:174:20 | (const char *)... | test.cpp:174:18:174:20 | (const char *)... | AST only |
+| test.cpp:176:7:176:7 | 1 | test.cpp:10:16:10:16 | 1 | AST only |
+| test.cpp:176:10:176:10 | 2 | test.cpp:21:16:21:16 | 2 | AST only |
+| test.cpp:177:7:177:7 | 3 | test.cpp:35:16:35:16 | 3 | AST only |
+| test.cpp:178:7:178:7 | 1 | test.cpp:10:16:10:16 | 1 | AST only |
+| test.cpp:178:10:178:10 | 2 | test.cpp:21:16:21:16 | 2 | AST only |

cpp/ql/test/library-tests/valuenumbering/GlobalValueNumbering/ir_gvn.expected

@@ -1145,3 +1145,206 @@ test.cpp:
 #  152|     v152_7(void)       = ReturnVoid                : 
 #  152|     v152_8(void)       = AliasedUse                : ~m156_7
 #  152|     v152_9(void)       = ExitFunction              : 
+
+#  163| int add(int, int)
+#  163|   Block 0
+#  163|     v163_1(void)        = EnterFunction            : 
+#  163|     m163_2(unknown)     = AliasedDefinition        : 
+#  163|         valnum = unique
+#  163|     m163_3(unknown)     = InitializeNonLocal       : 
+#  163|         valnum = unique
+#  163|     m163_4(unknown)     = Chi                      : total:m163_2, partial:m163_3
+#  163|         valnum = unique
+#  163|     r163_5(glval<int>)  = VariableAddress[a]       : 
+#  163|         valnum = r163_10, r163_5
+#  163|     m163_6(int)         = InitializeParameter[a]   : &:r163_5
+#  163|         valnum = m163_6, r163_11
+#  163|     r163_7(glval<int>)  = VariableAddress[b]       : 
+#  163|         valnum = r163_12, r163_7
+#  163|     m163_8(int)         = InitializeParameter[b]   : &:r163_7
+#  163|         valnum = m163_8, r163_13
+#  163|     r163_9(glval<int>)  = VariableAddress[#return] : 
+#  163|         valnum = r163_16, r163_9
+#  163|     r163_10(glval<int>) = VariableAddress[a]       : 
+#  163|         valnum = r163_10, r163_5
+#  163|     r163_11(int)        = Load[a]                  : &:r163_10, m163_6
+#  163|         valnum = m163_6, r163_11
+#  163|     r163_12(glval<int>) = VariableAddress[b]       : 
+#  163|         valnum = r163_12, r163_7
+#  163|     r163_13(int)        = Load[b]                  : &:r163_12, m163_8
+#  163|         valnum = m163_8, r163_13
+#  163|     r163_14(int)        = Add                      : r163_11, r163_13
+#  163|         valnum = m163_15, r163_14
+#  163|     m163_15(int)        = Store[#return]           : &:r163_9, r163_14
+#  163|         valnum = m163_15, r163_14
+#  163|     r163_16(glval<int>) = VariableAddress[#return] : 
+#  163|         valnum = r163_16, r163_9
+#  163|     v163_17(void)       = ReturnValue              : &:r163_16, m163_15
+#  163|     v163_18(void)       = AliasedUse               : m163_3
+#  163|     v163_19(void)       = ExitFunction             : 
+
+#  165| void test_func_value_numbering(char*, char*)
+#  165|   Block 0
+#  165|     v165_1(void)           = EnterFunction                : 
+#  165|     m165_2(unknown)        = AliasedDefinition            : 
+#  165|         valnum = unique
+#  165|     m165_3(unknown)        = InitializeNonLocal           : 
+#  165|         valnum = unique
+#  165|     m165_4(unknown)        = Chi                          : total:m165_2, partial:m165_3
+#  165|         valnum = unique
+#  165|     r165_5(glval<char *>)  = VariableAddress[dst]         : 
+#  165|         valnum = r165_5, r166_3, r167_3, r171_2, r173_3
+#  165|     m165_6(char *)         = InitializeParameter[dst]     : &:r165_5
+#  165|         valnum = m165_6, r165_7, r166_4, r167_4, r171_3, r173_4
+#  165|     r165_7(char *)         = Load[dst]                    : &:r165_5, m165_6
+#  165|         valnum = m165_6, r165_7, r166_4, r167_4, r171_3, r173_4
+#  165|     m165_8(unknown)        = InitializeIndirection[dst]   : &:r165_7
+#  165|         valnum = unique
+#  165|     r165_9(glval<char *>)  = VariableAddress[src]         : 
+#  165|         valnum = r165_9, r168_3, r169_3, r171_4, r174_3
+#  165|     m165_10(char *)        = InitializeParameter[src]     : &:r165_9
+#  165|         valnum = m165_10, r165_11, r168_4, r169_4, r171_5, r174_4
+#  165|     r165_11(char *)        = Load[src]                    : &:r165_9, m165_10
+#  165|         valnum = m165_10, r165_11, r168_4, r169_4, r171_5, r174_4
+#  165|     m165_12(unknown)       = InitializeIndirection[src]   : &:r165_11
+#  165|         valnum = unique
+#  166|     r166_1(glval<int>)     = VariableAddress[a]           : 
+#  166|         valnum = unique
+#  166|     r166_2(glval<unknown>) = FunctionAddress[strlen]      : 
+#  166|         valnum = unique
+#  166|     r166_3(glval<char *>)  = VariableAddress[dst]         : 
+#  166|         valnum = r165_5, r166_3, r167_3, r171_2, r173_3
+#  166|     r166_4(char *)         = Load[dst]                    : &:r166_3, m165_6
+#  166|         valnum = m165_6, r165_7, r166_4, r167_4, r171_3, r173_4
+#  166|     r166_5(char *)         = Convert                      : r166_4
+#  166|         valnum = r166_5, r167_5, r173_5
+#  166|     r166_6(int)            = Call[strlen]                 : func:r166_2, 0:r166_5
+#  166|         valnum = m166_8, m167_8, r166_6, r167_6
+#  166|     v166_7(void)           = ^BufferReadSideEffect[0]     : &:r166_5, ~m165_8
+#  166|     m166_8(int)            = Store[a]                     : &:r166_1, r166_6
+#  166|         valnum = m166_8, m167_8, r166_6, r167_6
+#  167|     r167_1(glval<int>)     = VariableAddress[b]           : 
+#  167|         valnum = unique
+#  167|     r167_2(glval<unknown>) = FunctionAddress[strlen]      : 
+#  167|         valnum = unique
+#  167|     r167_3(glval<char *>)  = VariableAddress[dst]         : 
+#  167|         valnum = r165_5, r166_3, r167_3, r171_2, r173_3
+#  167|     r167_4(char *)         = Load[dst]                    : &:r167_3, m165_6
+#  167|         valnum = m165_6, r165_7, r166_4, r167_4, r171_3, r173_4
+#  167|     r167_5(char *)         = Convert                      : r167_4
+#  167|         valnum = r166_5, r167_5, r173_5
+#  167|     r167_6(int)            = Call[strlen]                 : func:r167_2, 0:r167_5
+#  167|         valnum = m166_8, m167_8, r166_6, r167_6
+#  167|     v167_7(void)           = ^BufferReadSideEffect[0]     : &:r167_5, ~m165_8
+#  167|     m167_8(int)            = Store[b]                     : &:r167_1, r167_6
+#  167|         valnum = m166_8, m167_8, r166_6, r167_6
+#  168|     r168_1(glval<int>)     = VariableAddress[c]           : 
+#  168|         valnum = unique
+#  168|     r168_2(glval<unknown>) = FunctionAddress[strlen]      : 
+#  168|         valnum = unique
+#  168|     r168_3(glval<char *>)  = VariableAddress[src]         : 
+#  168|         valnum = r165_9, r168_3, r169_3, r171_4, r174_3
+#  168|     r168_4(char *)         = Load[src]                    : &:r168_3, m165_10
+#  168|         valnum = m165_10, r165_11, r168_4, r169_4, r171_5, r174_4
+#  168|     r168_5(char *)         = Convert                      : r168_4
+#  168|         valnum = r168_5, r169_5, r171_6, r174_5
+#  168|     r168_6(int)            = Call[strlen]                 : func:r168_2, 0:r168_5
+#  168|         valnum = m168_8, m169_8, m174_8, r168_6, r169_6, r174_6
+#  168|     v168_7(void)           = ^BufferReadSideEffect[0]     : &:r168_5, ~m165_12
+#  168|     m168_8(int)            = Store[c]                     : &:r168_1, r168_6
+#  168|         valnum = m168_8, m169_8, m174_8, r168_6, r169_6, r174_6
+#  169|     r169_1(glval<int>)     = VariableAddress[d]           : 
+#  169|         valnum = unique
+#  169|     r169_2(glval<unknown>) = FunctionAddress[strlen]      : 
+#  169|         valnum = unique
+#  169|     r169_3(glval<char *>)  = VariableAddress[src]         : 
+#  169|         valnum = r165_9, r168_3, r169_3, r171_4, r174_3
+#  169|     r169_4(char *)         = Load[src]                    : &:r169_3, m165_10
+#  169|         valnum = m165_10, r165_11, r168_4, r169_4, r171_5, r174_4
+#  169|     r169_5(char *)         = Convert                      : r169_4
+#  169|         valnum = r168_5, r169_5, r171_6, r174_5
+#  169|     r169_6(int)            = Call[strlen]                 : func:r169_2, 0:r169_5
+#  169|         valnum = m168_8, m169_8, m174_8, r168_6, r169_6, r174_6
+#  169|     v169_7(void)           = ^BufferReadSideEffect[0]     : &:r169_5, ~m165_12
+#  169|     m169_8(int)            = Store[d]                     : &:r169_1, r169_6
+#  169|         valnum = m168_8, m169_8, m174_8, r168_6, r169_6, r174_6
+#  171|     r171_1(glval<unknown>) = FunctionAddress[strcat]      : 
+#  171|         valnum = unique
+#  171|     r171_2(glval<char *>)  = VariableAddress[dst]         : 
+#  171|         valnum = r165_5, r166_3, r167_3, r171_2, r173_3
+#  171|     r171_3(char *)         = Load[dst]                    : &:r171_2, m165_6
+#  171|         valnum = m165_6, r165_7, r166_4, r167_4, r171_3, r173_4
+#  171|     r171_4(glval<char *>)  = VariableAddress[src]         : 
+#  171|         valnum = r165_9, r168_3, r169_3, r171_4, r174_3
+#  171|     r171_5(char *)         = Load[src]                    : &:r171_4, m165_10
+#  171|         valnum = m165_10, r165_11, r168_4, r169_4, r171_5, r174_4
+#  171|     r171_6(char *)         = Convert                      : r171_5
+#  171|         valnum = r168_5, r169_5, r171_6, r174_5
+#  171|     r171_7(char *)         = Call[strcat]                 : func:r171_1, 0:r171_3, 1:r171_6
+#  171|         valnum = unique
+#  171|     v171_8(void)           = ^BufferReadSideEffect[0]     : &:r171_3, ~m165_8
+#  171|     v171_9(void)           = ^BufferReadSideEffect[1]     : &:r171_6, ~m165_12
+#  171|     m171_10(unknown)       = ^BufferMayWriteSideEffect[0] : &:r171_3
+#  171|         valnum = unique
+#  171|     m171_11(unknown)       = Chi                          : total:m165_8, partial:m171_10
+#  171|         valnum = unique
+#  173|     r173_1(glval<int>)     = VariableAddress[e]           : 
+#  173|         valnum = unique
+#  173|     r173_2(glval<unknown>) = FunctionAddress[strlen]      : 
+#  173|         valnum = unique
+#  173|     r173_3(glval<char *>)  = VariableAddress[dst]         : 
+#  173|         valnum = r165_5, r166_3, r167_3, r171_2, r173_3
+#  173|     r173_4(char *)         = Load[dst]                    : &:r173_3, m165_6
+#  173|         valnum = m165_6, r165_7, r166_4, r167_4, r171_3, r173_4
+#  173|     r173_5(char *)         = Convert                      : r173_4
+#  173|         valnum = r166_5, r167_5, r173_5
+#  173|     r173_6(int)            = Call[strlen]                 : func:r173_2, 0:r173_5
+#  173|         valnum = m173_8, r173_6
+#  173|     v173_7(void)           = ^BufferReadSideEffect[0]     : &:r173_5, ~m171_11
+#  173|     m173_8(int)            = Store[e]                     : &:r173_1, r173_6
+#  173|         valnum = m173_8, r173_6
+#  174|     r174_1(glval<int>)     = VariableAddress[f]           : 
+#  174|         valnum = unique
+#  174|     r174_2(glval<unknown>) = FunctionAddress[strlen]      : 
+#  174|         valnum = unique
+#  174|     r174_3(glval<char *>)  = VariableAddress[src]         : 
+#  174|         valnum = r165_9, r168_3, r169_3, r171_4, r174_3
+#  174|     r174_4(char *)         = Load[src]                    : &:r174_3, m165_10
+#  174|         valnum = m165_10, r165_11, r168_4, r169_4, r171_5, r174_4
+#  174|     r174_5(char *)         = Convert                      : r174_4
+#  174|         valnum = r168_5, r169_5, r171_6, r174_5
+#  174|     r174_6(int)            = Call[strlen]                 : func:r174_2, 0:r174_5
+#  174|         valnum = m168_8, m169_8, m174_8, r168_6, r169_6, r174_6
+#  174|     v174_7(void)           = ^BufferReadSideEffect[0]     : &:r174_5, ~m165_12
+#  174|     m174_8(int)            = Store[f]                     : &:r174_1, r174_6
+#  174|         valnum = m168_8, m169_8, m174_8, r168_6, r169_6, r174_6
+#  176|     r176_1(glval<unknown>) = FunctionAddress[add]         : 
+#  176|         valnum = unique
+#  176|     r176_2(int)            = Constant[1]                  : 
+#  176|         valnum = r176_2, r178_2
+#  176|     r176_3(int)            = Constant[2]                  : 
+#  176|         valnum = r176_3, r178_3
+#  176|     r176_4(int)            = Call[add]                    : func:r176_1, 0:r176_2, 1:r176_3
+#  176|         valnum = unique
+#  177|     r177_1(glval<unknown>) = FunctionAddress[add]         : 
+#  177|         valnum = unique
+#  177|     r177_2(int)            = Constant[3]                  : 
+#  177|         valnum = unique
+#  177|     r177_3(int)            = Constant[4]                  : 
+#  177|         valnum = unique
+#  177|     r177_4(int)            = Call[add]                    : func:r177_1, 0:r177_2, 1:r177_3
+#  177|         valnum = unique
+#  178|     r178_1(glval<unknown>) = FunctionAddress[add]         : 
+#  178|         valnum = unique
+#  178|     r178_2(int)            = Constant[1]                  : 
+#  178|         valnum = r176_2, r178_2
+#  178|     r178_3(int)            = Constant[2]                  : 
+#  178|         valnum = r176_3, r178_3
+#  178|     r178_4(int)            = Call[add]                    : func:r178_1, 0:r178_2, 1:r178_3
+#  178|         valnum = unique
+#  179|     v179_1(void)           = NoOp                         : 
+#  165|     v165_13(void)          = ReturnIndirection[dst]       : &:r165_7, m171_11
+#  165|     v165_14(void)          = ReturnIndirection[src]       : &:r165_11, m165_12
+#  165|     v165_15(void)          = ReturnVoid                   : 
+#  165|     v165_16(void)          = AliasedUse                   : m165_3
+#  165|     v165_17(void)          = ExitFunction                 : 

cpp/ql/test/library-tests/valuenumbering/GlobalValueNumbering/test.cpp

@@ -156,4 +156,24 @@ void test_read_global_different(int n) {
   global_a->y = n;
 
   int d = global_a->x;
+}
+
+int strlen(const char *str);
+char *strcat(char *dst, const char *src);
+int add(int a, int b) { return a+b; }
+
+void test_func_value_numbering(char *dst, char *src) {
+  int a = strlen(dst);
+  int b = strlen(dst); // same as previous line
+  int c = strlen(src);
+  int d = strlen(src); // same as previous line
+
+  strcat(dst, src);
+
+  int e = strlen(dst); // different from a and b
+  int f = strlen(src); // same as c and d
+
+  add(1, 2);
+  add(3, 4);
+  add(1, 2); // same as two lines earlier
 }

csharp/ql/src/experimental/ir/implementation/internal/AliasedSSAStub.qll

@@ -17,3 +17,5 @@ module SSA {
 
   predicate hasUnreachedInstruction(IRFunctionBase irFunc) { none() }
 }
+
+predicate removedInstruction(TRawInstruction instr) { none() }

csharp/ql/src/experimental/ir/implementation/internal/TInstruction.qll

@@ -34,6 +34,7 @@ newtype TInstruction =
     AliasedSsa::SSA::hasPhiInstruction(blockStartInstr, memoryLocation)
   } or
   TAliasedSsaChiInstruction(TRawInstruction primaryInstruction) {
+    not AliasedSsa::removedInstruction(primaryInstruction) and
     AliasedSsa::SSA::hasChiInstruction(primaryInstruction)
   } or
   TAliasedSsaUnreachedInstruction(IRFunctionBase irFunc) {

csharp/ql/src/experimental/ir/implementation/raw/Instruction.qll

@@ -1712,6 +1712,11 @@ class SideEffectInstruction extends Instruction {
  */
 class CallSideEffectInstruction extends SideEffectInstruction {
   CallSideEffectInstruction() { this.getOpcode() instanceof Opcode::CallSideEffect }
+
+  /** Gets the operand for the value that will be read by this instruction */
+  final SideEffectOperand getSideEffectOperand() { result = this.getAnOperand() }
+
+  final Instruction getSideEffect() { result = this.getAnOperand().getDef() }
 }
 
 /**
@@ -1723,6 +1728,11 @@ class CallSideEffectInstruction extends SideEffectInstruction {
  */
 class CallReadSideEffectInstruction extends SideEffectInstruction {
   CallReadSideEffectInstruction() { this.getOpcode() instanceof Opcode::CallReadSideEffect }
+
+  /** Gets the operand for the value that will be read by this instruction */
+  final SideEffectOperand getSideEffectOperand() { result = this.getAnOperand() }
+
+  final Instruction getSideEffect() { result = this.getAnOperand().getDef() }
 }
 
 /**

csharp/ql/src/experimental/ir/implementation/raw/gvn/internal/ValueNumberingImports.qll

@@ -1,3 +1,4 @@
 import experimental.ir.internal.Overlap
 import experimental.ir.internal.IRCSharpLanguage as Language
 import experimental.ir.implementation.unaliased_ssa.IR
+import experimental.ir.interfaces.SideEffect as SideEffect

csharp/ql/src/experimental/ir/implementation/raw/gvn/internal/ValueNumberingInternal.qll

@@ -41,8 +41,92 @@ newtype TValueNumber =
   ) {
     loadTotalOverlapValueNumber(_, irFunc, type, memOperand, operand)
   } or
+  TCallValueNumber(TCallPartialValueNumber vn) { callValueNumber(_, _, vn) } or
   TUniqueValueNumber(IRFunction irFunc, Instruction instr) { uniqueValueNumber(instr, irFunc) }
 
+private class NumberableCallInstruction extends CallInstruction {
+  NumberableCallInstruction() {
+    not this.getResultIRType() instanceof IRVoidType and
+    exists(SideEffect::SideEffectFunction sideEffectFunc |
+      sideEffectFunc = this.getStaticCallTarget()
+    |
+      sideEffectFunc.hasOnlySpecificReadSideEffects() and
+      sideEffectFunc.hasOnlySpecificWriteSideEffects()
+    )
+  }
+}
+
+private newtype TCallPartialValueNumber =
+  TNilArgument() or
+  TArgument(TCallPartialValueNumber head, TValueNumber arg) {
+    exists(NumberableCallInstruction call, int index |
+      callArgValueNumber(call, index, arg) and
+      callPartialValueNumber(call, index, head)
+    )
+  }
+
+private predicate callValueNumber(
+  NumberableCallInstruction call, int index, TCallPartialValueNumber vn
+) {
+  index = max(int n | callArgRank(call, n, _) | n) and
+  exists(TCallPartialValueNumber head, TValueNumber arg |
+    callPartialValueNumber(call, index, pragma[only_bind_out](head)) and
+    callArgValueNumber(call, index, pragma[only_bind_into](arg)) and
+    vn = TArgument(head, arg)
+  )
+  or
+  not exists(int n | callArgRank(call, n, _)) and
+  index = -1 and
+  vn = TNilArgument()
+}
+
+private predicate callPartialValueNumber(
+  NumberableCallInstruction call, int index, TCallPartialValueNumber head
+) {
+  exists(call) and
+  index = 1 and
+  head = TNilArgument()
+  or
+  exists(TCallPartialValueNumber prev, TValueNumber prevVN |
+    callPartialValueNumber(call, index - 1, pragma[only_bind_out](prev)) and
+    callArgValueNumber(call, index - 1, pragma[only_bind_into](prevVN)) and
+    head = TArgument(prev, prevVN)
+  )
+}
+
+/**
+ */
+private predicate callArgValueNumber(NumberableCallInstruction call, int index, TValueNumber arg) {
+  exists(Instruction instr |
+    callArgRank(call, index, instr) and
+    arg = tvalueNumber(instr)
+  )
+}
+
+/**
+ * Holds if `arg` is the `index`th element in `call`'s extended argument list, including the `this`
+ * argument and side-effect reads.
+ */
+private predicate callArgRank(NumberableCallInstruction call, int index, Instruction arg) {
+  arg =
+    rank[index](int argIndex, boolean isEffect, Instruction instr |
+      // There is no need to include the call's read and write side effects on
+      // all-aliased-memory as `NumberableCallInstruction`s do not read or write
+      // to all-aliased-memory.
+      instr = call.getArgument(argIndex) and
+      isEffect = false
+      or
+      exists(ReadSideEffectInstruction read |
+        read.getPrimaryInstruction() = call and
+        read.getSideEffectOperand().getAnyDef() = instr and
+        read.getIndex() = argIndex and
+        isEffect = true
+      )
+    |
+      instr order by argIndex, isEffect
+    )
+}
+
 /**
  * A `CopyInstruction` whose source operand's value is congruent to the definition of that source
  * operand.
@@ -93,6 +177,8 @@ private predicate numberableInstruction(Instruction instr) {
   instr instanceof CongruentCopyInstruction
   or
   instr instanceof LoadTotalOverlapInstruction
+  or
+  instr instanceof NumberableCallInstruction
 }
 
 private predicate filteredNumberableInstruction(Instruction instr) {
@@ -309,6 +395,11 @@ private TValueNumber nonUniqueValueNumber(Instruction instr) {
       or
       // The value number of a copy is just the value number of its source value.
       result = tvalueNumber(instr.(CongruentCopyInstruction).getSourceValue())
+      or
+      exists(TCallPartialValueNumber pvn |
+        callValueNumber(instr, _, pvn) and
+        result = TCallValueNumber(pvn)
+      )
     )
   )
 }

csharp/ql/src/experimental/ir/implementation/unaliased_ssa/Instruction.qll

@@ -1712,6 +1712,11 @@ class SideEffectInstruction extends Instruction {
  */
 class CallSideEffectInstruction extends SideEffectInstruction {
   CallSideEffectInstruction() { this.getOpcode() instanceof Opcode::CallSideEffect }
+
+  /** Gets the operand for the value that will be read by this instruction */
+  final SideEffectOperand getSideEffectOperand() { result = this.getAnOperand() }
+
+  final Instruction getSideEffect() { result = this.getAnOperand().getDef() }
 }
 
 /**
@@ -1723,6 +1728,11 @@ class CallSideEffectInstruction extends SideEffectInstruction {
  */
 class CallReadSideEffectInstruction extends SideEffectInstruction {
   CallReadSideEffectInstruction() { this.getOpcode() instanceof Opcode::CallReadSideEffect }
+
+  /** Gets the operand for the value that will be read by this instruction */
+  final SideEffectOperand getSideEffectOperand() { result = this.getAnOperand() }
+
+  final Instruction getSideEffect() { result = this.getAnOperand().getDef() }
 }
 
 /**

csharp/ql/src/experimental/ir/implementation/unaliased_ssa/gvn/internal/ValueNumberingImports.qll

@@ -1,3 +1,4 @@
 import experimental.ir.internal.Overlap
 import experimental.ir.internal.IRCSharpLanguage as Language
 import experimental.ir.implementation.unaliased_ssa.IR
+import experimental.ir.interfaces.SideEffect as SideEffect

csharp/ql/src/experimental/ir/implementation/unaliased_ssa/gvn/internal/ValueNumberingInternal.qll

@@ -41,8 +41,92 @@ newtype TValueNumber =
   ) {
     loadTotalOverlapValueNumber(_, irFunc, type, memOperand, operand)
   } or
+  TCallValueNumber(TCallPartialValueNumber vn) { callValueNumber(_, _, vn) } or
   TUniqueValueNumber(IRFunction irFunc, Instruction instr) { uniqueValueNumber(instr, irFunc) }
 
+private class NumberableCallInstruction extends CallInstruction {
+  NumberableCallInstruction() {
+    not this.getResultIRType() instanceof IRVoidType and
+    exists(SideEffect::SideEffectFunction sideEffectFunc |
+      sideEffectFunc = this.getStaticCallTarget()
+    |
+      sideEffectFunc.hasOnlySpecificReadSideEffects() and
+      sideEffectFunc.hasOnlySpecificWriteSideEffects()
+    )
+  }
+}
+
+private newtype TCallPartialValueNumber =
+  TNilArgument() or
+  TArgument(TCallPartialValueNumber head, TValueNumber arg) {
+    exists(NumberableCallInstruction call, int index |
+      callArgValueNumber(call, index, arg) and
+      callPartialValueNumber(call, index, head)
+    )
+  }
+
+private predicate callValueNumber(
+  NumberableCallInstruction call, int index, TCallPartialValueNumber vn
+) {
+  index = max(int n | callArgRank(call, n, _) | n) and
+  exists(TCallPartialValueNumber head, TValueNumber arg |
+    callPartialValueNumber(call, index, pragma[only_bind_out](head)) and
+    callArgValueNumber(call, index, pragma[only_bind_into](arg)) and
+    vn = TArgument(head, arg)
+  )
+  or
+  not exists(int n | callArgRank(call, n, _)) and
+  index = -1 and
+  vn = TNilArgument()
+}
+
+private predicate callPartialValueNumber(
+  NumberableCallInstruction call, int index, TCallPartialValueNumber head
+) {
+  exists(call) and
+  index = 1 and
+  head = TNilArgument()
+  or
+  exists(TCallPartialValueNumber prev, TValueNumber prevVN |
+    callPartialValueNumber(call, index - 1, pragma[only_bind_out](prev)) and
+    callArgValueNumber(call, index - 1, pragma[only_bind_into](prevVN)) and
+    head = TArgument(prev, prevVN)
+  )
+}
+
+/**
+ */
+private predicate callArgValueNumber(NumberableCallInstruction call, int index, TValueNumber arg) {
+  exists(Instruction instr |
+    callArgRank(call, index, instr) and
+    arg = tvalueNumber(instr)
+  )
+}
+
+/**
+ * Holds if `arg` is the `index`th element in `call`'s extended argument list, including the `this`
+ * argument and side-effect reads.
+ */
+private predicate callArgRank(NumberableCallInstruction call, int index, Instruction arg) {
+  arg =
+    rank[index](int argIndex, boolean isEffect, Instruction instr |
+      // There is no need to include the call's read and write side effects on
+      // all-aliased-memory as `NumberableCallInstruction`s do not read or write
+      // to all-aliased-memory.
+      instr = call.getArgument(argIndex) and
+      isEffect = false
+      or
+      exists(ReadSideEffectInstruction read |
+        read.getPrimaryInstruction() = call and
+        read.getSideEffectOperand().getAnyDef() = instr and
+        read.getIndex() = argIndex and
+        isEffect = true
+      )
+    |
+      instr order by argIndex, isEffect
+    )
+}
+
 /**
  * A `CopyInstruction` whose source operand's value is congruent to the definition of that source
  * operand.
@@ -93,6 +177,8 @@ private predicate numberableInstruction(Instruction instr) {
   instr instanceof CongruentCopyInstruction
   or
   instr instanceof LoadTotalOverlapInstruction
+  or
+  instr instanceof NumberableCallInstruction
 }
 
 private predicate filteredNumberableInstruction(Instruction instr) {
@@ -309,6 +395,11 @@ private TValueNumber nonUniqueValueNumber(Instruction instr) {
       or
       // The value number of a copy is just the value number of its source value.
       result = tvalueNumber(instr.(CongruentCopyInstruction).getSourceValue())
+      or
+      exists(TCallPartialValueNumber pvn |
+        callValueNumber(instr, _, pvn) and
+        result = TCallValueNumber(pvn)
+      )
     )
   )
 }

csharp/ql/src/experimental/ir/implementation/unaliased_ssa/internal/SSAConstruction.qll

@@ -8,11 +8,6 @@ private import Imports::RawIR as RawIR
 private import SsaInstructions
 private import SsaOperands
 private import NewIR
-
-private class OldBlock = Reachability::ReachableBlock;
-
-private class OldInstruction = Reachability::ReachableInstruction;
-
 import Cached
 
 cached
@@ -58,7 +53,9 @@ private module Cached {
 
   cached
   predicate hasInstruction(TStageInstruction instr) {
-    instr instanceof TRawInstruction and instr instanceof OldInstruction
+    instr instanceof TRawInstruction and
+    instr instanceof OldInstruction and
+    not removedInstruction(instr)
     or
     instr = phiInstruction(_, _)
     or
@@ -382,7 +379,14 @@ private module Cached {
         (
           if Reachability::isInfeasibleInstructionSuccessor(oldInstruction, kind)
           then result = unreachedInstruction(instruction.getEnclosingIRFunction())
-          else result = getNewInstruction(oldInstruction.getSuccessor(kind))
+          else
+            if removedInstruction(oldInstruction.getSuccessor(kind))
+            then
+              // the only removed nodes are side-effect writes, but those may have Chi nodes
+              // skip to the following instruction in the old IR, which won't be removed
+              // if we start skipping specific side effects, this may no longer hold
+              result = getNewInstruction(oldInstruction.getSuccessor(kind).getSuccessor(kind))
+            else result = getNewInstruction(oldInstruction.getSuccessor(kind))
         )
       )
       or

csharp/ql/src/experimental/ir/implementation/unaliased_ssa/internal/SSAConstructionInternal.qll

@@ -14,3 +14,9 @@ import experimental.ir.implementation.internal.TOperand::UnaliasedSsaOperands as
 
 /** DEPRECATED: Alias for SsaOperands */
 deprecated module SSAOperands = SsaOperands;
+
+predicate removedInstruction(Reachability::ReachableInstruction instr) { none() }
+
+class OldBlock = Reachability::ReachableBlock;
+
+class OldInstruction = Reachability::ReachableInstruction;

csharp/ql/src/experimental/ir/interfaces/SideEffect.qll

@@ -0,0 +1,24 @@
+private import csharp as CSharp
+
+/**
+ * A class that models the side effects of a library function.
+ */
+abstract class SideEffectFunction extends CSharp::Callable {
+  /**
+   * Holds if the function never reads from memory that was defined before entry to the function.
+   * This memory could be from global variables, or from other memory that was reachable from a
+   * pointer that was passed into the function. Input side-effects, and reads from memory that
+   * cannot be visible to the caller (for example a buffer inside an I/O library) are not modeled
+   * here.
+   */
+  abstract predicate hasOnlySpecificReadSideEffects();
+
+  /**
+   * Holds if the function never writes to memory that remains allocated after the function
+   * returns. This memory could be from global variables, or from other memory that was reachable
+   * from a pointer that was passed into the function. Output side-effects, and writes to memory
+   * that cannot be visible to the caller (for example a buffer inside an I/O library) are not
+   * modeled here.
+   */
+  abstract predicate hasOnlySpecificWriteSideEffects();
+}