heritage.hh

Go to the documentation of this file.

/* ###
 * IP: GHIDRA
 * NOTE: Phi placement and renaming based on ACM journal articles
 *
 * 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.
 */

#ifndef __CPUI_HERITAGE__
#define __CPUI_HERITAGE__

#include "block.hh"

typedef map<Address,vector<Varnode *> > VariableStack;

struct SizePass {
  int4 size;            
  int4 pass;            
};

class LocationMap {
public:
  typedef map<Address,SizePass>::iterator iterator;
private:
  map<Address,SizePass> themap; 
public:
  iterator add(Address addr,int4 size,int4 pass,int4 &intersect); 
  iterator find(Address addr);                
  int4 findPass(Address addr) const;              
  void erase(iterator iter) { themap.erase(iter); }   
  iterator begin(void) { return themap.begin(); }     
  iterator end(void) { return themap.end(); }         
  void clear(void) { themap.clear(); }            
};

class PriorityQueue {
  vector<vector<FlowBlock *> > queue; 
  int4 curdepth;              
public:
  PriorityQueue(void) { curdepth = -2; } 
  void reset(int4 maxdepth);         
  void insert(FlowBlock *bl,int4 depth); 
  FlowBlock *extract(void);      
  bool empty(void) const { return (curdepth==-1); } 
};

class Funcdata;
class FuncCallSpecs;

class HeritageInfo {
  friend class Heritage;
  AddrSpace *space;     
  int4 delay;           
  int4 deadcodedelay;       
  int4 deadremoved;     
  bool loadGuardSearch;     
  bool warningissued;       
  void set(AddrSpace *spc,int4 dl,int4 dcdl) {
    space=spc; delay=dl; deadcodedelay=dcdl; deadremoved=0; warningissued=false; loadGuardSearch = false; } 
  bool isHeritaged(void) const { return (space != (AddrSpace *)0); }    
  void reset(void) {
    deadremoved = 0; deadcodedelay = delay; warningissued = false; loadGuardSearch = false; }   
};

class LoadGuard {
  friend class Heritage;
  PcodeOp *op;      
  AddrSpace *spc;   
  uintb pointerBase;    
  uintb minimumOffset;  
  uintb maximumOffset;  
  int4 step;        
  int4 analysisState;   
  void establishRange(const ValueSetRead &valueSet);    
  void finalizeRange(const ValueSetRead &valueSet); 

  void set(PcodeOp *o,AddrSpace *s,uintb off) {
    op = o; spc = s; pointerBase=off; minimumOffset=0; maximumOffset=s->getHighest(); step=0; analysisState=0;
  }
public:
  PcodeOp *getOp(void) const { return op; } 
  uintb getMinimum(void) const { return minimumOffset; }    
  uintb getMaximum(void) const { return maximumOffset; }    
  int4 getStep(void) const { return step; }     
  bool isGuarded(const Address &addr) const;        
  bool isRangeLocked(void) const { return (analysisState == 2); }   
  bool isValid(OpCode opc) const { return (!op->isDead() && op->code() == opc); }   
};

class Heritage {
  enum heritage_flags {
    boundary_node = 1,      
    mark_node = 2,      
    merged_node = 4     
  };

  struct StackNode {
    enum {
      nonconstant_index = 1,
      multiequal = 2
    };
    Varnode *vn;        
    uintb offset;       
    uint4 traversals;       
    list<PcodeOp *>::const_iterator iter;   

    StackNode(Varnode *v,uintb o,uint4 trav) {
      vn = v;
      offset = o;
      iter = v->beginDescend();
      traversals = trav;
    }
  };

  Funcdata *fd;             
  LocationMap globaldisjoint;   
  LocationMap disjoint;     
  vector<vector<FlowBlock *> > domchild; 
  vector<vector<FlowBlock *> > augment; 
  vector<uint4> flags;      
  vector<int4> depth;       
  int4 maxdepth;        
  int4 pass;            

  PriorityQueue pq;     
  vector<FlowBlock *> merge;    
  vector<HeritageInfo> infolist; 
  list<LoadGuard> loadGuard;    
  list<LoadGuard> storeGuard;   
  vector<PcodeOp *> loadCopyOps;    
  void clearInfoList(void);  

  HeritageInfo *getInfo(AddrSpace *spc) { return &(infolist[spc->getIndex()]); }

  const HeritageInfo *getInfo(AddrSpace *spc) const { return &(infolist[spc->getIndex()]); }

