1a937f220e14826266a8f05b58a541aad669c8912Lang Hames//===---------------- lib/CodeGen/CalcSpillWeights.h ------------*- C++ -*-===// 2a937f220e14826266a8f05b58a541aad669c8912Lang Hames// 3a937f220e14826266a8f05b58a541aad669c8912Lang Hames// The LLVM Compiler Infrastructure 4a937f220e14826266a8f05b58a541aad669c8912Lang Hames// 5a937f220e14826266a8f05b58a541aad669c8912Lang Hames// This file is distributed under the University of Illinois Open Source 6a937f220e14826266a8f05b58a541aad669c8912Lang Hames// License. See LICENSE.TXT for details. 7a937f220e14826266a8f05b58a541aad669c8912Lang Hames// 8a937f220e14826266a8f05b58a541aad669c8912Lang Hames//===----------------------------------------------------------------------===// 9a937f220e14826266a8f05b58a541aad669c8912Lang Hames 10a937f220e14826266a8f05b58a541aad669c8912Lang Hames 11a937f220e14826266a8f05b58a541aad669c8912Lang Hames#ifndef LLVM_CODEGEN_CALCSPILLWEIGHTS_H 12a937f220e14826266a8f05b58a541aad669c8912Lang Hames#define LLVM_CODEGEN_CALCSPILLWEIGHTS_H 13a937f220e14826266a8f05b58a541aad669c8912Lang Hames 14df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen#include "llvm/ADT/DenseMap.h" 15255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/CodeGen/SlotIndexes.h" 16a937f220e14826266a8f05b58a541aad669c8912Lang Hames 17a937f220e14826266a8f05b58a541aad669c8912Lang Hamesnamespace llvm { 18a937f220e14826266a8f05b58a541aad669c8912Lang Hames 19a937f220e14826266a8f05b58a541aad669c8912Lang Hames class LiveInterval; 20df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen class LiveIntervals; 214eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer class MachineBlockFrequencyInfo; 22df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen class MachineLoopInfo; 23df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen 24eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen /// normalizeSpillWeight - The spill weight of a live interval is computed as: 25eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen /// 26eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen /// (sum(use freq) + sum(def freq)) / (K + size) 27eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen /// 28eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen /// @param UseDefFreq Expected number of executed use and def instructions 29eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen /// per function call. Derived from block frequencies. 30eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen /// @param Size Size of live interval as returnexd by getSize() 31eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen /// 32eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen static inline float normalizeSpillWeight(float UseDefFreq, unsigned Size) { 33bee41501fae5414070a2797e853da15ea29b92a8Jakob Stoklund Olesen // The constant 25 instructions is added to avoid depending too much on 34bee41501fae5414070a2797e853da15ea29b92a8Jakob Stoklund Olesen // accidental SlotIndex gaps for small intervals. The effect is that small 35bee41501fae5414070a2797e853da15ea29b92a8Jakob Stoklund Olesen // intervals have a spill weight that is mostly proportional to the number 36bee41501fae5414070a2797e853da15ea29b92a8Jakob Stoklund Olesen // of uses, while large intervals get a spill weight that is closer to a use 37bee41501fae5414070a2797e853da15ea29b92a8Jakob Stoklund Olesen // density. 38bee41501fae5414070a2797e853da15ea29b92a8Jakob Stoklund Olesen return UseDefFreq / (Size + 25*SlotIndex::InstrDist); 39eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen } 40eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen 41df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen /// VirtRegAuxInfo - Calculate auxiliary information for a virtual 42df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen /// register such as its spill weight and allocation hint. 43df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen class VirtRegAuxInfo { 441394e6d9252ed188dbd73a59bcb4f15526641363Jakob Stoklund Olesen MachineFunction &MF; 451394e6d9252ed188dbd73a59bcb4f15526641363Jakob Stoklund Olesen LiveIntervals &LIS; 461394e6d9252ed188dbd73a59bcb4f15526641363Jakob Stoklund Olesen const MachineLoopInfo &Loops; 474eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer const MachineBlockFrequencyInfo &MBFI; 481394e6d9252ed188dbd73a59bcb4f15526641363Jakob Stoklund Olesen DenseMap<unsigned, float> Hint; 49df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen public: 50df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen VirtRegAuxInfo(MachineFunction &mf, LiveIntervals &lis, 514eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer const MachineLoopInfo &loops, 524eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer const MachineBlockFrequencyInfo &mbfi) 534eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer : MF(mf), LIS(lis), Loops(loops), MBFI(mbfi) {} 54df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen 55df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen /// CalculateWeightAndHint - (re)compute li's spill weight and allocation 56df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen /// hint. 57df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen void CalculateWeightAndHint(LiveInterval &li); 58df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen }; 59a937f220e14826266a8f05b58a541aad669c8912Lang Hames 60a937f220e14826266a8f05b58a541aad669c8912Lang Hames /// CalculateSpillWeights - Compute spill weights for all virtual register 61a937f220e14826266a8f05b58a541aad669c8912Lang Hames /// live intervals. 62a937f220e14826266a8f05b58a541aad669c8912Lang Hames class CalculateSpillWeights : public MachineFunctionPass { 63a937f220e14826266a8f05b58a541aad669c8912Lang Hames public: 64a937f220e14826266a8f05b58a541aad669c8912Lang Hames static char ID; 65a937f220e14826266a8f05b58a541aad669c8912Lang Hames 66081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson CalculateSpillWeights() : MachineFunctionPass(ID) { 67081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 68081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 69a937f220e14826266a8f05b58a541aad669c8912Lang Hames 70a937f220e14826266a8f05b58a541aad669c8912Lang Hames virtual void getAnalysisUsage(AnalysisUsage &au) const; 71a937f220e14826266a8f05b58a541aad669c8912Lang Hames 72df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction &fn); 73a937f220e14826266a8f05b58a541aad669c8912Lang Hames 74a937f220e14826266a8f05b58a541aad669c8912Lang Hames private: 75a937f220e14826266a8f05b58a541aad669c8912Lang Hames /// Returns true if the given live interval is zero length. 76a937f220e14826266a8f05b58a541aad669c8912Lang Hames bool isZeroLengthInterval(LiveInterval *li) const; 77a937f220e14826266a8f05b58a541aad669c8912Lang Hames }; 78a937f220e14826266a8f05b58a541aad669c8912Lang Hames 79a937f220e14826266a8f05b58a541aad669c8912Lang Hames} 80a937f220e14826266a8f05b58a541aad669c8912Lang Hames 81a937f220e14826266a8f05b58a541aad669c8912Lang Hames#endif // LLVM_CODEGEN_CALCSPILLWEIGHTS_H 82