148486893f46d2e12e926682a3ecb908716bc66c4Chris Lattner//===- IntervalPartition.h - Interval partition Calculation -----*- C++ -*-===// 29769ab22265b313171d201b5928688524a01bd87Misha Brukman// 36fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// The LLVM Compiler Infrastructure 46fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 79769ab22265b313171d201b5928688524a01bd87Misha Brukman// 86fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell//===----------------------------------------------------------------------===// 9a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// 108fc2f2072de83665ae20e06929e28317f449bcdfChris Lattner// This file contains the declaration of the IntervalPartition class, which 11f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner// calculates and represents the interval partition of a function, or a 12a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// preexisting interval partition. 13a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// 14a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// In this way, the interval partition may be used to reduce a flow graph down 15a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// to its degenerate single node interval partition (unless it is irreducible). 16a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// 17a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// TODO: The IntervalPartition class should take a bool parameter that tells 18a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// whether it should add the "tails" of an interval to an interval itself or if 19a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// they should be represented as distinct intervals. 20a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// 21a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner//===----------------------------------------------------------------------===// 22a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 23674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_ANALYSIS_INTERVALPARTITION_H 24674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_ANALYSIS_INTERVALPARTITION_H 25a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 26a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner#include "llvm/Analysis/Interval.h" 27facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner#include "llvm/Pass.h" 28c9235d2e855c56e9aa157969f8132a05f9ba89d8Dan Gohman#include <map> 29a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 30d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 31d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 32a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner//===----------------------------------------------------------------------===// 33a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// 34a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// IntervalPartition - This class builds and holds an "interval partition" for 35f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner// a function. This partition divides the control flow graph into a set of 36adb4a40cb6ef2dba298e9dac5a905fcd2bee6e35Will Dietz// maximal intervals, as defined with the properties above. Intuitively, an 3736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// interval is a (possibly nonexistent) loop with a "tail" of non-looping 38a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// nodes following it. 39a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner// 4089f2aa5fd8125b67e4759a9342002c7f99a64751Chris Lattnerclass IntervalPartition : public FunctionPass { 41697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner typedef std::map<BasicBlock*, Interval*> IntervalMapTy; 42a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner IntervalMapTy IntervalMap; 43a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 44697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner typedef std::vector<Interval*> IntervalListTy; 45a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner Interval *RootInterval; 4689f2aa5fd8125b67e4759a9342002c7f99a64751Chris Lattner std::vector<Interval*> Intervals; 47a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 48a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattnerpublic: 49ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 50794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 51dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines IntervalPartition() : FunctionPass(ID), RootInterval(nullptr) { 52081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeIntervalPartitionPass(*PassRegistry::getPassRegistry()); 53081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 541cee94f04111cfd7114979d6dfddce2669c9380dDevang Patel 55f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner // run - Calculate the interval partition for this function 5636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 57a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 58a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // IntervalPartition ctor - Build a reduced interval partition from an 59a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // existing interval graph. This takes an additional boolean parameter to 60a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // distinguish it from a copy constructor. Always pass in false for now. 61a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // 62a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner IntervalPartition(IntervalPartition &I, bool); 63a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 6497f51a3024a72ef8500e95b90e6361e6783160fdChris Lattner // print - Show contents in human readable format... 65dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void print(raw_ostream &O, const Module* = nullptr) const override; 6697f51a3024a72ef8500e95b90e6361e6783160fdChris Lattner 67a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // getRootInterval() - Return the root interval that contains the starting 68f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner // block of the function. 69a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner inline Interval *getRootInterval() { return RootInterval; } 70a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 71a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // isDegeneratePartition() - Returns true if the interval partition contains 72a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // a single interval, and thus cannot be simplified anymore. 7389f2aa5fd8125b67e4759a9342002c7f99a64751Chris Lattner bool isDegeneratePartition() { return Intervals.size() == 1; } 74a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 75a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // TODO: isIrreducible - look for triangle graph. 76a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 77a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // getBlockInterval - Return the interval that a basic block exists in. 78a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner inline Interval *getBlockInterval(BasicBlock *BB) { 79a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner IntervalMapTy::iterator I = IntervalMap.find(BB); 80dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return I != IntervalMap.end() ? I->second : nullptr; 81a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner } 82a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 83f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner // getAnalysisUsage - Implement the Pass API 8436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 85f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner AU.setPreservesAll(); 86facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner } 87facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner 8889f2aa5fd8125b67e4759a9342002c7f99a64751Chris Lattner // Interface to Intervals vector... 8989f2aa5fd8125b67e4759a9342002c7f99a64751Chris Lattner const std::vector<Interval*> &getIntervals() const { return Intervals; } 9089f2aa5fd8125b67e4759a9342002c7f99a64751Chris Lattner 91db57ef1cb3ba87024c5b54ebc1a95aad8e8e8b49Chris Lattner // releaseMemory - Reset state back to before function was analyzed 9236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void releaseMemory() override; 93facd752d3afaeca7dee46648f2a2ae209a94e5e9Chris Lattner 94db57ef1cb3ba87024c5b54ebc1a95aad8e8e8b49Chris Lattnerprivate: 954dd88f6fbf6dc44ceba03b34aeab458536789b98Chris Lattner // addIntervalToPartition - Add an interval to the internal list of intervals, 964dd88f6fbf6dc44ceba03b34aeab458536789b98Chris Lattner // and then add mappings from all of the basic blocks in the interval to the 974dd88f6fbf6dc44ceba03b34aeab458536789b98Chris Lattner // interval itself (in the IntervalMap). 98a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // 994dd88f6fbf6dc44ceba03b34aeab458536789b98Chris Lattner void addIntervalToPartition(Interval *I); 100a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 101a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // updatePredecessors - Interval generation only sets the successor fields of 102a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // the interval data structures. After interval generation is complete, 10381619b121c9a3ff32487343503ad80f2ffe48fc3Misha Brukman // run through all of the intervals and propagate successor info as 104a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // predecessor info. 105a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner // 106a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner void updatePredecessors(Interval *Int); 107a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner}; 108a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner 109d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 110d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 111a9a96efba43de8d1689f7d9af2b442efba8cfc71Chris Lattner#endif 112