OpenASIP 2.2
Loading...
Searching...
No Matches
DataDependenceGraphBuilder.hh
Go to the documentation of this file.
1/*
2 Copyright (c) 2002-2011 Tampere University.
3
4 This file is part of TTA-Based Codesign Environment (TCE).
5
6 Permission is hereby granted, free of charge, to any person obtaining a
7 copy of this software and associated documentation files (the "Software"),
8 to deal in the Software without restriction, including without limitation
9 the rights to use, copy, modify, merge, publish, distribute, sublicense,
10 and/or sell copies of the Software, and to permit persons to whom the
11 Software is furnished to do so, subject to the following conditions:
12
13 The above copyright notice and this permission notice shall be included in
14 all copies or substantial portions of the Software.
15
16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22 DEALINGS IN THE SOFTWARE.
23 */
24/**
25 * @file DataDependenceGraphBuilder.hh
26 *
27 * Declaration of data dependence graph builder class
28 *
29 * @author Heikki Kultala 2006-2009 (heikki.kultala-no.spam-tut.fi)
30 * @author Pekka Jääskeläinen 2011
31 * @note rating: red
32 */
33
34#ifndef TTA_DDG_BUILDER_HH
35#define TTA_DDG_BUILDER_HH
36
38#include "ControlFlowGraph.hh"
40#include "TCEString.hh"
41#include "MoveNodeUse.hh"
42#include "LiveRangeData.hh"
43
44namespace llvm {
45 class AAResults;
46 typedef AAResults AliasAnalysis;
47}
48
49namespace TTAProgram {
50 class Program;
51 class TerminalRegister;
52 class CodeSnippet;
53 class Instruction;
54 class Move;
55 class BasicBlock;
56}
57
58namespace TTAMachine {
59 class Machine;
60}
61
63class InterPassData;
64
65
66/**
67 * DataDependenceGraphBuilder class is responsible for building data
68 * dependence graphs.
69 */
71public:
74
76
78
80 ControlFlowGraph& cGraph,
82 const TTAMachine::Machine& mach,
83 const UniversalMachine* um = NULL,
84 bool createMemAndFUDeps = true,
85 bool createDeathInformation = true,
86 llvm::AliasAnalysis* AA = NULL);
90 const TTAMachine::Machine& mach,
91 const TCEString& ddgname = "small bb",
92 const UniversalMachine* um = NULL,
93 bool createMemAndFUDeps = true,
94 llvm::AliasAnalysis* AA = NULL);
95
96protected:
97
98 bool isTriggering(const MoveNode& mn);
99
100 std::set<TCEString> allParamRegs_;
101
104
110
111 typedef std::map<int, TCEString> SpecialRegisters;
112 typedef std::vector<MemoryAliasAnalyzer*> AliasAnalyzerVector;
113
114 enum BBState {
115 BB_UNREACHED = 0, /// Basic block we have not yet encountered.
116 BB_QUEUED, /// BB which is queued to be processed
117 BB_READY, ///BB which is already processed and is not queued.
119
123 /**
124 * This class stores all the basic-block related information needed by
125 * the data dependency graph creator.
126 */
127 struct BBData {
128
130 virtual ~BBData();
131 /// ProgramOperations lacking operands
133 /// ProgramOperations lacking result read
136 /// State of the BB.
138 /// Whether the BB has been constructed or not.
141 };
142
143 typedef std::map <BasicBlockNode*, BBData*> BBDataMap;
144 typedef std::list<BBData*> BBDataList;
145
147 BBData& bbd,
148 bool firstTime);
149
151
153
156 void createRegisterDeps();
157 void initializeBBStates();
159
163 bool aliveInformationNeeded = true);
164
165 void iterateBBs(
166 ConstructionPhase phase);
169
171 BBData& bbd,
172 bool queueAll,
173 ConstructionPhase phase);
175 const MoveNodeUseMapSet& srcMap,
176 MoveNodeUseMapSet& dstMap,
177 bool addLoopProperty);
179 TTAProgram::BasicBlock& processedBB,
180 BasicBlockNode& successor,
181 bool queueAll,
182 bool loop,
183 ConstructionPhase phase);
184 void updateBB(
185 BBData& bbd,
186 ConstructionPhase phase);
187
191 void constructBB(BasicBlockNodeSet& inputBlocks);
192
194 void processGuard(MoveNode& moveNode);
195 void processSource(MoveNode& moveNode);
196 void processResultRead(MoveNode& moveNode);
197 void processCall(MoveNode& mn);
198 void processReturn(MoveNode& moveNode);
199 void processEntryNode(MoveNode& mn);
201 class MoveNode& moveNode,
202 ConstructionPhase phase);
203 void processRegUse(
204 MoveNodeUse mn,
205 const TCEString& reg);
206
207 void updateMemUse(
208 MoveNodeUse mnd,
209 const TCEString& category);
210
211 void processRegWrite(
212 MoveNodeUse mn,
213 const TCEString& reg);
214 void updateMemWrite(
215 MoveNodeUse mnd,
216 const TCEString& category);
217
218 void processTriggerPO(class MoveNode& moveNode, Operation& dop);
220 MoveNode& moveNode,
221 Operation &dop);
223 MoveNode& moveNode,
224 Operation &dop);
226 class MoveNode& moveNode,
227 class Operation& dop);
228
230 MoveNodeUseSet& prevMoves,
231 const MoveNode& mn,
232 Operation& dop);
233
235 void processMemUse(MoveNodeUse mnd);
236
237 void processOperand(
238 class MoveNode& moveNode,
239 Operation &dop);
240
242 const ProgramOperation& pop1,
243 const ProgramOperation& pop2,
245
246 bool isAddressTraceable(const ProgramOperation& pop);
248
250 MoveNodeUse prev,
251 MoveNodeUse mnd,
254 MoveNodeUse& mnd,
255 std::set<MoveNodeUse>& prevNodes,
257 bool traceable);
259 MoveNodeUse& mnd,
260 std::set<MoveNodeUse>& defines);
261
262 std::set<MoveNodeUse> earlierWritesWithSameGuard(
263 MoveNodeUse& mnd, std::set<MoveNodeUse>& defines);
264
266 MoveNodeUse& mnd, std::set<MoveNodeUse>& defines);
267
269 const TCEString& reg,
270 MoveNodeUse& mnd,
271 MoveNodeUseSet& predecessorNodes,
273 bool guardedKillFound);
274
275 // functions related to iterating over basic blocks
276
277 void changeState(
278 BBData& bbd,
279 BBState newState,
280 bool priorize = false);
281
282 bool isAlwaysDifferentFU(const MoveNode* srcMN, const MoveNode* dstMN);
283
284 // related to mem operation addresses
285// MoveNode* addressMove(const MoveNode&mn);
286
287 /// find special register data from old frontend code
290 std::map<int,TCEString>& registers);
291
293 ControlFlowGraph& cfg,
294 std::map<int,TCEString>& registers);
295
298 std::map<int,TCEString>& registers);
299
301 const UniversalMachine& um,
302 std::map<int,TCEString>& registers);
303
307 bool setLoopProperty);
308
310
316 /// contains stack pointer, RV and parameter registers.
318 static const TCEString RA_NAME;
323};
324
325#endif
std::shared_ptr< ProgramOperation > ProgramOperationPtr
Definition MoveNode.hh:53
LiveRangeData::MoveNodeUseSet MoveNodeUseSet
void checkAndCreateMemAntideps(MoveNodeUse &mnd, std::set< MoveNodeUse > &prevNodes, DataDependenceEdge::DependenceType depType, bool traceable)
void constructIndividualBB(ConstructionPhase phase)
void findStaticRegisters(TTAProgram::CodeSnippet &cs, std::map< int, TCEString > &registers)
find special register data from old frontend code
std::map< int, TCEString > SpecialRegisters
void createRegisterAntideps(const TCEString &reg, MoveNodeUse &mnd, MoveNodeUseSet &predecessorNodes, DataDependenceEdge::DependenceType depType, bool guardedKillFound)
void appendMoveNodeUse(const LiveRangeData::MoveNodeUseSet &src, LiveRangeData::MoveNodeUseSet &dst, bool setLoopProperty)
void updateBB(BBData &bbd, ConstructionPhase phase)
bool hasEarlierWriteWithSameGuard(MoveNodeUse &mnd, std::set< MoveNodeUse > &defines)
void processOperand(class MoveNode &moveNode, Operation &dop)
void processTriggerMemoryAndFUStates(MoveNode &moveNode, Operation &dop)
void constructIndividualFromInlineAsmBB(ConstructionPhase phase)
void createSideEffectEdges(MoveNodeUseSet &prevMoves, const MoveNode &mn, Operation &dop)
std::set< MoveNodeUse > earlierWritesWithSameGuard(MoveNodeUse &mnd, std::set< MoveNodeUse > &defines)
void updatePreceedingRegistersUsedAfter(BBData &bbd, bool firstTime)
bool isAddressTraceable(const ProgramOperation &pop)
void setSucceedingPredeps(BBData &bbd, bool queueAll, ConstructionPhase phase)
ControlFlowGraph::NodeSet BasicBlockNodeSet
@ BB_STATES
BB which is already processed and is not queued.
@ BB_QUEUED
Basic block we have not yet encountered.
@ BB_READY
BB which is queued to be processed.
void iterateBBs(ConstructionPhase phase)
bool hasEarlierMemWriteToSameAddressWithSameGuard(MoveNodeUse &mnd, std::set< MoveNodeUse > &defines)
DataDependenceGraph::NodeSet MNodeSet
LiveRangeData::MoveNodeUseMap MoveNodeUseMap
void processTriggerRegistersAndOperations(MoveNode &moveNode, Operation &dop)
SpecialRegisters specialRegisters_
contains stack pointer, RV and parameter registers.
void processRegUse(MoveNodeUse mn, const TCEString &reg)
const TTAMachine::Machine * mach_
std::map< BasicBlockNode *, BBData * > BBDataMap
void processResultRead(MoveNode &moveNode)
void updateMemUse(MoveNodeUse mnd, const TCEString &category)
void constructBB(BasicBlockNodeSet &inputBlocks)
void setSucceedingPredepsForBB(TTAProgram::BasicBlock &processedBB, BasicBlockNode &successor, bool queueAll, bool loop, ConstructionPhase phase)
bool checkAndCreateMemDep(MoveNodeUse prev, MoveNodeUse mnd, DataDependenceEdge::DependenceType depType)
void createTriggerDependencies(class MoveNode &moveNode, class Operation &dop)
void processTriggerPO(class MoveNode &moveNode, Operation &dop)
MemoryAliasAnalyzer::AliasingResult analyzeMemoryAlias(const ProgramOperation &pop1, const ProgramOperation &pop2, MoveNodeUse::BBRelation bbInfo)
void processDestination(class MoveNode &moveNode, ConstructionPhase phase)
LiveRangeData::MoveNodeUseSetPair MoveNodeUseSetPair
void changeState(BBData &bbd, BBState newState, bool priorize=false)
void addAliasAnalyzer(MemoryAliasAnalyzer *analyzer)
void processRegWrite(MoveNodeUse mn, const TCEString &reg)
void updateMemWrite(MoveNodeUse mnd, const TCEString &category)
std::vector< MemoryAliasAnalyzer * > AliasAnalyzerVector
bool appendUseMapSets(const MoveNodeUseMapSet &srcMap, MoveNodeUseMapSet &dstMap, bool addLoopProperty)
LiveRangeData::MoveNodeUsePair MoveNodeUsePair
void createOperationEdges(ProgramOperationPtr po)
virtual DataDependenceGraph * build(ControlFlowGraph &cGraph, DataDependenceGraph::AntidependenceLevel antidependenceLevel, const TTAMachine::Machine &mach, const UniversalMachine *um=NULL, bool createMemAndFUDeps=true, bool createDeathInformation=true, llvm::AliasAnalysis *AA=NULL)
bool isAlwaysDifferentFU(const MoveNode *srcMN, const MoveNode *dstMN)
TCEString memoryCategory(const MoveNodeUse &mnd)
LiveRangeData::MoveNodeUseMapSet MoveNodeUseMapSet
std::set< GraphNode *, typename GraphNode::Comparator > NodeSet
Definition Graph.hh:53
AAResults AliasAnalysis
ProgramOperationPtr readPending_
ProgramOperations lacking result read.
bool constructed_
Whether the BB has been constructed or not.
ProgramOperationPtr destPending_
ProgramOperations lacking operands.
std::pair< TCEString, MoveNodeUse > MoveNodeUsePair
std::map< TCEString, MoveNodeUse > MoveNodeUseMap
std::set< MoveNodeUse > MoveNodeUseSet
std::pair< TCEString, MoveNodeUseSet > MoveNodeUseSetPair
std::map< TCEString, MoveNodeUseSet > MoveNodeUseMapSet