LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

IntervalPartition.cpp

Go to the documentation of this file.
00001 //===- IntervalPartition.cpp - Interval Partition module code -------------===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file contains the definition of the IntervalPartition class, which
00011 // calculates and represent the interval partition of a function.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #include "llvm/Analysis/IntervalIterator.h"
00016 #include "llvm/ADT/STLExtras.h"
00017 #include <algorithm>
00018 
00019 namespace llvm {
00020 
00021 static RegisterAnalysis<IntervalPartition>
00022 X("intervals", "Interval Partition Construction", true);
00023 
00024 //===----------------------------------------------------------------------===//
00025 // IntervalPartition Implementation
00026 //===----------------------------------------------------------------------===//
00027 
00028 // destroy - Reset state back to before function was analyzed
00029 void IntervalPartition::destroy() {
00030   std::for_each(Intervals.begin(), Intervals.end(), deleter<Interval>);
00031   IntervalMap.clear();
00032   RootInterval = 0;
00033 }
00034 
00035 void IntervalPartition::print(std::ostream &O) const {
00036   std::copy(Intervals.begin(), Intervals.end(),
00037             std::ostream_iterator<const Interval *>(O, "\n"));
00038 }
00039 
00040 // addIntervalToPartition - Add an interval to the internal list of intervals,
00041 // and then add mappings from all of the basic blocks in the interval to the
00042 // interval itself (in the IntervalMap).
00043 //
00044 void IntervalPartition::addIntervalToPartition(Interval *I) {
00045   Intervals.push_back(I);
00046 
00047   // Add mappings for all of the basic blocks in I to the IntervalPartition
00048   for (Interval::node_iterator It = I->Nodes.begin(), End = I->Nodes.end();
00049        It != End; ++It)
00050     IntervalMap.insert(std::make_pair(*It, I));
00051 }
00052 
00053 // updatePredecessors - Interval generation only sets the successor fields of
00054 // the interval data structures.  After interval generation is complete,
00055 // run through all of the intervals and propagate successor info as
00056 // predecessor info.
00057 //
00058 void IntervalPartition::updatePredecessors(Interval *Int) {
00059   BasicBlock *Header = Int->getHeaderNode();
00060   for (Interval::succ_iterator I = Int->Successors.begin(), 
00061                          E = Int->Successors.end(); I != E; ++I)
00062     getBlockInterval(*I)->Predecessors.push_back(Header);
00063 }
00064 
00065 // IntervalPartition ctor - Build the first level interval partition for the
00066 // specified function...
00067 //
00068 bool IntervalPartition::runOnFunction(Function &F) {
00069   // Pass false to intervals_begin because we take ownership of it's memory
00070   function_interval_iterator I = intervals_begin(&F, false);
00071   assert(I != intervals_end(&F) && "No intervals in function!?!?!");
00072 
00073   addIntervalToPartition(RootInterval = *I);
00074 
00075   ++I;  // After the first one...
00076 
00077   // Add the rest of the intervals to the partition...
00078   for_each(I, intervals_end(&F),
00079      bind_obj(this, &IntervalPartition::addIntervalToPartition));
00080 
00081   // Now that we know all of the successor information, propagate this to the
00082   // predecessors for each block...
00083   for_each(Intervals.begin(), Intervals.end(), 
00084      bind_obj(this, &IntervalPartition::updatePredecessors));
00085   return false;
00086 }
00087 
00088 
00089 // IntervalPartition ctor - Build a reduced interval partition from an
00090 // existing interval graph.  This takes an additional boolean parameter to
00091 // distinguish it from a copy constructor.  Always pass in false for now.
00092 //
00093 IntervalPartition::IntervalPartition(IntervalPartition &IP, bool) {
00094   Interval *FunctionStart = IP.getRootInterval();
00095   assert(FunctionStart && "Cannot operate on empty IntervalPartitions!");
00096 
00097   // Pass false to intervals_begin because we take ownership of it's memory
00098   interval_part_interval_iterator I = intervals_begin(IP, false);
00099   assert(I != intervals_end(IP) && "No intervals in interval partition!?!?!");
00100 
00101   addIntervalToPartition(RootInterval = *I);
00102 
00103   ++I;  // After the first one...
00104 
00105   // Add the rest of the intervals to the partition...
00106   for_each(I, intervals_end(IP),
00107      bind_obj(this, &IntervalPartition::addIntervalToPartition));
00108 
00109   // Now that we know all of the successor information, propagate this to the
00110   // predecessors for each block...
00111   for_each(Intervals.begin(), Intervals.end(), 
00112      bind_obj(this, &IntervalPartition::updatePredecessors));
00113 }
00114 
00115 } // End llvm namespace