llvm.org GIT mirror llvm / release_50 include / llvm / CodeGen / DFAPacketizer.h
release_50

Tree @release_50 (Download .tar.gz)

DFAPacketizer.h @release_50

643c0a4
dc81e5d
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
255f89f
9653264
643c0a4
9023370
643c0a4
 
 
dc81e5d
 
 
643c0a4
 
 
dc81e5d
ebafa0c
643c0a4
ebafa0c
643c0a4
dc81e5d
d8d11cb
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
643c0a4
 
 
d8d11cb
 
 
dc81e5d
 
643c0a4
bf390b0
dc81e5d
643c0a4
bf390b0
dc81e5d
 
f6f77e9
dc81e5d
 
d3b460f
bf390b0
dc81e5d
 
bf390b0
464f3a3
dc81e5d
f6f77e9
dc81e5d
 
 
 
d3b460f
bf390b0
 
d3b460f
d8d11cb
bf390b0
d3b460f
 
643c0a4
dc81e5d
d3b460f
 
643c0a4
dc81e5d
d3b460f
 
643c0a4
dc81e5d
d3b460f
 
643c0a4
9023370
 
dc81e5d
ebafa0c
d3b460f
 
 
 
 
 
 
ebafa0c
9023370
18693ad
ebafa0c
e0d5233
ebafa0c
9023370
 
ebafa0c
 
 
 
d3b460f
9023370
ebafa0c
 
e0d5233
 
 
ebafa0c
 
 
d3b460f
ebafa0c
 
 
 
d3b460f
ebafa0c
 
 
0ce039d
 
9023370
0ce039d
9023370
ebafa0c
c07a65e
 
 
0ce039d
 
9023370
d3b460f
 
 
ebafa0c
d3b460f
0ce039d
fe9f74e
9023370
 
ebafa0c
d3b460f
 
0ce039d
ebafa0c
8ad916f
 
 
 
 
 
0ce039d
8ad916f
d3b460f
ebafa0c
 
 
 
d3b460f
ebafa0c
 
 
9653264
 
 
ebafa0c
d3b460f
643c0a4
dc81e5d
643c0a4
//===- llvm/CodeGen/DFAPacketizer.h - DFA Packetizer for VLIW ---*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
// This class implements a deterministic finite automaton (DFA) based
// packetizing mechanism for VLIW architectures. It provides APIs to
// determine whether there exists a legal mapping of instructions to
// functional unit assignments in a packet. The DFA is auto-generated from
// the target's Schedule.td file.
//
// A DFA consists of 3 major elements: states, inputs, and transitions. For
// the packetizing mechanism, the input is the set of instruction classes for
// a target. The state models all possible combinations of functional unit
// consumption for a given set of instructions in a packet. A transition
// models the addition of an instruction to a packet. In the DFA constructed
// by this class, if an instruction can be added to a packet, then a valid
// transition exists from the corresponding state. Invalid transitions
// indicate that the instruction cannot be added to the current packet.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_DFAPACKETIZER_H
#define LLVM_CODEGEN_DFAPACKETIZER_H

#include "llvm/ADT/DenseMap.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/ScheduleDAGMutation.h"
#include <cstdint>
#include <map>
#include <memory>
#include <utility>
#include <vector>

namespace llvm {

class DefaultVLIWScheduler;
class InstrItineraryData;
class MachineFunction;
class MachineInstr;
class MachineLoopInfo;
class MCInstrDesc;
class SUnit;
class TargetInstrInfo;

// --------------------------------------------------------------------
// Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp

// DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput.
// This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer.
//
// e.g. terms x resource bit combinations that fit in uint32_t:
//      4 terms x 8  bits = 32 bits
//      3 terms x 10 bits = 30 bits
//      2 terms x 16 bits = 32 bits
//
// e.g. terms x resource bit combinations that fit in uint64_t:
//      8 terms x 8  bits = 64 bits
//      7 terms x 9  bits = 63 bits
//      6 terms x 10 bits = 60 bits
//      5 terms x 12 bits = 60 bits
//      4 terms x 16 bits = 64 bits <--- current
//      3 terms x 21 bits = 63 bits
//      2 terms x 32 bits = 64 bits
//
#define DFA_MAX_RESTERMS        4   // The max # of AND'ed resource terms.
#define DFA_MAX_RESOURCES       16  // The max # of resource bits in one term.

using DFAInput = uint64_t;
using DFAStateInput = int64_t;

#define DFA_TBLTYPE             "int64_t" // For generating DFAStateInputTable.
// --------------------------------------------------------------------

class DFAPacketizer {
private:
  using UnsignPair = std::pair<unsigned, DFAInput>;

