From dc81e5da271ed394e2029c83458773c4ae2fc5f4 Mon Sep 17 00:00:00 2001 From: Anshuman Dasgupta Date: Thu, 1 Dec 2011 21:10:21 +0000 Subject: Add a deterministic finite automaton based packetizer for VLIW architectures git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145629 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/DFAPacketizer.cpp | 98 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 98 insertions(+) create mode 100644 lib/CodeGen/DFAPacketizer.cpp (limited to 'lib/CodeGen/DFAPacketizer.cpp') diff --git a/lib/CodeGen/DFAPacketizer.cpp b/lib/CodeGen/DFAPacketizer.cpp new file mode 100644 index 0000000..f80f160 --- /dev/null +++ b/lib/CodeGen/DFAPacketizer.cpp @@ -0,0 +1,98 @@ +//=- llvm/CodeGen/DFAPacketizer.cpp - 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. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/DFAPacketizer.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/MC/MCInstrItineraries.h" +using namespace llvm; + +DFAPacketizer::DFAPacketizer(const InstrItineraryData *I, const int (*SIT)[2], + const unsigned* SET): + InstrItins(I), CurrentState(0), DFAStateInputTable(SIT), + DFAStateEntryTable(SET) {} + + +// +// ReadTable - Read the DFA transition table and update CachedTable +// +// Format of the transition tables: +// DFAStateInputTable[][2] = pairs of for all valid +// transitions +// DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable +// for the ith state +// +void DFAPacketizer::ReadTable(unsigned int state) { + unsigned ThisState = DFAStateEntryTable[state]; + unsigned NextStateInTable = DFAStateEntryTable[state+1]; + // Early exit in case CachedTable has already contains this + // state's transitions + if (CachedTable.count(UnsignPair(state, + DFAStateInputTable[ThisState][0]))) + return; + + for (unsigned i = ThisState; i < NextStateInTable; i++) + CachedTable[UnsignPair(state, DFAStateInputTable[i][0])] = + DFAStateInputTable[i][1]; +} + + +// canReserveResources - Check if the resources occupied by a MCInstrDesc +// are available in the current state +bool DFAPacketizer::canReserveResources(const llvm::MCInstrDesc* MID) { + unsigned InsnClass = MID->getSchedClass(); + const llvm::InstrStage* IS = InstrItins->beginStage(InsnClass); + unsigned FuncUnits = IS->getUnits(); + UnsignPair StateTrans = UnsignPair(CurrentState, FuncUnits); + ReadTable(CurrentState); + return (CachedTable.count(StateTrans) != 0); +} + + +// reserveResources - Reserve the resources occupied by a MCInstrDesc and +// change the current state to reflect that change +void DFAPacketizer::reserveResources(const llvm::MCInstrDesc* MID) { + unsigned InsnClass = MID->getSchedClass(); + const llvm::InstrStage* IS = InstrItins->beginStage(InsnClass); + unsigned FuncUnits = IS->getUnits(); + UnsignPair StateTrans = UnsignPair(CurrentState, FuncUnits); + ReadTable(CurrentState); + assert(CachedTable.count(StateTrans) != 0); + CurrentState = CachedTable[StateTrans]; +} + + +// canReserveResources - Check if the resources occupied by a machine +// instruction are available in the current state +bool DFAPacketizer::canReserveResources(llvm::MachineInstr* MI) { + const llvm::MCInstrDesc& MID = MI->getDesc(); + return canReserveResources(&MID); +} + +// reserveResources - Reserve the resources occupied by a machine +// instruction and change the current state to reflect that change +void DFAPacketizer::reserveResources(llvm::MachineInstr* MI) { + const llvm::MCInstrDesc& MID = MI->getDesc(); + reserveResources(&MID); +} -- cgit v1.1 From f6f77e90a18142e196cbc2a6ee87cdf7461b17df Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Tue, 6 Dec 2011 17:34:11 +0000 Subject: add missing point at the end of sentences git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145943 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/DFAPacketizer.cpp | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'lib/CodeGen/DFAPacketizer.cpp') diff --git a/lib/CodeGen/DFAPacketizer.cpp b/lib/CodeGen/DFAPacketizer.cpp index f80f160..c0e505f 100644 --- a/lib/CodeGen/DFAPacketizer.cpp +++ b/lib/CodeGen/DFAPacketizer.cpp @@ -35,7 +35,7 @@ DFAPacketizer::DFAPacketizer(const InstrItineraryData *I, const int (*SIT)[2], // -// ReadTable - Read the DFA transition table and update CachedTable +// ReadTable - Read the DFA transition table and update CachedTable. // // Format of the transition tables: // DFAStateInputTable[][2] = pairs of for all valid @@ -47,7 +47,7 @@ void DFAPacketizer::ReadTable(unsigned int state) { unsigned ThisState = DFAStateEntryTable[state]; unsigned NextStateInTable = DFAStateEntryTable[state+1]; // Early exit in case CachedTable has already contains this - // state's transitions + // state's transitions. if (CachedTable.count(UnsignPair(state, DFAStateInputTable[ThisState][0]))) return; @@ -59,7 +59,7 @@ void DFAPacketizer::ReadTable(unsigned int state) { // canReserveResources - Check if the resources occupied by a MCInstrDesc -// are available in the current state +// are available in the current state. bool DFAPacketizer::canReserveResources(const llvm::MCInstrDesc* MID) { unsigned InsnClass = MID->getSchedClass(); const llvm::InstrStage* IS = InstrItins->beginStage(InsnClass); @@ -71,7 +71,7 @@ bool DFAPacketizer::canReserveResources(const llvm::MCInstrDesc* MID) { // reserveResources - Reserve the resources occupied by a MCInstrDesc and -// change the current state to reflect that change +// change the current state to reflect that change. void DFAPacketizer::reserveResources(const llvm::MCInstrDesc* MID) { unsigned InsnClass = MID->getSchedClass(); const llvm::InstrStage* IS = InstrItins->beginStage(InsnClass); @@ -84,14 +84,14 @@ void DFAPacketizer::reserveResources(const llvm::MCInstrDesc* MID) { // canReserveResources - Check if the resources occupied by a machine -// instruction are available in the current state +// instruction are available in the current state. bool DFAPacketizer::canReserveResources(llvm::MachineInstr* MI) { const llvm::MCInstrDesc& MID = MI->getDesc(); return canReserveResources(&MID); } // reserveResources - Reserve the resources occupied by a machine -// instruction and change the current state to reflect that change +// instruction and change the current state to reflect that change. void DFAPacketizer::reserveResources(llvm::MachineInstr* MI) { const llvm::MCInstrDesc& MID = MI->getDesc(); reserveResources(&MID); -- cgit v1.1 From 464f3a332f81364ee09794f9502f0b25671149c6 Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Tue, 6 Dec 2011 17:34:16 +0000 Subject: use space star instead of star space git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145944 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/DFAPacketizer.cpp | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-) (limited to 'lib/CodeGen/DFAPacketizer.cpp') diff --git a/lib/CodeGen/DFAPacketizer.cpp b/lib/CodeGen/DFAPacketizer.cpp index c0e505f..16276bd 100644 --- a/lib/CodeGen/DFAPacketizer.cpp +++ b/lib/CodeGen/DFAPacketizer.cpp @@ -29,7 +29,7 @@ using namespace llvm; DFAPacketizer::DFAPacketizer(const InstrItineraryData *I, const int (*SIT)[2], - const unsigned* SET): + const unsigned *SET): InstrItins(I), CurrentState(0), DFAStateInputTable(SIT), DFAStateEntryTable(SET) {} @@ -60,9 +60,9 @@ void DFAPacketizer::ReadTable(unsigned int state) { // canReserveResources - Check if the resources occupied by a MCInstrDesc // are available in the current state. -bool DFAPacketizer::canReserveResources(const llvm::MCInstrDesc* MID) { +bool DFAPacketizer::canReserveResources(const llvm::MCInstrDesc *MID) { unsigned InsnClass = MID->getSchedClass(); - const llvm::InstrStage* IS = InstrItins->beginStage(InsnClass); + const llvm::InstrStage *IS = InstrItins->beginStage(InsnClass); unsigned FuncUnits = IS->getUnits(); UnsignPair StateTrans = UnsignPair(CurrentState, FuncUnits); ReadTable(CurrentState); @@ -72,9 +72,9 @@ bool DFAPacketizer::canReserveResources(const llvm::MCInstrDesc* MID) { // reserveResources - Reserve the resources occupied by a MCInstrDesc and // change the current state to reflect that change. -void DFAPacketizer::reserveResources(const llvm::MCInstrDesc* MID) { +void DFAPacketizer::reserveResources(const llvm::MCInstrDesc *MID) { unsigned InsnClass = MID->getSchedClass(); - const llvm::InstrStage* IS = InstrItins->beginStage(InsnClass); + const llvm::InstrStage *IS = InstrItins->beginStage(InsnClass); unsigned FuncUnits = IS->getUnits(); UnsignPair StateTrans = UnsignPair(CurrentState, FuncUnits); ReadTable(CurrentState); @@ -85,14 +85,14 @@ void DFAPacketizer::reserveResources(const llvm::MCInstrDesc* MID) { // canReserveResources - Check if the resources occupied by a machine // instruction are available in the current state. -bool DFAPacketizer::canReserveResources(llvm::MachineInstr* MI) { - const llvm::MCInstrDesc& MID = MI->getDesc(); +bool DFAPacketizer::canReserveResources(llvm::MachineInstr *MI) { + const llvm::MCInstrDesc &MID = MI->getDesc(); return canReserveResources(&MID); } // reserveResources - Reserve the resources occupied by a machine // instruction and change the current state to reflect that change. -void DFAPacketizer::reserveResources(llvm::MachineInstr* MI) { - const llvm::MCInstrDesc& MID = MI->getDesc(); +void DFAPacketizer::reserveResources(llvm::MachineInstr *MI) { + const llvm::MCInstrDesc &MID = MI->getDesc(); reserveResources(&MID); } -- cgit v1.1