Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 1 | //===- DataStructure.cpp - Implement the core data structure analysis -----===// |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 2 | // |
| 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. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | bb2a28f | 2002-03-26 22:39:06 +0000 | [diff] [blame] | 9 | // |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 10 | // This file implements the core data structure functionality. |
Chris Lattner | bb2a28f | 2002-03-26 22:39:06 +0000 | [diff] [blame] | 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
Chris Lattner | 4dabb2c | 2004-07-07 06:32:21 +0000 | [diff] [blame] | 14 | #include "llvm/Analysis/DataStructure/DSGraphTraits.h" |
Chris Lattner | 94f8470 | 2005-03-17 19:56:56 +0000 | [diff] [blame] | 15 | #include "llvm/Constants.h" |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 16 | #include "llvm/Function.h" |
Chris Lattner | cf14e71 | 2004-02-25 23:36:08 +0000 | [diff] [blame] | 17 | #include "llvm/GlobalVariable.h" |
Misha Brukman | 47b14a4 | 2004-07-29 17:30:56 +0000 | [diff] [blame] | 18 | #include "llvm/Instructions.h" |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 19 | #include "llvm/DerivedTypes.h" |
Chris Lattner | 7b7200c | 2002-10-02 04:57:39 +0000 | [diff] [blame] | 20 | #include "llvm/Target/TargetData.h" |
Chris Lattner | 58f98d0 | 2003-07-02 04:38:49 +0000 | [diff] [blame] | 21 | #include "llvm/Assembly/Writer.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 22 | #include "llvm/Support/CommandLine.h" |
| 23 | #include "llvm/Support/Debug.h" |
| 24 | #include "llvm/ADT/DepthFirstIterator.h" |
| 25 | #include "llvm/ADT/STLExtras.h" |
| 26 | #include "llvm/ADT/Statistic.h" |
| 27 | #include "llvm/Support/Timer.h" |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 28 | #include <algorithm> |
Chris Lattner | 9a92729 | 2003-11-12 23:11:14 +0000 | [diff] [blame] | 29 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 30 | |
Chris Lattner | b29dd0f | 2004-12-08 21:03:56 +0000 | [diff] [blame] | 31 | #define COLLAPSE_ARRAYS_AGGRESSIVELY 0 |
| 32 | |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 33 | namespace { |
Chris Lattner | e92e764 | 2004-02-07 23:58:05 +0000 | [diff] [blame] | 34 | Statistic<> NumFolds ("dsa", "Number of nodes completely folded"); |
| 35 | Statistic<> NumCallNodesMerged("dsa", "Number of call nodes merged"); |
| 36 | Statistic<> NumNodeAllocated ("dsa", "Number of nodes allocated"); |
| 37 | Statistic<> NumDNE ("dsa", "Number of nodes removed by reachability"); |
Chris Lattner | c3f5f77 | 2004-02-08 01:51:48 +0000 | [diff] [blame] | 38 | Statistic<> NumTrivialDNE ("dsa", "Number of nodes trivially removed"); |
| 39 | Statistic<> NumTrivialGlobalDNE("dsa", "Number of globals trivially removed"); |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 40 | }; |
| 41 | |
Chris Lattner | a88a55c | 2004-01-28 02:41:32 +0000 | [diff] [blame] | 42 | #if 1 |
Chris Lattner | 93ddd7e | 2004-01-22 16:36:28 +0000 | [diff] [blame] | 43 | #define TIME_REGION(VARNAME, DESC) \ |
| 44 | NamedRegionTimer VARNAME(DESC) |
| 45 | #else |
| 46 | #define TIME_REGION(VARNAME, DESC) |
| 47 | #endif |
| 48 | |
Chris Lattner | b106043 | 2002-11-07 05:20:53 +0000 | [diff] [blame] | 49 | using namespace DS; |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 50 | |
Chris Lattner | 6f96774 | 2004-10-30 04:05:01 +0000 | [diff] [blame] | 51 | /// isForwarding - Return true if this NodeHandle is forwarding to another |
| 52 | /// one. |
| 53 | bool DSNodeHandle::isForwarding() const { |
| 54 | return N && N->isForwarding(); |
| 55 | } |
| 56 | |
Chris Lattner | 731b2d7 | 2003-02-13 19:09:00 +0000 | [diff] [blame] | 57 | DSNode *DSNodeHandle::HandleForwarding() const { |
Chris Lattner | 4ff0b96 | 2004-02-08 01:27:18 +0000 | [diff] [blame] | 58 | assert(N->isForwarding() && "Can only be invoked if forwarding!"); |
Chris Lattner | 731b2d7 | 2003-02-13 19:09:00 +0000 | [diff] [blame] | 59 | |
| 60 | // Handle node forwarding here! |
| 61 | DSNode *Next = N->ForwardNH.getNode(); // Cause recursive shrinkage |
| 62 | Offset += N->ForwardNH.getOffset(); |
| 63 | |
| 64 | if (--N->NumReferrers == 0) { |
| 65 | // Removing the last referrer to the node, sever the forwarding link |
| 66 | N->stopForwarding(); |
| 67 | } |
| 68 | |
| 69 | N = Next; |
| 70 | N->NumReferrers++; |
| 71 | if (N->Size <= Offset) { |
| 72 | assert(N->Size <= 1 && "Forwarded to shrunk but not collapsed node?"); |
| 73 | Offset = 0; |
| 74 | } |
| 75 | return N; |
| 76 | } |
| 77 | |
Chris Lattner | bb2a28f | 2002-03-26 22:39:06 +0000 | [diff] [blame] | 78 | //===----------------------------------------------------------------------===// |
Chris Lattner | 612f0b7 | 2005-03-22 00:09:45 +0000 | [diff] [blame] | 79 | // DSScalarMap Implementation |
| 80 | //===----------------------------------------------------------------------===// |
| 81 | |
| 82 | DSNodeHandle &DSScalarMap::AddGlobal(GlobalValue *GV) { |
| 83 | assert(ValueMap.count(GV) == 0 && "GV already exists!"); |
| 84 | |
| 85 | // If the node doesn't exist, check to see if it's a global that is |
| 86 | // equated to another global in the program. |
| 87 | EquivalenceClasses<GlobalValue*>::iterator ECI = GlobalECs.findValue(GV); |
| 88 | if (ECI != GlobalECs.end()) { |
| 89 | GlobalValue *Leader = *GlobalECs.findLeader(ECI); |
| 90 | if (Leader != GV) { |
| 91 | GV = Leader; |
| 92 | iterator I = ValueMap.find(GV); |
| 93 | if (I != ValueMap.end()) |
| 94 | return I->second; |
| 95 | } |
| 96 | } |
| 97 | |
| 98 | // Okay, this is either not an equivalenced global or it is the leader, it |
| 99 | // will be inserted into the scalar map now. |
| 100 | GlobalSet.insert(GV); |
| 101 | |
| 102 | return ValueMap.insert(std::make_pair(GV, DSNodeHandle())).first->second; |
| 103 | } |
| 104 | |
| 105 | |
| 106 | //===----------------------------------------------------------------------===// |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 107 | // DSNode Implementation |
| 108 | //===----------------------------------------------------------------------===// |
Chris Lattner | bb2a28f | 2002-03-26 22:39:06 +0000 | [diff] [blame] | 109 | |
Chris Lattner | bd92b73 | 2003-06-19 21:15:11 +0000 | [diff] [blame] | 110 | DSNode::DSNode(const Type *T, DSGraph *G) |
Chris Lattner | 7079386 | 2003-07-02 23:57:05 +0000 | [diff] [blame] | 111 | : NumReferrers(0), Size(0), ParentGraph(G), Ty(Type::VoidTy), NodeType(0) { |
Chris Lattner | 8f0a16e | 2002-10-31 05:45:02 +0000 | [diff] [blame] | 112 | // Add the type entry if it is specified... |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 113 | if (T) mergeTypeInfo(T, 0); |
Chris Lattner | 9857c1a | 2004-02-08 01:05:37 +0000 | [diff] [blame] | 114 | if (G) G->addNode(this); |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 115 | ++NumNodeAllocated; |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 116 | } |
| 117 | |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 118 | // DSNode copy constructor... do not copy over the referrers list! |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 119 | DSNode::DSNode(const DSNode &N, DSGraph *G, bool NullLinks) |
Chris Lattner | 7079386 | 2003-07-02 23:57:05 +0000 | [diff] [blame] | 120 | : NumReferrers(0), Size(N.Size), ParentGraph(G), |
Chris Lattner | f590ced | 2004-03-04 17:06:53 +0000 | [diff] [blame] | 121 | Ty(N.Ty), NodeType(N.NodeType) { |
| 122 | if (!NullLinks) { |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 123 | Links = N.Links; |
Chris Lattner | f590ced | 2004-03-04 17:06:53 +0000 | [diff] [blame] | 124 | Globals = N.Globals; |
| 125 | } else |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 126 | Links.resize(N.Links.size()); // Create the appropriate number of null links |
Chris Lattner | e92e764 | 2004-02-07 23:58:05 +0000 | [diff] [blame] | 127 | G->addNode(this); |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 128 | ++NumNodeAllocated; |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 129 | } |
| 130 | |
Chris Lattner | 15869aa | 2003-11-02 22:27:28 +0000 | [diff] [blame] | 131 | /// getTargetData - Get the target data object used to construct this node. |
| 132 | /// |
| 133 | const TargetData &DSNode::getTargetData() const { |
| 134 | return ParentGraph->getTargetData(); |
| 135 | } |
| 136 | |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 137 | void DSNode::assertOK() const { |
| 138 | assert((Ty != Type::VoidTy || |
| 139 | Ty == Type::VoidTy && (Size == 0 || |
| 140 | (NodeType & DSNode::Array))) && |
| 141 | "Node not OK!"); |
Chris Lattner | 85cfe01 | 2003-07-03 02:03:53 +0000 | [diff] [blame] | 142 | |
| 143 | assert(ParentGraph && "Node has no parent?"); |
Chris Lattner | 62482e5 | 2004-01-28 09:15:42 +0000 | [diff] [blame] | 144 | const DSScalarMap &SM = ParentGraph->getScalarMap(); |
Chris Lattner | 85cfe01 | 2003-07-03 02:03:53 +0000 | [diff] [blame] | 145 | for (unsigned i = 0, e = Globals.size(); i != e; ++i) { |
Chris Lattner | f4f6227 | 2005-03-19 22:23:45 +0000 | [diff] [blame] | 146 | assert(SM.global_count(Globals[i])); |
Chris Lattner | 85cfe01 | 2003-07-03 02:03:53 +0000 | [diff] [blame] | 147 | assert(SM.find(Globals[i])->second.getNode() == this); |
| 148 | } |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 149 | } |
| 150 | |
| 151 | /// forwardNode - Mark this node as being obsolete, and all references to it |
| 152 | /// should be forwarded to the specified node and offset. |
| 153 | /// |
| 154 | void DSNode::forwardNode(DSNode *To, unsigned Offset) { |
| 155 | assert(this != To && "Cannot forward a node to itself!"); |
| 156 | assert(ForwardNH.isNull() && "Already forwarding from this node!"); |
| 157 | if (To->Size <= 1) Offset = 0; |
| 158 | assert((Offset < To->Size || (Offset == To->Size && Offset == 0)) && |
| 159 | "Forwarded offset is wrong!"); |
Chris Lattner | efffdc9 | 2004-07-07 06:12:52 +0000 | [diff] [blame] | 160 | ForwardNH.setTo(To, Offset); |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 161 | NodeType = DEAD; |
| 162 | Size = 0; |
| 163 | Ty = Type::VoidTy; |
Chris Lattner | 4ff0b96 | 2004-02-08 01:27:18 +0000 | [diff] [blame] | 164 | |
| 165 | // Remove this node from the parent graph's Nodes list. |
| 166 | ParentGraph->unlinkNode(this); |
| 167 | ParentGraph = 0; |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 168 | } |
| 169 | |
Chris Lattner | f9ae4c5 | 2002-07-11 20:32:22 +0000 | [diff] [blame] | 170 | // addGlobal - Add an entry for a global value to the Globals list. This also |
| 171 | // marks the node with the 'G' flag if it does not already have it. |
| 172 | // |
| 173 | void DSNode::addGlobal(GlobalValue *GV) { |
Chris Lattner | f4f6227 | 2005-03-19 22:23:45 +0000 | [diff] [blame] | 174 | // First, check to make sure this is the leader if the global is in an |
| 175 | // equivalence class. |
| 176 | GV = getParentGraph()->getScalarMap().getLeaderForGlobal(GV); |
| 177 | |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 178 | // Keep the list sorted. |
Chris Lattner | b3416bc | 2003-02-01 04:01:21 +0000 | [diff] [blame] | 179 | std::vector<GlobalValue*>::iterator I = |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 180 | std::lower_bound(Globals.begin(), Globals.end(), GV); |
| 181 | |
| 182 | if (I == Globals.end() || *I != GV) { |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 183 | Globals.insert(I, GV); |
| 184 | NodeType |= GlobalNode; |
| 185 | } |
Chris Lattner | f9ae4c5 | 2002-07-11 20:32:22 +0000 | [diff] [blame] | 186 | } |
| 187 | |
Chris Lattner | 7cdf321 | 2005-03-20 03:29:54 +0000 | [diff] [blame] | 188 | // removeGlobal - Remove the specified global that is explicitly in the globals |
| 189 | // list. |
| 190 | void DSNode::removeGlobal(GlobalValue *GV) { |
| 191 | std::vector<GlobalValue*>::iterator I = |
| 192 | std::lower_bound(Globals.begin(), Globals.end(), GV); |
| 193 | assert(I != Globals.end() && *I == GV && "Global not in node!"); |
| 194 | Globals.erase(I); |
| 195 | } |
| 196 | |
Chris Lattner | 8f0a16e | 2002-10-31 05:45:02 +0000 | [diff] [blame] | 197 | /// foldNodeCompletely - If we determine that this node has some funny |
| 198 | /// behavior happening to it that we cannot represent, we fold it down to a |
| 199 | /// single, completely pessimistic, node. This node is represented as a |
| 200 | /// single byte with a single TypeEntry of "void". |
| 201 | /// |
| 202 | void DSNode::foldNodeCompletely() { |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 203 | if (isNodeCompletelyFolded()) return; // If this node is already folded... |
Chris Lattner | 8f0a16e | 2002-10-31 05:45:02 +0000 | [diff] [blame] | 204 | |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 205 | ++NumFolds; |
| 206 | |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 207 | // If this node has a size that is <= 1, we don't need to create a forwarding |
| 208 | // node. |
| 209 | if (getSize() <= 1) { |
| 210 | NodeType |= DSNode::Array; |
| 211 | Ty = Type::VoidTy; |
| 212 | Size = 1; |
| 213 | assert(Links.size() <= 1 && "Size is 1, but has more links?"); |
| 214 | Links.resize(1); |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 215 | } else { |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 216 | // Create the node we are going to forward to. This is required because |
| 217 | // some referrers may have an offset that is > 0. By forcing them to |
| 218 | // forward, the forwarder has the opportunity to correct the offset. |
| 219 | DSNode *DestNode = new DSNode(0, ParentGraph); |
| 220 | DestNode->NodeType = NodeType|DSNode::Array; |
| 221 | DestNode->Ty = Type::VoidTy; |
| 222 | DestNode->Size = 1; |
| 223 | DestNode->Globals.swap(Globals); |
| 224 | |
| 225 | // Start forwarding to the destination node... |
| 226 | forwardNode(DestNode, 0); |
| 227 | |
| 228 | if (!Links.empty()) { |
| 229 | DestNode->Links.reserve(1); |
| 230 | |
| 231 | DSNodeHandle NH(DestNode); |
| 232 | DestNode->Links.push_back(Links[0]); |
| 233 | |
| 234 | // If we have links, merge all of our outgoing links together... |
| 235 | for (unsigned i = Links.size()-1; i != 0; --i) |
| 236 | NH.getNode()->Links[0].mergeWith(Links[i]); |
| 237 | Links.clear(); |
| 238 | } else { |
| 239 | DestNode->Links.resize(1); |
| 240 | } |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 241 | } |
Chris Lattner | 8f0a16e | 2002-10-31 05:45:02 +0000 | [diff] [blame] | 242 | } |
Chris Lattner | 076c1f9 | 2002-11-07 06:31:54 +0000 | [diff] [blame] | 243 | |
Chris Lattner | 8f0a16e | 2002-10-31 05:45:02 +0000 | [diff] [blame] | 244 | /// isNodeCompletelyFolded - Return true if this node has been completely |
| 245 | /// folded down to something that can never be expanded, effectively losing |
| 246 | /// all of the field sensitivity that may be present in the node. |
| 247 | /// |
| 248 | bool DSNode::isNodeCompletelyFolded() const { |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 249 | return getSize() == 1 && Ty == Type::VoidTy && isArray(); |
Chris Lattner | 8f0a16e | 2002-10-31 05:45:02 +0000 | [diff] [blame] | 250 | } |
| 251 | |
Chris Lattner | 82c6c72 | 2005-03-20 02:41:38 +0000 | [diff] [blame] | 252 | /// addFullGlobalsList - Compute the full set of global values that are |
| 253 | /// represented by this node. Unlike getGlobalsList(), this requires fair |
| 254 | /// amount of work to compute, so don't treat this method call as free. |
| 255 | void DSNode::addFullGlobalsList(std::vector<GlobalValue*> &List) const { |
| 256 | if (globals_begin() == globals_end()) return; |
| 257 | |
| 258 | EquivalenceClasses<GlobalValue*> &EC = getParentGraph()->getGlobalECs(); |
| 259 | |
| 260 | for (globals_iterator I = globals_begin(), E = globals_end(); I != E; ++I) { |
| 261 | EquivalenceClasses<GlobalValue*>::iterator ECI = EC.findValue(*I); |
| 262 | if (ECI == EC.end()) |
| 263 | List.push_back(*I); |
| 264 | else |
| 265 | List.insert(List.end(), EC.member_begin(ECI), EC.member_end()); |
| 266 | } |
| 267 | } |
| 268 | |
| 269 | /// addFullFunctionList - Identical to addFullGlobalsList, but only return the |
| 270 | /// functions in the full list. |
| 271 | void DSNode::addFullFunctionList(std::vector<Function*> &List) const { |
| 272 | if (globals_begin() == globals_end()) return; |
| 273 | |
| 274 | EquivalenceClasses<GlobalValue*> &EC = getParentGraph()->getGlobalECs(); |
| 275 | |
| 276 | for (globals_iterator I = globals_begin(), E = globals_end(); I != E; ++I) { |
| 277 | EquivalenceClasses<GlobalValue*>::iterator ECI = EC.findValue(*I); |
| 278 | if (ECI == EC.end()) { |
| 279 | if (Function *F = dyn_cast<Function>(*I)) |
| 280 | List.push_back(F); |
| 281 | } else { |
| 282 | for (EquivalenceClasses<GlobalValue*>::member_iterator MI = |
| 283 | EC.member_begin(ECI), E = EC.member_end(); MI != E; ++MI) |
| 284 | if (Function *F = dyn_cast<Function>(*MI)) |
| 285 | List.push_back(F); |
| 286 | } |
| 287 | } |
| 288 | } |
| 289 | |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 290 | namespace { |
| 291 | /// TypeElementWalker Class - Used for implementation of physical subtyping... |
| 292 | /// |
| 293 | class TypeElementWalker { |
| 294 | struct StackState { |
| 295 | const Type *Ty; |
| 296 | unsigned Offset; |
| 297 | unsigned Idx; |
| 298 | StackState(const Type *T, unsigned Off = 0) |
| 299 | : Ty(T), Offset(Off), Idx(0) {} |
| 300 | }; |
| 301 | |
| 302 | std::vector<StackState> Stack; |
Chris Lattner | 15869aa | 2003-11-02 22:27:28 +0000 | [diff] [blame] | 303 | const TargetData &TD; |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 304 | public: |
Chris Lattner | 15869aa | 2003-11-02 22:27:28 +0000 | [diff] [blame] | 305 | TypeElementWalker(const Type *T, const TargetData &td) : TD(td) { |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 306 | Stack.push_back(T); |
| 307 | StepToLeaf(); |
| 308 | } |
| 309 | |
| 310 | bool isDone() const { return Stack.empty(); } |
| 311 | const Type *getCurrentType() const { return Stack.back().Ty; } |
| 312 | unsigned getCurrentOffset() const { return Stack.back().Offset; } |
| 313 | |
| 314 | void StepToNextType() { |
| 315 | PopStackAndAdvance(); |
| 316 | StepToLeaf(); |
| 317 | } |
| 318 | |
| 319 | private: |
| 320 | /// PopStackAndAdvance - Pop the current element off of the stack and |
| 321 | /// advance the underlying element to the next contained member. |
| 322 | void PopStackAndAdvance() { |
| 323 | assert(!Stack.empty() && "Cannot pop an empty stack!"); |
| 324 | Stack.pop_back(); |
| 325 | while (!Stack.empty()) { |
| 326 | StackState &SS = Stack.back(); |
| 327 | if (const StructType *ST = dyn_cast<StructType>(SS.Ty)) { |
| 328 | ++SS.Idx; |
Chris Lattner | d21cd80 | 2004-02-09 04:37:31 +0000 | [diff] [blame] | 329 | if (SS.Idx != ST->getNumElements()) { |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 330 | const StructLayout *SL = TD.getStructLayout(ST); |
Chris Lattner | 507bdf9 | 2005-01-12 04:51:37 +0000 | [diff] [blame] | 331 | SS.Offset += |
| 332 | unsigned(SL->MemberOffsets[SS.Idx]-SL->MemberOffsets[SS.Idx-1]); |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 333 | return; |
| 334 | } |
| 335 | Stack.pop_back(); // At the end of the structure |
| 336 | } else { |
| 337 | const ArrayType *AT = cast<ArrayType>(SS.Ty); |
| 338 | ++SS.Idx; |
| 339 | if (SS.Idx != AT->getNumElements()) { |
Chris Lattner | 507bdf9 | 2005-01-12 04:51:37 +0000 | [diff] [blame] | 340 | SS.Offset += unsigned(TD.getTypeSize(AT->getElementType())); |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 341 | return; |
| 342 | } |
| 343 | Stack.pop_back(); // At the end of the array |
| 344 | } |
| 345 | } |
| 346 | } |
| 347 | |
| 348 | /// StepToLeaf - Used by physical subtyping to move to the first leaf node |
| 349 | /// on the type stack. |
| 350 | void StepToLeaf() { |
| 351 | if (Stack.empty()) return; |
| 352 | while (!Stack.empty() && !Stack.back().Ty->isFirstClassType()) { |
| 353 | StackState &SS = Stack.back(); |
| 354 | if (const StructType *ST = dyn_cast<StructType>(SS.Ty)) { |
Chris Lattner | d21cd80 | 2004-02-09 04:37:31 +0000 | [diff] [blame] | 355 | if (ST->getNumElements() == 0) { |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 356 | assert(SS.Idx == 0); |
| 357 | PopStackAndAdvance(); |
| 358 | } else { |
| 359 | // Step into the structure... |
Chris Lattner | d21cd80 | 2004-02-09 04:37:31 +0000 | [diff] [blame] | 360 | assert(SS.Idx < ST->getNumElements()); |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 361 | const StructLayout *SL = TD.getStructLayout(ST); |
Chris Lattner | d21cd80 | 2004-02-09 04:37:31 +0000 | [diff] [blame] | 362 | Stack.push_back(StackState(ST->getElementType(SS.Idx), |
Chris Lattner | 507bdf9 | 2005-01-12 04:51:37 +0000 | [diff] [blame] | 363 | SS.Offset+unsigned(SL->MemberOffsets[SS.Idx]))); |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 364 | } |
| 365 | } else { |
| 366 | const ArrayType *AT = cast<ArrayType>(SS.Ty); |
| 367 | if (AT->getNumElements() == 0) { |
| 368 | assert(SS.Idx == 0); |
| 369 | PopStackAndAdvance(); |
| 370 | } else { |
| 371 | // Step into the array... |
| 372 | assert(SS.Idx < AT->getNumElements()); |
| 373 | Stack.push_back(StackState(AT->getElementType(), |
| 374 | SS.Offset+SS.Idx* |
Chris Lattner | 507bdf9 | 2005-01-12 04:51:37 +0000 | [diff] [blame] | 375 | unsigned(TD.getTypeSize(AT->getElementType())))); |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 376 | } |
| 377 | } |
| 378 | } |
| 379 | } |
| 380 | }; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 381 | } // end anonymous namespace |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 382 | |
| 383 | /// ElementTypesAreCompatible - Check to see if the specified types are |
| 384 | /// "physically" compatible. If so, return true, else return false. We only |
Chris Lattner | dbfe36e | 2003-11-02 21:02:20 +0000 | [diff] [blame] | 385 | /// have to check the fields in T1: T2 may be larger than T1. If AllowLargerT1 |
| 386 | /// is true, then we also allow a larger T1. |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 387 | /// |
Chris Lattner | dbfe36e | 2003-11-02 21:02:20 +0000 | [diff] [blame] | 388 | static bool ElementTypesAreCompatible(const Type *T1, const Type *T2, |
Chris Lattner | 15869aa | 2003-11-02 22:27:28 +0000 | [diff] [blame] | 389 | bool AllowLargerT1, const TargetData &TD){ |
| 390 | TypeElementWalker T1W(T1, TD), T2W(T2, TD); |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 391 | |
| 392 | while (!T1W.isDone() && !T2W.isDone()) { |
| 393 | if (T1W.getCurrentOffset() != T2W.getCurrentOffset()) |
| 394 | return false; |
| 395 | |
| 396 | const Type *T1 = T1W.getCurrentType(); |
| 397 | const Type *T2 = T2W.getCurrentType(); |
| 398 | if (T1 != T2 && !T1->isLosslesslyConvertibleTo(T2)) |
| 399 | return false; |
| 400 | |
| 401 | T1W.StepToNextType(); |
| 402 | T2W.StepToNextType(); |
| 403 | } |
| 404 | |
Chris Lattner | dbfe36e | 2003-11-02 21:02:20 +0000 | [diff] [blame] | 405 | return AllowLargerT1 || T1W.isDone(); |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 406 | } |
| 407 | |
| 408 | |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 409 | /// mergeTypeInfo - This method merges the specified type into the current node |
| 410 | /// at the specified offset. This may update the current node's type record if |
| 411 | /// this gives more information to the node, it may do nothing to the node if |
| 412 | /// this information is already known, or it may merge the node completely (and |
| 413 | /// return true) if the information is incompatible with what is already known. |
Chris Lattner | 7b7200c | 2002-10-02 04:57:39 +0000 | [diff] [blame] | 414 | /// |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 415 | /// This method returns true if the node is completely folded, otherwise false. |
| 416 | /// |
Chris Lattner | 088b639 | 2003-03-03 17:13:31 +0000 | [diff] [blame] | 417 | bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset, |
| 418 | bool FoldIfIncompatible) { |
Chris Lattner | 15869aa | 2003-11-02 22:27:28 +0000 | [diff] [blame] | 419 | const TargetData &TD = getTargetData(); |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 420 | // Check to make sure the Size member is up-to-date. Size can be one of the |
| 421 | // following: |
| 422 | // Size = 0, Ty = Void: Nothing is known about this node. |
| 423 | // Size = 0, Ty = FnTy: FunctionPtr doesn't have a size, so we use zero |
| 424 | // Size = 1, Ty = Void, Array = 1: The node is collapsed |
| 425 | // Otherwise, sizeof(Ty) = Size |
| 426 | // |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 427 | assert(((Size == 0 && Ty == Type::VoidTy && !isArray()) || |
| 428 | (Size == 0 && !Ty->isSized() && !isArray()) || |
| 429 | (Size == 1 && Ty == Type::VoidTy && isArray()) || |
| 430 | (Size == 0 && !Ty->isSized() && !isArray()) || |
| 431 | (TD.getTypeSize(Ty) == Size)) && |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 432 | "Size member of DSNode doesn't match the type structure!"); |
| 433 | assert(NewTy != Type::VoidTy && "Cannot merge void type into DSNode!"); |
Chris Lattner | 7b7200c | 2002-10-02 04:57:39 +0000 | [diff] [blame] | 434 | |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 435 | if (Offset == 0 && NewTy == Ty) |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 436 | return false; // This should be a common case, handle it efficiently |
Chris Lattner | 7b7200c | 2002-10-02 04:57:39 +0000 | [diff] [blame] | 437 | |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 438 | // Return true immediately if the node is completely folded. |
| 439 | if (isNodeCompletelyFolded()) return true; |
| 440 | |
Chris Lattner | 23f83dc | 2002-11-08 22:49:57 +0000 | [diff] [blame] | 441 | // If this is an array type, eliminate the outside arrays because they won't |
| 442 | // be used anyway. This greatly reduces the size of large static arrays used |
| 443 | // as global variables, for example. |
| 444 | // |
Chris Lattner | d888893 | 2002-11-09 19:25:27 +0000 | [diff] [blame] | 445 | bool WillBeArray = false; |
Chris Lattner | 23f83dc | 2002-11-08 22:49:57 +0000 | [diff] [blame] | 446 | while (const ArrayType *AT = dyn_cast<ArrayType>(NewTy)) { |
| 447 | // FIXME: we might want to keep small arrays, but must be careful about |
| 448 | // things like: [2 x [10000 x int*]] |
| 449 | NewTy = AT->getElementType(); |
Chris Lattner | d888893 | 2002-11-09 19:25:27 +0000 | [diff] [blame] | 450 | WillBeArray = true; |
Chris Lattner | 23f83dc | 2002-11-08 22:49:57 +0000 | [diff] [blame] | 451 | } |
| 452 | |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 453 | // Figure out how big the new type we're merging in is... |
Chris Lattner | 507bdf9 | 2005-01-12 04:51:37 +0000 | [diff] [blame] | 454 | unsigned NewTySize = NewTy->isSized() ? (unsigned)TD.getTypeSize(NewTy) : 0; |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 455 | |
| 456 | // Otherwise check to see if we can fold this type into the current node. If |
| 457 | // we can't, we fold the node completely, if we can, we potentially update our |
| 458 | // internal state. |
| 459 | // |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 460 | if (Ty == Type::VoidTy) { |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 461 | // If this is the first type that this node has seen, just accept it without |
| 462 | // question.... |
Chris Lattner | dbfe36e | 2003-11-02 21:02:20 +0000 | [diff] [blame] | 463 | assert(Offset == 0 && !isArray() && |
| 464 | "Cannot have an offset into a void node!"); |
Chris Lattner | ec3f5c4 | 2005-03-17 05:25:34 +0000 | [diff] [blame] | 465 | |
| 466 | // If this node would have to have an unreasonable number of fields, just |
| 467 | // collapse it. This can occur for fortran common blocks, which have stupid |
| 468 | // things like { [100000000 x double], [1000000 x double] }. |
| 469 | unsigned NumFields = (NewTySize+DS::PointerSize-1) >> DS::PointerShift; |
| 470 | if (NumFields > 64) { |
| 471 | foldNodeCompletely(); |
| 472 | return true; |
| 473 | } |
| 474 | |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 475 | Ty = NewTy; |
| 476 | NodeType &= ~Array; |
| 477 | if (WillBeArray) NodeType |= Array; |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 478 | Size = NewTySize; |
| 479 | |
| 480 | // Calculate the number of outgoing links from this node. |
Chris Lattner | ec3f5c4 | 2005-03-17 05:25:34 +0000 | [diff] [blame] | 481 | Links.resize(NumFields); |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 482 | return false; |
Chris Lattner | 7b7200c | 2002-10-02 04:57:39 +0000 | [diff] [blame] | 483 | } |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 484 | |
| 485 | // Handle node expansion case here... |
| 486 | if (Offset+NewTySize > Size) { |
| 487 | // It is illegal to grow this node if we have treated it as an array of |
| 488 | // objects... |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 489 | if (isArray()) { |
Chris Lattner | 088b639 | 2003-03-03 17:13:31 +0000 | [diff] [blame] | 490 | if (FoldIfIncompatible) foldNodeCompletely(); |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 491 | return true; |
| 492 | } |
| 493 | |
| 494 | if (Offset) { // We could handle this case, but we don't for now... |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 495 | std::cerr << "UNIMP: Trying to merge a growth type into " |
| 496 | << "offset != 0: Collapsing!\n"; |
Chris Lattner | 088b639 | 2003-03-03 17:13:31 +0000 | [diff] [blame] | 497 | if (FoldIfIncompatible) foldNodeCompletely(); |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 498 | return true; |
| 499 | } |
| 500 | |
| 501 | // Okay, the situation is nice and simple, we are trying to merge a type in |
| 502 | // at offset 0 that is bigger than our current type. Implement this by |
| 503 | // switching to the new type and then merge in the smaller one, which should |
| 504 | // hit the other code path here. If the other code path decides it's not |
| 505 | // ok, it will collapse the node as appropriate. |
| 506 | // |
Chris Lattner | ec3f5c4 | 2005-03-17 05:25:34 +0000 | [diff] [blame] | 507 | |
| 508 | // If this node would have to have an unreasonable number of fields, just |
| 509 | // collapse it. This can occur for fortran common blocks, which have stupid |
| 510 | // things like { [100000000 x double], [1000000 x double] }. |
| 511 | unsigned NumFields = (NewTySize+DS::PointerSize-1) >> DS::PointerShift; |
| 512 | if (NumFields > 64) { |
| 513 | foldNodeCompletely(); |
| 514 | return true; |
| 515 | } |
| 516 | |
Chris Lattner | 94f8470 | 2005-03-17 19:56:56 +0000 | [diff] [blame] | 517 | const Type *OldTy = Ty; |
| 518 | Ty = NewTy; |
| 519 | NodeType &= ~Array; |
| 520 | if (WillBeArray) NodeType |= Array; |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 521 | Size = NewTySize; |
| 522 | |
| 523 | // Must grow links to be the appropriate size... |
Chris Lattner | 94f8470 | 2005-03-17 19:56:56 +0000 | [diff] [blame] | 524 | Links.resize(NumFields); |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 525 | |
| 526 | // Merge in the old type now... which is guaranteed to be smaller than the |
| 527 | // "current" type. |
| 528 | return mergeTypeInfo(OldTy, 0); |
| 529 | } |
| 530 | |
Chris Lattner | f17b39a | 2002-11-07 04:59:28 +0000 | [diff] [blame] | 531 | assert(Offset <= Size && |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 532 | "Cannot merge something into a part of our type that doesn't exist!"); |
| 533 | |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 534 | // Find the section of Ty that NewTy overlaps with... first we find the |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 535 | // type that starts at offset Offset. |
| 536 | // |
| 537 | unsigned O = 0; |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 538 | const Type *SubType = Ty; |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 539 | while (O < Offset) { |
| 540 | assert(Offset-O < TD.getTypeSize(SubType) && "Offset out of range!"); |
| 541 | |
Chris Lattner | f70c22b | 2004-06-17 18:19:28 +0000 | [diff] [blame] | 542 | switch (SubType->getTypeID()) { |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 543 | case Type::StructTyID: { |
| 544 | const StructType *STy = cast<StructType>(SubType); |
| 545 | const StructLayout &SL = *TD.getStructLayout(STy); |
Chris Lattner | 2787e03 | 2005-03-13 19:05:05 +0000 | [diff] [blame] | 546 | unsigned i = SL.getElementContainingOffset(Offset-O); |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 547 | |
| 548 | // The offset we are looking for must be in the i'th element... |
Chris Lattner | d21cd80 | 2004-02-09 04:37:31 +0000 | [diff] [blame] | 549 | SubType = STy->getElementType(i); |
Chris Lattner | 507bdf9 | 2005-01-12 04:51:37 +0000 | [diff] [blame] | 550 | O += (unsigned)SL.MemberOffsets[i]; |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 551 | break; |
| 552 | } |
| 553 | case Type::ArrayTyID: { |
| 554 | SubType = cast<ArrayType>(SubType)->getElementType(); |
Chris Lattner | 507bdf9 | 2005-01-12 04:51:37 +0000 | [diff] [blame] | 555 | unsigned ElSize = (unsigned)TD.getTypeSize(SubType); |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 556 | unsigned Remainder = (Offset-O) % ElSize; |
| 557 | O = Offset-Remainder; |
| 558 | break; |
| 559 | } |
| 560 | default: |
Chris Lattner | 088b639 | 2003-03-03 17:13:31 +0000 | [diff] [blame] | 561 | if (FoldIfIncompatible) foldNodeCompletely(); |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 562 | return true; |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 563 | } |
| 564 | } |
| 565 | |
| 566 | assert(O == Offset && "Could not achieve the correct offset!"); |
| 567 | |
| 568 | // If we found our type exactly, early exit |
| 569 | if (SubType == NewTy) return false; |
| 570 | |
Misha Brukman | 96a8bd7 | 2004-04-29 04:05:30 +0000 | [diff] [blame] | 571 | // Differing function types don't require us to merge. They are not values |
| 572 | // anyway. |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 573 | if (isa<FunctionType>(SubType) && |
| 574 | isa<FunctionType>(NewTy)) return false; |
| 575 | |
Chris Lattner | 507bdf9 | 2005-01-12 04:51:37 +0000 | [diff] [blame] | 576 | unsigned SubTypeSize = SubType->isSized() ? |
| 577 | (unsigned)TD.getTypeSize(SubType) : 0; |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 578 | |
| 579 | // Ok, we are getting desperate now. Check for physical subtyping, where we |
| 580 | // just require each element in the node to be compatible. |
Chris Lattner | 06e24c8 | 2003-06-29 22:36:31 +0000 | [diff] [blame] | 581 | if (NewTySize <= SubTypeSize && NewTySize && NewTySize < 256 && |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 582 | SubTypeSize && SubTypeSize < 256 && |
Chris Lattner | 15869aa | 2003-11-02 22:27:28 +0000 | [diff] [blame] | 583 | ElementTypesAreCompatible(NewTy, SubType, !isArray(), TD)) |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 584 | return false; |
| 585 | |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 586 | // Okay, so we found the leader type at the offset requested. Search the list |
| 587 | // of types that starts at this offset. If SubType is currently an array or |
| 588 | // structure, the type desired may actually be the first element of the |
| 589 | // composite type... |
| 590 | // |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 591 | unsigned PadSize = SubTypeSize; // Size, including pad memory which is ignored |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 592 | while (SubType != NewTy) { |
| 593 | const Type *NextSubType = 0; |
Chris Lattner | bf10f05 | 2002-11-09 00:49:05 +0000 | [diff] [blame] | 594 | unsigned NextSubTypeSize = 0; |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 595 | unsigned NextPadSize = 0; |
Chris Lattner | f70c22b | 2004-06-17 18:19:28 +0000 | [diff] [blame] | 596 | switch (SubType->getTypeID()) { |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 597 | case Type::StructTyID: { |
| 598 | const StructType *STy = cast<StructType>(SubType); |
| 599 | const StructLayout &SL = *TD.getStructLayout(STy); |
| 600 | if (SL.MemberOffsets.size() > 1) |
Chris Lattner | 507bdf9 | 2005-01-12 04:51:37 +0000 | [diff] [blame] | 601 | NextPadSize = (unsigned)SL.MemberOffsets[1]; |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 602 | else |
| 603 | NextPadSize = SubTypeSize; |
Chris Lattner | d21cd80 | 2004-02-09 04:37:31 +0000 | [diff] [blame] | 604 | NextSubType = STy->getElementType(0); |
Chris Lattner | 507bdf9 | 2005-01-12 04:51:37 +0000 | [diff] [blame] | 605 | NextSubTypeSize = (unsigned)TD.getTypeSize(NextSubType); |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 606 | break; |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 607 | } |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 608 | case Type::ArrayTyID: |
| 609 | NextSubType = cast<ArrayType>(SubType)->getElementType(); |
Chris Lattner | 507bdf9 | 2005-01-12 04:51:37 +0000 | [diff] [blame] | 610 | NextSubTypeSize = (unsigned)TD.getTypeSize(NextSubType); |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 611 | NextPadSize = NextSubTypeSize; |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 612 | break; |
| 613 | default: ; |
| 614 | // fall out |
| 615 | } |
| 616 | |
| 617 | if (NextSubType == 0) |
| 618 | break; // In the default case, break out of the loop |
| 619 | |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 620 | if (NextPadSize < NewTySize) |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 621 | break; // Don't allow shrinking to a smaller type than NewTySize |
| 622 | SubType = NextSubType; |
| 623 | SubTypeSize = NextSubTypeSize; |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 624 | PadSize = NextPadSize; |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 625 | } |
| 626 | |
| 627 | // If we found the type exactly, return it... |
| 628 | if (SubType == NewTy) |
| 629 | return false; |
| 630 | |
| 631 | // Check to see if we have a compatible, but different type... |
| 632 | if (NewTySize == SubTypeSize) { |
Misha Brukman | f117cc9 | 2003-05-20 18:45:36 +0000 | [diff] [blame] | 633 | // Check to see if this type is obviously convertible... int -> uint f.e. |
| 634 | if (NewTy->isLosslesslyConvertibleTo(SubType)) |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 635 | return false; |
| 636 | |
| 637 | // Check to see if we have a pointer & integer mismatch going on here, |
| 638 | // loading a pointer as a long, for example. |
| 639 | // |
| 640 | if (SubType->isInteger() && isa<PointerType>(NewTy) || |
| 641 | NewTy->isInteger() && isa<PointerType>(SubType)) |
| 642 | return false; |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 643 | } else if (NewTySize > SubTypeSize && NewTySize <= PadSize) { |
| 644 | // We are accessing the field, plus some structure padding. Ignore the |
| 645 | // structure padding. |
| 646 | return false; |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 647 | } |
| 648 | |
Chris Lattner | 58f98d0 | 2003-07-02 04:38:49 +0000 | [diff] [blame] | 649 | Module *M = 0; |
Chris Lattner | a5f47ea | 2005-03-15 16:55:04 +0000 | [diff] [blame] | 650 | if (getParentGraph()->retnodes_begin() != getParentGraph()->retnodes_end()) |
| 651 | M = getParentGraph()->retnodes_begin()->first->getParent(); |
Chris Lattner | 58f98d0 | 2003-07-02 04:38:49 +0000 | [diff] [blame] | 652 | DEBUG(std::cerr << "MergeTypeInfo Folding OrigTy: "; |
| 653 | WriteTypeSymbolic(std::cerr, Ty, M) << "\n due to:"; |
| 654 | WriteTypeSymbolic(std::cerr, NewTy, M) << " @ " << Offset << "!\n" |
| 655 | << "SubType: "; |
| 656 | WriteTypeSymbolic(std::cerr, SubType, M) << "\n\n"); |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 657 | |
Chris Lattner | 088b639 | 2003-03-03 17:13:31 +0000 | [diff] [blame] | 658 | if (FoldIfIncompatible) foldNodeCompletely(); |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 659 | return true; |
Chris Lattner | 7b7200c | 2002-10-02 04:57:39 +0000 | [diff] [blame] | 660 | } |
| 661 | |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 662 | |
| 663 | |
Misha Brukman | 96a8bd7 | 2004-04-29 04:05:30 +0000 | [diff] [blame] | 664 | /// addEdgeTo - Add an edge from the current node to the specified node. This |
| 665 | /// can cause merging of nodes in the graph. |
| 666 | /// |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 667 | void DSNode::addEdgeTo(unsigned Offset, const DSNodeHandle &NH) { |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 668 | if (NH.isNull()) return; // Nothing to do |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 669 | |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 670 | DSNodeHandle &ExistingEdge = getLink(Offset); |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 671 | if (!ExistingEdge.isNull()) { |
Chris Lattner | 7b7200c | 2002-10-02 04:57:39 +0000 | [diff] [blame] | 672 | // Merge the two nodes... |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 673 | ExistingEdge.mergeWith(NH); |
Chris Lattner | 7b7200c | 2002-10-02 04:57:39 +0000 | [diff] [blame] | 674 | } else { // No merging to perform... |
| 675 | setLink(Offset, NH); // Just force a link in there... |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 676 | } |
Chris Lattner | 7b7200c | 2002-10-02 04:57:39 +0000 | [diff] [blame] | 677 | } |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 678 | |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 679 | |
Misha Brukman | 96a8bd7 | 2004-04-29 04:05:30 +0000 | [diff] [blame] | 680 | /// MergeSortedVectors - Efficiently merge a vector into another vector where |
| 681 | /// duplicates are not allowed and both are sorted. This assumes that 'T's are |
| 682 | /// efficiently copyable and have sane comparison semantics. |
| 683 | /// |
Chris Lattner | b3416bc | 2003-02-01 04:01:21 +0000 | [diff] [blame] | 684 | static void MergeSortedVectors(std::vector<GlobalValue*> &Dest, |
| 685 | const std::vector<GlobalValue*> &Src) { |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 686 | // By far, the most common cases will be the simple ones. In these cases, |
| 687 | // avoid having to allocate a temporary vector... |
| 688 | // |
| 689 | if (Src.empty()) { // Nothing to merge in... |
| 690 | return; |
| 691 | } else if (Dest.empty()) { // Just copy the result in... |
| 692 | Dest = Src; |
| 693 | } else if (Src.size() == 1) { // Insert a single element... |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 694 | const GlobalValue *V = Src[0]; |
Chris Lattner | b3416bc | 2003-02-01 04:01:21 +0000 | [diff] [blame] | 695 | std::vector<GlobalValue*>::iterator I = |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 696 | std::lower_bound(Dest.begin(), Dest.end(), V); |
| 697 | if (I == Dest.end() || *I != Src[0]) // If not already contained... |
| 698 | Dest.insert(I, Src[0]); |
| 699 | } else if (Dest.size() == 1) { |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 700 | GlobalValue *Tmp = Dest[0]; // Save value in temporary... |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 701 | Dest = Src; // Copy over list... |
Chris Lattner | b3416bc | 2003-02-01 04:01:21 +0000 | [diff] [blame] | 702 | std::vector<GlobalValue*>::iterator I = |
Chris Lattner | 5190ce8 | 2002-11-12 07:20:45 +0000 | [diff] [blame] | 703 | std::lower_bound(Dest.begin(), Dest.end(), Tmp); |
| 704 | if (I == Dest.end() || *I != Tmp) // If not already contained... |
| 705 | Dest.insert(I, Tmp); |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 706 | |
| 707 | } else { |
| 708 | // Make a copy to the side of Dest... |
Chris Lattner | b3416bc | 2003-02-01 04:01:21 +0000 | [diff] [blame] | 709 | std::vector<GlobalValue*> Old(Dest); |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 710 | |
| 711 | // Make space for all of the type entries now... |
| 712 | Dest.resize(Dest.size()+Src.size()); |
| 713 | |
| 714 | // Merge the two sorted ranges together... into Dest. |
| 715 | std::merge(Old.begin(), Old.end(), Src.begin(), Src.end(), Dest.begin()); |
| 716 | |
| 717 | // Now erase any duplicate entries that may have accumulated into the |
| 718 | // vectors (because they were in both of the input sets) |
| 719 | Dest.erase(std::unique(Dest.begin(), Dest.end()), Dest.end()); |
| 720 | } |
| 721 | } |
| 722 | |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 723 | void DSNode::mergeGlobals(const std::vector<GlobalValue*> &RHS) { |
| 724 | MergeSortedVectors(Globals, RHS); |
| 725 | } |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 726 | |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 727 | // MergeNodes - Helper function for DSNode::mergeWith(). |
Vikram S. Adve | 2b7a92c | 2002-12-06 21:15:21 +0000 | [diff] [blame] | 728 | // This function does the hard work of merging two nodes, CurNodeH |
| 729 | // and NH after filtering out trivial cases and making sure that |
| 730 | // CurNodeH.offset >= NH.offset. |
| 731 | // |
| 732 | // ***WARNING*** |
| 733 | // Since merging may cause either node to go away, we must always |
| 734 | // use the node-handles to refer to the nodes. These node handles are |
| 735 | // automatically updated during merging, so will always provide access |
| 736 | // to the correct node after a merge. |
| 737 | // |
| 738 | void DSNode::MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH) { |
| 739 | assert(CurNodeH.getOffset() >= NH.getOffset() && |
| 740 | "This should have been enforced in the caller."); |
Chris Lattner | f590ced | 2004-03-04 17:06:53 +0000 | [diff] [blame] | 741 | assert(CurNodeH.getNode()->getParentGraph()==NH.getNode()->getParentGraph() && |
| 742 | "Cannot merge two nodes that are not in the same graph!"); |
Vikram S. Adve | 2b7a92c | 2002-12-06 21:15:21 +0000 | [diff] [blame] | 743 | |
| 744 | // Now we know that Offset >= NH.Offset, so convert it so our "Offset" (with |
| 745 | // respect to NH.Offset) is now zero. NOffset is the distance from the base |
| 746 | // of our object that N starts from. |
| 747 | // |
| 748 | unsigned NOffset = CurNodeH.getOffset()-NH.getOffset(); |
| 749 | unsigned NSize = NH.getNode()->getSize(); |
| 750 | |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 751 | // If the two nodes are of different size, and the smaller node has the array |
| 752 | // bit set, collapse! |
| 753 | if (NSize != CurNodeH.getNode()->getSize()) { |
Chris Lattner | b29dd0f | 2004-12-08 21:03:56 +0000 | [diff] [blame] | 754 | #if COLLAPSE_ARRAYS_AGGRESSIVELY |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 755 | if (NSize < CurNodeH.getNode()->getSize()) { |
| 756 | if (NH.getNode()->isArray()) |
| 757 | NH.getNode()->foldNodeCompletely(); |
| 758 | } else if (CurNodeH.getNode()->isArray()) { |
| 759 | NH.getNode()->foldNodeCompletely(); |
| 760 | } |
Chris Lattner | b29dd0f | 2004-12-08 21:03:56 +0000 | [diff] [blame] | 761 | #endif |
Chris Lattner | 5c5b10f | 2003-06-29 20:27:45 +0000 | [diff] [blame] | 762 | } |
| 763 | |
| 764 | // Merge the type entries of the two nodes together... |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 765 | if (NH.getNode()->Ty != Type::VoidTy) |
Vikram S. Adve | 2b7a92c | 2002-12-06 21:15:21 +0000 | [diff] [blame] | 766 | CurNodeH.getNode()->mergeTypeInfo(NH.getNode()->Ty, NOffset); |
Chris Lattner | bd92b73 | 2003-06-19 21:15:11 +0000 | [diff] [blame] | 767 | assert(!CurNodeH.getNode()->isDeadNode()); |
Vikram S. Adve | 2b7a92c | 2002-12-06 21:15:21 +0000 | [diff] [blame] | 768 | |
| 769 | // If we are merging a node with a completely folded node, then both nodes are |
| 770 | // now completely folded. |
| 771 | // |
| 772 | if (CurNodeH.getNode()->isNodeCompletelyFolded()) { |
| 773 | if (!NH.getNode()->isNodeCompletelyFolded()) { |
| 774 | NH.getNode()->foldNodeCompletely(); |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 775 | assert(NH.getNode() && NH.getOffset() == 0 && |
| 776 | "folding did not make offset 0?"); |
Vikram S. Adve | 2b7a92c | 2002-12-06 21:15:21 +0000 | [diff] [blame] | 777 | NOffset = NH.getOffset(); |
| 778 | NSize = NH.getNode()->getSize(); |
| 779 | assert(NOffset == 0 && NSize == 1); |
| 780 | } |
| 781 | } else if (NH.getNode()->isNodeCompletelyFolded()) { |
| 782 | CurNodeH.getNode()->foldNodeCompletely(); |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 783 | assert(CurNodeH.getNode() && CurNodeH.getOffset() == 0 && |
| 784 | "folding did not make offset 0?"); |
Vikram S. Adve | 2b7a92c | 2002-12-06 21:15:21 +0000 | [diff] [blame] | 785 | NSize = NH.getNode()->getSize(); |
Chris Lattner | 6f96774 | 2004-10-30 04:05:01 +0000 | [diff] [blame] | 786 | NOffset = NH.getOffset(); |
Vikram S. Adve | 2b7a92c | 2002-12-06 21:15:21 +0000 | [diff] [blame] | 787 | assert(NOffset == 0 && NSize == 1); |
| 788 | } |
| 789 | |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 790 | DSNode *N = NH.getNode(); |
| 791 | if (CurNodeH.getNode() == N || N == 0) return; |
Chris Lattner | bd92b73 | 2003-06-19 21:15:11 +0000 | [diff] [blame] | 792 | assert(!CurNodeH.getNode()->isDeadNode()); |
| 793 | |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 794 | // Merge the NodeType information. |
Chris Lattner | bd92b73 | 2003-06-19 21:15:11 +0000 | [diff] [blame] | 795 | CurNodeH.getNode()->NodeType |= N->NodeType; |
Vikram S. Adve | 2b7a92c | 2002-12-06 21:15:21 +0000 | [diff] [blame] | 796 | |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 797 | // Start forwarding to the new node! |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 798 | N->forwardNode(CurNodeH.getNode(), NOffset); |
Chris Lattner | bd92b73 | 2003-06-19 21:15:11 +0000 | [diff] [blame] | 799 | assert(!CurNodeH.getNode()->isDeadNode()); |
Vikram S. Adve | 2b7a92c | 2002-12-06 21:15:21 +0000 | [diff] [blame] | 800 | |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 801 | // Make all of the outgoing links of N now be outgoing links of CurNodeH. |
| 802 | // |
| 803 | for (unsigned i = 0; i < N->getNumLinks(); ++i) { |
| 804 | DSNodeHandle &Link = N->getLink(i << DS::PointerShift); |
Vikram S. Adve | 2b7a92c | 2002-12-06 21:15:21 +0000 | [diff] [blame] | 805 | if (Link.getNode()) { |
| 806 | // Compute the offset into the current node at which to |
| 807 | // merge this link. In the common case, this is a linear |
| 808 | // relation to the offset in the original node (with |
| 809 | // wrapping), but if the current node gets collapsed due to |
| 810 | // recursive merging, we must make sure to merge in all remaining |
| 811 | // links at offset zero. |
| 812 | unsigned MergeOffset = 0; |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 813 | DSNode *CN = CurNodeH.getNode(); |
| 814 | if (CN->Size != 1) |
| 815 | MergeOffset = ((i << DS::PointerShift)+NOffset) % CN->getSize(); |
| 816 | CN->addEdgeTo(MergeOffset, Link); |
Vikram S. Adve | 2b7a92c | 2002-12-06 21:15:21 +0000 | [diff] [blame] | 817 | } |
| 818 | } |
| 819 | |
| 820 | // Now that there are no outgoing edges, all of the Links are dead. |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 821 | N->Links.clear(); |
Vikram S. Adve | 2b7a92c | 2002-12-06 21:15:21 +0000 | [diff] [blame] | 822 | |
| 823 | // Merge the globals list... |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 824 | if (!N->Globals.empty()) { |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 825 | CurNodeH.getNode()->mergeGlobals(N->Globals); |
Vikram S. Adve | 2b7a92c | 2002-12-06 21:15:21 +0000 | [diff] [blame] | 826 | |
| 827 | // Delete the globals from the old node... |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 828 | std::vector<GlobalValue*>().swap(N->Globals); |
Vikram S. Adve | 2b7a92c | 2002-12-06 21:15:21 +0000 | [diff] [blame] | 829 | } |
| 830 | } |
| 831 | |
| 832 | |
Misha Brukman | 96a8bd7 | 2004-04-29 04:05:30 +0000 | [diff] [blame] | 833 | /// mergeWith - Merge this node and the specified node, moving all links to and |
| 834 | /// from the argument node into the current node, deleting the node argument. |
| 835 | /// Offset indicates what offset the specified node is to be merged into the |
| 836 | /// current node. |
| 837 | /// |
| 838 | /// The specified node may be a null pointer (in which case, we update it to |
| 839 | /// point to this node). |
| 840 | /// |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 841 | void DSNode::mergeWith(const DSNodeHandle &NH, unsigned Offset) { |
| 842 | DSNode *N = NH.getNode(); |
Chris Lattner | 5254a8d | 2004-01-22 16:31:08 +0000 | [diff] [blame] | 843 | if (N == this && NH.getOffset() == Offset) |
Chris Lattner | 8f0a16e | 2002-10-31 05:45:02 +0000 | [diff] [blame] | 844 | return; // Noop |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 845 | |
Chris Lattner | 5254a8d | 2004-01-22 16:31:08 +0000 | [diff] [blame] | 846 | // If the RHS is a null node, make it point to this node! |
| 847 | if (N == 0) { |
| 848 | NH.mergeWith(DSNodeHandle(this, Offset)); |
| 849 | return; |
| 850 | } |
| 851 | |
Chris Lattner | bd92b73 | 2003-06-19 21:15:11 +0000 | [diff] [blame] | 852 | assert(!N->isDeadNode() && !isDeadNode()); |
Chris Lattner | 679e8e1 | 2002-11-08 21:27:12 +0000 | [diff] [blame] | 853 | assert(!hasNoReferrers() && "Should not try to fold a useless node!"); |
| 854 | |
Chris Lattner | 0260663 | 2002-11-04 06:48:26 +0000 | [diff] [blame] | 855 | if (N == this) { |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 856 | // We cannot merge two pieces of the same node together, collapse the node |
| 857 | // completely. |
Chris Lattner | 3c87b29 | 2002-11-07 01:54:56 +0000 | [diff] [blame] | 858 | DEBUG(std::cerr << "Attempting to merge two chunks of" |
| 859 | << " the same node together!\n"); |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 860 | foldNodeCompletely(); |
Chris Lattner | 0260663 | 2002-11-04 06:48:26 +0000 | [diff] [blame] | 861 | return; |
| 862 | } |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 863 | |
Chris Lattner | 5190ce8 | 2002-11-12 07:20:45 +0000 | [diff] [blame] | 864 | // If both nodes are not at offset 0, make sure that we are merging the node |
| 865 | // at an later offset into the node with the zero offset. |
| 866 | // |
| 867 | if (Offset < NH.getOffset()) { |
| 868 | N->mergeWith(DSNodeHandle(this, Offset), NH.getOffset()); |
| 869 | return; |
| 870 | } else if (Offset == NH.getOffset() && getSize() < N->getSize()) { |
| 871 | // If the offsets are the same, merge the smaller node into the bigger node |
| 872 | N->mergeWith(DSNodeHandle(this, Offset), NH.getOffset()); |
| 873 | return; |
| 874 | } |
| 875 | |
Vikram S. Adve | 2b7a92c | 2002-12-06 21:15:21 +0000 | [diff] [blame] | 876 | // Ok, now we can merge the two nodes. Use a static helper that works with |
| 877 | // two node handles, since "this" may get merged away at intermediate steps. |
| 878 | DSNodeHandle CurNodeH(this, Offset); |
| 879 | DSNodeHandle NHCopy(NH); |
| 880 | DSNode::MergeNodes(CurNodeH, NHCopy); |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 881 | } |
| 882 | |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 883 | |
| 884 | //===----------------------------------------------------------------------===// |
| 885 | // ReachabilityCloner Implementation |
| 886 | //===----------------------------------------------------------------------===// |
| 887 | |
| 888 | DSNodeHandle ReachabilityCloner::getClonedNH(const DSNodeHandle &SrcNH) { |
| 889 | if (SrcNH.isNull()) return DSNodeHandle(); |
| 890 | const DSNode *SN = SrcNH.getNode(); |
| 891 | |
| 892 | DSNodeHandle &NH = NodeMap[SN]; |
Chris Lattner | 6f96774 | 2004-10-30 04:05:01 +0000 | [diff] [blame] | 893 | if (!NH.isNull()) { // Node already mapped? |
| 894 | DSNode *NHN = NH.getNode(); |
| 895 | return DSNodeHandle(NHN, NH.getOffset()+SrcNH.getOffset()); |
| 896 | } |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 897 | |
Chris Lattner | e6e93cc | 2004-03-04 19:47:04 +0000 | [diff] [blame] | 898 | // If SrcNH has globals and the destination graph has one of the same globals, |
| 899 | // merge this node with the destination node, which is much more efficient. |
Chris Lattner | 82c6c72 | 2005-03-20 02:41:38 +0000 | [diff] [blame] | 900 | if (SN->globals_begin() != SN->globals_end()) { |
Chris Lattner | e6e93cc | 2004-03-04 19:47:04 +0000 | [diff] [blame] | 901 | DSScalarMap &DestSM = Dest.getScalarMap(); |
Chris Lattner | 82c6c72 | 2005-03-20 02:41:38 +0000 | [diff] [blame] | 902 | for (DSNode::globals_iterator I = SN->globals_begin(),E = SN->globals_end(); |
Chris Lattner | e6e93cc | 2004-03-04 19:47:04 +0000 | [diff] [blame] | 903 | I != E; ++I) { |
| 904 | GlobalValue *GV = *I; |
| 905 | DSScalarMap::iterator GI = DestSM.find(GV); |
| 906 | if (GI != DestSM.end() && !GI->second.isNull()) { |
| 907 | // We found one, use merge instead! |
| 908 | merge(GI->second, Src.getNodeForValue(GV)); |
| 909 | assert(!NH.isNull() && "Didn't merge node!"); |
Chris Lattner | 6f96774 | 2004-10-30 04:05:01 +0000 | [diff] [blame] | 910 | DSNode *NHN = NH.getNode(); |
| 911 | return DSNodeHandle(NHN, NH.getOffset()+SrcNH.getOffset()); |
Chris Lattner | e6e93cc | 2004-03-04 19:47:04 +0000 | [diff] [blame] | 912 | } |
| 913 | } |
| 914 | } |
Chris Lattner | f590ced | 2004-03-04 17:06:53 +0000 | [diff] [blame] | 915 | |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 916 | DSNode *DN = new DSNode(*SN, &Dest, true /* Null out all links */); |
| 917 | DN->maskNodeTypes(BitsToKeep); |
Chris Lattner | 00948c0 | 2004-01-28 02:05:05 +0000 | [diff] [blame] | 918 | NH = DN; |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 919 | |
| 920 | // Next, recursively clone all outgoing links as necessary. Note that |
| 921 | // adding these links can cause the node to collapse itself at any time, and |
| 922 | // the current node may be merged with arbitrary other nodes. For this |
| 923 | // reason, we must always go through NH. |
| 924 | DN = 0; |
| 925 | for (unsigned i = 0, e = SN->getNumLinks(); i != e; ++i) { |
| 926 | const DSNodeHandle &SrcEdge = SN->getLink(i << DS::PointerShift); |
| 927 | if (!SrcEdge.isNull()) { |
| 928 | const DSNodeHandle &DestEdge = getClonedNH(SrcEdge); |
| 929 | // Compute the offset into the current node at which to |
| 930 | // merge this link. In the common case, this is a linear |
| 931 | // relation to the offset in the original node (with |
| 932 | // wrapping), but if the current node gets collapsed due to |
| 933 | // recursive merging, we must make sure to merge in all remaining |
| 934 | // links at offset zero. |
| 935 | unsigned MergeOffset = 0; |
| 936 | DSNode *CN = NH.getNode(); |
| 937 | if (CN->getSize() != 1) |
Chris Lattner | 37ec591 | 2004-06-23 06:29:59 +0000 | [diff] [blame] | 938 | MergeOffset = ((i << DS::PointerShift)+NH.getOffset()) % CN->getSize(); |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 939 | CN->addEdgeTo(MergeOffset, DestEdge); |
| 940 | } |
| 941 | } |
| 942 | |
| 943 | // If this node contains any globals, make sure they end up in the scalar |
| 944 | // map with the correct offset. |
Chris Lattner | 82c6c72 | 2005-03-20 02:41:38 +0000 | [diff] [blame] | 945 | for (DSNode::globals_iterator I = SN->globals_begin(), E = SN->globals_end(); |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 946 | I != E; ++I) { |
| 947 | GlobalValue *GV = *I; |
| 948 | const DSNodeHandle &SrcGNH = Src.getNodeForValue(GV); |
| 949 | DSNodeHandle &DestGNH = NodeMap[SrcGNH.getNode()]; |
| 950 | assert(DestGNH.getNode() == NH.getNode() &&"Global mapping inconsistent"); |
| 951 | Dest.getNodeForValue(GV).mergeWith(DSNodeHandle(DestGNH.getNode(), |
Chris Lattner | 00948c0 | 2004-01-28 02:05:05 +0000 | [diff] [blame] | 952 | DestGNH.getOffset()+SrcGNH.getOffset())); |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 953 | } |
Chris Lattner | 82c6c72 | 2005-03-20 02:41:38 +0000 | [diff] [blame] | 954 | NH.getNode()->mergeGlobals(SN->getGlobalsList()); |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 955 | |
| 956 | return DSNodeHandle(NH.getNode(), NH.getOffset()+SrcNH.getOffset()); |
| 957 | } |
| 958 | |
| 959 | void ReachabilityCloner::merge(const DSNodeHandle &NH, |
| 960 | const DSNodeHandle &SrcNH) { |
| 961 | if (SrcNH.isNull()) return; // Noop |
| 962 | if (NH.isNull()) { |
| 963 | // If there is no destination node, just clone the source and assign the |
| 964 | // destination node to be it. |
| 965 | NH.mergeWith(getClonedNH(SrcNH)); |
| 966 | return; |
| 967 | } |
| 968 | |
| 969 | // Okay, at this point, we know that we have both a destination and a source |
| 970 | // node that need to be merged. Check to see if the source node has already |
| 971 | // been cloned. |
| 972 | const DSNode *SN = SrcNH.getNode(); |
| 973 | DSNodeHandle &SCNH = NodeMap[SN]; // SourceClonedNodeHandle |
Chris Lattner | 0ad9170 | 2004-02-22 00:53:54 +0000 | [diff] [blame] | 974 | if (!SCNH.isNull()) { // Node already cloned? |
Chris Lattner | 6f96774 | 2004-10-30 04:05:01 +0000 | [diff] [blame] | 975 | DSNode *SCNHN = SCNH.getNode(); |
| 976 | NH.mergeWith(DSNodeHandle(SCNHN, |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 977 | SCNH.getOffset()+SrcNH.getOffset())); |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 978 | return; // Nothing to do! |
| 979 | } |
Chris Lattner | 6f96774 | 2004-10-30 04:05:01 +0000 | [diff] [blame] | 980 | |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 981 | // Okay, so the source node has not already been cloned. Instead of creating |
| 982 | // a new DSNode, only to merge it into the one we already have, try to perform |
| 983 | // the merge in-place. The only case we cannot handle here is when the offset |
| 984 | // into the existing node is less than the offset into the virtual node we are |
| 985 | // merging in. In this case, we have to extend the existing node, which |
| 986 | // requires an allocation anyway. |
| 987 | DSNode *DN = NH.getNode(); // Make sure the Offset is up-to-date |
| 988 | if (NH.getOffset() >= SrcNH.getOffset()) { |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 989 | if (!DN->isNodeCompletelyFolded()) { |
| 990 | // Make sure the destination node is folded if the source node is folded. |
| 991 | if (SN->isNodeCompletelyFolded()) { |
| 992 | DN->foldNodeCompletely(); |
| 993 | DN = NH.getNode(); |
| 994 | } else if (SN->getSize() != DN->getSize()) { |
| 995 | // If the two nodes are of different size, and the smaller node has the |
| 996 | // array bit set, collapse! |
Chris Lattner | b29dd0f | 2004-12-08 21:03:56 +0000 | [diff] [blame] | 997 | #if COLLAPSE_ARRAYS_AGGRESSIVELY |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 998 | if (SN->getSize() < DN->getSize()) { |
| 999 | if (SN->isArray()) { |
| 1000 | DN->foldNodeCompletely(); |
| 1001 | DN = NH.getNode(); |
| 1002 | } |
| 1003 | } else if (DN->isArray()) { |
| 1004 | DN->foldNodeCompletely(); |
| 1005 | DN = NH.getNode(); |
| 1006 | } |
Chris Lattner | b29dd0f | 2004-12-08 21:03:56 +0000 | [diff] [blame] | 1007 | #endif |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1008 | } |
| 1009 | |
| 1010 | // Merge the type entries of the two nodes together... |
| 1011 | if (SN->getType() != Type::VoidTy && !DN->isNodeCompletelyFolded()) { |
| 1012 | DN->mergeTypeInfo(SN->getType(), NH.getOffset()-SrcNH.getOffset()); |
| 1013 | DN = NH.getNode(); |
| 1014 | } |
| 1015 | } |
| 1016 | |
| 1017 | assert(!DN->isDeadNode()); |
| 1018 | |
| 1019 | // Merge the NodeType information. |
| 1020 | DN->mergeNodeFlags(SN->getNodeFlags() & BitsToKeep); |
| 1021 | |
| 1022 | // Before we start merging outgoing links and updating the scalar map, make |
| 1023 | // sure it is known that this is the representative node for the src node. |
| 1024 | SCNH = DSNodeHandle(DN, NH.getOffset()-SrcNH.getOffset()); |
| 1025 | |
| 1026 | // If the source node contains any globals, make sure they end up in the |
| 1027 | // scalar map with the correct offset. |
Chris Lattner | 82c6c72 | 2005-03-20 02:41:38 +0000 | [diff] [blame] | 1028 | if (SN->globals_begin() != SN->globals_end()) { |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1029 | // Update the globals in the destination node itself. |
Chris Lattner | 82c6c72 | 2005-03-20 02:41:38 +0000 | [diff] [blame] | 1030 | DN->mergeGlobals(SN->getGlobalsList()); |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1031 | |
| 1032 | // Update the scalar map for the graph we are merging the source node |
| 1033 | // into. |
Chris Lattner | 82c6c72 | 2005-03-20 02:41:38 +0000 | [diff] [blame] | 1034 | for (DSNode::globals_iterator I = SN->globals_begin(), |
| 1035 | E = SN->globals_end(); I != E; ++I) { |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1036 | GlobalValue *GV = *I; |
| 1037 | const DSNodeHandle &SrcGNH = Src.getNodeForValue(GV); |
| 1038 | DSNodeHandle &DestGNH = NodeMap[SrcGNH.getNode()]; |
| 1039 | assert(DestGNH.getNode()==NH.getNode() &&"Global mapping inconsistent"); |
| 1040 | Dest.getNodeForValue(GV).mergeWith(DSNodeHandle(DestGNH.getNode(), |
Chris Lattner | ead9eb7 | 2004-01-29 08:36:22 +0000 | [diff] [blame] | 1041 | DestGNH.getOffset()+SrcGNH.getOffset())); |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1042 | } |
Chris Lattner | 82c6c72 | 2005-03-20 02:41:38 +0000 | [diff] [blame] | 1043 | NH.getNode()->mergeGlobals(SN->getGlobalsList()); |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1044 | } |
| 1045 | } else { |
| 1046 | // We cannot handle this case without allocating a temporary node. Fall |
| 1047 | // back on being simple. |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1048 | DSNode *NewDN = new DSNode(*SN, &Dest, true /* Null out all links */); |
| 1049 | NewDN->maskNodeTypes(BitsToKeep); |
| 1050 | |
| 1051 | unsigned NHOffset = NH.getOffset(); |
| 1052 | NH.mergeWith(DSNodeHandle(NewDN, SrcNH.getOffset())); |
Chris Lattner | ead9eb7 | 2004-01-29 08:36:22 +0000 | [diff] [blame] | 1053 | |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1054 | assert(NH.getNode() && |
| 1055 | (NH.getOffset() > NHOffset || |
| 1056 | (NH.getOffset() == 0 && NH.getNode()->isNodeCompletelyFolded())) && |
| 1057 | "Merging did not adjust the offset!"); |
| 1058 | |
| 1059 | // Before we start merging outgoing links and updating the scalar map, make |
| 1060 | // sure it is known that this is the representative node for the src node. |
| 1061 | SCNH = DSNodeHandle(NH.getNode(), NH.getOffset()-SrcNH.getOffset()); |
Chris Lattner | ead9eb7 | 2004-01-29 08:36:22 +0000 | [diff] [blame] | 1062 | |
| 1063 | // If the source node contained any globals, make sure to create entries |
| 1064 | // in the scalar map for them! |
Chris Lattner | 82c6c72 | 2005-03-20 02:41:38 +0000 | [diff] [blame] | 1065 | for (DSNode::globals_iterator I = SN->globals_begin(), |
| 1066 | E = SN->globals_end(); I != E; ++I) { |
Chris Lattner | ead9eb7 | 2004-01-29 08:36:22 +0000 | [diff] [blame] | 1067 | GlobalValue *GV = *I; |
| 1068 | const DSNodeHandle &SrcGNH = Src.getNodeForValue(GV); |
| 1069 | DSNodeHandle &DestGNH = NodeMap[SrcGNH.getNode()]; |
| 1070 | assert(DestGNH.getNode()==NH.getNode() &&"Global mapping inconsistent"); |
| 1071 | assert(SrcGNH.getNode() == SN && "Global mapping inconsistent"); |
| 1072 | Dest.getNodeForValue(GV).mergeWith(DSNodeHandle(DestGNH.getNode(), |
| 1073 | DestGNH.getOffset()+SrcGNH.getOffset())); |
Chris Lattner | ead9eb7 | 2004-01-29 08:36:22 +0000 | [diff] [blame] | 1074 | } |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1075 | } |
| 1076 | |
| 1077 | |
| 1078 | // Next, recursively merge all outgoing links as necessary. Note that |
| 1079 | // adding these links can cause the destination node to collapse itself at |
| 1080 | // any time, and the current node may be merged with arbitrary other nodes. |
| 1081 | // For this reason, we must always go through NH. |
| 1082 | DN = 0; |
| 1083 | for (unsigned i = 0, e = SN->getNumLinks(); i != e; ++i) { |
| 1084 | const DSNodeHandle &SrcEdge = SN->getLink(i << DS::PointerShift); |
| 1085 | if (!SrcEdge.isNull()) { |
| 1086 | // Compute the offset into the current node at which to |
| 1087 | // merge this link. In the common case, this is a linear |
| 1088 | // relation to the offset in the original node (with |
| 1089 | // wrapping), but if the current node gets collapsed due to |
| 1090 | // recursive merging, we must make sure to merge in all remaining |
| 1091 | // links at offset zero. |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1092 | DSNode *CN = SCNH.getNode(); |
Chris Lattner | f590ced | 2004-03-04 17:06:53 +0000 | [diff] [blame] | 1093 | unsigned MergeOffset = |
| 1094 | ((i << DS::PointerShift)+SCNH.getOffset()) % CN->getSize(); |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1095 | |
Chris Lattner | f590ced | 2004-03-04 17:06:53 +0000 | [diff] [blame] | 1096 | DSNodeHandle Tmp = CN->getLink(MergeOffset); |
| 1097 | if (!Tmp.isNull()) { |
Chris Lattner | 0ad9170 | 2004-02-22 00:53:54 +0000 | [diff] [blame] | 1098 | // Perform the recursive merging. Make sure to create a temporary NH, |
| 1099 | // because the Link can disappear in the process of recursive merging. |
Chris Lattner | 0ad9170 | 2004-02-22 00:53:54 +0000 | [diff] [blame] | 1100 | merge(Tmp, SrcEdge); |
| 1101 | } else { |
Chris Lattner | f590ced | 2004-03-04 17:06:53 +0000 | [diff] [blame] | 1102 | Tmp.mergeWith(getClonedNH(SrcEdge)); |
| 1103 | // Merging this could cause all kinds of recursive things to happen, |
| 1104 | // culminating in the current node being eliminated. Since this is |
| 1105 | // possible, make sure to reaquire the link from 'CN'. |
| 1106 | |
| 1107 | unsigned MergeOffset = 0; |
| 1108 | CN = SCNH.getNode(); |
| 1109 | MergeOffset = ((i << DS::PointerShift)+SCNH.getOffset()) %CN->getSize(); |
| 1110 | CN->getLink(MergeOffset).mergeWith(Tmp); |
Chris Lattner | 0ad9170 | 2004-02-22 00:53:54 +0000 | [diff] [blame] | 1111 | } |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1112 | } |
| 1113 | } |
| 1114 | } |
| 1115 | |
| 1116 | /// mergeCallSite - Merge the nodes reachable from the specified src call |
| 1117 | /// site into the nodes reachable from DestCS. |
Chris Lattner | b343937 | 2005-03-21 20:28:50 +0000 | [diff] [blame] | 1118 | void ReachabilityCloner::mergeCallSite(DSCallSite &DestCS, |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1119 | const DSCallSite &SrcCS) { |
| 1120 | merge(DestCS.getRetVal(), SrcCS.getRetVal()); |
| 1121 | unsigned MinArgs = DestCS.getNumPtrArgs(); |
| 1122 | if (SrcCS.getNumPtrArgs() < MinArgs) MinArgs = SrcCS.getNumPtrArgs(); |
| 1123 | |
| 1124 | for (unsigned a = 0; a != MinArgs; ++a) |
| 1125 | merge(DestCS.getPtrArg(a), SrcCS.getPtrArg(a)); |
Chris Lattner | 3f90a94 | 2005-03-21 09:39:51 +0000 | [diff] [blame] | 1126 | |
| 1127 | for (unsigned a = MinArgs, e = SrcCS.getNumPtrArgs(); a != e; ++a) |
Chris Lattner | b343937 | 2005-03-21 20:28:50 +0000 | [diff] [blame] | 1128 | DestCS.addPtrArg(getClonedNH(SrcCS.getPtrArg(a))); |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1129 | } |
| 1130 | |
| 1131 | |
Chris Lattner | 9de906c | 2002-10-20 22:11:44 +0000 | [diff] [blame] | 1132 | //===----------------------------------------------------------------------===// |
| 1133 | // DSCallSite Implementation |
| 1134 | //===----------------------------------------------------------------------===// |
| 1135 | |
Vikram S. Adve | 26b9826 | 2002-10-20 21:41:02 +0000 | [diff] [blame] | 1136 | // Define here to avoid including iOther.h and BasicBlock.h in DSGraph.h |
Chris Lattner | 9de906c | 2002-10-20 22:11:44 +0000 | [diff] [blame] | 1137 | Function &DSCallSite::getCaller() const { |
Chris Lattner | 808a7ae | 2003-09-20 16:34:13 +0000 | [diff] [blame] | 1138 | return *Site.getInstruction()->getParent()->getParent(); |
Vikram S. Adve | 26b9826 | 2002-10-20 21:41:02 +0000 | [diff] [blame] | 1139 | } |
Vikram S. Adve | 42fd169 | 2002-10-20 18:07:37 +0000 | [diff] [blame] | 1140 | |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1141 | void DSCallSite::InitNH(DSNodeHandle &NH, const DSNodeHandle &Src, |
| 1142 | ReachabilityCloner &RC) { |
| 1143 | NH = RC.getClonedNH(Src); |
| 1144 | } |
Vikram S. Adve | 42fd169 | 2002-10-20 18:07:37 +0000 | [diff] [blame] | 1145 | |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 1146 | //===----------------------------------------------------------------------===// |
| 1147 | // DSGraph Implementation |
| 1148 | //===----------------------------------------------------------------------===// |
| 1149 | |
Chris Lattner | a9d6566 | 2003-06-30 05:57:30 +0000 | [diff] [blame] | 1150 | /// getFunctionNames - Return a space separated list of the name of the |
| 1151 | /// functions in this graph (if any) |
| 1152 | std::string DSGraph::getFunctionNames() const { |
| 1153 | switch (getReturnNodes().size()) { |
| 1154 | case 0: return "Globals graph"; |
Chris Lattner | a5f47ea | 2005-03-15 16:55:04 +0000 | [diff] [blame] | 1155 | case 1: return retnodes_begin()->first->getName(); |
Chris Lattner | a9d6566 | 2003-06-30 05:57:30 +0000 | [diff] [blame] | 1156 | default: |
| 1157 | std::string Return; |
Chris Lattner | a5f47ea | 2005-03-15 16:55:04 +0000 | [diff] [blame] | 1158 | for (DSGraph::retnodes_iterator I = retnodes_begin(); |
| 1159 | I != retnodes_end(); ++I) |
Chris Lattner | a9d6566 | 2003-06-30 05:57:30 +0000 | [diff] [blame] | 1160 | Return += I->first->getName() + " "; |
| 1161 | Return.erase(Return.end()-1, Return.end()); // Remove last space character |
| 1162 | return Return; |
| 1163 | } |
| 1164 | } |
| 1165 | |
| 1166 | |
Chris Lattner | f09ecff | 2005-03-21 22:49:53 +0000 | [diff] [blame] | 1167 | DSGraph::DSGraph(const DSGraph &G, EquivalenceClasses<GlobalValue*> &ECs, |
| 1168 | unsigned CloneFlags) |
Chris Lattner | f4f6227 | 2005-03-19 22:23:45 +0000 | [diff] [blame] | 1169 | : GlobalsGraph(0), ScalarMap(ECs), TD(G.TD) { |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1170 | PrintAuxCalls = false; |
Chris Lattner | 5a54063 | 2003-06-30 03:15:25 +0000 | [diff] [blame] | 1171 | NodeMapTy NodeMap; |
Chris Lattner | 3c920fa | 2005-03-22 00:21:05 +0000 | [diff] [blame^] | 1172 | cloneInto(G, ReturnNodes, NodeMap, CloneFlags); |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1173 | } |
| 1174 | |
Chris Lattner | f4f6227 | 2005-03-19 22:23:45 +0000 | [diff] [blame] | 1175 | DSGraph::DSGraph(const DSGraph &G, NodeMapTy &NodeMap, |
| 1176 | EquivalenceClasses<GlobalValue*> &ECs) |
| 1177 | : GlobalsGraph(0), ScalarMap(ECs), TD(G.TD) { |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1178 | PrintAuxCalls = false; |
Chris Lattner | 3c920fa | 2005-03-22 00:21:05 +0000 | [diff] [blame^] | 1179 | cloneInto(G, ReturnNodes, NodeMap); |
Chris Lattner | eff0da9 | 2002-10-21 15:32:34 +0000 | [diff] [blame] | 1180 | } |
| 1181 | |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 1182 | DSGraph::~DSGraph() { |
| 1183 | FunctionCalls.clear(); |
Chris Lattner | 679e8e1 | 2002-11-08 21:27:12 +0000 | [diff] [blame] | 1184 | AuxFunctionCalls.clear(); |
Chris Lattner | c875f02 | 2002-11-03 21:27:48 +0000 | [diff] [blame] | 1185 | ScalarMap.clear(); |
Chris Lattner | 5a54063 | 2003-06-30 03:15:25 +0000 | [diff] [blame] | 1186 | ReturnNodes.clear(); |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 1187 | |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 1188 | // Drop all intra-node references, so that assertions don't fail... |
Chris Lattner | 28897e1 | 2004-02-08 00:53:26 +0000 | [diff] [blame] | 1189 | for (node_iterator NI = node_begin(), E = node_end(); NI != E; ++NI) |
Chris Lattner | 84b80a2 | 2005-03-16 22:42:19 +0000 | [diff] [blame] | 1190 | NI->dropAllReferences(); |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 1191 | |
Chris Lattner | 28897e1 | 2004-02-08 00:53:26 +0000 | [diff] [blame] | 1192 | // Free all of the nodes. |
| 1193 | Nodes.clear(); |
Chris Lattner | c68c31b | 2002-07-10 22:38:08 +0000 | [diff] [blame] | 1194 | } |
| 1195 | |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1196 | // dump - Allow inspection of graph in a debugger. |
| 1197 | void DSGraph::dump() const { print(std::cerr); } |
| 1198 | |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 1199 | |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 1200 | /// remapLinks - Change all of the Links in the current node according to the |
| 1201 | /// specified mapping. |
Chris Lattner | 8f0a16e | 2002-10-31 05:45:02 +0000 | [diff] [blame] | 1202 | /// |
Chris Lattner | 8d32767 | 2003-06-30 03:36:09 +0000 | [diff] [blame] | 1203 | void DSNode::remapLinks(DSGraph::NodeMapTy &OldNodeMap) { |
Chris Lattner | 2f56138 | 2004-01-22 16:56:13 +0000 | [diff] [blame] | 1204 | for (unsigned i = 0, e = Links.size(); i != e; ++i) |
| 1205 | if (DSNode *N = Links[i].getNode()) { |
Chris Lattner | 091f776 | 2004-01-23 01:44:53 +0000 | [diff] [blame] | 1206 | DSGraph::NodeMapTy::const_iterator ONMI = OldNodeMap.find(N); |
Chris Lattner | 6f96774 | 2004-10-30 04:05:01 +0000 | [diff] [blame] | 1207 | if (ONMI != OldNodeMap.end()) { |
| 1208 | DSNode *ONMIN = ONMI->second.getNode(); |
| 1209 | Links[i].setTo(ONMIN, Links[i].getOffset()+ONMI->second.getOffset()); |
| 1210 | } |
Chris Lattner | 2f56138 | 2004-01-22 16:56:13 +0000 | [diff] [blame] | 1211 | } |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 1212 | } |
Vikram S. Adve | 355e2ca | 2002-07-30 22:05:22 +0000 | [diff] [blame] | 1213 | |
Chris Lattner | d672ab9 | 2005-02-15 18:40:55 +0000 | [diff] [blame] | 1214 | /// addObjectToGraph - This method can be used to add global, stack, and heap |
| 1215 | /// objects to the graph. This can be used when updating DSGraphs due to the |
| 1216 | /// introduction of new temporary objects. The new object is not pointed to |
| 1217 | /// and does not point to any other objects in the graph. |
| 1218 | DSNode *DSGraph::addObjectToGraph(Value *Ptr, bool UseDeclaredType) { |
| 1219 | assert(isa<PointerType>(Ptr->getType()) && "Ptr is not a pointer!"); |
| 1220 | const Type *Ty = cast<PointerType>(Ptr->getType())->getElementType(); |
| 1221 | DSNode *N = new DSNode(UseDeclaredType ? Ty : 0, this); |
Chris Lattner | 7a0c775 | 2005-02-15 18:48:48 +0000 | [diff] [blame] | 1222 | assert(ScalarMap[Ptr].isNull() && "Object already in this graph!"); |
Chris Lattner | d672ab9 | 2005-02-15 18:40:55 +0000 | [diff] [blame] | 1223 | ScalarMap[Ptr] = N; |
| 1224 | |
| 1225 | if (GlobalValue *GV = dyn_cast<GlobalValue>(Ptr)) { |
| 1226 | N->addGlobal(GV); |
| 1227 | } else if (MallocInst *MI = dyn_cast<MallocInst>(Ptr)) { |
| 1228 | N->setHeapNodeMarker(); |
| 1229 | } else if (AllocaInst *AI = dyn_cast<AllocaInst>(Ptr)) { |
| 1230 | N->setAllocaNodeMarker(); |
| 1231 | } else { |
| 1232 | assert(0 && "Illegal memory object input!"); |
| 1233 | } |
| 1234 | return N; |
| 1235 | } |
| 1236 | |
| 1237 | |
Chris Lattner | 5a54063 | 2003-06-30 03:15:25 +0000 | [diff] [blame] | 1238 | /// cloneInto - Clone the specified DSGraph into the current graph. The |
Chris Lattner | 3c920fa | 2005-03-22 00:21:05 +0000 | [diff] [blame^] | 1239 | /// translated ScalarMap for the old function is filled into the ScalarMap |
| 1240 | /// for the graph, and the translated ReturnNodes map is returned into |
| 1241 | /// ReturnNodes. |
Chris Lattner | 5a54063 | 2003-06-30 03:15:25 +0000 | [diff] [blame] | 1242 | /// |
| 1243 | /// The CloneFlags member controls various aspects of the cloning process. |
| 1244 | /// |
Chris Lattner | 3c920fa | 2005-03-22 00:21:05 +0000 | [diff] [blame^] | 1245 | void DSGraph::cloneInto(const DSGraph &G, |
Chris Lattner | 5a54063 | 2003-06-30 03:15:25 +0000 | [diff] [blame] | 1246 | ReturnNodesTy &OldReturnNodes, NodeMapTy &OldNodeMap, |
| 1247 | unsigned CloneFlags) { |
Chris Lattner | 93ddd7e | 2004-01-22 16:36:28 +0000 | [diff] [blame] | 1248 | TIME_REGION(X, "cloneInto"); |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 1249 | assert(OldNodeMap.empty() && "Returned OldNodeMap should be empty!"); |
Chris Lattner | 33312f7 | 2002-11-08 01:21:07 +0000 | [diff] [blame] | 1250 | assert(&G != this && "Cannot clone graph into itself!"); |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1251 | |
Chris Lattner | 1e88369 | 2003-02-03 20:08:51 +0000 | [diff] [blame] | 1252 | // Remove alloca or mod/ref bits as specified... |
Vikram S. Adve | 78bbec7 | 2003-07-16 21:36:31 +0000 | [diff] [blame] | 1253 | unsigned BitsToClear = ((CloneFlags & StripAllocaBit)? DSNode::AllocaNode : 0) |
| 1254 | | ((CloneFlags & StripModRefBits)? (DSNode::Modified | DSNode::Read) : 0) |
| 1255 | | ((CloneFlags & StripIncompleteBit)? DSNode::Incomplete : 0); |
Chris Lattner | bd92b73 | 2003-06-19 21:15:11 +0000 | [diff] [blame] | 1256 | BitsToClear |= DSNode::DEAD; // Clear dead flag... |
Chris Lattner | 9fd37ba | 2004-02-08 00:23:16 +0000 | [diff] [blame] | 1257 | |
Chris Lattner | 84b80a2 | 2005-03-16 22:42:19 +0000 | [diff] [blame] | 1258 | for (node_const_iterator I = G.node_begin(), E = G.node_end(); I != E; ++I) { |
| 1259 | assert(!I->isForwarding() && |
Chris Lattner | d85645f | 2004-02-21 22:28:26 +0000 | [diff] [blame] | 1260 | "Forward nodes shouldn't be in node list!"); |
Chris Lattner | 84b80a2 | 2005-03-16 22:42:19 +0000 | [diff] [blame] | 1261 | DSNode *New = new DSNode(*I, this); |
Chris Lattner | d85645f | 2004-02-21 22:28:26 +0000 | [diff] [blame] | 1262 | New->maskNodeTypes(~BitsToClear); |
Chris Lattner | 84b80a2 | 2005-03-16 22:42:19 +0000 | [diff] [blame] | 1263 | OldNodeMap[I] = New; |
Chris Lattner | d85645f | 2004-02-21 22:28:26 +0000 | [diff] [blame] | 1264 | } |
| 1265 | |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 1266 | #ifndef NDEBUG |
| 1267 | Timer::addPeakMemoryMeasurement(); |
| 1268 | #endif |
Chris Lattner | d85645f | 2004-02-21 22:28:26 +0000 | [diff] [blame] | 1269 | |
Vikram S. Adve | 355e2ca | 2002-07-30 22:05:22 +0000 | [diff] [blame] | 1270 | // Rewrite the links in the new nodes to point into the current graph now. |
Chris Lattner | d85645f | 2004-02-21 22:28:26 +0000 | [diff] [blame] | 1271 | // Note that we don't loop over the node's list to do this. The problem is |
| 1272 | // that remaping links can cause recursive merging to happen, which means |
| 1273 | // that node_iterator's can get easily invalidated! Because of this, we |
| 1274 | // loop over the OldNodeMap, which contains all of the new nodes as the |
| 1275 | // .second element of the map elements. Also note that if we remap a node |
| 1276 | // more than once, we won't break anything. |
| 1277 | for (NodeMapTy::iterator I = OldNodeMap.begin(), E = OldNodeMap.end(); |
| 1278 | I != E; ++I) |
| 1279 | I->second.getNode()->remapLinks(OldNodeMap); |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1280 | |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 1281 | // Copy the scalar map... merging all of the global nodes... |
Chris Lattner | 62482e5 | 2004-01-28 09:15:42 +0000 | [diff] [blame] | 1282 | for (DSScalarMap::const_iterator I = G.ScalarMap.begin(), |
Chris Lattner | c875f02 | 2002-11-03 21:27:48 +0000 | [diff] [blame] | 1283 | E = G.ScalarMap.end(); I != E; ++I) { |
Chris Lattner | f8c6aab | 2002-11-08 05:01:14 +0000 | [diff] [blame] | 1284 | DSNodeHandle &MappedNode = OldNodeMap[I->second.getNode()]; |
Chris Lattner | 3c920fa | 2005-03-22 00:21:05 +0000 | [diff] [blame^] | 1285 | DSNodeHandle &H = ScalarMap[I->first]; |
Chris Lattner | 6f96774 | 2004-10-30 04:05:01 +0000 | [diff] [blame] | 1286 | DSNode *MappedNodeN = MappedNode.getNode(); |
| 1287 | H.mergeWith(DSNodeHandle(MappedNodeN, |
Chris Lattner | 2cb9acd | 2003-06-30 05:09:29 +0000 | [diff] [blame] | 1288 | I->second.getOffset()+MappedNode.getOffset())); |
Chris Lattner | cf15db3 | 2002-10-17 20:09:52 +0000 | [diff] [blame] | 1289 | |
Chris Lattner | 2cb9acd | 2003-06-30 05:09:29 +0000 | [diff] [blame] | 1290 | // If this is a global, add the global to this fn or merge if already exists |
Chris Lattner | cc9bda6 | 2005-03-20 04:30:30 +0000 | [diff] [blame] | 1291 | if (GlobalValue* GV = dyn_cast<GlobalValue>(I->first)) |
Vikram S. Adve | 78bbec7 | 2003-07-16 21:36:31 +0000 | [diff] [blame] | 1292 | ScalarMap[GV].mergeWith(H); |
Chris Lattner | cf15db3 | 2002-10-17 20:09:52 +0000 | [diff] [blame] | 1293 | } |
Chris Lattner | fccd06f | 2002-10-01 22:33:50 +0000 | [diff] [blame] | 1294 | |
Chris Lattner | 679e8e1 | 2002-11-08 21:27:12 +0000 | [diff] [blame] | 1295 | if (!(CloneFlags & DontCloneCallNodes)) { |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1296 | // Copy the function calls list. |
| 1297 | for (fc_iterator I = G.fc_begin(), E = G.fc_end(); I != E; ++I) |
| 1298 | FunctionCalls.push_back(DSCallSite(*I, OldNodeMap)); |
Chris Lattner | acf491f | 2002-11-08 22:27:09 +0000 | [diff] [blame] | 1299 | } |
Chris Lattner | 679e8e1 | 2002-11-08 21:27:12 +0000 | [diff] [blame] | 1300 | |
Chris Lattner | acf491f | 2002-11-08 22:27:09 +0000 | [diff] [blame] | 1301 | if (!(CloneFlags & DontCloneAuxCallNodes)) { |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1302 | // Copy the auxiliary function calls list. |
| 1303 | for (afc_iterator I = G.afc_begin(), E = G.afc_end(); I != E; ++I) |
| 1304 | AuxFunctionCalls.push_back(DSCallSite(*I, OldNodeMap)); |
Chris Lattner | 679e8e1 | 2002-11-08 21:27:12 +0000 | [diff] [blame] | 1305 | } |
Chris Lattner | cf15db3 | 2002-10-17 20:09:52 +0000 | [diff] [blame] | 1306 | |
Chris Lattner | 5a54063 | 2003-06-30 03:15:25 +0000 | [diff] [blame] | 1307 | // Map the return node pointers over... |
Chris Lattner | a5f47ea | 2005-03-15 16:55:04 +0000 | [diff] [blame] | 1308 | for (retnodes_iterator I = G.retnodes_begin(), |
| 1309 | E = G.retnodes_end(); I != E; ++I) { |
Chris Lattner | 5a54063 | 2003-06-30 03:15:25 +0000 | [diff] [blame] | 1310 | const DSNodeHandle &Ret = I->second; |
| 1311 | DSNodeHandle &MappedRet = OldNodeMap[Ret.getNode()]; |
Chris Lattner | 6f96774 | 2004-10-30 04:05:01 +0000 | [diff] [blame] | 1312 | DSNode *MappedRetN = MappedRet.getNode(); |
Chris Lattner | 5a54063 | 2003-06-30 03:15:25 +0000 | [diff] [blame] | 1313 | OldReturnNodes.insert(std::make_pair(I->first, |
Chris Lattner | 6f96774 | 2004-10-30 04:05:01 +0000 | [diff] [blame] | 1314 | DSNodeHandle(MappedRetN, |
Chris Lattner | 5a54063 | 2003-06-30 03:15:25 +0000 | [diff] [blame] | 1315 | MappedRet.getOffset()+Ret.getOffset()))); |
| 1316 | } |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1317 | } |
| 1318 | |
Chris Lattner | c4ebdce | 2004-03-03 22:01:09 +0000 | [diff] [blame] | 1319 | static bool PathExistsToClonedNode(const DSNode *N, ReachabilityCloner &RC) { |
Chris Lattner | 2f34690 | 2004-03-04 03:57:53 +0000 | [diff] [blame] | 1320 | if (N) |
| 1321 | for (df_iterator<const DSNode*> I = df_begin(N), E = df_end(N); I != E; ++I) |
| 1322 | if (RC.hasClonedNode(*I)) |
| 1323 | return true; |
Chris Lattner | c4ebdce | 2004-03-03 22:01:09 +0000 | [diff] [blame] | 1324 | return false; |
| 1325 | } |
| 1326 | |
Chris Lattner | 2f34690 | 2004-03-04 03:57:53 +0000 | [diff] [blame] | 1327 | static bool PathExistsToClonedNode(const DSCallSite &CS, |
| 1328 | ReachabilityCloner &RC) { |
| 1329 | if (PathExistsToClonedNode(CS.getRetVal().getNode(), RC)) |
| 1330 | return true; |
| 1331 | for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) |
| 1332 | if (PathExistsToClonedNode(CS.getPtrArg(i).getNode(), RC)) |
| 1333 | return true; |
| 1334 | return false; |
| 1335 | } |
Chris Lattner | 4c6cb7a | 2004-01-22 15:30:58 +0000 | [diff] [blame] | 1336 | |
Chris Lattner | bb753c4 | 2005-02-03 18:40:25 +0000 | [diff] [blame] | 1337 | /// getFunctionArgumentsForCall - Given a function that is currently in this |
| 1338 | /// graph, return the DSNodeHandles that correspond to the pointer-compatible |
| 1339 | /// function arguments. The vector is filled in with the return value (or |
| 1340 | /// null if it is not pointer compatible), followed by all of the |
| 1341 | /// pointer-compatible arguments. |
| 1342 | void DSGraph::getFunctionArgumentsForCall(Function *F, |
| 1343 | std::vector<DSNodeHandle> &Args) const { |
| 1344 | Args.push_back(getReturnNodeFor(*F)); |
Chris Lattner | e4d5c44 | 2005-03-15 04:54:21 +0000 | [diff] [blame] | 1345 | for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E; ++AI) |
Chris Lattner | bb753c4 | 2005-02-03 18:40:25 +0000 | [diff] [blame] | 1346 | if (isPointerType(AI->getType())) { |
| 1347 | Args.push_back(getNodeForValue(AI)); |
| 1348 | assert(!Args.back().isNull() && "Pointer argument w/o scalarmap entry!?"); |
| 1349 | } |
| 1350 | } |
| 1351 | |
Chris Lattner | e859444 | 2005-02-04 19:58:28 +0000 | [diff] [blame] | 1352 | /// mergeInCallFromOtherGraph - This graph merges in the minimal number of |
| 1353 | /// nodes from G2 into 'this' graph, merging the bindings specified by the |
| 1354 | /// call site (in this graph) with the bindings specified by the vector in G2. |
| 1355 | /// The two DSGraphs must be different. |
Chris Lattner | 076c1f9 | 2002-11-07 06:31:54 +0000 | [diff] [blame] | 1356 | /// |
Chris Lattner | e859444 | 2005-02-04 19:58:28 +0000 | [diff] [blame] | 1357 | void DSGraph::mergeInGraph(const DSCallSite &CS, |
| 1358 | std::vector<DSNodeHandle> &Args, |
Chris Lattner | 9f93055 | 2003-06-30 05:27:18 +0000 | [diff] [blame] | 1359 | const DSGraph &Graph, unsigned CloneFlags) { |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1360 | TIME_REGION(X, "mergeInGraph"); |
| 1361 | |
Chris Lattner | 076c1f9 | 2002-11-07 06:31:54 +0000 | [diff] [blame] | 1362 | // If this is not a recursive call, clone the graph into this graph... |
| 1363 | if (&Graph != this) { |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1364 | // Clone the callee's graph into the current graph, keeping track of where |
| 1365 | // scalars in the old graph _used_ to point, and of the new nodes matching |
| 1366 | // nodes of the old graph. |
| 1367 | ReachabilityCloner RC(*this, Graph, CloneFlags); |
| 1368 | |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1369 | // Map the return node pointer over. |
Chris Lattner | 0ad9170 | 2004-02-22 00:53:54 +0000 | [diff] [blame] | 1370 | if (!CS.getRetVal().isNull()) |
Chris Lattner | bb753c4 | 2005-02-03 18:40:25 +0000 | [diff] [blame] | 1371 | RC.merge(CS.getRetVal(), Args[0]); |
Chris Lattner | f590ced | 2004-03-04 17:06:53 +0000 | [diff] [blame] | 1372 | |
Chris Lattner | bb753c4 | 2005-02-03 18:40:25 +0000 | [diff] [blame] | 1373 | // Map over all of the arguments. |
| 1374 | for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) { |
Chris Lattner | e859444 | 2005-02-04 19:58:28 +0000 | [diff] [blame] | 1375 | if (i == Args.size()-1) |
Chris Lattner | bb753c4 | 2005-02-03 18:40:25 +0000 | [diff] [blame] | 1376 | break; |
Chris Lattner | bb753c4 | 2005-02-03 18:40:25 +0000 | [diff] [blame] | 1377 | |
| 1378 | // Add the link from the argument scalar to the provided value. |
| 1379 | RC.merge(CS.getPtrArg(i), Args[i+1]); |
| 1380 | } |
| 1381 | |
Chris Lattner | 2f34690 | 2004-03-04 03:57:53 +0000 | [diff] [blame] | 1382 | // If requested, copy all of the calls. |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1383 | if (!(CloneFlags & DontCloneCallNodes)) { |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1384 | // Copy the function calls list. |
| 1385 | for (fc_iterator I = Graph.fc_begin(), E = Graph.fc_end(); I != E; ++I) |
| 1386 | FunctionCalls.push_back(DSCallSite(*I, RC)); |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1387 | } |
Chris Lattner | 2f34690 | 2004-03-04 03:57:53 +0000 | [diff] [blame] | 1388 | |
| 1389 | // If the user has us copying aux calls (the normal case), set up a data |
| 1390 | // structure to keep track of which ones we've copied over. |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1391 | std::set<const DSCallSite*> CopiedAuxCall; |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1392 | |
Chris Lattner | 0321b68 | 2004-02-27 20:05:15 +0000 | [diff] [blame] | 1393 | // Clone over all globals that appear in the caller and callee graphs. |
Chris Lattner | c4ebdce | 2004-03-03 22:01:09 +0000 | [diff] [blame] | 1394 | hash_set<GlobalVariable*> NonCopiedGlobals; |
Chris Lattner | 0321b68 | 2004-02-27 20:05:15 +0000 | [diff] [blame] | 1395 | for (DSScalarMap::global_iterator GI = Graph.getScalarMap().global_begin(), |
| 1396 | E = Graph.getScalarMap().global_end(); GI != E; ++GI) |
| 1397 | if (GlobalVariable *GV = dyn_cast<GlobalVariable>(*GI)) |
| 1398 | if (ScalarMap.count(GV)) |
| 1399 | RC.merge(ScalarMap[GV], Graph.getNodeForValue(GV)); |
Chris Lattner | c4ebdce | 2004-03-03 22:01:09 +0000 | [diff] [blame] | 1400 | else |
| 1401 | NonCopiedGlobals.insert(GV); |
| 1402 | |
| 1403 | // If the global does not appear in the callers graph we generally don't |
| 1404 | // want to copy the node. However, if there is a path from the node global |
| 1405 | // node to a node that we did copy in the graph, we *must* copy it to |
| 1406 | // maintain the connection information. Every time we decide to include a |
| 1407 | // new global, this might make other globals live, so we must iterate |
| 1408 | // unfortunately. |
Chris Lattner | 2f34690 | 2004-03-04 03:57:53 +0000 | [diff] [blame] | 1409 | bool MadeChange = true; |
| 1410 | while (MadeChange) { |
| 1411 | MadeChange = false; |
| 1412 | for (hash_set<GlobalVariable*>::iterator I = NonCopiedGlobals.begin(); |
| 1413 | I != NonCopiedGlobals.end();) { |
| 1414 | DSNode *GlobalNode = Graph.getNodeForValue(*I).getNode(); |
| 1415 | if (RC.hasClonedNode(GlobalNode)) { |
| 1416 | // Already cloned it, remove from set. |
| 1417 | NonCopiedGlobals.erase(I++); |
| 1418 | MadeChange = true; |
| 1419 | } else if (PathExistsToClonedNode(GlobalNode, RC)) { |
| 1420 | RC.getClonedNH(Graph.getNodeForValue(*I)); |
| 1421 | NonCopiedGlobals.erase(I++); |
| 1422 | MadeChange = true; |
| 1423 | } else { |
| 1424 | ++I; |
| 1425 | } |
| 1426 | } |
| 1427 | |
| 1428 | // If requested, copy any aux calls that can reach copied nodes. |
| 1429 | if (!(CloneFlags & DontCloneAuxCallNodes)) { |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1430 | for (afc_iterator I = Graph.afc_begin(), E = Graph.afc_end(); I!=E; ++I) |
| 1431 | if (CopiedAuxCall.insert(&*I).second && |
| 1432 | PathExistsToClonedNode(*I, RC)) { |
| 1433 | AuxFunctionCalls.push_back(DSCallSite(*I, RC)); |
Chris Lattner | 2f34690 | 2004-03-04 03:57:53 +0000 | [diff] [blame] | 1434 | MadeChange = true; |
| 1435 | } |
Chris Lattner | c4ebdce | 2004-03-03 22:01:09 +0000 | [diff] [blame] | 1436 | } |
| 1437 | } |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1438 | |
Chris Lattner | 4c6cb7a | 2004-01-22 15:30:58 +0000 | [diff] [blame] | 1439 | } else { |
Chris Lattner | bb753c4 | 2005-02-03 18:40:25 +0000 | [diff] [blame] | 1440 | // Merge the return value with the return value of the context. |
| 1441 | Args[0].mergeWith(CS.getRetVal()); |
Chris Lattner | 4c6cb7a | 2004-01-22 15:30:58 +0000 | [diff] [blame] | 1442 | |
Chris Lattner | bb753c4 | 2005-02-03 18:40:25 +0000 | [diff] [blame] | 1443 | // Resolve all of the function arguments. |
| 1444 | for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) { |
Chris Lattner | e859444 | 2005-02-04 19:58:28 +0000 | [diff] [blame] | 1445 | if (i == Args.size()-1) |
Chris Lattner | bb753c4 | 2005-02-03 18:40:25 +0000 | [diff] [blame] | 1446 | break; |
Chris Lattner | 4c6cb7a | 2004-01-22 15:30:58 +0000 | [diff] [blame] | 1447 | |
Chris Lattner | bb753c4 | 2005-02-03 18:40:25 +0000 | [diff] [blame] | 1448 | // Add the link from the argument scalar to the provided value. |
| 1449 | Args[i+1].mergeWith(CS.getPtrArg(i)); |
Chris Lattner | 4c6cb7a | 2004-01-22 15:30:58 +0000 | [diff] [blame] | 1450 | } |
Chris Lattner | 076c1f9 | 2002-11-07 06:31:54 +0000 | [diff] [blame] | 1451 | } |
| 1452 | } |
| 1453 | |
Chris Lattner | e859444 | 2005-02-04 19:58:28 +0000 | [diff] [blame] | 1454 | |
| 1455 | |
| 1456 | /// mergeInGraph - The method is used for merging graphs together. If the |
| 1457 | /// argument graph is not *this, it makes a clone of the specified graph, then |
| 1458 | /// merges the nodes specified in the call site with the formal arguments in the |
| 1459 | /// graph. |
| 1460 | /// |
| 1461 | void DSGraph::mergeInGraph(const DSCallSite &CS, Function &F, |
| 1462 | const DSGraph &Graph, unsigned CloneFlags) { |
Chris Lattner | e859444 | 2005-02-04 19:58:28 +0000 | [diff] [blame] | 1463 | // Set up argument bindings. |
| 1464 | std::vector<DSNodeHandle> Args; |
| 1465 | Graph.getFunctionArgumentsForCall(&F, Args); |
| 1466 | |
| 1467 | mergeInGraph(CS, Args, Graph, CloneFlags); |
| 1468 | } |
| 1469 | |
Chris Lattner | 58f98d0 | 2003-07-02 04:38:49 +0000 | [diff] [blame] | 1470 | /// getCallSiteForArguments - Get the arguments and return value bindings for |
| 1471 | /// the specified function in the current graph. |
| 1472 | /// |
| 1473 | DSCallSite DSGraph::getCallSiteForArguments(Function &F) const { |
| 1474 | std::vector<DSNodeHandle> Args; |
| 1475 | |
Chris Lattner | e4d5c44 | 2005-03-15 04:54:21 +0000 | [diff] [blame] | 1476 | for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) |
Chris Lattner | 58f98d0 | 2003-07-02 04:38:49 +0000 | [diff] [blame] | 1477 | if (isPointerType(I->getType())) |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1478 | Args.push_back(getNodeForValue(I)); |
Chris Lattner | 58f98d0 | 2003-07-02 04:38:49 +0000 | [diff] [blame] | 1479 | |
Chris Lattner | 808a7ae | 2003-09-20 16:34:13 +0000 | [diff] [blame] | 1480 | return DSCallSite(CallSite(), getReturnNodeFor(F), &F, Args); |
Chris Lattner | 58f98d0 | 2003-07-02 04:38:49 +0000 | [diff] [blame] | 1481 | } |
| 1482 | |
Chris Lattner | 85fb1be | 2004-03-09 19:37:06 +0000 | [diff] [blame] | 1483 | /// getDSCallSiteForCallSite - Given an LLVM CallSite object that is live in |
| 1484 | /// the context of this graph, return the DSCallSite for it. |
| 1485 | DSCallSite DSGraph::getDSCallSiteForCallSite(CallSite CS) const { |
| 1486 | DSNodeHandle RetVal; |
| 1487 | Instruction *I = CS.getInstruction(); |
| 1488 | if (isPointerType(I->getType())) |
| 1489 | RetVal = getNodeForValue(I); |
| 1490 | |
| 1491 | std::vector<DSNodeHandle> Args; |
| 1492 | Args.reserve(CS.arg_end()-CS.arg_begin()); |
| 1493 | |
| 1494 | // Calculate the arguments vector... |
| 1495 | for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I) |
| 1496 | if (isPointerType((*I)->getType())) |
Chris Lattner | 94f8470 | 2005-03-17 19:56:56 +0000 | [diff] [blame] | 1497 | if (isa<ConstantPointerNull>(*I)) |
| 1498 | Args.push_back(DSNodeHandle()); |
| 1499 | else |
| 1500 | Args.push_back(getNodeForValue(*I)); |
Chris Lattner | 85fb1be | 2004-03-09 19:37:06 +0000 | [diff] [blame] | 1501 | |
| 1502 | // Add a new function call entry... |
| 1503 | if (Function *F = CS.getCalledFunction()) |
| 1504 | return DSCallSite(CS, RetVal, F, Args); |
| 1505 | else |
| 1506 | return DSCallSite(CS, RetVal, |
| 1507 | getNodeForValue(CS.getCalledValue()).getNode(), Args); |
| 1508 | } |
| 1509 | |
Chris Lattner | 58f98d0 | 2003-07-02 04:38:49 +0000 | [diff] [blame] | 1510 | |
Vikram S. Adve | 355e2ca | 2002-07-30 22:05:22 +0000 | [diff] [blame] | 1511 | |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1512 | // markIncompleteNodes - Mark the specified node as having contents that are not |
| 1513 | // known with the current analysis we have performed. Because a node makes all |
Chris Lattner | bd92b73 | 2003-06-19 21:15:11 +0000 | [diff] [blame] | 1514 | // of the nodes it can reach incomplete if the node itself is incomplete, we |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1515 | // must recursively traverse the data structure graph, marking all reachable |
| 1516 | // nodes as incomplete. |
| 1517 | // |
| 1518 | static void markIncompleteNode(DSNode *N) { |
| 1519 | // Stop recursion if no node, or if node already marked... |
Chris Lattner | 72d50a0 | 2003-06-28 21:58:28 +0000 | [diff] [blame] | 1520 | if (N == 0 || N->isIncomplete()) return; |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1521 | |
| 1522 | // Actually mark the node |
Chris Lattner | bd92b73 | 2003-06-19 21:15:11 +0000 | [diff] [blame] | 1523 | N->setIncompleteMarker(); |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1524 | |
Misha Brukman | 2f2d065 | 2003-09-11 18:14:24 +0000 | [diff] [blame] | 1525 | // Recursively process children... |
Chris Lattner | 6be0794 | 2005-02-09 03:20:43 +0000 | [diff] [blame] | 1526 | for (DSNode::edge_iterator I = N->edge_begin(),E = N->edge_end(); I != E; ++I) |
| 1527 | if (DSNode *DSN = I->getNode()) |
Chris Lattner | 08db719 | 2002-11-06 06:20:27 +0000 | [diff] [blame] | 1528 | markIncompleteNode(DSN); |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1529 | } |
| 1530 | |
Chris Lattner | e71ffc2 | 2002-11-11 03:36:55 +0000 | [diff] [blame] | 1531 | static void markIncomplete(DSCallSite &Call) { |
| 1532 | // Then the return value is certainly incomplete! |
| 1533 | markIncompleteNode(Call.getRetVal().getNode()); |
| 1534 | |
| 1535 | // All objects pointed to by function arguments are incomplete! |
| 1536 | for (unsigned i = 0, e = Call.getNumPtrArgs(); i != e; ++i) |
| 1537 | markIncompleteNode(Call.getPtrArg(i).getNode()); |
| 1538 | } |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1539 | |
| 1540 | // markIncompleteNodes - Traverse the graph, identifying nodes that may be |
| 1541 | // modified by other functions that have not been resolved yet. This marks |
| 1542 | // nodes that are reachable through three sources of "unknownness": |
| 1543 | // |
| 1544 | // Global Variables, Function Calls, and Incoming Arguments |
| 1545 | // |
| 1546 | // For any node that may have unknown components (because something outside the |
| 1547 | // scope of current analysis may have modified it), the 'Incomplete' flag is |
| 1548 | // added to the NodeType. |
| 1549 | // |
Chris Lattner | 394471f | 2003-01-23 22:05:33 +0000 | [diff] [blame] | 1550 | void DSGraph::markIncompleteNodes(unsigned Flags) { |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1551 | // Mark any incoming arguments as incomplete. |
Chris Lattner | 5a54063 | 2003-06-30 03:15:25 +0000 | [diff] [blame] | 1552 | if (Flags & DSGraph::MarkFormalArgs) |
| 1553 | for (ReturnNodesTy::iterator FI = ReturnNodes.begin(), E =ReturnNodes.end(); |
| 1554 | FI != E; ++FI) { |
| 1555 | Function &F = *FI->first; |
Chris Lattner | e4d5c44 | 2005-03-15 04:54:21 +0000 | [diff] [blame] | 1556 | for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) |
Chris Lattner | b5ecd2e | 2005-03-13 20:22:10 +0000 | [diff] [blame] | 1557 | if (isPointerType(I->getType())) |
| 1558 | markIncompleteNode(getNodeForValue(I).getNode()); |
Chris Lattner | a4319e5 | 2005-03-12 14:58:28 +0000 | [diff] [blame] | 1559 | markIncompleteNode(FI->second.getNode()); |
Chris Lattner | 5a54063 | 2003-06-30 03:15:25 +0000 | [diff] [blame] | 1560 | } |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1561 | |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1562 | // Mark stuff passed into functions calls as being incomplete. |
Chris Lattner | e71ffc2 | 2002-11-11 03:36:55 +0000 | [diff] [blame] | 1563 | if (!shouldPrintAuxCalls()) |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1564 | for (std::list<DSCallSite>::iterator I = FunctionCalls.begin(), |
| 1565 | E = FunctionCalls.end(); I != E; ++I) |
| 1566 | markIncomplete(*I); |
Chris Lattner | e71ffc2 | 2002-11-11 03:36:55 +0000 | [diff] [blame] | 1567 | else |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1568 | for (std::list<DSCallSite>::iterator I = AuxFunctionCalls.begin(), |
| 1569 | E = AuxFunctionCalls.end(); I != E; ++I) |
| 1570 | markIncomplete(*I); |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1571 | |
Chris Lattner | e2bc7b2 | 2005-03-13 20:36:01 +0000 | [diff] [blame] | 1572 | // Mark all global nodes as incomplete. |
| 1573 | for (DSScalarMap::global_iterator I = ScalarMap.global_begin(), |
| 1574 | E = ScalarMap.global_end(); I != E; ++I) |
| 1575 | if (GlobalVariable *GV = dyn_cast<GlobalVariable>(*I)) |
| 1576 | if (!GV->hasInitializer() || // Always mark external globals incomp. |
| 1577 | (!GV->isConstant() && (Flags & DSGraph::IgnoreGlobals) == 0)) |
| 1578 | markIncompleteNode(ScalarMap[GV].getNode()); |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1579 | } |
| 1580 | |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1581 | static inline void killIfUselessEdge(DSNodeHandle &Edge) { |
| 1582 | if (DSNode *N = Edge.getNode()) // Is there an edge? |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 1583 | if (N->getNumReferrers() == 1) // Does it point to a lonely node? |
Chris Lattner | bd92b73 | 2003-06-19 21:15:11 +0000 | [diff] [blame] | 1584 | // No interesting info? |
| 1585 | if ((N->getNodeFlags() & ~DSNode::Incomplete) == 0 && |
Chris Lattner | 1855292 | 2002-11-18 21:44:46 +0000 | [diff] [blame] | 1586 | N->getType() == Type::VoidTy && !N->isNodeCompletelyFolded()) |
Chris Lattner | efffdc9 | 2004-07-07 06:12:52 +0000 | [diff] [blame] | 1587 | Edge.setTo(0, 0); // Kill the edge! |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1588 | } |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1589 | |
Chris Lattner | 82c6c72 | 2005-03-20 02:41:38 +0000 | [diff] [blame] | 1590 | #if 0 |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1591 | static inline bool nodeContainsExternalFunction(const DSNode *N) { |
| 1592 | const std::vector<GlobalValue*> &Globals = N->getGlobals(); |
| 1593 | for (unsigned i = 0, e = Globals.size(); i != e; ++i) |
Chris Lattner | 857eb06 | 2004-10-30 05:41:23 +0000 | [diff] [blame] | 1594 | if (Globals[i]->isExternal() && isa<Function>(Globals[i])) |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1595 | return true; |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1596 | return false; |
| 1597 | } |
Chris Lattner | 82c6c72 | 2005-03-20 02:41:38 +0000 | [diff] [blame] | 1598 | #endif |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1599 | |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1600 | static void removeIdenticalCalls(std::list<DSCallSite> &Calls) { |
Vikram S. Adve | 355e2ca | 2002-07-30 22:05:22 +0000 | [diff] [blame] | 1601 | // Remove trivially identical function calls |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1602 | Calls.sort(); // Sort by callee as primary key! |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1603 | |
| 1604 | // Scan the call list cleaning it up as necessary... |
Chris Lattner | 923fc05 | 2003-02-05 21:59:58 +0000 | [diff] [blame] | 1605 | DSNode *LastCalleeNode = 0; |
| 1606 | Function *LastCalleeFunc = 0; |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1607 | unsigned NumDuplicateCalls = 0; |
| 1608 | bool LastCalleeContainsExternalFunction = false; |
Chris Lattner | 857eb06 | 2004-10-30 05:41:23 +0000 | [diff] [blame] | 1609 | |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1610 | unsigned NumDeleted = 0; |
| 1611 | for (std::list<DSCallSite>::iterator I = Calls.begin(), E = Calls.end(); |
| 1612 | I != E;) { |
| 1613 | DSCallSite &CS = *I; |
| 1614 | std::list<DSCallSite>::iterator OldIt = I++; |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1615 | |
Chris Lattner | e425844 | 2002-11-11 21:35:38 +0000 | [diff] [blame] | 1616 | // If the Callee is a useless edge, this must be an unreachable call site, |
| 1617 | // eliminate it. |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 1618 | if (CS.isIndirectCall() && CS.getCalleeNode()->getNumReferrers() == 1 && |
Chris Lattner | abcdf80 | 2004-02-26 03:43:43 +0000 | [diff] [blame] | 1619 | CS.getCalleeNode()->isComplete() && |
Chris Lattner | 82c6c72 | 2005-03-20 02:41:38 +0000 | [diff] [blame] | 1620 | CS.getCalleeNode()->getGlobalsList().empty()) { // No useful info? |
Chris Lattner | 64507e3 | 2004-01-28 01:19:52 +0000 | [diff] [blame] | 1621 | #ifndef NDEBUG |
Chris Lattner | abcdf80 | 2004-02-26 03:43:43 +0000 | [diff] [blame] | 1622 | std::cerr << "WARNING: Useless call site found.\n"; |
Chris Lattner | 64507e3 | 2004-01-28 01:19:52 +0000 | [diff] [blame] | 1623 | #endif |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1624 | Calls.erase(OldIt); |
| 1625 | ++NumDeleted; |
| 1626 | continue; |
| 1627 | } |
| 1628 | |
| 1629 | // If the return value or any arguments point to a void node with no |
| 1630 | // information at all in it, and the call node is the only node to point |
| 1631 | // to it, remove the edge to the node (killing the node). |
| 1632 | // |
| 1633 | killIfUselessEdge(CS.getRetVal()); |
| 1634 | for (unsigned a = 0, e = CS.getNumPtrArgs(); a != e; ++a) |
| 1635 | killIfUselessEdge(CS.getPtrArg(a)); |
| 1636 | |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1637 | #if 0 |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1638 | // If this call site calls the same function as the last call site, and if |
| 1639 | // the function pointer contains an external function, this node will |
| 1640 | // never be resolved. Merge the arguments of the call node because no |
| 1641 | // information will be lost. |
| 1642 | // |
| 1643 | if ((CS.isDirectCall() && CS.getCalleeFunc() == LastCalleeFunc) || |
| 1644 | (CS.isIndirectCall() && CS.getCalleeNode() == LastCalleeNode)) { |
| 1645 | ++NumDuplicateCalls; |
| 1646 | if (NumDuplicateCalls == 1) { |
| 1647 | if (LastCalleeNode) |
| 1648 | LastCalleeContainsExternalFunction = |
| 1649 | nodeContainsExternalFunction(LastCalleeNode); |
| 1650 | else |
| 1651 | LastCalleeContainsExternalFunction = LastCalleeFunc->isExternal(); |
Chris Lattner | e425844 | 2002-11-11 21:35:38 +0000 | [diff] [blame] | 1652 | } |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1653 | |
| 1654 | // It is not clear why, but enabling this code makes DSA really |
| 1655 | // sensitive to node forwarding. Basically, with this enabled, DSA |
| 1656 | // performs different number of inlinings based on which nodes are |
| 1657 | // forwarding or not. This is clearly a problem, so this code is |
| 1658 | // disabled until this can be resolved. |
| 1659 | #if 1 |
| 1660 | if (LastCalleeContainsExternalFunction |
| 1661 | #if 0 |
| 1662 | || |
| 1663 | // This should be more than enough context sensitivity! |
| 1664 | // FIXME: Evaluate how many times this is tripped! |
| 1665 | NumDuplicateCalls > 20 |
| 1666 | #endif |
| 1667 | ) { |
| 1668 | |
| 1669 | std::list<DSCallSite>::iterator PrevIt = OldIt; |
| 1670 | --PrevIt; |
| 1671 | PrevIt->mergeWith(CS); |
| 1672 | |
| 1673 | // No need to keep this call anymore. |
| 1674 | Calls.erase(OldIt); |
| 1675 | ++NumDeleted; |
| 1676 | continue; |
| 1677 | } |
| 1678 | #endif |
| 1679 | } else { |
| 1680 | if (CS.isDirectCall()) { |
| 1681 | LastCalleeFunc = CS.getCalleeFunc(); |
| 1682 | LastCalleeNode = 0; |
| 1683 | } else { |
| 1684 | LastCalleeNode = CS.getCalleeNode(); |
| 1685 | LastCalleeFunc = 0; |
| 1686 | } |
| 1687 | NumDuplicateCalls = 0; |
| 1688 | } |
| 1689 | #endif |
| 1690 | |
| 1691 | if (I != Calls.end() && CS == *I) { |
| 1692 | Calls.erase(OldIt); |
| 1693 | ++NumDeleted; |
| 1694 | continue; |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1695 | } |
| 1696 | } |
Chris Lattner | 857eb06 | 2004-10-30 05:41:23 +0000 | [diff] [blame] | 1697 | |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1698 | // Resort now that we simplified things. |
| 1699 | Calls.sort(); |
Chris Lattner | 857eb06 | 2004-10-30 05:41:23 +0000 | [diff] [blame] | 1700 | |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1701 | // Now that we are in sorted order, eliminate duplicates. |
Chris Lattner | f9aace2 | 2005-01-31 00:10:58 +0000 | [diff] [blame] | 1702 | std::list<DSCallSite>::iterator CI = Calls.begin(), CE = Calls.end(); |
| 1703 | if (CI != CE) |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1704 | while (1) { |
Chris Lattner | f9aace2 | 2005-01-31 00:10:58 +0000 | [diff] [blame] | 1705 | std::list<DSCallSite>::iterator OldIt = CI++; |
| 1706 | if (CI == CE) break; |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1707 | |
| 1708 | // If this call site is now the same as the previous one, we can delete it |
| 1709 | // as a duplicate. |
Chris Lattner | f9aace2 | 2005-01-31 00:10:58 +0000 | [diff] [blame] | 1710 | if (*OldIt == *CI) { |
| 1711 | Calls.erase(CI); |
| 1712 | CI = OldIt; |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1713 | ++NumDeleted; |
| 1714 | } |
| 1715 | } |
| 1716 | |
| 1717 | //Calls.erase(std::unique(Calls.begin(), Calls.end()), Calls.end()); |
Vikram S. Adve | 355e2ca | 2002-07-30 22:05:22 +0000 | [diff] [blame] | 1718 | |
Chris Lattner | 33312f7 | 2002-11-08 01:21:07 +0000 | [diff] [blame] | 1719 | // Track the number of call nodes merged away... |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1720 | NumCallNodesMerged += NumDeleted; |
Chris Lattner | 33312f7 | 2002-11-08 01:21:07 +0000 | [diff] [blame] | 1721 | |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1722 | DEBUG(if (NumDeleted) |
| 1723 | std::cerr << "Merged " << NumDeleted << " call nodes.\n";); |
Vikram S. Adve | 355e2ca | 2002-07-30 22:05:22 +0000 | [diff] [blame] | 1724 | } |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1725 | |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1726 | |
Chris Lattner | e221976 | 2002-07-18 18:22:40 +0000 | [diff] [blame] | 1727 | // removeTriviallyDeadNodes - After the graph has been constructed, this method |
| 1728 | // removes all unreachable nodes that are created because they got merged with |
| 1729 | // other nodes in the graph. These nodes will all be trivially unreachable, so |
| 1730 | // we don't have to perform any non-trivial analysis here. |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1731 | // |
Chris Lattner | f40f0a3 | 2002-11-09 22:07:02 +0000 | [diff] [blame] | 1732 | void DSGraph::removeTriviallyDeadNodes() { |
Chris Lattner | 93ddd7e | 2004-01-22 16:36:28 +0000 | [diff] [blame] | 1733 | TIME_REGION(X, "removeTriviallyDeadNodes"); |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1734 | |
Chris Lattner | 5ace1e4 | 2004-07-08 07:25:51 +0000 | [diff] [blame] | 1735 | #if 0 |
| 1736 | /// NOTE: This code is disabled. This slows down DSA on 177.mesa |
| 1737 | /// substantially! |
| 1738 | |
Chris Lattner | bab8c28 | 2003-09-20 21:34:07 +0000 | [diff] [blame] | 1739 | // Loop over all of the nodes in the graph, calling getNode on each field. |
| 1740 | // This will cause all nodes to update their forwarding edges, causing |
| 1741 | // forwarded nodes to be delete-able. |
Chris Lattner | 5ace1e4 | 2004-07-08 07:25:51 +0000 | [diff] [blame] | 1742 | { TIME_REGION(X, "removeTriviallyDeadNodes:node_iterate"); |
Chris Lattner | 9fd37ba | 2004-02-08 00:23:16 +0000 | [diff] [blame] | 1743 | for (node_iterator NI = node_begin(), E = node_end(); NI != E; ++NI) { |
Chris Lattner | 84b80a2 | 2005-03-16 22:42:19 +0000 | [diff] [blame] | 1744 | DSNode &N = *NI; |
| 1745 | for (unsigned l = 0, e = N.getNumLinks(); l != e; ++l) |
| 1746 | N.getLink(l*N.getPointerSize()).getNode(); |
Chris Lattner | bab8c28 | 2003-09-20 21:34:07 +0000 | [diff] [blame] | 1747 | } |
Chris Lattner | 5ace1e4 | 2004-07-08 07:25:51 +0000 | [diff] [blame] | 1748 | } |
Chris Lattner | bab8c28 | 2003-09-20 21:34:07 +0000 | [diff] [blame] | 1749 | |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1750 | // NOTE: This code is disabled. Though it should, in theory, allow us to |
| 1751 | // remove more nodes down below, the scan of the scalar map is incredibly |
| 1752 | // expensive for certain programs (with large SCCs). In the future, if we can |
| 1753 | // make the scalar map scan more efficient, then we can reenable this. |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1754 | { TIME_REGION(X, "removeTriviallyDeadNodes:scalarmap"); |
| 1755 | |
Chris Lattner | 4c6cb7a | 2004-01-22 15:30:58 +0000 | [diff] [blame] | 1756 | // Likewise, forward any edges from the scalar nodes. While we are at it, |
| 1757 | // clean house a bit. |
Chris Lattner | 62482e5 | 2004-01-28 09:15:42 +0000 | [diff] [blame] | 1758 | for (DSScalarMap::iterator I = ScalarMap.begin(),E = ScalarMap.end();I != E;){ |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1759 | I->second.getNode(); |
| 1760 | ++I; |
Chris Lattner | 4c6cb7a | 2004-01-22 15:30:58 +0000 | [diff] [blame] | 1761 | } |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1762 | } |
| 1763 | #endif |
Vikram S. Adve | 78bbec7 | 2003-07-16 21:36:31 +0000 | [diff] [blame] | 1764 | bool isGlobalsGraph = !GlobalsGraph; |
| 1765 | |
Chris Lattner | 9fd37ba | 2004-02-08 00:23:16 +0000 | [diff] [blame] | 1766 | for (NodeListTy::iterator NI = Nodes.begin(), E = Nodes.end(); NI != E; ) { |
Chris Lattner | 28897e1 | 2004-02-08 00:53:26 +0000 | [diff] [blame] | 1767 | DSNode &Node = *NI; |
Vikram S. Adve | 78bbec7 | 2003-07-16 21:36:31 +0000 | [diff] [blame] | 1768 | |
| 1769 | // Do not remove *any* global nodes in the globals graph. |
| 1770 | // This is a special case because such nodes may not have I, M, R flags set. |
Chris Lattner | 28897e1 | 2004-02-08 00:53:26 +0000 | [diff] [blame] | 1771 | if (Node.isGlobalNode() && isGlobalsGraph) { |
Chris Lattner | 9fd37ba | 2004-02-08 00:23:16 +0000 | [diff] [blame] | 1772 | ++NI; |
Vikram S. Adve | 78bbec7 | 2003-07-16 21:36:31 +0000 | [diff] [blame] | 1773 | continue; |
Chris Lattner | 9fd37ba | 2004-02-08 00:23:16 +0000 | [diff] [blame] | 1774 | } |
Vikram S. Adve | 78bbec7 | 2003-07-16 21:36:31 +0000 | [diff] [blame] | 1775 | |
Chris Lattner | 28897e1 | 2004-02-08 00:53:26 +0000 | [diff] [blame] | 1776 | if (Node.isComplete() && !Node.isModified() && !Node.isRead()) { |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 1777 | // This is a useless node if it has no mod/ref info (checked above), |
| 1778 | // outgoing edges (which it cannot, as it is not modified in this |
| 1779 | // context), and it has no incoming edges. If it is a global node it may |
| 1780 | // have all of these properties and still have incoming edges, due to the |
| 1781 | // scalar map, so we check those now. |
| 1782 | // |
Chris Lattner | 82c6c72 | 2005-03-20 02:41:38 +0000 | [diff] [blame] | 1783 | if (Node.getNumReferrers() == Node.getGlobalsList().size()) { |
| 1784 | const std::vector<GlobalValue*> &Globals = Node.getGlobalsList(); |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 1785 | |
Chris Lattner | 17a93e2 | 2004-01-29 03:32:15 +0000 | [diff] [blame] | 1786 | // Loop through and make sure all of the globals are referring directly |
| 1787 | // to the node... |
| 1788 | for (unsigned j = 0, e = Globals.size(); j != e; ++j) { |
| 1789 | DSNode *N = getNodeForValue(Globals[j]).getNode(); |
Chris Lattner | 28897e1 | 2004-02-08 00:53:26 +0000 | [diff] [blame] | 1790 | assert(N == &Node && "ScalarMap doesn't match globals list!"); |
Chris Lattner | 17a93e2 | 2004-01-29 03:32:15 +0000 | [diff] [blame] | 1791 | } |
| 1792 | |
Chris Lattner | bd92b73 | 2003-06-19 21:15:11 +0000 | [diff] [blame] | 1793 | // Make sure NumReferrers still agrees, if so, the node is truly dead. |
Chris Lattner | 28897e1 | 2004-02-08 00:53:26 +0000 | [diff] [blame] | 1794 | if (Node.getNumReferrers() == Globals.size()) { |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 1795 | for (unsigned j = 0, e = Globals.size(); j != e; ++j) |
| 1796 | ScalarMap.erase(Globals[j]); |
Chris Lattner | 28897e1 | 2004-02-08 00:53:26 +0000 | [diff] [blame] | 1797 | Node.makeNodeDead(); |
Chris Lattner | c3f5f77 | 2004-02-08 01:51:48 +0000 | [diff] [blame] | 1798 | ++NumTrivialGlobalDNE; |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 1799 | } |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 1800 | } |
| 1801 | } |
| 1802 | |
Chris Lattner | 28897e1 | 2004-02-08 00:53:26 +0000 | [diff] [blame] | 1803 | if (Node.getNodeFlags() == 0 && Node.hasNoReferrers()) { |
Chris Lattner | 2609c07 | 2003-02-10 18:18:18 +0000 | [diff] [blame] | 1804 | // This node is dead! |
Chris Lattner | 28897e1 | 2004-02-08 00:53:26 +0000 | [diff] [blame] | 1805 | NI = Nodes.erase(NI); // Erase & remove from node list. |
Chris Lattner | c3f5f77 | 2004-02-08 01:51:48 +0000 | [diff] [blame] | 1806 | ++NumTrivialDNE; |
Chris Lattner | 9fd37ba | 2004-02-08 00:23:16 +0000 | [diff] [blame] | 1807 | } else { |
| 1808 | ++NI; |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1809 | } |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 1810 | } |
Chris Lattner | c3f5f77 | 2004-02-08 01:51:48 +0000 | [diff] [blame] | 1811 | |
| 1812 | removeIdenticalCalls(FunctionCalls); |
| 1813 | removeIdenticalCalls(AuxFunctionCalls); |
Chris Lattner | 0d9bab8 | 2002-07-18 00:12:30 +0000 | [diff] [blame] | 1814 | } |
| 1815 | |
| 1816 | |
Chris Lattner | 5c7380e | 2003-01-29 21:10:20 +0000 | [diff] [blame] | 1817 | /// markReachableNodes - This method recursively traverses the specified |
| 1818 | /// DSNodes, marking any nodes which are reachable. All reachable nodes it adds |
| 1819 | /// to the set, which allows it to only traverse visited nodes once. |
| 1820 | /// |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1821 | void DSNode::markReachableNodes(hash_set<const DSNode*> &ReachableNodes) const { |
Chris Lattner | 5c7380e | 2003-01-29 21:10:20 +0000 | [diff] [blame] | 1822 | if (this == 0) return; |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 1823 | assert(getForwardNode() == 0 && "Cannot mark a forwarded node!"); |
Chris Lattner | 4c6cb7a | 2004-01-22 15:30:58 +0000 | [diff] [blame] | 1824 | if (ReachableNodes.insert(this).second) // Is newly reachable? |
Chris Lattner | 6be0794 | 2005-02-09 03:20:43 +0000 | [diff] [blame] | 1825 | for (DSNode::const_edge_iterator I = edge_begin(), E = edge_end(); |
| 1826 | I != E; ++I) |
| 1827 | I->getNode()->markReachableNodes(ReachableNodes); |
Chris Lattner | 5c7380e | 2003-01-29 21:10:20 +0000 | [diff] [blame] | 1828 | } |
| 1829 | |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1830 | void DSCallSite::markReachableNodes(hash_set<const DSNode*> &Nodes) const { |
Chris Lattner | 5c7380e | 2003-01-29 21:10:20 +0000 | [diff] [blame] | 1831 | getRetVal().getNode()->markReachableNodes(Nodes); |
Chris Lattner | 923fc05 | 2003-02-05 21:59:58 +0000 | [diff] [blame] | 1832 | if (isIndirectCall()) getCalleeNode()->markReachableNodes(Nodes); |
Chris Lattner | 5c7380e | 2003-01-29 21:10:20 +0000 | [diff] [blame] | 1833 | |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 1834 | for (unsigned i = 0, e = getNumPtrArgs(); i != e; ++i) |
| 1835 | getPtrArg(i).getNode()->markReachableNodes(Nodes); |
Chris Lattner | e221976 | 2002-07-18 18:22:40 +0000 | [diff] [blame] | 1836 | } |
| 1837 | |
Chris Lattner | a1220af | 2003-02-01 06:17:02 +0000 | [diff] [blame] | 1838 | // CanReachAliveNodes - Simple graph walker that recursively traverses the graph |
| 1839 | // looking for a node that is marked alive. If an alive node is found, return |
| 1840 | // true, otherwise return false. If an alive node is reachable, this node is |
| 1841 | // marked as alive... |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1842 | // |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1843 | static bool CanReachAliveNodes(DSNode *N, hash_set<const DSNode*> &Alive, |
| 1844 | hash_set<const DSNode*> &Visited, |
Chris Lattner | 85cfe01 | 2003-07-03 02:03:53 +0000 | [diff] [blame] | 1845 | bool IgnoreGlobals) { |
Vikram S. Adve | 355e2ca | 2002-07-30 22:05:22 +0000 | [diff] [blame] | 1846 | if (N == 0) return false; |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 1847 | assert(N->getForwardNode() == 0 && "Cannot mark a forwarded node!"); |
Vikram S. Adve | 355e2ca | 2002-07-30 22:05:22 +0000 | [diff] [blame] | 1848 | |
Chris Lattner | 85cfe01 | 2003-07-03 02:03:53 +0000 | [diff] [blame] | 1849 | // If this is a global node, it will end up in the globals graph anyway, so we |
| 1850 | // don't need to worry about it. |
| 1851 | if (IgnoreGlobals && N->isGlobalNode()) return false; |
| 1852 | |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1853 | // If we know that this node is alive, return so! |
| 1854 | if (Alive.count(N)) return true; |
Vikram S. Adve | 355e2ca | 2002-07-30 22:05:22 +0000 | [diff] [blame] | 1855 | |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1856 | // Otherwise, we don't think the node is alive yet, check for infinite |
| 1857 | // recursion. |
Chris Lattner | 41c04f7 | 2003-02-01 04:52:08 +0000 | [diff] [blame] | 1858 | if (Visited.count(N)) return false; // Found a cycle |
Chris Lattner | a1220af | 2003-02-01 06:17:02 +0000 | [diff] [blame] | 1859 | Visited.insert(N); // No recursion, insert into Visited... |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1860 | |
Chris Lattner | 6be0794 | 2005-02-09 03:20:43 +0000 | [diff] [blame] | 1861 | for (DSNode::edge_iterator I = N->edge_begin(),E = N->edge_end(); I != E; ++I) |
| 1862 | if (CanReachAliveNodes(I->getNode(), Alive, Visited, IgnoreGlobals)) { |
Chris Lattner | a1220af | 2003-02-01 06:17:02 +0000 | [diff] [blame] | 1863 | N->markReachableNodes(Alive); |
| 1864 | return true; |
| 1865 | } |
| 1866 | return false; |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1867 | } |
Vikram S. Adve | 355e2ca | 2002-07-30 22:05:22 +0000 | [diff] [blame] | 1868 | |
Chris Lattner | a1220af | 2003-02-01 06:17:02 +0000 | [diff] [blame] | 1869 | // CallSiteUsesAliveArgs - Return true if the specified call site can reach any |
| 1870 | // alive nodes. |
| 1871 | // |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1872 | static bool CallSiteUsesAliveArgs(const DSCallSite &CS, |
| 1873 | hash_set<const DSNode*> &Alive, |
| 1874 | hash_set<const DSNode*> &Visited, |
Chris Lattner | 85cfe01 | 2003-07-03 02:03:53 +0000 | [diff] [blame] | 1875 | bool IgnoreGlobals) { |
| 1876 | if (CanReachAliveNodes(CS.getRetVal().getNode(), Alive, Visited, |
| 1877 | IgnoreGlobals)) |
Chris Lattner | 923fc05 | 2003-02-05 21:59:58 +0000 | [diff] [blame] | 1878 | return true; |
| 1879 | if (CS.isIndirectCall() && |
Chris Lattner | 85cfe01 | 2003-07-03 02:03:53 +0000 | [diff] [blame] | 1880 | CanReachAliveNodes(CS.getCalleeNode(), Alive, Visited, IgnoreGlobals)) |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1881 | return true; |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 1882 | for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) |
Chris Lattner | 85cfe01 | 2003-07-03 02:03:53 +0000 | [diff] [blame] | 1883 | if (CanReachAliveNodes(CS.getPtrArg(i).getNode(), Alive, Visited, |
| 1884 | IgnoreGlobals)) |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1885 | return true; |
Vikram S. Adve | 355e2ca | 2002-07-30 22:05:22 +0000 | [diff] [blame] | 1886 | return false; |
| 1887 | } |
| 1888 | |
Chris Lattner | e221976 | 2002-07-18 18:22:40 +0000 | [diff] [blame] | 1889 | // removeDeadNodes - Use a more powerful reachability analysis to eliminate |
| 1890 | // subgraphs that are unreachable. This often occurs because the data |
| 1891 | // structure doesn't "escape" into it's caller, and thus should be eliminated |
| 1892 | // from the caller's graph entirely. This is only appropriate to use when |
| 1893 | // inlining graphs. |
| 1894 | // |
Chris Lattner | 394471f | 2003-01-23 22:05:33 +0000 | [diff] [blame] | 1895 | void DSGraph::removeDeadNodes(unsigned Flags) { |
Chris Lattner | 9dc4185 | 2003-11-12 04:57:58 +0000 | [diff] [blame] | 1896 | DEBUG(AssertGraphOK(); if (GlobalsGraph) GlobalsGraph->AssertGraphOK()); |
Chris Lattner | 85cfe01 | 2003-07-03 02:03:53 +0000 | [diff] [blame] | 1897 | |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 1898 | // Reduce the amount of work we have to do... remove dummy nodes left over by |
| 1899 | // merging... |
Chris Lattner | a3fd88d | 2004-01-28 03:24:41 +0000 | [diff] [blame] | 1900 | removeTriviallyDeadNodes(); |
Vikram S. Adve | 355e2ca | 2002-07-30 22:05:22 +0000 | [diff] [blame] | 1901 | |
Chris Lattner | 93ddd7e | 2004-01-22 16:36:28 +0000 | [diff] [blame] | 1902 | TIME_REGION(X, "removeDeadNodes"); |
| 1903 | |
Misha Brukman | 2f2d065 | 2003-09-11 18:14:24 +0000 | [diff] [blame] | 1904 | // FIXME: Merge non-trivially identical call nodes... |
Chris Lattner | e221976 | 2002-07-18 18:22:40 +0000 | [diff] [blame] | 1905 | |
| 1906 | // Alive - a set that holds all nodes found to be reachable/alive. |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1907 | hash_set<const DSNode*> Alive; |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1908 | std::vector<std::pair<Value*, DSNode*> > GlobalNodes; |
Chris Lattner | e221976 | 2002-07-18 18:22:40 +0000 | [diff] [blame] | 1909 | |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1910 | // Copy and merge all information about globals to the GlobalsGraph if this is |
| 1911 | // not a final pass (where unreachable globals are removed). |
| 1912 | // |
| 1913 | // Strip all alloca bits since the current function is only for the BU pass. |
| 1914 | // Strip all incomplete bits since they are short-lived properties and they |
| 1915 | // will be correctly computed when rematerializing nodes into the functions. |
| 1916 | // |
| 1917 | ReachabilityCloner GGCloner(*GlobalsGraph, *this, DSGraph::StripAllocaBit | |
| 1918 | DSGraph::StripIncompleteBit); |
| 1919 | |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1920 | // Mark all nodes reachable by (non-global) scalar nodes as alive... |
Chris Lattner | f4f6227 | 2005-03-19 22:23:45 +0000 | [diff] [blame] | 1921 | { TIME_REGION(Y, "removeDeadNodes:scalarscan"); |
| 1922 | for (DSScalarMap::iterator I = ScalarMap.begin(), E = ScalarMap.end(); |
| 1923 | I != E; ++I) |
Chris Lattner | 5f07a8b | 2003-02-14 06:28:00 +0000 | [diff] [blame] | 1924 | if (isa<GlobalValue>(I->first)) { // Keep track of global nodes |
Chris Lattner | 6f96774 | 2004-10-30 04:05:01 +0000 | [diff] [blame] | 1925 | assert(!I->second.isNull() && "Null global node?"); |
Vikram S. Adve | 78bbec7 | 2003-07-16 21:36:31 +0000 | [diff] [blame] | 1926 | assert(I->second.getNode()->isGlobalNode() && "Should be a global node!"); |
Chris Lattner | 5f07a8b | 2003-02-14 06:28:00 +0000 | [diff] [blame] | 1927 | GlobalNodes.push_back(std::make_pair(I->first, I->second.getNode())); |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1928 | |
| 1929 | // Make sure that all globals are cloned over as roots. |
Chris Lattner | 00948c0 | 2004-01-28 02:05:05 +0000 | [diff] [blame] | 1930 | if (!(Flags & DSGraph::RemoveUnreachableGlobals)) { |
| 1931 | DSGraph::ScalarMapTy::iterator SMI = |
| 1932 | GlobalsGraph->getScalarMap().find(I->first); |
| 1933 | if (SMI != GlobalsGraph->getScalarMap().end()) |
| 1934 | GGCloner.merge(SMI->second, I->second); |
| 1935 | else |
| 1936 | GGCloner.getClonedNH(I->second); |
| 1937 | } |
Chris Lattner | 5f07a8b | 2003-02-14 06:28:00 +0000 | [diff] [blame] | 1938 | } else { |
Chris Lattner | f4f6227 | 2005-03-19 22:23:45 +0000 | [diff] [blame] | 1939 | I->second.getNode()->markReachableNodes(Alive); |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 1940 | } |
Chris Lattner | f4f6227 | 2005-03-19 22:23:45 +0000 | [diff] [blame] | 1941 | } |
Chris Lattner | e221976 | 2002-07-18 18:22:40 +0000 | [diff] [blame] | 1942 | |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1943 | // The return values are alive as well. |
Chris Lattner | 5a54063 | 2003-06-30 03:15:25 +0000 | [diff] [blame] | 1944 | for (ReturnNodesTy::iterator I = ReturnNodes.begin(), E = ReturnNodes.end(); |
| 1945 | I != E; ++I) |
| 1946 | I->second.getNode()->markReachableNodes(Alive); |
Vikram S. Adve | 355e2ca | 2002-07-30 22:05:22 +0000 | [diff] [blame] | 1947 | |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 1948 | // Mark any nodes reachable by primary calls as alive... |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1949 | for (fc_iterator I = fc_begin(), E = fc_end(); I != E; ++I) |
| 1950 | I->markReachableNodes(Alive); |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 1951 | |
Vikram S. Adve | 78bbec7 | 2003-07-16 21:36:31 +0000 | [diff] [blame] | 1952 | |
| 1953 | // Now find globals and aux call nodes that are already live or reach a live |
| 1954 | // value (which makes them live in turn), and continue till no more are found. |
| 1955 | // |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 1956 | bool Iterate; |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1957 | hash_set<const DSNode*> Visited; |
| 1958 | hash_set<const DSCallSite*> AuxFCallsAlive; |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 1959 | do { |
| 1960 | Visited.clear(); |
Chris Lattner | 7079386 | 2003-07-02 23:57:05 +0000 | [diff] [blame] | 1961 | // If any global node points to a non-global that is "alive", the global is |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 1962 | // "alive" as well... Remove it from the GlobalNodes list so we only have |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 1963 | // unreachable globals in the list. |
| 1964 | // |
| 1965 | Iterate = false; |
Vikram S. Adve | 78bbec7 | 2003-07-16 21:36:31 +0000 | [diff] [blame] | 1966 | if (!(Flags & DSGraph::RemoveUnreachableGlobals)) |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 1967 | for (unsigned i = 0; i != GlobalNodes.size(); ++i) |
| 1968 | if (CanReachAliveNodes(GlobalNodes[i].second, Alive, Visited, |
| 1969 | Flags & DSGraph::RemoveUnreachableGlobals)) { |
| 1970 | std::swap(GlobalNodes[i--], GlobalNodes.back()); // Move to end to... |
| 1971 | GlobalNodes.pop_back(); // erase efficiently |
| 1972 | Iterate = true; |
| 1973 | } |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1974 | |
Vikram S. Adve | 78bbec7 | 2003-07-16 21:36:31 +0000 | [diff] [blame] | 1975 | // Mark only unresolvable call nodes for moving to the GlobalsGraph since |
| 1976 | // call nodes that get resolved will be difficult to remove from that graph. |
| 1977 | // The final unresolved call nodes must be handled specially at the end of |
| 1978 | // the BU pass (i.e., in main or other roots of the call graph). |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1979 | for (afc_iterator CI = afc_begin(), E = afc_end(); CI != E; ++CI) |
Chris Lattner | d7642c4 | 2005-02-24 18:48:07 +0000 | [diff] [blame] | 1980 | if (!AuxFCallsAlive.count(&*CI) && |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1981 | (CI->isIndirectCall() |
| 1982 | || CallSiteUsesAliveArgs(*CI, Alive, Visited, |
Vikram S. Adve | 78bbec7 | 2003-07-16 21:36:31 +0000 | [diff] [blame] | 1983 | Flags & DSGraph::RemoveUnreachableGlobals))) { |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1984 | CI->markReachableNodes(Alive); |
Chris Lattner | d7642c4 | 2005-02-24 18:48:07 +0000 | [diff] [blame] | 1985 | AuxFCallsAlive.insert(&*CI); |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 1986 | Iterate = true; |
| 1987 | } |
| 1988 | } while (Iterate); |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 1989 | |
Vikram S. Adve | 78bbec7 | 2003-07-16 21:36:31 +0000 | [diff] [blame] | 1990 | // Move dead aux function calls to the end of the list |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 1991 | unsigned CurIdx = 0; |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 1992 | for (std::list<DSCallSite>::iterator CI = AuxFunctionCalls.begin(), |
| 1993 | E = AuxFunctionCalls.end(); CI != E; ) |
| 1994 | if (AuxFCallsAlive.count(&*CI)) |
| 1995 | ++CI; |
| 1996 | else { |
| 1997 | // Copy and merge global nodes and dead aux call nodes into the |
| 1998 | // GlobalsGraph, and all nodes reachable from those nodes. Update their |
| 1999 | // target pointers using the GGCloner. |
| 2000 | // |
| 2001 | if (!(Flags & DSGraph::RemoveUnreachableGlobals)) |
| 2002 | GlobalsGraph->AuxFunctionCalls.push_back(DSCallSite(*CI, GGCloner)); |
Vikram S. Adve | 78bbec7 | 2003-07-16 21:36:31 +0000 | [diff] [blame] | 2003 | |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 2004 | AuxFunctionCalls.erase(CI++); |
| 2005 | } |
Chris Lattner | aa8146f | 2002-11-10 06:59:55 +0000 | [diff] [blame] | 2006 | |
Chris Lattner | c3f5f77 | 2004-02-08 01:51:48 +0000 | [diff] [blame] | 2007 | // We are finally done with the GGCloner so we can destroy it. |
| 2008 | GGCloner.destroy(); |
Vikram S. Adve | 78bbec7 | 2003-07-16 21:36:31 +0000 | [diff] [blame] | 2009 | |
Vikram S. Adve | 40c600e | 2003-07-22 12:08:58 +0000 | [diff] [blame] | 2010 | // At this point, any nodes which are visited, but not alive, are nodes |
| 2011 | // which can be removed. Loop over all nodes, eliminating completely |
| 2012 | // unreachable nodes. |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 2013 | // |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 2014 | std::vector<DSNode*> DeadNodes; |
| 2015 | DeadNodes.reserve(Nodes.size()); |
Chris Lattner | 51c06ab | 2004-02-25 23:08:00 +0000 | [diff] [blame] | 2016 | for (NodeListTy::iterator NI = Nodes.begin(), E = Nodes.end(); NI != E;) { |
| 2017 | DSNode *N = NI++; |
| 2018 | assert(!N->isForwarding() && "Forwarded node in nodes list?"); |
| 2019 | |
| 2020 | if (!Alive.count(N)) { |
| 2021 | Nodes.remove(N); |
| 2022 | assert(!N->isForwarding() && "Cannot remove a forwarding node!"); |
Vikram S. Adve | 78bbec7 | 2003-07-16 21:36:31 +0000 | [diff] [blame] | 2023 | DeadNodes.push_back(N); |
| 2024 | N->dropAllReferences(); |
Chris Lattner | 51c06ab | 2004-02-25 23:08:00 +0000 | [diff] [blame] | 2025 | ++NumDNE; |
Chris Lattner | e221976 | 2002-07-18 18:22:40 +0000 | [diff] [blame] | 2026 | } |
Chris Lattner | 51c06ab | 2004-02-25 23:08:00 +0000 | [diff] [blame] | 2027 | } |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 2028 | |
Vikram S. Adve | 78bbec7 | 2003-07-16 21:36:31 +0000 | [diff] [blame] | 2029 | // Remove all unreachable globals from the ScalarMap. |
| 2030 | // If flag RemoveUnreachableGlobals is set, GlobalNodes has only dead nodes. |
| 2031 | // In either case, the dead nodes will not be in the set Alive. |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 2032 | for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i) |
Vikram S. Adve | 78bbec7 | 2003-07-16 21:36:31 +0000 | [diff] [blame] | 2033 | if (!Alive.count(GlobalNodes[i].second)) |
| 2034 | ScalarMap.erase(GlobalNodes[i].first); |
Chris Lattner | 0b14487 | 2004-01-27 22:03:40 +0000 | [diff] [blame] | 2035 | else |
| 2036 | assert((Flags & DSGraph::RemoveUnreachableGlobals) && "non-dead global"); |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 2037 | |
Vikram S. Adve | 78bbec7 | 2003-07-16 21:36:31 +0000 | [diff] [blame] | 2038 | // Delete all dead nodes now since their referrer counts are zero. |
Chris Lattner | 72d29a4 | 2003-02-11 23:11:51 +0000 | [diff] [blame] | 2039 | for (unsigned i = 0, e = DeadNodes.size(); i != e; ++i) |
| 2040 | delete DeadNodes[i]; |
| 2041 | |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 2042 | DEBUG(AssertGraphOK(); GlobalsGraph->AssertGraphOK()); |
Chris Lattner | e221976 | 2002-07-18 18:22:40 +0000 | [diff] [blame] | 2043 | } |
| 2044 | |
Chris Lattner | b29dd0f | 2004-12-08 21:03:56 +0000 | [diff] [blame] | 2045 | void DSGraph::AssertNodeContainsGlobal(const DSNode *N, GlobalValue *GV) const { |
Chris Lattner | 82c6c72 | 2005-03-20 02:41:38 +0000 | [diff] [blame] | 2046 | assert(std::find(N->globals_begin(),N->globals_end(), GV) != |
| 2047 | N->globals_end() && "Global value not in node!"); |
Chris Lattner | b29dd0f | 2004-12-08 21:03:56 +0000 | [diff] [blame] | 2048 | } |
| 2049 | |
Chris Lattner | 2c7725a | 2004-03-03 20:55:27 +0000 | [diff] [blame] | 2050 | void DSGraph::AssertCallSiteInGraph(const DSCallSite &CS) const { |
| 2051 | if (CS.isIndirectCall()) { |
| 2052 | AssertNodeInGraph(CS.getCalleeNode()); |
| 2053 | #if 0 |
| 2054 | if (CS.getNumPtrArgs() && CS.getCalleeNode() == CS.getPtrArg(0).getNode() && |
| 2055 | CS.getCalleeNode() && CS.getCalleeNode()->getGlobals().empty()) |
Chris Lattner | f8db8a0 | 2005-02-27 06:15:51 +0000 | [diff] [blame] | 2056 | std::cerr << "WARNING: WEIRD CALL SITE FOUND!\n"; |
Chris Lattner | 2c7725a | 2004-03-03 20:55:27 +0000 | [diff] [blame] | 2057 | #endif |
| 2058 | } |
| 2059 | AssertNodeInGraph(CS.getRetVal().getNode()); |
| 2060 | for (unsigned j = 0, e = CS.getNumPtrArgs(); j != e; ++j) |
| 2061 | AssertNodeInGraph(CS.getPtrArg(j).getNode()); |
| 2062 | } |
| 2063 | |
| 2064 | void DSGraph::AssertCallNodesInGraph() const { |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 2065 | for (fc_iterator I = fc_begin(), E = fc_end(); I != E; ++I) |
| 2066 | AssertCallSiteInGraph(*I); |
Chris Lattner | 2c7725a | 2004-03-03 20:55:27 +0000 | [diff] [blame] | 2067 | } |
| 2068 | void DSGraph::AssertAuxCallNodesInGraph() const { |
Chris Lattner | a9548d9 | 2005-01-30 23:51:02 +0000 | [diff] [blame] | 2069 | for (afc_iterator I = afc_begin(), E = afc_end(); I != E; ++I) |
| 2070 | AssertCallSiteInGraph(*I); |
Chris Lattner | 2c7725a | 2004-03-03 20:55:27 +0000 | [diff] [blame] | 2071 | } |
| 2072 | |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 2073 | void DSGraph::AssertGraphOK() const { |
Chris Lattner | 84b80a2 | 2005-03-16 22:42:19 +0000 | [diff] [blame] | 2074 | for (node_const_iterator NI = node_begin(), E = node_end(); NI != E; ++NI) |
| 2075 | NI->assertOK(); |
Chris Lattner | 85cfe01 | 2003-07-03 02:03:53 +0000 | [diff] [blame] | 2076 | |
Chris Lattner | 8d32767 | 2003-06-30 03:36:09 +0000 | [diff] [blame] | 2077 | for (ScalarMapTy::const_iterator I = ScalarMap.begin(), |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 2078 | E = ScalarMap.end(); I != E; ++I) { |
Chris Lattner | 6f96774 | 2004-10-30 04:05:01 +0000 | [diff] [blame] | 2079 | assert(!I->second.isNull() && "Null node in scalarmap!"); |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 2080 | AssertNodeInGraph(I->second.getNode()); |
| 2081 | if (GlobalValue *GV = dyn_cast<GlobalValue>(I->first)) { |
Chris Lattner | bd92b73 | 2003-06-19 21:15:11 +0000 | [diff] [blame] | 2082 | assert(I->second.getNode()->isGlobalNode() && |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 2083 | "Global points to node, but node isn't global?"); |
| 2084 | AssertNodeContainsGlobal(I->second.getNode(), GV); |
| 2085 | } |
| 2086 | } |
| 2087 | AssertCallNodesInGraph(); |
| 2088 | AssertAuxCallNodesInGraph(); |
Chris Lattner | 7d8d471 | 2004-10-31 17:45:40 +0000 | [diff] [blame] | 2089 | |
| 2090 | // Check that all pointer arguments to any functions in this graph have |
| 2091 | // destinations. |
| 2092 | for (ReturnNodesTy::const_iterator RI = ReturnNodes.begin(), |
| 2093 | E = ReturnNodes.end(); |
| 2094 | RI != E; ++RI) { |
| 2095 | Function &F = *RI->first; |
Chris Lattner | e4d5c44 | 2005-03-15 04:54:21 +0000 | [diff] [blame] | 2096 | for (Function::arg_iterator AI = F.arg_begin(); AI != F.arg_end(); ++AI) |
Chris Lattner | 7d8d471 | 2004-10-31 17:45:40 +0000 | [diff] [blame] | 2097 | if (isPointerType(AI->getType())) |
| 2098 | assert(!getNodeForValue(AI).isNull() && |
| 2099 | "Pointer argument must be in the scalar map!"); |
| 2100 | } |
Chris Lattner | 0ac7d5c | 2003-02-03 19:12:15 +0000 | [diff] [blame] | 2101 | } |
Vikram S. Adve | 78bbec7 | 2003-07-16 21:36:31 +0000 | [diff] [blame] | 2102 | |
Chris Lattner | 400433d | 2003-11-11 05:08:59 +0000 | [diff] [blame] | 2103 | /// computeNodeMapping - Given roots in two different DSGraphs, traverse the |
Chris Lattner | e84c23e | 2004-10-31 19:57:43 +0000 | [diff] [blame] | 2104 | /// nodes reachable from the two graphs, computing the mapping of nodes from the |
| 2105 | /// first to the second graph. This mapping may be many-to-one (i.e. the first |
| 2106 | /// graph may have multiple nodes representing one node in the second graph), |
| 2107 | /// but it will not work if there is a one-to-many or many-to-many mapping. |
Chris Lattner | 400433d | 2003-11-11 05:08:59 +0000 | [diff] [blame] | 2108 | /// |
| 2109 | void DSGraph::computeNodeMapping(const DSNodeHandle &NH1, |
Chris Lattner | afc1dba | 2003-11-12 17:58:22 +0000 | [diff] [blame] | 2110 | const DSNodeHandle &NH2, NodeMapTy &NodeMap, |
| 2111 | bool StrictChecking) { |
Chris Lattner | 400433d | 2003-11-11 05:08:59 +0000 | [diff] [blame] | 2112 | DSNode *N1 = NH1.getNode(), *N2 = NH2.getNode(); |
| 2113 | if (N1 == 0 || N2 == 0) return; |
| 2114 | |
| 2115 | DSNodeHandle &Entry = NodeMap[N1]; |
Chris Lattner | 6f96774 | 2004-10-30 04:05:01 +0000 | [diff] [blame] | 2116 | if (!Entry.isNull()) { |
Chris Lattner | 400433d | 2003-11-11 05:08:59 +0000 | [diff] [blame] | 2117 | // Termination of recursion! |
Chris Lattner | cc7c4ac | 2004-03-13 01:14:23 +0000 | [diff] [blame] | 2118 | if (StrictChecking) { |
| 2119 | assert(Entry.getNode() == N2 && "Inconsistent mapping detected!"); |
| 2120 | assert((Entry.getOffset() == (NH2.getOffset()-NH1.getOffset()) || |
| 2121 | Entry.getNode()->isNodeCompletelyFolded()) && |
| 2122 | "Inconsistent mapping detected!"); |
| 2123 | } |
Chris Lattner | 400433d | 2003-11-11 05:08:59 +0000 | [diff] [blame] | 2124 | return; |
| 2125 | } |
| 2126 | |
Chris Lattner | efffdc9 | 2004-07-07 06:12:52 +0000 | [diff] [blame] | 2127 | Entry.setTo(N2, NH2.getOffset()-NH1.getOffset()); |
Chris Lattner | 400433d | 2003-11-11 05:08:59 +0000 | [diff] [blame] | 2128 | |
| 2129 | // Loop over all of the fields that N1 and N2 have in common, recursively |
| 2130 | // mapping the edges together now. |
| 2131 | int N2Idx = NH2.getOffset()-NH1.getOffset(); |
| 2132 | unsigned N2Size = N2->getSize(); |
Chris Lattner | 841957e | 2005-03-15 04:40:24 +0000 | [diff] [blame] | 2133 | if (N2Size == 0) return; // No edges to map to. |
| 2134 | |
Chris Lattner | 4d5af8e | 2005-03-15 21:36:50 +0000 | [diff] [blame] | 2135 | for (unsigned i = 0, e = N1->getSize(); i < e; i += DS::PointerSize) { |
| 2136 | const DSNodeHandle &N1NH = N1->getLink(i); |
| 2137 | // Don't call N2->getLink if not needed (avoiding crash if N2Idx is not |
| 2138 | // aligned right). |
| 2139 | if (!N1NH.isNull()) { |
| 2140 | if (unsigned(N2Idx)+i < N2Size) |
| 2141 | computeNodeMapping(N1NH, N2->getLink(N2Idx+i), NodeMap); |
| 2142 | else |
| 2143 | computeNodeMapping(N1NH, |
| 2144 | N2->getLink(unsigned(N2Idx+i) % N2Size), NodeMap); |
| 2145 | } |
| 2146 | } |
Chris Lattner | 400433d | 2003-11-11 05:08:59 +0000 | [diff] [blame] | 2147 | } |
Chris Lattner | b2b17bb | 2005-03-14 19:22:47 +0000 | [diff] [blame] | 2148 | |
| 2149 | |
Chris Lattner | b0f92e3 | 2005-03-15 00:58:16 +0000 | [diff] [blame] | 2150 | /// computeGToGGMapping - Compute the mapping of nodes in the global graph to |
Chris Lattner | 36a13cd | 2005-03-15 17:52:18 +0000 | [diff] [blame] | 2151 | /// nodes in this graph. |
Chris Lattner | b0f92e3 | 2005-03-15 00:58:16 +0000 | [diff] [blame] | 2152 | void DSGraph::computeGToGGMapping(NodeMapTy &NodeMap) { |
Chris Lattner | b2b17bb | 2005-03-14 19:22:47 +0000 | [diff] [blame] | 2153 | DSGraph &GG = *getGlobalsGraph(); |
| 2154 | |
| 2155 | DSScalarMap &SM = getScalarMap(); |
| 2156 | for (DSScalarMap::global_iterator I = SM.global_begin(), |
| 2157 | E = SM.global_end(); I != E; ++I) |
| 2158 | DSGraph::computeNodeMapping(SM[*I], GG.getNodeForValue(*I), NodeMap); |
| 2159 | } |
| 2160 | |
Chris Lattner | b0f92e3 | 2005-03-15 00:58:16 +0000 | [diff] [blame] | 2161 | /// computeGGToGMapping - Compute the mapping of nodes in the global graph to |
Chris Lattner | 36a13cd | 2005-03-15 17:52:18 +0000 | [diff] [blame] | 2162 | /// nodes in this graph. Note that any uses of this method are probably bugs, |
| 2163 | /// unless it is known that the globals graph has been merged into this graph! |
| 2164 | void DSGraph::computeGGToGMapping(InvNodeMapTy &InvNodeMap) { |
| 2165 | NodeMapTy NodeMap; |
| 2166 | computeGToGGMapping(NodeMap); |
Chris Lattner | b0f92e3 | 2005-03-15 00:58:16 +0000 | [diff] [blame] | 2167 | |
Chris Lattner | 36a13cd | 2005-03-15 17:52:18 +0000 | [diff] [blame] | 2168 | while (!NodeMap.empty()) { |
| 2169 | InvNodeMap.insert(std::make_pair(NodeMap.begin()->second, |
| 2170 | NodeMap.begin()->first)); |
| 2171 | NodeMap.erase(NodeMap.begin()); |
| 2172 | } |
Chris Lattner | b0f92e3 | 2005-03-15 00:58:16 +0000 | [diff] [blame] | 2173 | } |
| 2174 | |
Chris Lattner | 4ffe5d8 | 2005-03-17 23:45:54 +0000 | [diff] [blame] | 2175 | |
| 2176 | /// computeCalleeCallerMapping - Given a call from a function in the current |
| 2177 | /// graph to the 'Callee' function (which lives in 'CalleeGraph'), compute the |
| 2178 | /// mapping of nodes from the callee to nodes in the caller. |
| 2179 | void DSGraph::computeCalleeCallerMapping(DSCallSite CS, const Function &Callee, |
| 2180 | DSGraph &CalleeGraph, |
| 2181 | NodeMapTy &NodeMap) { |
| 2182 | |
| 2183 | DSCallSite CalleeArgs = |
| 2184 | CalleeGraph.getCallSiteForArguments(const_cast<Function&>(Callee)); |
| 2185 | |
| 2186 | computeNodeMapping(CalleeArgs.getRetVal(), CS.getRetVal(), NodeMap); |
| 2187 | |
| 2188 | unsigned NumArgs = CS.getNumPtrArgs(); |
| 2189 | if (NumArgs > CalleeArgs.getNumPtrArgs()) |
| 2190 | NumArgs = CalleeArgs.getNumPtrArgs(); |
| 2191 | |
| 2192 | for (unsigned i = 0; i != NumArgs; ++i) |
| 2193 | computeNodeMapping(CalleeArgs.getPtrArg(i), CS.getPtrArg(i), NodeMap); |
| 2194 | |
| 2195 | // Map the nodes that are pointed to by globals. |
| 2196 | DSScalarMap &CalleeSM = CalleeGraph.getScalarMap(); |
| 2197 | DSScalarMap &CallerSM = getScalarMap(); |
| 2198 | |
| 2199 | if (CalleeSM.global_size() >= CallerSM.global_size()) { |
| 2200 | for (DSScalarMap::global_iterator GI = CallerSM.global_begin(), |
| 2201 | E = CallerSM.global_end(); GI != E; ++GI) |
| 2202 | if (CalleeSM.global_count(*GI)) |
| 2203 | computeNodeMapping(CalleeSM[*GI], CallerSM[*GI], NodeMap); |
| 2204 | } else { |
| 2205 | for (DSScalarMap::global_iterator GI = CalleeSM.global_begin(), |
| 2206 | E = CalleeSM.global_end(); GI != E; ++GI) |
| 2207 | if (CallerSM.global_count(*GI)) |
| 2208 | computeNodeMapping(CalleeSM[*GI], CallerSM[*GI], NodeMap); |
| 2209 | } |
| 2210 | } |