InlineOrder.h

Go to the documentation of this file.

//===- InlineOrder.h - Inlining order abstraction -*- C++ ---*-------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
#ifndef LLVM_ANALYSIS_INLINEORDER_H
#define LLVM_ANALYSIS_INLINEORDER_H
 
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include <algorithm>
#include <utility>
 
namespace llvm {
class CallBase;
class Function;
 
template <typename T> class InlineOrder {
public:
  using reference = T &;
  using const_reference = const T &;
 
  virtual ~InlineOrder() {}
 
  virtual size_t size() = 0;
 
  virtual void push(const T &Elt) = 0;
 
  virtual T pop() = 0;
 
  virtual const_reference front() = 0;
 
  virtual void erase_if(function_ref<bool(T)> Pred) = 0;
 
  bool empty() { return !size(); }
};
 
template <typename T, typename Container = SmallVector<T, 16>>
class DefaultInlineOrder : public InlineOrder<T> {
  using reference = T &;
  using const_reference = const T &;
 
public:
  size_t size() override { return Calls.size() - FirstIndex; }
 
  void push(const T &Elt) override { Calls.push_back(Elt); }
 
  T pop() override {
    assert(size() > 0);
    return Calls[FirstIndex++];
  }
 
  const_reference front() override {
    assert(size() > 0);
    return Calls[FirstIndex];
  }
 
  void erase_if(function_ref<bool(T)> Pred) override {
    Calls.erase(std::remove_if(Calls.begin() + FirstIndex, Calls.end(), Pred),
                Calls.end());
  }
 
private:
  Container Calls;
  size_t FirstIndex = 0;
};
 
class InlineSizePriority {
public:
  InlineSizePriority(int Size) : Size(Size) {}
 
  static bool isMoreDesirable(const InlineSizePriority &S1,
                              const InlineSizePriority &S2) {
    return S1.Size < S2.Size;
  }
 
  static InlineSizePriority evaluate(CallBase *CB) {
    Function *Callee = CB->getCalledFunction();
    return InlineSizePriority(Callee->getInstructionCount());
  }
 
  int Size;
};
 
template <typename PriorityT>
class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> {
  using T = std::pair<CallBase *, int>;
  using HeapT = std::pair<CallBase *, PriorityT>;
  using reference = T &;
  using const_reference = const T &;
 
  static bool cmp(const HeapT &P1, const HeapT &P2) {
    return PriorityT::isMoreDesirable(P2.second, P1.second);
  }
 
  // A call site could become less desirable for inlining because of the size
  // growth from prior inlining into the callee. This method is used to lazily
  // update the desirability of a call site if it's decreasing. It is only
  // called on pop() or front(), not every time the desirability changes. When
  // the desirability of the front call site decreases, an updated one would be
  // pushed right back into the heap. For simplicity, those cases where
  // the desirability of a call site increases are ignored here.
  void adjust() {
    bool Changed = false;
    do {
      CallBase *CB = Heap.front().first;
      const PriorityT PreviousGoodness = Heap.front().second;
      const PriorityT CurrentGoodness = PriorityT::evaluate(CB);
      Changed = PriorityT::isMoreDesirable(PreviousGoodness, CurrentGoodness);
      if (Changed) {
        std::pop_heap(Heap.begin(), Heap.end(), cmp);
        Heap.pop_back();
        Heap.push_back({CB, CurrentGoodness});
        std::push_heap(Heap.begin(), Heap.end(), cmp);
      }
    } while (Changed);
  }
 
public:
  size_t size() override { return Heap.size(); }
 
  void push(const T &Elt) override {
    CallBase *CB = Elt.first;
    const int InlineHistoryID = Elt.second;
    const PriorityT Goodness = PriorityT::evaluate(CB);
 
    Heap.push_back({CB, Goodness});
    std::push_heap(Heap.begin(), Heap.end(), cmp);
    InlineHistoryMap[CB] = InlineHistoryID;
  }
 
  T pop() override {
    assert(size() > 0);
    adjust();
 
    CallBase *CB = Heap.front().first;
    T Result = std::make_pair(CB, InlineHistoryMap[CB]);
    InlineHistoryMap.erase(CB);
    std::pop_heap(Heap.begin(), Heap.end(), cmp);
    Heap.pop_back();
    return Result;
  }
 
  const_reference front() override {
    assert(size() > 0);
    adjust();
 
    CallBase *CB = Heap.front().first;
    return *InlineHistoryMap.find(CB);
  }
 
  void erase_if(function_ref<bool(T)> Pred) override {
    auto PredWrapper = [=](HeapT P) -> bool {
      return Pred(std::make_pair(P.first, 0));
    };
    llvm::erase_if(Heap, PredWrapper);
    std::make_heap(Heap.begin(), Heap.end(), cmp);
  }
 
private:
  SmallVector<HeapT, 16> Heap;
  DenseMap<CallBase *, int> InlineHistoryMap;
};
} // namespace llvm
#endif // LLVM_ANALYSIS_INLINEORDER_H