OpenASIP 2.2
Loading...
Searching...
No Matches
BFMergeAndKeepUser.cc
Go to the documentation of this file.
1/*
2 Copyright (c) 2002-2020 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 BFMergeAndKeepUser.cc
26 *
27 * Definition of scheduler operation which performs a bypass, including the
28 * ddg updates.
29 *
30 * @author Heikki Kultala 2020 (hkultala-no.spam-tuni.fi)
31 * @note rating: red
32 */
33
34#include "BFMergeAndKeepUser.hh"
35#include "BFConnectNodes.hh"
36#include "BFRemoveEdge.hh"
37#include "ProgramOperation.hh"
38#include "DataDependenceEdge.hh"
40#include "Move.hh"
41#include "Terminal.hh"
42#include "MoveNodeDuplicator.hh"
43
45
46bool
48 MoveNode* src, MoveNode* dst, bool loopBypass, bool pre) {
49
50 bool sourceIsRegToItselfCopy = false;
51
52 if (src != nullptr && dst != nullptr &&
53 ddg().rootGraph()->hasNode(*dst) &
54 ddg().rootGraph()->hasNode(*src)) {
55 bool removedRawEdge = false;
56 auto edges = ddg().rootGraph()->connectingEdges(*src, *dst);
57 for (auto e: edges) {
58 if (e->isRAW()) {
59 removedRawEdge = true;
60 runChild(new BFRemoveEdge(sched_, *src, *dst, *e), pre);
61 reg_ = e->data();
62 }
63 }
64 if (!removedRawEdge) {
65 undo();
66 return false;
67 }
68
69 TTAProgram::Move& sm = src->move();
70 sourceIsRegToItselfCopy = sm.source().equals(sm.destination());
71
72 // if we are bypassing from a register-to-register copy, we'll have to
73 // copy incoming raw edges also in rootgraph level to preserve inter-bb
74 // -dependencies.
75 for (int i = 0; i < ddg().rootGraphInDegree(*src); i++) {
76 DataDependenceEdge& edge = ddg().rootGraphInEdge(*src,i);
77
78 // skip antidependencies due bypassed register.. these are no more
80 edge.data() == reg_) {
83 continue;
84 }
85 }
86
87 // do not copy guard use edges - the user already ahs them.
88 // copying them leads to exponential increase in guard ege counts.
89 if (edge.guardUse()) {
90 continue;
91 }
92
93 // copy other edges.
94 MoveNode& source = ddg().rootGraph()->tailNode(edge);
95 DataDependenceEdge* newEdge =
96 new DataDependenceEdge(edge, loopBypass);
97 runChild(new BFConnectNodes(sched_, source, *dst, newEdge), pre);
98 }
99
100 if (src->isSourceVariable() || src->isSourceRA()) {
101 // if bypassing reg-to-reg this copy anti edges resulting from the
102 // read of the other register.
103 for (int i = 0; i < ddg().rootGraphOutDegree(*src); i++) {
104 DataDependenceEdge& edge = ddg().rootGraphOutEdge(*src,i);
108 !edge.tailPseudo()) {
109
110 MoveNode& target = ddg().rootGraph()->headNode(edge);
111
112 if (!(static_cast<DataDependenceGraph*>(ddg().rootGraph()))
113 ->exclusingGuards(*dst, target) &&
114 dst != &target) {
115
116 DataDependenceEdge* newEdge =
117 new DataDependenceEdge(edge, loopBypass);
118 // TODO: loop here!
120 sched_, *dst, target, newEdge), pre);
121 }
122 }
123 }
124 }
125 }
126
127
128 if (dst != nullptr && ddg().rootGraph()->hasNode(*dst)) {
129 // fix WAR antidependencies to WaW
130 for (int i = 0; i < ddg().rootGraphOutDegree(*dst); i++) {
131 DataDependenceEdge& edge = ddg().rootGraphOutEdge(*dst,i);
134 edge.data() == reg_) {
135 // if stupid reg to itself copy, keep to in edges..
136 if (!sourceIsRegToItselfCopy) {
137 runChild(
138 new BFRemoveEdge(
139 sched_, *dst,
140 ddg().rootGraph()->headNode(edge), edge), pre);
141 i--; // don't skip one edge here!
142 }
143 }
144 }
145 }
146 return true;
147}
148
149bool
151
152
153 if (!ddg().mergeAndKeepAllowed(src_, dst_)) {
154 if (!force_) {
155 return false;
156 }
157 }
158
159 bool loopBypass = ddg().isLoopBypass(src_, dst_);
160
161 // Cannot bypass over multiple loop iterations. even with force flag.
162 if (loopBypass) {
163 for (int i = 0; i < ddg().inDegree(src_); i++) {
164 DataDependenceEdge& edge = ddg().inEdge(src_,i);
165 if (!edge.isFalseDep() && edge.isBackEdge()) {
166 return false;
167 }
168 }
169 }
171
172 if (!updateEdges(&src_, &dst_, loopBypass, true)) {
173 return false;
174 }
175
176
177 if (ii() && updatePrologMove_) {
178 MoveNode* prologMove = duplicator().getMoveNode(dst_);
179 if (prologMove != nullptr) {
180 auto prologSrcMove =
181 duplicator().duplicateMoveNode(src_,true, false);
182 duplicatedSrc_ = prologSrcMove.second;
183
186 sched_, *prologSrcMove.first, *prologMove));
187
189 prologSrcMove.first, prologMove, loopBypass, false);
190
191 }
192 }
193 return true;
194
195}
196
198 if (duplicatedSrc_) {
199 duplicator().disposeMoveNode(duplicator().getMoveNode(src_));
200 }
201}
void undoOnlyMe() override
bool updateEdges(MoveNode *src, MoveNode *dst, bool loopBypass, bool pre)
bool operator()() override
unsigned int ii() const
BF2Scheduler & sched_
DataDependenceGraph & ddg()
MoveNodeDuplicator & duplicator() const
BoostGraph * rootGraph()
virtual Node & headNode(const Edge &edge) const
virtual int rootGraphInDegree(const Node &node) const
virtual Edge & inEdge(const Node &node, const int index) const
virtual int rootGraphOutDegree(const Node &node) const
virtual Edge & rootGraphInEdge(const Node &node, const int index) const
virtual Edge & rootGraphOutEdge(const Node &node, const int index) const
virtual int inDegree(const Node &node) const
EdgeSet connectingEdges(const Node &nTail, const Node &nHead) const
virtual Node & tailNode(const Edge &edge) const
DependenceType dependenceType() const
EdgeReason edgeReason() const
const TCEString data() const
bool isLoopBypass(MoveNode &sourceNode, MoveNode &userNode)
MoveNode * getMoveNode(MoveNode &mn)
void disposeMoveNode(MoveNode *newMN)
std::pair< MoveNode *, bool > duplicateMoveNode(MoveNode &mn, bool addToDDG, bool ignoreSameBBBackEdges)
bool isSourceVariable() const
Definition MoveNode.cc:196
TTAProgram::Move & move()
bool isSourceRA() const
Definition MoveNode.cc:210
bool runPostChild(Reversible *preChild)
virtual void undo()
Definition Reversible.cc:69
bool runChild(std::stack< Reversible * > &children, Reversible *child)
bool runPreChild(Reversible *preChild)
Terminal & source() const
Definition Move.cc:302
Terminal & destination() const
Definition Move.cc:323
virtual bool equals(const Terminal &other) const =0