← Back to branch summary

~pali/+junk/llvm-toolchain-3.7

« back to all changes in this revision

Viewing changes to lib/CodeGen/LexicalScopes.cpp

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2015-07-15 17:51:08 UTC
  • Revision ID: package-import@ubuntu.com-20150715175108-l8mynwovkx4zx697
Tags: upstream-3.7~+rc2
Import upstream version 3.7~+rc2

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/CodeGen/LexicalScopes.cpp
 
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
 
 
17
#include "llvm/CodeGen/LexicalScopes.h"
 
18
#include "llvm/CodeGen/MachineFunction.h"
 
19
#include "llvm/CodeGen/MachineInstr.h"
 
20
#include "llvm/IR/DebugInfo.h"
 
21
#include "llvm/IR/Function.h"
 
22
#include "llvm/Support/Debug.h"
 
23
#include "llvm/Support/ErrorHandling.h"
 
24
#include "llvm/Support/FormattedStream.h"
 
25
using namespace llvm;
 
26
 
 
27
#define DEBUG_TYPE "lexicalscopes"
 
28
 
 
29
/// reset - Reset the instance so that it's prepared for another function.
 
30
void LexicalScopes::reset() {
 
31
  MF = nullptr;
 
32
  CurrentFnLexicalScope = nullptr;
 
33
  LexicalScopeMap.clear();
 
34
  AbstractScopeMap.clear();
 
35
  InlinedLexicalScopeMap.clear();
 
36
  AbstractScopesList.clear();
 
37
}
 
38
 
 
39
/// initialize - Scan machine function and constuct lexical scope nest.
 
40
void LexicalScopes::initialize(const MachineFunction &Fn) {
 
41
  reset();
 
42
  MF = &Fn;
 
43
  SmallVector<InsnRange, 4> MIRanges;
 
44
  DenseMap<const MachineInstr *, LexicalScope *> MI2ScopeMap;
 
45
  extractLexicalScopes(MIRanges, MI2ScopeMap);
 
46
  if (CurrentFnLexicalScope) {
 
47
    constructScopeNest(CurrentFnLexicalScope);
 
48
    assignInstructionRanges(MIRanges, MI2ScopeMap);
 
49
  }
 
50
}
 
51
 
 
52
/// extractLexicalScopes - Extract instruction ranges for each lexical scopes
 
53
/// for the given machine function.
 
