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