/*
 * Copyright (c) 2002 - 2006 IBM Corporation.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 */
package com.ibm.wala.ipa.callgraph.propagation;

import com.ibm.wala.analysis.reflection.CloneInterpreter;
import com.ibm.wala.cfg.ControlFlowGraph;
import com.ibm.wala.cfg.IBasicBlock;
import com.ibm.wala.classLoader.ArrayClass;
import com.ibm.wala.classLoader.CallSiteReference;
import com.ibm.wala.classLoader.IClass;
import com.ibm.wala.classLoader.IField;
import com.ibm.wala.classLoader.IMethod;
import com.ibm.wala.classLoader.NewSiteReference;
import com.ibm.wala.classLoader.ProgramCounter;
import com.ibm.wala.fixpoint.AbstractOperator;
import com.ibm.wala.ipa.callgraph.AnalysisOptions;
import com.ibm.wala.ipa.callgraph.CGNode;
import com.ibm.wala.ipa.callgraph.ContextKey;
import com.ibm.wala.ipa.callgraph.ContextSelector;
import com.ibm.wala.ipa.callgraph.Entrypoint;
import com.ibm.wala.ipa.callgraph.IAnalysisCacheView;
import com.ibm.wala.ipa.callgraph.impl.AbstractRootMethod;
import com.ibm.wala.ipa.callgraph.impl.DefaultEntrypoint;
import com.ibm.wala.ipa.callgraph.impl.ExplicitCallGraph;
import com.ibm.wala.ipa.cha.IClassHierarchy;
import com.ibm.wala.shrikeBT.ConditionalBranchInstruction;
import com.ibm.wala.shrikeBT.IInvokeInstruction;
import com.ibm.wala.ssa.DefUse;
import com.ibm.wala.ssa.IRView;
import com.ibm.wala.ssa.ISSABasicBlock;
import com.ibm.wala.ssa.SSAAbstractInvokeInstruction;
import com.ibm.wala.ssa.SSAAbstractThrowInstruction;
import com.ibm.wala.ssa.SSAArrayLoadInstruction;
import com.ibm.wala.ssa.SSAArrayStoreInstruction;
import com.ibm.wala.ssa.SSACFG;
import com.ibm.wala.ssa.SSACFG.BasicBlock;
import com.ibm.wala.ssa.SSACFG.ExceptionHandlerBasicBlock;
import com.ibm.wala.ssa.SSACheckCastInstruction;
import com.ibm.wala.ssa.SSAConditionalBranchInstruction;
import com.ibm.wala.ssa.SSAGetCaughtExceptionInstruction;
import com.ibm.wala.ssa.SSAGetInstruction;
import com.ibm.wala.ssa.SSAInstanceofInstruction;
import com.ibm.wala.ssa.SSAInstruction;
import com.ibm.wala.ssa.SSAInvokeInstruction;
import com.ibm.wala.ssa.SSALoadMetadataInstruction;
import com.ibm.wala.ssa.SSANewInstruction;
import com.ibm.wala.ssa.SSAPhiInstruction;
import com.ibm.wala.ssa.SSAPiInstruction;
import com.ibm.wala.ssa.SSAPutInstruction;
import com.ibm.wala.ssa.SSAReturnInstruction;
import com.ibm.wala.ssa.SSAThrowInstruction;
import com.ibm.wala.ssa.SymbolTable;
import com.ibm.wala.types.FieldReference;
import com.ibm.wala.types.MethodReference;
import com.ibm.wala.types.Selector;
import com.ibm.wala.types.TypeReference;
import com.ibm.wala.util.CancelException;
import com.ibm.wala.util.MonitorUtil;
import com.ibm.wala.util.MonitorUtil.IProgressMonitor;
import com.ibm.wala.util.collections.HashSetFactory;
import com.ibm.wala.util.collections.Iterator2Iterable;
import com.ibm.wala.util.debug.Assertions;
import com.ibm.wala.util.debug.UnimplementedError;
import com.ibm.wala.util.intset.IntIterator;
import com.ibm.wala.util.intset.IntSet;
import com.ibm.wala.util.intset.IntSetAction;
import com.ibm.wala.util.intset.IntSetUtil;
import com.ibm.wala.util.intset.MutableIntSet;
import com.ibm.wala.util.ref.ReferenceCleanser;
import com.ibm.wala.util.warnings.Warning;
import com.ibm.wala.util.warnings.Warnings;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.function.Consumer;

/**
 * This abstract base class provides the general algorithm for a call graph builder that relies on
 * propagation through an iterative dataflow solver, and constraints generated by statements in SSA
 * form.
 *
 * <p>TODO: This implementation currently keeps all points to sets live ... even those for local
 * variables that do not span interprocedural boundaries. This may be too space-inefficient .. we
 * can consider recomputing local sets on demand.
 */
