Trace.h revision 3f25328fbff583894772e45bb088e995b371190f
16ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner//===- llvm/Analysis/Trace.h - Represent one trace of LLVM code -*- C++ -*-===// 26ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner// 36ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner// The LLVM Compiler Infrastructure 46ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner// 56ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner// This file was developed by the LLVM research group and is distributed under 66ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner// the University of Illinois Open Source 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 216ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner#include <iosfwd> 226ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner#include <vector> 233f25328fbff583894772e45bb088e995b371190fChris Lattner#include <cassert> 246ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner 256ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattnernamespace llvm { 266ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner class BasicBlock; 276ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner class Function; 286ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner class Module; 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 1043f25328fbff583894772e45bb088e995b371190fChris Lattner /// print - Write trace to output stream. 1053f25328fbff583894772e45bb088e995b371190fChris Lattner /// 1063f25328fbff583894772e45bb088e995b371190fChris Lattner void print (std::ostream &O) const; 1076ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner 1083f25328fbff583894772e45bb088e995b371190fChris Lattner /// dump - Debugger convenience method; writes trace to standard error 1093f25328fbff583894772e45bb088e995b371190fChris Lattner /// output stream. 1106ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner /// 1113f25328fbff583894772e45bb088e995b371190fChris Lattner void dump () const; 1126ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner}; 1136ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner 1146ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner} // end namespace llvm 1156ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner 1166ba8972919b79996e7b9d646ca005d81dbebd04aChris Lattner#endif // TRACE_H 117