1 //===-- ModuleSummaryIndex.cpp - Module Summary Index ---------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the module index and summary classes for the 10 // IR library. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/IR/ModuleSummaryIndex.h" 15 #include "llvm/ADT/SCCIterator.h" 16 #include "llvm/ADT/Statistic.h" 17 #include "llvm/ADT/StringMap.h" 18 #include "llvm/Support/Path.h" 19 #include "llvm/Support/raw_ostream.h" 20 using namespace llvm; 21 22 #define DEBUG_TYPE "module-summary-index" 23 24 STATISTIC(ReadOnlyLiveGVars, 25 "Number of live global variables marked read only"); 26 STATISTIC(WriteOnlyLiveGVars, 27 "Number of live global variables marked write only"); 28 29 FunctionSummary FunctionSummary::ExternalNode = 30 FunctionSummary::makeDummyFunctionSummary({}); 31 32 bool ValueInfo::isDSOLocal() const { 33 // Need to check all summaries are local in case of hash collisions. 34 return getSummaryList().size() && 35 llvm::all_of(getSummaryList(), 36 [](const std::unique_ptr<GlobalValueSummary> &Summary) { 37 return Summary->isDSOLocal(); 38 }); 39 } 40 41 bool ValueInfo::canAutoHide() const { 42 // Can only auto hide if all copies are eligible to auto hide. 43 return getSummaryList().size() && 44 llvm::all_of(getSummaryList(), 45 [](const std::unique_ptr<GlobalValueSummary> &Summary) { 46 return Summary->canAutoHide(); 47 }); 48 } 49 50 // Gets the number of readonly and writeonly refs in RefEdgeList 51 std::pair<unsigned, unsigned> FunctionSummary::specialRefCounts() const { 52 // Here we take advantage of having all readonly and writeonly references 53 // located in the end of the RefEdgeList. 54 auto Refs = refs(); 55 unsigned RORefCnt = 0, WORefCnt = 0; 56 int I; 57 for (I = Refs.size() - 1; I >= 0 && Refs[I].isWriteOnly(); --I) 58 WORefCnt++; 59 for (; I >= 0 && Refs[I].isReadOnly(); --I) 60 RORefCnt++; 61 return {RORefCnt, WORefCnt}; 62 } 63 64 // Collect for the given module the list of function it defines 65 // (GUID -> Summary). 66 void ModuleSummaryIndex::collectDefinedFunctionsForModule( 67 StringRef ModulePath, GVSummaryMapTy &GVSummaryMap) const { 68 for (auto &GlobalList : *this) { 69 auto GUID = GlobalList.first; 70 for (auto &GlobSummary : GlobalList.second.SummaryList) { 71 auto *Summary = dyn_cast_or_null<FunctionSummary>(GlobSummary.get()); 72 if (!Summary) 73 // Ignore global variable, focus on functions 74 continue; 75 // Ignore summaries from other modules. 76 if (Summary->modulePath() != ModulePath) 77 continue; 78 GVSummaryMap[GUID] = Summary; 79 } 80 } 81 } 82 83 GlobalValueSummary * 84 ModuleSummaryIndex::getGlobalValueSummary(uint64_t ValueGUID, 85 bool PerModuleIndex) const { 86 auto VI = getValueInfo(ValueGUID); 87 assert(VI && "GlobalValue not found in index"); 88 assert((!PerModuleIndex || VI.getSummaryList().size() == 1) && 89 "Expected a single entry per global value in per-module index"); 90 auto &Summary = VI.getSummaryList()[0]; 91 return Summary.get(); 92 } 93 94 bool ModuleSummaryIndex::isGUIDLive(GlobalValue::GUID GUID) const { 95 auto VI = getValueInfo(GUID); 96 if (!VI) 97 return true; 98 const auto &SummaryList = VI.getSummaryList(); 99 if (SummaryList.empty()) 100 return true; 101 for (auto &I : SummaryList) 102 if (isGlobalValueLive(I.get())) 103 return true; 104 return false; 105 } 106 107 static void propagateAttributesToRefs(GlobalValueSummary *S) { 108 // If reference is not readonly or writeonly then referenced summary is not 109 // read/writeonly either. Note that: 110 // - All references from GlobalVarSummary are conservatively considered as 111 // not readonly or writeonly. Tracking them properly requires more complex 112 // analysis then we have now. 113 // 114 // - AliasSummary objects have no refs at all so this function is a no-op 115 // for them. 116 for (auto &VI : S->refs()) { 117 assert(VI.getAccessSpecifier() == 0 || isa<FunctionSummary>(S)); 118 for (auto &Ref : VI.getSummaryList()) 119 // If references to alias is not read/writeonly then aliasee 120 // is not read/writeonly 121 if (auto *GVS = dyn_cast<GlobalVarSummary>(Ref->getBaseObject())) { 122 if (!VI.isReadOnly()) 123 GVS->setReadOnly(false); 124 if (!VI.isWriteOnly()) 125 GVS->setWriteOnly(false); 126 } 127 } 128 } 129 130 // Do the access attribute propagation in combined index. 131 // The goal of attribute propagation is internalization of readonly (RO) 132 // or writeonly (WO) variables. To determine which variables are RO or WO 133 // and which are not we take following steps: 134 // - During analysis we speculatively assign readonly and writeonly 135 // attribute to all variables which can be internalized. When computing 136 // function summary we also assign readonly or writeonly attribute to a 137 // reference if function doesn't modify referenced variable (readonly) 138 // or doesn't read it (writeonly). 139 // 140 // - After computing dead symbols in combined index we do the attribute 141 // propagation. During this step we: 142 // a. clear RO and WO attributes from variables which are preserved or 143 // can't be imported 144 // b. clear RO and WO attributes from variables referenced by any global 145 // variable initializer 146 // c. clear RO attribute from variable referenced by a function when 147 // reference is not readonly 148 // d. clear WO attribute from variable referenced by a function when 149 // reference is not writeonly 150 // 151 // Because of (c, d) we don't internalize variables read by function A 152 // and modified by function B. 153 // 154 // Internalization itself happens in the backend after import is finished 155 // See internalizeGVsAfterImport. 156 void ModuleSummaryIndex::propagateAttributes( 157 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) { 158 for (auto &P : *this) 159 for (auto &S : P.second.SummaryList) { 160 if (!isGlobalValueLive(S.get())) 161 // We don't examine references from dead objects 162 continue; 163 164 // Global variable can't be marked read/writeonly if it is not eligible 165 // to import since we need to ensure that all external references get 166 // a local (imported) copy. It also can't be marked read/writeonly if 167 // it or any alias (since alias points to the same memory) are preserved 168 // or notEligibleToImport, since either of those means there could be 169 // writes (or reads in case of writeonly) that are not visible (because 170 // preserved means it could have external to DSO writes or reads, and 171 // notEligibleToImport means it could have writes or reads via inline 172 // assembly leading it to be in the @llvm.*used). 173 if (auto *GVS = dyn_cast<GlobalVarSummary>(S->getBaseObject())) 174 // Here we intentionally pass S.get() not GVS, because S could be 175 // an alias. 176 if (!canImportGlobalVar(S.get()) || 177 GUIDPreservedSymbols.count(P.first)) { 178 GVS->setReadOnly(false); 179 GVS->setWriteOnly(false); 180 } 181 propagateAttributesToRefs(S.get()); 182 } 183 if (llvm::AreStatisticsEnabled()) 184 for (auto &P : *this) 185 if (P.second.SummaryList.size()) 186 if (auto *GVS = dyn_cast<GlobalVarSummary>( 187 P.second.SummaryList[0]->getBaseObject())) 188 if (isGlobalValueLive(GVS)) { 189 if (GVS->maybeReadOnly()) 190 ReadOnlyLiveGVars++; 191 if (GVS->maybeWriteOnly()) 192 WriteOnlyLiveGVars++; 193 } 194 } 195 196 // TODO: write a graphviz dumper for SCCs (see ModuleSummaryIndex::exportToDot) 197 // then delete this function and update its tests 198 LLVM_DUMP_METHOD 199 void ModuleSummaryIndex::dumpSCCs(raw_ostream &O) { 200 for (scc_iterator<ModuleSummaryIndex *> I = 201 scc_begin<ModuleSummaryIndex *>(this); 202 !I.isAtEnd(); ++I) { 203 O << "SCC (" << utostr(I->size()) << " node" << (I->size() == 1 ? "" : "s") 204 << ") {\n"; 205 for (const ValueInfo V : *I) { 206 FunctionSummary *F = nullptr; 207 if (V.getSummaryList().size()) 208 F = cast<FunctionSummary>(V.getSummaryList().front().get()); 209 O << " " << (F == nullptr ? "External" : "") << " " << utostr(V.getGUID()) 210 << (I.hasLoop() ? " (has loop)" : "") << "\n"; 211 } 212 O << "}\n"; 213 } 214 } 215 216 namespace { 217 struct Attributes { 218 void add(const Twine &Name, const Twine &Value, 219 const Twine &Comment = Twine()); 220 void addComment(const Twine &Comment); 221 std::string getAsString() const; 222 223 std::vector<std::string> Attrs; 224 std::string Comments; 225 }; 226 227 struct Edge { 228 uint64_t SrcMod; 229 int Hotness; 230 GlobalValue::GUID Src; 231 GlobalValue::GUID Dst; 232 }; 233 } 234 235 void Attributes::add(const Twine &Name, const Twine &Value, 236 const Twine &Comment) { 237 std::string A = Name.str(); 238 A += "=\""; 239 A += Value.str(); 240 A += "\""; 241 Attrs.push_back(A); 242 addComment(Comment); 243 } 244 245 void Attributes::addComment(const Twine &Comment) { 246 if (!Comment.isTriviallyEmpty()) { 247 if (Comments.empty()) 248 Comments = " // "; 249 else 250 Comments += ", "; 251 Comments += Comment.str(); 252 } 253 } 254 255 std::string Attributes::getAsString() const { 256 if (Attrs.empty()) 257 return ""; 258 259 std::string Ret = "["; 260 for (auto &A : Attrs) 261 Ret += A + ","; 262 Ret.pop_back(); 263 Ret += "];"; 264 Ret += Comments; 265 return Ret; 266 } 267 268 static std::string linkageToString(GlobalValue::LinkageTypes LT) { 269 switch (LT) { 270 case GlobalValue::ExternalLinkage: 271 return "extern"; 272 case GlobalValue::AvailableExternallyLinkage: 273 return "av_ext"; 274 case GlobalValue::LinkOnceAnyLinkage: 275 return "linkonce"; 276 case GlobalValue::LinkOnceODRLinkage: 277 return "linkonce_odr"; 278 case GlobalValue::WeakAnyLinkage: 279 return "weak"; 280 case GlobalValue::WeakODRLinkage: 281 return "weak_odr"; 282 case GlobalValue::AppendingLinkage: 283 return "appending"; 284 case GlobalValue::InternalLinkage: 285 return "internal"; 286 case GlobalValue::PrivateLinkage: 287 return "private"; 288 case GlobalValue::ExternalWeakLinkage: 289 return "extern_weak"; 290 case GlobalValue::CommonLinkage: 291 return "common"; 292 } 293 294 return "<unknown>"; 295 } 296 297 static std::string fflagsToString(FunctionSummary::FFlags F) { 298 auto FlagValue = [](unsigned V) { return V ? '1' : '0'; }; 299 char FlagRep[] = {FlagValue(F.ReadNone), FlagValue(F.ReadOnly), 300 FlagValue(F.NoRecurse), FlagValue(F.ReturnDoesNotAlias), 301 FlagValue(F.NoInline), 0}; 302 303 return FlagRep; 304 } 305 306 // Get string representation of function instruction count and flags. 307 static std::string getSummaryAttributes(GlobalValueSummary* GVS) { 308 auto *FS = dyn_cast_or_null<FunctionSummary>(GVS); 309 if (!FS) 310 return ""; 311 312 return std::string("inst: ") + std::to_string(FS->instCount()) + 313 ", ffl: " + fflagsToString(FS->fflags()); 314 } 315 316 static std::string getNodeVisualName(GlobalValue::GUID Id) { 317 return std::string("@") + std::to_string(Id); 318 } 319 320 static std::string getNodeVisualName(const ValueInfo &VI) { 321 return VI.name().empty() ? getNodeVisualName(VI.getGUID()) : VI.name().str(); 322 } 323 324 static std::string getNodeLabel(const ValueInfo &VI, GlobalValueSummary *GVS) { 325 if (isa<AliasSummary>(GVS)) 326 return getNodeVisualName(VI); 327 328 std::string Attrs = getSummaryAttributes(GVS); 329 std::string Label = 330 getNodeVisualName(VI) + "|" + linkageToString(GVS->linkage()); 331 if (!Attrs.empty()) 332 Label += std::string(" (") + Attrs + ")"; 333 Label += "}"; 334 335 return Label; 336 } 337 338 // Write definition of external node, which doesn't have any 339 // specific module associated with it. Typically this is function 340 // or variable defined in native object or library. 341 static void defineExternalNode(raw_ostream &OS, const char *Pfx, 342 const ValueInfo &VI, GlobalValue::GUID Id) { 343 auto StrId = std::to_string(Id); 344 OS << " " << StrId << " [label=\""; 345 346 if (VI) { 347 OS << getNodeVisualName(VI); 348 } else { 349 OS << getNodeVisualName(Id); 350 } 351 OS << "\"]; // defined externally\n"; 352 } 353 354 static bool hasReadOnlyFlag(const GlobalValueSummary *S) { 355 if (auto *GVS = dyn_cast<GlobalVarSummary>(S)) 356 return GVS->maybeReadOnly(); 357 return false; 358 } 359 360 static bool hasWriteOnlyFlag(const GlobalValueSummary *S) { 361 if (auto *GVS = dyn_cast<GlobalVarSummary>(S)) 362 return GVS->maybeWriteOnly(); 363 return false; 364 } 365 366 void ModuleSummaryIndex::exportToDot(raw_ostream &OS) const { 367 std::vector<Edge> CrossModuleEdges; 368 DenseMap<GlobalValue::GUID, std::vector<uint64_t>> NodeMap; 369 using GVSOrderedMapTy = std::map<GlobalValue::GUID, GlobalValueSummary *>; 370 std::map<StringRef, GVSOrderedMapTy> ModuleToDefinedGVS; 371 collectDefinedGVSummariesPerModule(ModuleToDefinedGVS); 372 373 // Get node identifier in form MXXX_<GUID>. The MXXX prefix is required, 374 // because we may have multiple linkonce functions summaries. 375 auto NodeId = [](uint64_t ModId, GlobalValue::GUID Id) { 376 return ModId == (uint64_t)-1 ? std::to_string(Id) 377 : std::string("M") + std::to_string(ModId) + 378 "_" + std::to_string(Id); 379 }; 380 381 auto DrawEdge = [&](const char *Pfx, uint64_t SrcMod, GlobalValue::GUID SrcId, 382 uint64_t DstMod, GlobalValue::GUID DstId, 383 int TypeOrHotness) { 384 // 0 - alias 385 // 1 - reference 386 // 2 - constant reference 387 // 3 - writeonly reference 388 // Other value: (hotness - 4). 389 TypeOrHotness += 4; 390 static const char *EdgeAttrs[] = { 391 " [style=dotted]; // alias", 392 " [style=dashed]; // ref", 393 " [style=dashed,color=forestgreen]; // const-ref", 394 " [style=dashed,color=violetred]; // writeOnly-ref", 395 " // call (hotness : Unknown)", 396 " [color=blue]; // call (hotness : Cold)", 397 " // call (hotness : None)", 398 " [color=brown]; // call (hotness : Hot)", 399 " [style=bold,color=red]; // call (hotness : Critical)"}; 400 401 assert(static_cast<size_t>(TypeOrHotness) < 402 sizeof(EdgeAttrs) / sizeof(EdgeAttrs[0])); 403 OS << Pfx << NodeId(SrcMod, SrcId) << " -> " << NodeId(DstMod, DstId) 404 << EdgeAttrs[TypeOrHotness] << "\n"; 405 }; 406 407 OS << "digraph Summary {\n"; 408 for (auto &ModIt : ModuleToDefinedGVS) { 409 auto ModId = getModuleId(ModIt.first); 410 OS << " // Module: " << ModIt.first << "\n"; 411 OS << " subgraph cluster_" << std::to_string(ModId) << " {\n"; 412 OS << " style = filled;\n"; 413 OS << " color = lightgrey;\n"; 414 OS << " label = \"" << sys::path::filename(ModIt.first) << "\";\n"; 415 OS << " node [style=filled,fillcolor=lightblue];\n"; 416 417 auto &GVSMap = ModIt.second; 418 auto Draw = [&](GlobalValue::GUID IdFrom, GlobalValue::GUID IdTo, int Hotness) { 419 if (!GVSMap.count(IdTo)) { 420 CrossModuleEdges.push_back({ModId, Hotness, IdFrom, IdTo}); 421 return; 422 } 423 DrawEdge(" ", ModId, IdFrom, ModId, IdTo, Hotness); 424 }; 425 426 for (auto &SummaryIt : GVSMap) { 427 NodeMap[SummaryIt.first].push_back(ModId); 428 auto Flags = SummaryIt.second->flags(); 429 Attributes A; 430 if (isa<FunctionSummary>(SummaryIt.second)) { 431 A.add("shape", "record", "function"); 432 } else if (isa<AliasSummary>(SummaryIt.second)) { 433 A.add("style", "dotted,filled", "alias"); 434 A.add("shape", "box"); 435 } else { 436 A.add("shape", "Mrecord", "variable"); 437 if (Flags.Live && hasReadOnlyFlag(SummaryIt.second)) 438 A.addComment("immutable"); 439 if (Flags.Live && hasWriteOnlyFlag(SummaryIt.second)) 440 A.addComment("writeOnly"); 441 } 442 if (Flags.DSOLocal) 443 A.addComment("dsoLocal"); 444 if (Flags.CanAutoHide) 445 A.addComment("canAutoHide"); 446 447 auto VI = getValueInfo(SummaryIt.first); 448 A.add("label", getNodeLabel(VI, SummaryIt.second)); 449 if (!Flags.Live) 450 A.add("fillcolor", "red", "dead"); 451 else if (Flags.NotEligibleToImport) 452 A.add("fillcolor", "yellow", "not eligible to import"); 453 454 OS << " " << NodeId(ModId, SummaryIt.first) << " " << A.getAsString() 455 << "\n"; 456 } 457 OS << " // Edges:\n"; 458 459 for (auto &SummaryIt : GVSMap) { 460 auto *GVS = SummaryIt.second; 461 for (auto &R : GVS->refs()) 462 Draw(SummaryIt.first, R.getGUID(), 463 R.isWriteOnly() ? -1 : (R.isReadOnly() ? -2 : -3)); 464 465 if (auto *AS = dyn_cast_or_null<AliasSummary>(SummaryIt.second)) { 466 Draw(SummaryIt.first, AS->getAliaseeGUID(), -4); 467 continue; 468 } 469 470 if (auto *FS = dyn_cast_or_null<FunctionSummary>(SummaryIt.second)) 471 for (auto &CGEdge : FS->calls()) 472 Draw(SummaryIt.first, CGEdge.first.getGUID(), 473 static_cast<int>(CGEdge.second.Hotness)); 474 } 475 OS << " }\n"; 476 } 477 478 OS << " // Cross-module edges:\n"; 479 for (auto &E : CrossModuleEdges) { 480 auto &ModList = NodeMap[E.Dst]; 481 if (ModList.empty()) { 482 defineExternalNode(OS, " ", getValueInfo(E.Dst), E.Dst); 483 // Add fake module to the list to draw an edge to an external node 484 // in the loop below. 485 ModList.push_back(-1); 486 } 487 for (auto DstMod : ModList) 488 // The edge representing call or ref is drawn to every module where target 489 // symbol is defined. When target is a linkonce symbol there can be 490 // multiple edges representing a single call or ref, both intra-module and 491 // cross-module. As we've already drawn all intra-module edges before we 492 // skip it here. 493 if (DstMod != E.SrcMod) 494 DrawEdge(" ", E.SrcMod, E.Src, DstMod, E.Dst, E.Hotness); 495 } 496 497 OS << "}"; 498 } 499