← Back to branch summary

~ubuntu-branches/ubuntu/wily/clamav/wily-proposed

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/include/llvm/Analysis/RegionInfo.h

  • Committer: Package Import Robot
  • Author(s): Scott Kitterman, Sebastian Andrzej Siewior, Andreas Cadhalpun, Scott Kitterman, Javier Fernández-Sanguino
  • Date: 2015-01-28 00:25:13 UTC
  • mfrom: (0.48.14 sid)
  • Revision ID: package-import@ubuntu.com-20150128002513-lil2oi74cooy4lzr
Tags: 0.98.6+dfsg-1
http://bugs.debian.org/774686
http://bugs.debian.org/767350
http://bugs.debian.org/775400
http://bugs.debian.org/767353
http://bugs.debian.org/773563
[ Sebastian Andrzej Siewior ]
* update "fix-ssize_t-size_t-off_t-printf-modifier", include of misc.h was
  missing but was pulled in via the systemd patch.
* Don't leak return codes from libmspack to clamav API. (Closes: #774686).

[ Andreas Cadhalpun ]
* Add patch to avoid emitting incremental progress messages when not
  outputting to a terminal. (Closes: #767350)
* Update lintian-overrides for unused-file-paragraph-in-dep5-copyright.
* clamav-base.postinst: always chown /var/log/clamav and /var/lib/clamav
  to clamav:clamav, not only on fresh installations. (Closes: #775400)
* Adapt the clamav-daemon and clamav-freshclam logrotate scripts,
  so that they correctly work under systemd.
* Move the PidFile variable from the clamd/freshclam configuration files
  to the init scripts. This makes the init scripts more robust against
  misconfiguration and avoids error messages with systemd. (Closes: #767353)
* debian/copyright: drop files from Files-Excluded only present in github
  tarballs
* Drop Workaround-a-bug-in-libc-on-Hurd.patch, because hurd got fixed.
  (see #752237)
* debian/rules: Remove useless --with-system-tommath --without-included-ltdl
  configure options.

[ Scott Kitterman ]
* Stop stripping llvm when repacking the tarball as the system llvm on some
  releases is too old to use
* New upstream bugfix release
  - Library shared object revisions.
  - Includes a patch from Sebastian Andrzej Siewior making ClamAV pid files
    compatible with systemd.
  - Fix a heap out of bounds condition with crafted Yoda's crypter files.
    This issue was discovered by Felix Groebert of the Google Security Team.
  - Fix a heap out of bounds condition with crafted mew packer files. This
    issue was discovered by Felix Groebert of the Google Security Team.
  - Fix a heap out of bounds condition with crafted upx packer files. This
    issue was discovered by Kevin Szkudlapski of Quarkslab.
  - Fix a heap out of bounds condition with crafted upack packer files. This
    issue was discovered by Sebastian Andrzej Siewior. CVE-2014-9328.
  - Compensate a crash due to incorrect compiler optimization when handling
    crafted petite packer files. This issue was discovered by Sebastian
    Andrzej Siewior.
* Update lintian override for embedded zlib to match new so version

[ Javier Fernández-Sanguino ]
* Updated Spanish Debconf template translation (Closes: #773563)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/include/llvm/Analysis/RegionInfo.h
 
1
//===- RegionInfo.h - SESE region analysis ----------------------*- C++ -*-===//
 
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
// Calculate a program structure tree built out of single entry single exit
 
11
// regions.
 
12
// The basic ideas are taken from "The Program Structure Tree - Richard Johnson,
 
13
// David Pearson, Keshav Pingali - 1994", however enriched with ideas from "The
 
14
// Refined Process Structure Tree - Jussi Vanhatalo, Hagen Voelyer, Jana
 
15
// Koehler - 2009".
 
16
// The algorithm to calculate these data structures however is completely
 
17
// different, as it takes advantage of existing information already available
 
18
// in (Post)dominace tree and dominance frontier passes. This leads to a simpler
 
19
// and in practice hopefully better performing algorithm. The runtime of the
 
20
// algorithms described in the papers above are both linear in graph size,
 
21
// O(V+E), whereas this algorithm is not, as the dominance frontier information
 
22
// itself is not, but in practice runtime seems to be in the order of magnitude
 
23
// of dominance tree calculation.
 
24
//
 
25
//===----------------------------------------------------------------------===//
 
26
 
 
27
#ifndef LLVM_ANALYSIS_REGION_INFO_H
 
28
#define LLVM_ANALYSIS_REGION_INFO_H
 
29
 
 
30
#include "llvm/ADT/PointerIntPair.h"
 
31
#include "llvm/Analysis/Dominators.h"
 
32
#include "llvm/Analysis/PostDominators.h"
 
33
#include "llvm/Support/Allocator.h"
 
34
 
 
35
namespace llvm {
 
36
 
 
37
class Region;
 
38
class RegionInfo;
 
39
class raw_ostream;
 
40
class Loop;
 
41
class LoopInfo;
 
42
 
 
43
/// @brief Marker class to iterate over the elements of a Region in flat mode.
 
44
///
 
45
/// The class is used to either iterate in Flat mode or by not using it to not
 
46
/// iterate in Flat mode.  During a Flat mode iteration all Regions are entered
 
47
/// and the iteration returns every BasicBlock.  If the Flat mode is not
 
48
/// selected for SubRegions just one RegionNode containing the subregion is
 
49
/// returned.
 
50
template <class GraphType>
 
51
class FlatIt {};
 
52
 
 
53
/// @brief A RegionNode represents a subregion or a BasicBlock that is part of a
 
54
/// Region.
 
55
class RegionNode {
 
56
  // DO NOT IMPLEMENT
 
57
  RegionNode(const RegionNode &);
 
58
  // DO NOT IMPLEMENT
 
59
  const RegionNode &operator=(const RegionNode &);
 
60
 
 
61
  /// This is the entry basic block that starts this region node.  If this is a
 
62
  /// BasicBlock RegionNode, then entry is just the basic block, that this
 
63
  /// RegionNode represents.  Otherwise it is the entry of this (Sub)RegionNode.
 
64
  ///
 
65
  /// In the BBtoRegionNode map of the parent of this node, BB will always map
 
66
  /// to this node no matter which kind of node this one is.
 
67
  ///
 
68
  /// The node can hold either a Region or a BasicBlock.
 
69
  /// Use one bit to save, if this RegionNode is a subregion or BasicBlock
 
70
  /// RegionNode.
 
71
  PointerIntPair<BasicBlock*, 1, bool> entry;
 
72
 
 
73
protected:
 
74
  /// @brief The parent Region of this RegionNode.
 
75
  /// @see getParent()
 
76
  Region* parent;
 
77
 
 
78
public:
 
79
  /// @brief Create a RegionNode.
 
80
  ///
 
81
  /// @param Parent      The parent of this RegionNode.
 
82
  /// @param Entry       The entry BasicBlock of the RegionNode.  If this
 
83
  ///                    RegionNode represents a BasicBlock, this is the
 
84
  ///                    BasicBlock itself.  If it represents a subregion, this
 
85
  ///                    is the entry BasicBlock of the subregion.
 
86
  /// @param isSubRegion If this RegionNode represents a SubRegion.
 
87
  inline RegionNode(Region* Parent, BasicBlock* Entry, bool isSubRegion = 0)
 
88
    : entry(Entry, isSubRegion), parent(Parent) {}
 
89
 
 
90
  /// @brief Get the parent Region of this RegionNode.
 
91
  ///
 
92
  /// The parent Region is the Region this RegionNode belongs to. If for
 
93
  /// example a BasicBlock is element of two Regions, there exist two
 
94
  /// RegionNodes for this BasicBlock. Each with the getParent() function
 
95
  /// pointing to the Region this RegionNode belongs to.
 
96
  ///
 
97
  /// @return Get the parent Region of this RegionNode.
 
98
  inline Region* getParent() const { return parent; }
 
99
 
 
100
  /// @brief Get the entry BasicBlock of this RegionNode.
 
101
  ///
 
102
  /// If this RegionNode represents a BasicBlock this is just the BasicBlock
 
103
  /// itself, otherwise we return the entry BasicBlock of the Subregion
 
104
  ///
 
105
  /// @return The entry BasicBlock of this RegionNode.
 
106
  inline BasicBlock* getEntry() const { return entry.getPointer(); }
 
107
 
 
108
  /// @brief Get the content of this RegionNode.
 
109
  ///
 
110
  /// This can be either a BasicBlock or a subregion. Before calling getNodeAs()
 
111
  /// check the type of the content with the isSubRegion() function call.
 
112
  ///
 
113
  /// @return The content of this RegionNode.
 
114
  template<class T>
 
115
  inline T* getNodeAs() const;
 
116
 
 
117
  /// @brief Is this RegionNode a subregion?
 
118
  ///
 
119
  /// @return True if it contains a subregion. False if it contains a
 
120
  ///         BasicBlock.
 
121
  inline bool isSubRegion() const {
 
122
    return entry.getInt();
 
123
  }
 
124
};
 
125
 
 
126
/// Print a RegionNode.
 
127
inline raw_ostream &operator<<(raw_ostream &OS, const RegionNode &Node);
 
128
 
 
129
template<>
 
130
inline BasicBlock* RegionNode::getNodeAs<BasicBlock>() const {
 
131
  assert(!isSubRegion() && "This is not a BasicBlock RegionNode!");
 
132
  return getEntry();
 
133
}
 
134
 
 
135
template<>
 
136
inline Region* RegionNode::getNodeAs<Region>() const {
 
137
  assert(isSubRegion() && "This is not a subregion RegionNode!");
 
138
  return reinterpret_cast<Region*>(const_cast<RegionNode*>(this));
 
139
}
 
140
 
 
141
//===----------------------------------------------------------------------===//
 
142
/// @brief A single entry single exit Region.
 
143
///
 
144
/// A Region is a connected subgraph of a control flow graph that has exactly
 
145
/// two connections to the remaining graph. It can be used to analyze or
 
146
/// optimize parts of the control flow graph.
 
147
///
 
148
/// A <em> simple Region </em> is connected to the remaing graph by just two
 
149
/// edges. One edge entering the Region and another one leaving the Region.
 
150
///
 
151
/// An <em> extended Region </em> (or just Region) is a subgraph that can be
 
152
/// transform into a simple Region. The transformation is done by adding
 
153
/// BasicBlocks that merge several entry or exit edges so that after the merge
 
154
/// just one entry and one exit edge exists.
 
155
///
 
156
/// The \e Entry of a Region is the first BasicBlock that is passed after
 
157
/// entering the Region. It is an element of the Region. The entry BasicBlock
 
158
/// dominates all BasicBlocks in the Region.
 
159
///
 
160
/// The \e Exit of a Region is the first BasicBlock that is passed after
 
161
/// leaving the Region. It is not an element of the Region. The exit BasicBlock,
 
162
/// postdominates all BasicBlocks in the Region.
 
163
///
 
164
/// A <em> canonical Region </em> cannot be constructed by combining smaller
 
165
/// Regions.
 
166
///
 
167
/// Region A is the \e parent of Region B, if B is completely contained in A.
 
168
///
 
169
/// Two canonical Regions either do not intersect at all or one is
 
170
/// the parent of the other.
 
171
///
 
172
/// The <em> Program Structure Tree</em> is a graph (V, E) where V is the set of
 
173
/// Regions in the control flow graph and E is the \e parent relation of these
 
174
/// Regions.
 
175
///
 
176
/// Example:
 
177
///
 
178
/// \verbatim
 
179
/// A simple control flow graph, that contains two regions.
 
180
///
 
181
///        1
 
182
///       / |
 
183
///      2   |
 
184
///     / \   3
 
185
///    4   5  |
 
186
///    |   |  |
 
187
///    6   7  8
 
188
///     \  | /
 
189
///      \ |/       Region A: 1 -> 9 {1,2,3,4,5,6,7,8}
 
190
///        9        Region B: 2 -> 9 {2,4,5,6,7}
 
191
/// \endverbatim
 
192
///
 
193
/// You can obtain more examples by either calling
 
194
///
 
195
/// <tt> "opt -regions -analyze anyprogram.ll" </tt>
 
196
/// or
 
197
/// <tt> "opt -view-regions-only anyprogram.ll" </tt>
 
198
///
 
199
/// on any LLVM file you are interested in.
 
200
///
 
201
/// The first call returns a textual representation of the program structure
 
202
/// tree, the second one creates a graphical representation using graphviz.
 
203
class Region : public RegionNode {
 
204
  friend class RegionInfo;
 
205
  // DO NOT IMPLEMENT
 
206
  Region(const Region &);
 
207
  // DO NOT IMPLEMENT
 
208
  const Region &operator=(const Region &);
 
209
 
 
210
  // Information necessary to manage this Region.
 
211
  RegionInfo* RI;
 
212
  DominatorTree *DT;
 
213
 
 
214
  // The exit BasicBlock of this region.
 
215
  // (The entry BasicBlock is part of RegionNode)
 
216
  BasicBlock *exit;
 
217
 
 
218
  typedef std::vector<Region*> RegionSet;
 
219
 
 
220
  // The subregions of this region.
 
221
  RegionSet children;
 
222
 
 
223
  typedef std::map<BasicBlock*, RegionNode*> BBNodeMapT;
 
224
 
 
225
  // Save the BasicBlock RegionNodes that are element of this Region.
 
226
  mutable BBNodeMapT BBNodeMap;
 
227
 
 
228
  /// verifyBBInRegion - Check if a BB is in this Region. This check also works
 
229
  /// if the region is incorrectly built. (EXPENSIVE!)
 
230
  void verifyBBInRegion(BasicBlock* BB) const;
 
231
 
 
232
  /// verifyWalk - Walk over all the BBs of the region starting from BB and
 
233
  /// verify that all reachable basic blocks are elements of the region.
 
234
  /// (EXPENSIVE!)
 
235
  void verifyWalk(BasicBlock* BB, std::set<BasicBlock*>* visitedBB) const;
 
236
 
 
237
  /// verifyRegionNest - Verify if the region and its children are valid
 
238
  /// regions (EXPENSIVE!)
 
239
  void verifyRegionNest() const;
 
240
 
 
241
public:
 
242
  /// @brief Create a new region.
 
243
  ///
 
244
  /// @param Entry  The entry basic block of the region.
 
245
  /// @param Exit   The exit basic block of the region.
 
246
  /// @param RI     The region info object that is managing this region.
 
247
  /// @param DT     The dominator tree of the current function.
 
248
  /// @param Parent The surrounding region or NULL if this is a top level
 
249
  ///               region.
 
250
  Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo* RI,
 
251
         DominatorTree *DT, Region *Parent = 0);
 
252
 
 
253
  /// Delete the Region and all its subregions.
 
254
  ~Region();
 
255
 
 
256
  /// @brief Get the entry BasicBlock of the Region.
 
257
  /// @return The entry BasicBlock of the region.
 
258
  BasicBlock *getEntry() const { return RegionNode::getEntry(); }
 
259
 
 
260
  /// @brief Get the exit BasicBlock of the Region.
 
261
  /// @return The exit BasicBlock of the Region, NULL if this is the TopLevel
 
262
  ///         Region.
 
263
  BasicBlock *getExit() const { return exit; }
 
264
 
 
265
  /// @brief Get the parent of the Region.
 
266
  /// @return The parent of the Region or NULL if this is a top level
 
267
  ///         Region.
 
268
  Region *getParent() const { return RegionNode::getParent(); }
 
269
 
 
270
  /// @brief Get the RegionNode representing the current Region.
 
271
  /// @return The RegionNode representing the current Region.
 
272
  RegionNode* getNode() const {
 
273
    return const_cast<RegionNode*>(reinterpret_cast<const RegionNode*>(this));
 
274
  }
 
275
 
 
276
  /// @brief Get the nesting level of this Region.
 
277
  ///
 
278
  /// An toplevel Region has depth 0.
 
279
  ///
 
280
  /// @return The depth of the region.
 
281
  unsigned getDepth() const;
 
282
 
 
283
  /// @brief Is this a simple region?
 
284
  ///
 
285
  /// A region is simple if it has exactly one exit and one entry edge.
 
286
  ///
 
287
  /// @return True if the Region is simple.
 
288
  bool isSimple() const;
 
289
 
 
290
  /// @brief Returns the name of the Region.
 
291
  /// @return The Name of the Region.
 
292
  std::string getNameStr() const;
 
293
 
 
294
  /// @brief Return the RegionInfo object, that belongs to this Region.
 
295
  RegionInfo *getRegionInfo() const {
 
296
    return RI;
 
297
  }
 
298
 
 
299
  /// @brief Print the region.
 
300
  ///
 
301
  /// @param OS The output stream the Region is printed to.
 
302
  /// @param printTree Print also the tree of subregions.
 
303
  /// @param level The indentation level used for printing.
 
304
  void print(raw_ostream& OS, bool printTree = true, unsigned level = 0) const;
 
305
 
 
306
  /// @brief Print the region to stderr.
 
307
  void dump() const;
 
308
 
 
309
  /// @brief Check if the region contains a BasicBlock.
 
310
  ///
 
311
  /// @param BB The BasicBlock that might be contained in this Region.
 
312
  /// @return True if the block is contained in the region otherwise false.
 
313
  bool contains(const BasicBlock *BB) const;
 
314
 
 
315
  /// @brief Check if the region contains another region.
 
316
  ///
 
317
  /// @param SubRegion The region that might be contained in this Region.
 
318
  /// @return True if SubRegion is contained in the region otherwise false.
 
319
  bool contains(const Region *SubRegion) const {
 
320
    // Toplevel Region.
 
321
    if (!getExit())
 
322
      return true;
 
323
 
 
324
    return contains(SubRegion->getEntry())
 
325
      && (contains(SubRegion->getExit()) || SubRegion->getExit() == getExit());
 
326
  }
 
327
 
 
328
  /// @brief Check if the region contains an Instruction.
 
329
  ///
 
330
  /// @param Inst The Instruction that might be contained in this region.
 
331
  /// @return True if the Instruction is contained in the region otherwise false.
 
332
  bool contains(const Instruction *Inst) const {
 
333
    return contains(Inst->getParent());
 
334
  }
 
335
 
 
336
  /// @brief Check if the region contains a loop.
 
337
  ///
 
338
  /// @param L The loop that might be contained in this region.
 
339
  /// @return True if the loop is contained in the region otherwise false.
 
340
  ///         In case a NULL pointer is passed to this function the result
 
341
  ///         is false, except for the region that describes the whole function.
 
342
  ///         In that case true is returned.
 
343
  bool contains(const Loop *L) const;
 
344
 
 
345
  /// @brief Get the outermost loop in the region that contains a loop.
 
346
  ///
 
347
  /// Find for a Loop L the outermost loop OuterL that is a parent loop of L
 
348
  /// and is itself contained in the region.
 
349
  ///
 
350
  /// @param L The loop the lookup is started.
 
351
  /// @return The outermost loop in the region, NULL if such a loop does not
 
352
  ///         exist or if the region describes the whole function.
 
353
  Loop *outermostLoopInRegion(Loop *L) const;
 
354
 
 
355
  /// @brief Get the outermost loop in the region that contains a basic block.
 
356
  ///
 
357
  /// Find for a basic block BB the outermost loop L that contains BB and is
 
358
  /// itself contained in the region.
 
359
  ///
 
360
  /// @param LI A pointer to a LoopInfo analysis.
 
361
  /// @param BB The basic block surrounded by the loop.
 
362
  /// @return The outermost loop in the region, NULL if such a loop does not
 
363
  ///         exist or if the region describes the whole function.
 
364
  Loop *outermostLoopInRegion(LoopInfo *LI, BasicBlock* BB) const;
 
365
 
 
366
  /// @brief Get the subregion that starts at a BasicBlock
 
367
  ///
 
368
  /// @param BB The BasicBlock the subregion should start.
 
369
  /// @return The Subregion if available, otherwise NULL.
 
370
  Region* getSubRegionNode(BasicBlock *BB) const;
 
371
 
 
372
  /// @brief Get the RegionNode for a BasicBlock
 
373
  ///
 
374
  /// @param BB The BasicBlock at which the RegionNode should start.
 
375
  /// @return If available, the RegionNode that represents the subregion
 
376
  ///         starting at BB. If no subregion starts at BB, the RegionNode
 
377
  ///         representing BB.
 
378
  RegionNode* getNode(BasicBlock *BB) const;
 
379
 
 
380
  /// @brief Get the BasicBlock RegionNode for a BasicBlock
 
381
  ///
 
382
  /// @param BB The BasicBlock for which the RegionNode is requested.
 
383
  /// @return The RegionNode representing the BB.
 
384
  RegionNode* getBBNode(BasicBlock *BB) const;
 
385
 
 
386
  /// @brief Add a new subregion to this Region.
 
387
  ///
 
388
  /// @param SubRegion The new subregion that will be added.
 
389
  void addSubRegion(Region *SubRegion);
 
390
 
 
391
  /// @brief Remove a subregion from this Region.
 
392
  ///
 
393
  /// The subregion is not deleted, as it will probably be inserted into another
 
394
  /// region.
 
395
  /// @param SubRegion The SubRegion that will be removed.
 
396
  Region *removeSubRegion(Region *SubRegion);
 
397
 
 
398
  /// @brief Move all direct child nodes of this Region to another Region.
 
399
  ///
 
400
  /// @param To The Region the child nodes will be transfered to.
 
401
  void transferChildrenTo(Region *To);
 
402
 
 
403
  /// @brief Verify if the region is a correct region.
 
404
  ///
 
405
  /// Check if this is a correctly build Region. This is an expensive check, as
 
406
  /// the complete CFG of the Region will be walked.
 
407
  void verifyRegion() const;
 
408
 
 
409
  /// @brief Clear the cache for BB RegionNodes.
 
410
  ///
 
411
  /// After calling this function the BasicBlock RegionNodes will be stored at
 
412
  /// different memory locations. RegionNodes obtained before this function is
 
413
  /// called are therefore not comparable to RegionNodes abtained afterwords.
 
414
  void clearNodeCache();
 
415
 
 
416
  /// @name Subregion Iterators
 
417
  ///
 
418
  /// These iterators iterator over all subregions of this Region.
 
419
  //@{
 
420
  typedef RegionSet::iterator iterator;
 
421
  typedef RegionSet::const_iterator const_iterator;
 
422
 
 
423
  iterator begin() { return children.begin(); }
 
424
  iterator end() { return children.end(); }
 
425
 
 
426
  const_iterator begin() const { return children.begin(); }
 
427
  const_iterator end() const { return children.end(); }
 
428
  //@}
 
429
 
 
430
  /// @name BasicBlock Iterators
 
431
  ///
 
432
  /// These iterators iterate over all BasicBlock RegionNodes that are
 
433
  /// contained in this Region. The iterator also iterates over BasicBlocks
 
434
  /// that are elements of a subregion of this Region. It is therefore called a
 
435
  /// flat iterator.
 
436
  //@{
 
437
  typedef df_iterator<RegionNode*, SmallPtrSet<RegionNode*, 8>, false,
 
438
                      GraphTraits<FlatIt<RegionNode*> > > block_iterator;
 
439
 
 
440
  typedef df_iterator<const RegionNode*, SmallPtrSet<const RegionNode*, 8>,
 
441
                      false, GraphTraits<FlatIt<const RegionNode*> > >
 
442
            const_block_iterator;
 
443
 
 
444
  block_iterator block_begin();
 
445
  block_iterator block_end();
 
446
 
 
447
  const_block_iterator block_begin() const;
 
448
  const_block_iterator block_end() const;
 
449
  //@}
 
450
 
 
451
  /// @name Element Iterators
 
452
  ///
 
453
  /// These iterators iterate over all BasicBlock and subregion RegionNodes that
 
454
  /// are direct children of this Region. It does not iterate over any
 
455
  /// RegionNodes that are also element of a subregion of this Region.
 
456
  //@{
 
457
  typedef df_iterator<RegionNode*, SmallPtrSet<RegionNode*, 8>, false,
 
458
                      GraphTraits<RegionNode*> > element_iterator;
 
459
 
 
460
  typedef df_iterator<const RegionNode*, SmallPtrSet<const RegionNode*, 8>,
 
461
                      false, GraphTraits<const RegionNode*> >
 
462
            const_element_iterator;
 
463
 
 
464
  element_iterator element_begin();
 
465
  element_iterator element_end();
 
466
 
 
467
  const_element_iterator element_begin() const;
 
468
  const_element_iterator element_end() const;
 
469
  //@}
 
470
};
 
471
 
 
472
//===----------------------------------------------------------------------===//
 
473
/// @brief Analysis that detects all canonical Regions.
 
474
///
 
475
/// The RegionInfo pass detects all canonical regions in a function. The Regions
 
476
/// are connected using the parent relation. This builds a Program Structure
 
477
/// Tree.
 
478
class RegionInfo : public FunctionPass {
 
479
  typedef DenseMap<BasicBlock*,BasicBlock*> BBtoBBMap;
 
480
  typedef DenseMap<BasicBlock*, Region*> BBtoRegionMap;
 
481
  typedef SmallPtrSet<Region*, 4> RegionSet;
 
482
 
 
483
  // DO NOT IMPLEMENT
 
484
  RegionInfo(const RegionInfo &);
 
485
  // DO NOT IMPLEMENT
 
486
  const RegionInfo &operator=(const RegionInfo &);
 
487
 
 
488
  DominatorTree *DT;
 
489
  PostDominatorTree *PDT;
 
490
  DominanceFrontier *DF;
 
491
 
 
492
  /// The top level region.
 
493
  Region *TopLevelRegion;
 
494
 
 
495
  /// Map every BB to the smallest region, that contains BB.
 
496
  BBtoRegionMap BBtoRegion;
 
497
 
 
498
  // isCommonDomFrontier - Returns true if BB is in the dominance frontier of
 
499
  // entry, because it was inherited from exit. In the other case there is an
 
500
  // edge going from entry to BB without passing exit.
 
501
  bool isCommonDomFrontier(BasicBlock* BB, BasicBlock* entry,
 
502
                           BasicBlock* exit) const;
 
503
 
 
504
  // isRegion - Check if entry and exit surround a valid region, based on
 
505
  // dominance tree and dominance frontier.
 
506
  bool isRegion(BasicBlock* entry, BasicBlock* exit) const;
 
507
 
 
508
  // insertShortCut - Saves a shortcut pointing from entry to exit.
 
509
  // This function may extend this shortcut if possible.
 
510
  void insertShortCut(BasicBlock* entry, BasicBlock* exit,
 
511
                      BBtoBBMap* ShortCut) const;
 
512
 
 
513
  // getNextPostDom - Returns the next BB that postdominates N, while skipping
 
514
  // all post dominators that cannot finish a canonical region.
 
515
  DomTreeNode *getNextPostDom(DomTreeNode* N, BBtoBBMap *ShortCut) const;
 
516
 
 
517
  // isTrivialRegion - A region is trivial, if it contains only one BB.
 
518
  bool isTrivialRegion(BasicBlock *entry, BasicBlock *exit) const;
 
519
 
 
520
  // createRegion - Creates a single entry single exit region.
 
521
  Region *createRegion(BasicBlock *entry, BasicBlock *exit);
 
522
 
 
523
  // findRegionsWithEntry - Detect all regions starting with bb 'entry'.
 
524
  void findRegionsWithEntry(BasicBlock *entry, BBtoBBMap *ShortCut);
 
525
 
 
526
  // scanForRegions - Detects regions in F.
 
527
  void scanForRegions(Function &F, BBtoBBMap *ShortCut);
 
528
 
 
529
  // getTopMostParent - Get the top most parent with the same entry block.
 
530
  Region *getTopMostParent(Region *region);
 
531
 
 
532
  // buildRegionsTree - build the region hierarchy after all region detected.
 
533
  void buildRegionsTree(DomTreeNode *N, Region *region);
 
534
 
 
535
  // Calculate - detecte all regions in function and build the region tree.
 
536
  void Calculate(Function& F);
 
537
 
 
538
  void releaseMemory();
 
539
 
 
540
  // updateStatistics - Update statistic about created regions.
 
541
  void updateStatistics(Region *R);
 
542
 
 
543
  // isSimple - Check if a region is a simple region with exactly one entry
 
544
  // edge and exactly one exit edge.
 
545
  bool isSimple(Region* R) const;
 
546
 
 
547
public:
 
548
  static char ID;
 
549
  explicit RegionInfo();
 
550
 
 
551
  ~RegionInfo();
 
552
 
 
553
  /// @name FunctionPass interface
 
554
  //@{
 
555
  virtual bool runOnFunction(Function &F);
 
556
  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 
557
  virtual void print(raw_ostream &OS, const Module *) const;
 
558
  virtual void verifyAnalysis() const;
 
559
  //@}
 
560
 
 
561
  /// @brief Get the smallest region that contains a BasicBlock.
 
562
  ///
 
563
  /// @param BB The basic block.
 
564
  /// @return The smallest region, that contains BB or NULL, if there is no
 
565
  /// region containing BB.
 
566
  Region *getRegionFor(BasicBlock *BB) const;
 
567
 
 
568
  /// @brief A shortcut for getRegionFor().
 
569
  ///
 
570
  /// @param BB The basic block.
 
571
  /// @return The smallest region, that contains BB or NULL, if there is no
 
572
  /// region containing BB.
 
573
  Region *operator[](BasicBlock *BB) const;
 
574
 
 
575
  /// @brief Return the exit of the maximal refined region, that starts at a
 
576
  /// BasicBlock.
 
577
  ///
 
578
  /// @param BB The BasicBlock the refined region starts.
 
579
  BasicBlock *getMaxRegionExit(BasicBlock *BB) const;
 
580
 
 
581
  /// @brief Find the smallest region that contains two regions.
 
582
  ///
 
583
  /// @param A The first region.
 
584
  /// @param B The second region.
 
585
  /// @return The smallest region containing A and B.
 
586
  Region *getCommonRegion(Region* A, Region *B) const;
 
587
 
 
588
  /// @brief Find the smallest region that contains two basic blocks.
 
589
  ///
 
590
  /// @param A The first basic block.
 
591
  /// @param B The second basic block.
 
592
  /// @return The smallest region that contains A and B.
 
593
  Region* getCommonRegion(BasicBlock* A, BasicBlock *B) const {
 
594
    return getCommonRegion(getRegionFor(A), getRegionFor(B));
 
595
  }
 
596
 
 
597
  /// @brief Find the smallest region that contains a set of regions.
 
598
  ///
 
599
  /// @param Regions A vector of regions.
 
600
  /// @return The smallest region that contains all regions in Regions.
 
601
  Region* getCommonRegion(SmallVectorImpl<Region*> &Regions) const;
 
602
 
 
603
  /// @brief Find the smallest region that contains a set of basic blocks.
 
604
  ///
 
605
  /// @param BBs A vector of basic blocks.
 
606
  /// @return The smallest region that contains all basic blocks in BBS.
 
607
  Region* getCommonRegion(SmallVectorImpl<BasicBlock*> &BBs) const;
 
608
 
 
609
  Region *getTopLevelRegion() const {
 
610
    return TopLevelRegion;
 
611
  }
 
612
 
 
613
  /// @brief Clear the Node Cache for all Regions.
 
614
  ///
 
615
  /// @see Region::clearNodeCache()
 
616
  void clearNodeCache() {
 
617
    if (TopLevelRegion)
 
618
      TopLevelRegion->clearNodeCache();
 
619
  }
 
620
};
 
621
 
 
622
inline raw_ostream &operator<<(raw_ostream &OS, const RegionNode &Node) {
 
623
  if (Node.isSubRegion())
 
624
    return OS << Node.getNodeAs<Region>()->getNameStr();
 
625
  else
 
626
    return OS << Node.getNodeAs<BasicBlock>()->getNameStr();
 
627
}
 
628
} // End llvm namespace
 
629
#endif
 
630