54
void LexicalScopes::extractLexicalScopes(
 
55
    SmallVectorImpl<InsnRange> &MIRanges,
 
56
    DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {
 
57
 
 
58
  // Scan each instruction and create scopes. First build working set of scopes.
 
59
  for (const auto &MBB : *MF) {
 
60
    const MachineInstr *RangeBeginMI = nullptr;
 
61
    const MachineInstr *PrevMI = nullptr;
 
62
    const DILocation *PrevDL = nullptr;
 
63
    for (const auto &MInsn : MBB) {
 
64
      // Check if instruction has valid location information.
 
65
      const DILocation *MIDL = MInsn.getDebugLoc();
 
66
      if (!MIDL) {
 
67
        PrevMI = &MInsn;
 
68
        continue;
 
69
      }
 
70
 
 
71
      // If scope has not changed then skip this instruction.
 
72
      if (MIDL == PrevDL) {
 
73
        PrevMI = &MInsn;
 
74
        continue;
 
75
      }
 
76
 
 
77
      // Ignore DBG_VALUE. It does not contribute to any instruction in output.
 
78
      if (MInsn.isDebugValue())
 
79
        continue;
 
80
 
 
81
      if (RangeBeginMI) {
 
82
        // If we have already seen a beginning of an instruction range and
 
83
        // current instruction scope does not match scope of first instruction
 
84
        // in this range then create a new instruction range.
 
85
        InsnRange R(RangeBeginMI, PrevMI);
 
86
        MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
 
87
        MIRanges.push_back(R);
 
88
      }
 
89
 
 
90
      // This is a beginning of a new instruction range.
 
91
      RangeBeginMI = &MInsn;
 
92
 
 
93
      // Reset previous markers.
 
94
      PrevMI = &MInsn;
 
95
      PrevDL = MIDL;
 
96
    }
 
97
 
 
98
    // Create last instruction range.
 
99
    if (RangeBeginMI && PrevMI && PrevDL) {
 
100
      InsnRange R(RangeBeginMI, PrevMI);
 
101
      MIRanges.push_back(R);
 
102
      MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
 
103
    }
 
104
  }
 
105
}
 
106
 
 
107
/// findLexicalScope - Find lexical scope, either regular or inlined, for the
 
108
/// given DebugLoc. Return NULL if not found.
 
109
LexicalScope *LexicalScopes::findLexicalScope(const DILocation *DL) {
 
110
  DILocalScope *Scope = DL->getScope();
 
111
  if (!Scope)
 
112
    return nullptr;
 
113
 
 
114
  // The scope that we were created with could have an extra file - which
 
115
  // isn't what we care about in this case.
 
116
  if (auto *File = dyn_cast<DILexicalBlockFile>(Scope))
 
117
    Scope = File->getScope();
 
118
 
 
119
  if (auto *IA = DL->getInlinedAt()) {
 
120
    auto I = InlinedLexicalScopeMap.find(std::make_pair(Scope, IA));
 
121
    return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr;
 
122
  }
 
123
  return findLexicalScope(Scope);
 
124
}
 
125
 
 
126
/// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If
 
127
/// not available then create new lexical scope.
 
128
LexicalScope *LexicalScopes::getOrCreateLexicalScope(const DILocalScope *Scope,
 
129
                                                     const DILocation *IA) {
 
130
  if (IA) {
 
131
    // Create an abstract scope for inlined function.
 
132
    getOrCreateAbstractScope(Scope);
 
133
    // Create an inlined scope for inlined function.
 
134
    return getOrCreateInlinedScope(Scope, IA);
 
135
  }
 
136
 
 
137
  return getOrCreateRegularScope(Scope);
 
138
}
 
139
 
 
140
/// getOrCreateRegularScope - Find or create a regular lexical scope.
 
141
LexicalScope *
 
142
LexicalScopes::getOrCreateRegularScope(const DILocalScope *Scope) {
 
143
  if (auto *File = dyn_cast<DILexicalBlockFile>(Scope))
 
144
    Scope = File->getScope();
 
145
 
 
146
  auto I = LexicalScopeMap.find(Scope);
 
147
  if (I != LexicalScopeMap.end())
 
148
    return &I->second;
 
149
 
 
150
  // FIXME: Should the following dyn_cast be DILexicalBlock?
 
151
  LexicalScope *Parent = nullptr;
 
152
  if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
 
153
    Parent = getOrCreateLexicalScope(Block->getScope());
 
154
  I = LexicalScopeMap.emplace(std::piecewise_construct,
 
155
                              std::forward_as_tuple(Scope),
 
156
                              std::forward_as_tuple(Parent, Scope, nullptr,
 
157
                                                    false)).first;
 
158
 
 
159
  if (!Parent) {
 
160
    assert(cast<DISubprogram>(Scope)->describes(MF->getFunction()));
 
161
    assert(!CurrentFnLexicalScope);
 
162
    CurrentFnLexicalScope = &I->second;
 
163
  }
 
164
 
 
165
  return &I->second;
 
166
}
 
167
 
 
168
/// getOrCreateInlinedScope - Find or create an inlined lexical scope.
 
169
LexicalScope *
 
170
LexicalScopes::getOrCreateInlinedScope(const DILocalScope *Scope,
 
171
                                       const DILocation *InlinedAt) {
 
172
  std::pair<const DILocalScope *, const DILocation *> P(Scope, InlinedAt);
 
173
  auto I = InlinedLexicalScopeMap.find(P);
 
174
  if (I != InlinedLexicalScopeMap.end())
 
175
    return &I->second;
 
176
 
 
177
  LexicalScope *Parent;
 
178
  if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
 
179
    Parent = getOrCreateInlinedScope(Block->getScope(), InlinedAt);
 
180
  else
 
181
    Parent = getOrCreateLexicalScope(InlinedAt);
 
182
 
 
183
  I = InlinedLexicalScopeMap.emplace(std::piecewise_construct,
 
184
                                     std::forward_as_tuple(P),
 
185
                                     std::forward_as_tuple(Parent, Scope,
 
186
                                                           InlinedAt, false))
 
187
          .first;
 
188
  return &I->second;
 
189
}
 
190
 
 
191
/// getOrCreateAbstractScope - Find or create an abstract lexical scope.
 
192
LexicalScope *
 
193
LexicalScopes::getOrCreateAbstractScope(const DILocalScope *Scope) {
 
194
  assert(Scope && "Invalid Scope encoding!");
 
195
 
 
196
  if (auto *File = dyn_cast<DILexicalBlockFile>(Scope))
 
197
    Scope = File->getScope();
 
198
  auto I = AbstractScopeMap.find(Scope);
 
199
  if (I != AbstractScopeMap.end())
 
200
    return &I->second;
 
201
 
 
202
  // FIXME: Should the following isa be DILexicalBlock?
 
203
  LexicalScope *Parent = nullptr;
 
204
  if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
 
205
    Parent = getOrCreateAbstractScope(Block->getScope());
 
206
 
 
207
  I = AbstractScopeMap.emplace(std::piecewise_construct,
 
208
                               std::forward_as_tuple(Scope),
 
209
                               std::forward_as_tuple(Parent, Scope,
 
210
                                                     nullptr, true)).first;
 
211
  if (isa<DISubprogram>(Scope))
 
212
    AbstractScopesList.push_back(&I->second);
 
213
  return &I->second;
 
214
}
 
215
 
 
216
/// constructScopeNest
 
217
void LexicalScopes::constructScopeNest(LexicalScope *Scope) {
 
218
  assert(Scope && "Unable to calculate scope dominance graph!");
 
219
  SmallVector<LexicalScope *, 4> WorkStack;
 
220
  WorkStack.push_back(Scope);
 
221
  unsigned Counter = 0;
 
222
  while (!WorkStack.empty()) {
 
223
    LexicalScope *WS = WorkStack.back();
 
224
    const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
 
225
    bool visitedChildren = false;
 
226
    for (SmallVectorImpl<LexicalScope *>::const_iterator SI = Children.begin(),
 
227
                                                         SE = Children.end();
 
228
         SI != SE; ++SI) {
 
229
      LexicalScope *ChildScope = *SI;
 
230
      if (!ChildScope->getDFSOut()) {
 
231
        WorkStack.push_back(ChildScope);
 
232
        visitedChildren = true;
 
233
        ChildScope->setDFSIn(++Counter);
 
234
        break;
 
235
      }
 
236
    }
 
237
    if (!visitedChildren) {
 
238
      WorkStack.pop_back();
 
239
      WS->setDFSOut(++Counter);
 
240
    }
 
241
  }
 
242
}
 
243
 
 
244
/// assignInstructionRanges - Find ranges of instructions covered by each
 
245
/// lexical scope.
 
246
void LexicalScopes::assignInstructionRanges(
 
247
    SmallVectorImpl<InsnRange> &MIRanges,
 
248
    DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {
 
249
 
 
250
  LexicalScope *PrevLexicalScope = nullptr;
 
251
  for (SmallVectorImpl<InsnRange>::const_iterator RI = MIRanges.begin(),
 
252
                                                  RE = MIRanges.end();
 
253
       RI != RE; ++RI) {
 
254
    const InsnRange &R = *RI;
 
255
    LexicalScope *S = MI2ScopeMap.lookup(R.first);
 
256
    assert(S && "Lost LexicalScope for a machine instruction!");
 
257
    if (PrevLexicalScope && !PrevLexicalScope->dominates(S))
 
258
      PrevLexicalScope->closeInsnRange(S);
 
259
    S->openInsnRange(R.first);
 
260
    S->extendInsnRange(R.second);
 
261
    PrevLexicalScope = S;
 
262
  }
 
263
 
 
264
  if (PrevLexicalScope)
 
265
    PrevLexicalScope->closeInsnRange();
 
266
}
 
267
 
 
268
/// getMachineBasicBlocks - Populate given set using machine basic blocks which
 
269
/// have machine instructions that belong to lexical scope identified by
 
270
/// DebugLoc.
 
271
void LexicalScopes::getMachineBasicBlocks(
 
272
    const DILocation *DL, SmallPtrSetImpl<const MachineBasicBlock *> &MBBs) {
 
273
  MBBs.clear();
 
274
  LexicalScope *Scope = getOrCreateLexicalScope(DL);
 
275
  if (!Scope)
 
276
    return;
 
277
 
 
278
  if (Scope == CurrentFnLexicalScope) {
 
279
    for (const auto &MBB : *MF)
 
280
      MBBs.insert(&MBB);
 
281
    return;
 
282
  }
 
283
 
 
284
  SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges();
 
285
  for (SmallVectorImpl<InsnRange>::iterator I = InsnRanges.begin(),
 
286
                                            E = InsnRanges.end();
 
287
       I != E; ++I) {
 
288
    InsnRange &R = *I;
 
289
    MBBs.insert(R.first->getParent());
 
290
  }
 
291
}
 
292
 
 
293
/// dominates - Return true if DebugLoc's lexical scope dominates at least one
 
294
/// machine instruction's lexical scope in a given machine basic block.
 
295
bool LexicalScopes::dominates(const DILocation *DL, MachineBasicBlock *MBB) {
 
296
  LexicalScope *Scope = getOrCreateLexicalScope(DL);
 
297
  if (!Scope)
 
298
    return false;
 
299
 
 
300
  // Current function scope covers all basic blocks in the function.
 
301
  if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF)
 
302
    return true;
 
303
 
 
304
  bool Result = false;
 
305
  for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
 
306
       ++I) {
 
307
    if (const DILocation *IDL = I->getDebugLoc())
 
308
      if (LexicalScope *IScope = getOrCreateLexicalScope(IDL))
 
309
        if (Scope->dominates(IScope))
 
310
          return true;
 
311
  }
 
312
  return Result;
 
313
}
 
314
 
 
315
/// dump - Print data structures.
 
316
void LexicalScope::dump(unsigned Indent) const {
 
317
#ifndef NDEBUG
 
318
  raw_ostream &err = dbgs();
 
319
  err.indent(Indent);
 
320
  err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n";
 
321
  const MDNode *N = Desc;
 
322
  err.indent(Indent);
 
323
  N->dump();
 
324
  if (AbstractScope)
 
325
    err << std::string(Indent, ' ') << "Abstract Scope\n";
 
326
 
 
327
  if (!Children.empty())
 
328
    err << std::string(Indent + 2, ' ') << "Children ...\n";
 
329
  for (unsigned i = 0, e = Children.size(); i != e; ++i)
 
330
    if (Children[i] != this)
 
331
      Children[i]->dump(Indent + 2);
 
332
#endif
 
333
}