1200581Srdivacky//===---------------- lib/CodeGen/CalcSpillWeights.h ------------*- C++ -*-===// 2200581Srdivacky// 3200581Srdivacky// The LLVM Compiler Infrastructure 4200581Srdivacky// 5200581Srdivacky// This file is distributed under the University of Illinois Open Source 6200581Srdivacky// License. See LICENSE.TXT for details. 7200581Srdivacky// 8200581Srdivacky//===----------------------------------------------------------------------===// 9200581Srdivacky 10200581Srdivacky 11200581Srdivacky#ifndef LLVM_CODEGEN_CALCSPILLWEIGHTS_H 12200581Srdivacky#define LLVM_CODEGEN_CALCSPILLWEIGHTS_H 13200581Srdivacky 14249423Sdim#include "llvm/ADT/DenseMap.h" 15221345Sdim#include "llvm/CodeGen/SlotIndexes.h" 16200581Srdivacky 17200581Srdivackynamespace llvm { 18200581Srdivacky 19200581Srdivacky class LiveInterval; 20212904Sdim class LiveIntervals; 21263508Sdim class MachineBlockFrequencyInfo; 22212904Sdim class MachineLoopInfo; 23200581Srdivacky 24263508Sdim /// \brief Normalize the spill weight of a live interval 25218893Sdim /// 26263508Sdim /// The spill weight of a live interval is computed as: 27263508Sdim /// 28218893Sdim /// (sum(use freq) + sum(def freq)) / (K + size) 29218893Sdim /// 30218893Sdim /// @param UseDefFreq Expected number of executed use and def instructions 31218893Sdim /// per function call. Derived from block frequencies. 32218893Sdim /// @param Size Size of live interval as returnexd by getSize() 33218893Sdim /// 34218893Sdim static inline float normalizeSpillWeight(float UseDefFreq, unsigned Size) { 35221345Sdim // The constant 25 instructions is added to avoid depending too much on 36221345Sdim // accidental SlotIndex gaps for small intervals. The effect is that small 37221345Sdim // intervals have a spill weight that is mostly proportional to the number 38221345Sdim // of uses, while large intervals get a spill weight that is closer to a use 39221345Sdim // density. 40221345Sdim return UseDefFreq / (Size + 25*SlotIndex::InstrDist); 41218893Sdim } 42218893Sdim 43263508Sdim /// \brief Calculate auxiliary information for a virtual register such as its 44263508Sdim /// spill weight and allocation hint. 45212904Sdim class VirtRegAuxInfo { 46263508Sdim public: 47263508Sdim typedef float (*NormalizingFn)(float, unsigned); 48263508Sdim 49263508Sdim private: 50221345Sdim MachineFunction &MF; 51221345Sdim LiveIntervals &LIS; 52221345Sdim const MachineLoopInfo &Loops; 53263508Sdim const MachineBlockFrequencyInfo &MBFI; 54221345Sdim DenseMap<unsigned, float> Hint; 55263508Sdim NormalizingFn normalize; 56263508Sdim 57212904Sdim public: 58212904Sdim VirtRegAuxInfo(MachineFunction &mf, LiveIntervals &lis, 59263508Sdim const MachineLoopInfo &loops, 60263508Sdim const MachineBlockFrequencyInfo &mbfi, 61263508Sdim NormalizingFn norm = normalizeSpillWeight) 62263508Sdim : MF(mf), LIS(lis), Loops(loops), MBFI(mbfi), normalize(norm) {} 63212904Sdim 64263508Sdim /// \brief (re)compute li's spill weight and allocation hint. 65263508Sdim void calculateSpillWeightAndHint(LiveInterval &li); 66212904Sdim }; 67212904Sdim 68263508Sdim /// \brief Compute spill weights and allocation hints for all virtual register 69200581Srdivacky /// live intervals. 70263508Sdim void calculateSpillWeightsAndHints(LiveIntervals &LIS, MachineFunction &MF, 71263508Sdim const MachineLoopInfo &MLI, 72263508Sdim const MachineBlockFrequencyInfo &MBFI, 73263508Sdim VirtRegAuxInfo::NormalizingFn norm = 74263508Sdim normalizeSpillWeight); 75200581Srdivacky} 76200581Srdivacky 77200581Srdivacky#endif // LLVM_CODEGEN_CALCSPILLWEIGHTS_H 78