DFAPacketizer.cpp revision 464f3a332f81364ee09794f9502f0b25671149c6 
1//=- llvm/CodeGen/DFAPacketizer.cpp - 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#include "llvm/CodeGen/DFAPacketizer.h"
27#include "llvm/CodeGen/MachineInstr.h"
28#include "llvm/MC/MCInstrItineraries.h"
29using namespace llvm;
30
31DFAPacketizer::DFAPacketizer(const InstrItineraryData *I, const int (*SIT)[2],
32                             const unsigned *SET):
33  InstrItins(I), CurrentState(0), DFAStateInputTable(SIT),
34  DFAStateEntryTable(SET) {}
35
36
37//
38// ReadTable - Read the DFA transition table and update CachedTable.
39//
40// Format of the transition tables:
41// DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid
42//                           transitions
43// DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable
44//                         for the ith state
45//
46void DFAPacketizer::ReadTable(unsigned int state) {
47  unsigned ThisState = DFAStateEntryTable[state];
48  unsigned NextStateInTable = DFAStateEntryTable[state+1];
49  // Early exit in case CachedTable has already contains this
50  // state's transitions.
51  if (CachedTable.count(UnsignPair(state,
52                                   DFAStateInputTable[ThisState][0])))
53    return;
54
55  for (unsigned i = ThisState; i < NextStateInTable; i++)
56    CachedTable[UnsignPair(state, DFAStateInputTable[i][0])] =
57      DFAStateInputTable[i][1];
58}
59
60
61// canReserveResources - Check if the resources occupied by a MCInstrDesc
62// are available in the current state.
63bool DFAPacketizer::canReserveResources(const llvm::MCInstrDesc *MID) {
64  unsigned InsnClass = MID->getSchedClass();
65  const llvm::InstrStage *IS = InstrItins->beginStage(InsnClass);
66  unsigned FuncUnits = IS->getUnits();
67  UnsignPair StateTrans = UnsignPair(CurrentState, FuncUnits);
68  ReadTable(CurrentState);
69  return (CachedTable.count(StateTrans) != 0);
70}
71
72
73// reserveResources - Reserve the resources occupied by a MCInstrDesc and
74// change the current state to reflect that change.
75void DFAPacketizer::reserveResources(const llvm::MCInstrDesc *MID) {
76  unsigned InsnClass = MID->getSchedClass();
77  const llvm::InstrStage *IS = InstrItins->beginStage(InsnClass);
78  unsigned FuncUnits = IS->getUnits();
79  UnsignPair StateTrans = UnsignPair(CurrentState, FuncUnits);
80  ReadTable(CurrentState);
81  assert(CachedTable.count(StateTrans) != 0);
82  CurrentState = CachedTable[StateTrans];
83}
84
85
86// canReserveResources - Check if the resources occupied by a machine
87// instruction are available in the current state.
88bool DFAPacketizer::canReserveResources(llvm::MachineInstr *MI) {
89  const llvm::MCInstrDesc &MID = MI->getDesc();
90  return canReserveResources(&MID);
91}
92
93// reserveResources - Reserve the resources occupied by a machine
94// instruction and change the current state to reflect that change.
95void DFAPacketizer::reserveResources(llvm::MachineInstr *MI) {
96  const llvm::MCInstrDesc &MID = MI->getDesc();
97  reserveResources(&MID);
98}
99