1 /*========================== begin_copyright_notice ============================
2
3 Copyright (C) 2017-2021 Intel Corporation
4
5 SPDX-License-Identifier: MIT
6
7 ============================= end_copyright_notice ===========================*/
8
9 //
10 // This file implements FunctionGroup, FunctionGroupAnalysis.
11 // See FunctionGroup.h for more details.
12 //
13 // The FunctionGroupPass part was adapted from CallGraphSCCPass.cpp.
14 //
15 // This file is currently in lib/Target/GenX, as that is the only place it
16 // is used. It could be moved somewhere more general.
17 //
18 //===----------------------------------------------------------------------===//
19
20 #include "FunctionGroup.h"
21 #include "vc/GenXOpts/Utils/KernelInfo.h"
22 #include "llvm/Analysis/LoopInfo.h"
23 #include "llvm/GenXIntrinsics/GenXMetadata.h"
24 #include "llvm/IR/Dominators.h"
25 #include "llvm/IR/Function.h"
26 #include "llvm/IR/Instructions.h"
27 #include "llvm/IR/LLVMContext.h"
28 #include "llvm/IR/Module.h"
29 #include "llvm/Support/Debug.h"
30 #include "llvm/Support/Timer.h"
31 #include "llvm/Support/raw_ostream.h"
32 #include "llvm/Transforms/Utils/Cloning.h"
33 #include "llvm/Transforms/Utils/ValueMapper.h"
34
35 #include "GenXUtil.h"
36
37 #include "llvmWrapper/IR/LegacyPassManagers.h"
38 #include "llvmWrapper/IR/PassTimingInfo.h"
39
40 #include "Probe/Assertion.h"
41
42 #define DEBUG_TYPE "functiongroup-passmgr"
43
44 using namespace llvm;
45
verify() const46 bool FunctionGroup::verify() const {
47 // TODO: ideally, we'd like to access call-graph here. However,
48 // we do not maintain it here.
49 for (auto I = Functions.begin(), E = Functions.end(); I != E; ++I) {
50 Function *F = &(**I);
51 // Note: we do not check FG heads here -
52 // users of FG heads can belong to different FG
53 if (F == getHead())
54 continue;
55 for (auto *U : F->users()) {
56 auto *CI = genx::checkFunctionCall(U, F);
57 if (!CI)
58 continue;
59
60 // Note: it is expected that all users of any function from
61 // Functions array belong to the same FG
62 Function *Caller = CI->getFunction();
63 auto *OtherGroup = FGA->getAnyGroup(Caller);
64 IGC_ASSERT_MESSAGE(OtherGroup == this,
65 "inconsistent function group detected!");
66 if (OtherGroup != this)
67 return false;
68 }
69 }
70 return true;
71 }
72
73 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
print(raw_ostream & OS) const74 void FunctionGroup::print(raw_ostream &OS) const {
75 OS << "{{{" << getName() << "}}}\n";
76 for (const Function *F : Functions) {
77 OS << " " << F->getName() << "\n";
78 }
79
80 for (const auto &EnItem : enumerate(Subgroups)) {
81 OS << "--SGR[" << EnItem.index() << "]: ";
82 OS << "<" << EnItem.value()->getHead()->getName() << ">]\n";
83 }
84 }
85
dump() const86 void FunctionGroup::dump() const { print(dbgs()); }
87 #endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
88
89 /***********************************************************************
90 * FunctionGroupAnalysis implementation
91 */
92 char FunctionGroupAnalysis::ID = 0;
93 INITIALIZE_PASS(FunctionGroupAnalysis, "FunctionGroupAnalysis",
94 "FunctionGroupAnalysis", false, true /*analysis*/)
95
createFunctionGroupAnalysisPass()96 ModulePass *llvm::createFunctionGroupAnalysisPass() {
97 initializeFunctionGroupAnalysisPass(*PassRegistry::getPassRegistry());
98 return new FunctionGroupAnalysis();
99 }
100
101 // clear : clear out the analysis
clear()102 void FunctionGroupAnalysis::clear() {
103 for (auto T : TypesToProcess)
104 GroupMap[T].clear();
105
106 Groups.clear();
107 NonMainGroups.clear();
108 Visited.clear();
109 M = nullptr;
110 }
111
getGroup(const Function * F,FGType Type) const112 FunctionGroup *FunctionGroupAnalysis::getGroup(const Function *F,
113 FGType Type) const {
114 auto i = GroupMap[Type].find(F);
115 if (i == GroupMap[Type].end())
116 return nullptr;
117 return i->second;
118 }
119
120 // getGroup : get the FunctionGroup containing Function F, else 0
getGroup(const Function * F) const121 FunctionGroup *FunctionGroupAnalysis::getGroup(const Function *F) const {
122 return getGroup(F, FGType::GROUP);
123 }
124
getSubGroup(const Function * F) const125 FunctionGroup *FunctionGroupAnalysis::getSubGroup(const Function *F) const {
126 return getGroup(F, FGType::SUBGROUP);
127 }
128
getAnyGroup(const Function * F) const129 FunctionGroup *FunctionGroupAnalysis::getAnyGroup(const Function *F) const {
130 auto *Group = getGroup(F, FGType::SUBGROUP);
131 if (!Group)
132 Group = getGroup(F, FGType::GROUP);
133 IGC_ASSERT_MESSAGE(Group, "Function isn't assigned to any function group");
134 return Group;
135 }
136
137 // getGroupForHead : get the FunctionGroup for which Function F is the
138 // head, else 0
getGroupForHead(const Function * F) const139 FunctionGroup *FunctionGroupAnalysis::getGroupForHead(const Function *F) const {
140 auto *FG = getGroup(F);
141 IGC_ASSERT(FG->size());
142 if (*FG->begin() == F)
143 return FG;
144 return nullptr;
145 }
146
147 // replaceFunction : replace a Function in a FunctionGroup
148 // An in-use iterator in the modified FunctionGroup remains valid.
replaceFunction(Function * OldF,Function * NewF)149 void FunctionGroupAnalysis::replaceFunction(Function *OldF, Function *NewF) {
150 for (auto T : TypesToProcess) {
151 auto OldFIt = GroupMap[T].find(OldF);
152 if (OldFIt == GroupMap[T].end())
153 continue;
154 FunctionGroup *FG = OldFIt->second;
155 GroupMap[T].erase(OldFIt);
156 GroupMap[T][NewF] = FG;
157 for (auto i = FG->begin();; ++i) {
158 IGC_ASSERT(i != FG->end());
159 if (*i == OldF) {
160 *i = NewF;
161 break;
162 }
163 }
164 }
165 }
166
167 // addToFunctionGroup : add Function F to FunctionGroup FG
168 // Using this (rather than calling push_back directly on the FunctionGroup)
169 // means that the mapping from F to FG will be created, and getGroup() will
170 // work for this Function.
addToFunctionGroup(FunctionGroup * FG,Function * F,FGType Type)171 void FunctionGroupAnalysis::addToFunctionGroup(FunctionGroup *FG, Function *F,
172 FGType Type) {
173 IGC_ASSERT(FG);
174 IGC_ASSERT_MESSAGE(FG->getParent()->getModule() == M,
175 "attaching to FunctionGroup from wrong Module");
176 IGC_ASSERT_MESSAGE(!GroupMap[Type][F],
177 "Function already attached to FunctionGroup");
178 GroupMap[Type][F] = FG;
179 FG->push_back(F);
180 }
181
182 // createFunctionGroup : create new FunctionGroup for which F is the head
createFunctionGroup(Function * F,FGType Type)183 FunctionGroup *FunctionGroupAnalysis::createFunctionGroup(Function *F,
184 FGType Type) {
185 auto *FG = new FunctionGroup(this);
186 auto FGOwner = std::unique_ptr<FunctionGroup>(FG);
187 if (Type == FGType::GROUP)
188 Groups.push_back(std::move(FGOwner));
189 else
190 NonMainGroups.push_back(std::move(FGOwner));
191 addToFunctionGroup(FG, F, Type);
192 return FG;
193 }
194
195 // Returns true if pass is simple module pass,
196 // e.g. it is neither FG pass nor function pass manager.
isModulePass(Pass * P)197 static bool isModulePass(Pass *P) {
198 if (P->getPassKind() != PT_Module)
199 return false;
200 return !P->getAsPMDataManager();
201 }
202
TypeToAttr(FunctionGroupAnalysis::FGType Type)203 static StringRef TypeToAttr(FunctionGroupAnalysis::FGType Type) {
204 switch (Type) {
205 case FunctionGroupAnalysis::FGType::GROUP:
206 return genx::FunctionMD::CMGenXMain;
207 case FunctionGroupAnalysis::FGType::SUBGROUP:
208 return genx::FunctionMD::CMStackCall;
209 default:
210 IGC_ASSERT_EXIT_MESSAGE(0, "Can't gen attribute for nox-existent FG type");
211 break;
212 }
213 return "";
214 }
215
buildGroup(CallGraph & Callees,Function * F,FunctionGroup * curGr,FGType Type)216 bool FunctionGroupAnalysis::buildGroup(CallGraph &Callees, Function *F,
217 FunctionGroup *curGr, FGType Type) {
218 bool result = false;
219 LLVM_DEBUG(dbgs() << "process function " << F->getName() << " from " << curGr
220 << ", type = " << Type << "\n");
221 if (Visited.count(F) > 0) {
222 bool NeedCloning =
223 std::any_of(std::begin(TypesToProcess), std::end(TypesToProcess),
224 [&GM = GroupMap, curGr, F](FGType CurType) {
225 return GM[CurType].count(F) && GM[CurType][F] != curGr;
226 });
227 if (NeedCloning && !F->hasFnAttribute(TypeToAttr(Type))) {
228 ValueToValueMapTy VMap;
229 Function *ClonedFunc = CloneFunction(F, VMap);
230 LLVM_DEBUG(dbgs() << "Cloning: " << ClonedFunc->getName() << "\n");
231
232 result = true;
233
234 for (auto it = F->use_begin(); it != F->use_end();) {
235 Use *u = &*it++;
236 auto *CI = dyn_cast<CallInst>(u->getUser());
237 IGC_ASSERT(CI);
238 if (GroupMap[Type][CI->getFunction()] == curGr)
239 *u = ClonedFunc;
240 }
241 addToFunctionGroup(curGr, ClonedFunc, Type);
242
243 for (auto &Callee : Callees[F]) {
244 if (Callee == F)
245 continue;
246 if (genx::requiresStackCall(Callee)) {
247 LLVM_DEBUG(dbgs()
248 << "\tDo not process next callee " << Callee->getName()
249 << " because it's a stack call\n");
250 continue;
251 }
252 LLVM_DEBUG(dbgs() << "Next callee: " << Callee->getName() << "\n");
253 result |= buildGroup(Callees, Callee, curGr, Type);
254 }
255 }
256 } else if (!Visited.count(F)) {
257 Visited.insert(F);
258 // group is created either on a function with a corresponding attribute
259 // or on a root of a whole function tree that is kernel (genx_main)
260 if (F->hasFnAttribute(TypeToAttr(Type)) ||
261 F->hasFnAttribute(genx::FunctionMD::CMGenXMain)) {
262 LLVM_DEBUG(dbgs() << "Create new group of type " << Type << "\n");
263 curGr = createFunctionGroup(F, Type);
264 } else if (curGr) {
265 LLVM_DEBUG(dbgs() << "Add to group " << curGr->getHead()->getName()
266 << " of type " << Type << "\n");
267 addToFunctionGroup(curGr, F, Type);
268 }
269 for (auto &Callee : Callees[F]) {
270 if (genx::requiresStackCall(Callee)) {
271 LLVM_DEBUG(dbgs() << "\tDo not process next callee "
272 << Callee->getName()
273 << " because it's a stack call\n");
274 continue;
275 }
276
277 LLVM_DEBUG(dbgs() << "Next callee: " << Callee->getName() << "\n");
278 result |= buildGroup(Callees, Callee, curGr, Type);
279 }
280 }
281 LLVM_DEBUG(dbgs() << "finish processing function " << F->getName()
282 << " on level " << Type << "\n");
283 return result;
284 }
285
verify() const286 bool FunctionGroupAnalysis::verify() const {
287 return llvm::all_of(AllGroups(), [](const auto &GR) { return GR->verify(); });
288 }
289
290 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
print(raw_ostream & OS) const291 void FunctionGroupAnalysis::print(raw_ostream &OS) const {
292 OS << "Number of Groups = " << Groups.size() << "\n";
293 for (const auto &X : enumerate(Groups)) {
294 OS << "GR[" << X.index() << "] = <\n";
295 X.value()->print(OS);
296 OS << ">\n";
297 }
298 OS << "Number of SubGroups = " << NonMainGroups.size() << "\n";
299 for (const auto &X : enumerate(NonMainGroups)) {
300 OS << "SGR[" << X.index() << "] = <\n";
301 X.value()->print(OS);
302 OS << ">\n";
303 }
304 }
305
dump() const306 void FunctionGroupAnalysis::dump() const { print(dbgs()); }
307 #endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
308
309 //===----------------------------------------------------------------------===//
310 // DominatorTreeGroupWrapperPass Implementation
311 //===----------------------------------------------------------------------===//
312 //
313 // The implementation details of the wrapper pass that holds a DominatorTree
314 // per Function in a FunctionGroup.
315 //
316 //===----------------------------------------------------------------------===//
317 INITIALIZE_PASS_BEGIN(DominatorTreeGroupWrapperPassWrapper,
318 "groupdomtreeWrapper",
319 "Group Dominator Tree Construction Wrapper", true, true)
320 INITIALIZE_PASS_END(DominatorTreeGroupWrapperPassWrapper, "groupdomtreeWrapper",
321 "Group Dominator Tree Construction", true, true)
322
releaseMemory()323 void DominatorTreeGroupWrapperPass::releaseMemory() {
324 for (auto i = DTs.begin(), e = DTs.end(); i != e; ++i)
325 delete i->second;
326 DTs.clear();
327 }
328
runOnFunctionGroup(FunctionGroup & FG)329 bool DominatorTreeGroupWrapperPass::runOnFunctionGroup(FunctionGroup &FG) {
330 for (auto fgi = FG.begin(), fge = FG.end(); fgi != fge; ++fgi) {
331 Function *F = *fgi;
332 auto DT = new DominatorTree;
333 DT->recalculate(*F);
334 DTs[F] = DT;
335 }
336 return false;
337 }
338
verifyAnalysis() const339 void DominatorTreeGroupWrapperPass::verifyAnalysis() const {
340 for (auto i = DTs.begin(), e = DTs.end(); i != e; ++i)
341 i->second->verify();
342 }
343
print(raw_ostream & OS,const FunctionGroup *) const344 void DominatorTreeGroupWrapperPass::print(raw_ostream &OS,
345 const FunctionGroup *) const {
346 for (auto i = DTs.begin(), e = DTs.end(); i != e; ++i)
347 i->second->print(OS);
348 }
349
350 //===----------------------------------------------------------------------===//
351 // LoopInfoGroupWrapperPass Implementation
352 //===----------------------------------------------------------------------===//
353 //
354 // The implementation details of the wrapper pass that holds a LoopInfo
355 // per Function in a FunctionGroup.
356 //
357 //===----------------------------------------------------------------------===//
358 INITIALIZE_PASS_BEGIN(LoopInfoGroupWrapperPassWrapper, "grouploopinfoWrapper",
359 "Group Loop Info Construction Wrapper", true, true)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeGroupWrapperPassWrapper)360 INITIALIZE_PASS_DEPENDENCY(DominatorTreeGroupWrapperPassWrapper)
361 INITIALIZE_PASS_END(LoopInfoGroupWrapperPassWrapper, "grouploopinfoWrapper",
362 "Group Loop Info Construction Wrapper", true, true)
363
364 void LoopInfoGroupWrapperPass::releaseMemory() {
365 for (auto i = LIs.begin(), e = LIs.end(); i != e; ++i)
366 delete i->second;
367 LIs.clear();
368 }
369
runOnFunctionGroup(FunctionGroup & FG)370 bool LoopInfoGroupWrapperPass::runOnFunctionGroup(FunctionGroup &FG) {
371 auto &DTs = getAnalysis<DominatorTreeGroupWrapperPass>();
372 for (auto fgi = FG.begin(), fge = FG.end(); fgi != fge; ++fgi) {
373 Function *F = *fgi;
374 auto LI = new LoopInfo;
375 LI->analyze(*DTs.getDomTree(F));
376 LIs[F] = LI;
377 }
378 return false;
379 }
380
verifyAnalysis() const381 void LoopInfoGroupWrapperPass::verifyAnalysis() const {
382 auto &DTs = getAnalysis<DominatorTreeGroupWrapperPass>();
383 for (auto i = LIs.begin(), e = LIs.end(); i != e; ++i)
384 i->second->verify(*DTs.getDomTree(i->first));
385 }
386
print(raw_ostream & OS,const FunctionGroup *) const387 void LoopInfoGroupWrapperPass::print(raw_ostream &OS,
388 const FunctionGroup *) const {
389 for (auto i = LIs.begin(), e = LIs.end(); i != e; ++i)
390 i->second->print(OS);
391 }
392