  void splitJoinLevel(vector<Varnode *> &lastcombo,vector<Varnode *> &nextlev,JoinRecord *joinrec);
  void splitJoinRead(Varnode *vn,JoinRecord *joinrec);
  void splitJoinWrite(Varnode *vn,JoinRecord *joinrec);
  void floatExtensionRead(Varnode *vn,JoinRecord *joinrec);
  void floatExtensionWrite(Varnode *vn,JoinRecord *joinrec);
  void processJoins(void);
  void buildADT(void);      
  int4 collect(Address addr,int4 size,vector<Varnode *> &read,vector<Varnode *> &write,vector<Varnode *> &input) const;
  bool callOpIndirectEffect(const Address &addr,int4 size,PcodeOp *op) const;
  Varnode *normalizeReadSize(Varnode *vn,const Address &addr,int4 size);
  Varnode *normalizeWriteSize(Varnode *vn,const Address &addr,int4 size);
  Varnode *concatPieces(const vector<Varnode *> &vnlist,PcodeOp *insertop,Varnode *finalvn);
  void splitPieces(const vector<Varnode *> &vnlist,PcodeOp *insertop,const Address &addr,int4 size,Varnode *startvn);
  void findAddressForces(vector<PcodeOp *> &copySinks,vector<PcodeOp *> &forces);
  void propagateCopyAway(PcodeOp *op);
  void handleNewLoadCopies(void);
  void analyzeNewLoadGuards(void);
  void generateLoadGuard(StackNode &node,PcodeOp *op,AddrSpace *spc);
  void generateStoreGuard(StackNode &node,PcodeOp *op,AddrSpace *spc);
  bool protectFreeStores(AddrSpace *spc,vector<PcodeOp *> &freeStores);
  bool discoverIndexedStackPointers(AddrSpace *spc,vector<PcodeOp *> &freeStores,bool checkFreeStores);
  void reprocessFreeStores(AddrSpace *spc,vector<PcodeOp *> &freeStores);
  void guard(const Address &addr,int4 size,vector<Varnode *> &read,vector<Varnode *> &write,vector<Varnode *> &inputvars);
  void guardInput(const Address &addr,int4 size,vector<Varnode *> &input);
  void guardCallOverlappingInput(FuncCallSpecs *fc,const Address &addr,const Address &transAddr,int4 size);
  void guardCalls(uint4 flags,const Address &addr,int4 size,vector<Varnode *> &write);
  void guardStores(const Address &addr,int4 size,vector<Varnode *> &write);
  void guardLoads(uint4 flags,const Address &addr,int4 size,vector<Varnode *> &write);
  void guardReturns(uint4 flags,const Address &addr,int4 size,vector<Varnode *> &write);
  static void buildRefinement(vector<int4> &refine,const Address &addr,int4 size,const vector<Varnode *> &vnlist);
  void splitByRefinement(Varnode *vn,const Address &addr,const vector<int4> &refine,vector<Varnode *> &split);
  void refineRead(Varnode *vn,const Address &addr,const vector<int4> &refine,vector<Varnode *> &newvn);
  void refineWrite(Varnode *vn,const Address &addr,const vector<int4> &refine,vector<Varnode *> &newvn);
  void refineInput(Varnode *vn,const Address &addr,const vector<int4> &refine,vector<Varnode *> &newvn);
  void remove13Refinement(vector<int4> &refine);
  bool refinement(const Address &addr,int4 size,const vector<Varnode *> &readvars,const vector<Varnode *> &writevars,const vector<Varnode *> &inputvars);
  void visitIncr(FlowBlock *qnode,FlowBlock *vnode);
  void calcMultiequals(const vector<Varnode *> &write);
  void renameRecurse(BlockBasic *bl,VariableStack &varstack);
  void bumpDeadcodeDelay(Varnode *vn);
  void placeMultiequals(void);
  void rename(void);
public:
  Heritage(Funcdata *data); 

  int4 heritagePass(const Address &addr) const { return globaldisjoint.findPass(addr); }
  int4 numHeritagePasses(AddrSpace *spc) const;
  void seenDeadCode(AddrSpace *spc); 
  int4 getDeadCodeDelay(AddrSpace *spc) const; 
  void setDeadCodeDelay(AddrSpace *spc,int4 delay); 
  bool deadRemovalAllowed(AddrSpace *spc) const;    
  bool deadRemovalAllowedSeen(AddrSpace *spc);
  void buildInfoList(void);                     
  void forceRestructure(void) { maxdepth = -1; }    
  void clear(void);                 
  void heritage(void);                  
  const list<LoadGuard> &getLoadGuards(void) const { return loadGuard; }    
  const list<LoadGuard> &getStoreGuards(void) const { return storeGuard; }  
  const LoadGuard *getStoreGuard(PcodeOp *op) const;    
};

#endif