blockaction.hh

Go to the documentation of this file.

/* ###
 * 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.
 */
#ifndef __BLOCK_ACTION__
#define __BLOCK_ACTION__


#include "action.hh"

class FloatingEdge {
  FlowBlock *top;       
  FlowBlock *bottom;        
public:
  FloatingEdge(FlowBlock *t,FlowBlock *b) { top = t; bottom = b; }  
  FlowBlock *getTop(void) const { return top; }         
  FlowBlock *getBottom(void) const { return bottom; }       
  FlowBlock *getCurrentEdge(int4 &outedge,FlowBlock *graph);    
};

class LoopBody {
  FlowBlock *head;      
  vector<FlowBlock *> tails;    
  int4 depth;           
  int4 uniquecount;     
  FlowBlock *exitblock;     
  list<FloatingEdge> exitedges; 
  LoopBody *immed_container;    
  void extendToContainer(const LoopBody &container,vector<FlowBlock *> &body) const;
public:
  LoopBody(FlowBlock *h) { head=h; immed_container = (LoopBody *)0; depth=0; }  
  FlowBlock *getHead(void) const { return head; }           
  FlowBlock *getCurrentBounds(FlowBlock **top,FlowBlock *graph);    
  void addTail(FlowBlock *bl) { tails.push_back(bl); }          
  FlowBlock *getExitBlock(void) const { return exitblock; }     
  void findBase(vector<FlowBlock *> &body);             
  void extend(vector<FlowBlock *> &body) const;             
  void findExit(const vector<FlowBlock *> &body);           
  void orderTails(void);                        
  void labelExitEdges(const vector<FlowBlock *> &body);         
  void labelContainments(const vector<FlowBlock *> &body,const vector<LoopBody *> &looporder);
  void emitLikelyEdges(list<FloatingEdge> &likely,FlowBlock *graph);    
  void setExitMarks(FlowBlock *graph);                  
  void clearExitMarks(FlowBlock *graph);                
  bool operator<(const LoopBody &op2) const { return (depth > op2.depth); } 
  static void mergeIdenticalHeads(vector<LoopBody *> &looporder);   
  static bool compare_ends(LoopBody *a,LoopBody *b);            
  static int4 compare_head(LoopBody *a,FlowBlock *looptop);     
  static LoopBody *find(FlowBlock *looptop,const vector<LoopBody *> &looporder);    
  static void clearMarks(vector<FlowBlock *> &body);            
};

class TraceDAG {

  struct BlockTrace;

  struct BranchPoint {
    BranchPoint *parent;    
    int4 pathout;       
    FlowBlock *top;     
    vector<BlockTrace *> paths; 
    int4 depth;         
    bool ismark;        
    void createTraces(void);    
  public:
    void markPath(void);    
    int4 distance(BranchPoint *op2);    
    FlowBlock *getPathStart(int4 i);    
    BranchPoint(void);      
    BranchPoint(BlockTrace *parenttrace);   
    ~BranchPoint(void);     
  };

  struct BlockTrace {
    enum {
      f_active = 1,     
      f_terminal = 2        
    };
    uint4 flags;        
    BranchPoint *top;       
    int4 pathout;       
    FlowBlock *bottom;      
    FlowBlock *destnode;    
    int4 edgelump;      
    list<BlockTrace *>::iterator activeiter; 
    BranchPoint *derivedbp; 
  public:
    BlockTrace(BranchPoint *t,int4 po,int4 eo);     
    BlockTrace(BranchPoint *root,int4 po,FlowBlock *bl);    
    bool isActive(void) const { return ((flags & f_active)!=0); }   
    bool isTerminal(void) const { return ((flags & f_terminal)!=0); }   
  };

  struct BadEdgeScore {
    FlowBlock *exitproto;   
    BlockTrace *trace;      
    int4 distance;      
    int4 terminal;      
    int4 siblingedge;       
    bool compareFinal(const BadEdgeScore &op2) const;   
    bool operator<(const BadEdgeScore &op2) const;  
  };

  list<FloatingEdge> &likelygoto;   
  vector<FlowBlock *> rootlist;     
  vector<BranchPoint *> branchlist; 
  int4 activecount;         
  int4 missedactivecount;       
  list<BlockTrace *> activetrace;   
  list<BlockTrace *>::iterator current_activeiter;  
  FlowBlock *finishblock;       
  void removeTrace(BlockTrace *trace);  
  void processExitConflict(list<BadEdgeScore>::iterator start,list<BadEdgeScore>::iterator end);
  BlockTrace *selectBadEdge(void);  
  void insertActive(BlockTrace *trace); 
  void removeActive(BlockTrace *trace); 
  bool checkOpen(BlockTrace *trace);    
  list<BlockTrace *>::iterator openBranch(BlockTrace *parent);  
  bool checkRetirement(BlockTrace *trace,FlowBlock *&exitblock);    
  list<BlockTrace *>::iterator retireBranch(BranchPoint *bp,FlowBlock *exitblock);
  void clearVisitCount(void);       
public:
  TraceDAG(list<FloatingEdge> &lg); 
  ~TraceDAG(void);          
  void addRoot(FlowBlock *root) { rootlist.push_back(root); }   
  void initialize(void);        
  void pushBranches(void);      
  void setFinishBlock(FlowBlock *bl) { finishblock = bl; }  
};

