1 /*
2 * Copyright (c) 2023 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "data_dep_analysis.h"
17 #include "control_dep_analysis.h"
18 #include "aarch64_cg.h"
19
20 namespace maplebe {
Run(CDGRegion & region)21 void DataDepAnalysis::Run(CDGRegion ®ion)
22 {
23 MemPool *regionMp = memPoolCtrler.NewMemPool("inter-block dda mempool", true);
24 auto *regionAlloc = new MapleAllocator(regionMp);
25
26 MapleVector<Insn *> comments(interAlloc.Adapter());
27 CDGNode *root = region.GetRegionRoot();
28 CHECK_FATAL(root != nullptr, "the root of region must be computed first");
29 InitInfoInRegion(*regionMp, *regionAlloc, region);
30
31 // Visit CDGNodes in the region follow the topological order of CFG
32 for (auto cdgNode : region.GetRegionNodes()) {
33 BB *curBB = cdgNode->GetBB();
34 CHECK_FATAL(curBB != nullptr, "get bb from CDGNode failed");
35 // Init data dependence info for cur cdgNode
36 InitInfoInCDGNode(*regionMp, *regionAlloc, *curBB, *cdgNode);
37 const Insn *locInsn = curBB->GetFirstLoc();
38 FOR_BB_INSNS(insn, curBB)
39 {
40 if (!insn->IsMachineInstruction()) {
41 ddb.ProcessNonMachineInsn(*insn, comments, cdgNode->GetAllDataNodes(), locInsn);
42 continue;
43 }
44 cdgNode->AccNodeSum();
45 DepNode *ddgNode = ddb.GenerateDepNode(*insn, cdgNode->GetAllDataNodes(), cdgNode->GetNodeSum(), comments);
46 ddb.BuildOpndDependency(*insn);
47 BuildSpecialInsnDependency(*insn, *cdgNode, region, *regionAlloc);
48 ddb.BuildAmbiInsnDependency(*insn);
49 ddb.BuildAsmInsnDependency(*insn);
50 ddb.BuildSpecialCallDeps(*insn);
51 // For global schedule before RA, do not move the instruction before the call,
52 // avoid unnecessary callee allocation and callee save instructions.
53 if (!cgFunc.IsAfterRegAlloc()) {
54 ddb.BuildDepsLastCallInsn(*insn);
55 }
56 if (insn->IsFrameDef()) {
57 cdgNode->SetLastFrameDefInsn(insn);
58 }
59 UpdateRegUseAndDef(*insn, *ddgNode, *cdgNode);
60 }
61 cdgNode->CopyAndClearComments(comments);
62 UpdateReadyNodesInfo(*cdgNode, *root);
63 }
64 ClearInfoInRegion(regionMp, regionAlloc, region);
65 }
66
InitInfoInRegion(MemPool & regionMp,MapleAllocator & regionAlloc,CDGRegion & region)67 void DataDepAnalysis::InitInfoInRegion(MemPool ®ionMp, MapleAllocator ®ionAlloc, CDGRegion ®ion)
68 {
69 ddb.SetCDGRegion(®ion);
70 for (auto cdgNode : region.GetRegionNodes()) {
71 cdgNode->InitTopoInRegionInfo(regionMp, regionAlloc);
72 }
73 }
74
InitInfoInCDGNode(MemPool & regionMp,MapleAllocator & regionAlloc,BB & bb,CDGNode & cdgNode)75 void DataDepAnalysis::InitInfoInCDGNode(MemPool ®ionMp, MapleAllocator ®ionAlloc, BB &bb, CDGNode &cdgNode)
76 {
77 ddb.SetCDGNode(&cdgNode);
78 ddb.InitCDGNodeDataInfo(regionMp, regionAlloc, cdgNode);
79 }
80
BuildDepsForPrevSeparator(CDGNode & cdgNode,DepNode & depNode,CDGRegion & curRegion)81 void DataDepAnalysis::BuildDepsForPrevSeparator(CDGNode &cdgNode, DepNode &depNode, CDGRegion &curRegion)
82 {
83 if (cdgNode.GetRegion() != &curRegion) {
84 return;
85 }
86 DepNode *prevSepNode = nullptr;
87 MapleVector<DepNode *> &dataNodes = cdgNode.GetAllDataNodes();
88 CHECK_FATAL(dataNodes.size() > 0, "must not be zero");
89 for (auto i = static_cast<int32>(dataNodes.size() - 1); i >= 0; --i) {
90 if (dataNodes[static_cast<uint32>(i)]->GetType() == kNodeTypeSeparator) {
91 prevSepNode = dataNodes[static_cast<uint32>(i)];
92 break;
93 }
94 }
95 if (prevSepNode != nullptr) {
96 ddb.AddDependence(*prevSepNode, depNode, kDependenceTypeSeparator);
97 return;
98 }
99 BB *bb = cdgNode.GetBB();
100 CHECK_FATAL(bb != nullptr, "get bb from cdgNode failed");
101 for (auto predIt = bb->GetPredsBegin(); predIt != bb->GetPredsEnd(); ++predIt) {
102 CDGNode *predNode = (*predIt)->GetCDGNode();
103 CHECK_FATAL(predNode != nullptr, "get cdgNode from bb failed");
104 BuildDepsForPrevSeparator(*predNode, depNode, curRegion);
105 }
106 }
107
BuildSpecialInsnDependency(Insn & insn,CDGNode & cdgNode,CDGRegion & region,MapleAllocator & alloc)108 void DataDepAnalysis::BuildSpecialInsnDependency(Insn &insn, CDGNode &cdgNode, CDGRegion ®ion, MapleAllocator &alloc)
109 {
110 MapleVector<DepNode *> dataNodes(alloc.Adapter());
111 for (auto nodeId : cdgNode.GetTopoPredInRegion()) {
112 CDGNode *predNode = region.GetCDGNodeById(nodeId);
113 CHECK_FATAL(predNode != nullptr, "get cdgNode from region by id failed");
114 for (auto depNode : predNode->GetAllDataNodes()) {
115 dataNodes.emplace_back(depNode);
116 }
117 }
118 for (auto depNode : cdgNode.GetAllDataNodes()) {
119 if (depNode != insn.GetDepNode()) {
120 dataNodes.emplace_back(depNode);
121 }
122 }
123 ddb.BuildSpecialInsnDependency(insn, dataNodes);
124 }
125
UpdateRegUseAndDef(Insn & insn,const DepNode & depNode,CDGNode & cdgNode)126 void DataDepAnalysis::UpdateRegUseAndDef(Insn &insn, const DepNode &depNode, CDGNode &cdgNode)
127 {
128 // Update reg use
129 const auto &useRegNos = depNode.GetUseRegnos();
130 for (auto regNO : useRegNos) {
131 cdgNode.AppendUseInsnChain(regNO, &insn, interMp);
132 }
133
134 // Update reg def
135 const auto &defRegNos = depNode.GetDefRegnos();
136 for (const auto regNO : defRegNos) {
137 // Update reg def for cur depInfo
138 cdgNode.SetLatestDefInsn(regNO, &insn);
139 cdgNode.ClearUseInsnChain(regNO);
140 }
141 }
142
UpdateReadyNodesInfo(CDGNode & cdgNode,const CDGNode & root) const143 void DataDepAnalysis::UpdateReadyNodesInfo(CDGNode &cdgNode, const CDGNode &root) const
144 {
145 BB *bb = cdgNode.GetBB();
146 CHECK_FATAL(bb != nullptr, "get bb from cdgNode failed");
147 for (auto succIt = bb->GetSuccsBegin(); succIt != bb->GetSuccsEnd(); ++succIt) {
148 CDGNode *succNode = (*succIt)->GetCDGNode();
149 CHECK_FATAL(succNode != nullptr, "get cdgNode from bb failed");
150 if (succNode != &root && succNode->GetRegion() == cdgNode.GetRegion()) {
151 succNode->SetNodeSum(std::max(cdgNode.GetNodeSum(), succNode->GetNodeSum()));
152 // Successor nodes in region record nodeIds that have been visited in topology order
153 for (const auto &nodeId : cdgNode.GetTopoPredInRegion()) {
154 succNode->InsertVisitedTopoPredInRegion(nodeId);
155 }
156 succNode->InsertVisitedTopoPredInRegion(cdgNode.GetNodeId());
157 }
158 }
159 }
160
ClearInfoInRegion(MemPool * regionMp,MapleAllocator * regionAlloc,CDGRegion & region) const161 void DataDepAnalysis::ClearInfoInRegion(MemPool *regionMp, MapleAllocator *regionAlloc, CDGRegion ®ion) const
162 {
163 delete regionAlloc;
164 memPoolCtrler.DeleteMemPool(regionMp);
165 for (auto cdgNode : region.GetRegionNodes()) {
166 cdgNode->ClearDataDepInfo();
167 cdgNode->ClearTopoInRegionInfo();
168 }
169 }
170
GenerateDataDepGraphDotOfRegion(CDGRegion & region)171 void DataDepAnalysis::GenerateDataDepGraphDotOfRegion(CDGRegion ®ion)
172 {
173 bool hasExceedMaximum = (region.GetRegionNodes().size() > kMaxDumpRegionNodeNum);
174 std::streambuf *coutBuf = std::cout.rdbuf();
175 std::ofstream iddgFile;
176 std::streambuf *fileBuf = iddgFile.rdbuf();
177 (void)std::cout.rdbuf(fileBuf);
178
179 // Define the output file name
180 std::string fileName;
181 (void)fileName.append("interDDG_");
182 (void)fileName.append(cgFunc.GetName());
183 (void)fileName.append("_region");
184 (void)fileName.append(std::to_string(region.GetRegionId()));
185 (void)fileName.append(".dot");
186
187 iddgFile.open(fileName, std::ios::trunc);
188 if (!iddgFile.is_open()) {
189 LogInfo::MapleLogger(kLlWarn) << "fileName:" << fileName << " open failed.\n";
190 return;
191 }
192 iddgFile << "digraph InterDDG_" << cgFunc.GetName() << " {\n\n";
193 if (hasExceedMaximum) {
194 iddgFile << "newrank = true;\n";
195 }
196 iddgFile << " node [shape=box];\n\n";
197
198 for (auto cdgNode : region.GetRegionNodes()) {
199 // Dump nodes style
200 for (auto depNode : cdgNode->GetAllDataNodes()) {
201 ddb.DumpNodeStyleInDot(iddgFile, *depNode);
202 }
203 iddgFile << "\n";
204
205 /* Dump edges style */
206 for (auto depNode : cdgNode->GetAllDataNodes()) {
207 for (auto succ : depNode->GetSuccs()) {
208 // Avoid overly complex data dependency graphs
209 if (hasExceedMaximum && succ->GetDepType() == kDependenceTypeSeparator) {
210 continue;
211 }
212 iddgFile << " insn_" << depNode->GetInsn() << " -> "
213 << "insn_" << succ->GetTo().GetInsn();
214 iddgFile << " [";
215 switch (succ->GetDepType()) {
216 case kDependenceTypeTrue:
217 iddgFile << "color=red,";
218 iddgFile << "label= \"" << succ->GetLatency() << "\"";
219 break;
220 case kDependenceTypeOutput:
221 iddgFile << "label= \""
222 << "output"
223 << "\"";
224 break;
225 case kDependenceTypeAnti:
226 iddgFile << "label= \""
227 << "anti"
228 << "\"";
229 break;
230 case kDependenceTypeControl:
231 iddgFile << "label= \""
232 << "control"
233 << "\"";
234 break;
235 case kDependenceTypeMembar:
236 iddgFile << "label= \""
237 << "membar"
238 << "\"";
239 break;
240 case kDependenceTypeThrow:
241 iddgFile << "label= \""
242 << "throw"
243 << "\"";
244 break;
245 case kDependenceTypeSeparator:
246 iddgFile << "label= \""
247 << "separator"
248 << "\"";
249 break;
250 case kDependenceTypeMemAccess:
251 iddgFile << "label= \""
252 << "memAccess"
253 << "\"";
254 break;
255 default:
256 CHECK_FATAL(false, "invalid depType");
257 }
258 iddgFile << "];\n";
259 }
260 }
261 iddgFile << "\n";
262
263 // Dump BB cluster
264 BB *bb = cdgNode->GetBB();
265 CHECK_FATAL(bb != nullptr, "get bb from cdgNode failed");
266 iddgFile << " subgraph cluster_" << bb->GetId() << " {\n";
267 iddgFile << " color=blue;\n";
268 iddgFile << " label = \"bb #" << bb->GetId() << "\";\n";
269 for (auto depNode : cdgNode->GetAllDataNodes()) {
270 iddgFile << " insn_" << depNode->GetInsn() << ";\n";
271 }
272 iddgFile << "}\n\n";
273 }
274
275 iddgFile << "}\n";
276 (void)iddgFile.flush();
277 iddgFile.close();
278 (void)std::cout.rdbuf(coutBuf);
279 }
280 } // namespace maplebe
281