blob: e71f400f4aa446b061f68ef3e96e0e428639357d [file] [log] [blame]
Chris Lattnercf3056d2003-10-13 03:32:08 +00001//===- IntervalPartition.cpp - Interval Partition module code -------------===//
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002//
John Criswellb576c942003-10-20 19:43:21 +00003// The LLVM Compiler Infrastructure
4//
5// This file was developed by the LLVM research group and is distributed under
6// the University of Illinois Open Source License. See LICENSE.TXT for details.
Misha Brukman2b37d7c2005-04-21 21:13:18 +00007//
John Criswellb576c942003-10-20 19:43:21 +00008//===----------------------------------------------------------------------===//
Chris Lattner2d676c92001-06-24 04:07:44 +00009//
Chris Lattner1b7f7dc2002-04-28 16:21:30 +000010// This file contains the definition of the IntervalPartition class, which
Chris Lattner2fbfdcf2002-04-07 20:49:59 +000011// calculates and represent the interval partition of a function.
Chris Lattner2d676c92001-06-24 04:07:44 +000012//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/Analysis/IntervalIterator.h"
Chris Lattner13d01082005-02-22 23:27:21 +000016using namespace llvm;
Brian Gaeked0fde302003-11-11 22:41:34 +000017
Chris Lattner1e435162002-07-26 21:12:44 +000018static RegisterAnalysis<IntervalPartition>
Chris Lattner17689df2002-07-30 16:27:52 +000019X("intervals", "Interval Partition Construction", true);
Chris Lattner1e435162002-07-26 21:12:44 +000020
Chris Lattner2d676c92001-06-24 04:07:44 +000021//===----------------------------------------------------------------------===//
22// IntervalPartition Implementation
23//===----------------------------------------------------------------------===//
24
Chris Lattner2fbfdcf2002-04-07 20:49:59 +000025// destroy - Reset state back to before function was analyzed
Chris Lattner93193f82002-01-31 00:42:27 +000026void IntervalPartition::destroy() {
Chris Lattner13d01082005-02-22 23:27:21 +000027 for (unsigned i = 0, e = Intervals.size(); i != e; ++i)
28 delete Intervals[i];
Chris Lattner93193f82002-01-31 00:42:27 +000029 IntervalMap.clear();
30 RootInterval = 0;
Chris Lattner2d676c92001-06-24 04:07:44 +000031}
32
Reid Spencerce9653c2004-12-07 04:03:45 +000033void IntervalPartition::print(std::ostream &O, const Module*) const {
Chris Lattner38969482002-08-09 22:52:08 +000034 std::copy(Intervals.begin(), Intervals.end(),
Chris Lattnera59cbb22002-07-27 01:12:17 +000035 std::ostream_iterator<const Interval *>(O, "\n"));
36}
37
Chris Lattner23e36622001-06-25 03:55:04 +000038// addIntervalToPartition - Add an interval to the internal list of intervals,
39// and then add mappings from all of the basic blocks in the interval to the
40// interval itself (in the IntervalMap).
Chris Lattner2d676c92001-06-24 04:07:44 +000041//
Chris Lattner23e36622001-06-25 03:55:04 +000042void IntervalPartition::addIntervalToPartition(Interval *I) {
Chris Lattner38969482002-08-09 22:52:08 +000043 Intervals.push_back(I);
Chris Lattner2d676c92001-06-24 04:07:44 +000044
45 // Add mappings for all of the basic blocks in I to the IntervalPartition
46 for (Interval::node_iterator It = I->Nodes.begin(), End = I->Nodes.end();
47 It != End; ++It)
Chris Lattnercf3056d2003-10-13 03:32:08 +000048 IntervalMap.insert(std::make_pair(*It, I));
Chris Lattner2d676c92001-06-24 04:07:44 +000049}
50
Chris Lattner2d676c92001-06-24 04:07:44 +000051// updatePredecessors - Interval generation only sets the successor fields of
52// the interval data structures. After interval generation is complete,
Misha Brukmana3bbcb52002-10-29 23:06:16 +000053// run through all of the intervals and propagate successor info as
Chris Lattner2d676c92001-06-24 04:07:44 +000054// predecessor info.
55//
Chris Lattner1b7f7dc2002-04-28 16:21:30 +000056void IntervalPartition::updatePredecessors(Interval *Int) {
Chris Lattner2d676c92001-06-24 04:07:44 +000057 BasicBlock *Header = Int->getHeaderNode();
Misha Brukman2b37d7c2005-04-21 21:13:18 +000058 for (Interval::succ_iterator I = Int->Successors.begin(),
Chris Lattner2d676c92001-06-24 04:07:44 +000059 E = Int->Successors.end(); I != E; ++I)
60 getBlockInterval(*I)->Predecessors.push_back(Header);
61}
62
Chris Lattner2d676c92001-06-24 04:07:44 +000063// IntervalPartition ctor - Build the first level interval partition for the
Chris Lattner2fbfdcf2002-04-07 20:49:59 +000064// specified function...
Chris Lattner2d676c92001-06-24 04:07:44 +000065//
Chris Lattner7e708292002-06-25 16:13:24 +000066bool IntervalPartition::runOnFunction(Function &F) {
Chris Lattner23e36622001-06-25 03:55:04 +000067 // Pass false to intervals_begin because we take ownership of it's memory
Chris Lattner7e708292002-06-25 16:13:24 +000068 function_interval_iterator I = intervals_begin(&F, false);
69 assert(I != intervals_end(&F) && "No intervals in function!?!?!");
Chris Lattner23e36622001-06-25 03:55:04 +000070
71 addIntervalToPartition(RootInterval = *I);
72
Chris Lattner7fc9fe32001-06-27 23:41:11 +000073 ++I; // After the first one...
74
Chris Lattner13d01082005-02-22 23:27:21 +000075 // Add the rest of the intervals to the partition.
76 for (function_interval_iterator E = intervals_end(&F); I != E; ++I)
77 addIntervalToPartition(*I);
Chris Lattner2d676c92001-06-24 04:07:44 +000078
Misha Brukmana3bbcb52002-10-29 23:06:16 +000079 // Now that we know all of the successor information, propagate this to the
Chris Lattner13d01082005-02-22 23:27:21 +000080 // predecessors for each block.
81 for (unsigned i = 0, e = Intervals.size(); i != e; ++i)
82 updatePredecessors(Intervals[i]);
Chris Lattner93193f82002-01-31 00:42:27 +000083 return false;
Chris Lattner2d676c92001-06-24 04:07:44 +000084}
85
86
87// IntervalPartition ctor - Build a reduced interval partition from an
88// existing interval graph. This takes an additional boolean parameter to
89// distinguish it from a copy constructor. Always pass in false for now.
90//
Chris Lattner23e36622001-06-25 03:55:04 +000091IntervalPartition::IntervalPartition(IntervalPartition &IP, bool) {
Chris Lattner2fbfdcf2002-04-07 20:49:59 +000092 Interval *FunctionStart = IP.getRootInterval();
93 assert(FunctionStart && "Cannot operate on empty IntervalPartitions!");
Chris Lattner2d676c92001-06-24 04:07:44 +000094
Chris Lattner23e36622001-06-25 03:55:04 +000095 // Pass false to intervals_begin because we take ownership of it's memory
96 interval_part_interval_iterator I = intervals_begin(IP, false);
Chris Lattner7fc9fe32001-06-27 23:41:11 +000097 assert(I != intervals_end(IP) && "No intervals in interval partition!?!?!");
Chris Lattner23e36622001-06-25 03:55:04 +000098
99 addIntervalToPartition(RootInterval = *I);
100
Chris Lattner7fc9fe32001-06-27 23:41:11 +0000101 ++I; // After the first one...
102
Chris Lattner13d01082005-02-22 23:27:21 +0000103 // Add the rest of the intervals to the partition.
104 for (interval_part_interval_iterator E = intervals_end(IP); I != E; ++I)
105 addIntervalToPartition(*I);
Chris Lattner2d676c92001-06-24 04:07:44 +0000106
Misha Brukmana3bbcb52002-10-29 23:06:16 +0000107 // Now that we know all of the successor information, propagate this to the
Chris Lattner13d01082005-02-22 23:27:21 +0000108 // predecessors for each block.
109 for (unsigned i = 0, e = Intervals.size(); i != e; ++i)
110 updatePredecessors(Intervals[i]);
Chris Lattner2d676c92001-06-24 04:07:44 +0000111}
Brian Gaeked0fde302003-11-11 22:41:34 +0000112