class CollapseStructure {
  bool finaltrace;              
  bool likelylistfull;              
  list<FloatingEdge> likelygoto;        
  list<FloatingEdge>::iterator likelyiter;  
  list<LoopBody> loopbody;          
  list<LoopBody>::iterator loopbodyiter;    
  BlockGraph &graph;                
  int4 dataflow_changecount;            
  bool checkSwitchSkips(FlowBlock *switchbl,FlowBlock *exitblock);
  void onlyReachableFromRoot(FlowBlock *root,vector<FlowBlock *> &body);
  int4 markExitsAsGotos(vector<FlowBlock *> &body); 
  bool clipExtraRoots(void);            
  void labelLoops(vector<LoopBody *> &looporder);   
  void orderLoopBodies(void);           
  bool updateLoopBody(void);            
  FlowBlock *selectGoto(void);          
  bool ruleBlockGoto(FlowBlock *bl);        
  bool ruleBlockCat(FlowBlock *bl);     
  bool ruleBlockOr(FlowBlock *bl);      
  bool ruleBlockProperIf(FlowBlock *bl);    
  bool ruleBlockIfElse(FlowBlock *bl);      
  bool ruleBlockIfNoExit(FlowBlock *bl);    
  bool ruleBlockWhileDo(FlowBlock *bl);     
  bool ruleBlockDoWhile(FlowBlock *bl);     
  bool ruleBlockInfLoop(FlowBlock *bl);     
  bool ruleBlockSwitch(FlowBlock *bl);      
  bool ruleCaseFallthru(FlowBlock *bl);     
  int4 collapseInternal(FlowBlock *targetbl);   
  void collapseConditions(void);        
public:
  CollapseStructure(BlockGraph &g);     
  int4 getChangeCount(void) const { return dataflow_changecount; }  
  void collapseAll(void);           
};

class ConditionalJoin {
  struct MergePair {
    Varnode *side1;     
    Varnode *side2;     
    MergePair(Varnode *s1,Varnode *s2) { side1 = s1; side2 = s2; }  
    bool operator<(const MergePair &op2) const;             
  };
  Funcdata &data;           
  BlockBasic *block1;           
  BlockBasic *block2;           
  BlockBasic *exita;            
  BlockBasic *exitb;            
  int4 a_in1;               
  int4 a_in2;               
  int4 b_in1;               
  int4 b_in2;               
  PcodeOp *cbranch1;            
  PcodeOp *cbranch2;            
  BlockBasic *joinblock;        
  map<MergePair,Varnode *> mergeneed;   
  bool findDups(void);          
  void checkExitBlock(BlockBasic *exit,int4 in1,int4 in2);
  void cutDownMultiequals(BlockBasic *exit,int4 in1,int4 in2);
  void setupMultiequals(void);      
  void moveCbranch(void);       //< Move one of the duplicated CBRANCHs into the new \b joinblock
public:
  ConditionalJoin(Funcdata &fd) : data(fd) { }  
  bool match(BlockBasic *b1,BlockBasic *b2);    
  void execute(void);               
  void clear(void);             
};

class ActionNormalizeBranches : public Action {
public:
  ActionNormalizeBranches(const string &g) : Action(0,"normalizebranches",g) {} 
  virtual Action *clone(const ActionGroupList &grouplist) const {
    if (!grouplist.contains(getGroup())) return (Action *)0;
    return new ActionNormalizeBranches(getGroup());
  }
  virtual int4 apply(Funcdata &data);
};

class ActionPreferComplement : public Action {
public:
  ActionPreferComplement(const string &g) : Action(0,"prefercomplement",g) {}   
  virtual Action *clone(const ActionGroupList &grouplist) const {
    if (!grouplist.contains(getGroup())) return (Action *)0;
    return new ActionPreferComplement(getGroup());
  }
  virtual int4 apply(Funcdata &data);
};

class ActionBlockStructure : public Action {
public:
  ActionBlockStructure(const string &g) : Action(0,"blockstructure",g) {}   
  virtual Action *clone(const ActionGroupList &grouplist) const {
    if (!grouplist.contains(getGroup())) return (Action *)0;
    return new ActionBlockStructure(getGroup());
  }
  virtual int4 apply(Funcdata &data);
};

class ActionFinalStructure : public Action {
public:
  ActionFinalStructure(const string &g) : Action(0,"finalstructure",g) {}   
  virtual Action *clone(const ActionGroupList &grouplist) const {
    if (!grouplist.contains(getGroup())) return (Action *)0;
    return new ActionFinalStructure(getGroup());
  }
  virtual int4 apply(Funcdata &data);
};

class ActionReturnSplit : public Action {
  static void gatherReturnGotos(FlowBlock *parent,vector<FlowBlock *> &vec);
  static bool isSplittable(BlockBasic *b);      
public:
  ActionReturnSplit(const string &g) : Action(0,"returnsplit",g) {}     
  virtual Action *clone(const ActionGroupList &grouplist) const {
    if (!grouplist.contains(getGroup())) return (Action *)0;
    return new ActionReturnSplit(getGroup());
  }
  virtual int4 apply(Funcdata &data);
};

class ActionNodeJoin : public Action {
public:
  ActionNodeJoin(const string &g) : Action(0,"nodejoin",g) {}           
  virtual Action *clone(const ActionGroupList &grouplist) const {
    if (!grouplist.contains(getGroup())) return (Action *)0;
    return new ActionNodeJoin(getGroup());
  }
  virtual int4 apply(Funcdata &data);
};

#endif