Line data    Source code

       1             : //===- IntervalPartition.cpp - Interval Partition module code -------------===//
       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 contains the definition of the IntervalPartition class, which
      11             : // calculates and represent the interval partition of a function.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #include "llvm/Analysis/IntervalPartition.h"
      16             : #include "llvm/Analysis/Interval.h"
      17             : #include "llvm/Analysis/IntervalIterator.h"
      18             : #include "llvm/Pass.h"
      19             : #include <cassert>
      20             : #include <utility>
      21             : 
      22             : using namespace llvm;
      23             : 
      24             : char IntervalPartition::ID = 0;
      25             : 
      26       21512 : INITIALIZE_PASS(IntervalPartition, "intervals",
      27             :                 "Interval Partition Construction", true, true)
      28             : 
      29             : //===----------------------------------------------------------------------===//
      30             : // IntervalPartition Implementation
      31             : //===----------------------------------------------------------------------===//
      32             : 
      33             : // releaseMemory - Reset state back to before function was analyzed
      34           0 : void IntervalPartition::releaseMemory() {
      35           0 :   for (unsigned i = 0, e = Intervals.size(); i != e; ++i)
      36           0 :     delete Intervals[i];
      37             :   IntervalMap.clear();
      38             :   Intervals.clear();
      39           0 :   RootInterval = nullptr;
      40           0 : }
      41             : 
      42           0 : void IntervalPartition::print(raw_ostream &O, const Module*) const {
      43           0 :   for(unsigned i = 0, e = Intervals.size(); i != e; ++i)
      44           0 :     Intervals[i]->print(O);
      45           0 : }
      46             : 
      47             : // addIntervalToPartition - Add an interval to the internal list of intervals,
      48             : // and then add mappings from all of the basic blocks in the interval to the
      49             : // interval itself (in the IntervalMap).
      50           0 : void IntervalPartition::addIntervalToPartition(Interval *I) {
      51           0 :   Intervals.push_back(I);
      52             : 
      53             :   // Add mappings for all of the basic blocks in I to the IntervalPartition
      54           0 :   for (Interval::node_iterator It = I->Nodes.begin(), End = I->Nodes.end();
      55           0 :        It != End; ++It)
      56           0 :     IntervalMap.insert(std::make_pair(*It, I));
      57           0 : }
      58             : 
      59             : // updatePredecessors - Interval generation only sets the successor fields of
      60             : // the interval data structures.  After interval generation is complete,
      61             : // run through all of the intervals and propagate successor info as
      62             : // predecessor info.
      63           0 : void IntervalPartition::updatePredecessors(Interval *Int) {
      64           0 :   BasicBlock *Header = Int->getHeaderNode();
      65           0 :   for (BasicBlock *Successor : Int->Successors)
      66           0 :     getBlockInterval(Successor)->Predecessors.push_back(Header);
      67           0 : }
      68             : 
      69             : // IntervalPartition ctor - Build the first level interval partition for the
      70             : // specified function...
      71           0 : bool IntervalPartition::runOnFunction(Function &F) {
      72             :   // Pass false to intervals_begin because we take ownership of it's memory
      73           0 :   function_interval_iterator I = intervals_begin(&F, false);
      74             :   assert(I != intervals_end(&F) && "No intervals in function!?!?!");
      75             : 
      76           0 :   addIntervalToPartition(RootInterval = *I);
      77             : 
      78           0 :   ++I;  // After the first one...
      79             : 
      80             :   // Add the rest of the intervals to the partition.
      81           0 :   for (function_interval_iterator E = intervals_end(&F); I != E; ++I)
      82           0 :     addIntervalToPartition(*I);
      83             : 
      84             :   // Now that we know all of the successor information, propagate this to the
      85             :   // predecessors for each block.
      86           0 :   for (unsigned i = 0, e = Intervals.size(); i != e; ++i)
      87           0 :     updatePredecessors(Intervals[i]);
      88           0 :   return false;
      89             : }
      90             : 
      91             : // IntervalPartition ctor - Build a reduced interval partition from an
      92             : // existing interval graph.  This takes an additional boolean parameter to
      93             : // distinguish it from a copy constructor.  Always pass in false for now.
      94           0 : IntervalPartition::IntervalPartition(IntervalPartition &IP, bool)
      95           0 :   : FunctionPass(ID) {
      96             :   assert(IP.getRootInterval() && "Cannot operate on empty IntervalPartitions!");
      97             : 
      98             :   // Pass false to intervals_begin because we take ownership of it's memory
      99           0 :   interval_part_interval_iterator I = intervals_begin(IP, false);
     100             :   assert(I != intervals_end(IP) && "No intervals in interval partition!?!?!");
     101             : 
     102           0 :   addIntervalToPartition(RootInterval = *I);
     103             : 
     104           0 :   ++I;  // After the first one...
     105             : 
     106             :   // Add the rest of the intervals to the partition.
     107           0 :   for (interval_part_interval_iterator E = intervals_end(IP); I != E; ++I)
     108           0 :     addIntervalToPartition(*I);
     109             : 
     110             :   // Now that we know all of the successor information, propagate this to the
     111             :   // predecessors for each block.
     112           0 :   for (unsigned i = 0, e = Intervals.size(); i != e; ++i)
     113           0 :     updatePredecessors(Intervals[i]);
     114           0 : }