1 //===- OMPContext.cpp ------ Collection of helpers for OpenMP contexts ----===// 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 /// \file 9 /// 10 /// This file implements helper functions and classes to deal with OpenMP 11 /// contexts as used by `[begin/end] declare variant` and `metadirective`. 12 /// 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/Frontend/OpenMP/OMPContext.h" 16 #include "llvm/ADT/SetOperations.h" 17 #include "llvm/ADT/StringRef.h" 18 #include "llvm/ADT/StringSwitch.h" 19 #include "llvm/ADT/Triple.h" 20 #include "llvm/Support/Debug.h" 21 #include "llvm/Support/raw_ostream.h" 22 23 #define DEBUG_TYPE "openmp-ir-builder" 24 25 using namespace llvm; 26 using namespace omp; 27 28 OMPContext::OMPContext(bool IsDeviceCompilation, Triple TargetTriple) { 29 // Add the appropriate device kind trait based on the triple and the 30 // IsDeviceCompilation flag. 31 ActiveTraits.set(unsigned(IsDeviceCompilation 32 ? TraitProperty::device_kind_nohost 33 : TraitProperty::device_kind_host)); 34 switch (TargetTriple.getArch()) { 35 case Triple::arm: 36 case Triple::armeb: 37 case Triple::aarch64: 38 case Triple::aarch64_be: 39 case Triple::aarch64_32: 40 case Triple::mips: 41 case Triple::mipsel: 42 case Triple::mips64: 43 case Triple::mips64el: 44 case Triple::ppc: 45 case Triple::ppcle: 46 case Triple::ppc64: 47 case Triple::ppc64le: 48 case Triple::x86: 49 case Triple::x86_64: 50 ActiveTraits.set(unsigned(TraitProperty::device_kind_cpu)); 51 break; 52 case Triple::amdgcn: 53 case Triple::nvptx: 54 case Triple::nvptx64: 55 ActiveTraits.set(unsigned(TraitProperty::device_kind_gpu)); 56 break; 57 default: 58 break; 59 } 60 61 // Add the appropriate device architecture trait based on the triple. 62 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str) \ 63 if (TraitSelector::TraitSelectorEnum == TraitSelector::device_arch) { \ 64 if (TargetTriple.getArch() == TargetTriple.getArchTypeForLLVMName(Str)) \ 65 ActiveTraits.set(unsigned(TraitProperty::Enum)); \ 66 if (StringRef(Str) == StringRef("x86_64") && \ 67 TargetTriple.getArch() == Triple::x86_64) \ 68 ActiveTraits.set(unsigned(TraitProperty::Enum)); \ 69 } 70 #include "llvm/Frontend/OpenMP/OMPKinds.def" 71 72 // TODO: What exactly do we want to see as device ISA trait? 73 // The discussion on the list did not seem to have come to an agreed 74 // upon solution. 75 76 // LLVM is the "OpenMP vendor" but we could also interpret vendor as the 77 // target vendor. 78 ActiveTraits.set(unsigned(TraitProperty::implementation_vendor_llvm)); 79 80 // The user condition true is accepted but not false. 81 ActiveTraits.set(unsigned(TraitProperty::user_condition_true)); 82 83 // This is for sure some device. 84 ActiveTraits.set(unsigned(TraitProperty::device_kind_any)); 85 86 LLVM_DEBUG({ 87 dbgs() << "[" << DEBUG_TYPE 88 << "] New OpenMP context with the following properties:\n"; 89 for (unsigned Bit : ActiveTraits.set_bits()) { 90 TraitProperty Property = TraitProperty(Bit); 91 dbgs() << "\t " << getOpenMPContextTraitPropertyFullName(Property) 92 << "\n"; 93 } 94 }); 95 } 96 97 /// Return true if \p C0 is a subset of \p C1. Note that both arrays are 98 /// expected to be sorted. 99 template <typename T> static bool isSubset(ArrayRef<T> C0, ArrayRef<T> C1) { 100 #ifdef EXPENSIVE_CHECKS 101 assert(llvm::is_sorted(C0) && llvm::is_sorted(C1) && 102 "Expected sorted arrays!"); 103 #endif 104 if (C0.size() > C1.size()) 105 return false; 106 auto It0 = C0.begin(), End0 = C0.end(); 107 auto It1 = C1.begin(), End1 = C1.end(); 108 while (It0 != End0) { 109 if (It1 == End1) 110 return false; 111 if (*It0 == *It1) { 112 ++It0; 113 ++It1; 114 continue; 115 } 116 ++It0; 117 } 118 return true; 119 } 120 121 /// Return true if \p C0 is a strict subset of \p C1. Note that both arrays are 122 /// expected to be sorted. 123 template <typename T> 124 static bool isStrictSubset(ArrayRef<T> C0, ArrayRef<T> C1) { 125 if (C0.size() >= C1.size()) 126 return false; 127 return isSubset<T>(C0, C1); 128 } 129 130 static bool isStrictSubset(const VariantMatchInfo &VMI0, 131 const VariantMatchInfo &VMI1) { 132 // If all required traits are a strict subset and the ordered vectors storing 133 // the construct traits, we say it is a strict subset. Note that the latter 134 // relation is not required to be strict. 135 if (VMI0.RequiredTraits.count() >= VMI1.RequiredTraits.count()) 136 return false; 137 for (unsigned Bit : VMI0.RequiredTraits.set_bits()) 138 if (!VMI1.RequiredTraits.test(Bit)) 139 return false; 140 if (!isSubset<TraitProperty>(VMI0.ConstructTraits, VMI1.ConstructTraits)) 141 return false; 142 return true; 143 } 144 145 static int isVariantApplicableInContextHelper( 146 const VariantMatchInfo &VMI, const OMPContext &Ctx, 147 SmallVectorImpl<unsigned> *ConstructMatches, bool DeviceSetOnly) { 148 149 // The match kind determines if we need to match all traits, any of the 150 // traits, or none of the traits for it to be an applicable context. 151 enum MatchKind { MK_ALL, MK_ANY, MK_NONE }; 152 153 MatchKind MK = MK_ALL; 154 // Determine the match kind the user wants, "all" is the default and provided 155 // to the user only for completeness. 156 if (VMI.RequiredTraits.test( 157 unsigned(TraitProperty::implementation_extension_match_any))) 158 MK = MK_ANY; 159 if (VMI.RequiredTraits.test( 160 unsigned(TraitProperty::implementation_extension_match_none))) 161 MK = MK_NONE; 162 163 // Helper to deal with a single property that was (not) found in the OpenMP 164 // context based on the match kind selected by the user via 165 // `implementation={extensions(match_[all,any,none])}' 166 auto HandleTrait = [MK](TraitProperty Property, 167 bool WasFound) -> Optional<bool> /* Result */ { 168 // For kind "any" a single match is enough but we ignore non-matched 169 // properties. 170 if (MK == MK_ANY) { 171 if (WasFound) 172 return true; 173 return None; 174 } 175 176 // In "all" or "none" mode we accept a matching or non-matching property 177 // respectively and move on. We are not done yet! 178 if ((WasFound && MK == MK_ALL) || (!WasFound && MK == MK_NONE)) 179 return None; 180 181 // We missed a property, provide some debug output and indicate failure. 182 LLVM_DEBUG({ 183 if (MK == MK_ALL) 184 dbgs() << "[" << DEBUG_TYPE << "] Property " 185 << getOpenMPContextTraitPropertyName(Property, "") 186 << " was not in the OpenMP context but match kind is all.\n"; 187 if (MK == MK_NONE) 188 dbgs() << "[" << DEBUG_TYPE << "] Property " 189 << getOpenMPContextTraitPropertyName(Property, "") 190 << " was in the OpenMP context but match kind is none.\n"; 191 }); 192 return false; 193 }; 194 195 for (unsigned Bit : VMI.RequiredTraits.set_bits()) { 196 TraitProperty Property = TraitProperty(Bit); 197 if (DeviceSetOnly && 198 getOpenMPContextTraitSetForProperty(Property) != TraitSet::device) 199 continue; 200 201 // So far all extensions are handled elsewhere, we skip them here as they 202 // are not part of the OpenMP context. 203 if (getOpenMPContextTraitSelectorForProperty(Property) == 204 TraitSelector::implementation_extension) 205 continue; 206 207 bool IsActiveTrait = Ctx.ActiveTraits.test(unsigned(Property)); 208 209 // We overwrite the isa trait as it is actually up to the OMPContext hook to 210 // check the raw string(s). 211 if (Property == TraitProperty::device_isa___ANY) 212 IsActiveTrait = llvm::all_of(VMI.ISATraits, [&](StringRef RawString) { 213 return Ctx.matchesISATrait(RawString); 214 }); 215 216 Optional<bool> Result = HandleTrait(Property, IsActiveTrait); 217 if (Result.hasValue()) 218 return Result.getValue(); 219 } 220 221 if (!DeviceSetOnly) { 222 // We could use isSubset here but we also want to record the match 223 // locations. 224 unsigned ConstructIdx = 0, NoConstructTraits = Ctx.ConstructTraits.size(); 225 for (TraitProperty Property : VMI.ConstructTraits) { 226 assert(getOpenMPContextTraitSetForProperty(Property) == 227 TraitSet::construct && 228 "Variant context is ill-formed!"); 229 230 // Verify the nesting. 231 bool FoundInOrder = false; 232 while (!FoundInOrder && ConstructIdx != NoConstructTraits) 233 FoundInOrder = (Ctx.ConstructTraits[ConstructIdx++] == Property); 234 if (ConstructMatches) 235 ConstructMatches->push_back(ConstructIdx - 1); 236 237 Optional<bool> Result = HandleTrait(Property, FoundInOrder); 238 if (Result.hasValue()) 239 return Result.getValue(); 240 241 if (!FoundInOrder) { 242 LLVM_DEBUG(dbgs() << "[" << DEBUG_TYPE << "] Construct property " 243 << getOpenMPContextTraitPropertyName(Property, "") 244 << " was not nested properly.\n"); 245 return false; 246 } 247 248 // TODO: Verify SIMD 249 } 250 251 assert(isSubset<TraitProperty>(VMI.ConstructTraits, Ctx.ConstructTraits) && 252 "Broken invariant!"); 253 } 254 255 if (MK == MK_ANY) { 256 LLVM_DEBUG(dbgs() << "[" << DEBUG_TYPE 257 << "] None of the properties was in the OpenMP context " 258 "but match kind is any.\n"); 259 return false; 260 } 261 262 return true; 263 } 264 265 bool llvm::omp::isVariantApplicableInContext(const VariantMatchInfo &VMI, 266 const OMPContext &Ctx, 267 bool DeviceSetOnly) { 268 return isVariantApplicableInContextHelper( 269 VMI, Ctx, /* ConstructMatches */ nullptr, DeviceSetOnly); 270 } 271 272 static APInt getVariantMatchScore(const VariantMatchInfo &VMI, 273 const OMPContext &Ctx, 274 SmallVectorImpl<unsigned> &ConstructMatches) { 275 APInt Score(64, 1); 276 277 unsigned NoConstructTraits = VMI.ConstructTraits.size(); 278 for (unsigned Bit : VMI.RequiredTraits.set_bits()) { 279 TraitProperty Property = TraitProperty(Bit); 280 // If there is a user score attached, use it. 281 if (VMI.ScoreMap.count(Property)) { 282 const APInt &UserScore = VMI.ScoreMap.lookup(Property); 283 assert(UserScore.uge(0) && "Expect non-negative user scores!"); 284 Score += UserScore.getZExtValue(); 285 continue; 286 } 287 288 switch (getOpenMPContextTraitSetForProperty(Property)) { 289 case TraitSet::construct: 290 // We handle the construct traits later via the VMI.ConstructTraits 291 // container. 292 continue; 293 case TraitSet::implementation: 294 // No effect on the score (implementation defined). 295 continue; 296 case TraitSet::user: 297 // No effect on the score. 298 continue; 299 case TraitSet::device: 300 // Handled separately below. 301 break; 302 case TraitSet::invalid: 303 llvm_unreachable("Unknown trait set is not to be used!"); 304 } 305 306 // device={kind(any)} is "as if" no kind selector was specified. 307 if (Property == TraitProperty::device_kind_any) 308 continue; 309 310 switch (getOpenMPContextTraitSelectorForProperty(Property)) { 311 case TraitSelector::device_kind: 312 Score += (1ULL << (NoConstructTraits + 0)); 313 continue; 314 case TraitSelector::device_arch: 315 Score += (1ULL << (NoConstructTraits + 1)); 316 continue; 317 case TraitSelector::device_isa: 318 Score += (1ULL << (NoConstructTraits + 2)); 319 continue; 320 default: 321 continue; 322 } 323 } 324 325 unsigned ConstructIdx = 0; 326 assert(NoConstructTraits == ConstructMatches.size() && 327 "Mismatch in the construct traits!"); 328 for (TraitProperty Property : VMI.ConstructTraits) { 329 assert(getOpenMPContextTraitSetForProperty(Property) == 330 TraitSet::construct && 331 "Ill-formed variant match info!"); 332 (void)Property; 333 // ConstructMatches is the position p - 1 and we need 2^(p-1). 334 Score += (1ULL << ConstructMatches[ConstructIdx++]); 335 } 336 337 LLVM_DEBUG(dbgs() << "[" << DEBUG_TYPE << "] Variant has a score of " << Score 338 << "\n"); 339 return Score; 340 } 341 342 int llvm::omp::getBestVariantMatchForContext( 343 const SmallVectorImpl<VariantMatchInfo> &VMIs, const OMPContext &Ctx) { 344 345 APInt BestScore(64, 0); 346 int BestVMIIdx = -1; 347 const VariantMatchInfo *BestVMI = nullptr; 348 349 for (unsigned u = 0, e = VMIs.size(); u < e; ++u) { 350 const VariantMatchInfo &VMI = VMIs[u]; 351 352 SmallVector<unsigned, 8> ConstructMatches; 353 // If the variant is not applicable its not the best. 354 if (!isVariantApplicableInContextHelper(VMI, Ctx, &ConstructMatches, 355 /* DeviceSetOnly */ false)) 356 continue; 357 // Check if its clearly not the best. 358 APInt Score = getVariantMatchScore(VMI, Ctx, ConstructMatches); 359 if (Score.ult(BestScore)) 360 continue; 361 // Equal score need subset checks. 362 if (Score.eq(BestScore)) { 363 // Strict subset are never best. 364 if (isStrictSubset(VMI, *BestVMI)) 365 continue; 366 // Same score and the current best is no strict subset so we keep it. 367 if (!isStrictSubset(*BestVMI, VMI)) 368 continue; 369 } 370 // New best found. 371 BestVMI = &VMI; 372 BestVMIIdx = u; 373 BestScore = Score; 374 } 375 376 return BestVMIIdx; 377 } 378 379 TraitSet llvm::omp::getOpenMPContextTraitSetKind(StringRef S) { 380 return StringSwitch<TraitSet>(S) 381 #define OMP_TRAIT_SET(Enum, Str) .Case(Str, TraitSet::Enum) 382 #include "llvm/Frontend/OpenMP/OMPKinds.def" 383 .Default(TraitSet::invalid); 384 } 385 386 TraitSet 387 llvm::omp::getOpenMPContextTraitSetForSelector(TraitSelector Selector) { 388 switch (Selector) { 389 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp) \ 390 case TraitSelector::Enum: \ 391 return TraitSet::TraitSetEnum; 392 #include "llvm/Frontend/OpenMP/OMPKinds.def" 393 } 394 llvm_unreachable("Unknown trait selector!"); 395 } 396 TraitSet 397 llvm::omp::getOpenMPContextTraitSetForProperty(TraitProperty Property) { 398 switch (Property) { 399 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str) \ 400 case TraitProperty::Enum: \ 401 return TraitSet::TraitSetEnum; 402 #include "llvm/Frontend/OpenMP/OMPKinds.def" 403 } 404 llvm_unreachable("Unknown trait set!"); 405 } 406 StringRef llvm::omp::getOpenMPContextTraitSetName(TraitSet Kind) { 407 switch (Kind) { 408 #define OMP_TRAIT_SET(Enum, Str) \ 409 case TraitSet::Enum: \ 410 return Str; 411 #include "llvm/Frontend/OpenMP/OMPKinds.def" 412 } 413 llvm_unreachable("Unknown trait set!"); 414 } 415 416 TraitSelector llvm::omp::getOpenMPContextTraitSelectorKind(StringRef S) { 417 return StringSwitch<TraitSelector>(S) 418 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp) \ 419 .Case(Str, TraitSelector::Enum) 420 #include "llvm/Frontend/OpenMP/OMPKinds.def" 421 .Default(TraitSelector::invalid); 422 } 423 TraitSelector 424 llvm::omp::getOpenMPContextTraitSelectorForProperty(TraitProperty Property) { 425 switch (Property) { 426 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str) \ 427 case TraitProperty::Enum: \ 428 return TraitSelector::TraitSelectorEnum; 429 #include "llvm/Frontend/OpenMP/OMPKinds.def" 430 } 431 llvm_unreachable("Unknown trait set!"); 432 } 433 StringRef llvm::omp::getOpenMPContextTraitSelectorName(TraitSelector Kind) { 434 switch (Kind) { 435 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp) \ 436 case TraitSelector::Enum: \ 437 return Str; 438 #include "llvm/Frontend/OpenMP/OMPKinds.def" 439 } 440 llvm_unreachable("Unknown trait selector!"); 441 } 442 443 TraitProperty llvm::omp::getOpenMPContextTraitPropertyKind( 444 TraitSet Set, TraitSelector Selector, StringRef S) { 445 // Special handling for `device={isa(...)}` as we accept anything here. It is 446 // up to the target to decide if the feature is available. 447 if (Set == TraitSet::device && Selector == TraitSelector::device_isa) 448 return TraitProperty::device_isa___ANY; 449 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str) \ 450 if (Set == TraitSet::TraitSetEnum && Str == S) \ 451 return TraitProperty::Enum; 452 #include "llvm/Frontend/OpenMP/OMPKinds.def" 453 return TraitProperty::invalid; 454 } 455 TraitProperty 456 llvm::omp::getOpenMPContextTraitPropertyForSelector(TraitSelector Selector) { 457 return StringSwitch<TraitProperty>( 458 getOpenMPContextTraitSelectorName(Selector)) 459 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str) \ 460 .Case(Str, Selector == TraitSelector::TraitSelectorEnum \ 461 ? TraitProperty::Enum \ 462 : TraitProperty::invalid) 463 #include "llvm/Frontend/OpenMP/OMPKinds.def" 464 .Default(TraitProperty::invalid); 465 } 466 StringRef llvm::omp::getOpenMPContextTraitPropertyName(TraitProperty Kind, 467 StringRef RawString) { 468 if (Kind == TraitProperty::device_isa___ANY) 469 return RawString; 470 switch (Kind) { 471 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str) \ 472 case TraitProperty::Enum: \ 473 return Str; 474 #include "llvm/Frontend/OpenMP/OMPKinds.def" 475 } 476 llvm_unreachable("Unknown trait property!"); 477 } 478 StringRef llvm::omp::getOpenMPContextTraitPropertyFullName(TraitProperty Kind) { 479 switch (Kind) { 480 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str) \ 481 case TraitProperty::Enum: \ 482 return "(" #TraitSetEnum "," #TraitSelectorEnum "," Str ")"; 483 #include "llvm/Frontend/OpenMP/OMPKinds.def" 484 } 485 llvm_unreachable("Unknown trait property!"); 486 } 487 488 bool llvm::omp::isValidTraitSelectorForTraitSet(TraitSelector Selector, 489 TraitSet Set, 490 bool &AllowsTraitScore, 491 bool &RequiresProperty) { 492 AllowsTraitScore = Set != TraitSet::construct && Set != TraitSet::device; 493 switch (Selector) { 494 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp) \ 495 case TraitSelector::Enum: \ 496 RequiresProperty = ReqProp; \ 497 return Set == TraitSet::TraitSetEnum; 498 #include "llvm/Frontend/OpenMP/OMPKinds.def" 499 } 500 llvm_unreachable("Unknown trait selector!"); 501 } 502 503 bool llvm::omp::isValidTraitPropertyForTraitSetAndSelector( 504 TraitProperty Property, TraitSelector Selector, TraitSet Set) { 505 switch (Property) { 506 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str) \ 507 case TraitProperty::Enum: \ 508 return Set == TraitSet::TraitSetEnum && \ 509 Selector == TraitSelector::TraitSelectorEnum; 510 #include "llvm/Frontend/OpenMP/OMPKinds.def" 511 } 512 llvm_unreachable("Unknown trait property!"); 513 } 514 515 std::string llvm::omp::listOpenMPContextTraitSets() { 516 std::string S; 517 #define OMP_TRAIT_SET(Enum, Str) \ 518 if (StringRef(Str) != "invalid") \ 519 S.append("'").append(Str).append("'").append(" "); 520 #include "llvm/Frontend/OpenMP/OMPKinds.def" 521 S.pop_back(); 522 return S; 523 } 524 525 std::string llvm::omp::listOpenMPContextTraitSelectors(TraitSet Set) { 526 std::string S; 527 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp) \ 528 if (TraitSet::TraitSetEnum == Set && StringRef(Str) != "Invalid") \ 529 S.append("'").append(Str).append("'").append(" "); 530 #include "llvm/Frontend/OpenMP/OMPKinds.def" 531 S.pop_back(); 532 return S; 533 } 534 535 std::string 536 llvm::omp::listOpenMPContextTraitProperties(TraitSet Set, 537 TraitSelector Selector) { 538 std::string S; 539 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str) \ 540 if (TraitSet::TraitSetEnum == Set && \ 541 TraitSelector::TraitSelectorEnum == Selector && \ 542 StringRef(Str) != "invalid") \ 543 S.append("'").append(Str).append("'").append(" "); 544 #include "llvm/Frontend/OpenMP/OMPKinds.def" 545 if (S.empty()) 546 return "<none>"; 547 S.pop_back(); 548 return S; 549 } 550