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