  const InstrItineraryData *InstrItins;
  int CurrentState = 0;
  const DFAStateInput (*DFAStateInputTable)[2];
  const unsigned *DFAStateEntryTable;

  // CachedTable is a map from <FromState, Input> to ToState.
  DenseMap<UnsignPair, unsigned> CachedTable;

  // Read the DFA transition table and update CachedTable.
  void ReadTable(unsigned state);

public:
  DFAPacketizer(const InstrItineraryData *I, const DFAStateInput (*SIT)[2],
                const unsigned *SET);

  // Reset the current state to make all resources available.
  void clearResources() {
    CurrentState = 0;
  }

  // Return the DFAInput for an instruction class.
  DFAInput getInsnInput(unsigned InsnClass);

  // Return the DFAInput for an instruction class input vector.
  static DFAInput getInsnInput(const std::vector<unsigned> &InsnClass);

  // Check if the resources occupied by a MCInstrDesc are available in
  // the current state.
  bool canReserveResources(const MCInstrDesc *MID);

  // Reserve the resources occupied by a MCInstrDesc and change the current
  // state to reflect that change.
  void reserveResources(const MCInstrDesc *MID);

  // Check if the resources occupied by a machine instruction are available
  // in the current state.
  bool canReserveResources(MachineInstr &MI);

  // Reserve the resources occupied by a machine instruction and change the
  // current state to reflect that change.
  void reserveResources(MachineInstr &MI);

  const InstrItineraryData *getInstrItins() const { return InstrItins; }
};

// VLIWPacketizerList implements a simple VLIW packetizer using DFA. The
// packetizer works on machine basic blocks. For each instruction I in BB,
// the packetizer consults the DFA to see if machine resources are available
// to execute I. If so, the packetizer checks if I depends on any instruction
// in the current packet. If no dependency is found, I is added to current
// packet and the machine resource is marked as taken. If any dependency is
// found, a target API call is made to prune the dependence.
class VLIWPacketizerList {
protected:
  MachineFunction &MF;
  const TargetInstrInfo *TII;
  AliasAnalysis *AA;

  // The VLIW Scheduler.
  DefaultVLIWScheduler *VLIWScheduler;
  // Vector of instructions assigned to the current packet.
  std::vector<MachineInstr*> CurrentPacketMIs;
  // DFA resource tracker.
  DFAPacketizer *ResourceTracker;
  // Map: MI -> SU.
  std::map<MachineInstr*, SUnit*> MIToSUnit;

public:
  // The AliasAnalysis parameter can be nullptr.
  VLIWPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI,
                     AliasAnalysis *AA);

  virtual ~VLIWPacketizerList();

  // Implement this API in the backend to bundle instructions.
  void PacketizeMIs(MachineBasicBlock *MBB,
                    MachineBasicBlock::iterator BeginItr,
                    MachineBasicBlock::iterator EndItr);

  // Return the ResourceTracker.
  DFAPacketizer *getResourceTracker() {return ResourceTracker;}

  // addToPacket - Add MI to the current packet.
  virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI) {
    CurrentPacketMIs.push_back(&MI);
    ResourceTracker->reserveResources(MI);
    return MI;
  }

  // End the current packet and reset the state of the packetizer.
  // Overriding this function allows the target-specific packetizer
  // to perform custom finalization.
  virtual void endPacket(MachineBasicBlock *MBB,
                         MachineBasicBlock::iterator MI);

  // Perform initialization before packetizing an instruction. This
  // function is supposed to be overrided by the target dependent packetizer.
  virtual void initPacketizerState() {}

  // Check if the given instruction I should be ignored by the packetizer.
  virtual bool ignorePseudoInstruction(const MachineInstr &I,
                                       const MachineBasicBlock *MBB) {
    return false;
  }

  // Return true if instruction MI can not be packetized with any other
  // instruction, which means that MI itself is a packet.
  virtual bool isSoloInstruction(const MachineInstr &MI) { return true; }

  // Check if the packetizer should try to add the given instruction to
  // the current packet. One reasons for which it may not be desirable
  // to include an instruction in the current packet could be that it
  // would cause a stall.
  // If this function returns "false", the current packet will be ended,
  // and the instruction will be added to the next packet.
  virtual bool shouldAddToPacket(const MachineInstr &MI) { return true; }

  // Check if it is legal to packetize SUI and SUJ together.
  virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) {
    return false;
  }

  // Check if it is legal to prune dependece between SUI and SUJ.
  virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) {
    return false;
  }

  // Add a DAG mutation to be done before the packetization begins.
  void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation);
};

} // end namespace llvm

#endif // LLVM_CODEGEN_DFAPACKETIZER_H