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 #ifndef MAPLEBE_INCLUDE_CG_PDG_ANALYSIS_H
16 #define MAPLEBE_INCLUDE_CG_PDG_ANALYSIS_H
17
18 #include <utility>
19 #include "me_dominance.h"
20 #include "cfg_mst.h"
21 #include "instrument.h"
22 #include "cg_cdg.h"
23 #include "cg_dominance.h"
24 #include "data_dep_base.h"
25 #include "loop.h"
26
27 namespace maplebe {
28 #define CONTROL_DEP_ANALYSIS_DUMP CG_DEBUG_FUNC(cgFunc)
29 // Analyze Control Dependence
30 class ControlDepAnalysis {
31 public:
32 ControlDepAnalysis(CGFunc &func, MemPool &memPool, MemPool &tmpPool, DomAnalysis &d, PostDomAnalysis &pd,
33 LoopAnalysis &lp, CFGMST<BBEdge<maplebe::BB>, maplebe::BB> *cfgmst, std::string pName = "")
cgFunc(func)34 : cgFunc(func),
35 dom(&d),
36 pdom(&pd),
37 loop(&lp),
38 cfgMST(cfgmst),
39 cdgMemPool(memPool),
40 cdgAlloc(&memPool),
41 tmpAlloc(&tmpPool),
42 nonPdomEdges(tmpAlloc.Adapter()),
43 curCondNumOfBB(tmpAlloc.Adapter()),
44 phaseName(std::move(pName))
45 {
46 }
47 ControlDepAnalysis(CGFunc &func, MemPool &memPool, std::string pName = "", bool isSingle = true)
cgFunc(func)48 : cgFunc(func),
49 cdgMemPool(memPool),
50 cdgAlloc(&memPool),
51 tmpAlloc(&memPool),
52 nonPdomEdges(cdgAlloc.Adapter()),
53 curCondNumOfBB(cdgAlloc.Adapter()),
54 phaseName(std::move(pName)),
55 isSingleBB(isSingle)
56 {
57 }
~ControlDepAnalysis()58 virtual ~ControlDepAnalysis()
59 {
60 dom = nullptr;
61 fcdg = nullptr;
62 cfgMST = nullptr;
63 pdom = nullptr;
64 loop = nullptr;
65 }
66
PhaseName()67 std::string PhaseName() const
68 {
69 if (phaseName.empty()) {
70 return "controldepanalysis";
71 } else {
72 return phaseName;
73 }
74 }
SetIsSingleBB(bool isSingle)75 void SetIsSingleBB(bool isSingle)
76 {
77 isSingleBB = isSingle;
78 }
79
80 // The entry of analysis
81 void Run();
82
83 // Provide scheduling-related interfaces
84 void ComputeSingleBBRegions(); // For local-scheduling in a single BB
85 void GetEquivalentNodesInRegion(CDGRegion ®ion, CDGNode &cdgNode, std::vector<CDGNode *> &equivalentNodes);
86
87 // Interface for obtaining PDGAnalysis infos
GetFCDG()88 FCDG *GetFCDG()
89 {
90 return fcdg;
91 }
GetCFGMst()92 CFGMST<BBEdge<maplebe::BB>, maplebe::BB> *GetCFGMst()
93 {
94 return cfgMST;
95 }
96
97 // Print forward-control-dependence-graph in dot syntax
98 void GenerateFCDGDot() const;
99 // Print control-flow-graph with condition at edges in dot syntax
100 void GenerateCFGDot() const;
101 // Print control-flow-graph with only bbId
102 void GenerateSimplifiedCFGDot() const;
103 // Print control-flow-graph of the region in dot syntax
104 void GenerateCFGInRegionDot(CDGRegion ®ion) const;
105
106 protected:
107 void BuildCFGInfo();
108 void ConstructFCDG();
109 void ComputeRegions(bool doCDRegion);
110 void ComputeGeneralNonLinearRegions();
111 void FindInnermostLoops(std::vector<LoopDesc *> &innermostLoops, std::unordered_map<LoopDesc *, bool> &visited,
112 LoopDesc *lp);
113 void FindFallthroughPath(std::vector<CDGNode *> ®ionMembers, BB *curBB, bool isRoot);
114 void CreateRegionForSingleBB();
115 bool AddRegionNodesInTopologicalOrder(CDGRegion ®ion, CDGNode &root, const MapleSet<BBID> &members);
116 void ComputeSameCDRegions(bool considerNonDep);
117 void ComputeRegionForCurNode(uint32 curBBId, std::vector<bool> &visited);
118 void CreateAndDivideRegion(uint32 pBBId);
119 void ComputeRegionForNonDepNodes();
120 CDGRegion *FindExistRegion(CDGNode &node) const;
121 bool IsISEqualToCDs(CDGNode &parent, CDGNode &child) const;
122 void MergeRegions(CDGNode &mergeNode, CDGNode &candiNode);
123
124 CDGEdge *BuildControlDependence(const BB &fromBB, const BB &toBB, int32 condition);
125 CDGRegion *CreateFCDGRegion(CDGNode &curNode);
126 void CreateAllCDGNodes();
127 Dominance *ComputePdomInRegion(CDGRegion ®ion, std::vector<BB *> &nonUniformRegionCFG, uint32 &maxBBId);
128 bool IsInDifferentSCCNode(CDGRegion ®ion, std::vector<BB *> ®ionCFG, uint32 maxBBId, const BB &curBB,
129 const BB &memberBB);
130
AddNonPdomEdges(BBEdge<maplebe::BB> * bbEdge)131 void AddNonPdomEdges(BBEdge<maplebe::BB> *bbEdge)
132 {
133 nonPdomEdges.emplace_back(bbEdge);
134 }
135
GetAndAccSuccedCondNum(uint32 bbId)136 uint32 GetAndAccSuccedCondNum(uint32 bbId)
137 {
138 auto pair = curCondNumOfBB.try_emplace(bbId, 0);
139 if (pair.second) {
140 return 0;
141 } else {
142 uint32 curNum = pair.first->second;
143 pair.first->second = curNum + 1;
144 return curNum;
145 }
146 }
147
IsSameControlDependence(const CDGEdge & edge1,const CDGEdge & edge2)148 static bool IsSameControlDependence(const CDGEdge &edge1, const CDGEdge &edge2)
149 {
150 CDGNode &fromNode1 = edge1.GetFromNode();
151 CDGNode &fromNode2 = edge2.GetFromNode();
152 if (fromNode1.GetNodeId() != fromNode2.GetNodeId()) {
153 return false;
154 }
155 if (edge1.GetCondition() != edge2.GetCondition()) {
156 return false;
157 }
158 return true;
159 }
160
161 CGFunc &cgFunc;
162 DomAnalysis *dom = nullptr;
163 PostDomAnalysis *pdom = nullptr;
164 LoopAnalysis *loop = nullptr;
165 CFGMST<BBEdge<maplebe::BB>, maplebe::BB> *cfgMST = nullptr;
166 MemPool &cdgMemPool;
167 MapleAllocator cdgAlloc;
168 MapleAllocator tmpAlloc;
169 MapleVector<BBEdge<maplebe::BB> *> nonPdomEdges;
170 MapleUnorderedMap<uint32, uint32> curCondNumOfBB; // <BBId, assigned condNum>
171 FCDG *fcdg = nullptr;
172 uint32 lastRegionId = 0;
173 std::string phaseName;
174 bool isSingleBB = false;
175 };
176
177 MAPLE_FUNC_PHASE_DECLARE_BEGIN(CgControlDepAnalysis, maplebe::CGFunc);
GetResult()178 ControlDepAnalysis *GetResult()
179 {
180 return cda;
181 }
182 ControlDepAnalysis *cda = nullptr;
183 OVERRIDE_DEPENDENCE
184 MAPLE_FUNC_PHASE_DECLARE_END
185 } // namespace maplebe
186
187 #endif // MAPLEBE_INCLUDE_CG_PDG_ANALYSIS_H
188