Skip to content

Ghidra is a software reverse engineering (SRE) framework

215 KB
Raw Blame
/* ###
 * IP: GHIDRA
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
#include "coreaction.hh"
#include "condexe.hh"
#include "double.hh"
#include "subflow.hh"
#include "constseq.hh"
#include "bitfield.hh"

namespace ghidra {

/// \brief A stack equation
struct StackEqn {
  int4 var1;			///< Variable with 1 coefficient
  int4 var2;			///< Variable with -1 coefficient
  int4 rhs;			///< Right hand side of the equation
  static bool compare(const StackEqn &a,const StackEqn &b);	///< Order two equations
};

/// \brief A class that solves for stack-pointer changes across unknown sub-functions
class StackSolver {
  vector<StackEqn> eqs;		///< Known equations based on operations that explicitly change the stack-pointer
  vector<StackEqn> guess;	///< Guessed equations for underdetermined systems
  vector<Varnode *> vnlist;	///< The indexed set of variables, one for each reference to the stack-pointer
  vector<int4> companion;	///< Index of companion input for variable produced by CPUI_INDIRECT
  Address spacebase;		///< Starting address of the stack-pointer
  vector<int4> soln;		///< Collected solutions (corresponding to array of variables)
  int4 missedvariables;		///< Number of variables for which we are missing an equation
  void duplicate(void);		///< Duplicate each equation, multiplying by -1
  void propagate(int4 varnum,int4 val);	///< Propagate solution for one variable to other variables
public:
  void solve(void);		///< Solve the system of equations
  void build(const Funcdata &data,AddrSpace *id,int4 spcbase);	///< Build the system of equations
  int4 getNumVariables(void) const { return vnlist.size(); }	///< Get the number of variables in the system
  Varnode *getVariable(int4 i) const { return vnlist[i]; }	///< Get the i-th Varnode variable
  int4 getCompanion(int4 i) const { return companion[i]; }	///< Get the i-th variable's companion index
  int4 getSolution(int4 i) const { return soln[i]; }		///< Get the i-th variable's solution
};

/// \param a is the first equation to compare
/// \param b is the second
/// \return true if the first equation comes before the second
bool StackEqn::compare(const StackEqn &a,const StackEqn &b)

{
  return (a.var1<b.var1);
}

/// Given a solution for one variable, look for equations containing the variable
/// and attempt to solve for the other variable. Continue propagating new
/// solutions to other equations to find even more solutions.  Populate
/// the \b soln array with the solutions.
/// \param varnum is the index of the initial variable
/// \param val is the solution for the variable
void StackSolver::propagate(int4 varnum,int4 val)

{
  if (soln[varnum] != 65535) return; // This variable already specified
  soln[varnum] = val;

  StackEqn eqn;
  vector<int4> workstack;
  workstack.reserve(soln.size());
  workstack.push_back(varnum);
  vector<StackEqn>::iterator top;

  while(!workstack.empty()) {
    varnum = workstack.back();
    workstack.pop_back();

    eqn.var1 = varnum;
    top = lower_bound(eqs.begin(),eqs.end(),eqn,StackEqn::compare);
    while((top!=eqs.end())&&((*top).var1 == varnum)) {
      int4 var2 = (*top).var2;
      if (soln[var2] == 65535) {
	soln[var2] = soln[varnum]-(*top).rhs;
	workstack.push_back(var2);
      }
      ++top;
    }
  }
}

void StackSolver::duplicate(void)

{
  int4 size,i;
  StackEqn eqn;

  size = eqs.size();
  for(i=0;i<size;++i) {
    eqn.var1 = eqs[i].var2;
    eqn.var2 = eqs[i].var1;
    eqn.rhs = -eqs[i].rhs;
    eqs.push_back(eqn);
  }
  stable_sort(eqs.begin(),eqs.end(),StackEqn::compare);
}

void StackSolver::solve(void)

{
  // Use guesses to resolve subsystems not uniquely determined
  int4 i,size,var1,var2,count,lastcount;

  soln.clear();
  soln.resize(vnlist.size(),65535); // Initialize solutions vector
  duplicate();			// Duplicate and sort the equations

  propagate(0,0);		// We know one variable
  size = guess.size();
  lastcount = size+2;
  do {
    count = 0;
    for(i=0;i<size;++i) {
      var1 = guess[i].var1;
      var2 = guess[i].var2;
      if ((soln[var1]!=65535)&&(soln[var2]==65535))
	propagate(var2,soln[var1]-guess[i].rhs);
      else if ((soln[var1]==65535)&&(soln[var2]!=65535))
	propagate(var1,soln[var2]+guess[i].rhs);
      else if ((soln[var1]==65535)&&(soln[var2]==65535))
	count += 1;
    }
    if (count == lastcount) break;
    lastcount = count;
  } while(count > 0);
}

/// Collect references to the stack-pointer as variables, and examine their defining PcodeOps
/// to determine equations and coefficient.
/// \param data is the function being analyzed
/// \param id is the \e stack address space
/// \param spcbase is the index, relative to the stack space, of the stack pointer
void StackSolver::build(const Funcdata &data,AddrSpace *id,int4 spcbase)

{
  const VarnodeData &spacebasedata(id->getSpacebase(spcbase));
  spacebase = Address(spacebasedata.space,spacebasedata.offset);
  VarnodeLocSet::const_iterator begiter,enditer;

  begiter = data.beginLoc(spacebasedata.size,spacebase);
  enditer = data.endLoc(spacebasedata.size,spacebase);

  while(begiter != enditer) {	// All instances of the spacebase
    if ((*begiter)->isFree()) break;
    vnlist.push_back(*begiter);
    companion.push_back(-1);
    ++begiter;
  }
  missedvariables = 0;
  if (vnlist.empty()) return;
  if (!vnlist[0]->isInput())
    throw LowlevelError("Input value of stackpointer is not used");

  vector<Varnode *>::iterator iter;
  StackEqn eqn;
  for(int4 i=1;i<vnlist.size();++i) {
    Varnode *vn = vnlist[i];
    Varnode *othervn,*constvn;
    PcodeOp *op = vn->getDef();

    if (op->code() == CPUI_INT_ADD) {
      othervn = op->getIn(0);
      constvn = op->getIn(1);
      if (othervn->isConstant()) {
	constvn = othervn;
	othervn = op->getIn(1);
      }
      if (!constvn->isConstant()) { missedvariables+=1; continue; }
      if (othervn->getAddr() != spacebase) { missedvariables+=1; continue; }
      iter = lower_bound(vnlist.begin(),vnlist.end(),othervn,Varnode::comparePointers);
      eqn.var1 = i;
      eqn.var2 = iter-vnlist.begin();
      eqn.rhs = constvn->getOffset();
      eqs.push_back(eqn);
    }
    else if (op->code() == CPUI_COPY) {
      othervn = op->getIn(0);
      if (othervn->getAddr() != spacebase) { missedvariables+=1; continue; }
      iter = lower_bound(vnlist.begin(),vnlist.end(),othervn,Varnode::comparePointers);
      eqn.var1 = i;
      eqn.var2 = iter-vnlist.begin();
      eqn.rhs = 0;
      eqs.push_back(eqn);
    }
    else if (op->code() == CPUI_INDIRECT) {
      othervn = op->getIn(0);
      if (othervn->getAddr() != spacebase) { missedvariables += 1; continue; }
      iter = lower_bound(vnlist.begin(),vnlist.end(),othervn,Varnode::comparePointers);
      eqn.var1 = i;
      eqn.var2 = iter-vnlist.begin();
      companion[i] = eqn.var2;
      Varnode *iopvn = op->getIn(1);
      if (iopvn->getSpace()->getType()==IPTR_IOP) { // If INDIRECT is due call
	PcodeOp *iop = PcodeOp::getOpFromConst(iopvn->getAddr());
	FuncCallSpecs *fc = data.getCallSpecs(iop); // Look up function proto
	if (fc != (FuncCallSpecs *)0) {
	  if (fc->getExtraPop() != ProtoModel::extrapop_unknown) { // Double check that extrapop is unknown
	    eqn.rhs = fc->getExtraPop(); // As the deindirect process may have filled it in
	    eqs.push_back(eqn);
	    continue;
	  }
	}
      }

      eqn.rhs = 4;		// Otherwise make a guess
      guess.push_back(eqn);
    }
    else if (op->code() == CPUI_MULTIEQUAL) {
      for(int4 j=0;j<op->numInput();++j) {
	othervn = op->getIn(j);
	if (othervn->getAddr() != spacebase) { missedvariables += 1; continue; }
	iter = lower_bound(vnlist.begin(),vnlist.end(),othervn,Varnode::comparePointers);
	eqn.var1 = i;
	eqn.var2 = iter-vnlist.begin();
	eqn.rhs = 0;
	eqs.push_back(eqn);
      }
    }
    else if (op->code() == CPUI_INT_AND) {
      // This can occur if a function aligns its stack pointer
      othervn = op->getIn(0);
      constvn = op->getIn(1);
      if (othervn->isConstant()) {
	constvn = othervn;
	othervn = op->getIn(1);
      }
      if (!constvn->isConstant()) { missedvariables+=1; continue; }
      if (othervn->getAddr() != spacebase) { missedvariables+=1; continue; }
      iter = lower_bound(vnlist.begin(),vnlist.end(),othervn,Varnode::comparePointers);
      eqn.var1 = i;
      eqn.var2 = iter-vnlist.begin();
      eqn.rhs = 0;		// Treat this as a copy
      eqs.push_back(eqn);
    }
    else
      missedvariables += 1;
  }
}

/// \brief Calculate stack-pointer change across \e undetermined sub-functions
///
/// If there are sub-functions for which \e extra \e pop is not explicit,
/// do full linear analysis to (attempt to) recover the values.
/// \param data is the function to analyze
/// \param stackspace is the space associated with the stack-pointer
/// \param spcbase is the index (relative to the stackspace) of the stack-pointer
void ActionStackPtrFlow::analyzeExtraPop(Funcdata &data,AddrSpace *stackspace,int4 spcbase)

{
  ProtoModel *myfp = data.getArch()->evalfp_called;
  if (myfp == (ProtoModel *)0)
    myfp = data.getArch()->defaultfp;
  if (myfp->getExtraPop()!=ProtoModel::extrapop_unknown) return;

  StackSolver solver;
  try {
    solver.build(data,stackspace,spcbase);
  } catch(LowlevelError &err) {
    ostringstream s;
    s << "Stack frame is not setup normally: " << err.explain;
    data.warningHeader(s.str());
    return;
  }
  if (solver.getNumVariables() == 0) return;
  solver.solve();		// Solve the equations

  Varnode *invn = solver.getVariable(0);
  bool warningprinted = false;

  for(int4 i=1;i<solver.getNumVariables();++i) {
    Varnode *vn = solver.getVariable(i);
    int4 soln = solver.getSolution(i);
    if (soln == 65535) {
      if (!warningprinted) {
	data.warningHeader("Unable to track spacebase fully for "+stackspace->getName());
	warningprinted = true;
      }
      continue;
    }
    PcodeOp *op = vn->getDef();
    OpCode opc = op->code();

    if (opc == CPUI_INDIRECT) {
      Varnode *iopvn = op->getIn(1);
      if (iopvn->getSpace()->getType()==IPTR_IOP) {
	PcodeOp *iop = PcodeOp::getOpFromConst(iopvn->getAddr());
	FuncCallSpecs *fc = data.getCallSpecs(iop);
	if (fc != (FuncCallSpecs *)0) {
	  int4 soln2 = 0;
	  int4 comp = solver.getCompanion(i);
	  if (comp >= 0)
	    soln2 = solver.getSolution(comp);
	  fc->setEffectiveExtraPop(soln-soln2);
	}
      }
    }
    vector<Varnode *> paramlist;
    paramlist.push_back(invn);
    int4 sz = invn->getSize();
    paramlist.push_back(data.newConstant(sz,soln&calc_mask(sz)));
    data.opSetOpcode(op,CPUI_INT_ADD);
    data.opSetAllInput(op,paramlist);
    if (opc == CPUI_MULTIEQUAL) {
      BlockBasic *bb = op->getParent();
      data.opUninsert(op);
      data.opInsertBegin(op, bb);
    }
  }
  return;
}

/// \brief Is the given Varnode defined as a pointer relative to the stack-pointer?
///
/// Return true if -vn- is defined as the stackpointer input plus a constant (or zero)
/// This works through the general case and the special case when the constant is zero.
/// The constant value is passed-back to the caller.
/// \param spcbasein is the Varnode holding the \e input value of the stack-pointer
/// \param vn is the Varnode to check for relativeness
/// \param constval is a reference for passing back the constant offset
/// \return true if \b vn is stack relative
bool ActionStackPtrFlow::isStackRelative(Varnode *spcbasein,Varnode *vn,uintb &constval)

{
  if (spcbasein == vn) {
    constval = 0;
    return true;
  }
  if (!vn->isWritten()) return false;
  PcodeOp *addop = vn->getDef();
  if (addop->code() != CPUI_INT_ADD) return false;
  if (addop->getIn(0) != spcbasein) return false;
  Varnode *constvn = addop->getIn(1);
  if (!constvn->isConstant()) return false;
  constval = constvn->getOffset();
  return true;
}

/// \brief Adjust the LOAD where the stack-pointer alias has been recovered.
///
/// We've matched a LOAD with its matching store, now convert the LOAD op to a COPY of what was stored.
/// \param data is the function being analyzed
/// \param loadop is the LOAD op to adjust
/// \param storeop is the matching STORE op
/// \return true if the adjustment is successful
bool ActionStackPtrFlow::adjustLoad(Funcdata &data,PcodeOp *loadop,PcodeOp *storeop)

{
  Varnode *vn = storeop->getIn(2);
  if (vn->isConstant())
    vn = data.newConstant(vn->getSize(),vn->getOffset());
  else if (vn->isFree())
    return false;

  data.opRemoveInput(loadop,1);
  data.opSetOpcode(loadop,CPUI_COPY);
  data.opSetInput(loadop,vn,0);
  return true;
}

/// \brief Link LOAD to matching STORE of a constant
///
/// Try to find STORE op using same stack relative pointer as a given LOAD op.
/// If we find it and the STORE stores a constant, change the LOAD to a COPY.
/// \param data is the function owning the LOAD
/// \param id is the stackspace
/// \param spcbasein is the stack-pointer
/// \param loadop is the given LOAD op
/// \param constz is the stack relative offset of the LOAD pointer
/// \return 1 if we successfully change LOAD to COPY, 0 otherwise
int4 ActionStackPtrFlow::repair(Funcdata &data,AddrSpace *id,Varnode *spcbasein,PcodeOp *loadop,uintb constz)

{
  int4 loadsize = loadop->getOut()->getSize();
  BlockBasic *curblock = loadop->getParent();
  list<PcodeOp *>::iterator begiter = curblock->beginOp();
  list<PcodeOp *>::iterator iter = loadop->getBasicIter();
  for(;;) {
    if (iter == begiter) {
      if (curblock->sizeIn() != 1) return 0; // Can trace back to next basic block if only one path
      curblock = (BlockBasic *)curblock->getIn(0);
      begiter = curblock->beginOp();
      iter = curblock->endOp();
      continue;
    }
    else {
      --iter;
    }
    PcodeOp *curop = *iter;
    if (curop->isCall()) return 0; // Don't try to trace aliasing through a call
    if (curop->code() == CPUI_STORE) {
      Varnode *ptrvn = curop->getIn(1);
      Varnode *datavn = curop->getIn(2);
      uintb constnew;
      if (isStackRelative(spcbasein,ptrvn,constnew)) {
	if ((constnew == constz)&&(loadsize == datavn->getSize())) {
	  // We found the matching store
	  if (adjustLoad(data,loadop,curop))
	    return 1;
	  return 0;
	}
	else if ((constnew <= constz + (loadsize-1))&&(constnew+(datavn->getSize()-1)>=constz))
	  return 0;
      }
      else
	return 0;		// Any other kind of STORE we can't solve aliasing
    }
    else {
      Varnode *outvn = curop->getOut();
      if (outvn != (Varnode *)0) {
	if (outvn->getSpace() == id) return 0; // Stack already traced, too late
      }
    }
  }
}

/// \brief Find any stack pointer clogs and pass it on to the repair routines
///
/// A stack pointer \b clog is a constant addition to the stack-pointer,
/// but where the constant comes from the stack.
/// \param data is the function to analyze
/// \param id is the stack space
/// \param spcbase is the index of the stack-pointer relative to the stack space
/// \return the number of clogs that were repaired
int4 ActionStackPtrFlow::checkClog(Funcdata &data,AddrSpace *id,int4 spcbase)

{
  const VarnodeData &spacebasedata(id->getSpacebase(spcbase));
  Address spacebase = Address(spacebasedata.space,spacebasedata.offset);
  VarnodeLocSet::const_iterator begiter,enditer;
  int4 clogcount = 0;

  begiter = data.beginLoc(spacebasedata.size,spacebase);
  enditer = data.endLoc(spacebasedata.size,spacebase);

  Varnode *spcbasein;
  if (begiter == enditer) return clogcount;
  spcbasein = *begiter;
  ++begiter;
  if (!spcbasein->isInput()) return clogcount;
  while(begiter != enditer) {
    Varnode *outvn = *begiter;
    ++begiter;
    if (!outvn->isWritten()) continue;
    PcodeOp *addop = outvn->getDef();
    if (addop->code() != CPUI_INT_ADD) continue;
    Varnode *y = addop->getIn(1);
    if (!y->isWritten()) continue; // y must not be a constant
    Varnode *x = addop->getIn(0); // is y is not constant than x (in position 0) isn't either
    uintb constx;
    if (!isStackRelative(spcbasein,x,constx)) {	// If x is not stack relative
      x = y;			// Swap x and y
      y = addop->getIn(0);
      if (!isStackRelative(spcbasein,x,constx)) continue; // Now maybe the new x is stack relative
    }
    PcodeOp *loadop = y->getDef();
    if (loadop->code() == CPUI_INT_MULT) { // If we multiply
      Varnode *constvn = loadop->getIn(1);
      if (!constvn->isConstant()) continue;
      if (constvn->getOffset() != calc_mask(constvn->getSize())) continue; // Must multiply by -1
      y = loadop->getIn(0);
      if (!y->isWritten()) continue;
      loadop = y->getDef();
    }
    if (loadop->code() != CPUI_LOAD) continue;
    Varnode *ptrvn = loadop->getIn(1);
    uintb constz;
    if (!isStackRelative(spcbasein,ptrvn,constz)) continue;
    clogcount += repair(data,id,spcbasein,loadop,constz);
  }
  return clogcount;
}

int4 ActionStackPtrFlow::apply(Funcdata &data)

{
  if (analysis_finished)
    return 0;
  if (stackspace == (AddrSpace *)0) {
    analysis_finished = true;		// No stack to do analysis on
    return 0;
  }
  int4 numchange = checkClog(data,stackspace,0);
  if (numchange > 0) {
    count += 1;
  }
  if (numchange == 0) {
    analyzeExtraPop(data,stackspace,0);
    analysis_finished = true;
  }
  return 0;
}

/// \brief Register a lane size suggested by a piece of a laned register
///
/// If the piece's size is itself an allowed lane size, it is registered. Otherwise the piece
/// is a run of smaller lanes (three floats taken from a four float vector, for instance) and
/// the largest allowed lane size that tiles both the piece and its offset within the register
/// is registered, provided the piece holds at least two such lanes.
/// \param size is the size of the piece in bytes
/// \param offset is the byte offset of the piece within the register
/// \param allowedLanes is used to determine if a putative lane size is allowed
/// \param checkLanes collects the possible lane sizes
void ActionLaneDivide::addPieceLaneSize(int4 size,int4 offset,const LanedRegister &allowedLanes,LanedRegister &checkLanes)

{
  if (allowedLanes.allowedLane(size)) {
    checkLanes.addLaneSize(size);			// Register this possible size
    return;
  }
  int4 best = 0;
  LanedRegister::const_iterator enditer = allowedLanes.end();
  for(LanedRegister::const_iterator iter=allowedLanes.begin();iter!=enditer;++iter) {
    int4 laneSize = *iter;
    if (laneSize * 2 > size) break;			// Sizes come smallest first
    if ((size % laneSize) == 0 && (offset % laneSize) == 0)
      best = laneSize;
  }
  if (best > 0)
    checkLanes.addLaneSize(best);
}

/// \brief Examine the PcodeOps using the given Varnode to determine possible lane sizes
///
/// Run through the defining op and any descendant ops of the given Varnode, looking for
/// CPUI_PIECE and CPUI_SUBPIECE. Use these to determine possible lane sizes and
/// register them with the given LanedRegister object. A piece whose size is not itself a lane
/// size suggests the largest lane size that tiles it (addPieceLaneSize); so does the input of
/// a defining CPUI_INT_ZEXT when it is not itself a lane size (a run of lanes under zero lanes).
/// \param vn is the given Varnode
/// \param allowedLanes is used to determine if a putative lane size is allowed
/// \param checkLanes collects the possible lane sizes
void ActionLaneDivide::collectLaneSizes(Varnode *vn,const LanedRegister &allowedLanes,LanedRegister &checkLanes)

{
  list<PcodeOp *>::const_iterator iter = vn->beginDescend();
  list<PcodeOp *>::const_iterator enditer = vn->endDescend();
  while(iter != enditer) {
    PcodeOp *op = *iter;
    ++iter;
    if (op->code() != CPUI_SUBPIECE) continue;	// Is the big register split into pieces
    addPieceLaneSize(op->getOut()->getSize(),(int4)op->getIn(1)->getOffset(),allowedLanes,checkLanes);
  }
  if (!vn->isWritten()) return;
  PcodeOp *op = vn->getDef();
  if (op->code() == CPUI_PIECE) {			// Is the big register formed from smaller pieces
    int4 loSize = op->getIn(1)->getSize();
    addPieceLaneSize(loSize,0,allowedLanes,checkLanes);
    addPieceLaneSize(op->getIn(0)->getSize(),loSize,allowedLanes,checkLanes);
  }
  else if (op->code() == CPUI_INT_ZEXT) {
    // Is the big register a run of lanes with zero lanes above it. A single lane extended is left alone:
    // it suggests no lane size on its own.
    int4 inSize = op->getIn(0)->getSize();
    if (!allowedLanes.allowedLane(inSize))
      addPieceLaneSize(inSize,0,allowedLanes,checkLanes);
  }
}

/// \brief Search for a likely lane size and try to divide a single Varnode into these lanes
///
/// There are different ways to search for a lane size:
///
/// Mode 0: Collect putative lane sizes based on the local ops using the Varnode. Attempt
/// to divide based on each of those lane sizes in turn.
///
/// Mode 1: Similar to mode 0, except we allow for SUBPIECE operations that truncate to
/// variables that are smaller than the lane size.
///
/// Mode 2: Attempt to divide based on a default lane size.
/// \param data is the function being transformed
/// \param vn is the given single Varnode
/// \param lanedRegister is acceptable set of lane sizes for the Varnode
/// \param mode is the lane size search mode (0, 1, or 2)
/// \return \b true if the Varnode (and its data-flow) was successfully split
bool ActionLaneDivide::processVarnode(Funcdata &data,Varnode *vn,const LanedRegister &lanedRegister,int4 mode)

{
  LanedRegister checkLanes;		// Lanes we are going to try, initialized to no lanes
  bool allowDowncast = (mode > 0);
  if (mode < 2)
    collectLaneSizes(vn,lanedRegister,checkLanes);
  else {
    int4 defaultSize = data.getArch()->types->getSizeOfPointer();		// Default lane size
    if (defaultSize == 4 && lanedRegister.allowedLane(4))
      checkLanes.addLaneSize(4);
    else if (lanedRegister.allowedLane(8))
      checkLanes.addLaneSize(8);
    else if (lanedRegister.allowedLane(4))
      checkLanes.addLaneSize(4);
  }
  LanedRegister::const_iterator enditer = checkLanes.end();
  for(LanedRegister::const_iterator iter=checkLanes.begin();iter!=enditer;++iter) {
    int4 curSize = *iter;
    LaneDescription description(lanedRegister.getWholeSize(),curSize);	// Lane scheme dictated by curSize
    LaneDivide laneDivide(&data,vn,description,allowDowncast);
    if (laneDivide.doTrace()) {
      laneDivide.apply();
      count += 1;		// Indicate a change was made
      return true;
    }
  }
  return false;
}

int4 ActionLaneDivide::apply(Funcdata &data)

{
  // Varnodes keep registering as laned accesses after this pass: a stack location of a laned size
  // only appears once the stack analysis has turned its LOADs and STOREs into Varnodes, so the pass
  // runs again on each round of the main loop over whatever registered since its last run.
  map<VarnodeData,const LanedRegister *>::const_iterator iter;
  for(int4 mode=0;mode<3;++mode) {
    bool allStorageProcessed = true;
    for(iter=data.beginLaneAccess();iter!=data.endLaneAccess();++iter) {
      const LanedRegister *lanedReg = (*iter).second;
      Address addr = (*iter).first.getAddr();
      int4 sz = (*iter).first.size;
      VarnodeLocSet::const_iterator viter = data.beginLoc(sz,addr);
      VarnodeLocSet::const_iterator venditer = data.endLoc(sz,addr);
      bool allVarnodesProcessed = true;
      while(viter != venditer) {
	Varnode *vn = *viter;
	if (vn->hasNoDescend()) {
	  ++viter;
	  continue;
	}
	if (processVarnode(data, vn, *lanedReg, mode)) {
	  viter = data.beginLoc(sz,addr);
	  venditer = data.endLoc(sz, addr);	// Recalculate bounds
	  allVarnodesProcessed = true;
	}
	else {
	  ++viter;
	  allVarnodesProcessed = false;
	}
      }
      if (!allVarnodesProcessed)
	allStorageProcessed = false;
    }
    if (allStorageProcessed) break;
  }
  data.clearLanedAccessMap();
  return 0;
}

int4 ActionSegmentize::apply(Funcdata &data)

{
  int4 numops = data.getArch()->userops.numSegmentOps();
  if (numops==0) return 0;
  if (localcount>0) return 0;	// Only perform once
  localcount = 1;		// Mark as having performed once

  vector<Varnode *> bindlist;
  bindlist.push_back((Varnode *)0);
  bindlist.push_back((Varnode *)0);

  for(int4 i=0;i<numops;++i) {
    SegmentOp *segdef = data.getArch()->userops.getSegmentOp(i);
    if (segdef == (SegmentOp *)0) continue;
    AddrSpace *spc = segdef->getSpace();

    list<PcodeOp *>::const_iterator iter,enditer;
    iter = data.beginOp(CPUI_CALLOTHER);
    enditer = data.endOp(CPUI_CALLOTHER);
    int4 uindex = segdef->getIndex();
    while(iter != enditer) {
      PcodeOp *segroot = *iter++;
      if (segroot->isDead()) continue;
      if (segroot->getIn(0)->getOffset() != uindex) continue;
      if (!segdef->unify(data,segroot,bindlist)) {
	ostringstream err;
	err << "Segment op in wrong form at ";
	segroot->getAddr().printRaw(err);
	throw LowlevelError(err.str());
      }

      if (segdef->getNumVariableTerms()==1)
	bindlist[0] = data.newConstant(4,0);
      // Redefine the op as a segmentop
      data.opSetOpcode(segroot,CPUI_SEGMENTOP);
      data.opSetInput(segroot,data.newVarnodeSpace(spc),0);
      data.opSetInput(segroot,bindlist[0],1);
      data.opSetInput(segroot,bindlist[1],2);
      for(int4 j=segroot->numInput()-1;j>2;--j) // Remove anything else
	data.opRemoveInput(segroot,j);
      count += 1;
    }
  }
  return 0;
}

int4 ActionForceGoto::apply(Funcdata &data)

{
  data.getOverride().applyForceGoto(data);
  return 0;
}

int4 ActionConstbase::apply(Funcdata &data)

{
  if (data.getBasicBlocks().getSize()==0) return 0; // No blocks
  // Get start block, which is constructed to have nothing
  // falling into it
  BlockBasic *bb = (BlockBasic *)data.getBasicBlocks().getBlock(0);

  int4 injectid = data.getFuncProto().getInjectUponEntry();
  if (injectid >= 0) {
    InjectPayload *payload = data.getArch()->pcodeinjectlib->getPayload(injectid);
    data.doLiveInject(payload,bb->getStart(),bb,bb->beginOp());
  }

  const TrackedSet trackset( data.getArch()->context->getTrackedSet(data.getAddress()));

  for(int4 i=0;i<trackset.size();++i) {
    const TrackedContext &ctx(trackset[i]);

    Address addr(ctx.loc.space,ctx.loc.offset);
    PcodeOp *op = data.newOp(1,bb->getStart());
    data.newVarnodeOut(ctx.loc.size,addr,op);
    Varnode *vnin = data.newConstant(ctx.loc.size,ctx.val);
    data.opSetOpcode(op,CPUI_COPY);
    data.opSetInput(op,vnin,0);
    data.opInsertBegin(op,bb);
  }
  return 0;
}

// int4 ActionCse::apply(Funcdata &data)

// {
//   vector< pair<uintm,PcodeOp *> > list;
//   vector<Varnode *> vlist;
//   PcodeOp *op;
//   list<PcodeOp *>::const_iterator iter;
//   uintm hash;

//   for(iter=data.op_alive_begin();iter!=data.op_alive_end();++iter) {
//     op = *iter;
//     hash = op->getCseHash();
//     if (hash == 0) continue;
//     list.push_back(pair<uintm,PcodeOp *>(hash,op));
//   }
//   if (list.empty()) return 0;

//   cseEliminateList(data,list,vlist);
//   while(!vlist.empty()) {
//     count += 1;			// Indicate that changes have been made
//     list.clear();
//     cse_build_fromvarnode(list,vlist);
//     vlist.clear();
//     cseEliminateList(data,list,vlist);
//   }
//   return 0;
// }

/// We are substituting either -out1- for -out2-  OR  -out2- for -out1-
/// Return true if we prefer substituting -out2- for -out1-
/// \param out1 is one output
/// \param out2 is the other output
/// \return preference
bool ActionMultiCse::preferredOutput(Varnode *out1,Varnode *out2)

{
  // Prefer the output that is used in a CPUI_RETURN
  list<PcodeOp *>::const_iterator iter,enditer;
  enditer = out1->endDescend();
  for(iter=out1->beginDescend();iter!=enditer;++iter) {
    PcodeOp *op = *iter;
    if (op->code() == CPUI_RETURN)
      return false;
  }
  enditer = out2->endDescend();
  for(iter=out2->beginDescend();iter!=enditer;++iter) {
    PcodeOp *op = *iter;
    if (op->code() == CPUI_RETURN)
      return true;
  }
  // Prefer addrtied over register over unique
  if (!out1->isAddrTied()) {
    if (out2->isAddrTied())
      return true;
    else {
      if (out1->getSpace()->getType()==IPTR_INTERNAL) {
	if (out2->getSpace()->getType()!=IPTR_INTERNAL)
	  return true;
      }
    }
  }
  return false;
}

/// Find any matching CPUI_MULTIEQUAL that occurs before \b target that has \b in as an input.
/// Then test to see if the \b target and the recovered op are functionally equivalent.
/// \param bl is the parent block
/// \param target is the given target CPUI_MULTIEQUAL
/// \param in is the specific input Varnode
PcodeOp *ActionMultiCse::findMatch(BlockBasic *bl,PcodeOp *target,Varnode *in)

{
  list<PcodeOp *>::iterator iter = bl->beginOp();

  for(;;) {
    PcodeOp *op = *iter;
    ++iter;
    if (op == target)		// Caught up with target, nothing else before it
      break;
    int4 i,numinput;
    numinput = op->numInput();
    for(i=0;i<numinput;++i) {
      Varnode *vn = op->getIn(i);
      if (vn->isWritten() && (vn->getDef()->code() == CPUI_COPY))
	vn = vn->getDef()->getIn(0);		// Allow for differences in copy propagation
      if (vn == in) break;
    }
    if (i < numinput) {
      int4 j;
      Varnode *buf1[2];
      Varnode *buf2[2];
      for(j=0;j<numinput;++j) {
	Varnode *in1 = op->getIn(j);
	if (in1->isWritten() && (in1->getDef()->code() == CPUI_COPY))
	  in1 = in1->getDef()->getIn(0);	// Allow for differences in copy propagation
	Varnode *in2 = target->getIn(j);
	if (in2->isWritten() && (in2->getDef()->code() == CPUI_COPY))
	  in2 = in2->getDef()->getIn(0);
	if (in1 == in2) continue;
	if (0!=functionalEqualityLevel(in1,in2,buf1,buf2))
	  break;
      }
      if (j==numinput)		// We have found a redundancy
	return op;
    }
  }
  return (PcodeOp *)0;
}

/// Search for pairs of CPUI_MULTIEQUAL ops in \b bl that share an input.
/// If the pairs found are functionally equivalent, delete one of the two.
/// \param data is the function owning the block
/// \param bl is the specific basic block
/// return \b true if a CPUI_MULTIEQUAL was (successfully) deleted
bool ActionMultiCse::processBlock(Funcdata &data,BlockBasic *bl)

{
  vector<Varnode *> vnlist;
  PcodeOp *targetop = (PcodeOp *)0;
  PcodeOp *pairop;
  list<PcodeOp *>::iterator iter = bl->beginOp();
  list<PcodeOp *>::iterator enditer = bl->endOp();
  while(iter != enditer) {
    PcodeOp *op = *iter;
    ++iter;
    OpCode opc = op->code();
    if (opc == CPUI_COPY) continue;
    if (opc != CPUI_MULTIEQUAL) break;
    int4 vnpos = vnlist.size();
    int4 i;
    int4 numinput = op->numInput();
    for(i=0;i<numinput;++i) {
      Varnode *vn = op->getIn(i);
      if (vn->isWritten() && (vn->getDef()->code() == CPUI_COPY))	// Some copies may not propagate into MULTIEQUAL
	vn = vn->getDef()->getIn(0);					// Allow for differences in copy propagation
      vnlist.push_back(vn);
      if (vn->isMark()) {		// If we've seen this varnode before
	pairop = findMatch(bl,op,vn);
	if (pairop != (PcodeOp *)0)
	  break;
      }
    }
    if (i<numinput) {
      targetop = op;
      break;
    }
    for(i=vnpos;i<vnlist.size();++i)
      vnlist[i]->setMark();		// Mark that we have seen this varnode
  }

  // Clear out any of the marks we put down
  for(int4 i=0;i<vnlist.size();++i)
    vnlist[i]->clearMark();

  if (targetop != (PcodeOp *)0) {
    Varnode *out1 = pairop->getOut();
    Varnode *out2 = targetop->getOut();
    if (preferredOutput(out1,out2)) {
      data.totalReplace(out1,out2);	// Replace pairop and out1 in favor of targetop and out2
      data.opDestroy(pairop);
    }
    else {
      data.totalReplace(out2,out1);
      data.opDestroy(targetop);
    }
    count += 1;		// Indicate that a change has taken place
    return true;
  }
  return false;
}

int4 ActionMultiCse::apply(Funcdata &data)

{
  const BlockGraph &bblocks( data.getBasicBlocks() );
  int4 sz = bblocks.getSize();
  for(int4 i=0;i<sz;++i) {
    BlockBasic *bl = (BlockBasic *)bblocks.getBlock(i);
    while(processBlock(data,bl)) {
    }
  }
  return 0;
}

int4 ActionShadowVar::apply(Funcdata &data)

{
  const BlockGraph &bblocks(data.getBasicBlocks());
  BlockBasic *bl;
  PcodeOp *op;
  Varnode *vn;
  vector<Varnode *> vnlist;
  list<PcodeOp *> oplist;
  uintb startoffset;
  for(int4 i=0;i<bblocks.getSize();++i) {
    vnlist.clear();
    bl = (BlockBasic *)bblocks.getBlock(i);
    // Iterator over all MULTIEQUALs in the block
    // We have to check all ops in the first address
    // We cannot stop at first non-MULTIEQUAL because
    // other ops creep in because of multi_collapse
    startoffset = bl->getStart().getOffset();
    list<PcodeOp *>::iterator iter = bl->beginOp();
    while(iter != bl->endOp()) {
      op = *iter++;
      if (op->getAddr().getOffset() != startoffset) break;
      if (op->code() != CPUI_MULTIEQUAL) continue;
      vn = op->getIn(0);
      if (vn->isMark())
	  oplist.push_back(op);
      else {
	vn->setMark();
	vnlist.push_back(vn);
      }
    }
    for(int4 j=0;j<vnlist.size();++j)
      vnlist[j]->clearMark();
  }
  list<PcodeOp *>::iterator oiter;
  for(oiter=oplist.begin();oiter!=oplist.end();++oiter) {
    op = *oiter;
    PcodeOp *op2;
    for(op2=op->previousOp();op2!=(PcodeOp *)0;op2=op2->previousOp()) {
      if (op2->code() != CPUI_MULTIEQUAL) continue;
      int4 i;
      for(i=0;i<op->numInput();++i) // Check for match in each branch
	if (op->getIn(i) != op2->getIn(i)) break;
      if (i != op->numInput()) continue; // All branches did not match

      vector<Varnode *> plist;
      plist.push_back(op2->getOut());
      data.opSetOpcode(op,CPUI_COPY);
      data.opSetAllInput(op,plist);
      count += 1;
    }
  }

  return 0;
}

/// \brief Search for address space annotations in the path of a pointer constant.
///
/// From a constant, search forward in its data-flow either for a LOAD or STORE operation where we can
/// see the address space being accessed, or search for a pointer data-type with an address space attribute.
/// We make a limited traversal through the op reading the constant, through INT_ADD, INDIRECT, COPY,
/// and MULTIEQUAL until we hit a LOAD or STORE.
/// \param vn is the constant we are searching from
/// \param op is the PcodeOp reading the constant
/// \return the discovered AddrSpace or null
AddrSpace *ActionConstantPtr::searchForSpaceAttribute(Varnode *vn,PcodeOp *op)

{
  for(int4 i=0;i<3;++i) {
    Datatype *dt = vn->getType();
    if (dt->getMetatype() == TYPE_PTR) {
      AddrSpace *spc = ((TypePointer*)dt)->getSpace();
      if (spc != (AddrSpace*)0 && spc->getAddrSize() == vn->getSize())	// If provided a pointer with space attribute
	return spc;		// use that
    }
    switch(op->code()) {
      case CPUI_INT_ADD:
      case CPUI_COPY:
      case CPUI_INDIRECT:
      case CPUI_MULTIEQUAL:
	vn = op->getOut();
	op = vn->loneDescend();
	break;
      case CPUI_LOAD:
	return op->getIn(0)->getSpaceFromConst();
      case CPUI_STORE:
	if (op->getIn(1) == vn)
	  return op->getIn(0)->getSpaceFromConst();
	return (AddrSpace *)0;
      default:
	return (AddrSpace *)0;
    }
    if (op == (PcodeOp *)0) break;
  }
  for(list<PcodeOp *>::const_iterator iter=vn->beginDescend();iter!=vn->endDescend();++iter) {
    op = *iter;
    OpCode opc = op->code();
    if (opc == CPUI_LOAD)
      return op->getIn(0)->getSpaceFromConst();
    else if (opc == CPUI_STORE && op->getIn(1) == vn)
      return op->getIn(0)->getSpaceFromConst();
  }
  return (AddrSpace *)0;
}

/// \brief Select the AddrSpace in which we infer with the given constant is a pointer
///
/// The constant must match the AddrSpace address size. If there is more than one possible match,
/// search for more information in the syntax tree.
/// \param vn is the given constant Varnode
/// \param op is the PcodeOp which uses the constant
/// \param spaceList is the list of address spaces to select from
/// \return the selected address space or null
AddrSpace *ActionConstantPtr::selectInferSpace(Varnode *vn,PcodeOp *op,const vector<AddrSpace *> &spaceList)

{
  AddrSpace *resSpace = (AddrSpace *)0;
  if (vn->getType()->getMetatype() == TYPE_PTR) {
    AddrSpace *spc = ((TypePointer *)vn->getType())->getSpace();
    if (spc != (AddrSpace *)0 && spc->getAddrSize() == vn->getSize())
      return spc;
  }
  for(int4 i=0;i<spaceList.size();++i) {
    AddrSpace *spc = spaceList[i];
    int4 minSize = spc->getMinimumPtrSize();
    if (minSize == 0) {
      if (vn->getSize() != spc->getAddrSize())
	continue;
    }
    else if (vn->getSize() < minSize)
      continue;
    if (resSpace != (AddrSpace *)0) {
      AddrSpace *searchSpc = searchForSpaceAttribute(vn,op);
      if (searchSpc != (AddrSpace *)0)
	resSpace = searchSpc;
      break;
    }
    resSpace = spc;
  }
  return resSpace;
}

/// \brief Check if we need to try to infer a constant pointer from the input of the given COPY
///
/// In general, we do want try, but there is a special case where the COPY feeds into a RETURN and
/// the function does \e not return a pointer.  We also consider the \b infer_pointers boolean.
/// \param op is the given COPY op
/// \param data is the function
/// \return \b true if we should try to infer
bool ActionConstantPtr::checkCopy(PcodeOp *op,Funcdata &data)

{
  Varnode *vn = op->getOut();
  PcodeOp *retOp = vn->loneDescend();
  if (retOp != (PcodeOp *)0 && retOp->code() == CPUI_RETURN && data.getFuncProto().isOutputLocked()) {
    type_metatype meta = data.getFuncProto().getOutput()->getType()->getMetatype();
    if (meta != TYPE_PTR && meta != TYPE_UNKNOWN) {
      return false;		// Do NOT infer, we know the constant can't be pointer
    }
    return true;		// Try to infer, regardless of infer_pointers config, because we KNOW it is a pointer
  }
  return data.getArch()->infer_pointers;
}

/// \brief Determine if given Varnode might be a pointer constant.
///
/// If it is a pointer, return the symbol it points to, or NULL otherwise. If it is determined
/// that the Varnode is a pointer to a specific symbol, the encoding of the full pointer is passed back.
/// Usually this is just the constant value of the Varnode, but in this case of partial pointers
/// (like \e near pointers) the full pointer may contain additional information.
/// \param spc is the address space being pointed to
/// \param vn is the given Varnode
/// \param op is the lone descendant of the Varnode
/// \param slot is the slot index of the Varnode
/// \param rampoint will hold the Address of the resolved symbol
/// \param fullEncoding will hold the full pointer encoding being passed back
/// \param data is the function being analyzed
/// \return the recovered symbol or NULL
MapEntry *ActionConstantPtr::isPointer(AddrSpace *spc,Varnode *vn,PcodeOp *op,int4 slot,
				       Address &rampoint,uintb &fullEncoding,Funcdata &data)
{
  bool needexacthit;
  vn->setSymbolCheck(Varnode::symcheck_complete);
  Architecture *glb = data.getArch();
  Varnode *outvn;
  if (vn->getTypeReadFacing(op)->getMetatype() == TYPE_PTR) { // Are we explicitly marked as a pointer
    rampoint = glb->resolveConstant(spc,vn->getOffset(),vn->getSize(),op->getAddr(),fullEncoding);
    needexacthit = false;
  }
  else {
    if (vn->isTypeLock()) return (MapEntry *)0; // Locked as NOT a pointer
    needexacthit = true;
    // Check if the constant is involved in a potential pointer expression
    // as the base
    switch(op->code()) {
    case CPUI_CALL:
    case CPUI_CALLIND:
    {
      if (slot==0)
	return (MapEntry *)0;
      // A constant parameter could be a pointer
      FuncCallSpecs *fc = data.getCallSpecs(op);
      if (fc != (FuncCallSpecs *)0 && fc->isInputLocked() && fc->numParams() > slot-1) {
	type_metatype meta = fc->getParam(slot-1)->getType()->getMetatype();
	if (meta != TYPE_PTR && meta != TYPE_UNKNOWN) {
	  return (MapEntry *)0;	// Definitely not passing a pointer
	}
      }
      else if (!glb->infer_pointers)
	return (MapEntry *)0;
      break;
    }
    case CPUI_COPY:
      if (!checkCopy(op, data))
	return (MapEntry *)0;
      break;
    case CPUI_PIECE:
      // Pointers get concatenated in structures
    case CPUI_INT_EQUAL:
    case CPUI_INT_NOTEQUAL:
    case CPUI_INT_LESS:
    case CPUI_INT_LESSEQUAL:
      // A comparison with a constant could be a pointer
      if (!glb->infer_pointers)
	return (MapEntry *)0;
      break;
    case CPUI_INT_ADD:
      outvn = op->getOut();
      if (outvn->getTypeDefFacing()->getMetatype()==TYPE_PTR) {
	// Is there another pointer base in this expression
	if (op->getIn(1-slot)->getTypeReadFacing(op)->getMetatype()==TYPE_PTR)
	  return (MapEntry *)0; // If so, we are not a pointer
	// FIXME: need to fully explore additive tree
	needexacthit = false;
      }
      else if (!glb->infer_pointers)
	return (MapEntry *)0;
      break;
    case CPUI_STORE:
      if (slot != 2)
	return (MapEntry *)0;
      break;
    default:
      return (MapEntry *)0;
    }
    // Make sure the constant is in the expected range for a pointer
    if (spc->getPointerLowerBound() > vn->getOffset())
      return (MapEntry *)0;
    if (spc->getPointerUpperBound() < vn->getOffset())
      return (MapEntry *)0;
    // Check if the constant looks like a single bit or mask
    if (bit_transitions(vn->getOffset(),vn->getSize()) < 3)
      return (MapEntry *)0;
    rampoint = glb->resolveConstant(spc,vn->getOffset(),vn->getSize(),op->getAddr(),fullEncoding);
  }

  if (rampoint.isInvalid()) return (MapEntry *)0;
  if (!rampoint.highPtrPossible(1)) return (MapEntry *)0;
    // Since we are looking for a global address
    // Assume it is address tied and use empty usepoint
  MapEntry *entry = data.getScopeLocal()->getParent()->queryContainer(rampoint,1,Address());
  if (entry != (MapEntry *)0) {
    Datatype *ptrType = entry->getSymbol()->getType();
    if (ptrType->getMetatype() == TYPE_ARRAY) {
      Datatype *ct = ((TypeArray *)ptrType)->getBase();
      // In the special case of strings (character arrays) we allow the constant pointer to
      // refer to the middle of the string
      if (ct->isCharPrint())
	needexacthit = false;
    }
    if (needexacthit && entry->getAddr() != rampoint) {
      vn->setSymbolCheck(Varnode::symcheck_incomplete);	// May need to retest if we later discover vn is a pointer
      return (MapEntry *)0;
    }
  }
  return entry;
}

int4 ActionConstantPtr::apply(Funcdata &data)

{
  if (!data.hasTypeRecoveryStarted()) return 0;

  if (localcount >= 4)		// At most 4 passes (once type recovery starts)
    return 0;
  localcount += 1;

  VarnodeLocSet::const_iterator begiter,enditer;
  Architecture *glb = data.getArch();
  AddrSpace *cspc = glb->getConstantSpace();
  MapEntry *entry;
  Varnode *vn;

  begiter = data.beginLoc(cspc);
  enditer = data.endLoc(cspc);

  while(begiter!=enditer) {
    vn = *begiter++;
    if (!vn->isConstant()) break; // New varnodes may get inserted between begiter and enditer
    if (vn->getOffset() == 0) continue; // Never make constant 0 into spacebase
    uint4 check = vn->getSymbolCheck();
    if (check == Varnode::symcheck_complete) continue; // Have we checked this variable before
    if (check == Varnode::symcheck_incomplete && vn->getType()->getMetatype() != TYPE_PTR) continue;
    if (vn->hasNoDescend()) continue;
    if (vn->isSpacebase()) continue; // Don't use constant 0 which is already spacebase
    //    if (vn->getSize() != rspc->getAddrSize()) continue; // Must be size of pointer

    PcodeOp *op = vn->loneDescend();
    if (op == (PcodeOp *)0) continue;
    AddrSpace *rspc = selectInferSpace(vn, op, glb->inferPtrSpaces);
    if (rspc == (AddrSpace *)0) continue;
    int4 slot = op->getSlot(vn);
    OpCode opc = op->code();
    if (opc == CPUI_INT_ADD) {
      if (op->getIn(1-slot)->isSpacebase()) continue; // Make sure other side is not a spacebase already
    }
    else if (opc == CPUI_PTRSUB || opc==CPUI_PTRADD || opc == CPUI_SEGMENTOP)
      continue;
    Address rampoint;
    uintb fullEncoding;
    entry = isPointer(rspc,vn,op,slot,rampoint,fullEncoding,data);
    if (entry != (MapEntry *)0) {
      data.spacebaseConstant(op,slot,entry,rampoint,fullEncoding,vn->getSize());
      if ((opc == CPUI_INT_ADD)&&(slot==1))
	data.opSwapInput(op,0,1);
      count += 1;
    }
  }
  return 0;
}

int4 ActionDeindirect::apply(Funcdata &data)

{
  FuncCallSpecs *fc;
  PcodeOp *op;
  Varnode *vn;

  for(int4 i=0;i<data.numCalls();++i) {
    fc = data.getCallSpecs(i);
    op = fc->getOp();
    if (op->code() != CPUI_CALLIND) continue;
    vn = op->getIn(0);
    while(vn->isWritten()&&(vn->getDef()->code()==CPUI_COPY))
      vn = vn->getDef()->getIn(0);
    if (vn->isPersist() && vn->isExternalRef()) { // Check for possible external reference
      Funcdata *newfd = data.getScopeLocal()->getParent()->queryExternalRefFunction(vn->getAddr());
      if (newfd != (Funcdata *)0) {
	fc->deindirect(data,newfd);
	count += 1;
	continue;
      }
    }
    else if (vn->isConstant()) {
      AddrSpace *sp = data.getAddress().getSpace(); // Assume function is in same space as calling function
      // Convert constant to a byte address in this space
      uintb offset = AddrSpace::addressToByte(vn->getOffset(),sp->getWordSize());
      int4 align = data.getArch()->funcptr_align;
      if (align != 0) {		// If we know function pointer should be aligned
	offset >>= align;	// Remove any encoding bits before querying for the function
	offset <<= align;
      }
      Address codeaddr(sp,offset);
      Funcdata *newfd = data.getScopeLocal()->getParent()->queryFunction(codeaddr);
      if (newfd != (Funcdata *)0) {
	fc->deindirect(data,newfd);
	count += 1;
	continue;
      }
    }
    if (data.hasTypeRecoveryStarted()) {
      // Check for a function pointer that has an attached prototype
      Datatype *ct = op->getIn(0)->getTypeReadFacing(op);
      if ((ct->getMetatype()==TYPE_PTR)&&
	  (((TypePointer *)ct)->getPtrTo()->getMetatype()==TYPE_CODE)) {
	TypeCode *tc = (TypeCode *)((TypePointer *)ct)->getPtrTo();
	const FuncProto *fp = tc->getPrototype();
	if (fp!=(const FuncProto *)0) {
	  if (!fc->isInputLocked()) {
	    // We use isInputLocked as a test of whether the
	    // function pointer prototype has been applied before
	    fc->forceSet(data,*fp);
	    count += 1;
	  }
	}
	// FIXME: If fc's input IS locked presumably this means
	// that this prototype is already set, but it MIGHT mean
	// we have conflicting locked prototypes
      }
    }
  }
  return 0;
}

/// \brief Try to eliminate constant extended to be larger than sizeof(uintb)
///
/// If given varnode is defined as zext(#0), simplify operations that read it.
/// \param vn is the big varnode
/// \param data is the function
void ActionVarnodeProps::handleExtendedZero(Varnode *vn,Funcdata &data)

{
  PcodeOp *zext = vn->getDef();
  if (zext->code() != CPUI_INT_ZEXT) return;
  if (!zext->getIn(0)->constantMatch(0)) return;
  list<PcodeOp *>::const_iterator iter;
  iter = vn->beginDescend();
   while(iter != vn->endDescend()) {
    PcodeOp *subop = *iter;
    ++iter;
    switch(subop->code()) {
      case CPUI_INT_ADD:
      case CPUI_INT_OR:
      case CPUI_INT_XOR:
	data.opRemoveInput(subop, subop->getSlot(vn));	// Convert to COPY of other slot
	data.opSetOpcode(subop, CPUI_COPY);
	iter = vn->beginDescend();
	count += 1;
	break;
      case CPUI_INT_2COMP:
	data.opSetOpcode(subop, CPUI_COPY);
	count += 1;
	break;
      case CPUI_INT_LEFT:
      case CPUI_INT_RIGHT:
      case CPUI_INT_SRIGHT:
      case CPUI_INT_DIV:
      case CPUI_INT_SDIV:
      case CPUI_INT_REM:
      case CPUI_INT_SREM:
	if (subop->getIn(0) != vn)		// Check if zero is first input
	  break;
	data.opRemoveInput(subop, 1);		// Convert to COPY of zero
	data.opSetOpcode(subop, CPUI_COPY);
	iter = vn->beginDescend();
	count += 1;
	break;
      case CPUI_INT_MULT:
      case CPUI_INT_AND:
	data.opRemoveInput(subop, 1-subop->getSlot(vn));	// Convert to COPY of zero
	data.opSetOpcode(subop, CPUI_COPY);
	iter = vn->beginDescend();
	count += 1;
	break;
      default:
	break;
    }
  }
}

int4 ActionVarnodeProps::apply(Funcdata &data)

{
  Architecture *glb = data.getArch();
  bool cachereadonly = glb->readonlypropagate;
  int4 pass = data.getHeritagePass();
  VarnodeLocSet::const_iterator iter;
  Varnode *vn;

  iter = data.beginLoc();
  while(iter != data.endLoc()) {
    vn = *iter++;		// Advance iterator in case vn is deleted
    if (vn->isAnnotation()) continue;
    int4 vnSize = vn->getSize();
    if (vn->isAutoLiveHold()) {
      if (pass > 0) {
	if (vn->isWritten()) {
	  PcodeOp *loadOp = vn->getDef();
	  if (loadOp->code() == CPUI_LOAD) {
	    Varnode *ptr = loadOp->getIn(1);
	    if (ptr->isConstant() || ptr->isReadOnly())
	      continue;
	    if (ptr->isWritten()) {
	      PcodeOp *copyOp = ptr->getDef();
	      if (copyOp->code() == CPUI_COPY) {
		ptr = copyOp->getIn(0);
		if (ptr->isConstant() || ptr->isReadOnly())
		  continue;
	      }
	    }
	  }
	}
	vn->clearAutoLiveHold();
	count += 1;
      }
    }
    else if (vn->hasActionProperty()) {
      if (cachereadonly&&vn->isReadOnly()) {
	if (data.fillinReadOnly(vn)) // Try to replace vn with its lookup in LoadImage
	  count += 1;
      }
      else if (vn->isVolatile())
	if (data.replaceVolatile(vn))
	  count += 1;		// Try to replace vn with pcode op
    }
    else if ((vn->getNZMask() & vn->getConsume())==0) {
      // FIXME: uintb should be arbitrary precision
      if (vn->isConstant()) continue; // Don't replace a constant
      if (vn->isWritten()) {
	if (vnSize > sizeof(uintb)) {
	  handleExtendedZero(vn, data);
	  continue;
	}
	if (vn->getDef()->code() == CPUI_COPY) {
	  if (vn->getDef()->getIn(0)->isConstant()) {
	    // Don't replace a COPY 0, with a zero, let
	    // constant propagation do that. This prevents
	    // an infinite recursion
	    if (vn->getDef()->getIn(0)->getOffset() == 0)
	      continue;
	  }
	}
      }
      if (!vn->hasNoDescend()) {
	data.totalReplaceConstant(vn,0);
	count += 1;
      }
    }
  }
  return 0;
}

int4 ActionDirectWrite::apply(Funcdata &data)

{
  VarnodeLocSet::const_iterator iter;
  list<PcodeOp *>::const_iterator oiter;
  Varnode *vn,*dvn;
  PcodeOp *op;
  vector<Varnode *> worklist;

				// Collect legal inputs and other auto direct writes
  for(iter=data.beginLoc();iter!=data.endLoc();++iter) {
    vn = *iter;
    vn->clearDirectWrite();
    if (vn->isInput()) {
      if (vn->isPersist()||vn->isSpacebase()) {
	vn->setDirectWrite();
	worklist.push_back(vn);
      }
      else if (data.getFuncProto().possibleInputParam(vn->getAddr(),vn->getSize())) {
	vn->setDirectWrite();
	worklist.push_back(vn);
      }
    }
    else if (vn->isWritten()) {
      op = vn->getDef();
      if (!op->isMarker()) {
	if (vn->isPersist()) {
	  // Anything that writes to a global variable (in a real way) is considered a direct write
	  vn->setDirectWrite();
	  worklist.push_back(vn);
	}
	else if (op->code() == CPUI_COPY) {	// For most COPYs, do not consider it a direct write
	  if (vn->isStackStore()) {		// But, if the original operation was really a CPUI_STORE
	    Varnode *invn = op->getIn(0);	// Trace COPY source
	    if (invn->isWritten()) {		// Through possible multiple COPYs
	      PcodeOp *curop = invn->getDef();
	      if (curop->code() == CPUI_COPY)
		invn = curop->getIn(0);
	    }
	    if (invn->isWritten() && invn->getDef()->isMarker()) {	// if source is from an INDIRECT
	      vn->setDirectWrite();					// then treat this as a direct write
	      worklist.push_back(vn);
	    }
	  }
	}
	else if ((op->code()!=CPUI_PIECE)&&(op->code()!=CPUI_SUBPIECE)) {
	  // Anything that writes to a variable in a way that isn't some form of COPY is a direct write
	  vn->setDirectWrite();
	  worklist.push_back(vn);
	}
      }
      else if (!propagateIndirect && op->code() == CPUI_INDIRECT) {
	Varnode *outvn = op->getOut();
	if (op->getIn(0)->getAddr() != outvn->getAddr())	// Check if storage address changes from input to output
	  vn->setDirectWrite();					// Indicates an active COPY, which is a direct write
	else if (outvn->isPersist())				// Value must be present at global storage at point call is made
	  vn->setDirectWrite();					//   so treat as direct write
	// We do NOT add vn to worklist as INDIRECT otherwise does not propagate
      }
    }
    else if (vn->isConstant()) {
      if (!vn->isIndirectZero()) {
	vn->setDirectWrite();
	worklist.push_back(vn);
      }
    }
  }
				// Let legalness taint
  while(!worklist.empty()) {
    vn = worklist.back();
    worklist.pop_back();
    for(oiter=vn->beginDescend();oiter!=vn->endDescend();++oiter) {
      op = *oiter;
      if (!op->isAssignment()) continue;
      dvn = op->getOut();
      if (!dvn->isDirectWrite()) {
	dvn->setDirectWrite();
	// For call based INDIRECTs, output is marked, but does not propagate depending on setting
	if (propagateIndirect || op->code() != CPUI_INDIRECT || op->isIndirectStore())
	  worklist.push_back(dvn);
      }
    }
  }
  return 0;
}

int4 ActionExtraPopSetup::apply(Funcdata &data)

{
  FuncCallSpecs *fc;
  PcodeOp *op;

  if (stackspace == (AddrSpace *)0) return 0; // No stack to speak of
  const VarnodeData &point(stackspace->getSpacebase(0));
  Address sb_addr(point.space,point.offset);
  int4 sb_size = point.size;

  for(int4 i=0;i<data.numCalls();++i) {
    fc = data.getCallSpecs(i);
    if (fc->getExtraPop() == 0) continue; // Stack pointer is undisturbed
    if (fc->getExtraPop() != ProtoModel::extrapop_unknown) { // We know exactly how stack pointer is changed
      fc->setEffectiveExtraPop(fc->getExtraPop());
      op = data.newOp(2,fc->getOp()->getAddr());
      data.newVarnodeOut(sb_size,sb_addr,op);
      data.opSetInput(op,data.newVarnode(sb_size,sb_addr),0);
      data.opSetOpcode(op,CPUI_INT_ADD);
      data.opSetInput(op,data.newConstant(sb_size,fc->getExtraPop()),1);
      data.opInsertAfter(op,fc->getOp());
    }
    else {			// We don't know exactly, so we create INDIRECT
      op = data.newIndirect(fc->getOp());
      data.newVarnodeOut(sb_size,sb_addr,op);
      data.opSetInput(op,data.newVarnode(sb_size,sb_addr),0);
      data.opInsertBefore(op,fc->getOp());
    }
  }
  return 0;
}

/// \brief Set up the parameter recovery process for a single sub-function call
///
/// If the prototype is known (locked), insert stub Varnodes
/// If the prototype is varargs (dotdotdot), set up recovery of variable Varnodes
/// \param fc is the given sub-function
/// \param data is the function being analyzed
void ActionFuncLink::funcLinkInput(FuncCallSpecs *fc,Funcdata &data)

{
  bool inputlocked = fc->isInputLocked();
  bool varargs = fc->isDotdotdot();
  AddrSpace *spacebase = fc->getSpacebase();	// Non-zero spacebase indicates we need a stackplaceholder
  ParamActive *active = fc->getActiveInput();

  if ((!inputlocked)||varargs)
    fc->initActiveInput();
  if (inputlocked) {
    PcodeOp *op = fc->getOp();
    int4 numparam = fc->numParams();
    bool setplaceholder = varargs;
    for(int4 i=0;i<numparam;++i) {
      ProtoParameter *param = fc->getParam(i);
      if (!param->hasStorage()) {
	data.opInsertInput(op,data.newConstant(param->getSize(),0),op->numInput());	// Put #0 in unassigned slot
	continue;
      }
      ParamTrial &paramtrial(active->registerTrial(param->getAddress(),param->getSize()));
      paramtrial.markActive(); // Parameter is not optional
      if (varargs){
    	  paramtrial.setFixedPosition(i);
      }
      AddrSpace *spc = param->getAddress().getSpace();
      uintb off = param->getAddress().getOffset();
      int4 sz = param->getSize();
      if (spc->getType() == IPTR_SPACEBASE) { // Param is stack relative
	Varnode *loadval = data.opStackLoad(spc,off,sz,op,(Varnode *)0,false);
	data.opInsertInput(op,loadval,op->numInput());
	if (!setplaceholder) {
	  setplaceholder = true;
	  loadval->setSpacebasePlaceholder();
	  spacebase = (AddrSpace *)0;	// With a locked stack parameter, we don't need a stackplaceholder
	}
	continue;
      }
      if (spc->getType() == IPTR_JOIN) {
	JoinRecord *join = data.getArch()->findJoin(off);
	int4 index = -1;
	if (join->getPiece(0).space->getType() == IPTR_SPACEBASE)
	  index = 0;
	else if (join->getPiece(join->numPieces()-1).space->getType() == IPTR_SPACEBASE)
	  index = join->numPieces()-1;
	if (index >= 0) {
	  const VarnodeData &stack(join->getPiece(index));
	  const VarnodeData &remain(data.getArch()->stripJoinPiece(join, index));
	  Varnode *loadval = data.opStackLoad(stack.space,stack.offset,stack.size,op,(Varnode *)0,false);
	  Varnode *remainval = data.newVarnode(remain.size, remain.space, remain.offset);
	  PcodeOp *concatOp = data.newOp(2, op->getAddr());
	  data.opSetOpcode(concatOp, CPUI_PIECE);
	  if (index == 0) {
	    data.opSetInput(concatOp,loadval,0);
	    data.opSetInput(concatOp,remainval,1);
	  }
	  else {
	    data.opSetInput(concatOp,remainval,0);
	    data.opSetInput(concatOp,loadval,1);
	  }
	  Varnode *outvn = data.newUniqueOut(sz, concatOp);
	  data.opInsertBefore(concatOp, op);
	  data.opInsertInput(op,outvn,op->numInput());
	  continue;
	}
      }
      data.opInsertInput(op,data.newVarnode(param->getSize(),param->getAddress()),op->numInput());
    }
  }
  if (spacebase != (AddrSpace *)0)	// If we need it, create the stackplaceholder
    fc->createPlaceholder(data, spacebase);
}

/// \brief Set up the return value recovery process for a single sub-function call
///
/// If the prototype is known(locked), insert an output Varnode on the call
/// If the prototype is unknown set-up the ParamActive, so that outputs will be "gathered"
/// \param fc is the given sub-function
/// \param data is the function being analyzed
void ActionFuncLink::funcLinkOutput(FuncCallSpecs *fc,Funcdata &data)

{
  PcodeOp *callop = fc->getOp();
  if (callop->getOut() != (Varnode *)0) {
    // CALL ops are expected to have no output, but its possible an override has produced one
    if (callop->getOut()->getSpace()->getType() == IPTR_INTERNAL) {
      // Removing a varnode in the unique space will likely produce an input varnode in the unique space
      ostringstream s;
      s << "CALL op at ";
      callop->getAddr().printRaw(s);
      s << " has an unexpected output varnode";
      throw LowlevelError(s.str());
    }
    // Otherwise just remove the Varnode and assume return recovery will reintroduce it if necessary
    data.opUnsetOutput(callop);
  }
  if (fc->isOutputLocked()) {
    ProtoParameter *outparam = fc->getOutput();
    Datatype *outtype = outparam->getType();
    if (outparam->hasStorage()) {
      int4 sz = outparam->getSize();
      if (outtype->getMetatype() == TYPE_BOOL && data.isTypeRecoveryOn())
	data.opMarkCalculatedBool(callop);
      Address addr = outparam->getAddress();
      if (addr.getSpace()->getType() == IPTR_SPACEBASE) {
	// Delay creating output Varnode until heritage of the stack, when we know relative value of the stack pointer
	fc->setStackOutputLock(true);
	return;
      }
      data.newVarnodeOut(sz,addr,callop);
      VarnodeData vdata;
      OpCode res = fc->assumedOutputExtension(addr,sz,vdata);
      if (res == CPUI_PIECE) {		// Pick an extension based on type
	if (outtype->getMetatype() == TYPE_INT)
	  res = CPUI_INT_SEXT;
	else
	  res = CPUI_INT_ZEXT;
      }
      if (res != CPUI_COPY) { // We assume the (smallsize) output is extended to a full register
	// Create the extension operation to eliminate artifact
	PcodeOp *op = data.newOp(1,callop->getAddr());
	data.newVarnodeOut(vdata.size,vdata.getAddr(),op);
	Varnode *invn = data.newVarnode(sz,addr);
	data.opSetInput(op,invn,0);
	data.opSetOpcode(op,res);
	data.opInsertAfter(op,callop); // Insert immediately after the call
      }
    }
  }
  else
    fc->initActiveOutput();
}

int4 ActionFuncLink::apply(Funcdata &data)

{
  int4 i,size;

  size = data.numCalls();
  for(i=0;i<size;++i) {
    funcLinkInput(data.getCallSpecs(i),data);
    funcLinkOutput(data.getCallSpecs(i),data);
  }
  return 0;
}

int4 ActionFuncLinkOutOnly::apply(Funcdata &data)

{
  int4 size = data.numCalls();
  for(int4 i=0;i<size;++i)
    ActionFuncLink::funcLinkOutput(data.getCallSpecs(i),data);
  return 0;
}

int4 ActionParamDouble::apply(Funcdata &data)

{
  for(int4 i=0;i<data.numCalls();++i) {
    FuncCallSpecs *fc = data.getCallSpecs(i);
    PcodeOp *op = fc->getOp();
    if (fc->isInputActive()) {
      ParamActive *active = fc->getActiveInput();
      for(int4 j=0;j<active->getNumTrials();++j) {
	const ParamTrial &paramtrial( active->getTrial(j) );
	if (paramtrial.isChecked()) continue;
	if (paramtrial.isUnref()) continue;
	AddrSpace *spc = paramtrial.getAddress().getSpace();
	if (spc->getType() != IPTR_SPACEBASE) continue;
	int4 slot = paramtrial.getSlot();
	Varnode *vn = op->getIn(slot);
	if (!vn->isWritten()) continue;
	PcodeOp *concatop = vn->getDef();
	if (concatop->code() != CPUI_PIECE) continue;
	if (!fc->hasModel()) continue;
	Varnode *mostvn = concatop->getIn(0);
	Varnode *leastvn = concatop->getIn(1);
	int4 splitsize = spc->isBigEndian() ? mostvn->getSize() : leastvn->getSize();
	if (fc->checkInputSplit(paramtrial.getAddress(),paramtrial.getSize(),splitsize)) {
	  active->splitTrial(j,splitsize);
	  if (spc->isBigEndian()) {
	    data.opInsertInput(op,mostvn,slot);
	    data.opSetInput(op,leastvn,slot+1);
	  }
	  else {
	    data.opInsertInput(op,leastvn,slot);
	    data.opSetInput(op,mostvn,slot+1);
	  }
	  count += 1;		// Indicate that a change was made

	  j -= 1;	// Note we decrement j here, so that we can check nested CONCATs
	}
      }
    }
    else if ((!fc->isInputLocked())&&(data.isDoublePrecisOn())) {
      // Search for double precision objects that might become params
      int4 max = op->numInput() - 1;
      // Look for adjacent slots that form pieces of a double precision whole
      for(int4 j=1;j<max;++j) {
	Varnode *vn1 = op->getIn(j);
	Varnode *vn2 = op->getIn(j+1);
	SplitVarnode whole;
	bool isslothi;
	if (whole.inHandHi(vn1)) {
	  if (whole.getLo() != vn2) continue;
	  isslothi = true;
	}
	else if (whole.inHandLo(vn1)) {
	  if (whole.getHi() != vn2) continue;
	  isslothi = false;
	}
	else
	  continue;
	if (fc->checkInputJoin(j,isslothi,vn1,vn2)) {
	  data.opSetInput(op,whole.getWhole(),j);
	  data.opRemoveInput(op,j+1);
	  fc->doInputJoin(j,isslothi);
	  max = op->numInput() - 1;
	  count += 1;
	}
      }
    }
  }


  const FuncProto &fp( data.getFuncProto() );
  if (fp.isInputLocked() && data.isDoublePrecisOn()) {
    // Search for locked parameters that are being split into hi and lo components
    vector<Varnode *> lovec;
    vector<Varnode *> hivec;
    int4 minDoubleSize = data.getArch()->getDefaultSize();	// Minimum size to consider
    int4 numparams = fp.numParams();
    for(int4 i=0;i<numparams;++i) {
      ProtoParameter *param = fp.getParam(i);
      Datatype *tp = param->getType();
      if (!tp->isPrimitiveWhole())
	continue;		// Not double precision objects
      if (!param->hasStorage())
	continue;
      Varnode *vn = data.findVarnodeInput(tp->getSize(),param->getAddress());
      if (vn == (Varnode *)0) continue;
      if (vn->getSize() < minDoubleSize) continue;
      int4 halfSize = vn->getSize() / 2;
      lovec.clear();
      hivec.clear();
      bool otherUse = false;		// Have we seen use other than splitting into hi and lo
      list<PcodeOp *>::const_iterator iter,enditer;
      iter = vn->beginDescend();
      enditer = vn->endDescend();
      while(iter != enditer) {
	PcodeOp *subop = *iter;
	++iter;
	if (subop->code() != CPUI_SUBPIECE) continue;
	Varnode *outvn = subop->getOut();
	if (outvn->getSize() != halfSize) continue;
	if (subop->getIn(1)->getOffset() == 0)	// Possible lo precision piece
	  lovec.push_back(outvn);
	else if (subop->getIn(1)->getOffset() == halfSize)	// Possible hi precision piece
	  hivec.push_back(outvn);
	else {
	  otherUse = true;
	  break;
	}
      }
      if ((!otherUse)&&(!lovec.empty())&&(!hivec.empty())) {	// Seen (only) hi and lo uses
	for(int4 j=0;j<lovec.size();++j) {
	  Varnode *piecevn = lovec[j];
	  if (!piecevn->isPrecisLo()) {
	    piecevn->setPrecisLo();
	    count += 1;		// Indicate we made change
	  }
	}
	for(int4 j=0;j<hivec.size();++j) {
	  Varnode *piecevn = hivec[j];
	  if (!piecevn->isPrecisHi()) {
	    piecevn->setPrecisHi();
	    count += 1;
	  }
	}
      }
    }
  }
  return 0;
}

int4 ActionActiveParam::apply(Funcdata &data)

{
  int4 i;
  FuncCallSpecs *fc;
  AliasChecker aliascheck;
  aliascheck.gather(&data,data.getArch()->getStackSpace(),true);

  for(i=0;i<data.numCalls();++i) {
    fc = data.getCallSpecs(i);
				// An indirect function is not trimmable until
				// there has been at least one simplification pass
				// there has been a change to deindirect
    try {
      if (fc->isInputActive()) {
	ParamActive *activeinput = fc->getActiveInput();
	bool trimmable = ((activeinput->getNumPasses()>0)||(fc->getOp()->code() != CPUI_CALLIND));
	if (!activeinput->isFullyChecked())
	  fc->checkInputTrialUse(data,aliascheck);
	activeinput->finishPass();
	if (activeinput->getNumPasses() > activeinput->getMaxPass())
	  activeinput->markFullyChecked();
	else
	  count += 1;		// Count a change, to indicate we still have work to do
	if (trimmable && activeinput->isFullyChecked()) {
	  if (activeinput->needsFinalCheck())
	    fc->finalInputCheck();
	  fc->resolveModel(activeinput);
	  fc->deriveInputMap(activeinput);
	  fc->buildInputFromTrials(data);
	  fc->clearActiveInput();
	  count += 1;
	}
      }
    }
    catch(LowlevelError &err) {
      ostringstream s;
      s << "Error processing " << fc->getName();
      PcodeOp *op = fc->getOp();
      if (op != (PcodeOp *)0)
	s << " called at " << op->getSeqNum();
      s << ": " << err.explain;
      throw LowlevelError(s.str());
    }
  }
  return 0;
}

int4 ActionActiveReturn::apply(Funcdata &data)

{
  int4 i;
  FuncCallSpecs *fc;

  for(i=0;i<data.numCalls();++i) {
    fc = data.getCallSpecs(i);
    if (fc->isOutputActive()) {
      ParamActive *activeoutput = fc->getActiveOutput();
      vector<Varnode *> trialvn;
      fc->checkOutputTrialUse(data,trialvn);
      fc->deriveOutputMap(activeoutput);
      fc->buildOutputFromTrials(data,trialvn);
      fc->clearActiveOutput();
      count += 1;
    }
  }
  return 0;
}

// int4 ActionParamShiftStart::apply(Funcdata &data)

// {
//   int4 i;
//   FuncCallSpecs *fc;

//   for(i=0;i<data.numCalls();++i) {
//     fc = data.getCallSpecs(i);
//     fc->paramshiftModifyStart();
//   }
//   return 0;
// }

// int4 ActionParamShiftStop::apply(Funcdata &data)

// {
//   int4 i;
//   FuncCallSpecs *fc;

//   if (!paramshiftsleft) return 0;
//   paramshiftsleft = false;
//   for(i=0;i<data.numCalls();++i) {
//     fc = data.getCallSpecs(i);
//     if (fc->getParamshift() != 0) {
//       if (!fc->isInputActive()) {
// 	if (fc->paramshiftModifyStop(data))
// 	  count += 1;
//       }
//       else
// 	paramshiftsleft = true;
//     }
//   }
//   return 0;
// }

/// \brief Rewrite a CPUI_RETURN op to reflect a recovered output parameter.
///
/// Add a second input Varnode to the given CPUI_RETURN PcodeOp holding the return value
/// for the function at that point. Construct concatentations if there are multiple pieces
/// \param active is the output parameter description
/// \param retop is the given CPUI_RETURN
/// \param data is the function being analyzed
void ActionReturnRecovery::buildReturnOutput(ParamActive *active,PcodeOp *retop,Funcdata &data)

{
  vector<Varnode *> newparam;

  newparam.push_back(retop->getIn(0)); // Keep the first param (the return indirect reference)
  for(int4 i=0;i<active->getNumTrials();++i) { // Gather all the used varnodes to this return in proper order
    ParamTrial &curtrial(active->getTrial(i));
    if (!curtrial.isUsed()) break;
    if (curtrial.getSlot() >= retop->numInput()) break;
    newparam.push_back(retop->getIn(curtrial.getSlot()));
  }
  if (newparam.size()<=2)	// Easy zero or one return varnode case
    data.opSetAllInput(retop,newparam);
  else {
    vector<VarnodeData> pieces;
    int4 wholeSize = 0;
    for(int4 i=newparam.size()-1;i>=1;--i) {
      pieces.emplace_back(newparam[i]->getAddr(),newparam[i]->getSize());
      wholeSize += newparam[i]->getSize();
    }
    Address wholeAddr = data.getArch()->joinPieces(pieces, data.getArch()->translate);
    Varnode *lastVn = newparam[1];		// Start with least significant piece
    int4 curSize = lastVn->getSize();
    for(int4 i=2;i<newparam.size();++i) {	// Concatenate sequentially from least to most significant
      Varnode *vn = newparam[i];
      curSize += vn->getSize();			// Size of current concatenation
      Address addr = wholeAddr;			// Calculate address of current concatenation
      if (curSize != wholeSize) {
	if (addr.isBigEndian())
	  addr = addr + (wholeSize - curSize);
	addr.renormalize(curSize);
      }
      PcodeOp *newop = data.newOp(2,retop->getAddr());
      data.opSetOpcode(newop,CPUI_PIECE);
      Varnode *newout = data.newVarnodeOut(lastVn->getSize()+vn->getSize(),addr,newop);
      newout->setWriteMask();		// Don't let new Varnode cause additional heritage
      data.opSetInput(newop,vn,0);	// Most sig part
      data.opSetInput(newop,lastVn,1);
      data.opInsertBefore(newop,retop);
      lastVn= newout;
    }
    newparam.clear();
    newparam.push_back(retop->getIn(0));
    newparam.push_back(lastVn);
    data.opSetAllInput(retop,newparam);
  }
}

int4 ActionReturnRecovery::apply(Funcdata &data)

{
  ParamActive *active = data.getActiveOutput();
  if (active != (ParamActive *)0) {
    PcodeOp *op;
    Varnode *vn;
    list<PcodeOp *>::const_iterator iter,iterend;
    int4 i;

    int4 maxancestor = data.getArch()->trim_recurse_max;
    iterend = data.endOp(CPUI_RETURN);
    AncestorRealistic ancestorReal;
    for(iter=data.beginOp(CPUI_RETURN);iter!=iterend;++iter) {
      op = *iter;
      if (op->isDead()) continue;
      if (op->getHaltType() != 0) continue; // Don't evaluate special halts
      for(i=0;i<active->getNumTrials();++i) {
	ParamTrial &trial(active->getTrial(i));
	if (trial.isChecked()) continue; // Already checked
	int4 slot = trial.getSlot();
	vn = op->getIn(slot);
	if (ancestorReal.execute(op,slot,&trial,false))
	  if (data.ancestorOpUse(maxancestor,vn,op,trial,0,0))
	    trial.markActive(); // This varnode sees active use as a parameter
	count += 1;
      }
    }

    active->finishPass();
    if (active->getNumPasses() > active->getMaxPass())
      active->markFullyChecked();

    if (active->isFullyChecked()) {
      data.getFuncProto().deriveOutputMap(active);
      iterend = data.endOp(CPUI_RETURN);
      for(iter=data.beginOp(CPUI_RETURN);iter!=iterend;++iter) {
	op = *iter;
	if (op->isDead()) continue;
	if (op->getHaltType() != 0) continue;
	buildReturnOutput(active,op,data);
      }
      data.clearActiveOutput();
      count += 1;
    }
  }
  return 0;
}

int4 ActionRestrictLocal::apply(Funcdata &data)

{
  FuncCallSpecs *fc;
  list<PcodeOp *>::const_iterator iter;
  PcodeOp *op;
  Varnode *vn;
  int4 i;
  vector<EffectRecord>::const_iterator eiter,endeiter;

  for(i=0;i<data.numCalls();++i) {
    fc = data.getCallSpecs(i);
    op = fc->getOp();

    if (!fc->isInputLocked()) continue;
    if (fc->getSpacebaseOffset() == FuncCallSpecs::offset_unknown) continue;
    int4 numparam = fc->numParams();
    for(int4 j=0;j<numparam;++j) {
      ProtoParameter *param = fc->getParam(j);
      if (!param->hasStorage()) continue;
      Address addr = param->getAddress();
      spacetype tp = addr.getSpace()->getType();
      if (tp == IPTR_SPACEBASE) {
	uintb off = addr.getSpace()->wrapOffset(fc->getSpacebaseOffset() + addr.getOffset());
	data.getScopeLocal()->markNotMapped(addr.getSpace(),off,param->getSize(),true);
      }
      else if (tp == IPTR_JOIN) {
	JoinRecord *joinRec = data.getArch()->findJoin(addr.getOffset());
	for(int4 k=0;k<joinRec->numPieces();++k) {
	  const VarnodeData &vdata(joinRec->getPiece(k));
	  if (vdata.space->getType() == IPTR_SPACEBASE) {
	    uintb off = vdata.space->wrapOffset(fc->getSpacebaseOffset() + vdata.offset);
	    data.getScopeLocal()->markNotMapped(vdata.space,off,vdata.size,true);
	  }
	}
      }
    }
  }

  eiter = data.getFuncProto().effectBegin();
  endeiter = data.getFuncProto().effectEnd();
  for(;eiter!=endeiter;++eiter) { // Iterate through saved registers
    if ((*eiter).getType() == EffectRecord::killedbycall) continue;  // Not saved
    vn = data.findVarnodeInput((*eiter).getSize(),(*eiter).getAddress());
    if ((vn != (Varnode *)0)&&(vn->isUnaffected())) {
      // Mark storage locations for saved registers as not mapped
      // This should pickup unaffected, reload, and return_address effecttypes
      for(iter=vn->beginDescend();iter!=vn->endDescend();++iter) {
	op = *iter;
	if (op->code() != CPUI_COPY) continue;
	Varnode *outvn = op->getOut();
	if (!data.getScopeLocal()->isUnaffectedStorage(outvn))	// Is this where unaffected values get saved
	  continue;
	data.getScopeLocal()->markNotMapped(outvn->getSpace(),outvn->getOffset(),outvn->getSize(),false);
      }
    }
  }
  return 0;
}

/// Count the number of inputs to \b op which have their mark set
/// \param op is the PcodeOp to count
/// \return the number of marks set
uint4 ActionLikelyTrash::countMarks(PcodeOp *op)

{
  uint4 res = 0;
  for(int4 i=0;i<op->numInput();++i) {
    Varnode *vn = op->getIn(i);
    for(;;) {
      if (vn->isMark()) {
	res += 1;
	break;
      }
      if (!vn->isWritten()) break;
      PcodeOp *defOp = vn->getDef();
      if (defOp == op) {	// We have looped all the way around
	res += 1;
	break;
      }
      else if (defOp->code() != CPUI_INDIRECT)	// Chain up through INDIRECTs
	break;
      vn = vn->getDef()->getIn(0);
    }
  }
  return res;
}

/// \brief Decide if the given Varnode only ever flows into CPUI_INDIRECT
///
/// Return all the CPUI_INDIRECT ops that the Varnode hits in a list.
/// Trace forward down all paths from -vn-, if we hit
///    - CPUI_INDIRECT  -> trim that path and store that op in the resulting -indlist-
///    - CPUI_SUBPIECE
///    - CPUI_MULTIEQUAL
///    - CPUI_PIECE
///    - CPUI_AND       -> follow through to output
///    - anything else  -> consider -vn- to NOT be trash
///
/// For any CPUI_MULTIEQUAL and CPUI_PIECE that are hit, all the other inputs must be hit as well
/// \param vn is the given Varnode
/// \param indlist is the list to populate with CPUI_INDIRECT ops
/// \return \b true if all flows look like trash
bool ActionLikelyTrash::traceTrash(Varnode *vn,vector<PcodeOp *> &indlist)

{
  vector<PcodeOp *> allroutes;	// Keep track of merging ops (with more than 1 input)
  vector<Varnode *> markedlist;	// All varnodes we have visited on paths from -vn-
  list<PcodeOp *>::const_iterator iter,enditer;
  Varnode *outvn;
  uintb val;
  uint4 traced = 0;
  vn->setMark();
  markedlist.push_back(vn);
  bool istrash = true;

  while(traced < markedlist.size()) {
    Varnode *curvn = markedlist[traced++];
    iter = curvn->beginDescend();
    enditer = curvn->endDescend();
    for(;iter!=enditer;++iter) {
      PcodeOp *op = *iter;
      outvn = op->getOut();
      switch(op->code()) {
      case CPUI_INDIRECT:
	if (outvn->isPersist())
	  istrash = false;
	else if (op->isIndirectStore()) {
	  if (!outvn->isMark()) {
	    outvn->setMark();
	    markedlist.push_back(outvn);
	  }
	}
	else
	  indlist.push_back(op);
	break;
      case CPUI_SUBPIECE:
	if (outvn->isPersist())
	  istrash = false;
	else {
	  if (!outvn->isMark()) {
	    outvn->setMark();
	    markedlist.push_back(outvn);
	  }
	}
	break;
      case CPUI_MULTIEQUAL:
      case CPUI_PIECE:
	if (outvn->isPersist())
	  istrash = false;
	else {
	  if (!op->isMark()) {
	    op->setMark();
	    allroutes.push_back(op);
	  }
	  uint4 nummark = countMarks(op);
	  if (nummark == op->numInput()) {
	    if (!outvn->isMark()) {
	      outvn->setMark();
	      markedlist.push_back(outvn);
	    }
	  }
	}
	break;
      case CPUI_INT_AND:
	// If the AND is using only the topmost significant bytes then it is likely trash
	if (op->getIn(1)->isConstant()) {
	  val = op->getIn(1)->getOffset();
	  uintb mask = calc_mask(op->getIn(1)->getSize());
	  if ((val == ((mask<<8)&mask))||(val == ((mask<<16)&mask))||(val==((mask<<32)&mask))) {
	    indlist.push_back(op);
	    break;
	  }
	}
	istrash = false;
	break;
      default:
	istrash = false;
	break;
      }
      if (!istrash) break;
    }
    if (!istrash) break;
  }

  for(uint4 i=0;i<allroutes.size();++i) {
    if (!allroutes[i]->getOut()->isMark())
      istrash = false;		// Didn't see all inputs
    allroutes[i]->clearMark();
  }
  for(uint4 i=0;i<markedlist.size();++i)
    markedlist[i]->clearMark();

  return istrash;
}

int4 ActionLikelyTrash::apply(Funcdata &data)

{
  vector<PcodeOp *> indlist;

  vector<VarnodeData>::const_iterator iter,enditer;
  iter = data.getFuncProto().trashBegin();
  enditer = data.getFuncProto().trashEnd();
  for(;iter!=enditer;++iter) {
    const VarnodeData &vdata( *iter );
    Varnode *vn = data.findCoveredInput(vdata.size,vdata.getAddr());
    if (vn == (Varnode *)0) continue;
    if (vn->isTypeLock()||vn->isNameLock()) continue;
    indlist.clear();
    if (!traceTrash(vn,indlist)) continue;

    for(uint4 i=0;i<indlist.size();++i) {
      PcodeOp *op = indlist[i];
      if (op->code() == CPUI_INDIRECT) {
	// Trucate data-flow through INDIRECT, turning it into indirect creation
	data.opSetInput(op,data.newConstant(op->getOut()->getSize(), 0),0);
	data.markIndirectCreation(op,false);
      }
      else if (op->code() == CPUI_INT_AND) {
	data.opSetInput(op,data.newConstant(op->getIn(1)->getSize(),0),1);
      }
      count += 1;			// Indicate we made a change
    }
  }
  return 0;
}

/// \param vn is the given Varnode
/// \return \b true if it is a constant or a COPY of a constant
bool ActionRestructureVarnode::isCopyConstant(Varnode *vn)

{
  if (vn->isConstant()) return true;
  if (!vn->isWritten()) return false;
  if (vn->getDef()->code() != CPUI_COPY) return false;
  return vn->getDef()->getIn(0)->isConstant();
}

/// Return \b true if either the Varnode is a constant or if it is the not yet simplified
/// COPY or INT_ADD of constants.
/// \param vn is the given Varnode to test
/// \return \b true if the Varnode will be a constant
bool ActionRestructureVarnode::isDelayedConstant(Varnode *vn)

{
  if (vn->isConstant()) return true;
  if (!vn->isWritten()) return false;
  PcodeOp *op = vn->getDef();
  OpCode opc = op->code();
  if (opc == CPUI_COPY)
    return op->getIn(0)->isConstant();
  if (opc != CPUI_INT_ADD) return false;
  if (!isCopyConstant(op->getIn(1))) return false;
  if (!isCopyConstant(op->getIn(0))) return false;
  return true;
}

/// Test if the path to the given BRANCHIND originates from a constant but passes through INDIRECT operations.
/// This indicates that the switch value is produced indirectly, so we mark the earliest INDIRECT
/// operation as \e not \e collapsible, to guarantee that the indirect value is not lost during analysis.
/// \param op is the given BRANCHIND op
void ActionRestructureVarnode::protectSwitchPathIndirects(PcodeOp *op)

{
  PcodeOp *lastIndirect = (PcodeOp *)0;
  Varnode *curVn = op->getIn(0);
  while(curVn->isWritten()) {
    PcodeOp *curOp = curVn->getDef();
    uint4 evalType = curOp->getEvalType();
    if ((evalType & (PcodeOp::binary | PcodeOp::ternary)) != 0) {
      if (curOp->numInput() > 1) {
	if (isDelayedConstant(curOp->getIn(1)))
	  curVn = curOp->getIn(0);
	else if (isDelayedConstant(curOp->getIn(0)))
	  curVn = curOp->getIn(1);
	else
	  return;		// Multiple paths
      }
      else {
	curVn = curOp->getIn(0);
      }
    }
    else if ((evalType & PcodeOp::unary) != 0)
      curVn = curOp->getIn(0);
    else if (curOp->code() == CPUI_INDIRECT) {
      lastIndirect = curOp;
      curVn = curOp->getIn(0);
    }
    else if (curOp->code() == CPUI_LOAD) {
      curVn = curOp->getIn(1);
    }
    else if (curOp->code() == CPUI_MULTIEQUAL) {
      // Its possible there is a path from a constant that splits and rejoins.
      // We test for INDIRECTs coming into the MULTIEQUAL.  If there is at least one, we prevent it from collapsing,
      // otherwise we assume the MULTIEQUAL itself is unlikely to collapse.
      for(int4 i=0;i<curOp->numInput();++i) {
	curVn = curOp->getIn(i);
	if (!curVn->isWritten()) continue;
	PcodeOp *inOp = curVn->getDef();
	if (inOp->code() == CPUI_INDIRECT) {
	  inOp->setNoIndirectCollapse();
	  break;
	}
      }
      return;	// In any case, we don't try to backtrack further
    }
    else
      return;
  }
  if (!curVn->isConstant()) return;
  // If we reach here, there is exactly one path, from a constant to a switch
  if (lastIndirect != (PcodeOp *)0)
    lastIndirect->setNoIndirectCollapse();
}

/// Run through BRANCHIND ops, treat them as switches and protect the data-flow path to the destination variable
/// \param data is the function to examine
void ActionRestructureVarnode::protectSwitchPaths(Funcdata &data)

{
  const BlockGraph &bblocks(data.getBasicBlocks());
  for(int4 i=0;i<bblocks.getSize();++i) {
    PcodeOp *op = bblocks.getBlock(i)->lastOp();
    if (op == (PcodeOp *)0) continue;
    if (op->code() != CPUI_BRANCHIND) continue;
    protectSwitchPathIndirects(op);
  }
}

int4 ActionRestructureVarnode::apply(Funcdata &data)

{
  ScopeLocal *l1 = data.getScopeLocal();

  bool aliasyes = (numpass != 0);	// Alias calculations are not reliable on the first pass
  l1->restructureVarnode(aliasyes);
  if (data.syncVarnodesWithSymbols(l1,false,aliasyes))
    count += 1;

  if (data.isJumptableRecoveryOn())
    protectSwitchPaths(data);

  numpass += 1;
#ifdef OPACTION_DEBUG
  if ((flags&rule_debug)==0) return 0;
  ostringstream s;
  data.getScopeLocal()->printEntries(s);
  data.getArch()->printDebug(s.str());
#endif
  return 0;
}

int4 ActionMappedLocalSync::apply(Funcdata &data)

{
  ScopeLocal *l1 = data.getScopeLocal();

  if (data.syncVarnodesWithSymbols(l1,true,true))
    count += 1;

  if (l1->hasOverlapProbems())
    data.warningHeader("Could not reconcile some variable overlaps");

  return 0;
}

int4 ActionDefaultParams::apply(Funcdata &data)

{
  int4 i,size;
  FuncCallSpecs *fc;
  ProtoModel *evalfp = data.getArch()->evalfp_called; // Special model used when evaluating called funcs
  if (evalfp == (ProtoModel *)0) // If no special evaluation
    evalfp = data.getArch()->defaultfp;	// Use the default model

  size = data.numCalls();
  for(i=0;i<size;++i) {
    fc = data.getCallSpecs(i);
    if (!fc->hasModel()) {
      Funcdata *otherfunc = fc->getFuncdata();

      if (otherfunc != (Funcdata *)0) {
	fc->copy(otherfunc->getFuncProto());
	if ((!fc->isModelLocked())&& !fc->hasMatchingModel(evalfp))
	  fc->setModel(evalfp);
      }
      else
	fc->setInternal(evalfp,data.getArch()->types->getTypeVoid());
    }
    fc->insertPcode(data);	// Insert any necessary pcode
  }
  return 0;			// Indicate success
}

/// \brief Check if the data-type of the given value being used as a pointer makes sense
///
/// If the data-type is a pointer make sure:
///   - The pointed-to size matches the size of the value being loaded are stored
///   - Any address space attached to the pointer matches the address space of the LOAD/STORE
///
/// If any of the conditions are violated, a warning is added to the output.
/// \param op is the LOAD/STORE acting on a pointer
/// \param vn is the given value being used as a pointer
/// \param data is the function containing the PcodeOp
void ActionSetCasts::checkPointerIssues(PcodeOp *op,Varnode *vn,Funcdata &data)

{
  if (op->doesSpecialPrinting()) return;
  Datatype *ptrtype = op->getIn(1)->getHighTypeReadFacing(op);
  int4 valsize = vn->getSize();
  if ((ptrtype->getMetatype()!=TYPE_PTR)|| (((TypePointer *)ptrtype)->getPtrTo()->getSize() != valsize)) {
    string name = op->getOpcode()->getName();
    name[0] = toupper( name[0] );
    data.warning(name + " size is inaccurate",op->getAddr());
  }
  if (ptrtype->getMetatype()==TYPE_PTR) {
    AddrSpace *spc = ((TypePointer *)ptrtype)->getSpace();
    if (spc != (AddrSpace *)0) {
      AddrSpace *opSpc = op->getIn(0)->getSpaceFromConst();
      if (opSpc != spc && spc->getContain() != opSpc) {
	string name = op->getOpcode()->getName();
	name[0] = toupper( name[0] );
	ostringstream s;
	s << name << " refers to '" << opSpc->getName() << "' but pointer attribute is '";
	s << spc->getName() << '\'';
	data.warning(s.str(),op->getAddr());
      }
    }
  }
}

/// \brief Test if the given cast conflict can be resolved by passing to the first structure/array field
///
/// Test if the current data-type is a pointer to a structure and if interpreting
/// the data-type as a pointer to the structure's first field will get it to match the
/// required data-type.
/// \param reqtype is the required data-type
/// \param curtype is the current data-type
/// \param castStrategy is used to determine if the data-types are compatible
/// \return \b true if a pointer to the first field makes sense
bool ActionSetCasts::testStructOffset0(Datatype *reqtype,Datatype *curtype,CastStrategy *castStrategy)

{
  if (curtype->getMetatype() != TYPE_PTR) return false;
  Datatype *highPtrTo = ((TypePointer *)curtype)->getPtrTo();
  if (highPtrTo->getMetatype() == TYPE_STRUCT) {
    TypeStruct *highStruct = (TypeStruct *)highPtrTo;
    if (highStruct->numDepend() == 0) return false;
    vector<TypeField>::const_iterator iter = highStruct->beginField();
    if ((*iter).offset != 0) return false;
    reqtype = ((TypePointer *)reqtype)->getPtrTo();
    curtype = (*iter).type;
    if (reqtype->getMetatype() == TYPE_ARRAY)
      reqtype = ((TypeArray *)reqtype)->getBase();
    if (curtype->getMetatype() == TYPE_ARRAY)
      curtype = ((TypeArray *)curtype)->getBase();
  }
  else if (highPtrTo->getMetatype() == TYPE_ARRAY) {
    TypeArray *highArray = (TypeArray *)highPtrTo;
    reqtype = ((TypePointer *)reqtype)->getPtrTo();
    curtype = highArray->getBase();
  }
  else {
    return false;
  }
  if (reqtype->getMetatype() == TYPE_VOID) {
    return false;		// Don't induce PTRSUB for "void *"
  }
  return (castStrategy->castStandard(reqtype, curtype, true, true) == (Datatype *)0);
}

/// \brief Try to eliminate a CAST for a data-type needing resolution by matching the data-type needed by the p-code op
///
/// Merging can cause the high data-type to become unresolved even though the underlying data-type requires a specific
/// resolution.  This forces the resolution onto the high, if possible, in the context of the specific read or write.
/// \param dt is the data-type needed by the p-code op
/// \param op is the p-code op
/// \param slot is the index of the slot to test for resolution (-1 for output, >= 0 for input)
/// \param data is the function
/// \return \b true if the resolution was successfully changed and a CAST is not needed
bool ActionSetCasts::tryResolutionAdjustment(Datatype *dt,PcodeOp *op,int4 slot,Funcdata &data)

{
  if (dt->needsResolution()) return false;
  Varnode *vn = (slot < 0) ? op->getOut() : op->getIn(slot);
  Datatype *curType = vn->getHigh()->getType();
  if (!curType->needsResolution()) return false;
  if (slot < 0 && curType->getMetatype() == TYPE_PTR) return false;	// Cannot take field of pointer during assignment
  int4 fieldNum = curType->findCompatibleResolve(dt);
  if (fieldNum < 0) return false;
  TypeFactory *typegrp = data.getArch()->types;
  ResolvedUnion resolve(curType,fieldNum,*typegrp);
  if (!data.setUnionField(curType, op, slot, resolve))
    return false;
  if (slot >=0 && curType->getMetatype() == TYPE_PTR) {
    if (vn->isWritten() && (vn->getDef()->code() != CPUI_PTRSUB || vn->getDef()->getIn(0)->getType() != curType)) {
      // For pointers, if not already inserted, insert a PTRSUB representing the field access
      PcodeOp *ptrsub = insertPtrsubZero(op,slot,resolve.getDatatype(),data);
      data.setUnionField(curType, ptrsub,-1,resolve);			// Attach the resolution to the PTRSUB
    }
  }
  return true;
}

/// \brief Try to adjust the input and output Varnodes to a COPY, in order to eliminate a CAST
///
/// If input/output data-types are different, it may be due to late merges.  For
/// unions, the CAST can sometimes be eliminated by adjusting the data-type resolutions
/// of the Varnodes relative to the PcodeOp
/// \param op is the COPY
/// \param data is the function
/// \return \b true if an adjustment is made so that a CAST is no longer needed
bool ActionSetCasts::tryResolutionCopy(PcodeOp *op,Funcdata &data)

{
  Varnode *outvn = op->getOut();
  if (outvn == (Varnode *)0)
    return false;
  Datatype *outType = outvn->getHigh()->getType();
  Datatype *inType = op->getIn(0)->getHigh()->getType();
  if (!inType->needsResolution() && !outType->needsResolution()) return false;
  int4 inResolve = -1;
  int4 outResolve = -1;
  if (inType->needsResolution()) {
    inResolve = inType->findCompatibleResolve(outType);
    if (inResolve < 0) return false;
  }
  if (outType->needsResolution()  && outType->getMetatype() != TYPE_PTR) {
    if (inResolve >= 0)
      outResolve = outType->findCompatibleResolve(inType->getDepend(inResolve));
    else
      outResolve = outType->findCompatibleResolve(inType);
    if (outResolve < 0) return false;
  }

  TypeFactory *typegrp = data.getArch()->types;
  if (inResolve >= 0) {
    ResolvedUnion resolve(inType,inResolve,*typegrp);
    if (!data.setUnionField(inType, op, 0, resolve))
      return false;
  }
  if (outResolve >= 0) {
    ResolvedUnion resolve(outType,outResolve,*typegrp);
    if (!data.setUnionField(outType, op, -1, resolve))
      return false;
  }
  return true;
}

/// \brief Test if two data-types are operation identical
///
/// If, at a source code level, a variable with data-type \b ct1 can be
/// legally substituted for another variable with data-type \b ct2, return \b true.
/// The substitution must be allowed for all possible operations the variable
/// may be involved in.
/// \param ct1 is the first data-type
/// \param ct2 is the second data-type
bool ActionSetCasts::isOpIdentical(Datatype *ct1,Datatype *ct2)

{
  while((ct1->getMetatype()==TYPE_PTR)&&(ct2->getMetatype()==TYPE_PTR)) {
    ct1 = ((const TypePointer *)ct1)->getPtrTo();
    ct2 = ((const TypePointer *)ct2)->getPtrTo();
  }
  while(ct1->getTypedef() != (Datatype *)0)
    ct1 = ct1->getTypedef();
  while(ct2->getTypedef() != (Datatype *)0)
    ct2 = ct2->getTypedef();
  return (ct1 == ct2);
}

/// \brief If the given op reads a pointer to a union, insert the CPUI_PTRSUB that resolves the union
///
/// \param op is the given PcodeOp
/// \param slot is index of the input slot being read
/// \param data is the containing function
/// \param castStrategy is used to determine if the cast is still necessary after resolution
/// \return 1 if a PTRSUB is inserted, 0 otherwise
int4 ActionSetCasts::resolveUnion(PcodeOp *op,int4 slot,Funcdata &data,CastStrategy *castStrategy)

{
  Varnode *vn = op->getIn(slot);
  if (vn->isAnnotation()) return 0;
  Datatype *dt = vn->getHigh()->getType();
  if (!dt->needsResolution())
    return 0;
  const ResolvedUnion *resUnion = data.getUnionField(dt, op, slot);
  if (resUnion == (ResolvedUnion *)0) {
    dt->resolveInFlow(op, slot);	// Last chance to resolve data-type based on flow
    resUnion = data.getUnionField(dt, op, slot);
  }
  if (resUnion != (ResolvedUnion *)0 && resUnion->getFieldNum() >= 0) {
    if (dt->getMetatype() == TYPE_PTR) {
      // Test if a cast is still needed even after resolution
      Datatype *reqtype = vn->getTypeReadFacing(op);
      if (castStrategy->castStandard(reqtype, resUnion->getDatatype(), true, true) != (Datatype *)0)
	return 0;	// If cast still needed, don't do the resolve
      // Insert specific placeholder indicating which field is accessed
      PcodeOp *ptrsub = insertPtrsubZero(op,slot,reqtype,data);
      data.setUnionField(dt, ptrsub,-1,*resUnion);			// Attach the resolution to the PTRSUB
    }
    else if (vn->isImplied()) {
      if (vn->isWritten()) {
	// If the writefacing and readfacing resolutions for vn (an implied variable) are the same,
	// the resolutions are unnecessary and we treat the vn as if it had the field data-type
	const ResolvedUnion *writeRes = data.getUnionField(dt, vn->getDef(), -1);
	if (writeRes != (const ResolvedUnion *)0 && writeRes->getFieldNum() == resUnion->getFieldNum())
	  return 0;	// Don't print implied fields for vn
      }
      vn->setImpliedField();
    }
    return 1;
  }
  return 0;
}

/// \brief Insert cast to output Varnode type after given PcodeOp if it is necessary
///
/// \param op is the given PcodeOp
/// \param data is the function being analyzed
/// \param castStrategy is used to determine if the cast is necessary
/// \return 1 if a cast inserted, 0 otherwise
int4 ActionSetCasts::castOutput(PcodeOp *op,Funcdata &data,CastStrategy *castStrategy)

{
  Datatype *outct,*ct,*tokenct;
  Varnode *vn,*outvn;
  PcodeOp *newop;
  bool force=false;

  tokenct = op->getOpcode()->getOutputToken(op,castStrategy);
  outvn = op->getOut();
  Datatype *outHighType = outvn->getHigh()->getType();
  if (tokenct == outHighType) {
    if (tokenct->needsResolution()) {
      // operation copies directly to outvn AS a union
      ResolvedUnion resolve(tokenct);	// Force the varnode to resolve to the parent data-type
      data.setUnionField(tokenct, op, -1, resolve);
    }
    // Short circuit more sophisticated casting tests.  If they are the same type, there is no cast
    return 0;
  }
  Datatype *outHighResolve = outvn->getHighTypeDefFacing();
  if (outvn->isImplied()) {
    // implied varnode must have parse type
    if (outvn->isTypeLock()) {
      PcodeOp *outOp = outvn->loneDescend();
      // The Varnode input to a CPUI_RETURN is marked as implied but
      // casting should act as if it were explicit
      if (outOp == (PcodeOp *)0 || outOp->code() != CPUI_RETURN) {
	force = !isOpIdentical(outHighResolve, tokenct);
      }
    }
    else if (outHighResolve->getMetatype() != TYPE_PTR) {	// If implied varnode has an atomic (non-pointer) type
      outvn->updateType(tokenct); // Ignore it in favor of the token type
      outHighResolve = outvn->getHighTypeDefFacing();
    }
    else if (tokenct->getMetatype() == TYPE_PTR) { // If the token is a pointer AND implied varnode is pointer
      outct = ((TypePointer *)outHighResolve)->getPtrTo();
      type_metatype meta = outct->getMetatype();
      // Preserve implied pointer if it points to a composite
      if ((meta!=TYPE_ARRAY)&&(meta!=TYPE_STRUCT)&&(meta!=TYPE_UNION)) {
	outvn->updateType(tokenct); // Otherwise ignore it in favor of the token type
	outHighResolve = outvn->getHighTypeDefFacing();
      }
    }
  }
  OpCode opc = CPUI_CAST;
  if (!force) {
    outct = outHighResolve;	// Type of result
    if (outct->getMetatype() == TYPE_PTR && testStructOffset0(outct, tokenct, castStrategy)) {
      opc = CPUI_PTRSUB;
    }
    else {
      ct = castStrategy->castStandard(outct,tokenct,false,true);
      if (ct == (Datatype *)0) return 0;
    }
    if (tryResolutionAdjustment(tokenct, op, -1, data))
      return 0;
  }
				// Generate the cast op
  vn = data.newUnique(outvn->getSize());
  vn->updateType(tokenct);
  vn->setImplied();
  newop = data.newOp((opc != CPUI_CAST) ? 2 : 1,op->getAddr());
#ifdef CPUI_STATISTICS
  data.getArch()->stats->countCast();
#endif
  data.opSetOpcode(newop,opc);
  data.opSetOutput(newop,outvn);
  data.opSetInput(newop,vn,0);
  if (opc != CPUI_CAST) {
    data.opSetInput(newop,data.newConstant(4, 0),1);
  }
  data.opSetOutput(op,vn);
  data.opInsertAfter(newop,op); // Cast comes AFTER this operation
  if (tokenct->needsResolution())
    data.forceFacingType(tokenct, -1, newop, 0);
  if (outHighType->needsResolution())
    data.inheritUnionField(outHighType, newop, -1, op, -1);	// Inherit write resolution

  return 1;
}

/// \brief Insert a PTRSUB with offset 0 that accesses a field of the given data-type
///
/// The data-type can be a structure, in which case the field at offset zero is being accessed.
/// The data-type can reference a union, in which case a specific field is being accessed
/// as indicated by Funcdata::getUnionField.  The PTRSUB is inserted right before the given
/// PcodeOp.  The indicated input Varnode becomes the PTRSUB input, and the PTRSUB output
/// replaces the Varnode in the PcodeOp.
/// \param op is the given PcodeOp where the PTRSUB is inserted
/// \param slot is the slot corresponding to the indicated Varnode
/// \param ct is the data-type produced by the PTRSUB
/// \param data is containing Function
/// \return the new PTRSUB op
PcodeOp *ActionSetCasts::insertPtrsubZero(PcodeOp *op,int4 slot,Datatype *ct,Funcdata &data)

{
  Varnode *vn = op->getIn(slot);
  PcodeOp *newop = data.newOp(2,op->getAddr());
  Varnode *vnout = data.newUniqueOut(vn->getSize(), newop);
  vnout->updateType(ct);
  vnout->setImplied();
  data.opSetOpcode(newop, CPUI_PTRSUB);
  data.opSetInput(newop,vn,0);
  data.opSetInput(newop,data.newConstant(4, 0),1);
  data.opSetInput(op,vnout,slot);
  data.opInsertBefore(newop,op);
  return newop;
}

/// \brief Insert cast to produce the input Varnode to a given PcodeOp if necessary
///
/// This method can also mark a Varnode as an explicit integer constant.
/// Guard against chains of casts.
/// \param op is the given PcodeOp
/// \param slot is the slot of the input Varnode
/// \param data is the function being analyzed
/// \param castStrategy is used to determine if a cast is necessary
/// \return 1 if a change is made, 0 otherwise
int4 ActionSetCasts::castInput(PcodeOp *op,int4 slot,Funcdata &data,CastStrategy *castStrategy)

{
  Datatype *ct;
  Varnode *vn,*vnout,*vnin;
  PcodeOp *newop;

  ct = op->getOpcode()->getInputCast(op,slot,castStrategy); // Input type expected by this operation
  if (ct == (Datatype *)0) {
    bool resUnsigned = castStrategy->markExplicitUnsigned(op, slot);
    bool resSized = castStrategy->markExplicitLongSize(op, slot);
    if (resUnsigned || resSized)
      return 1;
    return 0;
  }

  vnin = vn = op->getIn(slot);
  // Check to make sure we don't have a double cast
  if (vn->isWritten() && (vn->getDef()->code() == CPUI_CAST)) {
    if (vn->isImplied()) {
      if (vn->loneDescend() == op) {
	vn->updateType(ct);
	if (vn->getType()==ct)
	  return 1;
      }
      vnin = vn->getDef()->getIn(0);	// Cast directly from input of previous cast
      if (ct == vnin->getType()) {	// If the earlier data-type is what the input expects
	data.opSetInput(op, vnin, slot);	// Just use the earlier Varnode
	return 1;
      }
    }
  }
  else if (vn->isConstant()) {
    vn->updateType(ct);
    if (vn->getType() == ct)
      return 1;
  }
  else if (ct->getMetatype() == TYPE_PTR && testStructOffset0(ct, vn->getHighTypeReadFacing(op), castStrategy)) {
    // Insert a PTRSUB(vn,#0) instead of a CAST
    newop = insertPtrsubZero(op, slot, ct, data);
    if (vn->getHigh()->getType()->needsResolution())
      data.inheritUnionField(vn->getHigh()->getType(),newop, 0, op, slot);
    return 1;
  }
  else if (op->code() != CPUI_COPY && tryResolutionAdjustment(ct, op, slot, data))
    return 1;
  else if (op->code() == CPUI_COPY && tryResolutionCopy(op, data)) {
    return 1;
  }
  newop = data.newOp(1,op->getAddr());
  vnout = data.newUniqueOut(vnin->getSize(),newop);
  vnout->updateType(ct);
  vnout->setImplied();
#ifdef CPUI_STATISTICS
  data.getArch()->stats->countCast();
#endif
  data.opSetOpcode(newop,CPUI_CAST);
  data.opSetInput(newop,vnin,0);
  data.opSetInput(op,vnout,slot);
  data.opInsertBefore(newop,op); // Cast comes AFTER operation
  if (ct->needsResolution()) {
    data.forceFacingType(ct, -1, newop, -1);
  }
  if (vn->getHigh()->getType()->needsResolution()) {
    data.inheritUnionField(vn->getHigh()->getType(),newop, 0, op, slot);
  }
  return 1;
}

int4 ActionSetCasts::apply(Funcdata &data)

{
  list<PcodeOp *>::const_iterator iter;
  PcodeOp *op;

  data.startCastPhase();
  CastStrategy *castStrategy = data.getArch()->print->getCastStrategy();
  // We follow data flow, doing basic blocks in dominance order
  // Doing operations in basic block order
  const BlockGraph &basicblocks( data.getBasicBlocks() );
  for(int4 j=0;j<basicblocks.getSize();++j) {
    BlockBasic *bb = (BlockBasic *)basicblocks.getBlock(j);
    for(iter=bb->beginOp();iter!=bb->endOp();++iter) {
      op = *iter;
      if (op->notPrinted()) continue;
      OpCode opc = op->code();
      if (opc == CPUI_CAST) continue;
      if (opc == CPUI_PTRADD) {	// Check for PTRADD that no longer fits its pointer
	int4 sz = (int4)op->getIn(2)->getOffset();
	Datatype *ct = op->getIn(0)->getHighTypeReadFacing(op);
	if (ct->getMetatype() != TYPE_PTR ||
	    ((TypePointer *)ct)->getPtrTo()->getAlignSize() != AddrSpace::addressToByteInt(sz, ((TypePointer *)ct)->getWordSize()))
	  data.opUndoPtradd(op,true);
      }
      else if (opc == CPUI_PTRSUB) {	// Check for PTRSUB that no longer fits pointer
	if (!op->getIn(0)->getTypeReadFacing(op)->isPtrsubMatching(op->getIn(1)->getOffset(),0,0)) {
	  if (op->getIn(1)->getOffset() == 0) {
	    data.opRemoveInput(op, 1);
	    data.opSetOpcode(op, CPUI_COPY);
	  }
	  else
	    data.opSetOpcode(op, CPUI_INT_ADD);
	}
      }
      // Allow unresolved high data-types to resolve
      for(int4 i=0;i<op->numInput();++i) {
	count += resolveUnion(op, i, data, castStrategy);
      }
      Varnode *vn = op->getOut();
      if (vn != (Varnode *)0) {
	Datatype *outHighType = vn->getHigh()->getType();
	if (outHighType->needsResolution())
	  outHighType->resolveInFlow(op, -1);		// Last chance to resolve data-type based on flow
      }
      // Do input casts first, as output may depend on input
      for(int4 i=0;i<op->numInput();++i) {
	count += castInput(op,i,data,castStrategy);
      }
      if (opc == CPUI_LOAD) {
	checkPointerIssues(op, op->getOut(), data);
      }
      else if (opc == CPUI_STORE) {
	checkPointerIssues(op, op->getIn(2), data);
      }
      if (vn != (Varnode *)0)
	count += castOutput(op,data,castStrategy);
    }
  }
  return 0;			// Indicate full completion
}

/// Name the Varnode which seems to be the putative switch variable for an
/// unrecovered jump-table with a special name.
/// \param data is the function being analyzed
void ActionNameVars::lookForBadJumpTables(Funcdata &data)

{
  int4 numfunc = data.numCalls();
  ScopeLocal *localmap = data.getScopeLocal();
  for(int4 i=0;i<numfunc;++i) {
    FuncCallSpecs *fc = data.getCallSpecs(i);
    if (fc->isBadJumpTable()) {
      PcodeOp *op = fc->getOp();
      Varnode *vn = op->getIn(0);
      if (vn->isImplied()&&vn->isWritten()) { // Skip any cast into the function
	PcodeOp *castop = vn->getDef();
	if (castop->code() == CPUI_CAST)
	  vn = castop->getIn(0);
      }
      if (vn->isFree()) continue;
      Symbol *sym = vn->getHigh()->getSymbol();
      if (sym == (Symbol *)0) continue;
      if (sym->isNameLocked()) continue; // Override any unlocked name
      if (sym->getScope() != localmap) continue; // Only name this in the local scope
      string newname = "UNRECOVERED_JUMPTABLE";
      sym->getScope()->renameSymbol(sym,localmap->makeNameUnique(newname));
    }
  }
}

/// \brief Add a recommendation to the database based on a particular sub-function parameter.
///
/// We know \b vn holds data-flow for parameter \b param,  try to attach its name to \b vn's symbol.
/// We update map from \b vn to a name recommendation record.
/// If \b vn is input to multiple functions, the one whose parameter has the most specified type
/// will be preferred. If \b vn is passed to the function via a cast, this name will only be used
/// if there is no other function that takes \b vn as a parameter.
/// \param param is function prototype symbol
/// \param vn is the Varnode associated with the parameter
/// \param recmap is the recommendation map
void ActionNameVars::makeRec(ProtoParameter *param,Varnode *vn,map<HighVariable *,OpRecommend> &recmap)

{
  if (!param->isNameLocked()) return;
  if (param->isNameUndefined()) return;
  if (vn->getSize() != param->getSize()) return;
  Datatype *ct = param->getType();
  if (vn->isImplied()&&vn->isWritten()) { // Skip any cast into the function
    PcodeOp *castop = vn->getDef();
    if (castop->code() == CPUI_CAST) {
      vn = castop->getIn(0);
      ct = (Datatype *)0;	// Indicate that this is a less preferred name
    }
  }
  HighVariable *high = vn->getHigh();
  if (high->isAddrTied()) return;	// Don't propagate parameter name to address tied variable
  if (param->getName().compare(0,6,"param_")==0) return;

  map<HighVariable *,OpRecommend>::iterator iter = recmap.find(high);
  if (iter != recmap.end()) {	// We have seen this varnode before
    if (ct == (Datatype *)0) return; // Cannot override with null (casted) type
    Datatype *oldtype = (*iter).second.ct;
    if (oldtype != (Datatype *)0) {
      if (oldtype->typeOrder(*ct) <= 0) return; // oldtype is more specified
    }
    (*iter).second.ct = ct;
    (*iter).second.namerec = param->getName();
  }
  else {
    OpRecommend oprec;
    oprec.ct = ct;
    oprec.namerec = param->getName();
    recmap[high] = oprec;
  }
}

/// \brief Collect potential variable names from sub-function parameters.
///
/// Run through all sub-functions with a known prototype and collect potential
/// names for current Varnodes used to pass the parameters. For these Varnodes,
/// select from among these names.
/// \param data is the function being analyzed
/// \param varlist is a list of Varnodes representing HighVariables that need names
void ActionNameVars::lookForFuncParamNames(Funcdata &data,const vector<Varnode *> &varlist)

{
  int4 numfunc = data.numCalls();
  if (numfunc == 0) return;

  map<HighVariable *,OpRecommend> recmap;

  ScopeLocal *localmap = data.getScopeLocal();
  for(int4 i=0;i<numfunc;++i) {	// Run through all calls to functions
    FuncCallSpecs *fc = data.getCallSpecs(i);
    if (!fc->isInputLocked()) continue;
    PcodeOp *op = fc->getOp();
    int4 numparam = fc->numParams();
    if (numparam >= op->numInput())
      numparam = op->numInput()-1;
    for(int4 j=0;j<numparam;++j) {
      ProtoParameter *param = fc->getParam(j); // Looking for a parameter
      Varnode *vn = op->getIn(j+1);
      makeRec(param,vn,recmap);
    }
  }
  if (recmap.empty()) return;

  map<HighVariable *,OpRecommend>::iterator iter;
  for(uint4 i=0;i<varlist.size();++i) {	// Do the actual naming in the original (address based) order
    Varnode *vn = varlist[i];
    if (vn->isFree()) continue;
    if (vn->isInput()) continue;	// Don't override unaffected or input naming strategy
    HighVariable *high = vn->getHigh();
    if (high->getNumMergeClasses() > 1) continue;	// Don't inherit a name if speculatively merged
    Symbol *sym = high->getSymbol();
    if (sym == (Symbol *)0) continue;
    if (!sym->isNameUndefined()) continue;
    iter = recmap.find(high);
    if (iter != recmap.end()) {
      sym->getScope()->renameSymbol(sym,localmap->makeNameUnique((*iter).second.namerec));
    }
  }
}

/// \brief Link symbols associated with a given \e spacebase Varnode
///
/// Look for PTRSUB ops which indicate a symbol reference within the address space
/// referred to by the \e spacebase Varnode.  Decode any symbol reference and link it
/// to the appropriate HighVariable
/// \param vn is the given \e spacebase Varnode
/// \param data is the function containing the Varnode
/// \param namerec is used to store any recovered Symbol without a name
void ActionNameVars::linkSpacebaseSymbol(Varnode *vn,Funcdata &data,vector<Varnode *> &namerec)

{
  if (!vn->isConstant() && !vn->isInput()) return;
  list<PcodeOp *>::const_iterator iter;
  for(iter=vn->beginDescend();iter!=vn->endDescend();++iter) {
    PcodeOp *op = *iter;
    if (op->code() != CPUI_PTRSUB) continue;
    Varnode *offVn = op->getIn(1);
    Symbol *sym = data.linkSymbolReference(offVn);
    if ((sym != (Symbol *)0) && sym->isNameUndefined())
      namerec.push_back(offVn);
  }
}

/// \brief Link formal Symbols to their HighVariable representative in the given Function
///
/// Run through all HighVariables for the given function and set up the explicit mapping with
/// existing Symbol objects.  If there is no matching Symbol for a given HighVariable, a new
/// Symbol is created. Any Symbol that does not have a name is added to a list for further
/// name resolution.
/// \param data is the given function
/// \param namerec is the container for collecting Symbols with a name
void ActionNameVars::linkSymbols(Funcdata &data,vector<Varnode *> &namerec)

{
  const AddrSpaceManager *manage = data.getArch();
  VarnodeLocSet::const_iterator iter,enditer;
  AddrSpace *spc;
  AddrSpace *constSpace = manage->getConstantSpace();
  enditer = data.endLoc(constSpace);
  for(iter=data.beginLoc(constSpace);iter!=enditer;++iter) {
    Varnode *curvn = *iter;
    if (curvn->getSymbolEntry() != (SymbolEntry *)0)
      data.linkSymbol(curvn);		// Special equate symbol
    else if (curvn->isSpacebase())
      linkSpacebaseSymbol(curvn, data, namerec);
  }

  TypeFactory *typeFactory = data.getArch()->types;
  for(int4 i=0;i<manage->numSpaces();++i) { // Build a list of nameable highs
    spc = manage->getSpace(i);
    if (spc == (AddrSpace *)0) continue;
    if (spc == constSpace) continue;
    enditer = data.endLoc(spc);
    for(iter=data.beginLoc(spc);iter!=enditer;++iter) {
      Varnode *curvn = *iter;
      if (curvn->isFree()) {
	continue;
      }
      if (curvn->isSpacebase())
	linkSpacebaseSymbol(curvn, data, namerec);
      Varnode *vn = curvn->getHigh()->getNameRepresentative();
      if (vn != curvn) continue; // Hit each high only once
      HighVariable *high = vn->getHigh();
      if (!high->hasName()) continue;
      Symbol *sym = data.linkSymbol(vn);
      if (sym != (Symbol *)0) {	// Can we associate high with a nameable symbol
	if (sym->isNameUndefined() && high->getSymbolOffset() < 0)
	  namerec.push_back(vn);	// Add if no name, and we have a high representing the whole
	if (sym->isSizeTypeLocked()) {
	  if (vn->getSize() == sym->getType()->getSize())
	    sym->getScope()->overrideSizeLockType(sym,high->getType());
	}
	if (vn->isAddrTied() && !sym->getScope()->isGlobal())
	  high->finalizeDatatype(typeFactory);
      }
    }
  }
}

int4 ActionNameVars::apply(Funcdata &data)

{
  vector<Varnode *> namerec;

  linkSymbols(data, namerec);
  data.getScopeLocal()->recoverNameRecommendationsForSymbols(); // Make sure recommended names hit before subfunc
  lookForBadJumpTables(data);
  lookForFuncParamNames(data,namerec);

  int4 base = 1;
  for(uint4 i=0;i<namerec.size();++i) {
    Varnode *vn = namerec[i];
    Symbol *sym = vn->getHigh()->getSymbol();
    if (sym->isNameUndefined()) {
      Scope *scope = sym->getScope();
      string newname = scope->buildDefaultName(sym, base, vn);
      scope->renameSymbol(sym,newname);
    }
  }
  data.getScopeLocal()->assignDefaultNames(base);
  return 0;
}

/// If the given Varnode is defined by CPUI_NEW, return -2 indicating it should be explicit
/// and that it needs special printing.
/// \param vn is the given Varnode
/// \param maxref is the maximum number of references to consider before forcing explicitness
/// \return -1 or -2 if given Varnode should be marked explicit, the number of descendants otherwise
int4 ActionMarkExplicit::baseExplicit(Varnode *vn,int4 maxref)

{
  list<PcodeOp *>::const_iterator iter;

  PcodeOp *def = vn->getDef();
  if (def == (PcodeOp *)0) return -1;
  if (def->isMarker()) return -1;
  if (def->isCall()) {
    if ((def->code() == CPUI_NEW)&&(def->numInput() == 1))
      return -2;		// Explicit, but may need special printing
    return -1;
  }
  HighVariable *high = vn->getHigh();
  if ((high!=(HighVariable *)0)&&(high->numInstances()>1)) return -1; // Must not be merged at all
  if (vn->isAddrTied()) {		// We need to see addrtied as explicit because pointers may reference it
    if (def->code() == CPUI_SUBPIECE) {
      Varnode *vin = def->getIn(0);
      if (vin->isAddrTied()) {
        if (vn->overlapJoin(*vin) == def->getIn(1)->getOffset())
          return -1;		// Should be explicit, will be a copymarker and not printed
      }
    }
    PcodeOp *useOp = vn->loneDescend();
    if (useOp == (PcodeOp *)0) return -1;
    if (useOp->code() == CPUI_INT_ZEXT) {
      Varnode *vnout = useOp->getOut();
      if ((!vnout->isAddrTied())||(0!=vnout->contains(*vn)))
	return -1;
    }
    else if (useOp->code() == CPUI_PIECE) {
      Varnode *rootVn = PieceNode::findRoot(vn);
      if (vn == rootVn) return -1;
      if (rootVn->getDef()->isPartialRoot()) {
	// Varnode is getting PIECEd into a structure.  All such PIECE operations should be explicit.
	// Internal PIECE operations will be hidden.
	return -1;
      }
    }
    else {
      return -1;
    }
  }
  else if (vn->isMapped()) {
    // If NOT addrtied but is still mapped, there must be either a first use (register) mapping
    // or a dynamic mapping causing the bit to be set. In either case, it should probably be explicit
    return -1;
  }
  else if (vn->isProtoPartial()) {
    // Varnode is getting PIECEd into a structure.  All such PIECE operations should be explicit.
    // Internal PIECE operations will be hidden.
    return -1;
  }
  else if (def->code() == CPUI_PIECE && def->getIn(0)->isProtoPartial()) {
    // The base of PIECE operations building a structure should be explicit.
    return -1;
  }
  if (vn->hasNoDescend()) return -1;	// Must have at least one descendant
  if (def->code() == CPUI_INSERT) {
    PcodeOp *storeOp = def->getOut()->loneDescend();
    if (storeOp == (PcodeOp *)0 || storeOp->code() != CPUI_STORE)
      return -1;		// INSERT output is explicit unless it is immediately used by STORE
  }

  if (def->code() == CPUI_PTRSUB) { // A dereference
    Varnode *basevn = def->getIn(0);
    if (basevn->isSpacebase()) { // of a spacebase
      if (basevn->isConstant() || basevn->isInput())
	maxref = 1000000;	// Should always be implicit, so remove limit on max references
    }
  }
  int4 desccount = 0;
  for(iter=vn->beginDescend();iter!=vn->endDescend();++iter) {
    PcodeOp *op = *iter;
    if (op->isMarker()) return -1;
    desccount += 1;
    if (desccount > maxref) return -1; // Must not exceed max descendants
  }

  return desccount;
}

/// Look for certain situations where one Varnode with multiple descendants has one descendant who also has
/// multiple descendants.  This routine is handed the list of Varnodes with multiple descendants;
/// These all must already have their mark set.
/// For the situations we can find with one flowing into another, mark the top Varnode
/// as \e explicit.
/// \param multlist is the list Varnodes with multiple descendants
/// \return the number Varnodes that were marked as explicit
int4 ActionMarkExplicit::multipleInteraction(vector<Varnode *> &multlist)

{
  vector<Varnode *> purgelist;

  for(int4 i=0;i<multlist.size();++i) {
    Varnode *vn = multlist[i];	// All elements in this list should have a defining op
    PcodeOp *op = vn->getDef();
    OpCode opc = op->code();
    if (op->isBoolOutput() || (opc == CPUI_INT_ZEXT) || (opc == CPUI_INT_SEXT) || (opc == CPUI_PTRADD)) {
      int4 maxparam = 2;
      if (op->numInput() < maxparam)
	maxparam = op->numInput();
      Varnode *topvn = (Varnode *)0;
      for(int4 j=0;j<maxparam;++j) {
	topvn = op->getIn(j);
	if (topvn->isMark()) {	// We have a "multiple" interaction between -topvn- and -vn-
	  OpCode topopc = CPUI_COPY;
	  if (topvn->isWritten()) {
	    if (topvn->getDef()->isBoolOutput())
	      continue;		// Try not to make boolean outputs explicit
	    topopc = topvn->getDef()->code();
	  }
	  if (opc == CPUI_PTRADD) {
	    if (topopc == CPUI_PTRADD)
	      purgelist.push_back(topvn);
	  }
	  else
	    purgelist.push_back(topvn);
	}
      }
    }
  }

  for(int4 i=0;i<purgelist.size();++i) {
    Varnode *vn = purgelist[i];
    vn->setExplicit();
    vn->clearImplied();
    vn->clearMark();
  }
  return purgelist.size();
}

/// Record the Varnode just encountered and set-up the next (backward) edges to traverse.
/// \param v is the Varnode just encountered
ActionMarkExplicit::OpStackElement::OpStackElement(Varnode *v)

{
  vn = v;
  slot = 0;
  slotback = 0;
  if (v->isWritten()) {
    OpCode opc = v->getDef()->code();
    if (opc == CPUI_LOAD) {
      slot = 1;
      slotback = 2;
    }
    else if (opc == CPUI_PTRADD)
      slotback = 1;			// Don't traverse the multiplier slot
    else if (opc == CPUI_SEGMENTOP) {
      slot = 2;
      slotback = 3;
    }
    else
      slotback = v->getDef()->numInput();
  }
}

/// Count the number of terms in the expression making up \b vn. If
/// there are more than \b max terms, mark \b vn as \e explicit.
/// The given Varnode is already assumed to have multiple descendants.
/// We do a depth first traversal along op inputs, to recursively
/// calculate the number of explicit terms in an expression.
/// \param vn is the given Varnode
/// \param max is the maximum number of terms to allow
void ActionMarkExplicit::processMultiplier(Varnode *vn,int4 max)

{
  vector<OpStackElement> opstack;
  Varnode *vncur;
  int4 finalcount = 0;

  opstack.push_back(vn);
  do {
    vncur = opstack.back().vn;
    bool isaterm = vncur->isExplicit() || (!vncur->isWritten());
    if (isaterm || (opstack.back().slotback<=opstack.back().slot)) { // Trimming condition
      if (isaterm) {
	if (!vncur->isSpacebase()) // Don't count space base
	  finalcount += 1;
      }
      if (finalcount > max) {
	vn->setExplicit();	// Make this variable explicit
	vn->clearImplied();
	return;
      }
      opstack.pop_back();
    }
    else {
      PcodeOp *op = vncur->getDef();
      Varnode *newvn = op->getIn(opstack.back().slot++);
      if (newvn->isMark()) {	// If an ancestor is marked(also possible implied with multiple descendants)
	vn->setExplicit();	// then automatically consider this to be explicit
	vn->clearImplied();
      }
      opstack.push_back(newvn);
    }
  } while(!opstack.empty());
}

/// Assume \b vn is produced via a CPUI_NEW operation. If it is immediately fed to a constructor,
/// set special printing flags on the Varnode.
/// \param data is the function being analyzed
/// \param vn is the given Varnode
void ActionMarkExplicit::checkNewToConstructor(Funcdata &data,Varnode *vn)

{  PcodeOp *op = vn->getDef();
  BlockBasic *bb = op->getParent();
  PcodeOp *firstuse = (PcodeOp *)0;
  list<PcodeOp *>::const_iterator iter;
  for(iter=vn->beginDescend();iter!=vn->endDescend();++iter) {
    PcodeOp *curop = *iter;
    if (curop->getParent() != bb) continue;
    if (firstuse == (PcodeOp *)0)
      firstuse = curop;
    else if (curop->getSeqNum().getOrder() < firstuse->getSeqNum().getOrder())
      firstuse = curop;
    else if (curop->code() == CPUI_CALLIND) {
      Varnode *ptr = curop->getIn(0);
      if (ptr->isWritten()) {
	if (ptr->getDef() == firstuse)
	  firstuse = curop;
      }
    }
  }
  if (firstuse == (PcodeOp *)0) return;

  if (!firstuse->isCall()) return;
  if (firstuse->getOut() != (Varnode *)0) return;
  if (firstuse->numInput() < 2) return;		// Must have at least 1 parameter (plus destination varnode)
  if (firstuse->getIn(1) != vn) return;		// First parameter must result of new
//  if (!fc->isConstructor()) return;		// Function must be a constructor
  data.opMarkSpecialPrint(firstuse);		// Mark call to print the new operator as well
  data.opMarkNonPrinting(op);			// Don't print the new operator as stand-alone operation
}

int4 ActionMarkExplicit::apply(Funcdata &data)

{
  VarnodeDefSet::const_iterator viter,enditer;
  vector<Varnode *> multlist;		// implied varnodes with >1 descendants
  int4 maxref;

  maxref = data.getArch()->max_implied_ref;
  enditer = data.beginDef(0); // Cut out free varnodes
  for(viter=data.beginDef();viter!=enditer;++viter) {
    Varnode *vn = *viter;

    int4 desccount = baseExplicit(vn,maxref);
    if (desccount < 0) {
      vn->setExplicit();
      count += 1;
      if (desccount < -1)
	checkNewToConstructor(data,vn);
    }
    else if (desccount > 1) {	// Keep track of possible implieds with more than one descendant
      vn->setMark();
      multlist.push_back(vn);
    }
  }

  count += multipleInteraction(multlist);
  int4 maxdup = data.getArch()->max_term_duplication;
  for(int4 i=0;i<multlist.size();++i) {
    Varnode *vn = multlist[i];
    if (vn->isMark())		// Mark may have been cleared by multipleInteraction
      processMultiplier(vn,maxdup);
  }
  for(int4 i=0;i<multlist.size();++i)
    multlist[i]->clearMark();
  return 0;
}

/// Return false only if one Varnode is obtained by adding non-zero thing to another Varnode.
/// The order of the Varnodes is not important.
/// \param vn1 is the first Varnode
/// \param vn2 is the second Varnode
/// \return false if the additive relationship holds
bool ActionMarkImplied::isPossibleAliasStep(Varnode *vn1,Varnode *vn2)

{
  Varnode *var[2];
  var[0] = vn1;
  var[1] = vn2;
  for(int4 i=0;i<2;++i) {
    Varnode *vncur = var[i];
    if (!vncur->isWritten()) continue;
    PcodeOp *op = vncur->getDef();
    OpCode opc = op->code();
    if ((opc!=CPUI_INT_ADD)&&(opc!=CPUI_PTRSUB)&&(opc!=CPUI_PTRADD)&&(opc!=CPUI_INT_XOR)) continue;
    if (var[1-i] != op->getIn(0)) continue;
    if (op->getIn(1)->isConstant()) return false;
  }
  return true;
}


/// Return false \b only if we can guarantee two Varnodes have different values.
/// \param vn1 is the first Varnode
/// \param vn2 is the second Varnode
/// \param depth is the maximum level to recurse
/// \return true if its possible the Varnodes hold the same value
bool ActionMarkImplied::isPossibleAlias(Varnode *vn1,Varnode *vn2,int4 depth)

{
  if (vn1 == vn2) return true;	// Definite alias
  if ((!vn1->isWritten())||(!vn2->isWritten())) {
    if (vn1->isConstant() && vn2->isConstant())
      return (vn1->getOffset()==vn2->getOffset()); // FIXME: these could be NEAR each other and still have an alias
    return isPossibleAliasStep(vn1,vn2);
  }

  if (!isPossibleAliasStep(vn1,vn2))
    return false;
  Varnode *cvn1,*cvn2;
  PcodeOp *op1 = vn1->getDef();
  PcodeOp *op2 = vn2->getDef();
  OpCode opc1 = op1->code();
  OpCode opc2 = op2->code();
  int4 mult1 = 1;
  int4 mult2 = 1;
  if (opc1 == CPUI_PTRSUB)
    opc1 = CPUI_INT_ADD;
  else if (opc1 == CPUI_PTRADD) {
    opc1 = CPUI_INT_ADD;
    mult1 = (int4) op1->getIn(2)->getOffset();
  }
  if (opc2 == CPUI_PTRSUB)
    opc2 = CPUI_INT_ADD;
  else if (opc2 == CPUI_PTRADD) {
    opc2 = CPUI_INT_ADD;
    mult2 = (int4) op2->getIn(2)->getOffset();
  }
  if (opc1 != opc2) return true;
  if (depth == 0) return true;	// Couldn't find absolute difference
  depth -= 1;
  switch(opc1) {
  case CPUI_COPY:
  case CPUI_INT_ZEXT:
  case CPUI_INT_SEXT:
  case CPUI_INT_2COMP:
  case CPUI_INT_NEGATE:
    return isPossibleAlias(op1->getIn(0),op2->getIn(0),depth);
  case CPUI_INT_ADD:
    cvn1 = op1->getIn(1);
    cvn2 = op2->getIn(1);
    if (cvn1->isConstant() && cvn2->isConstant()) {
      uintb val1 = mult1 * cvn1->getOffset();
      uintb val2 = mult2 * cvn2->getOffset();
      if (val1 == val2)
	return isPossibleAlias(op1->getIn(0),op2->getIn(0),depth);
      return !functionalEquality(op1->getIn(0),op2->getIn(0));
    }
    if (mult1 != mult2) return true;
    if (functionalEquality(op1->getIn(0),op2->getIn(0)))
      return isPossibleAlias(op1->getIn(1),op2->getIn(1),depth);
    if (functionalEquality(op1->getIn(1),op2->getIn(1)))
      return isPossibleAlias(op1->getIn(0),op2->getIn(0),depth);
    if (functionalEquality(op1->getIn(0),op2->getIn(1)))
      return isPossibleAlias(op1->getIn(1),op2->getIn(0),depth);
    if (functionalEquality(op1->getIn(1),op2->getIn(0)))
      return isPossibleAlias(op1->getIn(0),op2->getIn(1),depth);
    break;
  default:
    break;
  }
  return true;
}

/// Marking a Varnode as \e implied causes the input Varnodes to its defining op to propagate farther
/// in the output.  This may cause eventual variables to hold different values at the same
/// point in the code. Any input must test that its propagated Cover doesn't intersect its current Cover.
/// \param data is the function being analyzed
/// \param vn is the given Varnode
/// \return \b true if there is a Cover violation
bool ActionMarkImplied::checkImpliedCover(Funcdata &data,Varnode *vn)

{
  PcodeOp *op,*storeop,*callop;
  Varnode *defvn;
  int4 i;

  op = vn->getDef();
  if (op->code() == CPUI_LOAD) { // Check for loads crossing stores
    list<PcodeOp *>::const_iterator oiter,iterend;
    iterend = data.endOp(CPUI_STORE);
    for(oiter=data.beginOp(CPUI_STORE);oiter!=iterend;++oiter) {
      storeop = *oiter;
      if (storeop->isDead()) continue;
      if (vn->getCover()->contain(storeop,2)) {
				// The LOAD crosses a STORE. We are cavalier
				// and let it through unless we can verify
				// that the pointers are actually the same
	if (storeop->getIn(0)->getOffset() == op->getIn(0)->getOffset()) {
	  //	  if (!functionalDifference(storeop->getIn(1),op->getIn(1),2)) return false;
	  if (isPossibleAlias(storeop->getIn(1),op->getIn(1),2)) return false;
	}
      }
    }
  }
  if (op->isCall() || (op->code() == CPUI_LOAD)) { // loads crossing calls
    for(i=0;i<data.numCalls();++i) {
      callop = data.getCallSpecs(i)->getOp();
      if (vn->getCover()->contain(callop,2)) return false;
    }
  }
  for(i=0;i<op->numInput();++i) {
    defvn = op->getIn(i);
    if (defvn->isConstant()) continue;
    if (data.getMerge().inflateTest(defvn,vn->getHigh()))	// Test for intersection
      return false;
  }
  return true;
}

int4 ActionMarkImplied::apply(Funcdata &data)

{
  VarnodeLocSet::const_iterator viter;
  list<PcodeOp *>::const_iterator oiter;
  Varnode *vn,*vncur,*outvn;
  vector<DescTreeElement> varstack; // Depth first varnode traversal stack

  for(viter=data.beginLoc();viter!=data.endLoc();++viter) {
    vn = *viter;
    if (vn->isFree()) continue;
    if (vn->isExplicit()) continue;
    if (vn->isImplied()) continue;
    varstack.push_back(vn);
    do {
      vncur = varstack.back().vn;
      if (varstack.back().desciter == vncur->endDescend()) {
	// All descendants are traced first, try to make vncur implied
	count += 1;		// Will be marked either explicit or implied
	if (!checkImpliedCover(data,vncur)) // Can this variable be implied
	  vncur->setExplicit();	// if not, mark explicit
	else {
	  Merge::markImplied(vncur);
	  // setting the implied type is now taken care of by ActionSetCasts
	  //    vn->updatetype(op->outputtype_token(),false,false); // implied must have parsed type
	}
	varstack.pop_back();
      }
      else {
	outvn = (*varstack.back().desciter++)->getOut();
	if (outvn != (Varnode *)0) {
	  if ((!outvn->isExplicit())&&(!outvn->isImplied()))
	    varstack.push_back(outvn);
	}
      }
    } while(!varstack.empty());
  }

  return 0;
}

int4 ActionUnreachable::apply(Funcdata &data)

{				// Detect unreachable blocks and remove
  if (data.removeUnreachableBlocks(true,false))
    count += 1;			// Deleting at least one block

  return 0;
}

int4 ActionDoNothing::apply(Funcdata &data)

{				// Remove blocks that do nothing
  const BlockGraph &graph(data.getBasicBlocks());

  for(int4 i=0;i<graph.getSize();++i) {
    BlockBasic *bb = (BlockBasic *) graph.getBlock(i);
    bb->clearDelayedDonothing();
    if (bb->isDoNothing()) {
      if ((bb->sizeOut()==1)&&(bb->getOut(0)==bb)) { // Infinite loop
	if (!bb->isDonothingLoop()) {
	  bb->setDonothingLoop();
	  data.warning("Do nothing block with infinite loop",bb->getStart());
	}
      }
      else if (bb->unblockedMulti(0)) {
	if (data.isNormalizationOn() || data.isJumptableRecoveryOn() || bb->hasNoImmediateCopy(0)) {
	  data.removeDoNothingBlock(bb);
	  count += 1;
	  return 0;
	}
	else {
	  // If there were immediate COPYs but the block was otherwise removable,
	  // mark the block for possible late removal.
	  bb->setDelayedDonothing();
	}
      }
    }
  }
  return 0;
}

/// For each input to \b bl, check if all other out edges go to the same \e out block as \b bl.
/// \param bl is the block being removed
/// \return \b true if a redundancy would be created
bool ActionLateDoNothing::removingCreatesRedundancy(FlowBlock *bl)

{
  FlowBlock *outbl = bl->getOut(0);
  for(int4 i=0;i<bl->sizeIn();++i) {
    FlowBlock *inbl = bl->getIn(i);
    if (inbl->sizeOut() == 1) continue;
    int4 count;
    for(count=0;count<inbl->sizeOut();++count) {
      FlowBlock *curbl = inbl->getOut(count);
      if (curbl != bl && curbl != outbl)		// Check if this edge goes to outbl (possibly via bl)
	break;
    }
    if (count == inbl->sizeOut())			// All edges lead to outbl
      return true;
  }
  return false;
}

int4 ActionLateDoNothing::apply(Funcdata &data)

{
  const BlockGraph &graph(data.getBasicBlocks());
  vector<BlockBasic *> removeList;

  for(int4 i=0;i<graph.getSize();++i) {
    BlockBasic *bb = (BlockBasic *) graph.getBlock(i);
    if (!bb->isDelayedDonothing()) continue;
    if (bb->isDoNothing()) {
      if (removingCreatesRedundancy(bb)) continue;
      if ((bb->sizeOut() == 1) && (bb->getOut(0) == bb)) { // Infinite loop
	if (!bb->isDonothingLoop()) {
	  bb->setDonothingLoop();
	  data.warning("Do nothing block with infinite loop",bb->getStart());
	}
      }
      else if (bb->unblockedMulti(0)) removeList.push_back(bb);
    }
  }
  for(int4 i=0;i<removeList.size();++i) {
    data.removeDoNothingBlock(removeList[i]);
    count += 1;
  }
  return 0;
}

int4 ActionRedundBranch::apply(Funcdata &data)

{
  // Remove redundant branches, i.e. a CPUI_CBRANCH that falls thru and branches to the same place
  int4 i,j;
  const BlockGraph &graph(data.getBasicBlocks());
  BlockBasic *bb;
  FlowBlock *bl;

  for(i=0;i<graph.getSize();++i) {
    bb = (BlockBasic *) graph.getBlock(i);
    if (bb->sizeOut() == 0) continue;
    bl = bb->getOut(0);
    if (bb->sizeOut() == 1) {
      if ((bl->sizeIn() == 1)&&(!bl->isEntryPoint())&&(!bb->isSwitchOut())) {
	// Do not splice block coming from single exit switch as this prevents possible second stage recovery
	data.spliceBlockBasic(bb);
	count += 1;
	// This will remove one block, so reset i
	i = -1;
      }
      continue;
    }
    for(j=1;j<bb->sizeOut();++j) // Are all exits to the same block? (bl)
      if (bb->getOut(j) != bl) break;
    if (j!=bb->sizeOut()) continue;

    //    ostringstream s;
    //    s << "Removing redundant branch out of block ";
    //    s << "code_" << bb->start.Target().getShortcut();
    //    bb->start.Target().printRaw(s);
    //    data.warningHeader(s.str());
    data.removeBranch(bb,1);	// Remove the branch instruction
    count += 1;
  }
  return 0;			// Indicate full rule was applied
}

int4 ActionDeterminedBranch::apply(Funcdata &data)

{
  int4 i;
  const BlockGraph &graph(data.getBasicBlocks());
  BlockBasic *bb;
  PcodeOp *cbranch;

  for(i=0;i<graph.getSize();++i) {
    bb = (BlockBasic *) graph.getBlock(i);
    cbranch = bb->lastOp();
    if ((cbranch == (PcodeOp *)0)||(cbranch->code() != CPUI_CBRANCH)) continue;
    if (!cbranch->getIn(1)->isConstant()) continue;
    uintb val = cbranch->getIn(1)->getOffset();
    int4 num = ((val!=0)!=cbranch->isBooleanFlip()) ? 0 : 1;
    data.removeBranch(bb,num);
    count += 1;
  }
  return 0;
}

/// Given a new \e consume value to push to a Varnode, determine if this changes
/// the Varnodes consume value and whether to push the Varnode onto the work-list.
/// \param val is the new consume value
/// \param vn is the Varnode to push to
/// \param worklist is the current work-list
inline void ActionDeadCode::pushConsumed(uintb val,Varnode *vn,vector<Varnode *> &worklist)

{
  uintb newval = (val | vn->getConsume())&calc_mask(vn->getSize());
  if ((newval == vn->getConsume())&&vn->isConsumeVacuous()) return;
  vn->setConsumeVacuous();
  if (!vn->isConsumeList()) { // Check if already in list
    vn->setConsumeList();	// Mark as in the list
    if (vn->isWritten())
      worklist.push_back(vn);	// add to list
  }
  vn->setConsume(newval);
}

/// \brief Propagate the \e consumed value for one Varnode
///
/// The Varnode at the top of the stack is popped off, and its current
/// \e consumed value is propagated  backward to the inputs of the op
/// that produced it.
/// \param worklist is the current stack of dirty Varnodes
void ActionDeadCode::propagateConsumed(vector<Varnode *> &worklist)

{
  Varnode *vn = worklist.back();
  worklist.pop_back();
  uintb outc = vn->getConsume();
  vn->clearConsumeList();

  PcodeOp *op = vn->getDef();	// Assume vn is written

  int4 sz;
  uintb a,b;

  switch(op->code()) {
  case CPUI_INT_MULT:
    b = coveringmask(outc);
    if (op->getIn(1)->isConstant()) {
      int4 leastSet = leastsigbit_set(op->getIn(1)->getOffset());
      if (leastSet >= 0) {
	a = calc_mask(vn->getSize()) >> leastSet;
	a &= b;
      }
      else
	a = 0;
    }
    else
      a = b;
    pushConsumed(a,op->getIn(0),worklist);
    pushConsumed(b,op->getIn(1),worklist);
    break;
  case CPUI_INT_ADD:
  case CPUI_INT_SUB:
    a = coveringmask(outc);	// Make sure value is filled out as a contiguous mask
    pushConsumed(a,op->getIn(0),worklist);
    pushConsumed(a,op->getIn(1),worklist);
    break;
  case CPUI_SUBPIECE:
    sz = op->getIn(1)->getOffset();
    if (sz >= sizeof(uintb))	// If we are truncating beyond the precision of the consume field
      a = 0;			// this tells us nothing about consuming bits within the field
    else
      a = outc << (sz*8);
    if ((a==0)&&(outc!=0)&&(op->getIn(0)->getSize() > sizeof(uintb))) {
      // If the consumed mask is zero because
      // it isn't big enough to cover the whole varnode and
      // there are still upper bits that are consumed
      a = ~((uintb)0);
      a = a ^ (a >> 1);		// Set the highest bit possible in the mask to indicate some consumption
    }
    b = (outc == 0) ? 0 : ~((uintb)0);
    pushConsumed(a,op->getIn(0),worklist);
    pushConsumed(b,op->getIn(1),worklist);
    break;
  case CPUI_PIECE:
    sz = op->getIn(1)->getSize();
    if (vn->getSize() > sizeof(uintb)) { // If the concatenation goes beyond the consume precision
      if (sz >= sizeof(uintb)) {
	a = ~((uintb)0);	// Assume the bits not in the consume field are consumed
	b = outc;
      }
      else {
	a = (outc >> (sz*8)) ^ ( (~((uintb)0)) << 8*(sizeof(uintb)-sz));
	b = outc ^ (a << (sz*8));
      }
    }
    else {
      a = outc >> (sz*8);
      b = outc ^ (a << (sz*8));
    }
    pushConsumed(a,op->getIn(0),worklist);
    pushConsumed(b,op->getIn(1),worklist);
    break;
  case CPUI_INDIRECT:
    pushConsumed(outc,op->getIn(0),worklist);
    if (op->getIn(1)->getSpace()->getType()==IPTR_IOP) {
      PcodeOp *indop = PcodeOp::getOpFromConst(op->getIn(1)->getAddr());
      if (indop->isDead()) {
	ostringstream s;
	s << "Hanging INDIRECT at " << op->getAddr();
	throw LowlevelError(s.str());
      }
      if (indop->code() == CPUI_COPY) {
	if (indop->getOut()->characterizeOverlap(*op->getOut())>0) {
	  pushConsumed(~((uintb)0),indop->getOut(),worklist);	// Mark the copy as consumed
	  indop->setIndirectSource();
	}
      }
      else
	indop->setIndirectSource();
    }
    break;
  case CPUI_COPY:
  case CPUI_INT_NEGATE:
    pushConsumed(outc,op->getIn(0),worklist);
    break;
  case CPUI_INT_XOR:
  case CPUI_INT_OR:
    pushConsumed(outc,op->getIn(0),worklist);
    pushConsumed(outc,op->getIn(1),worklist);
    break;
  case CPUI_INT_AND:
    if (op->getIn(1)->isConstant()) {
      uintb val = op->getIn(1)->getOffset();
      pushConsumed(outc&val,op->getIn(0),worklist);
      pushConsumed(outc,op->getIn(1),worklist);
    }
    else {
      pushConsumed(outc,op->getIn(0),worklist);
      pushConsumed(outc,op->getIn(1),worklist);
    }
    break;
  case CPUI_MULTIEQUAL:
    for(int4 i=0;i<op->numInput();++i)
      pushConsumed(outc,op->getIn(i),worklist);
    break;
  case CPUI_INT_ZEXT:
    pushConsumed(outc,op->getIn(0),worklist);
    break;
  case CPUI_INT_SEXT:
    b = calc_mask(op->getIn(0)->getSize());
    a = outc & b;
    if (outc > b)
      a |= (b ^ (b>>1));	// Make sure signbit is marked used
    pushConsumed(a,op->getIn(0),worklist);
    break;
  case CPUI_INT_LEFT:
    if (op->getIn(1)->isConstant()) {
      sz = vn->getSize();
      int4 sa = op->getIn(1)->getOffset();
      if (sz > sizeof(uintb)) {	// If there exists bits beyond the precision of the consume field
	if (sa >= 8*sizeof(uintb))
	  a = ~((uintb)0);	// Make sure we assume one bits where we shift in unrepresented bits
	else if (sa == 0) {
	  a = outc;
	}
	else
	  a = (outc >> sa) ^ ( (~((uintb)0)) << (8*sizeof(uintb)-sa));
	sz = 8*sz -sa;
	if (sz < 8*sizeof(uintb)) {
	  uintb mask = ~((uintb)0);
	  mask <<= sz;
	  a = a & ~mask;	// Make sure high bits that are left shifted out are not marked consumed
	}
      }
      else
	a = outc >> sa;		// Most cases just do this
      b = (outc == 0) ? 0 : ~((uintb)0);
      pushConsumed(a,op->getIn(0),worklist);
      pushConsumed(b,op->getIn(1),worklist);
    }
    else {
      a = (outc==0) ? 0 : ~((uintb)0);
      pushConsumed(a,op->getIn(0),worklist);
      pushConsumed(a,op->getIn(1),worklist);
    }
    break;
  case CPUI_INT_RIGHT:
    if (op->getIn(1)->isConstant()) {
      int4 sa = op->getIn(1)->getOffset();
      if (sa >= 8*sizeof(uintb)) // If the shift is beyond the precision of the consume field
	a = 0;			// We know nothing about the low order consumption of the input bits
      else
	a = outc << sa;		// Most cases just do this
      if ((a==0)&&(outc!=0)&&(op->getIn(0)->getSize() > sizeof(uintb))) {
	// The consumed bits were shifted beyond the precision of the consume field,
	// but bits of the input above the field are still consumed
	a = ~((uintb)0);
	a = a ^ (a >> 1);	// Set the highest bit possible in the mask to indicate some consumption
      }
      b = (outc == 0) ? 0 : ~((uintb)0);
      pushConsumed(a,op->getIn(0),worklist);
      pushConsumed(b,op->getIn(1),worklist);
    }
    else {
      a = (outc==0) ? 0 : ~((uintb)0);
      pushConsumed(a,op->getIn(0),worklist);
      pushConsumed(a,op->getIn(1),worklist);
    }
    break;
  case CPUI_INT_LESS:
  case CPUI_INT_LESSEQUAL:
  case CPUI_INT_EQUAL:
  case CPUI_INT_NOTEQUAL:
    if (outc==0)
      a = 0;
    else			// Anywhere we know is zero, is not getting "consumed"
      a = op->getIn(0)->getNZMask() | op->getIn(1)->getNZMask();
    pushConsumed(a,op->getIn(0),worklist);
    pushConsumed(a,op->getIn(1),worklist);
    break;
  case CPUI_INSERT:
    a = 1;
    a <<= (int4)op->getIn(3)->getOffset();
    a -= 1;	// Insert mask
    pushConsumed(a,op->getIn(1),worklist);
    a <<= (int4)op->getIn(2)->getOffset();
    pushConsumed(outc & ~a, op->getIn(0), worklist);
    b = (outc == 0) ? 0 : ~((uintb)0);
    pushConsumed(b,op->getIn(2), worklist);
    pushConsumed(b,op->getIn(3), worklist);
    break;
  case CPUI_ZPULL:
  case CPUI_SPULL:
    a = 1;
    a <<= (int4)op->getIn(2)->getOffset();
    a -= 1;	// Pull mask
    a &= outc;	// Consumed bits of mask
    a <<= (int4)op->getIn(1)->getOffset();
    pushConsumed(a,op->getIn(0),worklist);
    b = (outc == 0) ? 0 : ~((uintb)0);
    pushConsumed(b,op->getIn(1), worklist);
    pushConsumed(b,op->getIn(2), worklist);
    break;
  case CPUI_POPCOUNT:
  case CPUI_LZCOUNT:
    a = 16 * op->getIn(0)->getSize() - 1;	// Mask for possible bits that could be set
    a &= outc;					// Of the bits that could be set, which are consumed
    b = (a == 0) ? 0 : ~((uintb)0);		// if any consumed, treat all input bits as consumed
    pushConsumed(b,op->getIn(0), worklist);
    break;
  case CPUI_CALL:
  case CPUI_CALLIND:
    break;		// Call output doesn't indicate consumption of inputs
  case CPUI_FLOAT_INT2FLOAT:
    a = 0;
    if (outc != 0)
      a = coveringmask(op->getIn(0)->getNZMask());
    pushConsumed(a,op->getIn(0), worklist);
    break;
  default:
    a = (outc==0) ? 0 : ~((uintb)0); // all or nothing
    for(int4 i=0;i<op->numInput();++i)
      pushConsumed(a,op->getIn(i),worklist);
    break;
  }

}

/// \brief Deal with unconsumed Varnodes
///
/// For a Varnode, none of whose bits are consumed, eliminate the PcodeOp defining it
/// and replace Varnode inputs to ops that officially read it with zero constants.
/// \param vn is the Varnode
/// \param data is the function being analyzed
/// \return true if the Varnode was eliminated
bool ActionDeadCode::neverConsumed(Varnode *vn,Funcdata &data)

{
  if (vn->getSize() > sizeof(uintb)) return false; // Not enough precision to really tell
  list<PcodeOp *>::const_iterator iter;
  PcodeOp *op;
  iter = vn->beginDescend();
  while(iter != vn->endDescend()) {
    op = *iter++;		// Advance before ref is removed
    int4 slot = op->getSlot(vn);
    // Replace vn with 0 whereever it is read
    // We don't worry about putting a constant in a marker
    // because if vn is not consumed and is input to a marker
    // then the output is also not consumed and the marker
    // op is about to be deleted anyway
    data.opSetInput(op,data.newConstant(vn->getSize(),0),slot);
  }
  op = vn->getDef();
  if (op->isCall())
    data.opUnsetOutput(op); // For calls just get rid of output
  else
    data.opDestroy(op);	// Otherwise completely remove the op
  return true;
}

/// \brief Determine how the given sub-function parameters are consumed
///
/// Set the consume property for each input Varnode of a CPUI_CALL or CPUI_CALLIND.
/// If the prototype is locked, assume parameters are entirely consumed.
/// \param fc is the call specification for the given sub-function
/// \param worklist will hold input Varnodes that can propagate their consume property
void ActionDeadCode::markConsumedParameters(FuncCallSpecs *fc,vector<Varnode *> &worklist)

{
  PcodeOp *callOp = fc->getOp();
  pushConsumed(~((uintb)0),callOp->getIn(0),worklist);		// In all cases the first operand is fully consumed
  if (fc->isInputLocked() || fc->isInputActive()) {		// If the prototype is locked in, or in active recovery
    for(int4 i=1;i<callOp->numInput();++i)
      pushConsumed(~((uintb)0),callOp->getIn(i),worklist);	// Treat all parameters as fully consumed
    return;
  }
  for(int4 i=1;i<callOp->numInput();++i) {
    Varnode *vn = callOp->getIn(i);
    uintb consumeVal;
    if (vn->isAutoLive())
      consumeVal = ~((uintb)0);
    else
      consumeVal = minimalmask(vn->getNZMask());
    int4 bytesConsumed = fc->getInputBytesConsumed(i);
    if (bytesConsumed != 0)
      consumeVal &= calc_mask(bytesConsumed);
    pushConsumed(consumeVal,vn,worklist);
  }
}

/// \brief Determine how the \e return \e values for the given function are consumed
///
/// Examine each CPUI_RETURN to see how the Varnode input is consumed.
/// If the function's prototype is locked, assume the Varnode is entirely consumed.
/// If there are no CPUI_RETURN ops, return 0
/// \param data is the given function
/// \return the bit mask of what is consumed
uintb ActionDeadCode::gatherConsumedReturn(Funcdata &data)

{
  if (data.getFuncProto().isOutputLocked() || data.getActiveOutput() != (ParamActive *)0)
    return ~((uintb)0);
  list<PcodeOp *>::const_iterator iter,enditer;
  enditer = data.endOp(CPUI_RETURN);
  uintb consumeVal = 0;
  for(iter=data.beginOp(CPUI_RETURN);iter!=enditer;++iter) {
    PcodeOp *returnOp = *iter;
    if (returnOp->isDead()) continue;
    if (returnOp->numInput() > 1) {
      Varnode *vn = returnOp->getIn(1);
      consumeVal |= minimalmask(vn->getNZMask());
    }
  }
  int4 val = data.getFuncProto().getReturnBytesConsumed();
  if (val != 0) {
    consumeVal &= calc_mask(val);
  }
  return consumeVal;
}

/// \brief Check if there are any unconsumed LOADs that may be from volatile addresses.
///
/// It may be too early to remove certain LOAD operations even though their result isn't
/// consumed because it may be of a volatile address with side effects.  If a LOAD meets this
/// criteria, it is added to the worklist and \b true is returned.
/// \param data is the function being analyzed
/// \param worklist is the container of consumed Varnodes to further process
/// \return \b true if there was at least one LOAD added to the worklist
bool ActionDeadCode::lastChanceLoad(Funcdata &data,vector<Varnode *> &worklist)

{
  if (data.getHeritagePass() > 1) return false;
  if (data.isJumptableRecoveryOn()) return false;
  list<PcodeOp *>::const_iterator iter = data.beginOp(CPUI_LOAD);
  list<PcodeOp *>::const_iterator enditer = data.endOp(CPUI_LOAD);
  bool res = false;
  while(iter != enditer) {
    PcodeOp *op = *iter;
    ++iter;
    if (op->isDead()) continue;
    Varnode *vn = op->getOut();
    if (vn->isConsumeVacuous()) continue;
    if (op->getIn(1)->isEventualConstant(3, 1)) {
      pushConsumed(~(uintb)0, vn, worklist);
      vn->setAutoLiveHold();
      res = true;
    }
  }
  return res;
}

int4 ActionDeadCode::apply(Funcdata &data)

{
  int4 i;
  list<PcodeOp *>::const_iterator iter;
  PcodeOp *op;
  Varnode *vn;
  uintb returnConsume;
  vector<Varnode *> worklist;
  VarnodeLocSet::const_iterator viter,endviter;
  const AddrSpaceManager *manage = data.getArch();
  AddrSpace *spc;

				// Clear consume flags
  for(viter=data.beginLoc();viter!=data.endLoc();++viter) {
    vn = *viter;
    vn->clearConsumeList();
    vn->clearConsumeVacuous();
    vn->setConsume(0);
    if (vn->isAddrForce()&&(!vn->isDirectWrite()))
      vn->clearAddrForce();
  }

				// Set pre-live registers
  for(i=0;i<manage->numSpaces();++i) {
    spc = manage->getSpace(i);
    if (spc == (AddrSpace *)0 || !spc->doesDeadcode()) continue;
    if (data.deadRemovalAllowed(spc)) continue; // Mark consumed if we have NOT heritaged
    viter = data.beginLoc(spc);
    endviter = data.endLoc(spc);
    while(viter != endviter) {
      vn = *viter++;
      pushConsumed(~((uintb)0),vn,worklist);
    }
  }

  returnConsume = gatherConsumedReturn(data);
  for(iter=data.beginOpAlive();iter!=data.endOpAlive();++iter) {
    op = *iter;

    op->clearIndirectSource();
    if (op->isCall()) {
      // Postpone setting consumption on CALL and CALLIND inputs
      if (op->isCallWithoutSpec()) {
	for(i=0;i<op->numInput();++i)
	  pushConsumed(~((uintb)0),op->getIn(i),worklist);
      }
      if (!op->isAssignment())
	continue;
      if (op->holdOutput())
	pushConsumed(~((uintb)0),op->getOut(),worklist);
    }
    else if (!op->isAssignment()) {
      OpCode opc = op->code();
      if (opc == CPUI_RETURN) {
	pushConsumed(~((uintb)0),op->getIn(0),worklist);
	for(i=1;i<op->numInput();++i)
	  pushConsumed(returnConsume,op->getIn(i),worklist);
      }
      else if (opc == CPUI_BRANCHIND) {
	JumpTable *jt = data.findJumpTable(op);
	uintb mask;
	if (jt != (JumpTable *)0)
	  mask = jt->getSwitchVarConsume();
	else
	  mask = ~((uintb)0);
	pushConsumed(mask,op->getIn(0),worklist);
      }
      else {
	for(i=0;i<op->numInput();++i)
	  pushConsumed(~((uintb)0),op->getIn(i),worklist);
      }
      // Postpone setting consumption on RETURN input
      continue;
    }
    else {
      for(i=0;i<op->numInput();++i) {
	vn = op->getIn(i);
	if (vn->isAutoLive())
	  pushConsumed(~((uintb)0),vn,worklist);
      }
    }
    vn = op->getOut();
    if (vn->isAutoLive())
      pushConsumed(~((uintb)0),vn,worklist);
  }

				// Mark consumption of call parameters
  for(i=0;i<data.numCalls();++i)
    markConsumedParameters(data.getCallSpecs(i),worklist);

				// Propagate the consume flags
  while(!worklist.empty())
    propagateConsumed(worklist);

  if (lastChanceLoad(data, worklist)) {
    while(!worklist.empty())
      propagateConsumed(worklist);
  }

  for(i=0;i<manage->numSpaces();++i) {
    spc = manage->getSpace(i);
    if (spc == (AddrSpace *)0 || !spc->doesDeadcode()) continue;
    if (!data.deadRemovalAllowed(spc)) continue; // Don't eliminate if we haven't heritaged
    viter = data.beginLoc(spc);
    endviter = data.endLoc(spc);
    int4 changecount = 0;
    while(viter != endviter) {
      vn = *viter++;		// Advance iterator BEFORE (possibly) deleting varnode
      if (!vn->isWritten()) continue;
      bool vacflag = vn->isConsumeVacuous();
      vn->clearConsumeList();
      vn->clearConsumeVacuous();
      if (!vacflag) {		// Not even vacuously consumed
	op = vn->getDef();
	changecount += 1;
	if (op->isCall())
	  data.opUnsetOutput(op); // For calls just get rid of output
	else
	  data.opDestroy(op);	// Otherwise completely remove the op
      }
      else {
	// Check for values that are never used, but bang around
	// for a while
	if (vn->getConsume()==0) {
	  if (neverConsumed(vn,data))
	    changecount += 1;
	}
      }
    }
    if (changecount != 0)
      data.seenDeadcode(spc);	// Record that we have seen dead code for this space
  }
#ifdef OPACTION_DEBUG
  data.debugModPrint(getName()); // Print dead ops before freeing them
#endif
  data.clearDeadVarnodes();
  data.clearDeadOps();
  return 0;
}

/// \brief Clear all marks on the given list of PcodeOps
///
/// \param opList is the given list
void ActionConditionalConst::clearMarks(const vector<PcodeOp *> &opList)

{
  for(int4 i=0;i<opList.size();++i)
    opList[i]->clearMark();
}

/// \brief Collect COPY, INDIRECT, and MULTIEQUAL ops reachable from the given Varnode, without going thru excised edges
///
/// If data-flow from the Varnode does not go through excised edges and reaches the op via other MULTIEQUALs,
/// INDIRECTs, and COPYs, the op is put in a list, and its mark is set
/// \param vn is the given Varnode
/// \param phiNodeEdges is the list of edges to excise
/// \param reachable will hold the list ops that have been reached
void ActionConditionalConst::collectReachable(Varnode *vn,vector<PcodeOpNode> &phiNodeEdges,vector<PcodeOp *> &reachable)

{
  sort(phiNodeEdges.begin(),phiNodeEdges.end());
  int4 count = 0;
  if (vn->isWritten()) {
    PcodeOp *op = vn->getDef();
    if (op->code() == CPUI_MULTIEQUAL) {
      // Consider defining MULTIEQUAL to be "reachable" This allows flowToAlternatePath to discover
      // a loop back to vn from the constBlock, even if no other non-constant path survives
      op->setMark();
      reachable.push_back(op);
    }
  }
  for(;;) {
    list<PcodeOp *>::const_iterator iter;
    for(iter=vn->beginDescend();iter!=vn->endDescend();++iter) {
      PcodeOp *op = *iter;
      if (op->isMark()) continue;
      OpCode opc = op->code();
      if (opc == CPUI_MULTIEQUAL) {
	PcodeOpNode tmpOp(op,0);
	for(tmpOp.slot=0;tmpOp.slot<op->numInput();++tmpOp.slot) {
	  if (op->getIn(tmpOp.slot) != vn) continue;		// Find incoming slot for current Varnode
	  // Don't count as flow if coming thru excised edge
	  if (!binary_search(phiNodeEdges.begin(),phiNodeEdges.end(),tmpOp)) break;
	}
	if (tmpOp.slot == op->numInput()) continue;		// Was the MULTIEQUAL reached
      }
      else if (opc != CPUI_COPY && opc != CPUI_INDIRECT)
	continue;
      reachable.push_back(op);
      op->setMark();
    }
    if (count >= reachable.size()) break;
    vn = reachable[count]->getOut();
    count += 1;
  }
}

/// \brief Does the output of the given op reunite with the alternate flow
///
/// Assuming alternate flows have been marked, follow the flow of the given op forward through
/// MULTIEQUAL, INDIRECT, and COPY ops.  If it hits the alternate flow, return \b true.
/// \param op is the given PcodeOp
/// \return \b true is there is an alternate path
bool ActionConditionalConst::flowToAlternatePath(PcodeOp *op)

{
  if (op->isMark()) return true;
  vector<Varnode *> markSet;
  Varnode *vn = op->getOut();
  markSet.push_back(vn);
  vn->setMark();
  int4 count = 0;
  bool foundPath = false;
  while(count < markSet.size()) {
    vn = markSet[count];
    count += 1;
    list<PcodeOp *>::const_iterator iter;
    for(iter=vn->beginDescend();iter!=vn->endDescend();++iter) {
      PcodeOp *nextOp  = *iter;
      OpCode opc = nextOp->code();
      if (opc == CPUI_MULTIEQUAL) {
	if (nextOp->isMark()) {
	  foundPath = true;
	  break;
	}
      }
      else if (opc != CPUI_COPY && opc != CPUI_INDIRECT)
	continue;
      Varnode *outVn = nextOp->getOut();
      if (outVn->isMark()) continue;
      outVn->setMark();
      markSet.push_back(outVn);
    }
    if (foundPath) break;
  }
  for(int4 i=0;i<markSet.size();++i)
    markSet[i]->clearMark();
  return foundPath;
}

/// \brief Test if flow from a specific edge is disjoint from other edges
///
/// All MULTIEQUAL and COPY ops reachable from the edge are marked. If any other edge
/// is in this marked set, mark both edges in the result set.
/// \param edges is the set of edges
/// \param i is the index of the specific edge to test
/// \param result is the array of marks to be returned
/// \return \b true if the selected edge flows together with any other edge
bool ActionConditionalConst::flowTogether(const vector<PcodeOpNode> &edges,int4 i,vector<int4> &result)

{
  vector<PcodeOp *> reachable;
  vector<PcodeOpNode> excise;	// No edge excised
  collectReachable(edges[i].op->getOut(),excise,reachable);
  bool res = false;
  for(int4 j=0;j<edges.size();++j) {
    if (i == j) continue;
    if (result[j] == 0) continue;	// Check for disconnected path
    if (edges[j].op->isMark()) {
      result[i] = 2;			// Disconnected paths, which flow together
      result[j] = 2;
      res = true;
    }
  }
  clearMarks(reachable);
  return res;
}

/// \brief Place a COPY of a constant at the end of a basic block
///
/// \param op is an alternate "last" op
/// \param bl is the basic block
/// \param constVn is the constant to be assigned
/// \param data is the function containing the block
/// \return the new output Varnode of the COPY
Varnode *ActionConditionalConst::placeCopy(PcodeOp *op,BlockBasic *bl,Varnode *constVn,Funcdata &data)

{
  PcodeOp *lastOp = bl->lastOp();
  list<PcodeOp *>::iterator iter;
  Address addr;
  if (lastOp == (PcodeOp *)0) {
    iter = bl->endOp();
    addr = op->getAddr();
  }
  else if (lastOp->isBranch()) {
    iter = lastOp->getBasicIter();	// Insert before any branch
    addr = lastOp->getAddr();
  }
  else {
    iter = bl->endOp();
    addr = lastOp->getAddr();
  }
  PcodeOp *copyOp = data.newOp(1,addr);
  data.opSetOpcode(copyOp, CPUI_COPY);
  Varnode *outVn = data.newUniqueOut(constVn->getSize(), copyOp);
  data.opSetInput(copyOp,constVn,0);
  data.opInsert(copyOp, bl, iter);
  return outVn;
}

/// \brief Place a single COPY assignment shared by multiple MULTIEQUALs
///
/// Find the common ancestor block among all MULTIEQUALs marked as flowing together.
/// Place a COPY assigning a constant at the bottom of this block.
/// Replace all the input edge Varnodes on the MULTIEQUALs with the output of this COPY.
/// \param phiNodeEdges is the list of MULTIEQUALs and their incoming edges
/// \param marks are the marks applied to the MULTIEQUALs (2 == flowtogether)
/// \param constVn is the constant being assigned by the COPY
/// \param data is the function
void ActionConditionalConst::placeMultipleConstants(vector<PcodeOpNode> &phiNodeEdges,vector<int4> &marks,
						    Varnode *constVn,Funcdata &data)
{
  vector<FlowBlock *> blocks;
  PcodeOp *op = (PcodeOp *)0;
  for(int4 i=0;i<phiNodeEdges.size();++i) {
    if (marks[i] != 2) continue;	// Check that the MULTIQUAL is marked as flowing together
    op = phiNodeEdges[i].op;
    FlowBlock *bl = op->getParent();
    bl = bl->getIn(phiNodeEdges[i].slot);
    blocks.push_back(bl);
  }
  BlockBasic *rootBlock = (BlockBasic *)FlowBlock::findCommonBlock(blocks);
  Varnode *outVn = placeCopy(op, rootBlock, constVn, data);
  for(int4 i=0;i<phiNodeEdges.size();++i) {
    if (marks[i] != 2) continue;
    data.opSetInput(phiNodeEdges[i].op, outVn, phiNodeEdges[i].slot);
  }
}

/// \brief Try to push the constant at the front point through to the output of the given PcodeOp
///
/// If successful, create a ConstPoint to search for reads of this new constant.
/// \param points is the set of points with the current point at the front
/// \param op is p-code op to push the constant through
void ActionConditionalConst::pushConstant(list<ConstPoint> &points,PcodeOp *op)

{
  if ((op->getEvalType() & PcodeOp::special) != 0) return;
  if (op->getOpcode()->isFloatingPointOp()) return;
  Varnode *outvn = op->getOut();
  if (outvn->getSize() > sizeof(uintb)) return;
  Varnode *vn = points.front().vn;
  int4 slot = op->getSlot(vn);
  uintb in[3];
  for(int4 i=0;i<op->numInput();++i) {
    if (i == slot)
      in[i] = points.front().value;
    else {
      Varnode *inVn = op->getIn(i);
      if (inVn->getSize() > sizeof(uintb)) return;
      if (inVn->isConstant())
	in[i] = op->getIn(i)->getOffset();
      else
	return;		// Not all inputs are constant
    }
  }
  bool evalError;
  uintb outval = op->executeSimple(in,evalError);
  if (evalError)
    return;
  points.emplace_back(outvn,outval,points.front().constBlock,points.front().inSlot,points.front().blockIsDom);
}

/// \brief Replace MULTIEQUAL edges with constant if there is no alternate flow
///
/// A given Varnode is known to be constant along a set of MULTIEQUAL edges. If these edges are excised from the
/// data-flow, and the output of a MULTIEQUAL does not rejoin with the Varnode along an alternate path, then that
/// edge is replaced with a constant.
/// \param varVn is the given Varnode
/// \param constVn is the constant to replace it with
/// \param phiNodeEdges is the set of edges the Varnode is known to be constant on
/// \param data is the function containing this data-flow
void ActionConditionalConst::handlePhiNodes(Varnode *varVn,Varnode *constVn,vector<PcodeOpNode> &phiNodeEdges,Funcdata &data)

{
  vector<PcodeOp *> alternateFlow;
  vector<int4> results(phiNodeEdges.size(),0);
  collectReachable(varVn,phiNodeEdges,alternateFlow);
  int4 alternate = 0;
  for(int4 i=0;i<phiNodeEdges.size();++i) {
    if (!flowToAlternatePath(phiNodeEdges[i].op)) {
      results[i] = 1;	// Mark as disconnecting
      alternate += 1;
    }
  }
  clearMarks(alternateFlow);

  bool hasFlowTogether = false;
  if (alternate > 1) {
    // If we reach here, multiple MULTIEQUAL are disjoint from the non-constant flow
    for(int4 i=0;i<results.size();++i) {
      if (results[i] == 0) continue;		// Is this a disconnected path
      if (flowTogether(phiNodeEdges,i,results))	// Check if the disconnected paths flow together
	hasFlowTogether = true;
    }
  }
  // Add COPY assignment for each edge that has its own disconnected path going forward
  for(int4 i=0;i<phiNodeEdges.size();++i) {
    if (results[i] != 1) continue;		// Check for disconnected path that does not flow into another path
    PcodeOp *op = phiNodeEdges[i].op;
    int4 slot = phiNodeEdges[i].slot;
    BlockBasic *bl = (BlockBasic *)op->getParent()->getIn(slot);
    Varnode *outVn = placeCopy(op, bl, constVn, data);
    data.opSetInput(op,outVn,slot);
    count += 1;
  }
  if (hasFlowTogether) {
    placeMultipleConstants(phiNodeEdges, results, constVn, data);	// Add COPY assignment for edges that flow together
    count += 1;
  }
}

/// \brief Test if we can reach the given Varnode via a path other than through the immediate edge
///
/// The given Varnode is an input to a MULTIEQUAL through a specific input slot.  If we can reach the
/// same Varnode backtracking through one of the other slots, return \b true.  We can backtrack
/// through MULTIEQUALs up to a given depth and possibly a final INT_ADD.
/// \param vn is the given Varnode
/// \param op is the MULTIEQUAL reading \b vn
/// \param slot is the input index of \b vn
/// \param depth is the maximum depth to backtrack
/// \return \b true if an alternate path to the Varnode is found
bool ActionConditionalConst::testAlternatePath(Varnode *vn,PcodeOp *op,int4 slot,int4 depth)

{
  for(int4 i=0;i<op->numInput();++i) {
    if (i == slot) continue;
    Varnode *inVn = op->getIn(i);
    if (inVn == vn) return true;
    if (inVn->isWritten()) {
      PcodeOp *curOp = inVn->getDef();
      OpCode opc = curOp->code();
      if (opc == CPUI_INT_ADD || opc == CPUI_PTRSUB || opc == CPUI_PTRADD) {
	if (curOp->getIn(0) == vn || curOp->getIn(1) == vn)
	  return true;
      }
      else if (opc == CPUI_MULTIEQUAL) {
	if (depth == 0) continue;
	if (testAlternatePath(vn,curOp,-1,depth-1))
	  return true;
      }
    }
  }
  return false;
}

/// \brief At each ConstPoint, replace reads of the Varnode down the constant path with a constant Varnode
///
/// Process ConstPoints from the front of the list.
/// For each read op of current point's Varnode, check if it is in the constant path.
/// If it is, replace the read with a new constant Varnode.
/// If not in the constant path, attempt to make the output Varnode into a new ConstPoint that may have
/// have reads in the constant path.
/// \param points is the list of ConstPoints
/// \param useMultiequal is \b true if conditional constants can be applied to MULTIEQUAL ops
/// \param data is the function being analyzed
void ActionConditionalConst::propagateConstant(list<ConstPoint> &points,bool useMultiequal,Funcdata &data)

{
  vector<PcodeOpNode> phiNodeEdges;
  while(!points.empty()) {
    ConstPoint &point(points.front());
    Varnode *varVn = point.vn;
    Varnode *constVn = point.constVn;
    FlowBlock *constBlock = point.constBlock;
    list<PcodeOp *>::const_iterator iter = varVn->beginDescend();
    list<PcodeOp *>::const_iterator enditer = varVn->endDescend();
    while(iter != enditer) {
      PcodeOp *op = *iter;
      while(iter != enditer && *iter == op)
	++iter;				// Advance iterator off of current op, as this descendant may be erased
      OpCode opc = op->code();
      if (opc == CPUI_INDIRECT)			// Don't propagate constant into these
	continue;
      else if (opc == CPUI_MULTIEQUAL) {
	if (!useMultiequal)
	  continue;
	if (varVn->isAddrTied() && varVn->getAddr() == op->getOut()->getAddr())
	  continue;
	FlowBlock *bl = op->getParent();
	if (bl == constBlock) {		// The immediate edge from the conditional block, coming into a MULTIEQUAL
	  if (op->getIn(point.inSlot) == varVn) {
	    // Its possible the compiler still intends the constant value to be the same variable
	    // Test for conditions when this is likely so we don't unnecessarily create a new variable
	    if (point.value > 1) continue;
	    if (op->getOut()->isAddrTied()) continue;
	    if (testAlternatePath(varVn, op, point.inSlot, 2)) continue;
	    phiNodeEdges.emplace_back(op,point.inSlot);
	  }
	}
	else if (point.blockIsDom) {
	  for(int4 slot=0;slot<op->numInput();++slot) {
	    if (op->getIn(slot) == varVn) {
	      if (constBlock->dominates(bl->getIn(slot))) {
		phiNodeEdges.emplace_back(op,slot);
	      }
	    }
	  }
	}
	continue;
      }
      else if (opc == CPUI_COPY) {		// Don't propagate into COPY unless...
	PcodeOp *followOp = op->getOut()->loneDescend();
	if (followOp == (PcodeOp *)0) continue;
	if (followOp->isMarker()) continue;
	if (followOp->code() == CPUI_COPY) continue;
						// ...unless COPY is into something more interesting
      }
      if (!point.blockIsDom) continue;
      if (constBlock->dominates(op->getParent())) {
	if (constVn == (Varnode *)0)
	  constVn = data.newConstant(varVn->getSize(), point.value);
	if (opc == CPUI_RETURN) {
          // CPUI_RETURN ops can't directly take constants
          // as inputs
          PcodeOp *copyBeforeRet = data.newOp(1, op->getAddr());
          data.opSetOpcode(copyBeforeRet,CPUI_COPY);
          data.opSetInput(copyBeforeRet,constVn,0);
          data.newVarnodeOut(varVn->getSize(),varVn->getAddr(),copyBeforeRet);
          data.opSetInput(op,copyBeforeRet->getOut(),1);
          data.opInsertBefore(copyBeforeRet,op);
	}
	else {
	  int4 slot = op->getSlot(varVn);
	  data.opSetInput(op,constVn,slot);	// Replace ref with constant!
	}
	count += 1;			// We made a change
      }
      else {
	pushConstant(points, op);
      }
    }
    if (!phiNodeEdges.empty()) {
      if (constVn == (Varnode *)0)
	constVn = data.newConstant(varVn->getSize(), point.value);
      handlePhiNodes(varVn, constVn, phiNodeEdges, data);
      phiNodeEdges.clear();
    }
    points.pop_front();
  }
}

/// \brief Find a Varnode being compared to a constant creating the given CBRANCH boolean
///
/// If the boolean is created by comparing a Varnode to a constant, create a ConstPoint record
/// indicating the path down which the Varnode can be considered constant.
/// \param points will hold any new ConstPoint
/// \param boolVn is the given CBRANCH boolean
/// \param bl is the block constaining the CBRANCH
/// \param blockDom is an array of booleans indicating along which out edges a constant could be pushed
/// \param flipEdge is \b true if the meaning of the CBRANCH has been flipped
void ActionConditionalConst::findConstCompare(list<ConstPoint> &points,Varnode *boolVn,FlowBlock *bl,
					      bool *blockDom,bool flipEdge)
{
  if (!boolVn->isWritten()) return;
  PcodeOp *compOp = boolVn->getDef();
  OpCode opc = compOp->code();
  if (opc == CPUI_BOOL_NEGATE) {
    flipEdge = !flipEdge;
    boolVn = compOp->getIn(0);
    if (!boolVn->isWritten()) return;
    compOp = boolVn->getDef();
    opc = compOp->code();
  }
  int4 constEdge;			// Out edge where value is constant
  if (opc == CPUI_INT_EQUAL)
    constEdge = 1;
  else if (opc == CPUI_INT_NOTEQUAL)
    constEdge = 0;
  else
    return;
  // Find the variable and verify that it is compared to a constant
  Varnode *varVn = compOp->getIn(0);
  Varnode *constVn = compOp->getIn(1);
  if (!constVn->isConstant()) {
    if (!varVn->isConstant())
      return;
    Varnode *tmp = constVn;
    constVn = varVn;
    varVn = tmp;
  }
  if (varVn->loneDescend() != (PcodeOp *)0) return;
  if (flipEdge)
    constEdge = 1 - constEdge;
  points.emplace_back(varVn,constVn,bl->getOut(constEdge),bl->getOutRevIndex(constEdge),blockDom[constEdge]);
}

int4 ActionConditionalConst::apply(Funcdata &data)

{
  bool useMultiequal = true;
  AddrSpace *stackSpace = data.getArch()->getStackSpace();
  if (stackSpace != (AddrSpace *)0) {
    // Determining if conditional constants should apply to MULTIEQUAL operations may require
    // flow calculations.
    int4 numPasses = data.numHeritagePasses(stackSpace);
    if (numPasses <= 0)		// If the stack hasn't been heritaged yet
      useMultiequal = false;	// Don't propagate into MULTIEQUAL
  }
  const BlockGraph &blockGraph(data.getBasicBlocks());
  bool blockDom[2];
  list<ConstPoint> points;
  for(int4 i=0;i<blockGraph.getSize();++i) {
    FlowBlock *bl = blockGraph.getBlock(i);
    PcodeOp *cBranch = bl->lastOp();
    if (cBranch == (PcodeOp *)0 || cBranch->code() != CPUI_CBRANCH) continue;
    Varnode *boolVn = cBranch->getIn(1);
    blockDom[0] = bl->getOut(0)->restrictedByConditional(bl);	// Make sure boolean constant holds down false branch
    blockDom[1] = bl->getOut(1)->restrictedByConditional(bl);
    bool flipEdge = cBranch->isBooleanFlip();
    if (boolVn->loneDescend() == (PcodeOp *)0) {	// If the boolean is read more than once
      // Search for implied constants, bool=0 down false branch, bool=1 down true branch
      points.emplace_back(boolVn, flipEdge ? 1 : 0, bl->getFalseOut(),bl->getOutRevIndex(0),blockDom[0]);
      points.emplace_back(boolVn, flipEdge ? 0 : 1, bl->getTrueOut(),bl->getOutRevIndex(1),blockDom[1]);
    }
    findConstCompare(points, boolVn, bl, blockDom, flipEdge);
    propagateConstant(points, useMultiequal, data);
  }
  return 0;
}

int4 ActionSwitchNorm::apply(Funcdata &data)

{
  for(int4 i=0;i<data.numJumpTables();++i) {
    JumpTable *jt = data.getJumpTable(i);
    if (!jt->isLabelled()) {
      jt->matchModel(&data);
      jt->recoverLabels(&data);	// Recover case statement labels
      jt->foldInNormalization(&data);
      count += 1;
    }
    if (jt->foldInGuards(&data)) {
      data.getStructure().clear();	// Make sure we redo structure
      count += 1;
    }
  }
  return 0;
}

int4 ActionNormalizeSetup::apply(Funcdata &data)

{
  FuncProto &fp( data.getFuncProto() );
  fp.clearInput();
  fp.setModelLock(false);	// This will cause the model to get reevaluated
  fp.setOutputLock(false);

  // FIXME:  This should probably save and restore symbols, model, and state
  //   If we are calculating normalized trees in console mode, this currently eliminates locks
  //   that may be needed by other normalizing calculations
  return 0;
}

/// \brief Extend Varnode inputs to match prototype model.
///
/// For prototype models that assume input variables are already extended in some way,
/// insert the appropriate extension operation to allow correct small-size input
/// Varnode to exist.
/// \param data is the function being analyzed
/// \param invn is the given (small) input Varnode
/// \param param is the matching symbol info for the Varnode
/// \param topbl is the entry block for the function
void ActionPrototypeTypes::extendInput(Funcdata &data,Varnode *invn,ProtoParameter *param,BlockBasic *topbl)

{
  VarnodeData vdata;
  OpCode res = data.getFuncProto().assumedInputExtension(invn->getAddr(),invn->getSize(),vdata);
  if (res == CPUI_COPY) return;		// no extension
  if (res == CPUI_PIECE) {	// Do an extension based on type of parameter
    if (param->getType()->getMetatype() == TYPE_INT)
      res = CPUI_INT_SEXT;
    else
      res = CPUI_INT_ZEXT;
  }
  PcodeOp *op = data.newOp(1,topbl->getStart());
  data.newVarnodeOut(vdata.size,vdata.getAddr(),op);
  data.opSetOpcode(op,res);
  data.opSetInput(op,invn,0);
  data.opInsertBegin(op,topbl);
}

int4 ActionPrototypeTypes::apply(Funcdata &data)

{
  list<PcodeOp *>::const_iterator iter,iterend;

  // Set the evaluation prototype if we are not already locked
  ProtoModel *evalfp = data.getArch()->evalfp_current;
  if (evalfp == (ProtoModel *)0)
    evalfp = data.getArch()->defaultfp;
  if ((!data.getFuncProto().isModelLocked()) && !data.getFuncProto().hasMatchingModel(evalfp))
    data.getFuncProto().setModel(evalfp);
  if (data.getFuncProto().hasThisPointer())
    data.prepareThisPointer();

  iterend = data.endOp(CPUI_RETURN);

				// Strip the indirect register from all RETURN ops
				// (Because we don't want to see this compiler
				// mechanism in the high-level C output)
  for(iter=data.beginOp(CPUI_RETURN);iter!=iterend;++iter) {
    PcodeOp *op = *iter;
    if (op->isDead()) continue;
    if (!op->getIn(0)->isConstant()) {
      Varnode *vn = data.newConstant(op->getIn(0)->getSize(),0);
      data.opSetInput(op,vn,0);
    }
  }

  if (data.getFuncProto().isOutputLocked()) {
    ProtoParameter *outparam = data.getFuncProto().getOutput();
    if (outparam->hasStorage()) {
      for(iter=data.beginOp(CPUI_RETURN);iter!=iterend;++iter) {
	PcodeOp *op = *iter;
	if (op->isDead()) continue;
	if (op->getHaltType() != 0) continue;
	Varnode *vn = data.newVarnode(outparam->getSize(),outparam->getAddress());
	data.opInsertInput(op,vn,op->numInput());
	vn->updateType(outparam->getType(),true,true);
      }
    }
  }
  else
    data.initActiveOutput(); // Initiate gathering potential return values

  AddrSpace *spc = data.getArch()->getDefaultCodeSpace();
  if (spc->isTruncated()) {
    // For truncated spaces we need a zext op, from the truncated stack pointer
    // into the full stack pointer
    AddrSpace *stackspc = data.getArch()->getStackSpace();
    BlockBasic *topbl = (BlockBasic *)0;
    if (data.getBasicBlocks().getSize() > 0)
      topbl = (BlockBasic *)data.getBasicBlocks().getBlock(0);
    if ((stackspc != (AddrSpace *)0)&&(topbl != (BlockBasic *)0)) {
      for(int4 i=0;i<stackspc->numSpacebase();++i) {
	const VarnodeData &fullReg( stackspc->getSpacebaseFull(i) );
	const VarnodeData &truncReg( stackspc->getSpacebase(i) );
	Varnode *invn = data.newVarnode( truncReg.size, truncReg.getAddr() );
	invn = data.setInputVarnode(invn);
	PcodeOp *extop = data.newOp(1,topbl->getStart());
	data.newVarnodeOut(fullReg.size,fullReg.getAddr(),extop);
	data.opSetOpcode(extop,CPUI_INT_ZEXT);
	data.opSetInput(extop,invn,0);
	data.opInsertBegin(extop,topbl);
      }
    }
  }

  // Force locked inputs to exist as varnodes

  // This is needed if we want to force a big input to exist
  // but only part of it is getting used. This is allows
  // a SUBPIECE instruction to get built with the big variable
  // as input and the part getting used as output.
  if (data.getFuncProto().isInputLocked()) {

    int4 ptr_size = spc->isTruncated() ? spc->getAddrSize() : 0; // Check if we need to do pointer trimming
    BlockBasic *topbl = (BlockBasic *)0;
    if (data.getBasicBlocks().getSize() > 0)
      topbl = (BlockBasic *)data.getBasicBlocks().getBlock(0);

    int4 numparams = data.getFuncProto().numParams();
    for(int4 i=0;i<numparams;++i) {
      ProtoParameter *param = data.getFuncProto().getParam(i);
      if (!param->hasStorage()) continue;
      Varnode *vn = data.newVarnode( param->getSize(), param->getAddress());
      vn = data.setInputVarnode(vn);
      vn->setLockedInput();
      if (topbl != (BlockBasic *)0)
	extendInput(data,vn,param,topbl);
      if (ptr_size > 0) {
	Datatype *ct = param->getType();
	if ((ct->getMetatype() == TYPE_PTR)&&(ct->getSize() == ptr_size))
	  vn->setPtrFlow();
      }
    }
  }
  return 0;
}

/// Sort by address, then by data-type size, then by data-type ordering.
/// \param op2 is the reference to compare with
/// \return \b true if \b this should be ordered before \b op2
bool ActionInputPrototype::InputRef::operator<(const InputRef &op2) const

{
  if (addr != op2.addr)
    return (addr < op2.addr);
  if (dataType == op2.dataType)
    return false;
  if (dataType->getSize() != op2.dataType->getSize())
    return (op2.dataType->getSize() < dataType->getSize());	// Bigger data-types first
  return (dataType->typeOrder(*op2.dataType) <= 0);
}

/// Remove the later reference of any pairs that overlap.
/// \param refs is the list of references
void ActionInputPrototype::InputRef::dedup(list<InputRef> &refs)

{
  list<InputRef>::const_iterator iter=refs.begin();
  if (iter == refs.end()) return;
  Address lastAddr = (*iter).addr;
  int4 size = (*iter).dataType->getSize();
  ++iter;
  while(iter != refs.end()) {
    if ((*iter).addr.overlap(0, lastAddr, size) >= 0)
      iter = refs.erase(iter);
    else {
      lastAddr = (*iter).addr;
      size = (*iter).dataType->getSize();
      ++iter;
    }
  }
}

/// \brief Gather references into the region of the stack reserved for parameters
///
/// Look for PTRSUBs and PTRADDs off of the \e spacebase pointer for the local scope.
/// Calculate the base address being referenced, and if it is a possible parameter,
/// store the address and data-type associated with the reference.  Sort and deup the references.
/// \param refs will hold any collected parameter references
/// \param data is the function
void ActionInputPrototype::gatherParamSpacebaseRefs(list<InputRef> &refs,Funcdata &data)

{
  AddrSpace *spcid = data.getScopeLocal()->getSpaceId();
  Varnode *spcvn = data.findSpacebaseInput(spcid);
  if (spcvn == (Varnode *)0) return;
  Datatype *spctype = spcvn->getType();
  if (spctype->getMetatype() != TYPE_PTR) return;
  spctype = ((TypePointer *)spctype)->getPtrTo();
  if (spctype->getMetatype() != TYPE_SPACEBASE) return;
  TypeSpacebase *sbtype = (TypeSpacebase *)spctype;
  const RangeList &paramRange(data.getFuncProto().getParamRange());
  list<PcodeOp *>::const_iterator iter;
  Address addr;
  Datatype *dt;

  for(iter=spcvn->beginDescend();iter!=spcvn->endDescend();++iter) {
    PcodeOp *op = *iter;
    Varnode *vn;
    OpCode opc = op->code();
    if (opc == CPUI_PTRSUB) {
      vn = op->getIn(1);
      addr = sbtype->getAddress(vn->getOffset(),vn->getSize(),op->getAddr());
    }
    else if (opc == CPUI_PTRADD) {
      vn = op->getIn(1);
      if (vn->isConstant()) {
	uintb off = vn->getOffset() * op->getIn(2)->getOffset();
	addr = sbtype->getAddress(off,vn->getSize(),op->getAddr());
      }
      else
	continue;
    }
    else
      continue;
    if (paramRange.inRange(addr, 1)) {
      dt = op->getOut()->getTypeDefFacing();
      if (dt->getMetatype() == TYPE_PTR) {
	dt = ((TypePointer *)dt)->getPtrTo();
	if (dt->getSize() == 0)
	  dt = data.getArch()->types->getBase(1,TYPE_UNKNOWN);
      }
      else
	dt = data.getArch()->types->getBase(1,TYPE_UNKNOWN);
      if (!data.getFuncProto().possibleInputParam(addr, dt->getSize())) {
	VarnodeData vData;
	if (data.getFuncProto().unjustifiedInputParam(addr, dt->getSize(), vData)) {
	  if (vData.getAddr() == addr && vData.size > dt->getSize()) {
	    // If the address range is unjustified but can be justified by just changing the size (big endian case)
	    // Change the data-type to be the justified size
	    dt = data.getArch()->types->getBase(vData.size,TYPE_UNKNOWN);
	  }
	}
      }
      refs.push_back(InputRef(addr,dt));
    }
  }
  refs.sort();
  InputRef::dedup(refs);
}

/// \brief Add an active parameter trial for any reference that is a possible input and doesn't intersect a Varnode
///
/// \param active is the container accumulating parameter trials
/// \param refs is the list of references
/// \param typeList accumulates a data-type per parameter trial
/// \param data is the function
void ActionInputPrototype::markActiveInputRefs(ParamActive &active,list<InputRef> &refs,vector<Datatype *> &typeList,
					       Funcdata &data)

{
  for(list<InputRef>::const_iterator iter=refs.begin();iter!=refs.end();++iter) {
    if (data.hasInputIntersection((*iter).dataType->getSize(), (*iter).addr))
      continue;
    if (!data.getFuncProto().possibleInputParam((*iter).addr, (*iter).dataType->getSize()))
      continue;
    ParamTrial &trial(active.registerTrial((*iter).addr,(*iter).dataType->getSize()));
    typeList.push_back((*iter).dataType);
    trial.markActive();
  }
}

/// \brief Add a Symbol for any reference that doesn't intersect an existing input Varnode
///
/// \param refs is the list of references
/// \param data is the function
void ActionInputPrototype::addRefOnlySymbols(list<InputRef> &refs,Funcdata &data)

{
  for(list<InputRef>::const_iterator iter=refs.begin();iter!=refs.end();++iter) {
    if (data.getScopeLocal()->findOverlap((*iter).addr, (*iter).dataType->getSize()))
      continue;
    data.getScopeLocal()->addSymbol("", (*iter).dataType, (*iter).addr, Address());
  }
}

int4 ActionInputPrototype::apply(Funcdata &data)

{
  vector<Datatype *> typeList;
  ParamActive active(false);
  Varnode *vn;
  list<InputRef> inputRefs;

  data.getScopeLocal()->clearCategory(Symbol::fake_input);
  data.getFuncProto().clearUnlockedInput();
  if (data.getScopeLocal()->hasOpenParamRefs())
    gatherParamSpacebaseRefs(inputRefs, data);
  if (!data.getFuncProto().isInputLocked()) {
    VarnodeDefSet::const_iterator iter,enditer;
    iter = data.beginDef(Varnode::input);
    enditer = data.endDef(Varnode::input);
    bool useHigh = data.isHighOn();
    while(iter != enditer) {
      vn = *iter;
      ++iter;
      if (data.getFuncProto().possibleInputParam(vn->getAddr(),vn->getSize())) {
	if (vn->isPersist()) {
	  int4 sz;
	  Address addr = data.findDisjointCover(vn, sz);
	  Datatype *ct;
	  if (sz == vn->getSize())
	    ct = useHigh ? vn->getHigh()->getType() : vn->getType();
	  else
	    ct = data.getArch()->types->getBase(sz, TYPE_UNKNOWN);
	  ParamTrial &paramtrial(active.registerTrial(addr,sz));
	  typeList.push_back(ct);
	  if (!vn->hasNoDescend())
	    paramtrial.markActive();	// Mark as active if it has descendants
	}
	else {
	  ParamTrial &paramtrial(active.registerTrial(vn->getAddr(),vn->getSize()));
	  Datatype *ct = useHigh ? vn->getHigh()->getType() : vn->getType();
	  typeList.push_back(ct);
	  if (!vn->hasNoDescend())
	    paramtrial.markActive();	// Mark as active if it has descendants
	}
      }
    }
    markActiveInputRefs(active, inputRefs, typeList, data);
    data.getFuncProto().resolveModel(&active);
    data.getFuncProto().deriveInputMap(&active); // Derive the correct prototype from trials
    // Create any unreferenced input varnodes
    for(int4 i=0;i<active.getNumTrials();++i) {
      ParamTrial &paramtrial(active.getTrial(i));
      if (paramtrial.isUnref() && paramtrial.isUsed()) {
	if (data.hasInputIntersection(paramtrial.getSize(), paramtrial.getAddress())) {
	  // There is something in the way of the unreferenced parameter, don't create it
	  paramtrial.markNoUse();
	}
	else {
	  int4 slot = typeList.size();
	  typeList.push_back(data.getArch()->types->getBase(paramtrial.getSize(), TYPE_UNKNOWN));
	  paramtrial.setSlot(slot + 1);
	}
      }
    }
    data.getFuncProto().updateInputTypes(data,typeList,&active);
  }
  addRefOnlySymbols(inputRefs, data);
  data.clearDeadVarnodes();
#ifdef OPACTION_DEBUG
  if ((flags&rule_debug)==0) return 0;
  ostringstream s;
  data.getScopeLocal()->printEntries(s);
  data.getArch()->printDebug(s.str());
#endif
  return 0;
}

int4 ActionOutputPrototype::apply(Funcdata &data)

{
  ProtoParameter *outparam = data.getFuncProto().getOutput();
  if ((!outparam->isTypeLocked())||outparam->isSizeTypeLocked()) {
    PcodeOp *op = data.getFirstReturnOp();
    vector<Varnode *> vnlist;
    if (op != (PcodeOp *)0) {
      for(int4 i=1;i<op->numInput();++i)
	vnlist.push_back(op->getIn(i));
    }
    if (data.isHighOn())
      data.getFuncProto().updateOutputTypes(vnlist);
    else
      data.getFuncProto().updateOutputNoTypes(vnlist,data.getArch()->types);
  }
  return 0;
}

int4 ActionUnjustifiedParams::apply(Funcdata &data)

{
  VarnodeDefSet::const_iterator iter,enditer;
  FuncProto &proto( data.getFuncProto() );

  iter = data.beginDef(Varnode::input);
  enditer = data.endDef(Varnode::input);

  while(iter != enditer) {
    Varnode *vn = *iter++;
    VarnodeData vdata;
    if (!proto.unjustifiedInputParam(vn->getAddr(),vn->getSize(),vdata)) continue;

    bool newcontainer;
    do {
      newcontainer = false;
      VarnodeDefSet::const_iterator begiter,iter2;
      begiter = data.beginDef(Varnode::input);
      iter2 = iter;
      bool overlaps = false;
      while(iter2 != begiter) {
	--iter2;
	vn = *iter2;
	if (vn->getSpace() != vdata.space) continue;
	uintb offset = vn->getOffset() + vn->getSize()-1; // Last offset in varnode
	if ((offset >= vdata.offset)&&(vn->getOffset()<vdata.offset)) { // If there is overlap that extends size
	  overlaps = true;
	  uintb endpoint = vdata.offset + vdata.size;
	  vdata.offset = vn->getOffset();
	  vdata.size = endpoint - vdata.offset;
	}
      }
      if (!overlaps) break;	// Found no additional overlaps, go with current justified container
      // If there were overlaps, container may no longer be justified
      newcontainer = proto.unjustifiedInputParam(vdata.getAddr(),vdata.size,vdata);
    } while(newcontainer);

    data.adjustInputVarnodes(vdata.getAddr(),vdata.size);
    // Reset iterator because of additions and deletions
    iter = data.beginDef(Varnode::input,vdata.getAddr());
    enditer = data.endDef(Varnode::input);
    count += 1;
  }
  return 0;
}

int4 ActionHideShadow::apply(Funcdata &data)

{
  VarnodeDefSet::const_iterator iter,enditer;
  HighVariable *high;

  enditer = data.endDef(Varnode::written);
  for(iter=data.beginDef();iter!=enditer;++iter) {
    high = (*iter)->getHigh();
    if (high->isMark()) continue;
    if (data.getMerge().hideShadows(high))
      count += 1;
    high->setMark();
  }
  for(iter=data.beginDef();iter!=enditer;++iter) {
    high = (*iter)->getHigh();
    high->clearMark();
  }
  return 0;
}

int4 ActionDynamicMapping::apply(Funcdata &data)

{
  ScopeLocal *localmap = data.getScopeLocal();
  list<DynamicEntry *>::iterator iter,enditer;
  iter = localmap->beginDynamic();
  enditer = localmap->endDynamic();
  DynamicHash dhash;
  while(iter != enditer) {
    DynamicEntry *entry = *iter;
    ++iter;
    if (data.attemptDynamicMapping(entry,dhash))
      count += 1;
  }
  return 0;
}

int4 ActionDynamicSymbols::apply(Funcdata &data)

{
  ScopeLocal *localmap = data.getScopeLocal();
  list<DynamicEntry *>::iterator iter,enditer;
  iter = localmap->beginDynamic();
  enditer = localmap->endDynamic();
  DynamicHash dhash;
  while(iter != enditer) {
    DynamicEntry *entry = *iter;
    ++iter;
    if (data.attemptDynamicMappingLate(entry, dhash))
      count += 1;
  }
  return 0;
}

int4 ActionPrototypeWarnings::apply(Funcdata &data)

{
  vector<string> overridemessages;
  data.getOverride().generateOverrideMessages(overridemessages,data.getArch());
  for(int4 i=0;i<overridemessages.size();++i)
    data.warningHeader(overridemessages[i]);

  FuncProto &ourproto( data.getFuncProto() );
  if (ourproto.hasInputErrors()) {
    data.warningHeader("Cannot assign parameter locations for this function: Prototype may be inaccurate");
  }
  if (ourproto.hasOutputErrors()) {
    data.warningHeader("Cannot assign location of return value for this function: Return value may be inaccurate");
  }
  if (ourproto.isModelUnknown()) {
    ostringstream s;
    s << "Unknown calling convention";
    if (ourproto.printModelInDecl())
      s << ": " << ourproto.getModelName();
    if (!ourproto.hasCustomStorage() && (ourproto.isInputLocked() || ourproto.isOutputLocked()))
      s << " -- yet parameter storage is locked";
    data.warningHeader(s.str());
 }
  int4 numcalls = data.numCalls();
  for(int4 i=0;i<numcalls;++i) {
    FuncCallSpecs *fc = data.getCallSpecs(i);
    Funcdata *fd = fc->getFuncdata();
    if (fc->hasInputErrors()) {
      ostringstream s;
      s << "Cannot assign parameter location for function ";
      if (fd != (Funcdata *)0)
	s << fd->getName();
      else
	s << "<indirect>";
      s << ": Prototype may be inaccurate";
      data.warning(s.str(),fc->getEntryAddress());
    }
    if (fc->hasOutputErrors()) {
      ostringstream s;
      s << "Cannot assign location of return value for function ";
      if (fd != (Funcdata *)0)
	s << fd->getName();
      else
	s << "<indirect>";
      s << ": Return value may be inaccurate";
      data.warning(s.str(),fc->getEntryAddress());
    }
  }
  return 0;
}

int4 ActionInternalStorage::apply(Funcdata &data)

{
  FuncProto &proto( data.getFuncProto() );
  vector<VarnodeData>::const_iterator iter = proto.internalBegin();
  vector<VarnodeData>::const_iterator enditer = proto.internalEnd();
  while(iter != enditer) {
    Address addr = (*iter).getAddr();
    int4 sz = (*iter).size;
    ++iter;

    VarnodeLocSet::const_iterator viter = data.beginLoc(sz, addr);
    VarnodeLocSet::const_iterator endviter = data.endLoc(sz, addr);
    while(viter != endviter) {
      Varnode *vn = *viter;
      ++viter;
      list<PcodeOp *>::const_iterator oiter = vn->beginDescend();
      while(oiter != vn->endDescend()) {
	PcodeOp *op = *oiter;
	++oiter;
	if (op->code() == CPUI_STORE) {
	  if (vn->isEventualConstant(3,0)) {
	    op->setStoreUnmapped();
	  }
	}
      }
    }
  }
  return 0;
}

#ifdef TYPEPROP_DEBUG
/// \brief Log a particular data-type propagation action.
///
/// Print the Varnode updated, the new data-type it contains, and
/// where the data-type propagated from.
/// \param glb is the Architecture holding the error console
/// \param vn is the target Varnode
/// \param newtype is the new data-type
/// \param op is the PcodeOp through which the data-type propagated
/// \param slot is the slot from which the data-type propagated
/// \param ptralias if not NULL holds the pointer that aliased the target Varnode
void ActionInferTypes::propagationDebug(Architecture *glb,Varnode *vn,const Datatype *newtype,PcodeOp *op,int4 slot,Varnode *ptralias)

{
  if (!TypeFactory::propagatedbg_on) return;
  ostringstream s;

  vn->printRaw(s);
  s << " : ";
  newtype->printRaw(s);
  if ((op == (PcodeOp *)0)&&(ptralias == (Varnode *)0)) {
    s << " init";
  }
  else if (ptralias != (Varnode *)0) {
    s << " alias ";
    ptralias->printRaw(s);
  }
  else {
    s << " from ";
    op->printRaw(s);
    s << " slot=" << dec << slot;
  }
  glb->printDebug(s.str());
}
#endif

/// Collect \e local data-type information on each Varnode inferred
/// from the PcodeOps that read and write to it.
/// \param data is the function being analyzed
void ActionInferTypes::buildLocaltypes(Funcdata &data)

{
  Datatype *ct;
  Varnode *vn;
  VarnodeLocSet::const_iterator iter;
  TypeFactory *typegrp = data.getArch()->types;

  for(iter=data.beginLoc();iter!=data.endLoc();++iter) {
    vn = *iter;
    if (vn->isAnnotation()) continue;
    if ((!vn->isWritten())&&(vn->hasNoDescend())) continue;
    bool needsBlock = false;
    SymbolEntry *entry = vn->getSymbolEntry();
    if (entry != (SymbolEntry *)0 && !vn->isTypeLock() && entry->getSymbol()->isTypeLocked()) {
      int4 curOff = entry->getOffset();
      if (entry->isMapEntry())
	curOff += (vn->getAddr().getOffset() - ((MapEntry *)entry)->getAddr().getOffset());
      ct = typegrp->getExactPiece(entry->getSymbol()->getType(), curOff, vn->getSize());
      if (ct == (Datatype *)0 || ct->getMetatype() == TYPE_UNKNOWN)	// If we can't resolve, or resolve to UNKNOWN
	ct = vn->getLocalType(needsBlock);		// Let data-type float, even though parent symbol is type-locked
    }
    else
      ct = vn->getLocalType(needsBlock);
    if (needsBlock)
      vn->setStopUpPropagation();
#ifdef TYPEPROP_DEBUG
    propagationDebug(data.getArch(),vn,ct,(PcodeOp *)0,0,(Varnode *)0);
#endif
    vn->setTempType(ct);
  }
}

/// For each Varnode copy the temporary data-type to the permament
/// field, taking into account previous locks.
/// \param data is the function being analyzed
/// \return \b true if any Varnode's data-type changed from the last round of propagation
bool ActionInferTypes::writeBack(Funcdata &data)

{
  bool change = false;
  Datatype *ct;
  Varnode *vn;
  VarnodeLocSet::const_iterator iter;

  for(iter=data.beginLoc();iter!=data.endLoc();++iter) {
    vn = *iter;
    if (vn->isAnnotation()) continue;
    if ((!vn->isWritten())&&(vn->hasNoDescend())) continue;
    ct = vn->getTempType();
    if (vn->updateType(ct))
      change = true;
  }
  return change;
}

/// \brief Attempt to propagate a data-type across a single PcodeOp edge
///
/// Given an \e input Varnode and an \e output Varnode defining a directed edge
/// through a PcodeOp, determine if and how the input data-type propagates to the
/// output. Update the output Varnode's (temporary) data-type. An input to the
/// edge may either an input or output to the PcodeOp.  A \e slot value of -1
/// indicates the PcodeOp output, a non-negative value indicates a PcodeOp input index.
/// \param typegrp is the TypeFactory for building a possibly transformed data-type
/// \param op is the PcodeOp through which the propagation edge flows
/// \param inslot indicates the edge's input Varnode
/// \param outslot indicates the edge's output Varnode
/// \return \b true if the data-type propagates
bool ActionInferTypes::propagateTypeEdge(TypeFactory *typegrp,PcodeOp *op,int4 inslot,int4 outslot)

{
  Varnode *invn,*outvn;

  if (inslot == outslot) return false; // don't backtrack
  invn = (inslot==-1) ? op->getOut() : op->getIn(inslot);
  Datatype *alttype = invn->getTempType();
  if (alttype->needsResolution()) {
    // Always give incoming data-type a chance to resolve, even if it would not otherwise propagate
    Datatype *resType = alttype->resolveInFlow(op, inslot);
    if (!op->isMarker())
      alttype = resType;
  }
  if (outslot < 0)
    outvn = op->getOut();
  else {
    outvn = op->getIn(outslot);
    if (outvn->isAnnotation()) return false;
  }
  if (outvn->isTypeLock()) return false; // Can't propagate through typelock
  if (outvn->stopsUpPropagation() && outslot >= 0) return false;	// Propagation is blocked

  if (alttype->getMetatype() == TYPE_BOOL) {	// Only propagate boolean
    if (outvn->getNZMask() > 1)			// If we know output can only take boolean values
      return false;
  }

  Datatype *newtype = op->getOpcode()->propagateType(alttype, op, invn, outvn, inslot, outslot);
  if (newtype == (Datatype *)0)
    return false;

  if (0>newtype->typeOrder(*outvn->getTempType())) {
#ifdef TYPEPROP_DEBUG
    propagationDebug(typegrp->getArch(),outvn,newtype,op,inslot,(Varnode *)0);
#endif
    outvn->setTempType(newtype);
    return !outvn->isMark();
  }
  return false;
}

/// \param v is the root Varnode to iterate over
PropagationState::PropagationState(Varnode *v)

{
  vn = v;
  iter = vn->beginDescend();
  if (iter != vn->endDescend()) {
    op = *iter++;
    if (op->getOut() != (Varnode *)0)
      slot = -1;
    else
      slot = 0;
    inslot = op->getSlot(vn);
  }
  else {
    op = vn->getDef();
    inslot = -1;
    slot = 0;
  }
}

/// At the high level, this iterates through all the descendant
/// PcodeOps of the root Varnode, then the defining PcodeOp.
/// At the low level, this iterates from the output Varnode
/// of the current PcodeOp then through all the input Varnodes
void PropagationState::step(void)

{
  slot += 1;
  if (slot < op->numInput())
    return;
  if (iter != vn->endDescend()) {
    op = *iter++;
    if (op->getOut() != (Varnode *)0)
      slot = -1;
    else
      slot = 0;
    inslot = op->getSlot(vn);
    return;
  }
  if (inslot == -1)
    op = (PcodeOp *)0;
  else
    op = vn->getDef();
  inslot = -1;
  slot = 0;
}

/// \brief Propagate a data-type starting from one Varnode across the function
///
/// Given a starting Varnode, propagate its Datatype as far as possible through
/// the data-flow graph, transforming the data-type through PcodeOps as necessary.
/// The data-type is push through all possible propagating edges, but each
/// Varnode is visited at most once.  Propagation is trimmed along any particular
/// path if the pushed data-type isn't \e more \e specific than the current
/// data-type on a Varnode, under the data-type ordering.
/// \param typegrp is the TypeFactory for constructing transformed data-types
/// \param vn is the Varnode holding the root data-type to push
void ActionInferTypes::propagateOneType(TypeFactory *typegrp,Varnode *vn)

{
  PropagationState *ptr;
  vector<PropagationState> state;

  state.emplace_back(vn);
  vn->setMark();

  while(!state.empty()) {
    ptr = &state.back();
    if (!ptr->valid()) {	// If we are out of edges to traverse
      ptr->vn->clearMark();
      state.pop_back();
    }
    else {
      if (propagateTypeEdge(typegrp,ptr->op,ptr->inslot,ptr->slot)) {
	vn = (ptr->slot==-1) ? ptr->op->getOut() : ptr->op->getIn(ptr->slot);
	ptr->step();		// Make sure to step before push_back
	state.emplace_back(vn);
	vn->setMark();
      }
      else
	ptr->step();
    }
  }
}

/// \brief Try to propagate a pointer data-type to known aliases.
///
/// Given a Varnode which is a likely pointer and an Address that
/// is a known alias of the pointer, attempt to propagate the Varnode's
/// data-type to Varnodes at that address.
/// \param data is the function being analyzed
/// \param vn is the given Varnode
/// \param addr is the aliased address
void ActionInferTypes::propagateRef(Funcdata &data,Varnode *vn,const Address &addr)

{
  Datatype *ct = vn->getTempType();
  if (ct->getMetatype() != TYPE_PTR) return;
  ct = ((TypePointer *)ct)->getPtrTo();
  if (ct->getMetatype() == TYPE_SPACEBASE) return;
  if (ct->getMetatype() == TYPE_UNKNOWN) return; // Don't bother propagating this
  VarnodeLocSet::const_iterator iter,enditer;
  uintb off = addr.getOffset();
  TypeFactory *typegrp = data.getArch()->types;
  Address endaddr = addr + ct->getSize();
  if (endaddr.getOffset() < off) // If the address wrapped
    enditer = data.endLoc(addr.getSpace());	// Go to end of space
  else
    enditer = data.endLoc(endaddr);
  iter = data.beginLoc(addr);
  uintb lastoff = 0;
  int4 lastsize = ct->getSize();
  Datatype *lastct = ct;
  while(iter != enditer) {
    Varnode *curvn = *iter;
    ++iter;
    if (curvn->isAnnotation()) continue;
    if ((!curvn->isWritten())&&curvn->hasNoDescend()) continue;
    if (curvn->isTypeLock()) continue;
    if (curvn->getSymbolEntry() != (SymbolEntry *)0) continue;
    uintb curoff = curvn->getOffset() - off;
    int4 cursize = curvn->getSize();
    if (curoff + cursize > ct->getSize()) continue;
    if ((cursize!=lastsize)||(curoff!=lastoff)) {
      lastoff = curoff;
      lastsize = cursize;
      lastct = typegrp->getExactPiece(ct, curoff, cursize);
    }
    if (lastct == (Datatype *)0) continue;

    // Try to propagate the reference type into a varnode that is pointed to by that reference
    if (0>lastct->typeOrder(*curvn->getTempType())) {
#ifdef TYPEPROP_DEBUG
      propagationDebug(data.getArch(),curvn,lastct,(PcodeOp *)0,0,vn);
#endif
      curvn->setTempType(lastct);
      propagateOneType(typegrp,curvn); // Try to propagate the new type as far as possible
    }
  }
}

/// \brief Search for pointers and propagate its data-type to known aliases
///
/// This routine looks for ADD operations off of a specific
/// \e spacebase register that produce output Varnodes with a known
/// data-type. The offset of the ADD is calculated into the corresponding
/// address space, and an attempt is made to propagate the Varnodes data-type
/// to other Varnodes in the address space at that offset.
/// \param data is the function being analyzed
/// \param spcvn is the spacebase register
void ActionInferTypes::propagateSpacebaseRef(Funcdata &data,Varnode *spcvn)

{
  Datatype *spctype = spcvn->getType();	// This is an absolute property of the varnode, so not temptype
  if (spctype->getMetatype() != TYPE_PTR) return;
  spctype = ((TypePointer *)spctype)->getPtrTo();
  if (spctype->getMetatype() != TYPE_SPACEBASE) return;
  TypeSpacebase *sbtype = (TypeSpacebase *)spctype;
  list<PcodeOp *>::const_iterator iter;
  Address addr;

  for(iter=spcvn->beginDescend();iter!=spcvn->endDescend();++iter) {
    PcodeOp *op = *iter;
    Varnode *vn;
    switch(op->code()) {
    case CPUI_COPY:
      vn = op->getIn(0);
      addr = sbtype->getAddress(0,vn->getSize(),op->getAddr());
      propagateRef(data,op->getOut(),addr);
      break;
    case CPUI_INT_ADD:
    case CPUI_PTRSUB:
      vn = op->getIn(1);
      if (vn->isConstant()) {
	addr = sbtype->getAddress(vn->getOffset(),vn->getSize(),op->getAddr());
	propagateRef(data,op->getOut(),addr);
      }
      break;
    case CPUI_PTRADD:
      vn = op->getIn(1);
      if (vn->isConstant()) {
	uintb off = vn->getOffset() * op->getIn(2)->getOffset();
	addr = sbtype->getAddress(off,vn->getSize(),op->getAddr());
	propagateRef(data,op->getOut(),addr);
      }
      break;
    default:
      break;
    }
  }
}

/// Return the CPUI_RETURN op with the most specialized data-type, which is not
/// dead and is not a special halt.
/// \param data is the function
/// \return the representative CPUI_RETURN op or NULL
PcodeOp *ActionInferTypes::canonicalReturnOp(Funcdata &data)

{
  PcodeOp *res = (PcodeOp *)0;
  Datatype *bestdt = (Datatype *)0;
  list<PcodeOp *>::const_iterator iter,iterend;
  iterend = data.endOp(CPUI_RETURN);
  for(iter=data.beginOp(CPUI_RETURN);iter!=iterend;++iter) {
    PcodeOp *retop = *iter;
    if (retop->isDead()) continue;
    if (retop->getHaltType()!=0) continue;
    if (retop->numInput() > 1) {
      Varnode *vn = retop->getIn(1);
      Datatype *ct = vn->getTempType();
      if (bestdt == (Datatype *)0) {
	res = retop;
	bestdt = ct;
      }
      else if (ct->typeOrder(*bestdt) < 0) {
	res = retop;
	bestdt = ct;
      }
    }
  }
  return res;
}

/// \brief Give data-types a chance to propagate between CPUI_RETURN operations.
///
/// Since a function is intended to return a single data-type, data-types effectively
/// propagate between the input Varnodes to CPUI_RETURN ops, if there are more than one.
void ActionInferTypes::propagateAcrossReturns(Funcdata &data)

{
  if (data.getFuncProto().isOutputLocked()) return;
  PcodeOp *op = canonicalReturnOp(data);
  if (op == (PcodeOp *)0) return;
  TypeFactory *typegrp = data.getArch()->types;
  Varnode *baseVn = op->getIn(1);
  Datatype *ct = baseVn->getTempType();
  int4 baseSize = baseVn->getSize();
  bool isBool = ct->getMetatype() == TYPE_BOOL;
  list<PcodeOp *>::const_iterator iter,iterend;
  iterend = data.endOp(CPUI_RETURN);
  for(iter=data.beginOp(CPUI_RETURN);iter!=iterend;++iter) {
    PcodeOp *retop = *iter;
    if (retop == op) continue;
    if (retop->isDead()) continue;
    if (retop->getHaltType()!=0) continue;
    if (retop->numInput() > 1) {
      Varnode *vn = retop->getIn(1);
      if (vn->getSize() != baseSize) continue;
      if (isBool && vn->getNZMask() > 1) continue;	// Don't propagate bool if value is not necessarily 0 or 1
      if (vn->getTempType() == ct) continue;		// Already propagated
      vn->setTempType(ct);
#ifdef TYPEPROP_DEBUG
      propagationDebug(typegrp->getArch(),vn,ct,op,1,(Varnode *)0);
#endif
      propagateOneType(typegrp, vn);
    }
  }
}

int4 ActionInferTypes::apply(Funcdata &data)

{
  // Make sure spacebase is accurate or bases could get typed and then ptrarithed
  if (!data.hasTypeRecoveryStarted()) return 0;
  TypeFactory *typegrp = data.getArch()->types;
  Varnode *vn;
  VarnodeLocSet::const_iterator iter;

#ifdef TYPEPROP_DEBUG
  if (TypeFactory::propagatedbg_on) {
    ostringstream s;
    s << "Type propagation pass - " << dec << localcount;
    data.getArch()->printDebug(s.str());
  }
#endif
  if (localcount >= 7) {       // This constant arrived at empirically
    if (localcount == 7) {
      data.warningHeader("Type propagation algorithm not settling");
      data.setTypeRecoveryExceeded();
      localcount += 1;
    }
    return 0;
  }
  data.getScopeLocal()->applyTypeRecommendations();
  buildLocaltypes(data);	// Set up initial types (based on local info)
  for(iter=data.beginLoc();iter!=data.endLoc();++iter) {
    vn = *iter;
    if (vn->isAnnotation()) continue;
    if ((!vn->isWritten())&&(vn->hasNoDescend())) continue;
    propagateOneType(typegrp,vn);
  }
  propagateAcrossReturns(data);
  AddrSpace *spcid = data.getScopeLocal()->getSpaceId();
  Varnode *spcvn = data.findSpacebaseInput(spcid);
  if (spcvn != (Varnode *)0)
    propagateSpacebaseRef(data,spcvn);
  if (writeBack(data)) {
    // count += 1;			// Do not consider this a data-flow change
    localcount += 1;
  }
  return 0;
}

/// (Re)build the default \e root Actions: decompile, jumptable, normalize, paramid, register, firstpass
void ActionDatabase::buildDefaultGroups(void)

{
  if (isDefaultGroups) return;
  groupmap.clear();
  const char *members[] = { "base", "protorecovery", "protorecovery_a", "deindirect", "localrecovery",
			    "deadcode", "typerecovery", "stackptrflow",
			    "blockrecovery", "stackvars", "deadcontrolflow", "switchnorm",
			    "cleanup", "splitcopy", "splitpointer", "merge", "dynamic", "casts", "analysis",
			    "fixateglobals", "fixateproto", "constsequence", "bitfields",
			    "segment", "returnsplit", "nodejoin", "doubleload", "doubleprecis",
			    "unreachable", "subvar", "floatprecision",
			    "conditionalexe", "" };
  setGroup("decompile",members);

  const char *jumptab[] = { "base", "noproto", "localrecovery", "deadcode", "stackptrflow",
			    "stackvars", "analysis", "segment", "subvar", "normalizebranches", "conditionalexe", "" };
  setGroup("jumptable",jumptab);

 const  char *normali[] = { "base", "protorecovery", "protorecovery_b", "deindirect", "localrecovery",
			    "deadcode", "stackptrflow", "normalanalysis",
			    "stackvars", "deadcontrolflow", "analysis", "fixateproto", "nodejoin",
			    "unreachable", "subvar", "floatprecision", "normalizebranches",
			    "conditionalexe", "" };
  setGroup("normalize",normali);

  const  char *paramid[] = { "base", "protorecovery", "protorecovery_b", "deindirect", "localrecovery",
                             "deadcode", "typerecovery", "stackptrflow", "siganalysis",
                             "stackvars", "deadcontrolflow", "analysis", "fixateproto",
                             "unreachable", "subvar", "floatprecision",
                             "conditionalexe", "" };
  setGroup("paramid",paramid);

  const char *regmemb[] = { "base", "analysis", "subvar", "" };
  setGroup("register",regmemb);

  const char *firstmem[] = { "base", "" };
  setGroup("firstpass",firstmem);
  isDefaultGroups = true;
}

/// Construct the \b universal Action that contains all possible components
/// \param conf is the Architecture that will use the Action
void ActionDatabase::universalAction(Architecture *conf)

{
  vector<Rule *>::iterator iter;
  ActionGroup *act;
  ActionGroup *actmainloop;
  ActionGroup *actfullloop;
  ActionPool *actprop,*actprop2;
  ActionPool *actcleanup;
  ActionGroup *actstackstall;
  AddrSpace *stackspace = conf->getStackSpace();

  act = new ActionRestartGroup(Action::rule_onceperfunc,"universal",1);
  registerAction(universalname,act);

  act->addAction( new ActionStart("base"));
  act->addAction( new ActionConstbase("base"));
  act->addAction( new ActionNormalizeSetup("normalanalysis"));
  act->addAction( new ActionDefaultParams("base"));
  //  act->addAction( new ActionParamShiftStart("paramshift") );
  act->addAction( new ActionExtraPopSetup("base",stackspace) );
  act->addAction( new ActionPrototypeTypes("protorecovery"));
  act->addAction( new ActionFuncLink("protorecovery") );
  act->addAction( new ActionFuncLinkOutOnly("noproto") );
  {
    actfullloop = new ActionGroup(Action::rule_repeatapply,"fullloop");
    {
      actmainloop = new ActionGroup(Action::rule_repeatapply,"mainloop");
      actmainloop->addAction( new ActionUnreachable("base") );
      actmainloop->addAction( new ActionVarnodeProps("base") );
      actmainloop->addAction( new ActionHeritage("base") );
      actmainloop->addAction( new ActionParamDouble("protorecovery") );
      actmainloop->addAction( new ActionSegmentize("base"));
      actmainloop->addAction( new ActionInternalStorage("base") );
      actmainloop->addAction( new ActionForceGoto("blockrecovery") );
      actmainloop->addAction( new ActionDirectWrite("protorecovery_a", true) );
      actmainloop->addAction( new ActionDirectWrite("protorecovery_b", false) );
      actmainloop->addAction( new ActionActiveParam("protorecovery") );
      actmainloop->addAction( new ActionReturnRecovery("protorecovery") );
      //      actmainloop->addAction( new ActionParamShiftStop("paramshift") );
      actmainloop->addAction( new ActionRestrictLocal("localrecovery") ); // Do before dead code removed
      actmainloop->addAction( new ActionDeadCode("deadcode") );
      actmainloop->addAction( new ActionDynamicMapping("dynamic") ); // Must come before restructurevarnode and infertypes
      actmainloop->addAction( new ActionSpacebase("base") );	// Must come before infertypes and nonzeromask
      actmainloop->addAction( new ActionNonzeroMask("analysis") );
      actmainloop->addAction( new ActionInferTypes("typerecovery") );
      actmainloop->addAction( new ActionRestructureVarnode("localrecovery") );
      actstackstall = new ActionGroup(Action::rule_repeatapply,"stackstall");
      {
	actprop = new ActionPool(Action::rule_repeatapply,"oppool1");
	actprop->addRule( new RuleEarlyRemoval("deadcode"));
	actprop->addRule( new RuleTermOrder("analysis"));
	actprop->addRule( new RuleSelectCse("analysis"));
	actprop->addRule( new RuleCollectTerms("analysis"));
	actprop->addRule( new RulePullsubMulti("analysis"));
	actprop->addRule( new RulePullsubIndirect("analysis"));
	actprop->addRule( new RulePushMulti("nodejoin"));
	actprop->addRule( new RuleSborrow("analysis") );
	actprop->addRule( new RuleScarry("analysis") );
	actprop->addRule( new RuleIntLessEqual("analysis") );
	actprop->addRule( new RuleTrivialArith("analysis") );
	actprop->addRule( new RuleTrivialBool("analysis") );
	actprop->addRule( new RuleTrivialShift("analysis") );
	actprop->addRule( new RuleSignShift("analysis") );
	actprop->addRule( new RuleTestSign("analysis") );
	actprop->addRule( new RuleIdentityEl("analysis") );
	actprop->addRule( new RuleOrMask("analysis") );
	actprop->addRule( new RuleAndMask("analysis") );
	actprop->addRule( new RuleOrConsume("analysis") );
	actprop->addRule( new RuleOrCollapse("analysis") );
	actprop->addRule( new RuleAndOrLump("analysis") );
	actprop->addRule( new RuleShiftBitops("analysis") );
	actprop->addRule( new RuleRightShiftAnd("analysis") );
	actprop->addRule( new RuleNotDistribute("analysis") );
	actprop->addRule( new RuleHighOrderAnd("analysis") );
	actprop->addRule( new RuleAndDistribute("analysis") );
	actprop->addRule( new RuleAndCommute("analysis") );
	actprop->addRule( new RuleAndPiece("analysis") );
	actprop->addRule( new RuleAndZext("analysis") );
	actprop->addRule( new RuleAndCompare("analysis") );
	actprop->addRule( new RuleDoubleSub("analysis") );
	actprop->addRule( new RuleDoubleShift("analysis") );
	actprop->addRule( new RuleDoubleArithShift("analysis") );
	actprop->addRule( new RuleConcatShift("analysis") );
	actprop->addRule( new RuleLeftRight("analysis") );
	actprop->addRule( new RuleShiftCompare("analysis") );
	actprop->addRule( new RuleShift2Mult("analysis") );
	actprop->addRule( new RuleShiftPiece("analysis") );
	actprop->addRule( new RuleMultiCollapse("analysis") );
	actprop->addRule( new RuleAliasUpdate("analysis") );
	actprop->addRule( new Rule2Comp2Mult("analysis") );
	actprop->addRule( new RuleSub2Add("analysis") );
	actprop->addRule( new RuleCarryElim("analysis") );
	actprop->addRule( new RuleBxor2NotEqual("analysis") );
	actprop->addRule( new RuleLess2Zero("analysis") );
	actprop->addRule( new RuleLessEqual2Zero("analysis") );
	actprop->addRule( new RuleSLess2Zero("analysis") );
	actprop->addRule( new RuleEqual2Zero("analysis") );
	actprop->addRule( new RuleEqual2Constant("analysis") );
	actprop->addRule( new RuleThreeWayCompare("analysis") );
	actprop->addRule( new RuleXorCollapse("analysis") );
	actprop->addRule( new RuleAddMultCollapse("analysis") );
	actprop->addRule( new RuleCollapseConstants("analysis") );
	actprop->addRule( new RuleTransformCpool("analysis") );
	actprop->addRule( new RulePropagateCopy("analysis") );
	actprop->addRule( new RuleZextEliminate("analysis") );
	actprop->addRule( new RuleSlessToLess("analysis") );
	actprop->addRule( new RuleZextSless("analysis") );
	actprop->addRule( new RuleBitUndistribute("analysis") );
	actprop->addRule( new RuleBooleanUndistribute("analysis") );
	actprop->addRule( new RuleBooleanDedup("analysis") );
	actprop->addRule( new RuleBoolZext("analysis") );
	actprop->addRule( new RuleBooleanNegate("analysis") );
	actprop->addRule( new RuleLogic2Bool("analysis") );
	actprop->addRule( new RuleSubExtComm("analysis") );
	actprop->addRule( new RuleSubCommute("analysis") );
	actprop->addRule( new RuleConcatCommute("analysis") );
	actprop->addRule( new RuleConcatZext("analysis") );
	actprop->addRule( new RuleZextCommute("analysis") );
	actprop->addRule( new RuleZextShiftZext("analysis") );
	actprop->addRule( new RuleShiftAnd("analysis") );
	actprop->addRule( new RuleConcatZero("analysis") );
	actprop->addRule( new RuleConcatLeftShift("analysis") );
	actprop->addRule( new RuleSubZext("analysis") );
	actprop->addRule( new RuleSubCancel("analysis") );
	actprop->addRule( new RuleShiftSub("analysis") );
	actprop->addRule( new RuleHumptyDumpty("analysis") );
	actprop->addRule( new RuleDumptyHump("analysis") );
	actprop->addRule( new RuleHumptyOr("analysis") );
	actprop->addRule( new RuleNegateIdentity("analysis") );
	actprop->addRule( new RuleSubNormal("analysis") );
	actprop->addRule( new RulePositiveDiv("analysis") );
	actprop->addRule( new RuleDivTermAdd("analysis") );
	actprop->addRule( new RuleDivTermAdd2("analysis") );
	actprop->addRule( new RuleDivOpt("analysis") );
	actprop->addRule( new RuleSignForm("analysis") );
	actprop->addRule( new RuleSignForm2("analysis") );
	actprop->addRule( new RuleSignDiv2("analysis") );
	actprop->addRule( new RuleDivChain("analysis") );
	actprop->addRule( new RuleSignNearMult("analysis") );
	actprop->addRule( new RuleModOpt("analysis") );
	actprop->addRule( new RuleSignMod2nOpt("analysis") );
	actprop->addRule( new RuleSignMod2nOpt2("analysis") );
	actprop->addRule( new RuleSignMod2Opt("analysis") );
	actprop->addRule( new RuleSwitchSingle("analysis") );
	actprop->addRule( new RuleCondNegate("analysis") );
	actprop->addRule( new RuleBoolNegate("analysis") );
	actprop->addRule( new RuleLessEqual("analysis") );
	actprop->addRule( new RuleLessNotEqual("analysis") );
	actprop->addRule( new RuleLessOne("analysis") );
	actprop->addRule( new RuleRangeMeld("analysis") );
	actprop->addRule( new RuleFloatRange("analysis") );
	actprop->addRule( new RulePiece2Zext("analysis") );
	actprop->addRule( new RulePiece2Sext("analysis") );
	actprop->addRule( new RulePopcountBoolXor("analysis") );
	actprop->addRule( new RuleXorSwap("analysis") );
	actprop->addRule( new RuleLzcountShiftBool("analysis") );
	actprop->addRule( new RuleFloatSign("analysis") );
	actprop->addRule( new RuleOrCompare("analysis") );
	actprop->addRule( new RuleSubvarAnd("subvar") );
	actprop->addRule( new RuleSubvarSubpiece("subvar") );
	actprop->addRule( new RuleSplitFlow("subvar") );
	actprop->addRule( new RulePtrFlow("subvar",conf) );
	actprop->addRule( new RuleSubvarCompZero("subvar") );
	actprop->addRule( new RuleSubvarShift("subvar") );
	actprop->addRule( new RuleSubvarZext("subvar") );
	actprop->addRule( new RuleSubvarSext("subvar") );
	actprop->addRule( new RuleNegateNegate("analysis") );
	actprop->addRule( new RuleConditionalMove("conditionalexe") );
	actprop->addRule( new RuleOrPredicate("conditionalexe") );
	actprop->addRule( new RuleFuncPtrEncoding("analysis") );
	actprop->addRule( new RuleSubfloatConvert("floatprecision") );
	actprop->addRule( new RuleFloatCast("floatprecision") );
	actprop->addRule( new RuleIgnoreNan("floatprecision") );
	actprop->addRule( new RuleUnsigned2Float("analysis") );
	actprop->addRule( new RuleInt2FloatCollapse("analysis") );
	actprop->addRule( new RulePtraddUndo("typerecovery") );
	actprop->addRule( new RulePtrsubUndo("typerecovery") );
	actprop->addRule( new RuleSegment("segment") );
	actprop->addRule( new RulePiecePathology("protorecovery") );

	actprop->addRule( new RuleDoubleLoad("doubleload") );
	actprop->addRule( new RuleDoubleStore("doubleprecis") );
	actprop->addRule( new RuleDoubleIn("doubleprecis") );
	actprop->addRule( new RuleDoubleOut("doubleprecis") );
	for(iter=conf->extra_pool_rules.begin();iter!=conf->extra_pool_rules.end();++iter)
	  actprop->addRule( *iter ); // Add CPU specific rules
	conf->extra_pool_rules.clear(); // Rules are now absorbed into universal
      }
      actstackstall->addAction( actprop );
      actstackstall->addAction( new ActionLaneDivide("base") );
      actstackstall->addAction( new ActionMultiCse("analysis") );
      actstackstall->addAction( new ActionShadowVar("analysis") );
      actstackstall->addAction( new ActionDeindirect("deindirect") );
      actstackstall->addAction( new ActionStackPtrFlow("stackptrflow",stackspace));
      actmainloop->addAction( actstackstall );
      actmainloop->addAction( new ActionRedundBranch("deadcontrolflow") ); // dead code removal
      actmainloop->addAction( new ActionBlockStructure("blockrecovery"));
      actmainloop->addAction( new ActionConstantPtr("typerecovery") );
      {
	actprop2 = new ActionPool(Action::rule_repeatapply,"oppool2");

	actprop2->addRule( new RulePushPtr("typerecovery") );
	actprop2->addRule( new RuleStructOffset0("typerecovery") );
	actprop2->addRule( new RulePtrArith("typerecovery") );
	//	actprop2->addRule( new RuleIndirectConcat("analysis") );
	actprop2->addRule( new RuleLoadVarnode("stackvars") );
	actprop2->addRule( new RuleStoreVarnode("stackvars") );
      }
      actmainloop->addAction( actprop2 );
      actmainloop->addAction( new ActionDeterminedBranch("unreachable") );
      actmainloop->addAction( new ActionUnreachable("unreachable") );
      actmainloop->addAction( new ActionNodeJoin("nodejoin") );
      actmainloop->addAction( new ActionConditionalExe("conditionalexe") );
      actmainloop->addAction( new ActionConditionalConst("analysis") );
    }
    actfullloop->addAction( actmainloop );
    actfullloop->addAction( new ActionLikelyTrash("protorecovery") );
    actfullloop->addAction( new ActionDirectWrite("protorecovery_a", true) );
    actfullloop->addAction( new ActionDirectWrite("protorecovery_b", false) );
    actfullloop->addAction( new ActionDeadCode("deadcode") );
    actfullloop->addAction( new ActionDoNothing("deadcontrolflow") );
    actfullloop->addAction( new ActionSwitchNorm("switchnorm") );
    actfullloop->addAction( new ActionReturnSplit("returnsplit") );
    actfullloop->addAction( new ActionUnjustifiedParams("protorecovery") );
    actfullloop->addAction( new ActionStartTypes("typerecovery") );
    actfullloop->addAction( new ActionActiveReturn("protorecovery") );
  }
  act->addAction( actfullloop );
  act->addAction( new ActionMappedLocalSync("localrecovery") );
  act->addAction( new ActionStartCleanUp("cleanup") );
  {
    actcleanup = new ActionPool(Action::rule_repeatapply,"cleanup");

    actcleanup->addRule( new RuleMultNegOne("cleanup") );
    actcleanup->addRule( new RuleAddUnsigned("cleanup") );
    actcleanup->addRule( new Rule2Comp2Sub("cleanup") );
    actcleanup->addRule( new RuleDumptyHumpLate("cleanup") );
    actcleanup->addRule( new RuleSubRight("cleanup") );
    actcleanup->addRule( new RuleFloatSignCleanup("cleanup") );
    actcleanup->addRule( new RuleExpandLoad("cleanup") );
    actcleanup->addRule( new RulePtrsubCharConstant("cleanup") );
    actcleanup->addRule( new RuleExtensionPush("cleanup") );
    actcleanup->addRule( new RulePieceStructure("cleanup") );
    actcleanup->addRule( new RuleAndStructure("cleanup") );
    actcleanup->addRule( new RuleSplitCopy("splitcopy") );
    actcleanup->addRule( new RuleSplitLoad("splitpointer") );
    actcleanup->addRule( new RuleSplitStore("splitpointer") );
    actcleanup->addRule( new RuleStringCopy("constsequence"));
    actcleanup->addRule( new RuleStringStore("constsequence"));
    actcleanup->addRule( new RuleBitFieldStore("bitfields"));
    actcleanup->addRule( new RuleBitFieldOut("bitfields"));
    actcleanup->addRule( new RuleBitFieldLoad("bitfields"));
    actcleanup->addRule( new RuleBitFieldIn("bitfields"));
    actcleanup->addRule( new RulePullAbsorb("bitfields"));
    actcleanup->addRule( new RuleInsertAbsorb("bitfields"));
  }
  act->addAction( actcleanup );

  act->addAction( new ActionPreferComplement("blockrecovery", true) );
  act->addAction( new ActionStructureTransform("blockrecovery", true) );	// Allow mods
  act->addAction( new ActionNormalizeBranches("normalizebranches") );
  act->addAction( new ActionAssignHigh("merge") );
  act->addAction( new ActionMergeRequired("merge") );
  act->addAction( new ActionMarkExplicit("merge") );
  act->addAction( new ActionMarkImplied("merge") ); // This must come BEFORE general merging
  act->addAction( new ActionMergeMultiEntry("merge") );
  act->addAction( new ActionMergeCopy("merge") );
  act->addAction( new ActionDominantCopy("merge") );
  act->addAction( new ActionDynamicSymbols("dynamic") );
  act->addAction( new ActionMarkIndirectOnly("merge") ); // Must come after required merges but before speculative
  act->addAction( new ActionMergeAdjacent("merge") );
  act->addAction( new ActionMergeType("merge") );
  act->addAction( new ActionHideShadow("merge") );
  act->addAction( new ActionCopyMarker("merge") );
  act->addAction( new ActionLateDoNothing("blockrecovery") );
  act->addAction( new ActionBlockStructure("blockrecovery") );
  act->addAction( new ActionPreferComplement("blockrecovery", false) );		// Don't allow mods
  act->addAction( new ActionStructureTransform("blockrecovery", false) );	// Don't allow mods
  act->addAction( new ActionOutputPrototype("localrecovery") );
  act->addAction( new ActionInputPrototype("fixateproto") );
  act->addAction( new ActionMapGlobals("fixateglobals") );
  act->addAction( new ActionDynamicSymbols("dynamic") );
  act->addAction( new ActionNameVars("merge") );
  act->addAction( new ActionSetCasts("casts") );
  act->addAction( new ActionFinalStructure("blockrecovery") );
  act->addAction( new ActionPrototypeWarnings("protorecovery") );
  act->addAction( new ActionStop("base") );
}

} // End namespace ghidra