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 24a77da0579bc141eba62760e21a216e5d3eafd792Arnaud A. de Grandmaison /// \brief Normalize the spill weight of a live interval 25a77da0579bc141eba62760e21a216e5d3eafd792Arnaud A. de Grandmaison /// 26a77da0579bc141eba62760e21a216e5d3eafd792Arnaud A. de Grandmaison /// The spill weight of a live interval is computed as: 27eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen /// 28eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen /// (sum(use freq) + sum(def freq)) / (K + size) 29eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen /// 30eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen /// @param UseDefFreq Expected number of executed use and def instructions 31eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen /// per function call. Derived from block frequencies. 32eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen /// @param Size Size of live interval as returnexd by getSize() 33eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen /// 34eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen static inline float normalizeSpillWeight(float UseDefFreq, unsigned Size) { 35bee41501fae5414070a2797e853da15ea29b92a8Jakob Stoklund Olesen // The constant 25 instructions is added to avoid depending too much on 36bee41501fae5414070a2797e853da15ea29b92a8Jakob Stoklund Olesen // accidental SlotIndex gaps for small intervals. The effect is that small 37bee41501fae5414070a2797e853da15ea29b92a8Jakob Stoklund Olesen // intervals have a spill weight that is mostly proportional to the number 38bee41501fae5414070a2797e853da15ea29b92a8Jakob Stoklund Olesen // of uses, while large intervals get a spill weight that is closer to a use 39bee41501fae5414070a2797e853da15ea29b92a8Jakob Stoklund Olesen // density. 40bee41501fae5414070a2797e853da15ea29b92a8Jakob Stoklund Olesen return UseDefFreq / (Size + 25*SlotIndex::InstrDist); 41eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen } 42eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen 43a77da0579bc141eba62760e21a216e5d3eafd792Arnaud A. de Grandmaison /// \brief Calculate auxiliary information for a virtual register such as its 44a77da0579bc141eba62760e21a216e5d3eafd792Arnaud A. de Grandmaison /// spill weight and allocation hint. 45df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen class VirtRegAuxInfo { 46d736763847cee94c40a7f4d106cad91445834b7cArnaud A. de Grandmaison public: 47d736763847cee94c40a7f4d106cad91445834b7cArnaud A. de Grandmaison typedef float (*NormalizingFn)(float, unsigned); 48d736763847cee94c40a7f4d106cad91445834b7cArnaud A. de Grandmaison 49d736763847cee94c40a7f4d106cad91445834b7cArnaud A. de Grandmaison private: 501394e6d9252ed188dbd73a59bcb4f15526641363Jakob Stoklund Olesen MachineFunction &MF; 511394e6d9252ed188dbd73a59bcb4f15526641363Jakob Stoklund Olesen LiveIntervals &LIS; 521394e6d9252ed188dbd73a59bcb4f15526641363Jakob Stoklund Olesen const MachineLoopInfo &Loops; 534eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer const MachineBlockFrequencyInfo &MBFI; 541394e6d9252ed188dbd73a59bcb4f15526641363Jakob Stoklund Olesen DenseMap<unsigned, float> Hint; 55d736763847cee94c40a7f4d106cad91445834b7cArnaud A. de Grandmaison NormalizingFn normalize; 56d736763847cee94c40a7f4d106cad91445834b7cArnaud A. de Grandmaison 57df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen public: 58df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen VirtRegAuxInfo(MachineFunction &mf, LiveIntervals &lis, 594eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer const MachineLoopInfo &loops, 60d736763847cee94c40a7f4d106cad91445834b7cArnaud A. de Grandmaison const MachineBlockFrequencyInfo &mbfi, 61d736763847cee94c40a7f4d106cad91445834b7cArnaud A. de Grandmaison NormalizingFn norm = normalizeSpillWeight) 62d736763847cee94c40a7f4d106cad91445834b7cArnaud A. de Grandmaison : MF(mf), LIS(lis), Loops(loops), MBFI(mbfi), normalize(norm) {} 63df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen 64a77da0579bc141eba62760e21a216e5d3eafd792Arnaud A. de Grandmaison /// \brief (re)compute li's spill weight and allocation hint. 65095f994ba63994e8eb4b77127f9b872429496dbaArnaud A. de Grandmaison void calculateSpillWeightAndHint(LiveInterval &li); 66df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen }; 67a937f220e14826266a8f05b58a541aad669c8912Lang Hames 68a77da0579bc141eba62760e21a216e5d3eafd792Arnaud A. de Grandmaison /// \brief Compute spill weights and allocation hints for all virtual register 69a937f220e14826266a8f05b58a541aad669c8912Lang Hames /// live intervals. 70095f994ba63994e8eb4b77127f9b872429496dbaArnaud A. de Grandmaison void calculateSpillWeightsAndHints(LiveIntervals &LIS, MachineFunction &MF, 71095f994ba63994e8eb4b77127f9b872429496dbaArnaud A. de Grandmaison const MachineLoopInfo &MLI, 72d736763847cee94c40a7f4d106cad91445834b7cArnaud A. de Grandmaison const MachineBlockFrequencyInfo &MBFI, 73d736763847cee94c40a7f4d106cad91445834b7cArnaud A. de Grandmaison VirtRegAuxInfo::NormalizingFn norm = 74d736763847cee94c40a7f4d106cad91445834b7cArnaud A. de Grandmaison normalizeSpillWeight); 75a937f220e14826266a8f05b58a541aad669c8912Lang Hames} 76a937f220e14826266a8f05b58a541aad669c8912Lang Hames 77a937f220e14826266a8f05b58a541aad669c8912Lang Hames#endif // LLVM_CODEGEN_CALCSPILLWEIGHTS_H 78