LCOV - code coverage report
Current view: top level - include/llvm/CodeGen - DFAPacketizer.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 7 19 36.8 %
Date: 2018-10-20 13:21:21 Functions: 2 10 20.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- llvm/CodeGen/DFAPacketizer.h - DFA Packetizer for VLIW ---*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : // This class implements a deterministic finite automaton (DFA) based
      10             : // packetizing mechanism for VLIW architectures. It provides APIs to
      11             : // determine whether there exists a legal mapping of instructions to
      12             : // functional unit assignments in a packet. The DFA is auto-generated from
      13             : // the target's Schedule.td file.
      14             : //
      15             : // A DFA consists of 3 major elements: states, inputs, and transitions. For
      16             : // the packetizing mechanism, the input is the set of instruction classes for
      17             : // a target. The state models all possible combinations of functional unit
      18             : // consumption for a given set of instructions in a packet. A transition
      19             : // models the addition of an instruction to a packet. In the DFA constructed
      20             : // by this class, if an instruction can be added to a packet, then a valid
      21             : // transition exists from the corresponding state. Invalid transitions
      22             : // indicate that the instruction cannot be added to the current packet.
      23             : //
      24             : //===----------------------------------------------------------------------===//
      25             : 
      26             : #ifndef LLVM_CODEGEN_DFAPACKETIZER_H
      27             : #define LLVM_CODEGEN_DFAPACKETIZER_H
      28             : 
      29             : #include "llvm/ADT/DenseMap.h"
      30             : #include "llvm/CodeGen/MachineBasicBlock.h"
      31             : #include "llvm/CodeGen/ScheduleDAGMutation.h"
      32             : #include <cstdint>
      33             : #include <map>
      34             : #include <memory>
      35             : #include <utility>
      36             : #include <vector>
      37             : 
      38             : namespace llvm {
      39             : 
      40             : class DefaultVLIWScheduler;
      41             : class InstrItineraryData;
      42             : class MachineFunction;
      43             : class MachineInstr;
      44             : class MachineLoopInfo;
      45             : class MCInstrDesc;
      46             : class SUnit;
      47             : class TargetInstrInfo;
      48             : 
      49             : // --------------------------------------------------------------------
      50             : // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp
      51             : 
      52             : // DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput.
      53             : // This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer.
      54             : //
      55             : // e.g. terms x resource bit combinations that fit in uint32_t:
      56             : //      4 terms x 8  bits = 32 bits
      57             : //      3 terms x 10 bits = 30 bits
      58             : //      2 terms x 16 bits = 32 bits
      59             : //
      60             : // e.g. terms x resource bit combinations that fit in uint64_t:
      61             : //      8 terms x 8  bits = 64 bits
      62             : //      7 terms x 9  bits = 63 bits
      63             : //      6 terms x 10 bits = 60 bits
      64             : //      5 terms x 12 bits = 60 bits
      65             : //      4 terms x 16 bits = 64 bits <--- current
      66             : //      3 terms x 21 bits = 63 bits
      67             : //      2 terms x 32 bits = 64 bits
      68             : //
      69             : #define DFA_MAX_RESTERMS        4   // The max # of AND'ed resource terms.
      70             : #define DFA_MAX_RESOURCES       16  // The max # of resource bits in one term.
      71             : 
      72             : using DFAInput = uint64_t;
      73             : using DFAStateInput = int64_t;
      74             : 
      75             : #define DFA_TBLTYPE             "int64_t" // For generating DFAStateInputTable.
      76             : // --------------------------------------------------------------------
      77             : 
      78       20988 : class DFAPacketizer {
      79             : private:
      80             :   using UnsignPair = std::pair<unsigned, DFAInput>;
      81             : 
      82             :   const InstrItineraryData *InstrItins;
      83             :   int CurrentState = 0;
      84             :   const DFAStateInput (*DFAStateInputTable)[2];
      85             :   const unsigned *DFAStateEntryTable;
      86             : 
      87             :   // CachedTable is a map from <FromState, Input> to ToState.
      88             :   DenseMap<UnsignPair, unsigned> CachedTable;
      89             : 
      90             :   // Read the DFA transition table and update CachedTable.
      91             :   void ReadTable(unsigned state);
      92             : 
      93             : public:
      94             :   DFAPacketizer(const InstrItineraryData *I, const DFAStateInput (*SIT)[2],
      95             :                 const unsigned *SET);
      96             : 
      97             :   // Reset the current state to make all resources available.
      98           0 :   void clearResources() {
      99      104344 :     CurrentState = 0;
     100           0 :   }
     101             : 
     102             :   // Return the DFAInput for an instruction class.
     103             :   DFAInput getInsnInput(unsigned InsnClass);
     104             : 
     105             :   // Return the DFAInput for an instruction class input vector.
     106             :   static DFAInput getInsnInput(const std::vector<unsigned> &InsnClass);
     107             : 
     108             :   // Check if the resources occupied by a MCInstrDesc are available in
     109             :   // the current state.
     110             :   bool canReserveResources(const MCInstrDesc *MID);
     111             : 
     112             :   // Reserve the resources occupied by a MCInstrDesc and change the current
     113             :   // state to reflect that change.
     114             :   void reserveResources(const MCInstrDesc *MID);
     115             : 
     116             :   // Check if the resources occupied by a machine instruction are available
     117             :   // in the current state.
     118             :   bool canReserveResources(MachineInstr &MI);
     119             : 
     120             :   // Reserve the resources occupied by a machine instruction and change the
     121             :   // current state to reflect that change.
     122             :   void reserveResources(MachineInstr &MI);
     123             : 
     124           0 :   const InstrItineraryData *getInstrItins() const { return InstrItins; }
     125             : };
     126             : 
     127             : // VLIWPacketizerList implements a simple VLIW packetizer using DFA. The
     128             : // packetizer works on machine basic blocks. For each instruction I in BB,
     129             : // the packetizer consults the DFA to see if machine resources are available
     130             : // to execute I. If so, the packetizer checks if I depends on any instruction
     131             : // in the current packet. If no dependency is found, I is added to current
     132             : // packet and the machine resource is marked as taken. If any dependency is
     133             : // found, a target API call is made to prune the dependence.
     134             : class VLIWPacketizerList {
     135             : protected:
     136             :   MachineFunction &MF;
     137             :   const TargetInstrInfo *TII;
     138             :   AliasAnalysis *AA;
     139             : 
     140             :   // The VLIW Scheduler.
     141             :   DefaultVLIWScheduler *VLIWScheduler;
     142             :   // Vector of instructions assigned to the current packet.
     143             :   std::vector<MachineInstr*> CurrentPacketMIs;
     144             :   // DFA resource tracker.
     145             :   DFAPacketizer *ResourceTracker;
     146             :   // Map: MI -> SU.
     147             :   std::map<MachineInstr*, SUnit*> MIToSUnit;
     148             : 
     149             : public:
     150             :   // The AliasAnalysis parameter can be nullptr.
     151             :   VLIWPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI,
     152             :                      AliasAnalysis *AA);
     153             : 
     154             :   virtual ~VLIWPacketizerList();
     155             : 
     156             :   // Implement this API in the backend to bundle instructions.
     157             :   void PacketizeMIs(MachineBasicBlock *MBB,
     158             :                     MachineBasicBlock::iterator BeginItr,
     159             :                     MachineBasicBlock::iterator EndItr);
     160             : 
     161             :   // Return the ResourceTracker.
     162           0 :   DFAPacketizer *getResourceTracker() {return ResourceTracker;}
     163             : 
     164             :   // addToPacket - Add MI to the current packet.
     165       46385 :   virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI) {
     166       46385 :     CurrentPacketMIs.push_back(&MI);
     167       46385 :     ResourceTracker->reserveResources(MI);
     168       46385 :     return MI;
     169             :   }
     170             : 
     171             :   // End the current packet and reset the state of the packetizer.
     172             :   // Overriding this function allows the target-specific packetizer
     173             :   // to perform custom finalization.
     174             :   virtual void endPacket(MachineBasicBlock *MBB,
     175             :                          MachineBasicBlock::iterator MI);
     176             : 
     177             :   // Perform initialization before packetizing an instruction. This
     178             :   // function is supposed to be overrided by the target dependent packetizer.
     179           0 :   virtual void initPacketizerState() {}
     180             : 
     181             :   // Check if the given instruction I should be ignored by the packetizer.
     182           0 :   virtual bool ignorePseudoInstruction(const MachineInstr &I,
     183             :                                        const MachineBasicBlock *MBB) {
     184           0 :     return false;
     185             :   }
     186             : 
     187             :   // Return true if instruction MI can not be packetized with any other
     188             :   // instruction, which means that MI itself is a packet.
     189           0 :   virtual bool isSoloInstruction(const MachineInstr &MI) { return true; }
     190             : 
     191             :   // Check if the packetizer should try to add the given instruction to
     192             :   // the current packet. One reasons for which it may not be desirable
     193             :   // to include an instruction in the current packet could be that it
     194             :   // would cause a stall.
     195             :   // If this function returns "false", the current packet will be ended,
     196             :   // and the instruction will be added to the next packet.
     197       46210 :   virtual bool shouldAddToPacket(const MachineInstr &MI) { return true; }
     198             : 
     199             :   // Check if it is legal to packetize SUI and SUJ together.
     200           0 :   virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) {
     201           0 :     return false;
     202             :   }
     203             : 
     204             :   // Check if it is legal to prune dependece between SUI and SUJ.
     205           0 :   virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) {
     206           0 :     return false;
     207             :   }
     208             : 
     209             :   // Add a DAG mutation to be done before the packetization begins.
     210             :   void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation);
     211             : 
     212             :   bool alias(const MachineInstr &MI1, const MachineInstr &MI2,
     213             :              bool UseTBAA = true) const;
     214             : 
     215             : private:
     216             :   bool alias(const MachineMemOperand &Op1, const MachineMemOperand &Op2,
     217             :              bool UseTBAA = true) const;
     218             : };
     219             : 
     220             : } // end namespace llvm
     221             : 
     222             : #endif // LLVM_CODEGEN_DFAPACKETIZER_H

Generated by: LCOV version 1.13