Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 1 | //===- LexicalScopes.cpp - Collecting lexical scope info ------------------===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file implements LexicalScopes analysis. |
| 11 | // |
| 12 | // This pass collects lexical scope information and maps machine instructions |
| 13 | // to respective lexical scopes. |
| 14 | // |
| 15 | //===----------------------------------------------------------------------===// |
| 16 | |
Eugene Zelenko | 5db84df | 2017-02-17 21:43:25 +0000 | [diff] [blame] | 17 | #include "llvm/ADT/DenseMap.h" |
| 18 | #include "llvm/ADT/SmallVector.h" |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 19 | #include "llvm/CodeGen/LexicalScopes.h" |
Eugene Zelenko | 5db84df | 2017-02-17 21:43:25 +0000 | [diff] [blame] | 20 | #include "llvm/CodeGen/MachineBasicBlock.h" |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 21 | #include "llvm/CodeGen/MachineFunction.h" |
| 22 | #include "llvm/CodeGen/MachineInstr.h" |
Eugene Zelenko | 5db84df | 2017-02-17 21:43:25 +0000 | [diff] [blame] | 23 | #include "llvm/IR/DebugInfoMetadata.h" |
| 24 | #include "llvm/IR/Metadata.h" |
| 25 | #include "llvm/Support/Casting.h" |
| 26 | #include "llvm/Support/Compiler.h" |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 27 | #include "llvm/Support/Debug.h" |
Eugene Zelenko | 5db84df | 2017-02-17 21:43:25 +0000 | [diff] [blame] | 28 | #include "llvm/Support/raw_ostream.h" |
| 29 | #include <cassert> |
| 30 | #include <string> |
| 31 | #include <tuple> |
| 32 | #include <utility> |
| 33 | |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 34 | using namespace llvm; |
| 35 | |
Chandler Carruth | 1b9dde0 | 2014-04-22 02:02:50 +0000 | [diff] [blame] | 36 | #define DEBUG_TYPE "lexicalscopes" |
| 37 | |
Eric Christopher | b7dee8a | 2013-11-20 00:54:28 +0000 | [diff] [blame] | 38 | /// reset - Reset the instance so that it's prepared for another function. |
| 39 | void LexicalScopes::reset() { |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 40 | MF = nullptr; |
| 41 | CurrentFnLexicalScope = nullptr; |
David Blaikie | 2f143e0 | 2014-05-08 22:24:51 +0000 | [diff] [blame] | 42 | LexicalScopeMap.clear(); |
| 43 | AbstractScopeMap.clear(); |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 44 | InlinedLexicalScopeMap.clear(); |
| 45 | AbstractScopesList.clear(); |
| 46 | } |
| 47 | |
| 48 | /// initialize - Scan machine function and constuct lexical scope nest. |
| 49 | void LexicalScopes::initialize(const MachineFunction &Fn) { |
Teresa Johnson | 76b5b74 | 2017-02-17 00:21:19 +0000 | [diff] [blame] | 50 | // Don't attempt any lexical scope creation for a NoDebug compile unit. |
| 51 | if (Fn.getFunction()->getSubprogram()->getUnit()->getEmissionKind() == |
| 52 | DICompileUnit::NoDebug) |
| 53 | return; |
Eric Christopher | b7dee8a | 2013-11-20 00:54:28 +0000 | [diff] [blame] | 54 | reset(); |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 55 | MF = &Fn; |
| 56 | SmallVector<InsnRange, 4> MIRanges; |
| 57 | DenseMap<const MachineInstr *, LexicalScope *> MI2ScopeMap; |
| 58 | extractLexicalScopes(MIRanges, MI2ScopeMap); |
| 59 | if (CurrentFnLexicalScope) { |
| 60 | constructScopeNest(CurrentFnLexicalScope); |
| 61 | assignInstructionRanges(MIRanges, MI2ScopeMap); |
| 62 | } |
| 63 | } |
| 64 | |
| 65 | /// extractLexicalScopes - Extract instruction ranges for each lexical scopes |
| 66 | /// for the given machine function. |
Eric Christopher | 6211e4b | 2013-11-20 00:54:19 +0000 | [diff] [blame] | 67 | void LexicalScopes::extractLexicalScopes( |
| 68 | SmallVectorImpl<InsnRange> &MIRanges, |
| 69 | DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) { |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 70 | // Scan each instruction and create scopes. First build working set of scopes. |
Alexey Samsonov | 41b977d | 2014-04-30 18:29:51 +0000 | [diff] [blame] | 71 | for (const auto &MBB : *MF) { |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 72 | const MachineInstr *RangeBeginMI = nullptr; |
| 73 | const MachineInstr *PrevMI = nullptr; |
Duncan P. N. Exon Smith | a9308c4 | 2015-04-29 16:38:44 +0000 | [diff] [blame] | 74 | const DILocation *PrevDL = nullptr; |
Alexey Samsonov | f74bde6 | 2014-04-30 22:17:38 +0000 | [diff] [blame] | 75 | for (const auto &MInsn : MBB) { |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 76 | // Check if instruction has valid location information. |
Duncan P. N. Exon Smith | a9308c4 | 2015-04-29 16:38:44 +0000 | [diff] [blame] | 77 | const DILocation *MIDL = MInsn.getDebugLoc(); |
Duncan P. N. Exon Smith | 9dffcd0 | 2015-03-30 19:14:47 +0000 | [diff] [blame] | 78 | if (!MIDL) { |
Alexey Samsonov | f74bde6 | 2014-04-30 22:17:38 +0000 | [diff] [blame] | 79 | PrevMI = &MInsn; |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 80 | continue; |
| 81 | } |
| 82 | |
| 83 | // If scope has not changed then skip this instruction. |
| 84 | if (MIDL == PrevDL) { |
Alexey Samsonov | f74bde6 | 2014-04-30 22:17:38 +0000 | [diff] [blame] | 85 | PrevMI = &MInsn; |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 86 | continue; |
| 87 | } |
| 88 | |
Adrian Prantl | fb31da1 | 2017-05-22 20:47:09 +0000 | [diff] [blame^] | 89 | // Ignore DBG_VALUE and similar instruction that do not contribute to any |
| 90 | // instruction in the output. |
| 91 | if (MInsn.isMetaInstruction()) |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 92 | continue; |
| 93 | |
| 94 | if (RangeBeginMI) { |
| 95 | // If we have already seen a beginning of an instruction range and |
| 96 | // current instruction scope does not match scope of first instruction |
| 97 | // in this range then create a new instruction range. |
| 98 | InsnRange R(RangeBeginMI, PrevMI); |
| 99 | MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL); |
| 100 | MIRanges.push_back(R); |
| 101 | } |
| 102 | |
| 103 | // This is a beginning of a new instruction range. |
Alexey Samsonov | f74bde6 | 2014-04-30 22:17:38 +0000 | [diff] [blame] | 104 | RangeBeginMI = &MInsn; |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 105 | |
| 106 | // Reset previous markers. |
Alexey Samsonov | f74bde6 | 2014-04-30 22:17:38 +0000 | [diff] [blame] | 107 | PrevMI = &MInsn; |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 108 | PrevDL = MIDL; |
| 109 | } |
| 110 | |
| 111 | // Create last instruction range. |
Duncan P. N. Exon Smith | 9dffcd0 | 2015-03-30 19:14:47 +0000 | [diff] [blame] | 112 | if (RangeBeginMI && PrevMI && PrevDL) { |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 113 | InsnRange R(RangeBeginMI, PrevMI); |
| 114 | MIRanges.push_back(R); |
| 115 | MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL); |
| 116 | } |
| 117 | } |
| 118 | } |
| 119 | |
| 120 | /// findLexicalScope - Find lexical scope, either regular or inlined, for the |
| 121 | /// given DebugLoc. Return NULL if not found. |
Duncan P. N. Exon Smith | a9308c4 | 2015-04-29 16:38:44 +0000 | [diff] [blame] | 122 | LexicalScope *LexicalScopes::findLexicalScope(const DILocation *DL) { |
| 123 | DILocalScope *Scope = DL->getScope(); |
Eric Christopher | 6211e4b | 2013-11-20 00:54:19 +0000 | [diff] [blame] | 124 | if (!Scope) |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 125 | return nullptr; |
Eric Christopher | 6647b83 | 2011-10-11 22:59:11 +0000 | [diff] [blame] | 126 | |
| 127 | // The scope that we were created with could have an extra file - which |
| 128 | // isn't what we care about in this case. |
Amjad Aboud | a5ba991 | 2016-04-21 16:58:49 +0000 | [diff] [blame] | 129 | Scope = Scope->getNonLexicalBlockFileScope(); |
Eric Christopher | 6211e4b | 2013-11-20 00:54:19 +0000 | [diff] [blame] | 130 | |
Duncan P. N. Exon Smith | 5a227ff | 2015-03-30 21:54:46 +0000 | [diff] [blame] | 131 | if (auto *IA = DL->getInlinedAt()) { |
David Blaikie | 9b8c8cd | 2014-05-14 01:08:28 +0000 | [diff] [blame] | 132 | auto I = InlinedLexicalScopeMap.find(std::make_pair(Scope, IA)); |
| 133 | return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr; |
| 134 | } |
David Blaikie | 2f143e0 | 2014-05-08 22:24:51 +0000 | [diff] [blame] | 135 | return findLexicalScope(Scope); |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 136 | } |
| 137 | |
| 138 | /// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If |
| 139 | /// not available then create new lexical scope. |
Duncan P. N. Exon Smith | a9308c4 | 2015-04-29 16:38:44 +0000 | [diff] [blame] | 140 | LexicalScope *LexicalScopes::getOrCreateLexicalScope(const DILocalScope *Scope, |
| 141 | const DILocation *IA) { |
Duncan P. N. Exon Smith | 82eba74 | 2015-03-30 23:47:26 +0000 | [diff] [blame] | 142 | if (IA) { |
Teresa Johnson | 76b5b74 | 2017-02-17 00:21:19 +0000 | [diff] [blame] | 143 | // Skip scopes inlined from a NoDebug compile unit. |
| 144 | if (Scope->getSubprogram()->getUnit()->getEmissionKind() == |
| 145 | DICompileUnit::NoDebug) |
| 146 | return getOrCreateLexicalScope(IA); |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 147 | // Create an abstract scope for inlined function. |
| 148 | getOrCreateAbstractScope(Scope); |
| 149 | // Create an inlined scope for inlined function. |
Duncan P. N. Exon Smith | 82eba74 | 2015-03-30 23:47:26 +0000 | [diff] [blame] | 150 | return getOrCreateInlinedScope(Scope, IA); |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 151 | } |
Eric Christopher | 6211e4b | 2013-11-20 00:54:19 +0000 | [diff] [blame] | 152 | |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 153 | return getOrCreateRegularScope(Scope); |
| 154 | } |
| 155 | |
| 156 | /// getOrCreateRegularScope - Find or create a regular lexical scope. |
Duncan P. N. Exon Smith | 33af7a8 | 2015-03-30 23:21:21 +0000 | [diff] [blame] | 157 | LexicalScope * |
Duncan P. N. Exon Smith | a9308c4 | 2015-04-29 16:38:44 +0000 | [diff] [blame] | 158 | LexicalScopes::getOrCreateRegularScope(const DILocalScope *Scope) { |
Amjad Aboud | a5ba991 | 2016-04-21 16:58:49 +0000 | [diff] [blame] | 159 | assert(Scope && "Invalid Scope encoding!"); |
| 160 | Scope = Scope->getNonLexicalBlockFileScope(); |
Eric Christopher | 6211e4b | 2013-11-20 00:54:19 +0000 | [diff] [blame] | 161 | |
David Blaikie | 2f143e0 | 2014-05-08 22:24:51 +0000 | [diff] [blame] | 162 | auto I = LexicalScopeMap.find(Scope); |
| 163 | if (I != LexicalScopeMap.end()) |
| 164 | return &I->second; |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 165 | |
Duncan P. N. Exon Smith | a9308c4 | 2015-04-29 16:38:44 +0000 | [diff] [blame] | 166 | // FIXME: Should the following dyn_cast be DILexicalBlock? |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 167 | LexicalScope *Parent = nullptr; |
Duncan P. N. Exon Smith | a9308c4 | 2015-04-29 16:38:44 +0000 | [diff] [blame] | 168 | if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope)) |
Duncan P. N. Exon Smith | 82eba74 | 2015-03-30 23:47:26 +0000 | [diff] [blame] | 169 | Parent = getOrCreateLexicalScope(Block->getScope()); |
Aaron Ballman | f17583e | 2015-02-16 18:21:19 +0000 | [diff] [blame] | 170 | I = LexicalScopeMap.emplace(std::piecewise_construct, |
| 171 | std::forward_as_tuple(Scope), |
Duncan P. N. Exon Smith | 33af7a8 | 2015-03-30 23:21:21 +0000 | [diff] [blame] | 172 | std::forward_as_tuple(Parent, Scope, nullptr, |
| 173 | false)).first; |
David Blaikie | 2f143e0 | 2014-05-08 22:24:51 +0000 | [diff] [blame] | 174 | |
David Blaikie | 3dfe478 | 2014-10-14 18:22:52 +0000 | [diff] [blame] | 175 | if (!Parent) { |
Duncan P. N. Exon Smith | a9308c4 | 2015-04-29 16:38:44 +0000 | [diff] [blame] | 176 | assert(cast<DISubprogram>(Scope)->describes(MF->getFunction())); |
David Blaikie | 3dfe478 | 2014-10-14 18:22:52 +0000 | [diff] [blame] | 177 | assert(!CurrentFnLexicalScope); |
David Blaikie | 2f143e0 | 2014-05-08 22:24:51 +0000 | [diff] [blame] | 178 | CurrentFnLexicalScope = &I->second; |
David Blaikie | 3dfe478 | 2014-10-14 18:22:52 +0000 | [diff] [blame] | 179 | } |
Eric Christopher | 6211e4b | 2013-11-20 00:54:19 +0000 | [diff] [blame] | 180 | |
David Blaikie | 2f143e0 | 2014-05-08 22:24:51 +0000 | [diff] [blame] | 181 | return &I->second; |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 182 | } |
| 183 | |
| 184 | /// getOrCreateInlinedScope - Find or create an inlined lexical scope. |
Duncan P. N. Exon Smith | 33af7a8 | 2015-03-30 23:21:21 +0000 | [diff] [blame] | 185 | LexicalScope * |
Duncan P. N. Exon Smith | a9308c4 | 2015-04-29 16:38:44 +0000 | [diff] [blame] | 186 | LexicalScopes::getOrCreateInlinedScope(const DILocalScope *Scope, |
| 187 | const DILocation *InlinedAt) { |
Amjad Aboud | a5ba991 | 2016-04-21 16:58:49 +0000 | [diff] [blame] | 188 | assert(Scope && "Invalid Scope encoding!"); |
| 189 | Scope = Scope->getNonLexicalBlockFileScope(); |
Duncan P. N. Exon Smith | a9308c4 | 2015-04-29 16:38:44 +0000 | [diff] [blame] | 190 | std::pair<const DILocalScope *, const DILocation *> P(Scope, InlinedAt); |
David Blaikie | 9b8c8cd | 2014-05-14 01:08:28 +0000 | [diff] [blame] | 191 | auto I = InlinedLexicalScopeMap.find(P); |
| 192 | if (I != InlinedLexicalScopeMap.end()) |
David Blaikie | 2f143e0 | 2014-05-08 22:24:51 +0000 | [diff] [blame] | 193 | return &I->second; |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 194 | |
David Blaikie | 9b8c8cd | 2014-05-14 01:08:28 +0000 | [diff] [blame] | 195 | LexicalScope *Parent; |
Duncan P. N. Exon Smith | a9308c4 | 2015-04-29 16:38:44 +0000 | [diff] [blame] | 196 | if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope)) |
Duncan P. N. Exon Smith | 33af7a8 | 2015-03-30 23:21:21 +0000 | [diff] [blame] | 197 | Parent = getOrCreateInlinedScope(Block->getScope(), InlinedAt); |
David Blaikie | 9b8c8cd | 2014-05-14 01:08:28 +0000 | [diff] [blame] | 198 | else |
Duncan P. N. Exon Smith | 33af7a8 | 2015-03-30 23:21:21 +0000 | [diff] [blame] | 199 | Parent = getOrCreateLexicalScope(InlinedAt); |
David Blaikie | 9b8c8cd | 2014-05-14 01:08:28 +0000 | [diff] [blame] | 200 | |
Eric Christopher | 14303d1 | 2017-02-14 19:43:50 +0000 | [diff] [blame] | 201 | I = InlinedLexicalScopeMap |
| 202 | .emplace(std::piecewise_construct, std::forward_as_tuple(P), |
| 203 | std::forward_as_tuple(Parent, Scope, InlinedAt, false)) |
Aaron Ballman | f17583e | 2015-02-16 18:21:19 +0000 | [diff] [blame] | 204 | .first; |
David Blaikie | 2f143e0 | 2014-05-08 22:24:51 +0000 | [diff] [blame] | 205 | return &I->second; |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 206 | } |
| 207 | |
| 208 | /// getOrCreateAbstractScope - Find or create an abstract lexical scope. |
Duncan P. N. Exon Smith | 33af7a8 | 2015-03-30 23:21:21 +0000 | [diff] [blame] | 209 | LexicalScope * |
Duncan P. N. Exon Smith | a9308c4 | 2015-04-29 16:38:44 +0000 | [diff] [blame] | 210 | LexicalScopes::getOrCreateAbstractScope(const DILocalScope *Scope) { |
Duncan P. N. Exon Smith | 33af7a8 | 2015-03-30 23:21:21 +0000 | [diff] [blame] | 211 | assert(Scope && "Invalid Scope encoding!"); |
Amjad Aboud | a5ba991 | 2016-04-21 16:58:49 +0000 | [diff] [blame] | 212 | Scope = Scope->getNonLexicalBlockFileScope(); |
David Blaikie | ea86226 | 2014-05-25 18:11:35 +0000 | [diff] [blame] | 213 | auto I = AbstractScopeMap.find(Scope); |
David Blaikie | 2f143e0 | 2014-05-08 22:24:51 +0000 | [diff] [blame] | 214 | if (I != AbstractScopeMap.end()) |
| 215 | return &I->second; |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 216 | |
Duncan P. N. Exon Smith | a9308c4 | 2015-04-29 16:38:44 +0000 | [diff] [blame] | 217 | // FIXME: Should the following isa be DILexicalBlock? |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 218 | LexicalScope *Parent = nullptr; |
Duncan P. N. Exon Smith | a9308c4 | 2015-04-29 16:38:44 +0000 | [diff] [blame] | 219 | if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope)) |
Duncan P. N. Exon Smith | 33af7a8 | 2015-03-30 23:21:21 +0000 | [diff] [blame] | 220 | Parent = getOrCreateAbstractScope(Block->getScope()); |
| 221 | |
David Blaikie | 2f143e0 | 2014-05-08 22:24:51 +0000 | [diff] [blame] | 222 | I = AbstractScopeMap.emplace(std::piecewise_construct, |
David Blaikie | ea86226 | 2014-05-25 18:11:35 +0000 | [diff] [blame] | 223 | std::forward_as_tuple(Scope), |
| 224 | std::forward_as_tuple(Parent, Scope, |
David Blaikie | 2f143e0 | 2014-05-08 22:24:51 +0000 | [diff] [blame] | 225 | nullptr, true)).first; |
Duncan P. N. Exon Smith | a9308c4 | 2015-04-29 16:38:44 +0000 | [diff] [blame] | 226 | if (isa<DISubprogram>(Scope)) |
David Blaikie | 2f143e0 | 2014-05-08 22:24:51 +0000 | [diff] [blame] | 227 | AbstractScopesList.push_back(&I->second); |
| 228 | return &I->second; |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 229 | } |
| 230 | |
| 231 | /// constructScopeNest |
| 232 | void LexicalScopes::constructScopeNest(LexicalScope *Scope) { |
Eric Christopher | 6211e4b | 2013-11-20 00:54:19 +0000 | [diff] [blame] | 233 | assert(Scope && "Unable to calculate scope dominance graph!"); |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 234 | SmallVector<LexicalScope *, 4> WorkStack; |
| 235 | WorkStack.push_back(Scope); |
| 236 | unsigned Counter = 0; |
| 237 | while (!WorkStack.empty()) { |
| 238 | LexicalScope *WS = WorkStack.back(); |
Craig Topper | 80170e5 | 2013-07-03 04:30:58 +0000 | [diff] [blame] | 239 | const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren(); |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 240 | bool visitedChildren = false; |
Adrian Prantl | 16b2ace | 2016-09-28 17:31:17 +0000 | [diff] [blame] | 241 | for (auto &ChildScope : Children) |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 242 | if (!ChildScope->getDFSOut()) { |
| 243 | WorkStack.push_back(ChildScope); |
| 244 | visitedChildren = true; |
| 245 | ChildScope->setDFSIn(++Counter); |
| 246 | break; |
| 247 | } |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 248 | if (!visitedChildren) { |
| 249 | WorkStack.pop_back(); |
| 250 | WS->setDFSOut(++Counter); |
| 251 | } |
| 252 | } |
| 253 | } |
| 254 | |
Devang Patel | 784077e | 2011-08-10 23:58:09 +0000 | [diff] [blame] | 255 | /// assignInstructionRanges - Find ranges of instructions covered by each |
| 256 | /// lexical scope. |
Eric Christopher | 6211e4b | 2013-11-20 00:54:19 +0000 | [diff] [blame] | 257 | void LexicalScopes::assignInstructionRanges( |
| 258 | SmallVectorImpl<InsnRange> &MIRanges, |
| 259 | DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) { |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 260 | LexicalScope *PrevLexicalScope = nullptr; |
Adrian Prantl | 16b2ace | 2016-09-28 17:31:17 +0000 | [diff] [blame] | 261 | for (const auto &R : MIRanges) { |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 262 | LexicalScope *S = MI2ScopeMap.lookup(R.first); |
Eric Christopher | 6211e4b | 2013-11-20 00:54:19 +0000 | [diff] [blame] | 263 | assert(S && "Lost LexicalScope for a machine instruction!"); |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 264 | if (PrevLexicalScope && !PrevLexicalScope->dominates(S)) |
| 265 | PrevLexicalScope->closeInsnRange(S); |
| 266 | S->openInsnRange(R.first); |
| 267 | S->extendInsnRange(R.second); |
| 268 | PrevLexicalScope = S; |
| 269 | } |
| 270 | |
| 271 | if (PrevLexicalScope) |
| 272 | PrevLexicalScope->closeInsnRange(); |
| 273 | } |
| 274 | |
| 275 | /// getMachineBasicBlocks - Populate given set using machine basic blocks which |
Eric Christopher | 6211e4b | 2013-11-20 00:54:19 +0000 | [diff] [blame] | 276 | /// have machine instructions that belong to lexical scope identified by |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 277 | /// DebugLoc. |
Eric Christopher | 6211e4b | 2013-11-20 00:54:19 +0000 | [diff] [blame] | 278 | void LexicalScopes::getMachineBasicBlocks( |
Duncan P. N. Exon Smith | a9308c4 | 2015-04-29 16:38:44 +0000 | [diff] [blame] | 279 | const DILocation *DL, SmallPtrSetImpl<const MachineBasicBlock *> &MBBs) { |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 280 | MBBs.clear(); |
| 281 | LexicalScope *Scope = getOrCreateLexicalScope(DL); |
| 282 | if (!Scope) |
| 283 | return; |
Eric Christopher | 6211e4b | 2013-11-20 00:54:19 +0000 | [diff] [blame] | 284 | |
Devang Patel | db4374a | 2011-08-12 18:01:34 +0000 | [diff] [blame] | 285 | if (Scope == CurrentFnLexicalScope) { |
Alexey Samsonov | 41b977d | 2014-04-30 18:29:51 +0000 | [diff] [blame] | 286 | for (const auto &MBB : *MF) |
| 287 | MBBs.insert(&MBB); |
Devang Patel | db4374a | 2011-08-12 18:01:34 +0000 | [diff] [blame] | 288 | return; |
| 289 | } |
| 290 | |
Craig Topper | 80170e5 | 2013-07-03 04:30:58 +0000 | [diff] [blame] | 291 | SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges(); |
Adrian Prantl | 16b2ace | 2016-09-28 17:31:17 +0000 | [diff] [blame] | 292 | for (auto &R : InsnRanges) |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 293 | MBBs.insert(R.first->getParent()); |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 294 | } |
| 295 | |
| 296 | /// dominates - Return true if DebugLoc's lexical scope dominates at least one |
| 297 | /// machine instruction's lexical scope in a given machine basic block. |
Duncan P. N. Exon Smith | a9308c4 | 2015-04-29 16:38:44 +0000 | [diff] [blame] | 298 | bool LexicalScopes::dominates(const DILocation *DL, MachineBasicBlock *MBB) { |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 299 | LexicalScope *Scope = getOrCreateLexicalScope(DL); |
| 300 | if (!Scope) |
| 301 | return false; |
Devang Patel | db4374a | 2011-08-12 18:01:34 +0000 | [diff] [blame] | 302 | |
| 303 | // Current function scope covers all basic blocks in the function. |
| 304 | if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF) |
| 305 | return true; |
| 306 | |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 307 | bool Result = false; |
Adrian Prantl | 16b2ace | 2016-09-28 17:31:17 +0000 | [diff] [blame] | 308 | for (auto &I : *MBB) { |
| 309 | if (const DILocation *IDL = I.getDebugLoc()) |
Duncan P. N. Exon Smith | 3386e0e | 2015-03-30 23:58:59 +0000 | [diff] [blame] | 310 | if (LexicalScope *IScope = getOrCreateLexicalScope(IDL)) |
| 311 | if (Scope->dominates(IScope)) |
| 312 | return true; |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 313 | } |
| 314 | return Result; |
| 315 | } |
| 316 | |
Matthias Braun | 8c209aa | 2017-01-28 02:02:38 +0000 | [diff] [blame] | 317 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| 318 | LLVM_DUMP_METHOD void LexicalScope::dump(unsigned Indent) const { |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 319 | raw_ostream &err = dbgs(); |
Manman Ren | e498b25 | 2013-02-02 00:02:03 +0000 | [diff] [blame] | 320 | err.indent(Indent); |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 321 | err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n"; |
| 322 | const MDNode *N = Desc; |
Manman Ren | e498b25 | 2013-02-02 00:02:03 +0000 | [diff] [blame] | 323 | err.indent(Indent); |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 324 | N->dump(); |
| 325 | if (AbstractScope) |
Manman Ren | e498b25 | 2013-02-02 00:02:03 +0000 | [diff] [blame] | 326 | err << std::string(Indent, ' ') << "Abstract Scope\n"; |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 327 | |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 328 | if (!Children.empty()) |
Manman Ren | e498b25 | 2013-02-02 00:02:03 +0000 | [diff] [blame] | 329 | err << std::string(Indent + 2, ' ') << "Children ...\n"; |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 330 | for (unsigned i = 0, e = Children.size(); i != e; ++i) |
| 331 | if (Children[i] != this) |
Manman Ren | e498b25 | 2013-02-02 00:02:03 +0000 | [diff] [blame] | 332 | Children[i]->dump(Indent + 2); |
Devang Patel | e1649c3 | 2011-08-10 19:04:06 +0000 | [diff] [blame] | 333 | } |
Matthias Braun | 8c209aa | 2017-01-28 02:02:38 +0000 | [diff] [blame] | 334 | #endif |