Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 1 | //===- Local.cpp - Compute a local data structure graph for a function ----===// |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 2 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file was developed by the LLVM research group and is distributed under |
| 6 | // the University of Illinois Open Source License. See LICENSE.TXT for details. |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 7 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 9 | // |
| 10 | // Compute the local version of the data structure graph for a function. The |
| 11 | // external interface to this file is the DSGraph constructor. |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
Chris Lattner | 4dabb2c | 2004-07-07 06:32:21 +0000 | [diff] [blame] | 15 | #include "llvm/Analysis/DataStructure/DataStructure.h" |
| 16 | #include "llvm/Analysis/DataStructure/DSGraph.h" |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 17 | #include "llvm/Constants.h" |
| 18 | #include "llvm/DerivedTypes.h" |
Chris Lattner | 808a7ae | 2003-09-20 16:34:13 +0000 | [diff] [blame] | 19 | #include "llvm/Instructions.h" |
Chris Lattner | a07b72f | 2004-02-13 16:09:54 +0000 | [diff] [blame] | 20 | #include "llvm/Intrinsics.h" |
Chris Lattner | fa3711a | 2003-11-25 20:19:55 +0000 | [diff] [blame] | 21 | #include "llvm/Support/GetElementPtrTypeIterator.h" |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 22 | #include "llvm/Support/InstVisitor.h" |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 23 | #include "llvm/Target/TargetData.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 24 | #include "llvm/Support/CommandLine.h" |
| 25 | #include "llvm/Support/Debug.h" |
| 26 | #include "llvm/Support/Timer.h" |
Chris Lattner | 86a5484 | 2006-01-22 22:53:01 +0000 | [diff] [blame] | 27 | #include <iostream> |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 28 | |
| 29 | // FIXME: This should eventually be a FunctionPass that is automatically |
| 30 | // aggregated into a Pass. |
| 31 | // |
| 32 | #include "llvm/Module.h" |
| 33 | |
Chris Lattner | 9a92729 | 2003-11-12 23:11:14 +0000 | [diff] [blame] | 34 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 35 | |
Chris Lattner | 5d8925c | 2006-08-27 22:30:17 +0000 | [diff] [blame] | 36 | static RegisterPass<LocalDataStructures> |
Chris Lattner | 97f51a3 | 2002-07-27 01:12:15 +0000 | [diff] [blame] | 37 | X("datastructure", "Local Data Structure Analysis"); |
Chris Lattner | 97f51a3 | 2002-07-27 01:12:15 +0000 | [diff] [blame] | 38 | |
Chris Lattner | a190766 | 2003-11-13 03:10:49 +0000 | [diff] [blame] | 39 | static cl::opt<bool> |
Chris Lattner | f0431b0 | 2004-08-02 20:16:21 +0000 | [diff] [blame] | 40 | TrackIntegersAsPointers("dsa-track-integers", cl::Hidden, |
Chris Lattner | a190766 | 2003-11-13 03:10:49 +0000 | [diff] [blame] | 41 | cl::desc("If this is set, track integers as potential pointers")); |
Chris Lattner | a190766 | 2003-11-13 03:10:49 +0000 | [diff] [blame] | 42 | |
Andrew Lenharth | 1bce1fb | 2006-11-07 20:39:05 +0000 | [diff] [blame] | 43 | static cl::opt<bool> |
| 44 | IgnoreSetCC("dsa-ignore-setcc", cl::Hidden, |
| 45 | cl::desc("If this is set, do nothing at pointer comparisons")); |
| 46 | |
John Criswell | fa70052 | 2005-12-19 17:38:39 +0000 | [diff] [blame] | 47 | static cl::list<std::string> |
John Criswell | 61af913 | 2005-12-19 20:14:38 +0000 | [diff] [blame] | 48 | AllocList("dsa-alloc-list", |
John Criswell | fa70052 | 2005-12-19 17:38:39 +0000 | [diff] [blame] | 49 | cl::value_desc("list"), |
| 50 | cl::desc("List of functions that allocate memory from the heap"), |
John Criswell | 61af913 | 2005-12-19 20:14:38 +0000 | [diff] [blame] | 51 | cl::CommaSeparated, cl::Hidden); |
John Criswell | fa70052 | 2005-12-19 17:38:39 +0000 | [diff] [blame] | 52 | |
John Criswell | 3075160 | 2005-12-19 19:54:23 +0000 | [diff] [blame] | 53 | static cl::list<std::string> |
John Criswell | 61af913 | 2005-12-19 20:14:38 +0000 | [diff] [blame] | 54 | FreeList("dsa-free-list", |
John Criswell | 3075160 | 2005-12-19 19:54:23 +0000 | [diff] [blame] | 55 | cl::value_desc("list"), |
| 56 | cl::desc("List of functions that free memory from the heap"), |
John Criswell | 61af913 | 2005-12-19 20:14:38 +0000 | [diff] [blame] | 57 | cl::CommaSeparated, cl::Hidden); |
John Criswell | 3075160 | 2005-12-19 19:54:23 +0000 | [diff] [blame] | 58 | |
Chris Lattner | 9a92729 | 2003-11-12 23:11:14 +0000 | [diff] [blame] | 59 | namespace llvm { |
Chris Lattner | b106043 | 2002-11-07 05:20:53 +0000 | [diff] [blame] | 60 | namespace DS { |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 61 | // isPointerType - Return true if this type is big enough to hold a pointer. |
| 62 | bool isPointerType(const Type *Ty) { |
| 63 | if (isa<PointerType>(Ty)) |
| 64 | return true; |
Chris Lattner | a190766 | 2003-11-13 03:10:49 +0000 | [diff] [blame] | 65 | else if (TrackIntegersAsPointers && Ty->isPrimitiveType() &&Ty->isInteger()) |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 66 | return Ty->getPrimitiveSize() >= PointerSize; |
| 67 | return false; |
| 68 | } |
Chris Lattner | 9a92729 | 2003-11-12 23:11:14 +0000 | [diff] [blame] | 69 | }} |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 70 | |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 71 | using namespace DS; |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 72 | |
| 73 | namespace { |
Chris Lattner | 923fc05 | 2003-02-05 21:59:58 +0000 | [diff] [blame] | 74 | cl::opt<bool> |
| 75 | DisableDirectCallOpt("disable-direct-call-dsopt", cl::Hidden, |
| 76 | cl::desc("Disable direct call optimization in " |
| 77 | "DSGraph construction")); |
Chris Lattner | ca3f790 | 2003-02-08 20:18:39 +0000 | [diff] [blame] | 78 | cl::opt<bool> |
| 79 | DisableFieldSensitivity("disable-ds-field-sensitivity", cl::Hidden, |
| 80 | cl::desc("Disable field sensitivity in DSGraphs")); |
Chris Lattner | 923fc05 | 2003-02-05 21:59:58 +0000 | [diff] [blame] | 81 | |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 82 | //===--------------------------------------------------------------------===// |
| 83 | // GraphBuilder Class |
| 84 | //===--------------------------------------------------------------------===// |
| 85 | // |
| 86 | /// This class is the builder class that constructs the local data structure |
| 87 | /// graph by performing a single pass over the function in question. |
| 88 | /// |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 89 | class GraphBuilder : InstVisitor<GraphBuilder> { |
| 90 | DSGraph &G; |
Chris Lattner | 26c4fc3 | 2003-09-20 21:48:16 +0000 | [diff] [blame] | 91 | DSNodeHandle *RetNode; // Node that gets returned... |
Chris Lattner | 62482e5 | 2004-01-28 09:15:42 +0000 | [diff] [blame] | 92 | DSScalarMap &ScalarMap; |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 93 | std::list<DSCallSite> *FunctionCalls; |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 94 | |
| 95 | public: |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 96 | GraphBuilder(Function &f, DSGraph &g, DSNodeHandle &retNode, |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 97 | std::list<DSCallSite> &fc) |
Chris Lattner | 26c4fc3 | 2003-09-20 21:48:16 +0000 | [diff] [blame] | 98 | : G(g), RetNode(&retNode), ScalarMap(G.getScalarMap()), |
| 99 | FunctionCalls(&fc) { |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 100 | |
| 101 | // Create scalar nodes for all pointer arguments... |
Chris Lattner | a513fb1 | 2005-03-22 02:45:13 +0000 | [diff] [blame] | 102 | for (Function::arg_iterator I = f.arg_begin(), E = f.arg_end(); |
| 103 | I != E; ++I) |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 104 | if (isPointerType(I->getType())) |
| 105 | getValueDest(*I); |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 106 | |
Chris Lattner | 26c4fc3 | 2003-09-20 21:48:16 +0000 | [diff] [blame] | 107 | visit(f); // Single pass over the function |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 108 | } |
| 109 | |
Chris Lattner | 26c4fc3 | 2003-09-20 21:48:16 +0000 | [diff] [blame] | 110 | // GraphBuilder ctor for working on the globals graph |
| 111 | GraphBuilder(DSGraph &g) |
| 112 | : G(g), RetNode(0), ScalarMap(G.getScalarMap()), FunctionCalls(0) { |
| 113 | } |
| 114 | |
| 115 | void mergeInGlobalInitializer(GlobalVariable *GV); |
| 116 | |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 117 | private: |
| 118 | // Visitor functions, used to handle each instruction type we encounter... |
| 119 | friend class InstVisitor<GraphBuilder>; |
Chris Lattner | bd92b73 | 2003-06-19 21:15:11 +0000 | [diff] [blame] | 120 | void visitMallocInst(MallocInst &MI) { handleAlloc(MI, true); } |
| 121 | void visitAllocaInst(AllocaInst &AI) { handleAlloc(AI, false); } |
| 122 | void handleAlloc(AllocationInst &AI, bool isHeap); |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 123 | |
| 124 | void visitPHINode(PHINode &PN); |
Chris Lattner | 6e84bd7 | 2005-02-25 01:27:48 +0000 | [diff] [blame] | 125 | void visitSelectInst(SelectInst &SI); |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 126 | |
Chris Lattner | 5134006 | 2002-11-08 05:00:44 +0000 | [diff] [blame] | 127 | void visitGetElementPtrInst(User &GEP); |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 128 | void visitReturnInst(ReturnInst &RI); |
| 129 | void visitLoadInst(LoadInst &LI); |
| 130 | void visitStoreInst(StoreInst &SI); |
| 131 | void visitCallInst(CallInst &CI); |
Chris Lattner | 808a7ae | 2003-09-20 16:34:13 +0000 | [diff] [blame] | 132 | void visitInvokeInst(InvokeInst &II); |
Chris Lattner | 3267265 | 2005-03-05 19:04:31 +0000 | [diff] [blame] | 133 | void visitSetCondInst(SetCondInst &SCI); |
Vikram S. Adve | bac0622 | 2002-12-06 21:17:10 +0000 | [diff] [blame] | 134 | void visitFreeInst(FreeInst &FI); |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 135 | void visitCastInst(CastInst &CI); |
Chris Lattner | 878e521 | 2003-02-04 00:59:50 +0000 | [diff] [blame] | 136 | void visitInstruction(Instruction &I); |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 137 | |
Andrew Lenharth | 118c094 | 2006-11-03 17:43:19 +0000 | [diff] [blame] | 138 | bool visitIntrinsic(CallSite CS, Function* F); |
| 139 | bool visitExternal(CallSite CS, Function* F); |
Chris Lattner | 808a7ae | 2003-09-20 16:34:13 +0000 | [diff] [blame] | 140 | void visitCallSite(CallSite CS); |
Chris Lattner | 6b3e3cc | 2004-03-04 20:33:47 +0000 | [diff] [blame] | 141 | void visitVAArgInst(VAArgInst &I); |
Chris Lattner | 26c4fc3 | 2003-09-20 21:48:16 +0000 | [diff] [blame] | 142 | |
| 143 | void MergeConstantInitIntoNode(DSNodeHandle &NH, Constant *C); |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 144 | private: |
| 145 | // Helper functions used to implement the visitation functions... |
| 146 | |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 147 | /// createNode - Create a new DSNode, ensuring that it is properly added to |
| 148 | /// the graph. |
| 149 | /// |
Chris Lattner | bd92b73 | 2003-06-19 21:15:11 +0000 | [diff] [blame] | 150 | DSNode *createNode(const Type *Ty = 0) { |
| 151 | DSNode *N = new DSNode(Ty, &G); // Create the node |
Chris Lattner | e158b19 | 2003-06-16 12:08:18 +0000 | [diff] [blame] | 152 | if (DisableFieldSensitivity) { |
Chris Lattner | 2412a05 | 2004-05-23 21:14:09 +0000 | [diff] [blame] | 153 | // Create node handle referring to the old node so that it is |
| 154 | // immediately removed from the graph when the node handle is destroyed. |
| 155 | DSNodeHandle OldNNH = N; |
Chris Lattner | ca3f790 | 2003-02-08 20:18:39 +0000 | [diff] [blame] | 156 | N->foldNodeCompletely(); |
Chris Lattner | e158b19 | 2003-06-16 12:08:18 +0000 | [diff] [blame] | 157 | if (DSNode *FN = N->getForwardNode()) |
| 158 | N = FN; |
| 159 | } |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 160 | return N; |
| 161 | } |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 162 | |
Chris Lattner | c875f02 | 2002-11-03 21:27:48 +0000 | [diff] [blame] | 163 | /// setDestTo - Set the ScalarMap entry for the specified value to point to |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 164 | /// the specified destination. If the Value already points to a node, make |
| 165 | /// sure to merge the two destinations together. |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 166 | /// |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 167 | void setDestTo(Value &V, const DSNodeHandle &NH); |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 168 | |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 169 | /// getValueDest - Return the DSNode that the actual value points to. |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 170 | /// |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 171 | DSNodeHandle getValueDest(Value &V); |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 172 | |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 173 | /// getLink - This method is used to return the specified link in the |
| 174 | /// specified node if one exists. If a link does not already exist (it's |
Chris Lattner | 7e51c87 | 2002-10-31 06:52:26 +0000 | [diff] [blame] | 175 | /// null), then we create a new node, link it, then return it. |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 176 | /// |
Chris Lattner | 7e51c87 | 2002-10-31 06:52:26 +0000 | [diff] [blame] | 177 | DSNodeHandle &getLink(const DSNodeHandle &Node, unsigned Link = 0); |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 178 | }; |
| 179 | } |
| 180 | |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 181 | using namespace DS; |
| 182 | |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 183 | //===----------------------------------------------------------------------===// |
| 184 | // DSGraph constructor - Simply use the GraphBuilder to construct the local |
| 185 | // graph. |
Chris Lattner | f4f6227 | 2005-03-19 22:23:45 +0000 | [diff] [blame] | 186 | DSGraph::DSGraph(EquivalenceClasses<GlobalValue*> &ECs, const TargetData &td, |
| 187 | Function &F, DSGraph *GG) |
| 188 | : GlobalsGraph(GG), ScalarMap(ECs), TD(td) { |
Chris Lattner | 2a06886 | 2002-11-10 06:53:38 +0000 | [diff] [blame] | 189 | PrintAuxCalls = false; |
Chris Lattner | 3051419 | 2003-07-02 04:37:26 +0000 | [diff] [blame] | 190 | |
Bill Wendling | 5294fb0 | 2006-11-17 07:33:59 +0000 | [diff] [blame] | 191 | DOUT << " [Loc] Calculating graph for: " << F.getName() << "\n"; |
Chris Lattner | 3051419 | 2003-07-02 04:37:26 +0000 | [diff] [blame] | 192 | |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 193 | // Use the graph builder to construct the local version of the graph |
Chris Lattner | 26c4fc3 | 2003-09-20 21:48:16 +0000 | [diff] [blame] | 194 | GraphBuilder B(F, *this, ReturnNodes[&F], FunctionCalls); |
Chris Lattner | 4fe3461 | 2002-11-18 21:44:19 +0000 | [diff] [blame] | 195 | #ifndef NDEBUG |
| 196 | Timer::addPeakMemoryMeasurement(); |
| 197 | #endif |
Chris Lattner | 1a1a85d | 2003-02-14 04:55:58 +0000 | [diff] [blame] | 198 | |
Chris Lattner | c420ab6 | 2004-02-25 23:31:02 +0000 | [diff] [blame] | 199 | // If there are any constant globals referenced in this function, merge their |
| 200 | // initializers into the local graph from the globals graph. |
| 201 | if (ScalarMap.global_begin() != ScalarMap.global_end()) { |
| 202 | ReachabilityCloner RC(*this, *GG, 0); |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 203 | |
Chris Lattner | c420ab6 | 2004-02-25 23:31:02 +0000 | [diff] [blame] | 204 | for (DSScalarMap::global_iterator I = ScalarMap.global_begin(); |
| 205 | I != ScalarMap.global_end(); ++I) |
| 206 | if (GlobalVariable *GV = dyn_cast<GlobalVariable>(*I)) |
Chris Lattner | 76a9eb3 | 2004-03-03 23:00:19 +0000 | [diff] [blame] | 207 | if (!GV->isExternal() && GV->isConstant()) |
Chris Lattner | c420ab6 | 2004-02-25 23:31:02 +0000 | [diff] [blame] | 208 | RC.merge(ScalarMap[GV], GG->ScalarMap[GV]); |
| 209 | } |
| 210 | |
Chris Lattner | 394471f | 2003-01-23 22:05:33 +0000 | [diff] [blame] | 211 | markIncompleteNodes(DSGraph::MarkFormalArgs); |
Chris Lattner | 9651725 | 2002-11-09 20:55:24 +0000 | [diff] [blame] | 212 | |
| 213 | // Remove any nodes made dead due to merging... |
Chris Lattner | 394471f | 2003-01-23 22:05:33 +0000 | [diff] [blame] | 214 | removeDeadNodes(DSGraph::KeepUnreachableGlobals); |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 215 | } |
| 216 | |
| 217 | |
| 218 | //===----------------------------------------------------------------------===// |
| 219 | // Helper method implementations... |
| 220 | // |
| 221 | |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 222 | /// getValueDest - Return the DSNode that the actual value points to. |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 223 | /// |
Chris Lattner | 5134006 | 2002-11-08 05:00:44 +0000 | [diff] [blame] | 224 | DSNodeHandle GraphBuilder::getValueDest(Value &Val) { |
| 225 | Value *V = &Val; |
Chris Lattner | 82962de | 2004-11-03 18:51:26 +0000 | [diff] [blame] | 226 | if (isa<Constant>(V) && cast<Constant>(V)->isNullValue()) |
Chris Lattner | 5134006 | 2002-11-08 05:00:44 +0000 | [diff] [blame] | 227 | return 0; // Null doesn't point to anything, don't add to ScalarMap! |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 228 | |
Vikram S. Adve | bac0622 | 2002-12-06 21:17:10 +0000 | [diff] [blame] | 229 | DSNodeHandle &NH = ScalarMap[V]; |
Chris Lattner | 62c3a95 | 2004-10-30 04:22:45 +0000 | [diff] [blame] | 230 | if (!NH.isNull()) |
Vikram S. Adve | bac0622 | 2002-12-06 21:17:10 +0000 | [diff] [blame] | 231 | return NH; // Already have a node? Just return it... |
| 232 | |
| 233 | // Otherwise we need to create a new node to point to. |
| 234 | // Check first for constant expressions that must be traversed to |
| 235 | // extract the actual value. |
Reid Spencer | e840434 | 2004-07-18 00:18:30 +0000 | [diff] [blame] | 236 | DSNode* N; |
| 237 | if (GlobalValue* GV = dyn_cast<GlobalValue>(V)) { |
Chris Lattner | 48427b5 | 2005-03-20 01:18:00 +0000 | [diff] [blame] | 238 | // Create a new global node for this global variable. |
Reid Spencer | e840434 | 2004-07-18 00:18:30 +0000 | [diff] [blame] | 239 | N = createNode(GV->getType()->getElementType()); |
| 240 | N->addGlobal(GV); |
| 241 | } else if (Constant *C = dyn_cast<Constant>(V)) { |
| 242 | if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame^] | 243 | if (CE->isCast()) { |
Chris Lattner | a513fb1 | 2005-03-22 02:45:13 +0000 | [diff] [blame] | 244 | if (isa<PointerType>(CE->getOperand(0)->getType())) |
| 245 | NH = getValueDest(*CE->getOperand(0)); |
| 246 | else |
| 247 | NH = createNode()->setUnknownNodeMarker(); |
| 248 | } else if (CE->getOpcode() == Instruction::GetElementPtr) { |
Chris Lattner | 5134006 | 2002-11-08 05:00:44 +0000 | [diff] [blame] | 249 | visitGetElementPtrInst(*CE); |
Chris Lattner | 62482e5 | 2004-01-28 09:15:42 +0000 | [diff] [blame] | 250 | DSScalarMap::iterator I = ScalarMap.find(CE); |
Chris Lattner | 2cfbaaf | 2002-11-09 20:14:03 +0000 | [diff] [blame] | 251 | assert(I != ScalarMap.end() && "GEP didn't get processed right?"); |
Chris Lattner | 1e56c54 | 2003-02-09 23:04:12 +0000 | [diff] [blame] | 252 | NH = I->second; |
| 253 | } else { |
| 254 | // This returns a conservative unknown node for any unhandled ConstExpr |
Chris Lattner | bd92b73 | 2003-06-19 21:15:11 +0000 | [diff] [blame] | 255 | return NH = createNode()->setUnknownNodeMarker(); |
Chris Lattner | 5134006 | 2002-11-08 05:00:44 +0000 | [diff] [blame] | 256 | } |
Chris Lattner | 62c3a95 | 2004-10-30 04:22:45 +0000 | [diff] [blame] | 257 | if (NH.isNull()) { // (getelementptr null, X) returns null |
Chris Lattner | 1e56c54 | 2003-02-09 23:04:12 +0000 | [diff] [blame] | 258 | ScalarMap.erase(V); |
| 259 | return 0; |
| 260 | } |
| 261 | return NH; |
Chris Lattner | bd1d382 | 2004-10-16 18:19:26 +0000 | [diff] [blame] | 262 | } else if (isa<UndefValue>(C)) { |
| 263 | ScalarMap.erase(V); |
| 264 | return 0; |
Chris Lattner | 5134006 | 2002-11-08 05:00:44 +0000 | [diff] [blame] | 265 | } else { |
| 266 | assert(0 && "Unknown constant type!"); |
| 267 | } |
Reid Spencer | e840434 | 2004-07-18 00:18:30 +0000 | [diff] [blame] | 268 | N = createNode(); // just create a shadow node |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 269 | } else { |
| 270 | // Otherwise just create a shadow node |
Chris Lattner | bd92b73 | 2003-06-19 21:15:11 +0000 | [diff] [blame] | 271 | N = createNode(); |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 272 | } |
| 273 | |
Chris Lattner | efffdc9 | 2004-07-07 06:12:52 +0000 | [diff] [blame] | 274 | NH.setTo(N, 0); // Remember that we are pointing to it... |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 275 | return NH; |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 276 | } |
| 277 | |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 278 | |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 279 | /// getLink - This method is used to return the specified link in the |
| 280 | /// specified node if one exists. If a link does not already exist (it's |
| 281 | /// null), then we create a new node, link it, then return it. We must |
| 282 | /// specify the type of the Node field we are accessing so that we know what |
| 283 | /// type should be linked to if we need to create a new node. |
| 284 | /// |
Chris Lattner | 7e51c87 | 2002-10-31 06:52:26 +0000 | [diff] [blame] | 285 | DSNodeHandle &GraphBuilder::getLink(const DSNodeHandle &node, unsigned LinkNo) { |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 286 | DSNodeHandle &Node = const_cast<DSNodeHandle&>(node); |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 287 | DSNodeHandle &Link = Node.getLink(LinkNo); |
Chris Lattner | 62c3a95 | 2004-10-30 04:22:45 +0000 | [diff] [blame] | 288 | if (Link.isNull()) { |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 289 | // If the link hasn't been created yet, make and return a new shadow node |
Chris Lattner | bd92b73 | 2003-06-19 21:15:11 +0000 | [diff] [blame] | 290 | Link = createNode(); |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 291 | } |
| 292 | return Link; |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 293 | } |
| 294 | |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 295 | |
Chris Lattner | c875f02 | 2002-11-03 21:27:48 +0000 | [diff] [blame] | 296 | /// setDestTo - Set the ScalarMap entry for the specified value to point to the |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 297 | /// specified destination. If the Value already points to a node, make sure to |
| 298 | /// merge the two destinations together. |
| 299 | /// |
| 300 | void GraphBuilder::setDestTo(Value &V, const DSNodeHandle &NH) { |
Chris Lattner | 6b3e3cc | 2004-03-04 20:33:47 +0000 | [diff] [blame] | 301 | ScalarMap[&V].mergeWith(NH); |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 302 | } |
| 303 | |
| 304 | |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 305 | //===----------------------------------------------------------------------===// |
| 306 | // Specific instruction type handler implementations... |
| 307 | // |
| 308 | |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 309 | /// Alloca & Malloc instruction implementation - Simply create a new memory |
| 310 | /// object, pointing the scalar to it. |
| 311 | /// |
Chris Lattner | bd92b73 | 2003-06-19 21:15:11 +0000 | [diff] [blame] | 312 | void GraphBuilder::handleAlloc(AllocationInst &AI, bool isHeap) { |
| 313 | DSNode *N = createNode(); |
| 314 | if (isHeap) |
| 315 | N->setHeapNodeMarker(); |
| 316 | else |
| 317 | N->setAllocaNodeMarker(); |
| 318 | setDestTo(AI, N); |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 319 | } |
| 320 | |
| 321 | // PHINode - Make the scalar for the PHI node point to all of the things the |
| 322 | // incoming values point to... which effectively causes them to be merged. |
| 323 | // |
| 324 | void GraphBuilder::visitPHINode(PHINode &PN) { |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 325 | if (!isPointerType(PN.getType())) return; // Only pointer PHIs |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 326 | |
Chris Lattner | c875f02 | 2002-11-03 21:27:48 +0000 | [diff] [blame] | 327 | DSNodeHandle &PNDest = ScalarMap[&PN]; |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 328 | for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 329 | PNDest.mergeWith(getValueDest(*PN.getIncomingValue(i))); |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 330 | } |
| 331 | |
Chris Lattner | 6e84bd7 | 2005-02-25 01:27:48 +0000 | [diff] [blame] | 332 | void GraphBuilder::visitSelectInst(SelectInst &SI) { |
| 333 | if (!isPointerType(SI.getType())) return; // Only pointer Selects |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 334 | |
Chris Lattner | 6e84bd7 | 2005-02-25 01:27:48 +0000 | [diff] [blame] | 335 | DSNodeHandle &Dest = ScalarMap[&SI]; |
| 336 | Dest.mergeWith(getValueDest(*SI.getOperand(1))); |
| 337 | Dest.mergeWith(getValueDest(*SI.getOperand(2))); |
| 338 | } |
| 339 | |
Chris Lattner | 3267265 | 2005-03-05 19:04:31 +0000 | [diff] [blame] | 340 | void GraphBuilder::visitSetCondInst(SetCondInst &SCI) { |
| 341 | if (!isPointerType(SCI.getOperand(0)->getType()) || |
| 342 | isa<ConstantPointerNull>(SCI.getOperand(1))) return; // Only pointers |
Andrew Lenharth | 1bce1fb | 2006-11-07 20:39:05 +0000 | [diff] [blame] | 343 | if(!IgnoreSetCC) |
| 344 | ScalarMap[SCI.getOperand(0)].mergeWith(getValueDest(*SCI.getOperand(1))); |
Chris Lattner | 3267265 | 2005-03-05 19:04:31 +0000 | [diff] [blame] | 345 | } |
| 346 | |
| 347 | |
Chris Lattner | 5134006 | 2002-11-08 05:00:44 +0000 | [diff] [blame] | 348 | void GraphBuilder::visitGetElementPtrInst(User &GEP) { |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 349 | DSNodeHandle Value = getValueDest(*GEP.getOperand(0)); |
Chris Lattner | 753b113 | 2005-02-24 19:55:31 +0000 | [diff] [blame] | 350 | if (Value.isNull()) |
| 351 | Value = createNode(); |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 352 | |
Chris Lattner | 179bc7d | 2003-11-14 17:09:46 +0000 | [diff] [blame] | 353 | // As a special case, if all of the index operands of GEP are constant zeros, |
| 354 | // handle this just like we handle casts (ie, don't do much). |
| 355 | bool AllZeros = true; |
| 356 | for (unsigned i = 1, e = GEP.getNumOperands(); i != e; ++i) |
| 357 | if (GEP.getOperand(i) != |
| 358 | Constant::getNullValue(GEP.getOperand(i)->getType())) { |
| 359 | AllZeros = false; |
| 360 | break; |
| 361 | } |
| 362 | |
| 363 | // If all of the indices are zero, the result points to the operand without |
| 364 | // applying the type. |
Chris Lattner | 0c9707a | 2005-03-18 23:18:20 +0000 | [diff] [blame] | 365 | if (AllZeros || (!Value.isNull() && |
| 366 | Value.getNode()->isNodeCompletelyFolded())) { |
Chris Lattner | 179bc7d | 2003-11-14 17:09:46 +0000 | [diff] [blame] | 367 | setDestTo(GEP, Value); |
| 368 | return; |
| 369 | } |
| 370 | |
| 371 | |
Chris Lattner | 8f0a16e | 2002-10-31 05:45:02 +0000 | [diff] [blame] | 372 | const PointerType *PTy = cast<PointerType>(GEP.getOperand(0)->getType()); |
| 373 | const Type *CurTy = PTy->getElementType(); |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 374 | |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 375 | if (Value.getNode()->mergeTypeInfo(CurTy, Value.getOffset())) { |
| 376 | // If the node had to be folded... exit quickly |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 377 | setDestTo(GEP, Value); // GEP result points to folded node |
Chris Lattner | 8f0a16e | 2002-10-31 05:45:02 +0000 | [diff] [blame] | 378 | return; |
| 379 | } |
| 380 | |
Chris Lattner | 15869aa | 2003-11-02 22:27:28 +0000 | [diff] [blame] | 381 | const TargetData &TD = Value.getNode()->getTargetData(); |
| 382 | |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 383 | #if 0 |
Chris Lattner | 8f0a16e | 2002-10-31 05:45:02 +0000 | [diff] [blame] | 384 | // Handle the pointer index specially... |
| 385 | if (GEP.getNumOperands() > 1 && |
Chris Lattner | 28977af | 2004-04-05 01:30:19 +0000 | [diff] [blame] | 386 | (!isa<Constant>(GEP.getOperand(1)) || |
| 387 | !cast<Constant>(GEP.getOperand(1))->isNullValue())) { |
Chris Lattner | 8f0a16e | 2002-10-31 05:45:02 +0000 | [diff] [blame] | 388 | |
| 389 | // If we already know this is an array being accessed, don't do anything... |
| 390 | if (!TopTypeRec.isArray) { |
| 391 | TopTypeRec.isArray = true; |
| 392 | |
| 393 | // If we are treating some inner field pointer as an array, fold the node |
| 394 | // up because we cannot handle it right. This can come because of |
| 395 | // something like this: &((&Pt->X)[1]) == &Pt->Y |
| 396 | // |
| 397 | if (Value.getOffset()) { |
| 398 | // Value is now the pointer we want to GEP to be... |
| 399 | Value.getNode()->foldNodeCompletely(); |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 400 | setDestTo(GEP, Value); // GEP result points to folded node |
Chris Lattner | 8f0a16e | 2002-10-31 05:45:02 +0000 | [diff] [blame] | 401 | return; |
| 402 | } else { |
| 403 | // This is a pointer to the first byte of the node. Make sure that we |
| 404 | // are pointing to the outter most type in the node. |
| 405 | // FIXME: We need to check one more case here... |
| 406 | } |
| 407 | } |
| 408 | } |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 409 | #endif |
Chris Lattner | 8f0a16e | 2002-10-31 05:45:02 +0000 | [diff] [blame] | 410 | |
| 411 | // All of these subscripts are indexing INTO the elements we have... |
Chris Lattner | 26c4fc3 | 2003-09-20 21:48:16 +0000 | [diff] [blame] | 412 | unsigned Offset = 0; |
Chris Lattner | fa3711a | 2003-11-25 20:19:55 +0000 | [diff] [blame] | 413 | for (gep_type_iterator I = gep_type_begin(GEP), E = gep_type_end(GEP); |
| 414 | I != E; ++I) |
| 415 | if (const StructType *STy = dyn_cast<StructType>(*I)) { |
Andrew Lenharth | 118c094 | 2006-11-03 17:43:19 +0000 | [diff] [blame] | 416 | const ConstantInt* CUI = cast<ConstantInt>(I.getOperand()); |
| 417 | unsigned FieldNo = |
| 418 | CUI->getType()->isSigned() ? CUI->getSExtValue() : CUI->getZExtValue(); |
Chris Lattner | 507bdf9 | 2005-01-12 04:51:37 +0000 | [diff] [blame] | 419 | Offset += (unsigned)TD.getStructLayout(STy)->MemberOffsets[FieldNo]; |
Reid Spencer | 3ed469c | 2006-11-02 20:25:50 +0000 | [diff] [blame] | 420 | } else if (isa<PointerType>(*I)) { |
Chris Lattner | 82e9d72 | 2004-03-01 19:02:54 +0000 | [diff] [blame] | 421 | if (!isa<Constant>(I.getOperand()) || |
| 422 | !cast<Constant>(I.getOperand())->isNullValue()) |
| 423 | Value.getNode()->setArrayMarker(); |
Chris Lattner | fa3711a | 2003-11-25 20:19:55 +0000 | [diff] [blame] | 424 | } |
| 425 | |
| 426 | |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 427 | #if 0 |
Chris Lattner | fa3711a | 2003-11-25 20:19:55 +0000 | [diff] [blame] | 428 | if (const SequentialType *STy = cast<SequentialType>(*I)) { |
| 429 | CurTy = STy->getElementType(); |
Jim Laskey | 978b35e | 2006-10-23 14:39:22 +0000 | [diff] [blame] | 430 | if (ConstantInt *CS = dyn_cast<ConstantInt>(GEP.getOperand(i))) { |
Andrew Lenharth | 118c094 | 2006-11-03 17:43:19 +0000 | [diff] [blame] | 431 | Offset += |
| 432 | (CS->getType()->isSigned() ? CS->getSExtValue() : CS->getZExtValue()) |
| 433 | * TD.getTypeSize(CurTy); |
Chris Lattner | e03f32b | 2002-10-02 06:24:36 +0000 | [diff] [blame] | 434 | } else { |
| 435 | // Variable index into a node. We must merge all of the elements of the |
| 436 | // sequential type here. |
| 437 | if (isa<PointerType>(STy)) |
| 438 | std::cerr << "Pointer indexing not handled yet!\n"; |
| 439 | else { |
| 440 | const ArrayType *ATy = cast<ArrayType>(STy); |
| 441 | unsigned ElSize = TD.getTypeSize(CurTy); |
| 442 | DSNode *N = Value.getNode(); |
| 443 | assert(N && "Value must have a node!"); |
| 444 | unsigned RawOffset = Offset+Value.getOffset(); |
| 445 | |
| 446 | // Loop over all of the elements of the array, merging them into the |
Misha Brukman | 2f2d065 | 2003-09-11 18:14:24 +0000 | [diff] [blame] | 447 | // zeroth element. |
Chris Lattner | e03f32b | 2002-10-02 06:24:36 +0000 | [diff] [blame] | 448 | for (unsigned i = 1, e = ATy->getNumElements(); i != e; ++i) |
| 449 | // Merge all of the byte components of this array element |
| 450 | for (unsigned j = 0; j != ElSize; ++j) |
| 451 | N->mergeIndexes(RawOffset+j, RawOffset+i*ElSize+j); |
| 452 | } |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 453 | } |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 454 | } |
Chris Lattner | fa3711a | 2003-11-25 20:19:55 +0000 | [diff] [blame] | 455 | #endif |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 456 | |
| 457 | // Add in the offset calculated... |
| 458 | Value.setOffset(Value.getOffset()+Offset); |
| 459 | |
Sumant Kowshik | 8a3802d | 2005-12-06 18:04:30 +0000 | [diff] [blame] | 460 | // Check the offset |
| 461 | DSNode *N = Value.getNode(); |
| 462 | if (N && |
| 463 | !N->isNodeCompletelyFolded() && |
| 464 | (N->getSize() != 0 || Offset != 0) && |
| 465 | !N->isForwarding()) { |
| 466 | if ((Offset >= N->getSize()) || int(Offset) < 0) { |
| 467 | // Accessing offsets out of node size range |
| 468 | // This is seen in the "magic" struct in named (from bind), where the |
| 469 | // fourth field is an array of length 0, presumably used to create struct |
| 470 | // instances of different sizes |
| 471 | |
| 472 | // Collapse the node since its size is now variable |
| 473 | N->foldNodeCompletely(); |
| 474 | } |
| 475 | } |
| 476 | |
| 477 | // Value is now the pointer we want to GEP to be... |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 478 | setDestTo(GEP, Value); |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 479 | } |
| 480 | |
| 481 | void GraphBuilder::visitLoadInst(LoadInst &LI) { |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 482 | DSNodeHandle Ptr = getValueDest(*LI.getOperand(0)); |
Chris Lattner | 6e84bd7 | 2005-02-25 01:27:48 +0000 | [diff] [blame] | 483 | if (Ptr.isNull()) |
| 484 | Ptr = createNode(); |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 485 | |
| 486 | // Make that the node is read from... |
Chris Lattner | bd92b73 | 2003-06-19 21:15:11 +0000 | [diff] [blame] | 487 | Ptr.getNode()->setReadMarker(); |
Chris Lattner | 8f0a16e | 2002-10-31 05:45:02 +0000 | [diff] [blame] | 488 | |
| 489 | // Ensure a typerecord exists... |
Chris Lattner | 088b639 | 2003-03-03 17:13:31 +0000 | [diff] [blame] | 490 | Ptr.getNode()->mergeTypeInfo(LI.getType(), Ptr.getOffset(), false); |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 491 | |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 492 | if (isPointerType(LI.getType())) |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 493 | setDestTo(LI, getLink(Ptr)); |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 494 | } |
| 495 | |
| 496 | void GraphBuilder::visitStoreInst(StoreInst &SI) { |
Chris Lattner | 8f0a16e | 2002-10-31 05:45:02 +0000 | [diff] [blame] | 497 | const Type *StoredTy = SI.getOperand(0)->getType(); |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 498 | DSNodeHandle Dest = getValueDest(*SI.getOperand(1)); |
Chris Lattner | 6b3e3cc | 2004-03-04 20:33:47 +0000 | [diff] [blame] | 499 | if (Dest.isNull()) return; |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 500 | |
Vikram S. Adve | bac0622 | 2002-12-06 21:17:10 +0000 | [diff] [blame] | 501 | // Mark that the node is written to... |
Chris Lattner | bd92b73 | 2003-06-19 21:15:11 +0000 | [diff] [blame] | 502 | Dest.getNode()->setModifiedMarker(); |
Chris Lattner | 8f0a16e | 2002-10-31 05:45:02 +0000 | [diff] [blame] | 503 | |
Chris Lattner | 26c4fc3 | 2003-09-20 21:48:16 +0000 | [diff] [blame] | 504 | // Ensure a type-record exists... |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 505 | Dest.getNode()->mergeTypeInfo(StoredTy, Dest.getOffset()); |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 506 | |
| 507 | // Avoid adding edges from null, or processing non-"pointer" stores |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 508 | if (isPointerType(StoredTy)) |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 509 | Dest.addEdgeTo(getValueDest(*SI.getOperand(0))); |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 510 | } |
| 511 | |
| 512 | void GraphBuilder::visitReturnInst(ReturnInst &RI) { |
Chris Lattner | 9267329 | 2002-11-02 00:13:20 +0000 | [diff] [blame] | 513 | if (RI.getNumOperands() && isPointerType(RI.getOperand(0)->getType())) |
Chris Lattner | 26c4fc3 | 2003-09-20 21:48:16 +0000 | [diff] [blame] | 514 | RetNode->mergeWith(getValueDest(*RI.getOperand(0))); |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 515 | } |
| 516 | |
Chris Lattner | 6b3e3cc | 2004-03-04 20:33:47 +0000 | [diff] [blame] | 517 | void GraphBuilder::visitVAArgInst(VAArgInst &I) { |
Andrew Lenharth | 558bc88 | 2005-06-18 18:34:52 +0000 | [diff] [blame] | 518 | //FIXME: also updates the argument |
Chris Lattner | 6b3e3cc | 2004-03-04 20:33:47 +0000 | [diff] [blame] | 519 | DSNodeHandle Ptr = getValueDest(*I.getOperand(0)); |
| 520 | if (Ptr.isNull()) return; |
| 521 | |
| 522 | // Make that the node is read from. |
| 523 | Ptr.getNode()->setReadMarker(); |
| 524 | |
Chris Lattner | 62c3a95 | 2004-10-30 04:22:45 +0000 | [diff] [blame] | 525 | // Ensure a type record exists. |
| 526 | DSNode *PtrN = Ptr.getNode(); |
| 527 | PtrN->mergeTypeInfo(I.getType(), Ptr.getOffset(), false); |
Chris Lattner | 6b3e3cc | 2004-03-04 20:33:47 +0000 | [diff] [blame] | 528 | |
| 529 | if (isPointerType(I.getType())) |
| 530 | setDestTo(I, getLink(Ptr)); |
| 531 | } |
| 532 | |
| 533 | |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 534 | void GraphBuilder::visitCallInst(CallInst &CI) { |
Chris Lattner | 808a7ae | 2003-09-20 16:34:13 +0000 | [diff] [blame] | 535 | visitCallSite(&CI); |
| 536 | } |
| 537 | |
| 538 | void GraphBuilder::visitInvokeInst(InvokeInst &II) { |
| 539 | visitCallSite(&II); |
| 540 | } |
| 541 | |
Andrew Lenharth | 118c094 | 2006-11-03 17:43:19 +0000 | [diff] [blame] | 542 | /// returns true if the intrinsic is handled |
| 543 | bool GraphBuilder::visitIntrinsic(CallSite CS, Function *F) { |
| 544 | switch (F->getIntrinsicID()) { |
| 545 | case Intrinsic::vastart: |
| 546 | getValueDest(*CS.getInstruction()).getNode()->setAllocaNodeMarker(); |
| 547 | return true; |
| 548 | case Intrinsic::vacopy: |
| 549 | getValueDest(*CS.getInstruction()). |
| 550 | mergeWith(getValueDest(**(CS.arg_begin()))); |
| 551 | return true; |
| 552 | case Intrinsic::vaend: |
| 553 | case Intrinsic::dbg_func_start: |
| 554 | case Intrinsic::dbg_region_end: |
| 555 | case Intrinsic::dbg_stoppoint: |
| 556 | return true; // noop |
| 557 | case Intrinsic::memcpy_i32: |
| 558 | case Intrinsic::memcpy_i64: |
| 559 | case Intrinsic::memmove_i32: |
| 560 | case Intrinsic::memmove_i64: { |
| 561 | // Merge the first & second arguments, and mark the memory read and |
| 562 | // modified. |
| 563 | DSNodeHandle RetNH = getValueDest(**CS.arg_begin()); |
| 564 | RetNH.mergeWith(getValueDest(**(CS.arg_begin()+1))); |
| 565 | if (DSNode *N = RetNH.getNode()) |
| 566 | N->setModifiedMarker()->setReadMarker(); |
| 567 | return true; |
| 568 | } |
| 569 | case Intrinsic::memset_i32: |
| 570 | case Intrinsic::memset_i64: |
| 571 | // Mark the memory modified. |
| 572 | if (DSNode *N = getValueDest(**CS.arg_begin()).getNode()) |
| 573 | N->setModifiedMarker(); |
| 574 | return true; |
| 575 | default: |
Bill Wendling | 5294fb0 | 2006-11-17 07:33:59 +0000 | [diff] [blame] | 576 | DOUT << "[dsa:local] Unhandled intrinsic: " << F->getName() << "\n"; |
Andrew Lenharth | 118c094 | 2006-11-03 17:43:19 +0000 | [diff] [blame] | 577 | return false; |
| 578 | } |
| 579 | } |
| 580 | |
| 581 | /// returns true if the external is a recognized libc function with a |
| 582 | /// known (and generated) graph |
| 583 | bool GraphBuilder::visitExternal(CallSite CS, Function *F) { |
| 584 | if (F->getName() == "calloc" |
| 585 | || F->getName() == "posix_memalign" |
| 586 | || F->getName() == "memalign" || F->getName() == "valloc") { |
| 587 | setDestTo(*CS.getInstruction(), |
| 588 | createNode()->setHeapNodeMarker()->setModifiedMarker()); |
| 589 | return true; |
| 590 | } else if (F->getName() == "realloc") { |
| 591 | DSNodeHandle RetNH = getValueDest(*CS.getInstruction()); |
| 592 | if (CS.arg_begin() != CS.arg_end()) |
| 593 | RetNH.mergeWith(getValueDest(**CS.arg_begin())); |
| 594 | if (DSNode *N = RetNH.getNode()) |
| 595 | N->setHeapNodeMarker()->setModifiedMarker()->setReadMarker(); |
| 596 | return true; |
| 597 | } else if (F->getName() == "memmove") { |
| 598 | // Merge the first & second arguments, and mark the memory read and |
| 599 | // modified. |
| 600 | DSNodeHandle RetNH = getValueDest(**CS.arg_begin()); |
| 601 | RetNH.mergeWith(getValueDest(**(CS.arg_begin()+1))); |
| 602 | if (DSNode *N = RetNH.getNode()) |
| 603 | N->setModifiedMarker()->setReadMarker(); |
| 604 | return true; |
| 605 | } else if (F->getName() == "free") { |
| 606 | // Mark that the node is written to... |
| 607 | if (DSNode *N = getValueDest(**CS.arg_begin()).getNode()) |
| 608 | N->setModifiedMarker()->setHeapNodeMarker(); |
| 609 | } else if (F->getName() == "atoi" || F->getName() == "atof" || |
| 610 | F->getName() == "atol" || F->getName() == "atoll" || |
| 611 | F->getName() == "remove" || F->getName() == "unlink" || |
| 612 | F->getName() == "rename" || F->getName() == "memcmp" || |
| 613 | F->getName() == "strcmp" || F->getName() == "strncmp" || |
| 614 | F->getName() == "execl" || F->getName() == "execlp" || |
| 615 | F->getName() == "execle" || F->getName() == "execv" || |
| 616 | F->getName() == "execvp" || F->getName() == "chmod" || |
| 617 | F->getName() == "puts" || F->getName() == "write" || |
| 618 | F->getName() == "open" || F->getName() == "create" || |
| 619 | F->getName() == "truncate" || F->getName() == "chdir" || |
| 620 | F->getName() == "mkdir" || F->getName() == "rmdir" || |
| 621 | F->getName() == "strlen") { |
| 622 | // These functions read all of their pointer operands. |
| 623 | for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); |
| 624 | AI != E; ++AI) { |
| 625 | if (isPointerType((*AI)->getType())) |
| 626 | if (DSNode *N = getValueDest(**AI).getNode()) |
| 627 | N->setReadMarker(); |
| 628 | } |
| 629 | return true; |
| 630 | } else if (F->getName() == "memchr") { |
| 631 | DSNodeHandle RetNH = getValueDest(**CS.arg_begin()); |
| 632 | DSNodeHandle Result = getValueDest(*CS.getInstruction()); |
| 633 | RetNH.mergeWith(Result); |
| 634 | if (DSNode *N = RetNH.getNode()) |
| 635 | N->setReadMarker(); |
| 636 | return true; |
| 637 | } else if (F->getName() == "read" || F->getName() == "pipe" || |
| 638 | F->getName() == "wait" || F->getName() == "time" || |
| 639 | F->getName() == "getrusage") { |
| 640 | // These functions write all of their pointer operands. |
| 641 | for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); |
| 642 | AI != E; ++AI) { |
| 643 | if (isPointerType((*AI)->getType())) |
| 644 | if (DSNode *N = getValueDest(**AI).getNode()) |
| 645 | N->setModifiedMarker(); |
| 646 | } |
| 647 | return true; |
| 648 | } else if (F->getName() == "stat" || F->getName() == "fstat" || |
| 649 | F->getName() == "lstat") { |
| 650 | // These functions read their first operand if its a pointer. |
| 651 | CallSite::arg_iterator AI = CS.arg_begin(); |
| 652 | if (isPointerType((*AI)->getType())) { |
| 653 | DSNodeHandle Path = getValueDest(**AI); |
| 654 | if (DSNode *N = Path.getNode()) N->setReadMarker(); |
| 655 | } |
| 656 | |
| 657 | // Then they write into the stat buffer. |
| 658 | DSNodeHandle StatBuf = getValueDest(**++AI); |
| 659 | if (DSNode *N = StatBuf.getNode()) { |
| 660 | N->setModifiedMarker(); |
| 661 | const Type *StatTy = F->getFunctionType()->getParamType(1); |
| 662 | if (const PointerType *PTy = dyn_cast<PointerType>(StatTy)) |
| 663 | N->mergeTypeInfo(PTy->getElementType(), StatBuf.getOffset()); |
| 664 | } |
| 665 | return true; |
| 666 | } else if (F->getName() == "strtod" || F->getName() == "strtof" || |
| 667 | F->getName() == "strtold") { |
| 668 | // These functions read the first pointer |
| 669 | if (DSNode *Str = getValueDest(**CS.arg_begin()).getNode()) { |
| 670 | Str->setReadMarker(); |
| 671 | // If the second parameter is passed, it will point to the first |
| 672 | // argument node. |
| 673 | const DSNodeHandle &EndPtrNH = getValueDest(**(CS.arg_begin()+1)); |
| 674 | if (DSNode *End = EndPtrNH.getNode()) { |
| 675 | End->mergeTypeInfo(PointerType::get(Type::SByteTy), |
| 676 | EndPtrNH.getOffset(), false); |
| 677 | End->setModifiedMarker(); |
| 678 | DSNodeHandle &Link = getLink(EndPtrNH); |
| 679 | Link.mergeWith(getValueDest(**CS.arg_begin())); |
| 680 | } |
| 681 | } |
| 682 | return true; |
| 683 | } else if (F->getName() == "fopen" || F->getName() == "fdopen" || |
| 684 | F->getName() == "freopen") { |
| 685 | // These functions read all of their pointer operands. |
| 686 | for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); |
| 687 | AI != E; ++AI) |
| 688 | if (isPointerType((*AI)->getType())) |
| 689 | if (DSNode *N = getValueDest(**AI).getNode()) |
| 690 | N->setReadMarker(); |
| 691 | |
| 692 | // fopen allocates in an unknown way and writes to the file |
| 693 | // descriptor. Also, merge the allocated type into the node. |
| 694 | DSNodeHandle Result = getValueDest(*CS.getInstruction()); |
| 695 | if (DSNode *N = Result.getNode()) { |
| 696 | N->setModifiedMarker()->setUnknownNodeMarker(); |
| 697 | const Type *RetTy = F->getFunctionType()->getReturnType(); |
| 698 | if (const PointerType *PTy = dyn_cast<PointerType>(RetTy)) |
| 699 | N->mergeTypeInfo(PTy->getElementType(), Result.getOffset()); |
| 700 | } |
| 701 | |
| 702 | // If this is freopen, merge the file descriptor passed in with the |
| 703 | // result. |
| 704 | if (F->getName() == "freopen") { |
| 705 | // ICC doesn't handle getting the iterator, decrementing and |
| 706 | // dereferencing it in one operation without error. Do it in 2 steps |
| 707 | CallSite::arg_iterator compit = CS.arg_end(); |
| 708 | Result.mergeWith(getValueDest(**--compit)); |
| 709 | } |
| 710 | return true; |
| 711 | } else if (F->getName() == "fclose" && CS.arg_end()-CS.arg_begin() ==1){ |
| 712 | // fclose reads and deallocates the memory in an unknown way for the |
| 713 | // file descriptor. It merges the FILE type into the descriptor. |
| 714 | DSNodeHandle H = getValueDest(**CS.arg_begin()); |
| 715 | if (DSNode *N = H.getNode()) { |
| 716 | N->setReadMarker()->setUnknownNodeMarker(); |
| 717 | const Type *ArgTy = F->getFunctionType()->getParamType(0); |
| 718 | if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) |
| 719 | N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); |
| 720 | } |
| 721 | return true; |
| 722 | } else if (CS.arg_end()-CS.arg_begin() == 1 && |
| 723 | (F->getName() == "fflush" || F->getName() == "feof" || |
| 724 | F->getName() == "fileno" || F->getName() == "clearerr" || |
| 725 | F->getName() == "rewind" || F->getName() == "ftell" || |
| 726 | F->getName() == "ferror" || F->getName() == "fgetc" || |
| 727 | F->getName() == "fgetc" || F->getName() == "_IO_getc")) { |
| 728 | // fflush reads and writes the memory for the file descriptor. It |
| 729 | // merges the FILE type into the descriptor. |
| 730 | DSNodeHandle H = getValueDest(**CS.arg_begin()); |
| 731 | if (DSNode *N = H.getNode()) { |
| 732 | N->setReadMarker()->setModifiedMarker(); |
| 733 | |
| 734 | const Type *ArgTy = F->getFunctionType()->getParamType(0); |
| 735 | if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) |
| 736 | N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); |
| 737 | } |
| 738 | return true; |
| 739 | } else if (CS.arg_end()-CS.arg_begin() == 4 && |
| 740 | (F->getName() == "fwrite" || F->getName() == "fread")) { |
| 741 | // fread writes the first operand, fwrite reads it. They both |
| 742 | // read/write the FILE descriptor, and merges the FILE type. |
| 743 | CallSite::arg_iterator compit = CS.arg_end(); |
| 744 | DSNodeHandle H = getValueDest(**--compit); |
| 745 | if (DSNode *N = H.getNode()) { |
| 746 | N->setReadMarker()->setModifiedMarker(); |
| 747 | const Type *ArgTy = F->getFunctionType()->getParamType(3); |
| 748 | if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) |
| 749 | N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); |
| 750 | } |
| 751 | |
| 752 | H = getValueDest(**CS.arg_begin()); |
| 753 | if (DSNode *N = H.getNode()) |
| 754 | if (F->getName() == "fwrite") |
| 755 | N->setReadMarker(); |
| 756 | else |
| 757 | N->setModifiedMarker(); |
| 758 | return true; |
| 759 | } else if (F->getName() == "fgets" && CS.arg_end()-CS.arg_begin() == 3){ |
| 760 | // fgets reads and writes the memory for the file descriptor. It |
| 761 | // merges the FILE type into the descriptor, and writes to the |
| 762 | // argument. It returns the argument as well. |
| 763 | CallSite::arg_iterator AI = CS.arg_begin(); |
| 764 | DSNodeHandle H = getValueDest(**AI); |
| 765 | if (DSNode *N = H.getNode()) |
| 766 | N->setModifiedMarker(); // Writes buffer |
| 767 | H.mergeWith(getValueDest(*CS.getInstruction())); // Returns buffer |
| 768 | ++AI; ++AI; |
| 769 | |
| 770 | // Reads and writes file descriptor, merge in FILE type. |
| 771 | H = getValueDest(**AI); |
| 772 | if (DSNode *N = H.getNode()) { |
| 773 | N->setReadMarker()->setModifiedMarker(); |
| 774 | const Type *ArgTy = F->getFunctionType()->getParamType(2); |
| 775 | if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) |
| 776 | N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); |
| 777 | } |
| 778 | return true; |
| 779 | } else if (F->getName() == "ungetc" || F->getName() == "fputc" || |
| 780 | F->getName() == "fputs" || F->getName() == "putc" || |
| 781 | F->getName() == "ftell" || F->getName() == "rewind" || |
| 782 | F->getName() == "_IO_putc") { |
| 783 | // These functions read and write the memory for the file descriptor, |
| 784 | // which is passes as the last argument. |
| 785 | CallSite::arg_iterator compit = CS.arg_end(); |
| 786 | DSNodeHandle H = getValueDest(**--compit); |
| 787 | if (DSNode *N = H.getNode()) { |
| 788 | N->setReadMarker()->setModifiedMarker(); |
| 789 | FunctionType::param_iterator compit2 = F->getFunctionType()->param_end(); |
| 790 | const Type *ArgTy = *--compit2; |
| 791 | if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) |
| 792 | N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); |
| 793 | } |
| 794 | |
| 795 | // Any pointer arguments are read. |
| 796 | for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); |
| 797 | AI != E; ++AI) |
| 798 | if (isPointerType((*AI)->getType())) |
| 799 | if (DSNode *N = getValueDest(**AI).getNode()) |
| 800 | N->setReadMarker(); |
| 801 | return true; |
| 802 | } else if (F->getName() == "fseek" || F->getName() == "fgetpos" || |
| 803 | F->getName() == "fsetpos") { |
| 804 | // These functions read and write the memory for the file descriptor, |
| 805 | // and read/write all other arguments. |
| 806 | DSNodeHandle H = getValueDest(**CS.arg_begin()); |
| 807 | if (DSNode *N = H.getNode()) { |
| 808 | FunctionType::param_iterator compit2 = F->getFunctionType()->param_end(); |
| 809 | const Type *ArgTy = *--compit2; |
| 810 | if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) |
| 811 | N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); |
| 812 | } |
| 813 | |
| 814 | // Any pointer arguments are read. |
| 815 | for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); |
| 816 | AI != E; ++AI) |
| 817 | if (isPointerType((*AI)->getType())) |
| 818 | if (DSNode *N = getValueDest(**AI).getNode()) |
| 819 | N->setReadMarker()->setModifiedMarker(); |
| 820 | return true; |
| 821 | } else if (F->getName() == "printf" || F->getName() == "fprintf" || |
| 822 | F->getName() == "sprintf") { |
| 823 | CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); |
| 824 | |
| 825 | if (F->getName() == "fprintf") { |
| 826 | // fprintf reads and writes the FILE argument, and applies the type |
| 827 | // to it. |
| 828 | DSNodeHandle H = getValueDest(**AI); |
| 829 | if (DSNode *N = H.getNode()) { |
| 830 | N->setModifiedMarker(); |
| 831 | const Type *ArgTy = (*AI)->getType(); |
| 832 | if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) |
| 833 | N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); |
| 834 | } |
| 835 | } else if (F->getName() == "sprintf") { |
| 836 | // sprintf writes the first string argument. |
| 837 | DSNodeHandle H = getValueDest(**AI++); |
| 838 | if (DSNode *N = H.getNode()) { |
| 839 | N->setModifiedMarker(); |
| 840 | const Type *ArgTy = (*AI)->getType(); |
| 841 | if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) |
| 842 | N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); |
| 843 | } |
| 844 | } |
| 845 | |
| 846 | for (; AI != E; ++AI) { |
| 847 | // printf reads all pointer arguments. |
| 848 | if (isPointerType((*AI)->getType())) |
| 849 | if (DSNode *N = getValueDest(**AI).getNode()) |
| 850 | N->setReadMarker(); |
| 851 | } |
| 852 | return true; |
| 853 | } else if (F->getName() == "vprintf" || F->getName() == "vfprintf" || |
| 854 | F->getName() == "vsprintf") { |
| 855 | CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); |
| 856 | |
| 857 | if (F->getName() == "vfprintf") { |
| 858 | // ffprintf reads and writes the FILE argument, and applies the type |
| 859 | // to it. |
| 860 | DSNodeHandle H = getValueDest(**AI); |
| 861 | if (DSNode *N = H.getNode()) { |
| 862 | N->setModifiedMarker()->setReadMarker(); |
| 863 | const Type *ArgTy = (*AI)->getType(); |
| 864 | if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) |
| 865 | N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); |
| 866 | } |
| 867 | ++AI; |
| 868 | } else if (F->getName() == "vsprintf") { |
| 869 | // vsprintf writes the first string argument. |
| 870 | DSNodeHandle H = getValueDest(**AI++); |
| 871 | if (DSNode *N = H.getNode()) { |
| 872 | N->setModifiedMarker(); |
| 873 | const Type *ArgTy = (*AI)->getType(); |
| 874 | if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) |
| 875 | N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); |
| 876 | } |
| 877 | } |
| 878 | |
| 879 | // Read the format |
| 880 | if (AI != E) { |
| 881 | if (isPointerType((*AI)->getType())) |
| 882 | if (DSNode *N = getValueDest(**AI).getNode()) |
| 883 | N->setReadMarker(); |
| 884 | ++AI; |
| 885 | } |
| 886 | |
| 887 | // Read the valist, and the pointed-to objects. |
| 888 | if (AI != E && isPointerType((*AI)->getType())) { |
| 889 | const DSNodeHandle &VAList = getValueDest(**AI); |
| 890 | if (DSNode *N = VAList.getNode()) { |
| 891 | N->setReadMarker(); |
| 892 | N->mergeTypeInfo(PointerType::get(Type::SByteTy), |
| 893 | VAList.getOffset(), false); |
| 894 | |
| 895 | DSNodeHandle &VAListObjs = getLink(VAList); |
| 896 | VAListObjs.getNode()->setReadMarker(); |
| 897 | } |
| 898 | } |
| 899 | |
| 900 | return true; |
| 901 | } else if (F->getName() == "scanf" || F->getName() == "fscanf" || |
| 902 | F->getName() == "sscanf") { |
| 903 | CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); |
| 904 | |
| 905 | if (F->getName() == "fscanf") { |
| 906 | // fscanf reads and writes the FILE argument, and applies the type |
| 907 | // to it. |
| 908 | DSNodeHandle H = getValueDest(**AI); |
| 909 | if (DSNode *N = H.getNode()) { |
| 910 | N->setReadMarker(); |
| 911 | const Type *ArgTy = (*AI)->getType(); |
| 912 | if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) |
| 913 | N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); |
| 914 | } |
| 915 | } else if (F->getName() == "sscanf") { |
| 916 | // sscanf reads the first string argument. |
| 917 | DSNodeHandle H = getValueDest(**AI++); |
| 918 | if (DSNode *N = H.getNode()) { |
| 919 | N->setReadMarker(); |
| 920 | const Type *ArgTy = (*AI)->getType(); |
| 921 | if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) |
| 922 | N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); |
| 923 | } |
| 924 | } |
| 925 | |
| 926 | for (; AI != E; ++AI) { |
| 927 | // scanf writes all pointer arguments. |
| 928 | if (isPointerType((*AI)->getType())) |
| 929 | if (DSNode *N = getValueDest(**AI).getNode()) |
| 930 | N->setModifiedMarker(); |
| 931 | } |
| 932 | return true; |
| 933 | } else if (F->getName() == "strtok") { |
| 934 | // strtok reads and writes the first argument, returning it. It reads |
| 935 | // its second arg. FIXME: strtok also modifies some hidden static |
| 936 | // data. Someday this might matter. |
| 937 | CallSite::arg_iterator AI = CS.arg_begin(); |
| 938 | DSNodeHandle H = getValueDest(**AI++); |
| 939 | if (DSNode *N = H.getNode()) { |
| 940 | N->setReadMarker()->setModifiedMarker(); // Reads/Writes buffer |
| 941 | const Type *ArgTy = F->getFunctionType()->getParamType(0); |
| 942 | if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) |
| 943 | N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); |
| 944 | } |
| 945 | H.mergeWith(getValueDest(*CS.getInstruction())); // Returns buffer |
| 946 | |
| 947 | H = getValueDest(**AI); // Reads delimiter |
| 948 | if (DSNode *N = H.getNode()) { |
| 949 | N->setReadMarker(); |
| 950 | const Type *ArgTy = F->getFunctionType()->getParamType(1); |
| 951 | if (const PointerType *PTy = dyn_cast<PointerType>(ArgTy)) |
| 952 | N->mergeTypeInfo(PTy->getElementType(), H.getOffset()); |
| 953 | } |
| 954 | return true; |
| 955 | } else if (F->getName() == "strchr" || F->getName() == "strrchr" || |
| 956 | F->getName() == "strstr") { |
| 957 | // These read their arguments, and return the first one |
| 958 | DSNodeHandle H = getValueDest(**CS.arg_begin()); |
| 959 | H.mergeWith(getValueDest(*CS.getInstruction())); // Returns buffer |
| 960 | |
| 961 | for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); |
| 962 | AI != E; ++AI) |
| 963 | if (isPointerType((*AI)->getType())) |
| 964 | if (DSNode *N = getValueDest(**AI).getNode()) |
| 965 | N->setReadMarker(); |
| 966 | |
| 967 | if (DSNode *N = H.getNode()) |
| 968 | N->setReadMarker(); |
| 969 | return true; |
| 970 | } else if (F->getName() == "__assert_fail") { |
| 971 | for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); |
| 972 | AI != E; ++AI) |
| 973 | if (isPointerType((*AI)->getType())) |
| 974 | if (DSNode *N = getValueDest(**AI).getNode()) |
| 975 | N->setReadMarker(); |
| 976 | return true; |
| 977 | } else if (F->getName() == "modf" && CS.arg_end()-CS.arg_begin() == 2) { |
| 978 | // This writes its second argument, and forces it to double. |
| 979 | CallSite::arg_iterator compit = CS.arg_end(); |
| 980 | DSNodeHandle H = getValueDest(**--compit); |
| 981 | if (DSNode *N = H.getNode()) { |
| 982 | N->setModifiedMarker(); |
| 983 | N->mergeTypeInfo(Type::DoubleTy, H.getOffset()); |
| 984 | } |
| 985 | return true; |
| 986 | } else if (F->getName() == "strcat" || F->getName() == "strncat") { |
| 987 | //This might be making unsafe assumptions about usage |
| 988 | //Merge return and first arg |
| 989 | DSNodeHandle RetNH = getValueDest(*CS.getInstruction()); |
| 990 | RetNH.mergeWith(getValueDest(**CS.arg_begin())); |
| 991 | if (DSNode *N = RetNH.getNode()) |
| 992 | N->setHeapNodeMarker()->setModifiedMarker()->setReadMarker(); |
| 993 | //and read second pointer |
| 994 | if (DSNode *N = getValueDest(**(CS.arg_begin() + 1)).getNode()) |
| 995 | N->setReadMarker(); |
| 996 | return true; |
| 997 | } else if (F->getName() == "strcpy" || F->getName() == "strncpy") { |
| 998 | //This might be making unsafe assumptions about usage |
| 999 | //Merge return and first arg |
| 1000 | DSNodeHandle RetNH = getValueDest(*CS.getInstruction()); |
| 1001 | RetNH.mergeWith(getValueDest(**CS.arg_begin())); |
| 1002 | if (DSNode *N = RetNH.getNode()) |
| 1003 | N->setHeapNodeMarker()->setModifiedMarker(); |
| 1004 | //and read second pointer |
| 1005 | if (DSNode *N = getValueDest(**(CS.arg_begin() + 1)).getNode()) |
| 1006 | N->setReadMarker(); |
| 1007 | return true; |
| 1008 | } |
| 1009 | return false; |
| 1010 | } |
| 1011 | |
Chris Lattner | 808a7ae | 2003-09-20 16:34:13 +0000 | [diff] [blame] | 1012 | void GraphBuilder::visitCallSite(CallSite CS) { |
Chris Lattner | cb58240 | 2004-02-26 22:07:22 +0000 | [diff] [blame] | 1013 | Value *Callee = CS.getCalledValue(); |
Chris Lattner | cb58240 | 2004-02-26 22:07:22 +0000 | [diff] [blame] | 1014 | |
Chris Lattner | 894263b | 2003-09-20 16:50:46 +0000 | [diff] [blame] | 1015 | // Special case handling of certain libc allocation functions here. |
Chris Lattner | cb58240 | 2004-02-26 22:07:22 +0000 | [diff] [blame] | 1016 | if (Function *F = dyn_cast<Function>(Callee)) |
Chris Lattner | 894263b | 2003-09-20 16:50:46 +0000 | [diff] [blame] | 1017 | if (F->isExternal()) |
Andrew Lenharth | 118c094 | 2006-11-03 17:43:19 +0000 | [diff] [blame] | 1018 | if (F->isIntrinsic() && visitIntrinsic(CS, F)) |
Chris Lattner | 6b3e3cc | 2004-03-04 20:33:47 +0000 | [diff] [blame] | 1019 | return; |
Andrew Lenharth | 118c094 | 2006-11-03 17:43:19 +0000 | [diff] [blame] | 1020 | else { |
John Criswell | fa70052 | 2005-12-19 17:38:39 +0000 | [diff] [blame] | 1021 | // Determine if the called function is one of the specified heap |
| 1022 | // allocation functions |
Andrew Lenharth | 118c094 | 2006-11-03 17:43:19 +0000 | [diff] [blame] | 1023 | if (AllocList.end() != std::find(AllocList.begin(), AllocList.end(), F->getName())) { |
| 1024 | setDestTo(*CS.getInstruction(), |
| 1025 | createNode()->setHeapNodeMarker()->setModifiedMarker()); |
| 1026 | return; |
| 1027 | } |
John Criswell | fa70052 | 2005-12-19 17:38:39 +0000 | [diff] [blame] | 1028 | |
John Criswell | 3075160 | 2005-12-19 19:54:23 +0000 | [diff] [blame] | 1029 | // Determine if the called function is one of the specified heap |
| 1030 | // free functions |
Andrew Lenharth | 118c094 | 2006-11-03 17:43:19 +0000 | [diff] [blame] | 1031 | if (FreeList.end() != std::find(FreeList.begin(), FreeList.end(), F->getName())) { |
| 1032 | // Mark that the node is written to... |
| 1033 | if (DSNode *N = getValueDest(*(CS.getArgument(0))).getNode()) |
| 1034 | N->setModifiedMarker()->setHeapNodeMarker(); |
| 1035 | return; |
| 1036 | } |
| 1037 | if (visitExternal(CS,F)) |
| 1038 | return; |
| 1039 | // Unknown function, warn if it returns a pointer type or takes a |
| 1040 | // pointer argument. |
| 1041 | bool Warn = isPointerType(CS.getInstruction()->getType()); |
| 1042 | if (!Warn) |
| 1043 | for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); |
| 1044 | I != E; ++I) |
| 1045 | if (isPointerType((*I)->getType())) { |
| 1046 | Warn = true; |
| 1047 | break; |
Chris Lattner | 3aeb40c | 2004-03-04 21:03:54 +0000 | [diff] [blame] | 1048 | } |
Andrew Lenharth | 118c094 | 2006-11-03 17:43:19 +0000 | [diff] [blame] | 1049 | if (Warn) { |
Bill Wendling | 5294fb0 | 2006-11-17 07:33:59 +0000 | [diff] [blame] | 1050 | DOUT << "WARNING: Call to unknown external function '" |
| 1051 | << F->getName() << "' will cause pessimistic results!\n"; |
Chris Lattner | a07b72f | 2004-02-13 16:09:54 +0000 | [diff] [blame] | 1052 | } |
Chris Lattner | 894263b | 2003-09-20 16:50:46 +0000 | [diff] [blame] | 1053 | } |
| 1054 | |
Chris Lattner | c314ac4 | 2002-07-11 20:32:02 +0000 | [diff] [blame] | 1055 | // Set up the return value... |
Chris Lattner | 0969c50 | 2002-10-21 02:08:03 +0000 | [diff] [blame] | 1056 | DSNodeHandle RetVal; |
Chris Lattner | 808a7ae | 2003-09-20 16:34:13 +0000 | [diff] [blame] | 1057 | Instruction *I = CS.getInstruction(); |
| 1058 | if (isPointerType(I->getType())) |
| 1059 | RetVal = getValueDest(*I); |
Chris Lattner | c314ac4 | 2002-07-11 20:32:02 +0000 | [diff] [blame] | 1060 | |
Chris Lattner | cb58240 | 2004-02-26 22:07:22 +0000 | [diff] [blame] | 1061 | DSNode *CalleeNode = 0; |
| 1062 | if (DisableDirectCallOpt || !isa<Function>(Callee)) { |
| 1063 | CalleeNode = getValueDest(*Callee).getNode(); |
| 1064 | if (CalleeNode == 0) { |
| 1065 | std::cerr << "WARNING: Program is calling through a null pointer?\n"<< *I; |
Chris Lattner | fbc2d84 | 2003-09-24 23:42:58 +0000 | [diff] [blame] | 1066 | return; // Calling a null pointer? |
| 1067 | } |
| 1068 | } |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1069 | |
Chris Lattner | 0969c50 | 2002-10-21 02:08:03 +0000 | [diff] [blame] | 1070 | std::vector<DSNodeHandle> Args; |
Chris Lattner | 808a7ae | 2003-09-20 16:34:13 +0000 | [diff] [blame] | 1071 | Args.reserve(CS.arg_end()-CS.arg_begin()); |
Chris Lattner | 0969c50 | 2002-10-21 02:08:03 +0000 | [diff] [blame] | 1072 | |
| 1073 | // Calculate the arguments vector... |
Chris Lattner | 808a7ae | 2003-09-20 16:34:13 +0000 | [diff] [blame] | 1074 | for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I) |
| 1075 | if (isPointerType((*I)->getType())) |
| 1076 | Args.push_back(getValueDest(**I)); |
Chris Lattner | 0969c50 | 2002-10-21 02:08:03 +0000 | [diff] [blame] | 1077 | |
| 1078 | // Add a new function call entry... |
Chris Lattner | cb58240 | 2004-02-26 22:07:22 +0000 | [diff] [blame] | 1079 | if (CalleeNode) |
| 1080 | FunctionCalls->push_back(DSCallSite(CS, RetVal, CalleeNode, Args)); |
Chris Lattner | 923fc05 | 2003-02-05 21:59:58 +0000 | [diff] [blame] | 1081 | else |
Chris Lattner | cb58240 | 2004-02-26 22:07:22 +0000 | [diff] [blame] | 1082 | FunctionCalls->push_back(DSCallSite(CS, RetVal, cast<Function>(Callee), |
Chris Lattner | 26c4fc3 | 2003-09-20 21:48:16 +0000 | [diff] [blame] | 1083 | Args)); |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 1084 | } |
Chris Lattner | 055dc2c | 2002-07-18 15:54:42 +0000 | [diff] [blame] | 1085 | |
Vikram S. Adve | bac0622 | 2002-12-06 21:17:10 +0000 | [diff] [blame] | 1086 | void GraphBuilder::visitFreeInst(FreeInst &FI) { |
Vikram S. Adve | bac0622 | 2002-12-06 21:17:10 +0000 | [diff] [blame] | 1087 | // Mark that the node is written to... |
Chris Lattner | d561209 | 2004-02-24 22:02:48 +0000 | [diff] [blame] | 1088 | if (DSNode *N = getValueDest(*FI.getOperand(0)).getNode()) |
| 1089 | N->setModifiedMarker()->setHeapNodeMarker(); |
Vikram S. Adve | bac0622 | 2002-12-06 21:17:10 +0000 | [diff] [blame] | 1090 | } |
| 1091 | |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 1092 | /// Handle casts... |
| 1093 | void GraphBuilder::visitCastInst(CastInst &CI) { |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame^] | 1094 | // Pointers can only be cast with BitCast so check that the instruction |
| 1095 | // is a BitConvert. If not, its guaranteed not to involve any pointers so |
| 1096 | // we don't do anything. |
| 1097 | switch (CI.getOpcode()) { |
| 1098 | default: break; |
| 1099 | case Instruction::BitCast: |
| 1100 | case Instruction::IntToPtr: |
| 1101 | if (isPointerType(CI.getType())) |
| 1102 | if (isPointerType(CI.getOperand(0)->getType())) { |
| 1103 | DSNodeHandle Ptr = getValueDest(*CI.getOperand(0)); |
| 1104 | if (Ptr.getNode() == 0) return; |
| 1105 | // Cast one pointer to the other, just act like a copy instruction |
| 1106 | setDestTo(CI, Ptr); |
| 1107 | } else { |
| 1108 | // Cast something (floating point, small integer) to a pointer. We |
| 1109 | // need to track the fact that the node points to SOMETHING, just |
| 1110 | // something we don't know about. Make an "Unknown" node. |
| 1111 | setDestTo(CI, createNode()->setUnknownNodeMarker()); |
| 1112 | } |
| 1113 | break; |
| 1114 | } |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 1115 | } |
Chris Lattner | 055dc2c | 2002-07-18 15:54:42 +0000 | [diff] [blame] | 1116 | |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 1117 | |
Chris Lattner | 878e521 | 2003-02-04 00:59:50 +0000 | [diff] [blame] | 1118 | // visitInstruction - For all other instruction types, if we have any arguments |
| 1119 | // that are of pointer type, make them have unknown composition bits, and merge |
| 1120 | // the nodes together. |
| 1121 | void GraphBuilder::visitInstruction(Instruction &Inst) { |
| 1122 | DSNodeHandle CurNode; |
| 1123 | if (isPointerType(Inst.getType())) |
| 1124 | CurNode = getValueDest(Inst); |
| 1125 | for (User::op_iterator I = Inst.op_begin(), E = Inst.op_end(); I != E; ++I) |
| 1126 | if (isPointerType((*I)->getType())) |
| 1127 | CurNode.mergeWith(getValueDest(**I)); |
| 1128 | |
Chris Lattner | 62c3a95 | 2004-10-30 04:22:45 +0000 | [diff] [blame] | 1129 | if (DSNode *N = CurNode.getNode()) |
| 1130 | N->setUnknownNodeMarker(); |
Chris Lattner | 878e521 | 2003-02-04 00:59:50 +0000 | [diff] [blame] | 1131 | } |
| 1132 | |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 1133 | |
| 1134 | |
| 1135 | //===----------------------------------------------------------------------===// |
| 1136 | // LocalDataStructures Implementation |
| 1137 | //===----------------------------------------------------------------------===// |
| 1138 | |
Chris Lattner | 26c4fc3 | 2003-09-20 21:48:16 +0000 | [diff] [blame] | 1139 | // MergeConstantInitIntoNode - Merge the specified constant into the node |
| 1140 | // pointed to by NH. |
| 1141 | void GraphBuilder::MergeConstantInitIntoNode(DSNodeHandle &NH, Constant *C) { |
| 1142 | // Ensure a type-record exists... |
Chris Lattner | 62c3a95 | 2004-10-30 04:22:45 +0000 | [diff] [blame] | 1143 | DSNode *NHN = NH.getNode(); |
| 1144 | NHN->mergeTypeInfo(C->getType(), NH.getOffset()); |
Chris Lattner | 26c4fc3 | 2003-09-20 21:48:16 +0000 | [diff] [blame] | 1145 | |
| 1146 | if (C->getType()->isFirstClassType()) { |
| 1147 | if (isPointerType(C->getType())) |
| 1148 | // Avoid adding edges from null, or processing non-"pointer" stores |
| 1149 | NH.addEdgeTo(getValueDest(*C)); |
| 1150 | return; |
| 1151 | } |
Chris Lattner | 15869aa | 2003-11-02 22:27:28 +0000 | [diff] [blame] | 1152 | |
| 1153 | const TargetData &TD = NH.getNode()->getTargetData(); |
| 1154 | |
Chris Lattner | 26c4fc3 | 2003-09-20 21:48:16 +0000 | [diff] [blame] | 1155 | if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) { |
| 1156 | for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) |
| 1157 | // We don't currently do any indexing for arrays... |
| 1158 | MergeConstantInitIntoNode(NH, cast<Constant>(CA->getOperand(i))); |
| 1159 | } else if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) { |
| 1160 | const StructLayout *SL = TD.getStructLayout(CS->getType()); |
| 1161 | for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) { |
Chris Lattner | 62c3a95 | 2004-10-30 04:22:45 +0000 | [diff] [blame] | 1162 | DSNode *NHN = NH.getNode(); |
Andrew Lenharth | 99c1942 | 2006-04-13 19:31:49 +0000 | [diff] [blame] | 1163 | //Some programmers think ending a structure with a [0 x sbyte] is cute |
Andrew Lenharth | 99c1942 | 2006-04-13 19:31:49 +0000 | [diff] [blame] | 1164 | if (SL->MemberOffsets[i] < SL->StructSize) { |
| 1165 | DSNodeHandle NewNH(NHN, NH.getOffset()+(unsigned)SL->MemberOffsets[i]); |
| 1166 | MergeConstantInitIntoNode(NewNH, cast<Constant>(CS->getOperand(i))); |
| 1167 | } else if (SL->MemberOffsets[i] == SL->StructSize) { |
Bill Wendling | 5294fb0 | 2006-11-17 07:33:59 +0000 | [diff] [blame] | 1168 | DOUT << "Zero size element at end of struct\n"; |
Andrew Lenharth | ceeb17d | 2006-04-25 19:33:23 +0000 | [diff] [blame] | 1169 | NHN->foldNodeCompletely(); |
Andrew Lenharth | 99c1942 | 2006-04-13 19:31:49 +0000 | [diff] [blame] | 1170 | } else { |
| 1171 | assert(0 && "type was smaller than offsets of of struct layout indicate"); |
| 1172 | } |
Chris Lattner | 26c4fc3 | 2003-09-20 21:48:16 +0000 | [diff] [blame] | 1173 | } |
Chris Lattner | 48b2f6b | 2004-10-26 16:23:03 +0000 | [diff] [blame] | 1174 | } else if (isa<ConstantAggregateZero>(C) || isa<UndefValue>(C)) { |
Chris Lattner | 896481e | 2004-02-15 05:53:42 +0000 | [diff] [blame] | 1175 | // Noop |
Chris Lattner | 26c4fc3 | 2003-09-20 21:48:16 +0000 | [diff] [blame] | 1176 | } else { |
| 1177 | assert(0 && "Unknown constant type!"); |
| 1178 | } |
| 1179 | } |
| 1180 | |
| 1181 | void GraphBuilder::mergeInGlobalInitializer(GlobalVariable *GV) { |
| 1182 | assert(!GV->isExternal() && "Cannot merge in external global!"); |
| 1183 | // Get a node handle to the global node and merge the initializer into it. |
| 1184 | DSNodeHandle NH = getValueDest(*GV); |
| 1185 | MergeConstantInitIntoNode(NH, GV->getInitializer()); |
| 1186 | } |
| 1187 | |
| 1188 | |
Chris Lattner | 9b426bd | 2005-03-20 03:32:35 +0000 | [diff] [blame] | 1189 | /// BuildGlobalECs - Look at all of the nodes in the globals graph. If any node |
| 1190 | /// contains multiple globals, DSA will never, ever, be able to tell the globals |
| 1191 | /// apart. Instead of maintaining this information in all of the graphs |
| 1192 | /// throughout the entire program, store only a single global (the "leader") in |
| 1193 | /// the graphs, and build equivalence classes for the rest of the globals. |
| 1194 | static void BuildGlobalECs(DSGraph &GG, std::set<GlobalValue*> &ECGlobals) { |
| 1195 | DSScalarMap &SM = GG.getScalarMap(); |
| 1196 | EquivalenceClasses<GlobalValue*> &GlobalECs = SM.getGlobalECs(); |
| 1197 | for (DSGraph::node_iterator I = GG.node_begin(), E = GG.node_end(); |
| 1198 | I != E; ++I) { |
| 1199 | if (I->getGlobalsList().size() <= 1) continue; |
| 1200 | |
| 1201 | // First, build up the equivalence set for this block of globals. |
| 1202 | const std::vector<GlobalValue*> &GVs = I->getGlobalsList(); |
| 1203 | GlobalValue *First = GVs[0]; |
| 1204 | for (unsigned i = 1, e = GVs.size(); i != e; ++i) |
| 1205 | GlobalECs.unionSets(First, GVs[i]); |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 1206 | |
Chris Lattner | 9b426bd | 2005-03-20 03:32:35 +0000 | [diff] [blame] | 1207 | // Next, get the leader element. |
| 1208 | assert(First == GlobalECs.getLeaderValue(First) && |
| 1209 | "First did not end up being the leader?"); |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 1210 | |
Chris Lattner | 9b426bd | 2005-03-20 03:32:35 +0000 | [diff] [blame] | 1211 | // Next, remove all globals from the scalar map that are not the leader. |
| 1212 | assert(GVs[0] == First && "First had to be at the front!"); |
| 1213 | for (unsigned i = 1, e = GVs.size(); i != e; ++i) { |
| 1214 | ECGlobals.insert(GVs[i]); |
| 1215 | SM.erase(SM.find(GVs[i])); |
| 1216 | } |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 1217 | |
Chris Lattner | 9b426bd | 2005-03-20 03:32:35 +0000 | [diff] [blame] | 1218 | // Finally, change the global node to only contain the leader. |
| 1219 | I->clearGlobals(); |
| 1220 | I->addGlobal(First); |
| 1221 | } |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 1222 | |
Chris Lattner | 9b426bd | 2005-03-20 03:32:35 +0000 | [diff] [blame] | 1223 | DEBUG(GG.AssertGraphOK()); |
| 1224 | } |
| 1225 | |
| 1226 | /// EliminateUsesOfECGlobals - Once we have determined that some globals are in |
| 1227 | /// really just equivalent to some other globals, remove the globals from the |
| 1228 | /// specified DSGraph (if present), and merge any nodes with their leader nodes. |
| 1229 | static void EliminateUsesOfECGlobals(DSGraph &G, |
| 1230 | const std::set<GlobalValue*> &ECGlobals) { |
| 1231 | DSScalarMap &SM = G.getScalarMap(); |
| 1232 | EquivalenceClasses<GlobalValue*> &GlobalECs = SM.getGlobalECs(); |
| 1233 | |
| 1234 | bool MadeChange = false; |
| 1235 | for (DSScalarMap::global_iterator GI = SM.global_begin(), E = SM.global_end(); |
| 1236 | GI != E; ) { |
| 1237 | GlobalValue *GV = *GI++; |
| 1238 | if (!ECGlobals.count(GV)) continue; |
| 1239 | |
| 1240 | const DSNodeHandle &GVNH = SM[GV]; |
| 1241 | assert(!GVNH.isNull() && "Global has null NH!?"); |
| 1242 | |
| 1243 | // Okay, this global is in some equivalence class. Start by finding the |
| 1244 | // leader of the class. |
| 1245 | GlobalValue *Leader = GlobalECs.getLeaderValue(GV); |
| 1246 | |
| 1247 | // If the leader isn't already in the graph, insert it into the node |
| 1248 | // corresponding to GV. |
| 1249 | if (!SM.global_count(Leader)) { |
| 1250 | GVNH.getNode()->addGlobal(Leader); |
| 1251 | SM[Leader] = GVNH; |
| 1252 | } else { |
| 1253 | // Otherwise, the leader is in the graph, make sure the nodes are the |
| 1254 | // merged in the specified graph. |
| 1255 | const DSNodeHandle &LNH = SM[Leader]; |
| 1256 | if (LNH.getNode() != GVNH.getNode()) |
| 1257 | LNH.mergeWith(GVNH); |
| 1258 | } |
| 1259 | |
| 1260 | // Next step, remove the global from the DSNode. |
| 1261 | GVNH.getNode()->removeGlobal(GV); |
| 1262 | |
| 1263 | // Finally, remove the global from the ScalarMap. |
| 1264 | SM.erase(GV); |
| 1265 | MadeChange = true; |
| 1266 | } |
| 1267 | |
| 1268 | DEBUG(if(MadeChange) G.AssertGraphOK()); |
| 1269 | } |
| 1270 | |
Chris Lattner | b12914b | 2004-09-20 04:48:05 +0000 | [diff] [blame] | 1271 | bool LocalDataStructures::runOnModule(Module &M) { |
Chris Lattner | 15869aa | 2003-11-02 22:27:28 +0000 | [diff] [blame] | 1272 | const TargetData &TD = getAnalysis<TargetData>(); |
Chris Lattner | aa0b468 | 2002-11-09 21:12:07 +0000 | [diff] [blame] | 1273 | |
Chris Lattner | f4f6227 | 2005-03-19 22:23:45 +0000 | [diff] [blame] | 1274 | // First step, build the globals graph. |
| 1275 | GlobalsGraph = new DSGraph(GlobalECs, TD); |
Chris Lattner | c420ab6 | 2004-02-25 23:31:02 +0000 | [diff] [blame] | 1276 | { |
| 1277 | GraphBuilder GGB(*GlobalsGraph); |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 1278 | |
Chris Lattner | f4f6227 | 2005-03-19 22:23:45 +0000 | [diff] [blame] | 1279 | // Add initializers for all of the globals to the globals graph. |
| 1280 | for (Module::global_iterator I = M.global_begin(), E = M.global_end(); |
| 1281 | I != E; ++I) |
Chris Lattner | c420ab6 | 2004-02-25 23:31:02 +0000 | [diff] [blame] | 1282 | if (!I->isExternal()) |
| 1283 | GGB.mergeInGlobalInitializer(I); |
| 1284 | } |
| 1285 | |
Chris Lattner | f4f6227 | 2005-03-19 22:23:45 +0000 | [diff] [blame] | 1286 | // Next step, iterate through the nodes in the globals graph, unioning |
| 1287 | // together the globals into equivalence classes. |
Chris Lattner | 9b426bd | 2005-03-20 03:32:35 +0000 | [diff] [blame] | 1288 | std::set<GlobalValue*> ECGlobals; |
| 1289 | BuildGlobalECs(*GlobalsGraph, ECGlobals); |
Bill Wendling | 5294fb0 | 2006-11-17 07:33:59 +0000 | [diff] [blame] | 1290 | DOUT << "Eliminating " << ECGlobals.size() << " EC Globals!\n"; |
Chris Lattner | 9b426bd | 2005-03-20 03:32:35 +0000 | [diff] [blame] | 1291 | ECGlobals.clear(); |
Chris Lattner | f4f6227 | 2005-03-19 22:23:45 +0000 | [diff] [blame] | 1292 | |
Chris Lattner | aa0b468 | 2002-11-09 21:12:07 +0000 | [diff] [blame] | 1293 | // Calculate all of the graphs... |
| 1294 | for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) |
| 1295 | if (!I->isExternal()) |
Chris Lattner | f4f6227 | 2005-03-19 22:23:45 +0000 | [diff] [blame] | 1296 | DSInfo.insert(std::make_pair(I, new DSGraph(GlobalECs, TD, *I, |
| 1297 | GlobalsGraph))); |
Chris Lattner | 26c4fc3 | 2003-09-20 21:48:16 +0000 | [diff] [blame] | 1298 | |
Chris Lattner | c3f5f77 | 2004-02-08 01:51:48 +0000 | [diff] [blame] | 1299 | GlobalsGraph->removeTriviallyDeadNodes(); |
Chris Lattner | 26c4fc3 | 2003-09-20 21:48:16 +0000 | [diff] [blame] | 1300 | GlobalsGraph->markIncompleteNodes(DSGraph::MarkFormalArgs); |
Chris Lattner | 9b426bd | 2005-03-20 03:32:35 +0000 | [diff] [blame] | 1301 | |
| 1302 | // Now that we've computed all of the graphs, and merged all of the info into |
| 1303 | // the globals graph, see if we have further constrained the globals in the |
| 1304 | // program if so, update GlobalECs and remove the extraneous globals from the |
| 1305 | // program. |
| 1306 | BuildGlobalECs(*GlobalsGraph, ECGlobals); |
| 1307 | if (!ECGlobals.empty()) { |
Bill Wendling | 5294fb0 | 2006-11-17 07:33:59 +0000 | [diff] [blame] | 1308 | DOUT << "Eliminating " << ECGlobals.size() << " EC Globals!\n"; |
Chris Lattner | 9b426bd | 2005-03-20 03:32:35 +0000 | [diff] [blame] | 1309 | for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(), |
| 1310 | E = DSInfo.end(); I != E; ++I) |
| 1311 | EliminateUsesOfECGlobals(*I->second, ECGlobals); |
| 1312 | } |
| 1313 | |
Chris Lattner | aa0b468 | 2002-11-09 21:12:07 +0000 | [diff] [blame] | 1314 | return false; |
| 1315 | } |
| 1316 | |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 1317 | // releaseMemory - If the pass pipeline is done with this pass, we can release |
| 1318 | // our memory... here... |
| 1319 | // |
| 1320 | void LocalDataStructures::releaseMemory() { |
Chris Lattner | 81d924d | 2003-06-30 04:53:27 +0000 | [diff] [blame] | 1321 | for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(), |
| 1322 | E = DSInfo.end(); I != E; ++I) { |
| 1323 | I->second->getReturnNodes().erase(I->first); |
| 1324 | if (I->second->getReturnNodes().empty()) |
| 1325 | delete I->second; |
| 1326 | } |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 1327 | |
| 1328 | // Empty map so next time memory is released, data structures are not |
| 1329 | // re-deleted. |
| 1330 | DSInfo.clear(); |
Chris Lattner | 2e4f9bf | 2002-11-09 20:01:01 +0000 | [diff] [blame] | 1331 | delete GlobalsGraph; |
| 1332 | GlobalsGraph = 0; |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 1333 | } |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 1334 | |