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 22using namespace llvm; 23 24char IntervalPartition::ID = 0; 25 26IntervalPartition::IntervalPartition() : FunctionPass(ID) { 27 initializeIntervalPartitionPass(*PassRegistry::getPassRegistry()); 28} 29 30INITIALIZE_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 38void IntervalPartition::releaseMemory() { 39 for (Interval *I : Intervals) 40 delete I; 41 IntervalMap.clear(); 42 Intervals.clear(); 43 RootInterval = nullptr; 44} 45 46void 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). 54void IntervalPartition::addIntervalToPartition(Interval *I) { 55 Intervals.push_back(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(std::make_pair(*It, 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. 67void IntervalPartition::updatePredecessors(Interval *Int) { 68 BasicBlock *Header = Int->getHeaderNode(); 69 for (BasicBlock *Successor : Int->Successors) 70 getBlockInterval(Successor)->Predecessors.push_back(Header); 71} 72 73// IntervalPartition ctor - Build the first level interval partition for the 74// specified function... 75bool 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, false); 78 assert(I != intervals_end(&F) && "No intervals in function!?!?!"); 79 80 addIntervalToPartition(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); 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(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. 98IntervalPartition::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, false); 104 assert(I != intervals_end(IP) && "No intervals in interval partition!?!?!"); 105 106 addIntervalToPartition(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); 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(I); 118} 119