Trace.h revision 255f89faee13dc491cb64fbeae3c763e7e2ea4e6
16ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner//===- llvm/Analysis/Trace.h - Represent one trace of LLVM code -*- C++ -*-===//
26ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner//
36ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner//                     The LLVM Compiler Infrastructure
46ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner//
57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source
67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details.
76ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner//
86ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner//===----------------------------------------------------------------------===//
96ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner//
106ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner// This class represents a single trace of LLVM basic blocks.  A trace is a
116ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner// single entry, multiple exit, region of code that is often hot.  Trace-based
126ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner// optimizations treat traces almost like they are a large, strange, basic
136ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner// block: because the trace path is assumed to be hot, optimizations for the
146ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner// fall-through path are made at the expense of the non-fall-through paths.
156ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner//
166ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner//===----------------------------------------------------------------------===//
176ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner
186ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner#ifndef LLVM_ANALYSIS_TRACE_H
196ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner#define LLVM_ANALYSIS_TRACE_H
206ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner
213f25328fbff583894772e45bb088e995b371190fChris Lattner#include <cassert>
22255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include <vector>
236ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner
249769ab22265b313171d201b5928688524a01bd87Misha Brukmannamespace llvm {
256ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  class BasicBlock;
266ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  class Function;
276ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  class Module;
28bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner  class raw_ostream;
296ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner
306ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattnerclass Trace {
316ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  typedef std::vector<BasicBlock *> BasicBlockListType;
326ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  BasicBlockListType BasicBlocks;
336ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner
346ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattnerpublic:
356ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  /// Trace ctor - Make a new trace from a vector of basic blocks,
366ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  /// residing in the function which is the parent of the first
376ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  /// basic block in the vector.
386ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  ///
393f25328fbff583894772e45bb088e995b371190fChris Lattner  Trace(const std::vector<BasicBlock *> &vBB) : BasicBlocks (vBB) {}
406ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner
416ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  /// getEntryBasicBlock - Return the entry basic block (first block)
426ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  /// of the trace.
436ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  ///
446ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  BasicBlock *getEntryBasicBlock () const { return BasicBlocks[0]; }
456ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner
463f25328fbff583894772e45bb088e995b371190fChris Lattner  /// operator[]/getBlock - Return basic block N in the trace.
473f25328fbff583894772e45bb088e995b371190fChris Lattner  ///
483f25328fbff583894772e45bb088e995b371190fChris Lattner  BasicBlock *operator[](unsigned i) const { return BasicBlocks[i]; }
493f25328fbff583894772e45bb088e995b371190fChris Lattner  BasicBlock *getBlock(unsigned i)   const { return BasicBlocks[i]; }
503f25328fbff583894772e45bb088e995b371190fChris Lattner
516ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  /// getFunction - Return this trace's parent function.
526ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  ///
536ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  Function *getFunction () const;
546ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner
556ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  /// getModule - Return this Module that contains this trace's parent
566ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  /// function.
576ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  ///
586ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  Module *getModule () const;
596ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner
603f25328fbff583894772e45bb088e995b371190fChris Lattner  /// getBlockIndex - Return the index of the specified basic block in the
613f25328fbff583894772e45bb088e995b371190fChris Lattner  /// trace, or -1 if it is not in the trace.
623f25328fbff583894772e45bb088e995b371190fChris Lattner  int getBlockIndex(const BasicBlock *X) const {
633f25328fbff583894772e45bb088e995b371190fChris Lattner    for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i)
643f25328fbff583894772e45bb088e995b371190fChris Lattner      if (BasicBlocks[i] == X)
653f25328fbff583894772e45bb088e995b371190fChris Lattner        return i;
663f25328fbff583894772e45bb088e995b371190fChris Lattner    return -1;
673f25328fbff583894772e45bb088e995b371190fChris Lattner  }
683f25328fbff583894772e45bb088e995b371190fChris Lattner
693f25328fbff583894772e45bb088e995b371190fChris Lattner  /// contains - Returns true if this trace contains the given basic
703f25328fbff583894772e45bb088e995b371190fChris Lattner  /// block.
716ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  ///
723f25328fbff583894772e45bb088e995b371190fChris Lattner  bool contains(const BasicBlock *X) const {
733f25328fbff583894772e45bb088e995b371190fChris Lattner    return getBlockIndex(X) != -1;
743f25328fbff583894772e45bb088e995b371190fChris Lattner  }
756ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner
763f25328fbff583894772e45bb088e995b371190fChris Lattner  /// Returns true if B1 occurs before B2 in the trace, or if it is the same
773f25328fbff583894772e45bb088e995b371190fChris Lattner  /// block as B2..  Both blocks must be in the trace.
786ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  ///
793f25328fbff583894772e45bb088e995b371190fChris Lattner  bool dominates(const BasicBlock *B1, const BasicBlock *B2) const {
803f25328fbff583894772e45bb088e995b371190fChris Lattner    int B1Idx = getBlockIndex(B1), B2Idx = getBlockIndex(B2);
813f25328fbff583894772e45bb088e995b371190fChris Lattner    assert(B1Idx != -1 && B2Idx != -1 && "Block is not in the trace!");
823f25328fbff583894772e45bb088e995b371190fChris Lattner    return B1Idx <= B2Idx;
833f25328fbff583894772e45bb088e995b371190fChris Lattner  }
846ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner
856ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  // BasicBlock iterators...
866ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  typedef BasicBlockListType::iterator iterator;
876ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  typedef BasicBlockListType::const_iterator const_iterator;
886ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
896ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  typedef std::reverse_iterator<iterator> reverse_iterator;
906ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner
916ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  iterator                begin()       { return BasicBlocks.begin(); }
926ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  const_iterator          begin() const { return BasicBlocks.begin(); }
936ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  iterator                end  ()       { return BasicBlocks.end();   }
946ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  const_iterator          end  () const { return BasicBlocks.end();   }
956ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner
966ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  reverse_iterator       rbegin()       { return BasicBlocks.rbegin(); }
976ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  const_reverse_iterator rbegin() const { return BasicBlocks.rbegin(); }
986ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  reverse_iterator       rend  ()       { return BasicBlocks.rend();   }
996ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  const_reverse_iterator rend  () const { return BasicBlocks.rend();   }
1006ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner
1016ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  unsigned                 size() const { return BasicBlocks.size(); }
1026ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  bool                    empty() const { return BasicBlocks.empty(); }
1036ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner
10471d3a87ec1cf788236f48527f2cf5e2ae65df492Brian Gaeke  iterator erase(iterator q)               { return BasicBlocks.erase (q); }
10571d3a87ec1cf788236f48527f2cf5e2ae65df492Brian Gaeke  iterator erase(iterator q1, iterator q2) { return BasicBlocks.erase (q1, q2); }
10671d3a87ec1cf788236f48527f2cf5e2ae65df492Brian Gaeke
1073f25328fbff583894772e45bb088e995b371190fChris Lattner  /// print - Write trace to output stream.
1083f25328fbff583894772e45bb088e995b371190fChris Lattner  ///
109bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner  void print(raw_ostream &O) const;
1106ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner
1113f25328fbff583894772e45bb088e995b371190fChris Lattner  /// dump - Debugger convenience method; writes trace to standard error
1123f25328fbff583894772e45bb088e995b371190fChris Lattner  /// output stream.
1136ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner  ///
114bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner  void dump() const;
1156ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner};
1166ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner
1176ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner} // end namespace llvm
1186ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner
1196ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner#endif // TRACE_H
120