public abstract class SSAPropagationCallGraphBuilder extends PropagationCallGraphBuilder
    implements HeapModel {
  private static final boolean DEBUG = false;

  private static final boolean DEBUG_MULTINEWARRAY = DEBUG | false;

  /** Should we periodically clear out soft reference caches in an attempt to help the GC? */
  public static final boolean PERIODIC_WIPE_SOFT_CACHES = true;

  /** Interval which defines the period to clear soft reference caches */
  public static final int WIPE_SOFT_CACHE_INTERVAL = 2500;

  /** Counter for wiping soft caches */
  private static int wipeCount = 0;

  // /** use type inference to avoid unnecessary filter constraints? */
  // private final static boolean OPTIMIZE_WITH_TYPE_INFERENCE = true;
  /**
   * An optimization: if we can locally determine the final solution for a points-to set, then don't
   * actually create the points-to set, but instead short circuit by propagating the final solution
   * to all such uses.
   *
   * <p>String constants are ALWAYS considered invariant, regardless of the value of this flag.
   *
   * <p>However, if this flag is set, then the solver is more aggressive identifying invariants.
   *
   * <p>Doesn't play well with pre-transitive solver; turning off for now.
   */
  private static final boolean SHORT_CIRCUIT_INVARIANT_SETS = true;

  /**
   * An optimization: if we can locally determine that a particular pointer p has exactly one use,
   * then we don't actually create the points-to-set for p, but instead short-circuit by propagating
   * the final solution to the unique use.
   *
   * <p>Doesn't play well with pre-transitive solver; turning off for now.
   */
  protected static final boolean SHORT_CIRCUIT_SINGLE_USES = false;

  /** Should we change calls to clone() to assignments? */
  private final boolean clone2Assign = false;

  /** Cache for efficiency */
  private static final Selector cloneSelector = CloneInterpreter.CLONE.getSelector();

  /** set of class whose clinits have already been processed */
  private final Set<IClass> clinitVisited = HashSetFactory.make();

  private final Set<IClass> finalizeVisited = HashSetFactory.make();

  public IProgressMonitor monitor;

  protected SSAPropagationCallGraphBuilder(
      IMethod abstractRootMethod,
      AnalysisOptions options,
      IAnalysisCacheView cache,
      PointerKeyFactory pointerKeyFactory) {
    super(abstractRootMethod, options, cache, pointerKeyFactory);
    // this.usePreTransitiveSolver = options.usePreTransitiveSolver();
  }

  public SSAContextInterpreter getCFAContextInterpreter() {
    return (SSAContextInterpreter) getContextInterpreter();
  }

  /**
   * @return the instance key that represents the exception of type _type_ thrown by a particular
   *     PEI.
   * @throws IllegalArgumentException if ikFactory is null
   */
  public static InstanceKey getInstanceKeyForPEI(
      CGNode node, ProgramCounter x, TypeReference type, InstanceKeyFactory ikFactory) {
    if (ikFactory == null) {
      throw new IllegalArgumentException("ikFactory is null");
    }
    return ikFactory.getInstanceKeyForPEI(node, x, type);
  }

  /**
   * Visit all instructions in a node, and add dataflow constraints induced by each statement in the
   * SSA form.
   */
  @Override
  protected boolean addConstraintsFromNode(CGNode node, IProgressMonitor monitor)
      throws CancelException {
    this.monitor = monitor;
    if (haveAlreadyVisited(node)) {
      return false;
    } else {
      markAlreadyVisited(node);
    }
    return unconditionallyAddConstraintsFromNode(node, monitor);
  }

  @Override
  protected boolean unconditionallyAddConstraintsFromNode(CGNode node, IProgressMonitor monitor)
      throws CancelException {
    this.monitor = monitor;
    if (PERIODIC_WIPE_SOFT_CACHES) {
      wipeCount++;
      if (wipeCount >= WIPE_SOFT_CACHE_INTERVAL) {
        wipeCount = 0;
        ReferenceCleanser.clearSoftCaches();
      }
    }

    if (DEBUG) {
      System.err.println("\n\nAdd constraints from node " + node);
    }
    IRView ir = getCFAContextInterpreter().getIRView(node);
    if (DEBUG) {
      if (ir == null) {
        System.err.println("\n   No statements\n");
      } else {
        try {
          System.err.println(ir.toString());
        } catch (Error e) {
          e.printStackTrace();
        }
      }
    }

    if (ir == null) {
      return false;
    }

    addNodeInstructionConstraints(node, monitor);

    addNodeValueConstraints(node, monitor);

    DefUse du = getCFAContextInterpreter().getDU(node);
    addNodePassthruExceptionConstraints(node, ir, du);
    // conservatively assume something changed
    return true;
  }

  /** @return a visitor to examine instructions in the ir */
  protected ConstraintVisitor makeVisitor(CGNode node) {
    return new ConstraintVisitor(this, node);
  }

  /** Add pointer flow constraints based on instructions in a given node */
  protected void addNodeInstructionConstraints(CGNode node, IProgressMonitor monitor)
      throws CancelException {
    this.monitor = monitor;
    ConstraintVisitor v = makeVisitor(node);

    IRView ir = v.ir;
    for (ISSABasicBlock sbb : Iterator2Iterable.make(ir.getBlocks())) {
      BasicBlock b = (BasicBlock) sbb;
      addBlockInstructionConstraints(node, ir, b, v, monitor);
      if (wasChanged(node)) {
        return;
      }
    }
  }

  /** Hook for aubclasses to add pointer flow constraints based on values in a given node */
  @SuppressWarnings("unused")
  protected void addNodeValueConstraints(CGNode node, IProgressMonitor monitor)
      throws CancelException {}

  /** Add constraints for a particular basic block. */
  protected void addBlockInstructionConstraints(
      CGNode node, IRView ir, BasicBlock b, ConstraintVisitor v, IProgressMonitor monitor)
      throws CancelException {
    this.monitor = monitor;
    v.setBasicBlock(b);

    // visit each instruction in the basic block.
    for (SSAInstruction s : b) {
      MonitorUtil.throwExceptionIfCanceled(monitor);
      if (s != null) {
        s.visit(v);
        if (wasChanged(node)) {
          return;
        }
      }
    }

    addPhiConstraints(node, ir.getControlFlowGraph(), b, v);
  }

  private void addPhiConstraints(
      CGNode node,
      ControlFlowGraph<SSAInstruction, ISSABasicBlock> controlFlowGraph,
      BasicBlock b,
      ConstraintVisitor v) {
    // visit each phi instruction in each successor block
    for (ISSABasicBlock isb : Iterator2Iterable.make(controlFlowGraph.getSuccNodes(b))) {
      BasicBlock sb = (BasicBlock) isb;
      if (!sb.hasPhi()) {
        continue;
      }
      int n = 0;
      for (IBasicBlock<?> back : Iterator2Iterable.make(controlFlowGraph.getPredNodes(sb))) {
        if (back == b) {
          break;
        }
        ++n;
      }
      assert n < controlFlowGraph.getPredNodeCount(sb);
      for (SSAInstruction inst : Iterator2Iterable.make(sb.iteratePhis())) {
        SSAPhiInstruction phi = (SSAPhiInstruction) inst;
        if (phi == null) {
          continue;
        }
        PointerKey def = getPointerKeyForLocal(node, phi.getDef());
        if (hasNoInterestingUses(node, phi.getDef(), v.du)) {
          system.recordImplicitPointsToSet(def);
        } else {
          // the following test restricts the constraints to reachable
          // paths, according to verification constraints
          if (phi.getUse(n) > 0) {
            PointerKey use = getPointerKeyForLocal(node, phi.getUse(n));
            if (contentsAreInvariant(v.symbolTable, v.du, phi.getUse(n))) {
              system.recordImplicitPointsToSet(use);
              InstanceKey[] ik =
                  getInvariantContents(v.symbolTable, v.du, node, phi.getUse(n), this);
              for (InstanceKey element : ik) {
                system.newConstraint(def, element);
              }
            } else {
              system.newConstraint(def, assignOperator, use);
            }
          }
        }
      }
    }
  }

  /**
   * Add constraints to represent the flow of exceptions to the exceptional return value for this
   * node
   */
  protected void addNodePassthruExceptionConstraints(CGNode node, IRView ir, DefUse du) {
    // add constraints relating to thrown exceptions that reach the exit block.
    List<ProgramCounter> peis = getIncomingPEIs(ir, ir.getExitBlock());
    PointerKey exception = getPointerKeyForExceptionalReturnValue(node);

    TypeReference throwableType =
        node.getMethod().getDeclaringClass().getClassLoader().getLanguage().getThrowableType();
    IClass c = node.getClassHierarchy().lookupClass(throwableType);
    addExceptionDefConstraints(ir, du, node, peis, exception, Collections.singleton(c));
  }

  /**
   * Generate constraints which assign exception values into an exception pointer
   *
   * @param node governing node
   * @param peis list of PEI instructions
   * @param exceptionVar PointerKey representing a pointer to an exception value
   * @param catchClasses the types "caught" by the exceptionVar
   */
  @SuppressWarnings("unused")
  private void addExceptionDefConstraints(
      IRView ir,
      DefUse du,
      CGNode node,
      List<ProgramCounter> peis,
      PointerKey exceptionVar,
      Set<IClass> catchClasses) {
    if (DEBUG) {
      System.err.println("Add exception def constraints for node " + node);
    }
    for (ProgramCounter peiLoc : peis) {
      if (DEBUG) {
        System.err.println("peiLoc: " + peiLoc);
      }
      SSAInstruction pei = ir.getPEI(peiLoc);

      if (DEBUG) {
        System.err.println("Add exceptions from pei " + pei);
      }

      if (pei instanceof SSAAbstractInvokeInstruction) {
        SSAAbstractInvokeInstruction s = (SSAAbstractInvokeInstruction) pei;
        PointerKey e = getPointerKeyForLocal(node, s.getException());

        if (!SHORT_CIRCUIT_SINGLE_USES || !hasUniqueCatchBlock(s, ir)) {
          addAssignmentsForCatchPointerKey(exceptionVar, catchClasses, e);
        } // else {
        // System.err.println("SKIPPING ASSIGNMENTS TO " + exceptionVar + " FROM " +
        // e);
        // }
      } else if (pei instanceof SSAAbstractThrowInstruction) {
        SSAAbstractThrowInstruction s = (SSAAbstractThrowInstruction) pei;
        PointerKey e = getPointerKeyForLocal(node, s.getException());

        if (contentsAreInvariant(ir.getSymbolTable(), du, s.getException())) {
          InstanceKey[] ik =
              getInvariantContents(ir.getSymbolTable(), du, node, s.getException(), this);
          for (InstanceKey element : ik) {
            system.findOrCreateIndexForInstanceKey(element);
            assignInstanceToCatch(exceptionVar, catchClasses, element);
          }
        } else {
          addAssignmentsForCatchPointerKey(exceptionVar, catchClasses, e);
        }
      }

      // Account for those exceptions for which we do not actually have a
      // points-to set for
      // the pei, but just instance keys
      Collection<TypeReference> types = pei.getExceptionTypes();
      if (types != null) {
        for (TypeReference type : types) {
          if (type != null) {
            InstanceKey ik = getInstanceKeyForPEI(node, peiLoc, type, instanceKeyFactory);
            if (ik == null) {
              continue;
            }
            assert ik instanceof ConcreteTypeKey
                : "uh oh: need to implement getCaughtException constraints for instance " + ik;
            ConcreteTypeKey ck = (ConcreteTypeKey) ik;
            IClass klass = ck.getType();
            if (PropagationCallGraphBuilder.catches(catchClasses, klass, cha)) {
              system.newConstraint(
                  exceptionVar, getInstanceKeyForPEI(node, peiLoc, type, instanceKeyFactory));
            }
          }
        }
      }
    }
  }

  /**
   * @return true iff there's a unique catch block which catches all exceptions thrown by a certain
   *     call site.
   */
  protected static boolean hasUniqueCatchBlock(SSAAbstractInvokeInstruction call, IRView ir) {
    ISSABasicBlock[] bb = ir.getBasicBlocksForCall(call.getCallSite());
    if (bb.length == 1) {
      Iterator<ISSABasicBlock> it =
          ir.getControlFlowGraph().getExceptionalSuccessors(bb[0]).iterator();
      // check that there's exactly one element in the iterator
      if (it.hasNext()) {
        ISSABasicBlock sb = it.next();
        return (!it.hasNext()
            && (sb.isExitBlock()
                || ((sb instanceof ExceptionHandlerBasicBlock)
                    && ((ExceptionHandlerBasicBlock) sb).getCatchInstruction() != null)));
      }
    }
    return false;
  }

  /**
   * precondition: hasUniqueCatchBlock(call,node,cg)
   *
   * @return the unique pointer key which catches the exceptions thrown by a call
   * @throws IllegalArgumentException if ir == null
   * @throws IllegalArgumentException if call == null
   */
  public PointerKey getUniqueCatchKey(SSAAbstractInvokeInstruction call, IRView ir, CGNode node)
      throws IllegalArgumentException, IllegalArgumentException {
    if (call == null) {
      throw new IllegalArgumentException("call == null");
    }
    if (ir == null) {
      throw new IllegalArgumentException("ir == null");
    }
    ISSABasicBlock[] bb = ir.getBasicBlocksForCall(call.getCallSite());
    assert bb.length == 1;
    SSACFG.BasicBlock cb =
        (BasicBlock) ir.getControlFlowGraph().getExceptionalSuccessors(bb[0]).iterator().next();
    if (cb.isExitBlock()) {
      return getPointerKeyForExceptionalReturnValue(node);
    } else {
      SSACFG.ExceptionHandlerBasicBlock ehbb = (ExceptionHandlerBasicBlock) cb;
      SSAGetCaughtExceptionInstruction ci = ehbb.getCatchInstruction();
      return getPointerKeyForLocal(node, ci.getDef());
    }
  }

  /**
   * @return a List of Instructions that may transfer control to bb via an exceptional edge
   * @throws IllegalArgumentException if ir is null
   */
  public static List<ProgramCounter> getIncomingPEIs(IRView ir, ISSABasicBlock bb) {
    if (ir == null) {
      throw new IllegalArgumentException("ir is null");
    }
    if (DEBUG) {
      System.err.println("getIncomingPEIs " + bb);
    }
    ControlFlowGraph<SSAInstruction, ISSABasicBlock> g = ir.getControlFlowGraph();
    List<ProgramCounter> result = new ArrayList<>(g.getPredNodeCount(bb));
    for (ISSABasicBlock sbb : Iterator2Iterable.make(g.getPredNodes(bb))) {
      BasicBlock pred = (BasicBlock) sbb;
      if (DEBUG) {
        System.err.println("pred: " + pred);
      }
      if (pred.isEntryBlock()) continue;
      int index = pred.getLastInstructionIndex();
      SSAInstruction pei = ir.getInstructions()[index];
      // Note: pei might be null if pred is unreachable.
      // TODO: consider pruning CFG for unreachable blocks.
      if (pei != null && pei.isPEI()) {
        if (DEBUG) {
          System.err.println(
              "PEI: " + pei + " index " + index + " PC " + g.getProgramCounter(index));
        }
        result.add(new ProgramCounter(g.getProgramCounter(index)));
      }
    }
    return result;
  }

  private class CrossProductRec {
    private final InstanceKey[][] invariants;
    private final Consumer<InstanceKey[]> f;
    private final SSAAbstractInvokeInstruction call;
    private final CGNode caller;
    private final int[] params;
    private final CallSiteReference site;
    private final InstanceKey[] keys;

    private CrossProductRec(
        InstanceKey[][] invariants,
        SSAAbstractInvokeInstruction call,
        CGNode caller,
        Consumer<InstanceKey[]> f) {
      this.invariants = invariants;
      this.f = f;
      this.call = call;
      this.caller = caller;
      this.site = call.getCallSite();
      MutableIntSet indices = IntSetUtil.makeMutableCopy(getRelevantParameters(caller, site));
      getRelevantParameters(caller, site)
          .foreach(
              (i) -> {
                if (i >= call.getNumberOfUses()) {
                  indices.remove(i);
                }
              });
      this.params = IntSetUtil.toArray(indices);
      this.keys = new InstanceKey[params.length];
    }

    protected void rec(final int pi, final int rhsi) {
      if (pi == params.length) {
        f.accept(keys);
      } else {
        final int p = params[pi];
        InstanceKey[] ik = invariants != null ? invariants[p] : null;
        if (ik != null) {
          if (ik.length > 0) {
            for (InstanceKey element : ik) {
              system.findOrCreateIndexForInstanceKey(element);
              keys[pi] = element;
              rec(pi + 1, rhsi);
            }
          } /* else {
              if (!site.isDispatch() || p != 0) {
                keys[pi] = null;
                rec(pi + 1, rhsi);
              }
            } */
        } else {
          IntSet s = getParamObjects(pi, rhsi);
          if (s != null && !s.isEmpty()) {
            s.foreach(
                x -> {
                  keys[pi] = system.getInstanceKey(x);
                  rec(pi + 1, rhsi + 1);
                });
          } /*else {
              if (!site.isDispatch() || p != 0) {
                keys[pi] = null;
                rec(pi + 1, rhsi + 1);
              }
            } */
        }
      }
    }

    protected IntSet getParamObjects(int paramIndex, @SuppressWarnings("unused") int rhsi) {
      int paramVn = call.getUse(paramIndex);
      PointerKey var = getPointerKeyForLocal(caller, paramVn);
      IntSet s = system.findOrCreatePointsToSet(var).getValue();
      return s;
    }
  }

  /** A visitor that generates constraints based on statements in SSA form. */
  protected static class ConstraintVisitor extends SSAInstruction.Visitor {

    /**
     * The governing call graph builder. This field is used instead of an inner class in order to
     * allow more flexible reuse of this visitor in subclasses
     */
    protected final SSAPropagationCallGraphBuilder builder;

    /** The node whose statements we are currently traversing */
    protected final CGNode node;

    /** The governing call graph. */
    private final ExplicitCallGraph callGraph;

    /** The governing IR */
    protected final IRView ir;

    /** The governing propagation system, into which constraints are added */
    protected final PropagationSystem system;

    /** The basic block currently being processed */
    protected ISSABasicBlock basicBlock;

    /** Governing symbol table */
    protected final SymbolTable symbolTable;

    /** Def-use information */
    protected final DefUse du;

    public ConstraintVisitor(SSAPropagationCallGraphBuilder builder, CGNode node) {
      this.builder = builder;
      this.node = node;

      this.callGraph = builder.getCallGraph();

      this.system = builder.getPropagationSystem();

      SSAContextInterpreter interp = builder.getCFAContextInterpreter();
      this.ir = interp.getIRView(node);
      this.symbolTable = this.ir.getSymbolTable();

      this.du = interp.getDU(node);

      assert symbolTable != null;
    }

    protected SSAPropagationCallGraphBuilder getBuilder() {
      return builder;
    }

    protected AnalysisOptions getOptions() {
      return builder.options;
    }

    protected IAnalysisCacheView getAnalysisCache() {
      return builder.getAnalysisCache();
    }

    public PointerKey getPointerKeyForLocal(int valueNumber) {
      return getBuilder().getPointerKeyForLocal(node, valueNumber);
    }

    public FilteredPointerKey getFilteredPointerKeyForLocal(
        int valueNumber, FilteredPointerKey.TypeFilter filter) {
      return getBuilder().getFilteredPointerKeyForLocal(node, valueNumber, filter);
    }

    public PointerKey getPointerKeyForReturnValue() {
      return getBuilder().getPointerKeyForReturnValue(node);
    }

    public PointerKey getPointerKeyForExceptionalReturnValue() {
      return getBuilder().getPointerKeyForExceptionalReturnValue(node);
    }

    public PointerKey getPointerKeyForStaticField(IField f) {
      return getBuilder().getPointerKeyForStaticField(f);
    }

    public PointerKey getPointerKeyForInstanceField(InstanceKey I, IField f) {
      return getBuilder().getPointerKeyForInstanceField(I, f);
    }

    public PointerKey getPointerKeyForArrayContents(InstanceKey I) {
      return getBuilder().getPointerKeyForArrayContents(I);
    }

    public InstanceKey getInstanceKeyForAllocation(NewSiteReference allocation) {
      return getBuilder().getInstanceKeyForAllocation(node, allocation);
    }

    public InstanceKey getInstanceKeyForMultiNewArray(NewSiteReference allocation, int dim) {
      return getBuilder().getInstanceKeyForMultiNewArray(node, allocation, dim);
    }

    public <T> InstanceKey getInstanceKeyForConstant(T S) {
      TypeReference type =
          node.getMethod().getDeclaringClass().getClassLoader().getLanguage().getConstantType(S);
      return getBuilder().getInstanceKeyForConstant(type, S);
    }

    public InstanceKey getInstanceKeyForPEI(ProgramCounter instr, TypeReference type) {
      return getBuilder().getInstanceKeyForPEI(node, instr, type);
    }

    public InstanceKey getInstanceKeyForClassObject(Object obj, TypeReference type) {
      return getBuilder().getInstanceKeyForMetadataObject(obj, type);
    }

    public CGNode getTargetForCall(
        CGNode caller, CallSiteReference site, IClass recv, InstanceKey iKey[]) {
      return getBuilder().getTargetForCall(caller, site, recv, iKey);
    }

    protected boolean contentsAreInvariant(SymbolTable symbolTable, DefUse du, int valueNumber) {
      return getBuilder().contentsAreInvariant(symbolTable, du, valueNumber);
    }

    protected boolean contentsAreInvariant(SymbolTable symbolTable, DefUse du, int valueNumber[]) {
      return getBuilder().contentsAreInvariant(symbolTable, du, valueNumber);
    }

    protected InstanceKey[] getInvariantContents(int valueNumber) {
      return getInvariantContents(ir.getSymbolTable(), du, node, valueNumber);
    }

    protected InstanceKey[] getInvariantContents(
        SymbolTable symbolTable, DefUse du, CGNode node, int valueNumber) {
      return getBuilder().getInvariantContents(symbolTable, du, node, valueNumber, getBuilder());
    }

    protected IClassHierarchy getClassHierarchy() {
      return getBuilder().getClassHierarchy();
    }

    protected boolean hasNoInterestingUses(int vn) {
      return getBuilder().hasNoInterestingUses(node, vn, du);
    }

    protected boolean isRootType(IClass klass) {
      return SSAPropagationCallGraphBuilder.isRootType(klass);
    }

    /*
     * @see com.ibm.wala.ssa.SSAInstruction.Visitor#visitArrayLoad(com.ibm.wala.ssa.SSAArrayLoadInstruction)
     */
    @Override
    public void visitArrayLoad(SSAArrayLoadInstruction instruction) {
      // skip arrays of primitive type
      if (instruction.typeIsPrimitive()) {
        return;
      }
      doVisitArrayLoad(instruction.getDef(), instruction.getArrayRef());
    }

    protected void doVisitArrayLoad(int def, int arrayRef) {
      PointerKey result = getPointerKeyForLocal(def);
      PointerKey arrayRefPtrKey = getPointerKeyForLocal(arrayRef);
      if (hasNoInterestingUses(def)) {
        system.recordImplicitPointsToSet(result);
      } else {
        if (contentsAreInvariant(symbolTable, du, arrayRef)) {
          system.recordImplicitPointsToSet(arrayRefPtrKey);
          InstanceKey[] ik = getInvariantContents(arrayRef);
          for (InstanceKey instanceKey : ik) {
            if (!representsNullType(instanceKey)) {
              system.findOrCreateIndexForInstanceKey(instanceKey);
              PointerKey p = getPointerKeyForArrayContents(instanceKey);
              if (p == null) {
              } else {
                system.newConstraint(result, assignOperator, p);
              }
            }
          }
        } else {
          assert !system.isUnified(result);
          assert !system.isUnified(arrayRefPtrKey);
          system.newSideEffect(
              getBuilder().new ArrayLoadOperator(system.findOrCreatePointsToSet(result)),
              arrayRefPtrKey);
        }
      }
    }

    /*
     * @see com.ibm.wala.ssa.SSAInstruction.Visitor#visitArrayStore(com.ibm.wala.ssa.SSAArrayStoreInstruction)
     */
    public void doVisitArrayStore(int arrayRef, int value) {
      // (requires the creation of assign constraints as
      // the set points-to(a[]) grows.)
      PointerKey valuePtrKey = getPointerKeyForLocal(value);
      PointerKey arrayRefPtrKey = getPointerKeyForLocal(arrayRef);
      // if (!supportFullPointerFlowGraph &&
      // contentsAreInvariant(instruction.getArrayRef())) {
      if (contentsAreInvariant(symbolTable, du, arrayRef)) {
        system.recordImplicitPointsToSet(arrayRefPtrKey);
        InstanceKey[] ik = getInvariantContents(arrayRef);

        for (InstanceKey instanceKey : ik) {
          if (!representsNullType(instanceKey) && !(instanceKey instanceof ZeroLengthArrayInNode)) {
            system.findOrCreateIndexForInstanceKey(instanceKey);
            PointerKey p = getPointerKeyForArrayContents(instanceKey);
            IClass contents = ((ArrayClass) instanceKey.getConcreteType()).getElementClass();
            if (p == null) {
            } else {
              if (contentsAreInvariant(symbolTable, du, value)) {
                system.recordImplicitPointsToSet(valuePtrKey);
                InstanceKey[] vk = getInvariantContents(value);
                for (InstanceKey element : vk) {
                  system.findOrCreateIndexForInstanceKey(element);
                  if (element.getConcreteType() != null) {
                    if (getClassHierarchy().isAssignableFrom(contents, element.getConcreteType())) {
                      system.newConstraint(p, element);
                    }
                  }
                }
              } else {
                if (isRootType(contents)) {
                  system.newConstraint(p, assignOperator, valuePtrKey);
                } else {
                  system.newConstraint(p, getBuilder().filterOperator, valuePtrKey);
                }
              }
            }
          }
        }
      } else {
        if (contentsAreInvariant(symbolTable, du, value)) {
          system.recordImplicitPointsToSet(valuePtrKey);
          InstanceKey[] ik = getInvariantContents(value);
          for (InstanceKey element : ik) {
            system.findOrCreateIndexForInstanceKey(element);
            assert !system.isUnified(arrayRefPtrKey);
            system.newSideEffect(
                getBuilder().new InstanceArrayStoreOperator(element), arrayRefPtrKey);
          }
        } else {
          system.newSideEffect(
              getBuilder().new ArrayStoreOperator(system.findOrCreatePointsToSet(valuePtrKey)),
              arrayRefPtrKey);
        }
      }
    }

    @Override
    public void visitArrayStore(SSAArrayStoreInstruction instruction) {
      // skip arrays of primitive type
      if (instruction.typeIsPrimitive()) {
        return;
      }
      doVisitArrayStore(instruction.getArrayRef(), instruction.getValue());
    }

    /*
     * @see com.ibm.wala.ssa.SSAInstruction.Visitor#visitCheckCast(com.ibm.wala.ssa.SSACheckCastInstruction)
     */
    @Override
    public void visitCheckCast(SSACheckCastInstruction instruction) {

      boolean isRoot = false;
      Set<IClass> types = HashSetFactory.make();

      for (TypeReference t : instruction.getDeclaredResultTypes()) {
        IClass cls = getClassHierarchy().lookupClass(t);
        if (cls == null) {
          Warnings.add(CheckcastFailure.create(t));
          return;
        } else {
          if (isRootType(cls)) {
            isRoot = true;
          }
          types.add(cls);
        }
      }

      PointerKey result =
          getFilteredPointerKeyForLocal(
              instruction.getResult(),
              new FilteredPointerKey.MultipleClassesFilter(types.toArray(new IClass[0])));
      PointerKey value = getPointerKeyForLocal(instruction.getVal());

      if (hasNoInterestingUses(instruction.getDef())) {
        system.recordImplicitPointsToSet(result);
      } else {
        if (contentsAreInvariant(symbolTable, du, instruction.getVal())) {
          system.recordImplicitPointsToSet(value);
          InstanceKey[] ik = getInvariantContents(instruction.getVal());
          for (TypeReference t : instruction.getDeclaredResultTypes()) {
            IClass cls = getClassHierarchy().lookupClass(t);

            if (cls.isInterface()) {
              for (InstanceKey element : ik) {
                system.findOrCreateIndexForInstanceKey(element);
                if (getClassHierarchy().implementsInterface(element.getConcreteType(), cls)) {
                  system.newConstraint(result, element);
                }
              }
            } else {
              for (InstanceKey element : ik) {
                system.findOrCreateIndexForInstanceKey(element);
                if (getClassHierarchy().isSubclassOf(element.getConcreteType(), cls)) {
                  system.newConstraint(result, element);
                }
              }
            }
          }
        } else {
          if (isRoot) {
            system.newConstraint(result, assignOperator, value);
          } else {
            system.newConstraint(result, getBuilder().filterOperator, value);
          }
        }
      }
    }

    /*
     * @see com.ibm.wala.ssa.SSAInstruction.Visitor#visitReturn(com.ibm.wala.ssa.SSAReturnInstruction)
     */
    @Override
    public void visitReturn(SSAReturnInstruction instruction) {

      // skip returns of primitive type
      if (instruction.returnsPrimitiveType() || instruction.returnsVoid()) {
        return;
      }
      if (DEBUG) {
        System.err.println("visitReturn: " + instruction);
      }

      PointerKey returnValue = getPointerKeyForReturnValue();
      PointerKey result = getPointerKeyForLocal(instruction.getResult());
      if (contentsAreInvariant(symbolTable, du, instruction.getResult())) {
        system.recordImplicitPointsToSet(result);
        InstanceKey[] ik = getInvariantContents(instruction.getResult());
        for (InstanceKey element : ik) {
          if (DEBUG) {
            System.err.println("invariant contents: " + returnValue + ' ' + element);
          }
          system.newConstraint(returnValue, element);
        }
      } else {
        system.newConstraint(returnValue, assignOperator, result);
      }
    }

    /*
     * @see com.ibm.wala.ssa.SSAInstruction.Visitor#visitGet(com.ibm.wala.ssa.SSAGetInstruction)
     */
    @Override
    public void visitGet(SSAGetInstruction instruction) {
      visitGetInternal(
          instruction.getDef(),
          instruction.getRef(),
          instruction.isStatic(),
          instruction.getDeclaredField());
    }

    protected void visitGetInternal(int lval, int ref, boolean isStatic, FieldReference field) {
      if (DEBUG) {
        System.err.println("visitGet " + field);
      }

      PointerKey def = getPointerKeyForLocal(lval);
      assert def != null;

      IField f = getClassHierarchy().resolveField(field);
      if (f == null
          && callGraph
              .getFakeRootNode()
              .getMethod()
              .getDeclaringClass()
              .getReference()
              .equals(field.getDeclaringClass())) {
        f = callGraph.getFakeRootNode().getMethod().getDeclaringClass().getField(field.getName());
      }

      if (f == null) {
        return;
      }

      if (isStatic) {
        IClass klass = getClassHierarchy().lookupClass(field.getDeclaringClass());
        if (klass == null) {
        } else {
          // side effect of getstatic: may call class initializer
          if (DEBUG) {
            System.err.println("getstatic call class init " + klass);
          }
          processClassInitializer(klass);
        }
      }

      // skip getfields of primitive type (optimisation)
      if (field.getFieldType().isPrimitiveType()) {
        return;
      }

      if (hasNoInterestingUses(lval)) {
        system.recordImplicitPointsToSet(def);
      } else {
        if (isStatic) {
          PointerKey fKey = getPointerKeyForStaticField(f);
          system.newConstraint(def, assignOperator, fKey);
        } else {
          PointerKey refKey = getPointerKeyForLocal(ref);
          // if (!supportFullPointerFlowGraph &&
          // contentsAreInvariant(ref)) {
          if (contentsAreInvariant(symbolTable, du, ref)) {
            system.recordImplicitPointsToSet(refKey);
            InstanceKey[] ik = getInvariantContents(ref);
            for (InstanceKey instanceKey : ik) {
              if (!representsNullType(instanceKey)) {
                system.findOrCreateIndexForInstanceKey(instanceKey);
                PointerKey p = getPointerKeyForInstanceField(instanceKey, f);
                if (p != null) {
                  system.newConstraint(def, assignOperator, p);
                }
              }
            }
          } else {
            system.newSideEffect(
                getBuilder().new GetFieldOperator(f, system.findOrCreatePointsToSet(def)), refKey);
          }
        }
      }
    }

    /*
     * @see com.ibm.wala.ssa.Instruction.Visitor#visitPut(com.ibm.wala.ssa.PutInstruction)
     */
    @Override
    public void visitPut(SSAPutInstruction instruction) {
      visitPutInternal(
          instruction.getVal(),
          instruction.getRef(),
          instruction.isStatic(),
          instruction.getDeclaredField());
    }

    public void visitPutInternal(int rval, int ref, boolean isStatic, FieldReference field) {

      if (DEBUG) {
        System.err.println("visitPut " + field);
      }

      // skip putfields of primitive type
      if (field.getFieldType().isPrimitiveType()) {
        return;
      }
      IField f = getClassHierarchy().resolveField(field);
      if (f == null) {
        if (DEBUG) {
          System.err.println("Could not resolve field " + field);
        }
        Warnings.add(FieldResolutionFailure.create(field));
        return;
      }
      assert f.getFieldTypeReference().getName().equals(field.getFieldType().getName())
          : "name clash of two fields with the same name but different type: "
              + f.getReference()
              + " <=> "
              + field;
      assert isStatic || !symbolTable.isStringConstant(ref)
          : "put to string constant shouldn't be allowed?";
      if (isStatic) {
        processPutStatic(rval, field, f);
      } else {
        processPutField(rval, ref, f);
      }
    }

    public void processPutField(int rval, int ref, IField f) {
      assert !f.getFieldTypeReference().isPrimitiveType();
      PointerKey refKey = getPointerKeyForLocal(ref);
      PointerKey rvalKey = getPointerKeyForLocal(rval);
      // if (!supportFullPointerFlowGraph &&
      // contentsAreInvariant(rval)) {
      if (contentsAreInvariant(symbolTable, du, rval)) {
        system.recordImplicitPointsToSet(rvalKey);
        InstanceKey[] ik = getInvariantContents(rval);
        if (contentsAreInvariant(symbolTable, du, ref)) {
          system.recordImplicitPointsToSet(refKey);
          InstanceKey[] refk = getInvariantContents(ref);
          for (InstanceKey instanceKey : refk) {
            if (!representsNullType(instanceKey)) {
              system.findOrCreateIndexForInstanceKey(instanceKey);
              PointerKey p = getPointerKeyForInstanceField(instanceKey, f);
              for (InstanceKey element : ik) {
                system.newConstraint(p, element);
              }
            }
          }
        } else {
          for (InstanceKey element : ik) {
            system.findOrCreateIndexForInstanceKey(element);
            system.newSideEffect(getBuilder().new InstancePutFieldOperator(f, element), refKey);
          }
        }
      } else {
        if (contentsAreInvariant(symbolTable, du, ref)) {
          system.recordImplicitPointsToSet(refKey);
          InstanceKey[] refk = getInvariantContents(ref);
          for (InstanceKey instanceKey : refk) {
            if (!representsNullType(instanceKey)) {
              system.findOrCreateIndexForInstanceKey(instanceKey);
              PointerKey p = getPointerKeyForInstanceField(instanceKey, f);
              system.newConstraint(p, assignOperator, rvalKey);
            }
          }
        } else {
          if (DEBUG) {
            System.err.println("adding side effect " + f);
          }
          system.newSideEffect(
              getBuilder().new PutFieldOperator(f, system.findOrCreatePointsToSet(rvalKey)),
              refKey);
        }
      }
    }

    protected void processPutStatic(int rval, FieldReference field, IField f) {
      PointerKey fKey = getPointerKeyForStaticField(f);
      PointerKey rvalKey = getPointerKeyForLocal(rval);

      // if (!supportFullPointerFlowGraph &&
      // contentsAreInvariant(rval)) {
      if (contentsAreInvariant(symbolTable, du, rval)) {
        system.recordImplicitPointsToSet(rvalKey);
        InstanceKey[] ik = getInvariantContents(rval);
        for (InstanceKey element : ik) {
          system.newConstraint(fKey, element);
        }
      } else {
        system.newConstraint(fKey, assignOperator, rvalKey);
      }
      if (DEBUG) {
        System.err.println("visitPut class init " + field.getDeclaringClass() + ' ' + field);
      }
      // side effect of putstatic: may call class initializer
      IClass klass = getClassHierarchy().lookupClass(field.getDeclaringClass());
      if (klass == null) {
        Warnings.add(FieldResolutionFailure.create(field));
      } else {
        processClassInitializer(klass);
      }
    }

    /*
     * @see com.ibm.wala.ssa.Instruction.Visitor#visitInvoke(com.ibm.wala.ssa.InvokeInstruction)
     */
    @Override
    public void visitInvoke(SSAInvokeInstruction instruction) {
      visitInvokeInternal(instruction, new DefaultInvariantComputer());
    }

    protected void visitInvokeInternal(
        final SSAAbstractInvokeInstruction instruction, InvariantComputer invs) {
      if (DEBUG) {
        System.err.println("visitInvoke: " + instruction);
      }

      PointerKey uniqueCatch = null;
      if (hasUniqueCatchBlock(instruction, ir)) {
        uniqueCatch = getBuilder().getUniqueCatchKey(instruction, ir, node);
      }

      InstanceKey[][] invariantParameters = invs.computeInvariantParameters(instruction);

      IntSet params =
          getBuilder().getContextSelector().getRelevantParameters(node, instruction.getCallSite());
      if (!instruction.getCallSite().isStatic()
          && !params.contains(0)
          && (invariantParameters == null || invariantParameters[0] == null)) {
        params = IntSetUtil.makeMutableCopy(params);
        ((MutableIntSet) params).add(0);
      }

      if (invariantParameters != null) {
        for (int i = 0; i < invariantParameters.length; i++) {
          if (invariantParameters[i] != null) {
            params = IntSetUtil.makeMutableCopy(params);
            ((MutableIntSet) params).remove(i);
          }
        }
      }

      if (!params.isEmpty() && params.max() >= instruction.getNumberOfUses()) {
        MutableIntSet trimmedParams = IntSetUtil.makeMutableCopy(params);
        params.foreach(
            (i) -> {
              if (i >= instruction.getNumberOfUses()) trimmedParams.remove(i);
            });
        params = trimmedParams;
      }

      if (params.isEmpty()) {
        for (CGNode n : getBuilder().getTargetsForCall(node, instruction, invariantParameters)) {
          getBuilder().processResolvedCall(node, instruction, n, invariantParameters, uniqueCatch);
          if (DEBUG) {
            System.err.println("visitInvoke class init " + n);
          }

          // side effect of invoke: may call class initializer
          processClassInitializer(n.getMethod().getDeclaringClass());
        }
      } else {
        // Add a side effect that will fire when we determine a value
        // for a dispatch parameter. This side effect will create a new node
        // and new constraints based on the new callee context.
        final int vns[] = new int[params.size()];
        params.foreach(
            new IntSetAction() {
              private int i = 0;

              @Override
              public void act(int x) {
                vns[i++] = instruction.getUse(x);
              }
            });

        if (contentsAreInvariant(symbolTable, du, vns)) {
          for (CGNode n : getBuilder().getTargetsForCall(node, instruction, invariantParameters)) {
            getBuilder()
                .processResolvedCall(node, instruction, n, invariantParameters, uniqueCatch);
            // side effect of invoke: may call class initializer
            processClassInitializer(n.getMethod().getDeclaringClass());
          }
        } else {
          if (DEBUG) {
            System.err.println("Add side effect, dispatch to " + instruction + " for " + params);
          }

          final List<PointerKey> pks = new ArrayList<>(params.size());
          params.foreach(
              x -> {
                if (!contentsAreInvariant(symbolTable, du, instruction.getUse(x))) {
                  pks.add(getBuilder().getPointerKeyForLocal(node, instruction.getUse(x)));
                }
              });

          DispatchOperator dispatchOperator =
              getBuilder()
              .new DispatchOperator(instruction, node, invariantParameters, uniqueCatch, params);
          system.newSideEffect(dispatchOperator, pks.toArray(new PointerKey[0]));
        }
      }
    }

    /*
     * @see com.ibm.wala.ssa.Instruction.Visitor#visitNew(com.ibm.wala.ssa.NewInstruction)
     */
    @Override
    public void visitNew(SSANewInstruction instruction) {
      InstanceKey iKey = getInstanceKeyForAllocation(instruction.getNewSite());

      if (iKey == null) {
        // something went wrong. I hope someone raised a warning.
        return;
      }
      PointerKey def = getPointerKeyForLocal(instruction.getDef());
      IClass klass = iKey.getConcreteType();

      if (DEBUG) {
        System.err.println(
            "visitNew: "
                + instruction
                + " i:"
                + iKey
                + ' '
                + system.findOrCreateIndexForInstanceKey(iKey));
      }

      if (klass == null) {
        if (DEBUG) {
          System.err.println("Resolution failure: " + instruction);
        }
        return;
      }

      if (!contentsAreInvariant(symbolTable, du, instruction.getDef())) {
        system.newConstraint(def, iKey);
      } else {
        system.findOrCreateIndexForInstanceKey(iKey);
        system.recordImplicitPointsToSet(def);
      }

      // side effect of new: may call class initializer
      if (DEBUG) {
        System.err.println("visitNew call clinit: " + klass);
      }
      processClassInitializer(klass);
      processFinalizeMethod(klass);

      // add instance keys and pointer keys for array contents
      int dim = 0;
      InstanceKey lastInstance = iKey;
      while (klass != null && klass.isArrayClass()) {
        klass = ((ArrayClass) klass).getElementClass();
        // klass == null means it's a primitive
        if (klass != null && klass.isArrayClass()) {
          if (instruction.getNumberOfUses() <= (dim + 1)) {
            break;
          }
          int sv = instruction.getUse(dim + 1);
          if (ir.getSymbolTable().isIntegerConstant(sv)) {
            Integer c = (Integer) ir.getSymbolTable().getConstantValue(sv);
            if (c == 0) {
              break;
            }
          }
          InstanceKey ik = getInstanceKeyForMultiNewArray(instruction.getNewSite(), dim);
          PointerKey pk = getPointerKeyForArrayContents(lastInstance);
          if (DEBUG_MULTINEWARRAY) {
            System.err.println("multinewarray constraint: ");
            System.err.println("   pk: " + pk);
            System.err.println(
                "   ik: "
                    + system.findOrCreateIndexForInstanceKey(ik)
                    + " concrete type "
                    + ik.getConcreteType()
                    + " is "
                    + ik);
            System.err.println("   klass:" + klass);
          }
          system.newConstraint(pk, ik);
          lastInstance = ik;
          dim++;
        }
      }
    }

    /*
     * @see com.ibm.wala.ssa.Instruction.Visitor#visitThrow(com.ibm.wala.ssa.ThrowInstruction)
     */
    @Override
    public void visitThrow(SSAThrowInstruction instruction) {
      // don't do anything: we handle exceptional edges
      // in a separate pass
    }

    /*
     * @see com.ibm.wala.ssa.Instruction.Visitor#visitGetCaughtException(com.ibm.wala.ssa.GetCaughtExceptionInstruction)
     */
    @Override
    public void visitGetCaughtException(SSAGetCaughtExceptionInstruction instruction) {
      List<ProgramCounter> peis = getIncomingPEIs(ir, getBasicBlock());
      PointerKey def = getPointerKeyForLocal(instruction.getDef());
      // SJF: we don't optimize based on dead catch blocks yet ... it's a little
      // tricky due interaction with the SINGLE_USE optimization which directly
      // shoves exceptional return values from calls into exception vars.
      // it may not be worth doing this.
      // if (hasNoInterestingUses(instruction.getDef(), du)) {
      // solver.recordImplicitPointsToSet(def);
      // } else {
      Set<IClass> types = getCaughtExceptionTypes(instruction, ir);
      getBuilder().addExceptionDefConstraints(ir, du, node, peis, def, types);
      // }
    }

    /** TODO: What is this doing? Document me! */
    private int booleanConstantTest(SSAConditionalBranchInstruction c, int v) {
      int result = 0;

      // right for OPR_eq
      if ((symbolTable.isZeroOrFalse(c.getUse(0)) && c.getUse(1) == v)
          || (symbolTable.isZeroOrFalse(c.getUse(1)) && c.getUse(0) == v)) {
        result = -1;
      } else if ((symbolTable.isOneOrTrue(c.getUse(0)) && c.getUse(1) == v)
          || (symbolTable.isOneOrTrue(c.getUse(1)) && c.getUse(0) == v)) {
        result = 1;
      }

      if (c.getOperator() == ConditionalBranchInstruction.Operator.NE) {
        result = -result;
      }

      return result;
    }

    private int nullConstantTest(SSAConditionalBranchInstruction c, int v) {
      if ((symbolTable.isNullConstant(c.getUse(0)) && c.getUse(1) == v)
          || (symbolTable.isNullConstant(c.getUse(1)) && c.getUse(0) == v)) {
        if (c.getOperator() == ConditionalBranchInstruction.Operator.EQ) {
          return 1;
        } else {
          return -1;
        }
      } else {
        return 0;
      }
    }

    @Override
    public void visitPhi(SSAPhiInstruction instruction) {
      if (ir.getMethod() instanceof AbstractRootMethod) {
        PointerKey dst = getPointerKeyForLocal(instruction.getDef());
        if (hasNoInterestingUses(instruction.getDef())) {
          system.recordImplicitPointsToSet(dst);
        } else {
          for (int i = 0; i < instruction.getNumberOfUses(); i++) {
            PointerKey use = getPointerKeyForLocal(instruction.getUse(i));
            if (contentsAreInvariant(symbolTable, du, instruction.getUse(i))) {
              system.recordImplicitPointsToSet(use);
              InstanceKey[] ik = getInvariantContents(instruction.getUse(i));
              for (InstanceKey element : ik) {
                system.newConstraint(dst, element);
              }
            } else {
              system.newConstraint(dst, assignOperator, use);
            }
          }
        }
      }
    }

    /*
     * @see com.ibm.wala.ssa.SSAInstruction.Visitor#visitPi(com.ibm.wala.ssa.SSAPiInstruction)
     */
    @Override
    public void visitPi(SSAPiInstruction instruction) {
      int dir;

      if (hasNoInterestingUses(instruction.getDef())) {
        PointerKey dst = getPointerKeyForLocal(instruction.getDef());
        system.recordImplicitPointsToSet(dst);
      } else {
        ControlFlowGraph<SSAInstruction, ISSABasicBlock> cfg = ir.getControlFlowGraph();
        int val = instruction.getVal();
        if (com.ibm.wala.cfg.Util.endsWithConditionalBranch(cfg, getBasicBlock())
            && cfg.getSuccNodeCount(getBasicBlock()) == 2) {
          SSAConditionalBranchInstruction cond =
              (SSAConditionalBranchInstruction)
                  com.ibm.wala.cfg.Util.getLastInstruction(cfg, getBasicBlock());
          SSAInstruction cause = instruction.getCause();
          BasicBlock target = (BasicBlock) cfg.getNode(instruction.getSuccessor());

          if ((cause instanceof SSAInstanceofInstruction)) {
            int direction = booleanConstantTest(cond, cause.getDef());
            if (direction != 0) {
              TypeReference type = ((SSAInstanceofInstruction) cause).getCheckedType();
              IClass cls = getClassHierarchy().lookupClass(type);
              if (cls == null) {
                PointerKey dst = getPointerKeyForLocal(instruction.getDef());
                addPiAssignment(dst, val);
              } else {
                PointerKey dst =
                    getFilteredPointerKeyForLocal(
                        instruction.getDef(), new FilteredPointerKey.SingleClassFilter(cls));
                // if true, only allow objects assignable to cls.  otherwise, only allow objects
                // *not* assignable to cls
                boolean useFilter =
                    (target == com.ibm.wala.cfg.Util.getTakenSuccessor(cfg, getBasicBlock())
                            && direction == 1)
                        || (target
                                == com.ibm.wala.cfg.Util.getNotTakenSuccessor(cfg, getBasicBlock())
                            && direction == -1);
                PointerKey src = getPointerKeyForLocal(val);
                if (contentsAreInvariant(symbolTable, du, val)) {
                  system.recordImplicitPointsToSet(src);
                  InstanceKey[] ik = getInvariantContents(val);
                  for (InstanceKey element : ik) {
                    boolean assignable =
                        getClassHierarchy().isAssignableFrom(cls, element.getConcreteType());
                    if ((assignable && useFilter) || (!assignable && !useFilter)) {
                      system.newConstraint(dst, element);
                    }
                  }
                } else {
                  FilterOperator op =
                      useFilter ? getBuilder().filterOperator : getBuilder().inverseFilterOperator;
                  system.newConstraint(dst, op, src);
                }
              }
            }
          } else if ((dir = nullConstantTest(cond, val)) != 0) {
            if ((target == com.ibm.wala.cfg.Util.getTakenSuccessor(cfg, getBasicBlock())
                    && dir == -1)
                || (target == com.ibm.wala.cfg.Util.getNotTakenSuccessor(cfg, getBasicBlock())
                    && dir == 1)) {
              PointerKey dst = getPointerKeyForLocal(instruction.getDef());
              addPiAssignment(dst, val);
            }
          } else {
            PointerKey dst = getPointerKeyForLocal(instruction.getDef());
            addPiAssignment(dst, val);
          }
        } else {
          PointerKey dst = getPointerKeyForLocal(instruction.getDef());
          addPiAssignment(dst, val);
        }
      }
    }

    /**
     * Add a constraint to the system indicating that the contents of local src flows to dst, with
     * no special type filter.
     */
    private void addPiAssignment(PointerKey dst, int src) {
      PointerKey srcKey = getPointerKeyForLocal(src);
      if (contentsAreInvariant(symbolTable, du, src)) {
        system.recordImplicitPointsToSet(srcKey);
        InstanceKey[] ik = getInvariantContents(src);
        for (InstanceKey element : ik) {
          system.newConstraint(dst, element);
        }
      } else {
        system.newConstraint(dst, assignOperator, srcKey);
      }
    }

    public ISSABasicBlock getBasicBlock() {
      return basicBlock;
    }

    /** The calling loop must call this in each iteration! */
    public void setBasicBlock(ISSABasicBlock block) {
      basicBlock = block;
    }

    protected interface InvariantComputer {

      InstanceKey[][] computeInvariantParameters(SSAAbstractInvokeInstruction call);
    }

    public class DefaultInvariantComputer implements InvariantComputer {
      /**
       * Side effect: records invariant parameters as implicit points-to-sets.
       *
       * @return if non-null, then result[i] holds the set of instance keys which may be passed as
       *     the ith parameter. (which must be invariant)
       */
      @Override
      public InstanceKey[][] computeInvariantParameters(SSAAbstractInvokeInstruction call) {
        InstanceKey[][] constParams = null;
        for (int i = 0; i < call.getNumberOfUses(); i++) {
          // not sure how getUse(i) <= 0 .. dead code?
          // TODO: investigate
          if (call.getUse(i) > 0) {
            if (contentsAreInvariant(symbolTable, du, call.getUse(i))) {
              system.recordImplicitPointsToSet(getPointerKeyForLocal(call.getUse(i)));
              if (constParams == null) {
                constParams = new InstanceKey[call.getNumberOfUses()][];
              }
              constParams[i] = getInvariantContents(call.getUse(i));
              for (int j = 0; j < constParams[i].length; j++) {
                system.findOrCreateIndexForInstanceKey(constParams[i][j]);
              }
            }
          }
        }
        return constParams;
      }
    }

    @Override
    public void visitLoadMetadata(SSALoadMetadataInstruction instruction) {
      PointerKey def = getPointerKeyForLocal(instruction.getDef());
      InstanceKey iKey =
          getInstanceKeyForClassObject(instruction.getToken(), instruction.getType());

      if (instruction.getToken() instanceof TypeReference) {
        IClass klass = getClassHierarchy().lookupClass((TypeReference) instruction.getToken());
        if (klass != null) {
          processClassInitializer(klass);
        }
      }

      if (!contentsAreInvariant(symbolTable, du, instruction.getDef())) {
        system.newConstraint(def, iKey);
      } else {
        system.findOrCreateIndexForInstanceKey(iKey);
        system.recordImplicitPointsToSet(def);
      }
    }

    private void processFinalizeMethod(final IClass klass) {
      if (getBuilder().finalizeVisited.add(klass)) {
        IMethod finalizer = klass.getMethod(MethodReference.finalizeSelector);
        if (finalizer != null
            && !finalizer.getDeclaringClass().getReference().equals(TypeReference.JavaLangObject)) {
          Entrypoint ef =
              new DefaultEntrypoint(finalizer, getClassHierarchy()) {
                @Override
                protected TypeReference[] makeParameterTypes(IMethod method, int i) {
                  if (i == 0) {
                    return new TypeReference[] {klass.getReference()};
                  } else {
                    return super.makeParameterTypes(method, i);
                  }
                }
              };
          ef.addCall((AbstractRootMethod) callGraph.getFakeRootNode().getMethod());
          getBuilder().markChanged(callGraph.getFakeRootNode());
        }
      }
    }

    /**
     * TODO: lift most of this logic to PropagationCallGraphBuilder
     *
     * <p>Add a call to the class initializer from the root method.
     */
    protected void processClassInitializer(IClass klass) {

      assert klass != null;

      if (!getBuilder().getOptions().getHandleStaticInit()) {
        return;
      }

      if (getBuilder().clinitVisited.contains(klass)) {
        return;
      }
      getBuilder().clinitVisited.add(klass);

      if (klass.getClassInitializer() != null) {
        if (DEBUG) {
          System.err.println("process class initializer for " + klass);
        }

        // add an invocation from the fake root method to the <clinit>
        MethodReference m = klass.getClassInitializer().getReference();
        CallSiteReference site = CallSiteReference.make(1, m, IInvokeInstruction.Dispatch.STATIC);
        IMethod targetMethod =
            getOptions()
                .getMethodTargetSelector()
                .getCalleeTarget(callGraph.getFakeRootNode(), site, null);
        if (targetMethod != null) {
          CGNode target = getTargetForCall(callGraph.getFakeRootNode(), site, null, null);
          if (target != null && callGraph.getPredNodeCount(target) == 0) {
            AbstractRootMethod fakeWorldClinitMethod =
                (AbstractRootMethod) callGraph.getFakeWorldClinitNode().getMethod();
            SSAAbstractInvokeInstruction s = fakeWorldClinitMethod.addInvocation(new int[0], site);
            PointerKey uniqueCatch =
                getBuilder().getPointerKeyForExceptionalReturnValue(callGraph.getFakeRootNode());
            getBuilder()
                .processResolvedCall(
                    callGraph.getFakeWorldClinitNode(), s, target, null, uniqueCatch);
          }
        }
      }

      IClass sc = klass.getSuperclass();
      if (sc != null) {
        processClassInitializer(sc);
      }
    }
  }

  /**
   * Add constraints for a call site after we have computed a reachable target for the dispatch
   *
   * <p>Side effect: add edge to the call graph.
   *
   * @param constParams if non-null, then constParams[i] holds the set of instance keys that are
   *     passed as param i, or null if param i is not invariant
   * @param uniqueCatchKey if non-null, then this is the unique PointerKey that catches all
   *     exceptions from this call site.
   */
  private void processResolvedCall(
      CGNode caller,
      SSAAbstractInvokeInstruction instruction,
      CGNode target,
      InstanceKey[][] constParams,
      PointerKey uniqueCatchKey) {

    if (DEBUG) {
      System.err.println("processResolvedCall: " + caller + " ," + instruction + " , " + target);
    }

    if (DEBUG) {
      System.err.println("addTarget: " + caller + " ," + instruction + " , " + target);
    }
    caller.addTarget(instruction.getCallSite(), target);

    if (callGraph.getFakeRootNode().equals(caller)) {
      if (entrypointCallSites.contains(instruction.getCallSite())) {
        callGraph.registerEntrypoint(target);
      }
    }

    if (!haveAlreadyVisited(target)) {
      markDiscovered(target);
    }

    processCallingConstraints(caller, instruction, target, constParams, uniqueCatchKey);
  }

  @SuppressWarnings("unused")
  protected void processCallingConstraints(
      CGNode caller,
      SSAAbstractInvokeInstruction instruction,
      CGNode target,
      InstanceKey[][] constParams,
      PointerKey uniqueCatchKey) {
    // TODO: i'd like to enable this optimization, but it's a little tricky
    // to recover the implicit points-to sets with recursion. TODO: don't
    // be lazy and code the recursive logic to enable this.
    // if (hasNoInstructions(target)) {
    // // record points-to sets for formals implicitly .. computed on
    // // demand.
    // // TODO: generalize this by using hasNoInterestingUses on parameters.
    // // however .. have to be careful to cache results in that case ... don't
    // // want
    // // to recompute du each time we process a call to Object.<init> !
    // for (int i = 0; i < instruction.getNumberOfUses(); i++) {
    // // we rely on the invariant that the value number for the ith parameter
    // // is i+1
    // final int vn = i + 1;
    // PointerKey formal = getPointerKeyForLocal(target, vn);
    // if (target.getMethod().getParameterType(i).isReferenceType()) {
    // system.recordImplicitPointsToSet(formal);
    // }
    // }
    // } else {
    // generate contraints from parameter passing
    int nUses = instruction.getNumberOfPositionalParameters();
    int nExpected = target.getMethod().getNumberOfParameters();

    /*
     * int nExpected = target.getMethod().getReference().getNumberOfParameters(); if (!target.getMethod().isStatic() &&
     * !target.getMethod().isClinit()) { nExpected++; }
     */

    if (nUses != nExpected) {
      // some sort of unverifiable code mismatch. give up.
      return;
    }

    // we're a little sloppy for now ... we don't filter calls to
    // java.lang.Object.
    // TODO: we need much more precise filters than cones in order to handle
    // the various types of dispatch logic. We need a filter that expresses
    // "the set of types s.t. x.foo resolves to y.foo."
    for (int i = 0; i < instruction.getNumberOfPositionalParameters(); i++) {
      if (target.getMethod().getParameterType(i).isReferenceType()) {
        PointerKey formal = getTargetPointerKey(target, i);
        if (constParams != null && constParams[i] != null) {
          InstanceKey[] ik = constParams[i];
          for (InstanceKey element : ik) {
            system.newConstraint(formal, element);
          }
        } else {
          if (instruction.getUse(i) < 0) {
            Assertions.UNREACHABLE("unexpected " + instruction + " in " + caller);
          }
          PointerKey actual = getPointerKeyForLocal(caller, instruction.getUse(i));
          if (formal instanceof FilteredPointerKey) {
            system.newConstraint(formal, filterOperator, actual);
          } else {
            system.newConstraint(formal, assignOperator, actual);
          }
        }
      }
    }

    // generate contraints from return value.
    if (instruction.hasDef() && instruction.getDeclaredResultType().isReferenceType()) {
      PointerKey result = getPointerKeyForLocal(caller, instruction.getDef());
      PointerKey ret = getPointerKeyForReturnValue(target);
      system.newConstraint(result, assignOperator, ret);
    }
    // generate constraints from exception return value.
    PointerKey e = getPointerKeyForLocal(caller, instruction.getException());
    PointerKey er = getPointerKeyForExceptionalReturnValue(target);
    if (SHORT_CIRCUIT_SINGLE_USES && uniqueCatchKey != null) {
      // e has exactly one use. so, represent e implicitly
      system.newConstraint(uniqueCatchKey, assignOperator, er);
    } else {
      system.newConstraint(e, assignOperator, er);
    }
    // }
  }

  /**
   * An operator to fire when we discover a potential new callee for a virtual or interface call
   * site.
   *
   * <p>This operator will create a new callee context and constraints if necessary.
   */
  final class DispatchOperator extends AbstractOperator<PointsToSetVariable>
      implements IPointerOperator {
    private final SSAAbstractInvokeInstruction call;

    private final CGNode node;

    private final InstanceKey[][] constParams;

    private final PointerKey uniqueCatch;

    /**
     * relevant parameter indices for the registered {@link ContextSelector}
     *
     * @see ContextSelector#getRelevantParameters(CGNode, CallSiteReference)
     */
    private final int[] dispatchIndices;

    /**
     * The set of instance keys that have already been processed. previousPtrs[i] contains the
     * processed instance keys for parameter position dispatchIndices[i]
     */
    private final MutableIntSet[] previousPtrs;

    /**
     * @param constParams if non-null, then constParams[i] holds the String constant that is passed
     *     as param i, or null if param i is not a String constant
     */
    DispatchOperator(
        SSAAbstractInvokeInstruction call,
        CGNode node,
        InstanceKey[][] constParams,
        PointerKey uniqueCatch,
        IntSet dispatchIndices) {
      this.call = call;
      this.node = node;
      this.constParams = constParams;
      this.uniqueCatch = uniqueCatch;
      this.dispatchIndices = IntSetUtil.toArray(dispatchIndices);
      // we better always be interested in the receiver
      // assert this.dispatchIndices[0] == 0;
      previousPtrs = new MutableIntSet[dispatchIndices.size()];
      Arrays.setAll(previousPtrs, i -> IntSetUtil.getDefaultIntSetFactory().make());
    }

    private byte cpa(final PointsToSetVariable[] rhs) {
      final MutableBoolean changed = new MutableBoolean();
      for (int rhsIndex = 0; rhsIndex < rhs.length; rhsIndex++) {
        final int y = rhsIndex;
        IntSet currentObjs = rhs[rhsIndex].getValue();
        if (currentObjs != null) {
          final IntSet oldObjs = previousPtrs[rhsIndex];

          currentObjs.foreachExcluding(
              oldObjs,
              x ->
                  new CrossProductRec(
                      constParams,
                      call,
                      node,
                      v -> {
                        IClass recv = null;
                        if (call.getCallSite().isDispatch()) {
                          recv = v[0].getConcreteType();
                        }

                        CGNode target = getTargetForCall(node, call.getCallSite(), recv, v);
                        if (target != null) {
                          changed.b = true;
                          processResolvedCall(node, call, target, constParams, uniqueCatch);
                          if (!haveAlreadyVisited(target)) {
                            markDiscovered(target);
                          }
                        }
                      }) {

                    {
                      rec(0, 0);
                    }

                    @Override
                    protected IntSet getParamObjects(int paramVn, int rhsi) {
                      if (rhsi == y) {
                        return IntSetUtil.make(new int[] {x});
                      } else {
                        return previousPtrs[rhsi];
                      }
                    }
                  });
          previousPtrs[rhsIndex].addAll(currentObjs);
        }
      }

      byte sideEffectMask = changed.b ? (byte) SIDE_EFFECT_MASK : 0;
      return (byte) (NOT_CHANGED | sideEffectMask);
    }

    /*
     * @see com.ibm.wala.dataflow.fixpoint.UnaryOperator#evaluate(com.ibm.wala.dataflow.fixpoint.IVariable,
     * com.ibm.wala.dataflow.fixpoint.IVariable)
     */
    @Override
    public byte evaluate(PointsToSetVariable lhs, final PointsToSetVariable[] rhs) {
      assert dispatchIndices.length >= rhs.length : "bad operator at " + call;

      return cpa(rhs);

      /*
      // did evaluating the dispatch operation add a new possible target
      // to the call site?
      final MutableBoolean addedNewTarget = new MutableBoolean();

      final MutableIntSet receiverVals;
      if (constParams != null && constParams[0] != null) {
        receiverVals = IntSetUtil.make();
        for(InstanceKey ik : constParams[0]) {
          receiverVals.add(system.getInstanceIndex(ik));
        }
      } else {
        receiverVals = rhs[0].getValue();
      }

      if (receiverVals == null) {
        // this constraint was put on the work list, probably by
        // initialization,
        // even though the right-hand-side is empty.
        // TODO: be more careful about what goes on the worklist to
        // avoid this.
        if (DEBUG) {
          System.err.println("EVAL dispatch with value null");
        }
        return NOT_CHANGED;

      }
      // we handle the parameter positions one by one, rather than enumerating
      // the cartesian product of possibilities. this disallows
      // context-sensitivity policies like true CPA, but is necessary for
      // performance.
      InstanceKey keys[] = new InstanceKey[constParams == null? dispatchIndices[dispatchIndices.length-1]+1: constParams.length];
      // determine whether we're handling a new receiver; used later
      // to check for redundancy
      boolean newReceiver = !receiverVals.isSubset(previousPtrs[0]);
      // keep separate rhsIndex, since it doesn't advance for constant
      // parameters
      int rhsIndex = (constParams != null && constParams[0] != null)? 0: 1;
      // this flag is set to true if we ever call handleAllReceivers() in the
      // loop below. we need to catch the case where we have a new receiver, but
      // there are no other dispatch indices with new values
      boolean propagatedReceivers = false;
      // we start at index 1 since we need to handle the receiver specially; see
      // below
      for (int index = 1; index < dispatchIndices.length; index++) {
        try {
          MonitorUtil.throwExceptionIfCanceled(monitor);
        } catch (CancelException e) {
          throw new CancelRuntimeException(e);
        }
        int paramIndex = dispatchIndices[index];
        assert keys[paramIndex] == null;
        final MutableIntSet prevAtIndex = previousPtrs[index];
        if (constParams != null && constParams[paramIndex] != null) {
          // we have a constant parameter.  only need to propagate again if we've never done it before or if we have a new receiver
          if (newReceiver || prevAtIndex.isEmpty()) {
            for(int i = 0; i < constParams[paramIndex].length; i++) {
              keys[paramIndex] = constParams[paramIndex][i];
              handleAllReceivers(receiverVals,keys, addedNewTarget);
              propagatedReceivers = true;
              int ii = system.instanceKeys.getMappedIndex(constParams[paramIndex][i]);
              prevAtIndex.add(ii);
            }
          }
        } else { // non-constant parameter
          PointsToSetVariable v = rhs[rhsIndex];
          if (v.getValue() != null) {
            IntIterator ptrs = v.getValue().intIterator();
            while (ptrs.hasNext()) {
              int ptr = ptrs.next();
              if (newReceiver || !prevAtIndex.contains(ptr)) {
                keys[paramIndex] = system.getInstanceKey(ptr);
                handleAllReceivers(receiverVals,keys, addedNewTarget);
                propagatedReceivers = true;
                prevAtIndex.add(ptr);
              }
            }
          }
          rhsIndex++;
        }
        keys[paramIndex] = null;
      }
      if (newReceiver) {
        if (!propagatedReceivers) {
          // we have a new receiver value, and it wasn't propagated at all,
          // so propagate it now
          handleAllReceivers(receiverVals, keys, addedNewTarget);
        }
        // update receiver cache
        previousPtrs[0].addAll(receiverVals);
      }

      byte sideEffectMask = addedNewTarget.b ? (byte) SIDE_EFFECT_MASK : 0;
      return (byte) (NOT_CHANGED | sideEffectMask);
      */
    }

    @SuppressWarnings("unused")
    private void handleAllReceivers(
        MutableIntSet receiverVals, InstanceKey[] keys, MutableBoolean sideEffect) {
      assert keys[0] == null;
      IntIterator receiverIter = receiverVals.intIterator();
      while (receiverIter.hasNext()) {
        final int rcvr = receiverIter.next();
        keys[0] = system.getInstanceKey(rcvr);
        if (clone2Assign) {
          // for efficiency: assume that only call sites that reference
          // clone() might dispatch to clone methods
          if (call.getCallSite().getDeclaredTarget().getSelector().equals(cloneSelector)) {
            IClass recv = (keys[0] != null) ? keys[0].getConcreteType() : null;
            IMethod targetMethod =
                getOptions()
                    .getMethodTargetSelector()
                    .getCalleeTarget(node, call.getCallSite(), recv);
            if (targetMethod != null
                && targetMethod.getReference().equals(CloneInterpreter.CLONE)) {
              // treat this call to clone as an assignment
              PointerKey result = getPointerKeyForLocal(node, call.getDef());
              PointerKey receiver = getPointerKeyForLocal(node, call.getReceiver());
              system.newConstraint(result, assignOperator, receiver);
              return;
            }
          }
        }
        CGNode target = getTargetForCall(node, call.getCallSite(), keys[0].getConcreteType(), keys);
        if (target == null) {
          // This indicates an error; I sure hope getTargetForCall
          // raised a warning about this!
          if (DEBUG) {
            System.err.println("Warning: null target for call " + call);
          }
        } else {
          IntSet targets = getCallGraph().getPossibleTargetNumbers(node, call.getCallSite());
          // even if we've seen this target before, if we have constant
          // parameters, we may need to re-process the call, as the constraints
          // for the first time we reached this target may not have been fully
          // general. TODO a more refined check?
          if (targets != null && targets.contains(target.getGraphNodeId()) && noConstParams()) {
            // do nothing; we've previously discovered and handled this
            // receiver for this call site.
          } else {
            // process the newly discovered target for this call
            sideEffect.b = true;
            processResolvedCall(node, call, target, constParams, uniqueCatch);
            if (!haveAlreadyVisited(target)) {
              markDiscovered(target);
            }
          }
        }
      }
      keys[0] = null;
    }

    private boolean noConstParams() {
      if (constParams != null) {
        for (int i = 0; i < constParams.length; i++) {
          if (constParams[i] != null) {
            for (int j = 0; j < constParams[i].length; i++) {
              if (constParams[i][j] != null) {
                return false;
              }
            }
          }
        }
      }
      return true;
    }

    @Override
    public String toString() {
      return "Dispatch to " + call + " in node " + node;
    }

    @Override
    public int hashCode() {
      int h = 1;
      if (constParams != null) {
        for (InstanceKey[] cs : constParams) {
          if (cs != null) {
            for (InstanceKey c : cs) {
              if (c != null) {
                h ^= c.hashCode();
              }
            }
          }
        }
      }
      return h * node.hashCode() + 90289 * call.hashCode();
    }

    @Override
    public boolean equals(Object o) {
      // note that these are not necessarily canonical, since
      // with synthetic factories we may regenerate constraints
      // many times. TODO: change processing of synthetic factories
      // so that we guarantee to insert each dispatch equation
      // only once ... if this were true we could optimize this
      // with reference equality

      // instanceof is OK because this class is final
      if (o instanceof DispatchOperator) {
        DispatchOperator other = (DispatchOperator) o;
        return node.equals(other.node)
            && call.equals(other.call)
            && Arrays.deepEquals(constParams, other.constParams);
      } else {
        return false;
      }
    }

    /*
     * @see com.ibm.wala.ipa.callgraph.propagation.IPointerOperator#isComplex()
     */
    @Override
    public boolean isComplex() {
      return true;
    }
  }

  protected void iterateCrossProduct(
      final CGNode caller,
      final SSAAbstractInvokeInstruction call,
      final InstanceKey[][] invariants,
      final Consumer<InstanceKey[]> f) {
    new CrossProductRec(invariants, call, caller, f).rec(0, 0);
  }

  protected Set<CGNode> getTargetsForCall(
      final CGNode caller, final SSAAbstractInvokeInstruction instruction, InstanceKey[][] invs) {
    // This method used to take a CallSiteReference as a parameter, rather than
    // an SSAAbstractInvokeInstruction. This was bad, since it's
    // possible for multiple invoke instructions with different actual
    // parameters to be associated with a single CallSiteReference. Changed
    // to take the invoke instruction as a parameter instead, since invs is
    // associated with the instruction
    final CallSiteReference site = instruction.getCallSite();
    final Set<CGNode> targets = HashSetFactory.make();
    Consumer<InstanceKey[]> f =
        v -> {
          IClass recv = null;
          if (site.isDispatch()) {
            recv = v[0].getConcreteType();
          }
          CGNode target = getTargetForCall(caller, site, recv, v);
          if (target != null) {
            targets.add(target);
          }
        };
    iterateCrossProduct(caller, instruction, invs, f);
    return targets;
  }

  private IntSet getRelevantParameters(final CGNode caller, final CallSiteReference site)
      throws UnimplementedError {
    IntSet params = contextSelector.getRelevantParameters(caller, site);
    if (!site.isStatic() && !params.contains(0)) {
      params = IntSetUtil.makeMutableCopy(params);
      ((MutableIntSet) params).add(0);
    }
    return params;
  }

  public boolean hasNoInterestingUses(CGNode node, int vn, DefUse du) {

    if (du == null) {
      throw new IllegalArgumentException("du is null");
    }
    if (vn <= 0) {
      throw new IllegalArgumentException("v is invalid: " + vn);
    }
    // todo: enhance this by solving a dead-code elimination
    // problem.
    InterestingVisitor v = makeInterestingVisitor(node, vn);
    for (SSAInstruction s : Iterator2Iterable.make(du.getUses(v.vn))) {
      s.visit(v);
      if (v.bingo) {
        return false;
      }
    }
    return true;
  }

  protected InterestingVisitor makeInterestingVisitor(
      @SuppressWarnings("unused") CGNode node, int vn) {
    return new InterestingVisitor(vn);
  }

  /** sets bingo to true when it visits an interesting instruction */
  protected static class InterestingVisitor extends SSAInstruction.Visitor {
    protected final int vn;

    public InterestingVisitor(int vn) {
      this.vn = vn;
    }

    protected boolean bingo = false;

    @Override
    public void visitArrayLoad(SSAArrayLoadInstruction instruction) {
      if (!instruction.typeIsPrimitive() && instruction.getArrayRef() == vn) {
        bingo = true;
      }
    }

    @Override
    public void visitArrayStore(SSAArrayStoreInstruction instruction) {
      if (!instruction.typeIsPrimitive()
          && (instruction.getArrayRef() == vn || instruction.getValue() == vn)) {
        bingo = true;
      }
    }

    @Override
    public void visitCheckCast(SSACheckCastInstruction instruction) {
      bingo = true;
    }

    @Override
    public void visitGet(SSAGetInstruction instruction) {
      FieldReference field = instruction.getDeclaredField();
      if (!field.getFieldType().isPrimitiveType()) {
        bingo = true;
      }
    }

    @Override
    public void visitGetCaughtException(SSAGetCaughtExceptionInstruction instruction) {
      bingo = true;
    }

    @Override
    public void visitInvoke(SSAInvokeInstruction instruction) {
      bingo = true;
    }

    @Override
    public void visitPhi(SSAPhiInstruction instruction) {
      bingo = true;
    }

    @Override
    public void visitPi(SSAPiInstruction instruction) {
      bingo = true;
    }

    @Override
    public void visitPut(SSAPutInstruction instruction) {
      FieldReference field = instruction.getDeclaredField();
      if (!field.getFieldType().isPrimitiveType()) {
        bingo = true;
      }
    }

    @Override
    public void visitReturn(SSAReturnInstruction instruction) {
      bingo = true;
    }

    @Override
    public void visitThrow(SSAThrowInstruction instruction) {
      bingo = true;
    }
  }

  /**
   * TODO: enhance this logic using type inference
   *
   * @return true if we need to filter the receiver type to account for virtual dispatch
   */
  @SuppressWarnings("unused")
  private boolean needsFilterForReceiver(SSAAbstractInvokeInstruction instruction, CGNode target) {

    FilteredPointerKey.TypeFilter f =
        (FilteredPointerKey.TypeFilter) target.getContext().get(ContextKey.PARAMETERS[0]);

    if (f != null) {
      // the context selects a particular concrete type for the receiver.
      // we need to filter, unless the declared receiver type implies the
      // concrete type (TODO: need to implement this optimization)
      return true;
    }

    // don't need to filter for invokestatic
    if (instruction.getCallSite().isStatic() || instruction.getCallSite().isSpecial()) {
      return false;
    }

    MethodReference declaredTarget = instruction.getDeclaredTarget();
    IMethod resolvedTarget = getClassHierarchy().resolveMethod(declaredTarget);
    // if resolvedTarget == null, then there's some problem that will be flagged as a warning

    return true;
  }

  private static boolean isRootType(IClass klass) {
    return klass.getClassHierarchy().isRootClass(klass);
  }

  @SuppressWarnings("unused")
  private static boolean isRootType(FilteredPointerKey.TypeFilter filter) {
    if (filter instanceof FilteredPointerKey.SingleClassFilter) {
      return isRootType(((FilteredPointerKey.SingleClassFilter) filter).getConcreteType());
    } else {
      return false;
    }
  }

  /**
   * TODO: enhance this logic using type inference TODO!!!: enhance filtering to consider concrete
   * types, not just cones. precondition: needs Filter
   *
   * @return an IClass which represents
   */
  public PointerKey getTargetPointerKey(CGNode target, int index) {
    int vn;
    if (target.getIR() != null) {
      vn = target.getIR().getSymbolTable().getParameter(index);
    } else {
      vn = index + 1;
    }

    FilteredPointerKey.TypeFilter filter =
        (FilteredPointerKey.TypeFilter) target.getContext().get(ContextKey.PARAMETERS[index]);
    if (filter != null && !filter.isRootFilter()) {
      return getFilteredPointerKeyForLocal(target, vn, filter);

    } else {
      // the context does not select a particular concrete type for the
      // receiver, so use the type of the method
      IClass C;
      if (index == 0 && !target.getMethod().isStatic()) {
        C = getReceiverClass(target.getMethod());
      } else {
        C = cha.lookupClass(target.getMethod().getParameterType(index));
      }

      if (C == null || C.getClassHierarchy().getRootClass().equals(C)) {
        return getPointerKeyForLocal(target, vn);
      } else {
        return getFilteredPointerKeyForLocal(
            target, vn, new FilteredPointerKey.SingleClassFilter(C));
      }
    }
  }

  /** @return the receiver class for this method. */
  private IClass getReceiverClass(IMethod method) {
    TypeReference formalType = method.getParameterType(0);
    IClass C = getClassHierarchy().lookupClass(formalType);
    if (method.isStatic()) {
      Assertions.UNREACHABLE("asked for receiver of static method " + method);
    }
    if (C == null) {
      Assertions.UNREACHABLE("no class found for " + formalType + " recv of " + method);
    }
    return C;
  }

  /**
   * A value is "invariant" if we can figure out the instances it can ever point to locally, without
   * resorting to propagation.
   *
   * @return true iff the contents of the local with this value number can be deduced locally,
   *     without propagation
   */
  public boolean contentsAreInvariant(SymbolTable symbolTable, DefUse du, int valueNumber) {
    if (isConstantRef(symbolTable, valueNumber)) {
      return true;
    } else if (SHORT_CIRCUIT_INVARIANT_SETS) {
      SSAInstruction def = du.getDef(valueNumber);
      if (def instanceof SSANewInstruction) {
        return true;
      } else {
        return false;
      }
    } else {
      return false;
    }
  }

  protected boolean contentsAreInvariant(SymbolTable symbolTable, DefUse du, int valueNumbers[]) {
    for (int valueNumber : valueNumbers) {
      if (!contentsAreInvariant(symbolTable, du, valueNumber)) {
        return false;
      }
    }
    return true;
  }

  /**
   * precondition:contentsAreInvariant(valueNumber)
   *
   * @return the complete set of instances that the local with vn=valueNumber may point to.
   */
  public InstanceKey[] getInvariantContents(
      SymbolTable symbolTable, DefUse du, CGNode node, int valueNumber, HeapModel hm) {
    return getInvariantContents(symbolTable, du, node, valueNumber, hm, false);
  }

  protected InstanceKey[] getInvariantContents(
      SymbolTable symbolTable,
      DefUse du,
      CGNode node,
      int valueNumber,
      HeapModel hm,
      boolean ensureIndexes) {
    InstanceKey[] result;
    if (isConstantRef(symbolTable, valueNumber)) {
      Object x = symbolTable.getConstantValue(valueNumber);
      if (x instanceof String) {
        // this is always the case in Java. use strong typing in the call to
        // getInstanceKeyForConstant.
        String S = (String) x;
        TypeReference type =
            node.getMethod().getDeclaringClass().getClassLoader().getLanguage().getConstantType(S);
        if (type == null) {
          return new InstanceKey[0];
        }
        InstanceKey ik = hm.getInstanceKeyForConstant(type, S);
        if (ik != null) {
          result = new InstanceKey[] {ik};
        } else {
          result = new InstanceKey[0];
        }
      } else {
        // some non-built in type (e.g. Integer). give up on strong typing.
        // language-specific subclasses (e.g. Javascript) should override this method to get strong
        // typing
        // with generics if desired.
        TypeReference type =
            node.getMethod().getDeclaringClass().getClassLoader().getLanguage().getConstantType(x);
        if (type == null) {
          return new InstanceKey[0];
        }
        InstanceKey ik = hm.getInstanceKeyForConstant(type, x);
        if (ik != null) {
          result = new InstanceKey[] {ik};
        } else {
          result = new InstanceKey[0];
        }
      }
    } else {
      SSANewInstruction def = (SSANewInstruction) du.getDef(valueNumber);
      InstanceKey iKey = hm.getInstanceKeyForAllocation(node, def.getNewSite());
      result = (iKey == null) ? new InstanceKey[0] : new InstanceKey[] {iKey};
    }

    if (ensureIndexes) {
      for (InstanceKey element : result) {
        system.findOrCreateIndexForInstanceKey(element);
      }
    }

    return result;
  }

  protected boolean isConstantRef(SymbolTable symbolTable, int valueNumber) {
    if (valueNumber == -1) {
      return false;
    }
    if (symbolTable.isConstant(valueNumber)) {
      Object v = symbolTable.getConstantValue(valueNumber);
      return (!(v instanceof Number));
    } else {
      return false;
    }
  }

  /**
   * @author sfink
   *     <p>A warning for when we fail to resolve the type for a checkcast
   */
  private static class CheckcastFailure extends Warning {

    final TypeReference type;

    CheckcastFailure(TypeReference type) {
      super(Warning.SEVERE);
      this.type = type;
    }

    @Override
    public String getMsg() {
      return getClass().toString() + " : " + type;
    }

    public static CheckcastFailure create(TypeReference type) {
      return new CheckcastFailure(type);
    }
  }

  /**
   * @author sfink
   *     <p>A warning for when we fail to resolve the type for a field
   */
  private static class FieldResolutionFailure extends Warning {

    final FieldReference field;

    FieldResolutionFailure(FieldReference field) {
      super(Warning.SEVERE);
      this.field = field;
    }

    @Override
    public String getMsg() {
      return getClass().toString() + " : " + field;
    }

    public static FieldResolutionFailure create(FieldReference field) {
      return new FieldResolutionFailure(field);
    }
  }

  /*
   * @see com.ibm.wala.ipa.callgraph.propagation.HeapModel#iteratePointerKeys()
   */
  @Override
  public Iterator<PointerKey> iteratePointerKeys() {
    return system.iteratePointerKeys();
  }

  public static Set<IClass> getCaughtExceptionTypes(
      SSAGetCaughtExceptionInstruction instruction, IRView ir) {
    if (ir == null) {
      throw new IllegalArgumentException("ir is null");
    }
    if (instruction == null) {
      throw new IllegalArgumentException("instruction is null");
    }
    Iterator<TypeReference> exceptionTypes =
        ((ExceptionHandlerBasicBlock)
                ir.getControlFlowGraph().getNode(instruction.getBasicBlockNumber()))
            .getCaughtExceptionTypes();
    HashSet<IClass> types = HashSetFactory.make(10);
    for (TypeReference tr : Iterator2Iterable.make(exceptionTypes)) {
      IClass c = ir.getMethod().getClassHierarchy().lookupClass(tr);
      if (c != null) {
        types.add(c);
      }
    }
    return types;
  }

  @Override
  public InstanceKey getInstanceKeyForPEI(CGNode node, ProgramCounter instr, TypeReference type) {
    return getInstanceKeyForPEI(node, instr, type, instanceKeyFactory);
  }

  /*
   * @see com.ibm.wala.ipa.callgraph.propagation.PropagationCallGraphBuilder#makeSolver()
   */
  @Override
  protected IPointsToSolver makeSolver() {
    return new StandardSolver(system, this);
    // return usePreTransitiveSolver ? (IPointsToSolver) new PreTransitiveSolver(system, this) : new
    // StandardSolver(system, this);
    // return true ? (IPointsToSolver)new PreTransitiveSolver(system,this) : new
    // StandardSolver(system,this);
  }
}
