Update copyright to LGPL on all files
[dyninst.git] / depGraphAPI / src / analyzeFDG.h
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 #ifndef CONTROLFLOWFIXER_H_
33 #define CONTROLFLOWFIXER_H_
34
35 #include <map>
36
37 #include "Node.h"
38 #include "FDG.h"
39
40 #include "Operation.h"
41
42 class BPatch_basicBlock;
43 class BPatch_function;
44
45 namespace Dyninst {
46 namespace DepGraphAPI {
47
48 /**
49  * The tool that creates the Flow Dependence Graph (FDG) associated with a given 
50  * function (currently BPatch_function).
51  */
52 class FDGAnalyzer {
53     friend class xPDGAnalyzer;
54 public:
55     typedef BPatch_basicBlock Block;
56     typedef std::set<Block*> BlockSet;
57     typedef Node::Ptr NodePtr;
58     typedef std::set<NodePtr> NodeSet;
59
60 private:
61     typedef BPatch_function Function;
62     typedef std::map<Block*, Node::Ptr> NodeMap;
63     typedef std::map<Block*, BlockSet> DependenceMap;
64   
65   /**
66    * Analyzed function
67    */
68   Function *func_;
69   
70   /**
71    * The Flow Dependence Graph
72    */
73   FDG::Ptr fdg;
74   
75   /**
76    * Maps each block A to a set of Block S which A depends on (for all S, A depends on S). 
77    */
78   DependenceMap blockToJumps;
79   
80   /**
81    * Set of blocks which ends with a jump/branch/return instruction.
82    */
83   BlockSet markedBlocks;
84
85 public:
86   FDGAnalyzer(Function *f) : func_(f) {};
87
88   /**
89    * Returns the FDG created by this intraFunctionCDGCreator object.
90    */
91   FDG::Ptr analyze();
92
93   ~FDGAnalyzer();
94
95 protected:
96   /**
97    * Returns true iff this operation is a return or exit operation.
98    */
99   static bool isReturnOp(const Dyninst::InstructionAPI::Operation& opType);
100
101   /**
102    * Returns true iff this operation is a branch operation (including jumps) such as jnz, jnle, etc.
103    */
104   static bool isBranchOp(const Dyninst::InstructionAPI::Operation& opType);
105   
106 private:
107   void createNodes(BlockSet &blocks);
108   Node::Ptr makeNode(NodeMap& nodeMap, Block* block);
109   void markBlocksWithJump(BlockSet &blocks);
110   void findDependencies(BlockSet &blocks);
111   void findBlocksRecursive(BlockSet& needThese, BlockSet& visited, Block* givenBlock);
112 };
113
114 };
115 };
116
117 #endif /* CONTROLFLOWFIXER_H_ */