Chris Lattner | cf3056d | 2003-10-13 03:32:08 +0000 | [diff] [blame] | 1 | //===- IntervalPartition.cpp - Interval Partition module code -------------===// |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame^] | 2 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 3 | // 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 Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame^] | 7 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | 2d676c9 | 2001-06-24 04:07:44 +0000 | [diff] [blame] | 9 | // |
Chris Lattner | 1b7f7dc | 2002-04-28 16:21:30 +0000 | [diff] [blame] | 10 | // This file contains the definition of the IntervalPartition class, which |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 11 | // calculates and represent the interval partition of a function. |
Chris Lattner | 2d676c9 | 2001-06-24 04:07:44 +0000 | [diff] [blame] | 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #include "llvm/Analysis/IntervalIterator.h" |
Chris Lattner | 13d0108 | 2005-02-22 23:27:21 +0000 | [diff] [blame] | 16 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 17 | |
Chris Lattner | 1e43516 | 2002-07-26 21:12:44 +0000 | [diff] [blame] | 18 | static RegisterAnalysis<IntervalPartition> |
Chris Lattner | 17689df | 2002-07-30 16:27:52 +0000 | [diff] [blame] | 19 | X("intervals", "Interval Partition Construction", true); |
Chris Lattner | 1e43516 | 2002-07-26 21:12:44 +0000 | [diff] [blame] | 20 | |
Chris Lattner | 2d676c9 | 2001-06-24 04:07:44 +0000 | [diff] [blame] | 21 | //===----------------------------------------------------------------------===// |
| 22 | // IntervalPartition Implementation |
| 23 | //===----------------------------------------------------------------------===// |
| 24 | |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 25 | // destroy - Reset state back to before function was analyzed |
Chris Lattner | 93193f8 | 2002-01-31 00:42:27 +0000 | [diff] [blame] | 26 | void IntervalPartition::destroy() { |
Chris Lattner | 13d0108 | 2005-02-22 23:27:21 +0000 | [diff] [blame] | 27 | for (unsigned i = 0, e = Intervals.size(); i != e; ++i) |
| 28 | delete Intervals[i]; |
Chris Lattner | 93193f8 | 2002-01-31 00:42:27 +0000 | [diff] [blame] | 29 | IntervalMap.clear(); |
| 30 | RootInterval = 0; |
Chris Lattner | 2d676c9 | 2001-06-24 04:07:44 +0000 | [diff] [blame] | 31 | } |
| 32 | |
Reid Spencer | ce9653c | 2004-12-07 04:03:45 +0000 | [diff] [blame] | 33 | void IntervalPartition::print(std::ostream &O, const Module*) const { |
Chris Lattner | 3896948 | 2002-08-09 22:52:08 +0000 | [diff] [blame] | 34 | std::copy(Intervals.begin(), Intervals.end(), |
Chris Lattner | a59cbb2 | 2002-07-27 01:12:17 +0000 | [diff] [blame] | 35 | std::ostream_iterator<const Interval *>(O, "\n")); |
| 36 | } |
| 37 | |
Chris Lattner | 23e3662 | 2001-06-25 03:55:04 +0000 | [diff] [blame] | 38 | // 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 Lattner | 2d676c9 | 2001-06-24 04:07:44 +0000 | [diff] [blame] | 41 | // |
Chris Lattner | 23e3662 | 2001-06-25 03:55:04 +0000 | [diff] [blame] | 42 | void IntervalPartition::addIntervalToPartition(Interval *I) { |
Chris Lattner | 3896948 | 2002-08-09 22:52:08 +0000 | [diff] [blame] | 43 | Intervals.push_back(I); |
Chris Lattner | 2d676c9 | 2001-06-24 04:07:44 +0000 | [diff] [blame] | 44 | |
| 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 Lattner | cf3056d | 2003-10-13 03:32:08 +0000 | [diff] [blame] | 48 | IntervalMap.insert(std::make_pair(*It, I)); |
Chris Lattner | 2d676c9 | 2001-06-24 04:07:44 +0000 | [diff] [blame] | 49 | } |
| 50 | |
Chris Lattner | 2d676c9 | 2001-06-24 04:07:44 +0000 | [diff] [blame] | 51 | // updatePredecessors - Interval generation only sets the successor fields of |
| 52 | // the interval data structures. After interval generation is complete, |
Misha Brukman | a3bbcb5 | 2002-10-29 23:06:16 +0000 | [diff] [blame] | 53 | // run through all of the intervals and propagate successor info as |
Chris Lattner | 2d676c9 | 2001-06-24 04:07:44 +0000 | [diff] [blame] | 54 | // predecessor info. |
| 55 | // |
Chris Lattner | 1b7f7dc | 2002-04-28 16:21:30 +0000 | [diff] [blame] | 56 | void IntervalPartition::updatePredecessors(Interval *Int) { |
Chris Lattner | 2d676c9 | 2001-06-24 04:07:44 +0000 | [diff] [blame] | 57 | BasicBlock *Header = Int->getHeaderNode(); |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame^] | 58 | for (Interval::succ_iterator I = Int->Successors.begin(), |
Chris Lattner | 2d676c9 | 2001-06-24 04:07:44 +0000 | [diff] [blame] | 59 | E = Int->Successors.end(); I != E; ++I) |
| 60 | getBlockInterval(*I)->Predecessors.push_back(Header); |
| 61 | } |
| 62 | |
Chris Lattner | 2d676c9 | 2001-06-24 04:07:44 +0000 | [diff] [blame] | 63 | // IntervalPartition ctor - Build the first level interval partition for the |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 64 | // specified function... |
Chris Lattner | 2d676c9 | 2001-06-24 04:07:44 +0000 | [diff] [blame] | 65 | // |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 66 | bool IntervalPartition::runOnFunction(Function &F) { |
Chris Lattner | 23e3662 | 2001-06-25 03:55:04 +0000 | [diff] [blame] | 67 | // Pass false to intervals_begin because we take ownership of it's memory |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 68 | function_interval_iterator I = intervals_begin(&F, false); |
| 69 | assert(I != intervals_end(&F) && "No intervals in function!?!?!"); |
Chris Lattner | 23e3662 | 2001-06-25 03:55:04 +0000 | [diff] [blame] | 70 | |
| 71 | addIntervalToPartition(RootInterval = *I); |
| 72 | |
Chris Lattner | 7fc9fe3 | 2001-06-27 23:41:11 +0000 | [diff] [blame] | 73 | ++I; // After the first one... |
| 74 | |
Chris Lattner | 13d0108 | 2005-02-22 23:27:21 +0000 | [diff] [blame] | 75 | // 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 Lattner | 2d676c9 | 2001-06-24 04:07:44 +0000 | [diff] [blame] | 78 | |
Misha Brukman | a3bbcb5 | 2002-10-29 23:06:16 +0000 | [diff] [blame] | 79 | // Now that we know all of the successor information, propagate this to the |
Chris Lattner | 13d0108 | 2005-02-22 23:27:21 +0000 | [diff] [blame] | 80 | // predecessors for each block. |
| 81 | for (unsigned i = 0, e = Intervals.size(); i != e; ++i) |
| 82 | updatePredecessors(Intervals[i]); |
Chris Lattner | 93193f8 | 2002-01-31 00:42:27 +0000 | [diff] [blame] | 83 | return false; |
Chris Lattner | 2d676c9 | 2001-06-24 04:07:44 +0000 | [diff] [blame] | 84 | } |
| 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 Lattner | 23e3662 | 2001-06-25 03:55:04 +0000 | [diff] [blame] | 91 | IntervalPartition::IntervalPartition(IntervalPartition &IP, bool) { |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 92 | Interval *FunctionStart = IP.getRootInterval(); |
| 93 | assert(FunctionStart && "Cannot operate on empty IntervalPartitions!"); |
Chris Lattner | 2d676c9 | 2001-06-24 04:07:44 +0000 | [diff] [blame] | 94 | |
Chris Lattner | 23e3662 | 2001-06-25 03:55:04 +0000 | [diff] [blame] | 95 | // Pass false to intervals_begin because we take ownership of it's memory |
| 96 | interval_part_interval_iterator I = intervals_begin(IP, false); |
Chris Lattner | 7fc9fe3 | 2001-06-27 23:41:11 +0000 | [diff] [blame] | 97 | assert(I != intervals_end(IP) && "No intervals in interval partition!?!?!"); |
Chris Lattner | 23e3662 | 2001-06-25 03:55:04 +0000 | [diff] [blame] | 98 | |
| 99 | addIntervalToPartition(RootInterval = *I); |
| 100 | |
Chris Lattner | 7fc9fe3 | 2001-06-27 23:41:11 +0000 | [diff] [blame] | 101 | ++I; // After the first one... |
| 102 | |
Chris Lattner | 13d0108 | 2005-02-22 23:27:21 +0000 | [diff] [blame] | 103 | // 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 Lattner | 2d676c9 | 2001-06-24 04:07:44 +0000 | [diff] [blame] | 106 | |
Misha Brukman | a3bbcb5 | 2002-10-29 23:06:16 +0000 | [diff] [blame] | 107 | // Now that we know all of the successor information, propagate this to the |
Chris Lattner | 13d0108 | 2005-02-22 23:27:21 +0000 | [diff] [blame] | 108 | // predecessors for each block. |
| 109 | for (unsigned i = 0, e = Intervals.size(); i != e; ++i) |
| 110 | updatePredecessors(Intervals[i]); |
Chris Lattner | 2d676c9 | 2001-06-24 04:07:44 +0000 | [diff] [blame] | 111 | } |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 112 | |