1239310Sdim//===- CodeGenSchedule.cpp - Scheduling MachineModels ---------------------===// 2239310Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6239310Sdim// 7239310Sdim//===----------------------------------------------------------------------===// 8239310Sdim// 9276479Sdim// This file defines structures to encapsulate the machine model as described in 10239310Sdim// the target description. 11239310Sdim// 12239310Sdim//===----------------------------------------------------------------------===// 13239310Sdim 14341825Sdim#include "CodeGenSchedule.h" 15314564Sdim#include "CodeGenInstruction.h" 16239310Sdim#include "CodeGenTarget.h" 17341825Sdim#include "llvm/ADT/MapVector.h" 18341825Sdim#include "llvm/ADT/STLExtras.h" 19314564Sdim#include "llvm/ADT/SmallPtrSet.h" 20314564Sdim#include "llvm/ADT/SmallSet.h" 21314564Sdim#include "llvm/ADT/SmallVector.h" 22314564Sdim#include "llvm/Support/Casting.h" 23239310Sdim#include "llvm/Support/Debug.h" 24341825Sdim#include "llvm/Support/Regex.h" 25314564Sdim#include "llvm/Support/raw_ostream.h" 26249423Sdim#include "llvm/TableGen/Error.h" 27314564Sdim#include <algorithm> 28314564Sdim#include <iterator> 29314564Sdim#include <utility> 30239310Sdim 31239310Sdimusing namespace llvm; 32239310Sdim 33276479Sdim#define DEBUG_TYPE "subtarget-emitter" 34276479Sdim 35243830Sdim#ifndef NDEBUG 36296417Sdimstatic void dumpIdxVec(ArrayRef<unsigned> V) { 37296417Sdim for (unsigned Idx : V) 38296417Sdim dbgs() << Idx << ", "; 39243830Sdim} 40243830Sdim#endif 41243830Sdim 42261991Sdimnamespace { 43314564Sdim 44243830Sdim// (instrs a, b, ...) Evaluate and union all arguments. Identical to AddOp. 45243830Sdimstruct InstrsOp : public SetTheory::Operator { 46276479Sdim void apply(SetTheory &ST, DagInit *Expr, SetTheory::RecSet &Elts, 47276479Sdim ArrayRef<SMLoc> Loc) override { 48243830Sdim ST.evaluate(Expr->arg_begin(), Expr->arg_end(), Elts, Loc); 49243830Sdim } 50243830Sdim}; 51243830Sdim 52243830Sdim// (instregex "OpcPat",...) Find all instructions matching an opcode pattern. 53243830Sdimstruct InstRegexOp : public SetTheory::Operator { 54243830Sdim const CodeGenTarget &Target; 55243830Sdim InstRegexOp(const CodeGenTarget &t): Target(t) {} 56243830Sdim 57341825Sdim /// Remove any text inside of parentheses from S. 58341825Sdim static std::string removeParens(llvm::StringRef S) { 59341825Sdim std::string Result; 60341825Sdim unsigned Paren = 0; 61341825Sdim // NB: We don't care about escaped parens here. 62341825Sdim for (char C : S) { 63341825Sdim switch (C) { 64341825Sdim case '(': 65341825Sdim ++Paren; 66341825Sdim break; 67341825Sdim case ')': 68341825Sdim --Paren; 69341825Sdim break; 70341825Sdim default: 71341825Sdim if (Paren == 0) 72341825Sdim Result += C; 73341825Sdim } 74341825Sdim } 75341825Sdim return Result; 76341825Sdim } 77341825Sdim 78243830Sdim void apply(SetTheory &ST, DagInit *Expr, SetTheory::RecSet &Elts, 79276479Sdim ArrayRef<SMLoc> Loc) override { 80341825Sdim ArrayRef<const CodeGenInstruction *> Instructions = 81341825Sdim Target.getInstructionsByEnumValue(); 82341825Sdim 83341825Sdim unsigned NumGeneric = Target.getNumFixedInstructions(); 84341825Sdim unsigned NumPseudos = Target.getNumPseudoInstructions(); 85341825Sdim auto Generics = Instructions.slice(0, NumGeneric); 86341825Sdim auto Pseudos = Instructions.slice(NumGeneric, NumPseudos); 87341825Sdim auto NonPseudos = Instructions.slice(NumGeneric + NumPseudos); 88341825Sdim 89327952Sdim for (Init *Arg : make_range(Expr->arg_begin(), Expr->arg_end())) { 90327952Sdim StringInit *SI = dyn_cast<StringInit>(Arg); 91243830Sdim if (!SI) 92341825Sdim PrintFatalError(Loc, "instregex requires pattern string: " + 93341825Sdim Expr->getAsString()); 94341825Sdim StringRef Original = SI->getValue(); 95341825Sdim 96341825Sdim // Extract a prefix that we can binary search on. 97341825Sdim static const char RegexMetachars[] = "()^$|*+?.[]\\{}"; 98341825Sdim auto FirstMeta = Original.find_first_of(RegexMetachars); 99341825Sdim 100341825Sdim // Look for top-level | or ?. We cannot optimize them to binary search. 101341825Sdim if (removeParens(Original).find_first_of("|?") != std::string::npos) 102341825Sdim FirstMeta = 0; 103341825Sdim 104341825Sdim Optional<Regex> Regexpr = None; 105341825Sdim StringRef Prefix = Original.substr(0, FirstMeta); 106341825Sdim StringRef PatStr = Original.substr(FirstMeta); 107341825Sdim if (!PatStr.empty()) { 108341825Sdim // For the rest use a python-style prefix match. 109341825Sdim std::string pat = PatStr; 110341825Sdim if (pat[0] != '^') { 111341825Sdim pat.insert(0, "^("); 112341825Sdim pat.insert(pat.end(), ')'); 113341825Sdim } 114341825Sdim Regexpr = Regex(pat); 115243830Sdim } 116341825Sdim 117341825Sdim int NumMatches = 0; 118341825Sdim 119341825Sdim // The generic opcodes are unsorted, handle them manually. 120341825Sdim for (auto *Inst : Generics) { 121341825Sdim StringRef InstName = Inst->TheDef->getName(); 122341825Sdim if (InstName.startswith(Prefix) && 123341825Sdim (!Regexpr || Regexpr->match(InstName.substr(Prefix.size())))) { 124280031Sdim Elts.insert(Inst->TheDef); 125341825Sdim NumMatches++; 126341825Sdim } 127243830Sdim } 128341825Sdim 129341825Sdim // Target instructions are split into two ranges: pseudo instructions 130341825Sdim // first, than non-pseudos. Each range is in lexicographical order 131341825Sdim // sorted by name. Find the sub-ranges that start with our prefix. 132341825Sdim struct Comp { 133341825Sdim bool operator()(const CodeGenInstruction *LHS, StringRef RHS) { 134341825Sdim return LHS->TheDef->getName() < RHS; 135341825Sdim } 136341825Sdim bool operator()(StringRef LHS, const CodeGenInstruction *RHS) { 137341825Sdim return LHS < RHS->TheDef->getName() && 138341825Sdim !RHS->TheDef->getName().startswith(LHS); 139341825Sdim } 140341825Sdim }; 141341825Sdim auto Range1 = 142341825Sdim std::equal_range(Pseudos.begin(), Pseudos.end(), Prefix, Comp()); 143341825Sdim auto Range2 = std::equal_range(NonPseudos.begin(), NonPseudos.end(), 144341825Sdim Prefix, Comp()); 145341825Sdim 146341825Sdim // For these ranges we know that instruction names start with the prefix. 147341825Sdim // Check if there's a regex that needs to be checked. 148341825Sdim const auto HandleNonGeneric = [&](const CodeGenInstruction *Inst) { 149341825Sdim StringRef InstName = Inst->TheDef->getName(); 150341825Sdim if (!Regexpr || Regexpr->match(InstName.substr(Prefix.size()))) { 151341825Sdim Elts.insert(Inst->TheDef); 152341825Sdim NumMatches++; 153341825Sdim } 154341825Sdim }; 155341825Sdim std::for_each(Range1.first, Range1.second, HandleNonGeneric); 156341825Sdim std::for_each(Range2.first, Range2.second, HandleNonGeneric); 157341825Sdim 158341825Sdim if (0 == NumMatches) 159341825Sdim PrintFatalError(Loc, "instregex has no matches: " + Original); 160243830Sdim } 161243830Sdim } 162243830Sdim}; 163314564Sdim 164261991Sdim} // end anonymous namespace 165243830Sdim 166243830Sdim/// CodeGenModels ctor interprets machine model records and populates maps. 167239310SdimCodeGenSchedModels::CodeGenSchedModels(RecordKeeper &RK, 168239310Sdim const CodeGenTarget &TGT): 169249423Sdim Records(RK), Target(TGT) { 170239310Sdim 171243830Sdim Sets.addFieldExpander("InstRW", "Instrs"); 172239310Sdim 173243830Sdim // Allow Set evaluation to recognize the dags used in InstRW records: 174243830Sdim // (instrs Op1, Op1...) 175360784Sdim Sets.addOperator("instrs", std::make_unique<InstrsOp>()); 176360784Sdim Sets.addOperator("instregex", std::make_unique<InstRegexOp>(Target)); 177243830Sdim 178243830Sdim // Instantiate a CodeGenProcModel for each SchedMachineModel with the values 179243830Sdim // that are explicitly referenced in tablegen records. Resources associated 180243830Sdim // with each processor will be derived later. Populate ProcModelMap with the 181243830Sdim // CodeGenProcModel instances. 182243830Sdim collectProcModels(); 183243830Sdim 184243830Sdim // Instantiate a CodeGenSchedRW for each SchedReadWrite record explicitly 185243830Sdim // defined, and populate SchedReads and SchedWrites vectors. Implicit 186243830Sdim // SchedReadWrites that represent sequences derived from expanded variant will 187243830Sdim // be inferred later. 188243830Sdim collectSchedRW(); 189243830Sdim 190243830Sdim // Instantiate a CodeGenSchedClass for each unique SchedRW signature directly 191243830Sdim // required by an instruction definition, and populate SchedClassIdxMap. Set 192243830Sdim // NumItineraryClasses to the number of explicit itinerary classes referenced 193243830Sdim // by instructions. Set NumInstrSchedClasses to the number of itinerary 194243830Sdim // classes plus any classes implied by instructions that derive from class 195243830Sdim // Sched and provide SchedRW list. This does not infer any new classes from 196243830Sdim // SchedVariant. 197243830Sdim collectSchedClasses(); 198243830Sdim 199243830Sdim // Find instruction itineraries for each processor. Sort and populate 200243830Sdim // CodeGenProcModel::ItinDefList. (Cycle-to-cycle itineraries). This requires 201243830Sdim // all itinerary classes to be discovered. 202243830Sdim collectProcItins(); 203243830Sdim 204243830Sdim // Find ItinRW records for each processor and itinerary class. 205243830Sdim // (For per-operand resources mapped to itinerary classes). 206243830Sdim collectProcItinRW(); 207243830Sdim 208309124Sdim // Find UnsupportedFeatures records for each processor. 209309124Sdim // (For per-operand resources mapped to itinerary classes). 210309124Sdim collectProcUnsupportedFeatures(); 211309124Sdim 212243830Sdim // Infer new SchedClasses from SchedVariant. 213243830Sdim inferSchedClasses(); 214243830Sdim 215243830Sdim // Populate each CodeGenProcModel's WriteResDefs, ReadAdvanceDefs, and 216243830Sdim // ProcResourceDefs. 217341825Sdim LLVM_DEBUG( 218341825Sdim dbgs() << "\n+++ RESOURCE DEFINITIONS (collectProcResources) +++\n"); 219243830Sdim collectProcResources(); 220309124Sdim 221341825Sdim // Collect optional processor description. 222341825Sdim collectOptionalProcessorInfo(); 223341825Sdim 224344779Sdim // Check MCInstPredicate definitions. 225344779Sdim checkMCInstPredicates(); 226344779Sdim 227344779Sdim // Check STIPredicate definitions. 228344779Sdim checkSTIPredicates(); 229344779Sdim 230344779Sdim // Find STIPredicate definitions for each processor model, and construct 231344779Sdim // STIPredicateFunction objects. 232344779Sdim collectSTIPredicates(); 233344779Sdim 234309124Sdim checkCompleteness(); 235239310Sdim} 236239310Sdim 237344779Sdimvoid CodeGenSchedModels::checkSTIPredicates() const { 238344779Sdim DenseMap<StringRef, const Record *> Declarations; 239344779Sdim 240344779Sdim // There cannot be multiple declarations with the same name. 241344779Sdim const RecVec Decls = Records.getAllDerivedDefinitions("STIPredicateDecl"); 242344779Sdim for (const Record *R : Decls) { 243344779Sdim StringRef Name = R->getValueAsString("Name"); 244344779Sdim const auto It = Declarations.find(Name); 245344779Sdim if (It == Declarations.end()) { 246344779Sdim Declarations[Name] = R; 247344779Sdim continue; 248344779Sdim } 249344779Sdim 250344779Sdim PrintError(R->getLoc(), "STIPredicate " + Name + " multiply declared."); 251344779Sdim PrintNote(It->second->getLoc(), "Previous declaration was here."); 252344779Sdim PrintFatalError(R->getLoc(), "Invalid STIPredicateDecl found."); 253344779Sdim } 254344779Sdim 255344779Sdim // Disallow InstructionEquivalenceClasses with an empty instruction list. 256344779Sdim const RecVec Defs = 257344779Sdim Records.getAllDerivedDefinitions("InstructionEquivalenceClass"); 258344779Sdim for (const Record *R : Defs) { 259344779Sdim RecVec Opcodes = R->getValueAsListOfDefs("Opcodes"); 260344779Sdim if (Opcodes.empty()) { 261344779Sdim PrintFatalError(R->getLoc(), "Invalid InstructionEquivalenceClass " 262344779Sdim "defined with an empty opcode list."); 263344779Sdim } 264344779Sdim } 265344779Sdim} 266344779Sdim 267344779Sdim// Used by function `processSTIPredicate` to construct a mask of machine 268344779Sdim// instruction operands. 269344779Sdimstatic APInt constructOperandMask(ArrayRef<int64_t> Indices) { 270344779Sdim APInt OperandMask; 271344779Sdim if (Indices.empty()) 272344779Sdim return OperandMask; 273344779Sdim 274344779Sdim int64_t MaxIndex = *std::max_element(Indices.begin(), Indices.end()); 275344779Sdim assert(MaxIndex >= 0 && "Invalid negative indices in input!"); 276344779Sdim OperandMask = OperandMask.zext(MaxIndex + 1); 277344779Sdim for (const int64_t Index : Indices) { 278344779Sdim assert(Index >= 0 && "Invalid negative indices!"); 279344779Sdim OperandMask.setBit(Index); 280344779Sdim } 281344779Sdim 282344779Sdim return OperandMask; 283344779Sdim} 284344779Sdim 285344779Sdimstatic void 286344779SdimprocessSTIPredicate(STIPredicateFunction &Fn, 287344779Sdim const DenseMap<Record *, unsigned> &ProcModelMap) { 288344779Sdim DenseMap<const Record *, unsigned> Opcode2Index; 289344779Sdim using OpcodeMapPair = std::pair<const Record *, OpcodeInfo>; 290344779Sdim std::vector<OpcodeMapPair> OpcodeMappings; 291344779Sdim std::vector<std::pair<APInt, APInt>> OpcodeMasks; 292344779Sdim 293344779Sdim DenseMap<const Record *, unsigned> Predicate2Index; 294344779Sdim unsigned NumUniquePredicates = 0; 295344779Sdim 296344779Sdim // Number unique predicates and opcodes used by InstructionEquivalenceClass 297344779Sdim // definitions. Each unique opcode will be associated with an OpcodeInfo 298344779Sdim // object. 299344779Sdim for (const Record *Def : Fn.getDefinitions()) { 300344779Sdim RecVec Classes = Def->getValueAsListOfDefs("Classes"); 301344779Sdim for (const Record *EC : Classes) { 302344779Sdim const Record *Pred = EC->getValueAsDef("Predicate"); 303344779Sdim if (Predicate2Index.find(Pred) == Predicate2Index.end()) 304344779Sdim Predicate2Index[Pred] = NumUniquePredicates++; 305344779Sdim 306344779Sdim RecVec Opcodes = EC->getValueAsListOfDefs("Opcodes"); 307344779Sdim for (const Record *Opcode : Opcodes) { 308344779Sdim if (Opcode2Index.find(Opcode) == Opcode2Index.end()) { 309344779Sdim Opcode2Index[Opcode] = OpcodeMappings.size(); 310344779Sdim OpcodeMappings.emplace_back(Opcode, OpcodeInfo()); 311344779Sdim } 312344779Sdim } 313344779Sdim } 314344779Sdim } 315344779Sdim 316344779Sdim // Initialize vector `OpcodeMasks` with default values. We want to keep track 317344779Sdim // of which processors "use" which opcodes. We also want to be able to 318344779Sdim // identify predicates that are used by different processors for a same 319344779Sdim // opcode. 320344779Sdim // This information is used later on by this algorithm to sort OpcodeMapping 321344779Sdim // elements based on their processor and predicate sets. 322344779Sdim OpcodeMasks.resize(OpcodeMappings.size()); 323344779Sdim APInt DefaultProcMask(ProcModelMap.size(), 0); 324344779Sdim APInt DefaultPredMask(NumUniquePredicates, 0); 325344779Sdim for (std::pair<APInt, APInt> &MaskPair : OpcodeMasks) 326344779Sdim MaskPair = std::make_pair(DefaultProcMask, DefaultPredMask); 327344779Sdim 328344779Sdim // Construct a OpcodeInfo object for every unique opcode declared by an 329344779Sdim // InstructionEquivalenceClass definition. 330344779Sdim for (const Record *Def : Fn.getDefinitions()) { 331344779Sdim RecVec Classes = Def->getValueAsListOfDefs("Classes"); 332344779Sdim const Record *SchedModel = Def->getValueAsDef("SchedModel"); 333344779Sdim unsigned ProcIndex = ProcModelMap.find(SchedModel)->second; 334344779Sdim APInt ProcMask(ProcModelMap.size(), 0); 335344779Sdim ProcMask.setBit(ProcIndex); 336344779Sdim 337344779Sdim for (const Record *EC : Classes) { 338344779Sdim RecVec Opcodes = EC->getValueAsListOfDefs("Opcodes"); 339344779Sdim 340344779Sdim std::vector<int64_t> OpIndices = 341344779Sdim EC->getValueAsListOfInts("OperandIndices"); 342344779Sdim APInt OperandMask = constructOperandMask(OpIndices); 343344779Sdim 344344779Sdim const Record *Pred = EC->getValueAsDef("Predicate"); 345344779Sdim APInt PredMask(NumUniquePredicates, 0); 346344779Sdim PredMask.setBit(Predicate2Index[Pred]); 347344779Sdim 348344779Sdim for (const Record *Opcode : Opcodes) { 349344779Sdim unsigned OpcodeIdx = Opcode2Index[Opcode]; 350344779Sdim if (OpcodeMasks[OpcodeIdx].first[ProcIndex]) { 351344779Sdim std::string Message = 352344779Sdim "Opcode " + Opcode->getName().str() + 353344779Sdim " used by multiple InstructionEquivalenceClass definitions."; 354344779Sdim PrintFatalError(EC->getLoc(), Message); 355344779Sdim } 356344779Sdim OpcodeMasks[OpcodeIdx].first |= ProcMask; 357344779Sdim OpcodeMasks[OpcodeIdx].second |= PredMask; 358344779Sdim OpcodeInfo &OI = OpcodeMappings[OpcodeIdx].second; 359344779Sdim 360344779Sdim OI.addPredicateForProcModel(ProcMask, OperandMask, Pred); 361344779Sdim } 362344779Sdim } 363344779Sdim } 364344779Sdim 365344779Sdim // Sort OpcodeMappings elements based on their CPU and predicate masks. 366344779Sdim // As a last resort, order elements by opcode identifier. 367344779Sdim llvm::sort(OpcodeMappings, 368344779Sdim [&](const OpcodeMapPair &Lhs, const OpcodeMapPair &Rhs) { 369344779Sdim unsigned LhsIdx = Opcode2Index[Lhs.first]; 370344779Sdim unsigned RhsIdx = Opcode2Index[Rhs.first]; 371353358Sdim const std::pair<APInt, APInt> &LhsMasks = OpcodeMasks[LhsIdx]; 372353358Sdim const std::pair<APInt, APInt> &RhsMasks = OpcodeMasks[RhsIdx]; 373344779Sdim 374353358Sdim auto LessThan = [](const APInt &Lhs, const APInt &Rhs) { 375353358Sdim unsigned LhsCountPopulation = Lhs.countPopulation(); 376353358Sdim unsigned RhsCountPopulation = Rhs.countPopulation(); 377353358Sdim return ((LhsCountPopulation < RhsCountPopulation) || 378353358Sdim ((LhsCountPopulation == RhsCountPopulation) && 379353358Sdim (Lhs.countLeadingZeros() > Rhs.countLeadingZeros()))); 380353358Sdim }; 381344779Sdim 382353358Sdim if (LhsMasks.first != RhsMasks.first) 383353358Sdim return LessThan(LhsMasks.first, RhsMasks.first); 384344779Sdim 385353358Sdim if (LhsMasks.second != RhsMasks.second) 386353358Sdim return LessThan(LhsMasks.second, RhsMasks.second); 387353358Sdim 388344779Sdim return LhsIdx < RhsIdx; 389344779Sdim }); 390344779Sdim 391344779Sdim // Now construct opcode groups. Groups are used by the SubtargetEmitter when 392344779Sdim // expanding the body of a STIPredicate function. In particular, each opcode 393344779Sdim // group is expanded into a sequence of labels in a switch statement. 394344779Sdim // It identifies opcodes for which different processors define same predicates 395344779Sdim // and same opcode masks. 396344779Sdim for (OpcodeMapPair &Info : OpcodeMappings) 397344779Sdim Fn.addOpcode(Info.first, std::move(Info.second)); 398344779Sdim} 399344779Sdim 400344779Sdimvoid CodeGenSchedModels::collectSTIPredicates() { 401344779Sdim // Map STIPredicateDecl records to elements of vector 402344779Sdim // CodeGenSchedModels::STIPredicates. 403344779Sdim DenseMap<const Record *, unsigned> Decl2Index; 404344779Sdim 405344779Sdim RecVec RV = Records.getAllDerivedDefinitions("STIPredicate"); 406344779Sdim for (const Record *R : RV) { 407344779Sdim const Record *Decl = R->getValueAsDef("Declaration"); 408344779Sdim 409344779Sdim const auto It = Decl2Index.find(Decl); 410344779Sdim if (It == Decl2Index.end()) { 411344779Sdim Decl2Index[Decl] = STIPredicates.size(); 412344779Sdim STIPredicateFunction Predicate(Decl); 413344779Sdim Predicate.addDefinition(R); 414344779Sdim STIPredicates.emplace_back(std::move(Predicate)); 415344779Sdim continue; 416344779Sdim } 417344779Sdim 418344779Sdim STIPredicateFunction &PreviousDef = STIPredicates[It->second]; 419344779Sdim PreviousDef.addDefinition(R); 420344779Sdim } 421344779Sdim 422344779Sdim for (STIPredicateFunction &Fn : STIPredicates) 423344779Sdim processSTIPredicate(Fn, ProcModelMap); 424344779Sdim} 425344779Sdim 426344779Sdimvoid OpcodeInfo::addPredicateForProcModel(const llvm::APInt &CpuMask, 427344779Sdim const llvm::APInt &OperandMask, 428344779Sdim const Record *Predicate) { 429344779Sdim auto It = llvm::find_if( 430344779Sdim Predicates, [&OperandMask, &Predicate](const PredicateInfo &P) { 431344779Sdim return P.Predicate == Predicate && P.OperandMask == OperandMask; 432344779Sdim }); 433344779Sdim if (It == Predicates.end()) { 434344779Sdim Predicates.emplace_back(CpuMask, OperandMask, Predicate); 435344779Sdim return; 436344779Sdim } 437344779Sdim It->ProcModelMask |= CpuMask; 438344779Sdim} 439344779Sdim 440344779Sdimvoid CodeGenSchedModels::checkMCInstPredicates() const { 441344779Sdim RecVec MCPredicates = Records.getAllDerivedDefinitions("TIIPredicate"); 442344779Sdim if (MCPredicates.empty()) 443344779Sdim return; 444344779Sdim 445344779Sdim // A target cannot have multiple TIIPredicate definitions with a same name. 446344779Sdim llvm::StringMap<const Record *> TIIPredicates(MCPredicates.size()); 447344779Sdim for (const Record *TIIPred : MCPredicates) { 448344779Sdim StringRef Name = TIIPred->getValueAsString("FunctionName"); 449344779Sdim StringMap<const Record *>::const_iterator It = TIIPredicates.find(Name); 450344779Sdim if (It == TIIPredicates.end()) { 451344779Sdim TIIPredicates[Name] = TIIPred; 452344779Sdim continue; 453344779Sdim } 454344779Sdim 455344779Sdim PrintError(TIIPred->getLoc(), 456344779Sdim "TIIPredicate " + Name + " is multiply defined."); 457344779Sdim PrintNote(It->second->getLoc(), 458344779Sdim " Previous definition of " + Name + " was here."); 459344779Sdim PrintFatalError(TIIPred->getLoc(), 460344779Sdim "Found conflicting definitions of TIIPredicate."); 461344779Sdim } 462344779Sdim} 463344779Sdim 464341825Sdimvoid CodeGenSchedModels::collectRetireControlUnits() { 465341825Sdim RecVec Units = Records.getAllDerivedDefinitions("RetireControlUnit"); 466341825Sdim 467341825Sdim for (Record *RCU : Units) { 468341825Sdim CodeGenProcModel &PM = getProcModel(RCU->getValueAsDef("SchedModel")); 469341825Sdim if (PM.RetireControlUnit) { 470341825Sdim PrintError(RCU->getLoc(), 471341825Sdim "Expected a single RetireControlUnit definition"); 472341825Sdim PrintNote(PM.RetireControlUnit->getLoc(), 473341825Sdim "Previous definition of RetireControlUnit was here"); 474341825Sdim } 475341825Sdim PM.RetireControlUnit = RCU; 476341825Sdim } 477341825Sdim} 478341825Sdim 479344779Sdimvoid CodeGenSchedModels::collectLoadStoreQueueInfo() { 480344779Sdim RecVec Queues = Records.getAllDerivedDefinitions("MemoryQueue"); 481344779Sdim 482344779Sdim for (Record *Queue : Queues) { 483344779Sdim CodeGenProcModel &PM = getProcModel(Queue->getValueAsDef("SchedModel")); 484344779Sdim if (Queue->isSubClassOf("LoadQueue")) { 485344779Sdim if (PM.LoadQueue) { 486344779Sdim PrintError(Queue->getLoc(), 487344779Sdim "Expected a single LoadQueue definition"); 488344779Sdim PrintNote(PM.LoadQueue->getLoc(), 489344779Sdim "Previous definition of LoadQueue was here"); 490344779Sdim } 491344779Sdim 492344779Sdim PM.LoadQueue = Queue; 493344779Sdim } 494344779Sdim 495344779Sdim if (Queue->isSubClassOf("StoreQueue")) { 496344779Sdim if (PM.StoreQueue) { 497344779Sdim PrintError(Queue->getLoc(), 498344779Sdim "Expected a single StoreQueue definition"); 499344779Sdim PrintNote(PM.LoadQueue->getLoc(), 500344779Sdim "Previous definition of StoreQueue was here"); 501344779Sdim } 502344779Sdim 503344779Sdim PM.StoreQueue = Queue; 504344779Sdim } 505344779Sdim } 506344779Sdim} 507344779Sdim 508341825Sdim/// Collect optional processor information. 509341825Sdimvoid CodeGenSchedModels::collectOptionalProcessorInfo() { 510341825Sdim // Find register file definitions for each processor. 511341825Sdim collectRegisterFiles(); 512341825Sdim 513341825Sdim // Collect processor RetireControlUnit descriptors if available. 514341825Sdim collectRetireControlUnits(); 515341825Sdim 516344779Sdim // Collect information about load/store queues. 517344779Sdim collectLoadStoreQueueInfo(); 518341825Sdim 519341825Sdim checkCompleteness(); 520341825Sdim} 521341825Sdim 522243830Sdim/// Gather all processor models. 523243830Sdimvoid CodeGenSchedModels::collectProcModels() { 524243830Sdim RecVec ProcRecords = Records.getAllDerivedDefinitions("Processor"); 525344779Sdim llvm::sort(ProcRecords, LessRecordFieldName()); 526239310Sdim 527243830Sdim // Reserve space because we can. Reallocation would be ok. 528243830Sdim ProcModels.reserve(ProcRecords.size()+1); 529243830Sdim 530243830Sdim // Use idx=0 for NoModel/NoItineraries. 531243830Sdim Record *NoModelDef = Records.getDef("NoSchedModel"); 532243830Sdim Record *NoItinsDef = Records.getDef("NoItineraries"); 533288943Sdim ProcModels.emplace_back(0, "NoSchedModel", NoModelDef, NoItinsDef); 534243830Sdim ProcModelMap[NoModelDef] = 0; 535243830Sdim 536243830Sdim // For each processor, find a unique machine model. 537341825Sdim LLVM_DEBUG(dbgs() << "+++ PROCESSOR MODELs (addProcModel) +++\n"); 538327952Sdim for (Record *ProcRecord : ProcRecords) 539327952Sdim addProcModel(ProcRecord); 540243830Sdim} 541243830Sdim 542243830Sdim/// Get a unique processor model based on the defined MachineModel and 543243830Sdim/// ProcessorItineraries. 544243830Sdimvoid CodeGenSchedModels::addProcModel(Record *ProcDef) { 545243830Sdim Record *ModelKey = getModelOrItinDef(ProcDef); 546243830Sdim if (!ProcModelMap.insert(std::make_pair(ModelKey, ProcModels.size())).second) 547243830Sdim return; 548243830Sdim 549243830Sdim std::string Name = ModelKey->getName(); 550243830Sdim if (ModelKey->isSubClassOf("SchedMachineModel")) { 551243830Sdim Record *ItinsDef = ModelKey->getValueAsDef("Itineraries"); 552288943Sdim ProcModels.emplace_back(ProcModels.size(), Name, ModelKey, ItinsDef); 553243830Sdim } 554243830Sdim else { 555243830Sdim // An itinerary is defined without a machine model. Infer a new model. 556243830Sdim if (!ModelKey->getValueAsListOfDefs("IID").empty()) 557243830Sdim Name = Name + "Model"; 558288943Sdim ProcModels.emplace_back(ProcModels.size(), Name, 559288943Sdim ProcDef->getValueAsDef("SchedModel"), ModelKey); 560243830Sdim } 561341825Sdim LLVM_DEBUG(ProcModels.back().dump()); 562243830Sdim} 563243830Sdim 564243830Sdim// Recursively find all reachable SchedReadWrite records. 565243830Sdimstatic void scanSchedRW(Record *RWDef, RecVec &RWDefs, 566243830Sdim SmallPtrSet<Record*, 16> &RWSet) { 567280031Sdim if (!RWSet.insert(RWDef).second) 568243830Sdim return; 569243830Sdim RWDefs.push_back(RWDef); 570327952Sdim // Reads don't currently have sequence records, but it can be added later. 571243830Sdim if (RWDef->isSubClassOf("WriteSequence")) { 572243830Sdim RecVec Seq = RWDef->getValueAsListOfDefs("Writes"); 573327952Sdim for (Record *WSRec : Seq) 574327952Sdim scanSchedRW(WSRec, RWDefs, RWSet); 575243830Sdim } 576243830Sdim else if (RWDef->isSubClassOf("SchedVariant")) { 577243830Sdim // Visit each variant (guarded by a different predicate). 578243830Sdim RecVec Vars = RWDef->getValueAsListOfDefs("Variants"); 579327952Sdim for (Record *Variant : Vars) { 580243830Sdim // Visit each RW in the sequence selected by the current variant. 581327952Sdim RecVec Selected = Variant->getValueAsListOfDefs("Selected"); 582327952Sdim for (Record *SelDef : Selected) 583327952Sdim scanSchedRW(SelDef, RWDefs, RWSet); 584243830Sdim } 585243830Sdim } 586243830Sdim} 587243830Sdim 588243830Sdim// Collect and sort all SchedReadWrites reachable via tablegen records. 589243830Sdim// More may be inferred later when inferring new SchedClasses from variants. 590243830Sdimvoid CodeGenSchedModels::collectSchedRW() { 591243830Sdim // Reserve idx=0 for invalid writes/reads. 592243830Sdim SchedWrites.resize(1); 593243830Sdim SchedReads.resize(1); 594243830Sdim 595243830Sdim SmallPtrSet<Record*, 16> RWSet; 596243830Sdim 597243830Sdim // Find all SchedReadWrites referenced by instruction defs. 598243830Sdim RecVec SWDefs, SRDefs; 599309124Sdim for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) { 600280031Sdim Record *SchedDef = Inst->TheDef; 601249423Sdim if (SchedDef->isValueUnset("SchedRW")) 602243830Sdim continue; 603243830Sdim RecVec RWs = SchedDef->getValueAsListOfDefs("SchedRW"); 604327952Sdim for (Record *RW : RWs) { 605327952Sdim if (RW->isSubClassOf("SchedWrite")) 606327952Sdim scanSchedRW(RW, SWDefs, RWSet); 607243830Sdim else { 608327952Sdim assert(RW->isSubClassOf("SchedRead") && "Unknown SchedReadWrite"); 609327952Sdim scanSchedRW(RW, SRDefs, RWSet); 610243830Sdim } 611243830Sdim } 612243830Sdim } 613243830Sdim // Find all ReadWrites referenced by InstRW. 614243830Sdim RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW"); 615327952Sdim for (Record *InstRWDef : InstRWDefs) { 616243830Sdim // For all OperandReadWrites. 617327952Sdim RecVec RWDefs = InstRWDef->getValueAsListOfDefs("OperandReadWrites"); 618327952Sdim for (Record *RWDef : RWDefs) { 619327952Sdim if (RWDef->isSubClassOf("SchedWrite")) 620327952Sdim scanSchedRW(RWDef, SWDefs, RWSet); 621243830Sdim else { 622327952Sdim assert(RWDef->isSubClassOf("SchedRead") && "Unknown SchedReadWrite"); 623327952Sdim scanSchedRW(RWDef, SRDefs, RWSet); 624243830Sdim } 625243830Sdim } 626243830Sdim } 627243830Sdim // Find all ReadWrites referenced by ItinRW. 628243830Sdim RecVec ItinRWDefs = Records.getAllDerivedDefinitions("ItinRW"); 629327952Sdim for (Record *ItinRWDef : ItinRWDefs) { 630243830Sdim // For all OperandReadWrites. 631327952Sdim RecVec RWDefs = ItinRWDef->getValueAsListOfDefs("OperandReadWrites"); 632327952Sdim for (Record *RWDef : RWDefs) { 633327952Sdim if (RWDef->isSubClassOf("SchedWrite")) 634327952Sdim scanSchedRW(RWDef, SWDefs, RWSet); 635243830Sdim else { 636327952Sdim assert(RWDef->isSubClassOf("SchedRead") && "Unknown SchedReadWrite"); 637327952Sdim scanSchedRW(RWDef, SRDefs, RWSet); 638243830Sdim } 639243830Sdim } 640243830Sdim } 641243830Sdim // Find all ReadWrites referenced by SchedAlias. AliasDefs needs to be sorted 642243830Sdim // for the loop below that initializes Alias vectors. 643243830Sdim RecVec AliasDefs = Records.getAllDerivedDefinitions("SchedAlias"); 644344779Sdim llvm::sort(AliasDefs, LessRecord()); 645327952Sdim for (Record *ADef : AliasDefs) { 646327952Sdim Record *MatchDef = ADef->getValueAsDef("MatchRW"); 647327952Sdim Record *AliasDef = ADef->getValueAsDef("AliasRW"); 648243830Sdim if (MatchDef->isSubClassOf("SchedWrite")) { 649243830Sdim if (!AliasDef->isSubClassOf("SchedWrite")) 650327952Sdim PrintFatalError(ADef->getLoc(), "SchedWrite Alias must be SchedWrite"); 651243830Sdim scanSchedRW(AliasDef, SWDefs, RWSet); 652243830Sdim } 653243830Sdim else { 654243830Sdim assert(MatchDef->isSubClassOf("SchedRead") && "Unknown SchedReadWrite"); 655243830Sdim if (!AliasDef->isSubClassOf("SchedRead")) 656327952Sdim PrintFatalError(ADef->getLoc(), "SchedRead Alias must be SchedRead"); 657243830Sdim scanSchedRW(AliasDef, SRDefs, RWSet); 658243830Sdim } 659243830Sdim } 660243830Sdim // Sort and add the SchedReadWrites directly referenced by instructions or 661243830Sdim // itinerary resources. Index reads and writes in separate domains. 662344779Sdim llvm::sort(SWDefs, LessRecord()); 663327952Sdim for (Record *SWDef : SWDefs) { 664327952Sdim assert(!getSchedRWIdx(SWDef, /*IsRead=*/false) && "duplicate SchedWrite"); 665327952Sdim SchedWrites.emplace_back(SchedWrites.size(), SWDef); 666243830Sdim } 667344779Sdim llvm::sort(SRDefs, LessRecord()); 668327952Sdim for (Record *SRDef : SRDefs) { 669327952Sdim assert(!getSchedRWIdx(SRDef, /*IsRead-*/true) && "duplicate SchedWrite"); 670327952Sdim SchedReads.emplace_back(SchedReads.size(), SRDef); 671243830Sdim } 672243830Sdim // Initialize WriteSequence vectors. 673327952Sdim for (CodeGenSchedRW &CGRW : SchedWrites) { 674327952Sdim if (!CGRW.IsSequence) 675243830Sdim continue; 676327952Sdim findRWs(CGRW.TheDef->getValueAsListOfDefs("Writes"), CGRW.Sequence, 677243830Sdim /*IsRead=*/false); 678243830Sdim } 679243830Sdim // Initialize Aliases vectors. 680327952Sdim for (Record *ADef : AliasDefs) { 681327952Sdim Record *AliasDef = ADef->getValueAsDef("AliasRW"); 682243830Sdim getSchedRW(AliasDef).IsAlias = true; 683327952Sdim Record *MatchDef = ADef->getValueAsDef("MatchRW"); 684243830Sdim CodeGenSchedRW &RW = getSchedRW(MatchDef); 685243830Sdim if (RW.IsAlias) 686327952Sdim PrintFatalError(ADef->getLoc(), "Cannot Alias an Alias"); 687327952Sdim RW.Aliases.push_back(ADef); 688243830Sdim } 689341825Sdim LLVM_DEBUG( 690341825Sdim dbgs() << "\n+++ SCHED READS and WRITES (collectSchedRW) +++\n"; 691341825Sdim for (unsigned WIdx = 0, WEnd = SchedWrites.size(); WIdx != WEnd; ++WIdx) { 692341825Sdim dbgs() << WIdx << ": "; 693341825Sdim SchedWrites[WIdx].dump(); 694341825Sdim dbgs() << '\n'; 695341825Sdim } for (unsigned RIdx = 0, REnd = SchedReads.size(); RIdx != REnd; 696341825Sdim ++RIdx) { 697341825Sdim dbgs() << RIdx << ": "; 698341825Sdim SchedReads[RIdx].dump(); 699341825Sdim dbgs() << '\n'; 700341825Sdim } RecVec RWDefs = Records.getAllDerivedDefinitions("SchedReadWrite"); 701341825Sdim for (Record *RWDef 702341825Sdim : RWDefs) { 703341825Sdim if (!getSchedRWIdx(RWDef, RWDef->isSubClassOf("SchedRead"))) { 704341825Sdim StringRef Name = RWDef->getName(); 705341825Sdim if (Name != "NoWrite" && Name != "ReadDefault") 706341825Sdim dbgs() << "Unused SchedReadWrite " << Name << '\n'; 707341825Sdim } 708341825Sdim }); 709243830Sdim} 710243830Sdim 711243830Sdim/// Compute a SchedWrite name from a sequence of writes. 712296417Sdimstd::string CodeGenSchedModels::genRWName(ArrayRef<unsigned> Seq, bool IsRead) { 713243830Sdim std::string Name("("); 714296417Sdim for (auto I = Seq.begin(), E = Seq.end(); I != E; ++I) { 715243830Sdim if (I != Seq.begin()) 716243830Sdim Name += '_'; 717243830Sdim Name += getSchedRW(*I, IsRead).Name; 718243830Sdim } 719243830Sdim Name += ')'; 720243830Sdim return Name; 721243830Sdim} 722243830Sdim 723341825Sdimunsigned CodeGenSchedModels::getSchedRWIdx(const Record *Def, 724341825Sdim bool IsRead) const { 725243830Sdim const std::vector<CodeGenSchedRW> &RWVec = IsRead ? SchedReads : SchedWrites; 726341825Sdim const auto I = find_if( 727341825Sdim RWVec, [Def](const CodeGenSchedRW &RW) { return RW.TheDef == Def; }); 728341825Sdim return I == RWVec.end() ? 0 : std::distance(RWVec.begin(), I); 729243830Sdim} 730243830Sdim 731243830Sdimbool CodeGenSchedModels::hasReadOfWrite(Record *WriteDef) const { 732327952Sdim for (const CodeGenSchedRW &Read : SchedReads) { 733327952Sdim Record *ReadDef = Read.TheDef; 734243830Sdim if (!ReadDef || !ReadDef->isSubClassOf("ProcReadAdvance")) 735243830Sdim continue; 736243830Sdim 737243830Sdim RecVec ValidWrites = ReadDef->getValueAsListOfDefs("ValidWrites"); 738314564Sdim if (is_contained(ValidWrites, WriteDef)) { 739243830Sdim return true; 740243830Sdim } 741243830Sdim } 742243830Sdim return false; 743243830Sdim} 744243830Sdim 745341825Sdimstatic void splitSchedReadWrites(const RecVec &RWDefs, 746341825Sdim RecVec &WriteDefs, RecVec &ReadDefs) { 747327952Sdim for (Record *RWDef : RWDefs) { 748327952Sdim if (RWDef->isSubClassOf("SchedWrite")) 749327952Sdim WriteDefs.push_back(RWDef); 750243830Sdim else { 751327952Sdim assert(RWDef->isSubClassOf("SchedRead") && "unknown SchedReadWrite"); 752327952Sdim ReadDefs.push_back(RWDef); 753243830Sdim } 754243830Sdim } 755243830Sdim} 756243830Sdim 757243830Sdim// Split the SchedReadWrites defs and call findRWs for each list. 758243830Sdimvoid CodeGenSchedModels::findRWs(const RecVec &RWDefs, 759243830Sdim IdxVec &Writes, IdxVec &Reads) const { 760341825Sdim RecVec WriteDefs; 761341825Sdim RecVec ReadDefs; 762341825Sdim splitSchedReadWrites(RWDefs, WriteDefs, ReadDefs); 763341825Sdim findRWs(WriteDefs, Writes, false); 764341825Sdim findRWs(ReadDefs, Reads, true); 765243830Sdim} 766243830Sdim 767243830Sdim// Call getSchedRWIdx for all elements in a sequence of SchedRW defs. 768243830Sdimvoid CodeGenSchedModels::findRWs(const RecVec &RWDefs, IdxVec &RWs, 769243830Sdim bool IsRead) const { 770327952Sdim for (Record *RWDef : RWDefs) { 771327952Sdim unsigned Idx = getSchedRWIdx(RWDef, IsRead); 772243830Sdim assert(Idx && "failed to collect SchedReadWrite"); 773243830Sdim RWs.push_back(Idx); 774243830Sdim } 775243830Sdim} 776243830Sdim 777243830Sdimvoid CodeGenSchedModels::expandRWSequence(unsigned RWIdx, IdxVec &RWSeq, 778243830Sdim bool IsRead) const { 779243830Sdim const CodeGenSchedRW &SchedRW = getSchedRW(RWIdx, IsRead); 780243830Sdim if (!SchedRW.IsSequence) { 781243830Sdim RWSeq.push_back(RWIdx); 782243830Sdim return; 783243830Sdim } 784243830Sdim int Repeat = 785243830Sdim SchedRW.TheDef ? SchedRW.TheDef->getValueAsInt("Repeat") : 1; 786243830Sdim for (int i = 0; i < Repeat; ++i) { 787327952Sdim for (unsigned I : SchedRW.Sequence) { 788327952Sdim expandRWSequence(I, RWSeq, IsRead); 789243830Sdim } 790243830Sdim } 791243830Sdim} 792243830Sdim 793243830Sdim// Expand a SchedWrite as a sequence following any aliases that coincide with 794243830Sdim// the given processor model. 795243830Sdimvoid CodeGenSchedModels::expandRWSeqForProc( 796243830Sdim unsigned RWIdx, IdxVec &RWSeq, bool IsRead, 797243830Sdim const CodeGenProcModel &ProcModel) const { 798243830Sdim 799243830Sdim const CodeGenSchedRW &SchedWrite = getSchedRW(RWIdx, IsRead); 800276479Sdim Record *AliasDef = nullptr; 801341825Sdim for (const Record *Rec : SchedWrite.Aliases) { 802341825Sdim const CodeGenSchedRW &AliasRW = getSchedRW(Rec->getValueAsDef("AliasRW")); 803341825Sdim if (Rec->getValueInit("SchedModel")->isComplete()) { 804341825Sdim Record *ModelDef = Rec->getValueAsDef("SchedModel"); 805243830Sdim if (&getProcModel(ModelDef) != &ProcModel) 806243830Sdim continue; 807243830Sdim } 808243830Sdim if (AliasDef) 809243830Sdim PrintFatalError(AliasRW.TheDef->getLoc(), "Multiple aliases " 810243830Sdim "defined for processor " + ProcModel.ModelName + 811243830Sdim " Ensure only one SchedAlias exists per RW."); 812243830Sdim AliasDef = AliasRW.TheDef; 813243830Sdim } 814243830Sdim if (AliasDef) { 815243830Sdim expandRWSeqForProc(getSchedRWIdx(AliasDef, IsRead), 816243830Sdim RWSeq, IsRead,ProcModel); 817243830Sdim return; 818243830Sdim } 819243830Sdim if (!SchedWrite.IsSequence) { 820243830Sdim RWSeq.push_back(RWIdx); 821243830Sdim return; 822243830Sdim } 823243830Sdim int Repeat = 824243830Sdim SchedWrite.TheDef ? SchedWrite.TheDef->getValueAsInt("Repeat") : 1; 825341825Sdim for (int I = 0, E = Repeat; I < E; ++I) { 826341825Sdim for (unsigned Idx : SchedWrite.Sequence) { 827341825Sdim expandRWSeqForProc(Idx, RWSeq, IsRead, ProcModel); 828243830Sdim } 829243830Sdim } 830243830Sdim} 831243830Sdim 832243830Sdim// Find the existing SchedWrite that models this sequence of writes. 833296417Sdimunsigned CodeGenSchedModels::findRWForSequence(ArrayRef<unsigned> Seq, 834243830Sdim bool IsRead) { 835243830Sdim std::vector<CodeGenSchedRW> &RWVec = IsRead ? SchedReads : SchedWrites; 836243830Sdim 837341825Sdim auto I = find_if(RWVec, [Seq](CodeGenSchedRW &RW) { 838341825Sdim return makeArrayRef(RW.Sequence) == Seq; 839341825Sdim }); 840243830Sdim // Index zero reserved for invalid RW. 841341825Sdim return I == RWVec.end() ? 0 : std::distance(RWVec.begin(), I); 842243830Sdim} 843243830Sdim 844243830Sdim/// Add this ReadWrite if it doesn't already exist. 845243830Sdimunsigned CodeGenSchedModels::findOrInsertRW(ArrayRef<unsigned> Seq, 846243830Sdim bool IsRead) { 847243830Sdim assert(!Seq.empty() && "cannot insert empty sequence"); 848243830Sdim if (Seq.size() == 1) 849243830Sdim return Seq.back(); 850243830Sdim 851243830Sdim unsigned Idx = findRWForSequence(Seq, IsRead); 852243830Sdim if (Idx) 853243830Sdim return Idx; 854243830Sdim 855341825Sdim std::vector<CodeGenSchedRW> &RWVec = IsRead ? SchedReads : SchedWrites; 856341825Sdim unsigned RWIdx = RWVec.size(); 857243830Sdim CodeGenSchedRW SchedRW(RWIdx, IsRead, Seq, genRWName(Seq, IsRead)); 858341825Sdim RWVec.push_back(SchedRW); 859243830Sdim return RWIdx; 860243830Sdim} 861243830Sdim 862243830Sdim/// Visit all the instruction definitions for this target to gather and 863243830Sdim/// enumerate the itinerary classes. These are the explicitly specified 864243830Sdim/// SchedClasses. More SchedClasses may be inferred. 865243830Sdimvoid CodeGenSchedModels::collectSchedClasses() { 866243830Sdim 867243830Sdim // NoItinerary is always the first class at Idx=0 868341825Sdim assert(SchedClasses.empty() && "Expected empty sched class"); 869341825Sdim SchedClasses.emplace_back(0, "NoInstrModel", 870341825Sdim Records.getDef("NoItinerary")); 871243830Sdim SchedClasses.back().ProcIndices.push_back(0); 872239310Sdim 873249423Sdim // Create a SchedClass for each unique combination of itinerary class and 874249423Sdim // SchedRW list. 875309124Sdim for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) { 876280031Sdim Record *ItinDef = Inst->TheDef->getValueAsDef("Itinerary"); 877243830Sdim IdxVec Writes, Reads; 878280031Sdim if (!Inst->TheDef->isValueUnset("SchedRW")) 879280031Sdim findRWs(Inst->TheDef->getValueAsListOfDefs("SchedRW"), Writes, Reads); 880249423Sdim 881243830Sdim // ProcIdx == 0 indicates the class applies to all processors. 882341825Sdim unsigned SCIdx = addSchedClass(ItinDef, Writes, Reads, /*ProcIndices*/{0}); 883280031Sdim InstrClassMap[Inst->TheDef] = SCIdx; 884243830Sdim } 885243830Sdim // Create classes for InstRW defs. 886243830Sdim RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW"); 887344779Sdim llvm::sort(InstRWDefs, LessRecord()); 888341825Sdim LLVM_DEBUG(dbgs() << "\n+++ SCHED CLASSES (createInstRWClass) +++\n"); 889327952Sdim for (Record *RWDef : InstRWDefs) 890327952Sdim createInstRWClass(RWDef); 891239310Sdim 892243830Sdim NumInstrSchedClasses = SchedClasses.size(); 893243830Sdim 894243830Sdim bool EnableDump = false; 895341825Sdim LLVM_DEBUG(EnableDump = true); 896243830Sdim if (!EnableDump) 897243830Sdim return; 898249423Sdim 899341825Sdim LLVM_DEBUG( 900341825Sdim dbgs() 901341825Sdim << "\n+++ ITINERARIES and/or MACHINE MODELS (collectSchedClasses) +++\n"); 902309124Sdim for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) { 903321369Sdim StringRef InstName = Inst->TheDef->getName(); 904341825Sdim unsigned SCIdx = getSchedClassIdx(*Inst); 905249423Sdim if (!SCIdx) { 906341825Sdim LLVM_DEBUG({ 907341825Sdim if (!Inst->hasNoSchedulingInfo) 908341825Sdim dbgs() << "No machine model for " << Inst->TheDef->getName() << '\n'; 909341825Sdim }); 910249423Sdim continue; 911249423Sdim } 912249423Sdim CodeGenSchedClass &SC = getSchedClass(SCIdx); 913249423Sdim if (SC.ProcIndices[0] != 0) 914280031Sdim PrintFatalError(Inst->TheDef->getLoc(), "Instruction's sched class " 915249423Sdim "must not be subtarget specific."); 916249423Sdim 917249423Sdim IdxVec ProcIndices; 918249423Sdim if (SC.ItinClassDef->getName() != "NoItinerary") { 919249423Sdim ProcIndices.push_back(0); 920249423Sdim dbgs() << "Itinerary for " << InstName << ": " 921249423Sdim << SC.ItinClassDef->getName() << '\n'; 922249423Sdim } 923249423Sdim if (!SC.Writes.empty()) { 924249423Sdim ProcIndices.push_back(0); 925341825Sdim LLVM_DEBUG({ 926341825Sdim dbgs() << "SchedRW machine model for " << InstName; 927341825Sdim for (IdxIter WI = SC.Writes.begin(), WE = SC.Writes.end(); WI != WE; 928341825Sdim ++WI) 929341825Sdim dbgs() << " " << SchedWrites[*WI].Name; 930341825Sdim for (IdxIter RI = SC.Reads.begin(), RE = SC.Reads.end(); RI != RE; ++RI) 931341825Sdim dbgs() << " " << SchedReads[*RI].Name; 932341825Sdim dbgs() << '\n'; 933341825Sdim }); 934249423Sdim } 935249423Sdim const RecVec &RWDefs = SchedClasses[SCIdx].InstRWs; 936327952Sdim for (Record *RWDef : RWDefs) { 937249423Sdim const CodeGenProcModel &ProcModel = 938341825Sdim getProcModel(RWDef->getValueAsDef("SchedModel")); 939249423Sdim ProcIndices.push_back(ProcModel.Index); 940341825Sdim LLVM_DEBUG(dbgs() << "InstRW on " << ProcModel.ModelName << " for " 941341825Sdim << InstName); 942243830Sdim IdxVec Writes; 943243830Sdim IdxVec Reads; 944327952Sdim findRWs(RWDef->getValueAsListOfDefs("OperandReadWrites"), 945249423Sdim Writes, Reads); 946341825Sdim LLVM_DEBUG({ 947341825Sdim for (unsigned WIdx : Writes) 948341825Sdim dbgs() << " " << SchedWrites[WIdx].Name; 949341825Sdim for (unsigned RIdx : Reads) 950341825Sdim dbgs() << " " << SchedReads[RIdx].Name; 951341825Sdim dbgs() << '\n'; 952341825Sdim }); 953243830Sdim } 954314564Sdim // If ProcIndices contains zero, the class applies to all processors. 955341825Sdim LLVM_DEBUG({ 956341825Sdim if (!std::count(ProcIndices.begin(), ProcIndices.end(), 0)) { 957341825Sdim for (const CodeGenProcModel &PM : ProcModels) { 958341825Sdim if (!std::count(ProcIndices.begin(), ProcIndices.end(), PM.Index)) 959341825Sdim dbgs() << "No machine model for " << Inst->TheDef->getName() 960341825Sdim << " on processor " << PM.ModelName << '\n'; 961341825Sdim } 962314564Sdim } 963341825Sdim }); 964243830Sdim } 965239310Sdim} 966239310Sdim 967243830Sdim// Get the SchedClass index for an instruction. 968341825Sdimunsigned 969341825SdimCodeGenSchedModels::getSchedClassIdx(const CodeGenInstruction &Inst) const { 970249423Sdim return InstrClassMap.lookup(Inst.TheDef); 971243830Sdim} 972239310Sdim 973296417Sdimstd::string 974296417SdimCodeGenSchedModels::createSchedClassName(Record *ItinClassDef, 975296417Sdim ArrayRef<unsigned> OperWrites, 976296417Sdim ArrayRef<unsigned> OperReads) { 977243830Sdim 978243830Sdim std::string Name; 979249423Sdim if (ItinClassDef && ItinClassDef->getName() != "NoItinerary") 980249423Sdim Name = ItinClassDef->getName(); 981296417Sdim for (unsigned Idx : OperWrites) { 982249423Sdim if (!Name.empty()) 983243830Sdim Name += '_'; 984296417Sdim Name += SchedWrites[Idx].Name; 985243830Sdim } 986296417Sdim for (unsigned Idx : OperReads) { 987243830Sdim Name += '_'; 988296417Sdim Name += SchedReads[Idx].Name; 989243830Sdim } 990243830Sdim return Name; 991243830Sdim} 992243830Sdim 993243830Sdimstd::string CodeGenSchedModels::createSchedClassName(const RecVec &InstDefs) { 994243830Sdim 995243830Sdim std::string Name; 996243830Sdim for (RecIter I = InstDefs.begin(), E = InstDefs.end(); I != E; ++I) { 997243830Sdim if (I != InstDefs.begin()) 998243830Sdim Name += '_'; 999243830Sdim Name += (*I)->getName(); 1000243830Sdim } 1001243830Sdim return Name; 1002243830Sdim} 1003243830Sdim 1004249423Sdim/// Add an inferred sched class from an itinerary class and per-operand list of 1005249423Sdim/// SchedWrites and SchedReads. ProcIndices contains the set of IDs of 1006249423Sdim/// processors that may utilize this class. 1007249423Sdimunsigned CodeGenSchedModels::addSchedClass(Record *ItinClassDef, 1008296417Sdim ArrayRef<unsigned> OperWrites, 1009296417Sdim ArrayRef<unsigned> OperReads, 1010296417Sdim ArrayRef<unsigned> ProcIndices) { 1011243830Sdim assert(!ProcIndices.empty() && "expect at least one ProcIdx"); 1012243830Sdim 1013341825Sdim auto IsKeyEqual = [=](const CodeGenSchedClass &SC) { 1014341825Sdim return SC.isKeyEqual(ItinClassDef, OperWrites, OperReads); 1015341825Sdim }; 1016341825Sdim 1017341825Sdim auto I = find_if(make_range(schedClassBegin(), schedClassEnd()), IsKeyEqual); 1018341825Sdim unsigned Idx = I == schedClassEnd() ? 0 : std::distance(schedClassBegin(), I); 1019249423Sdim if (Idx || SchedClasses[0].isKeyEqual(ItinClassDef, OperWrites, OperReads)) { 1020243830Sdim IdxVec PI; 1021243830Sdim std::set_union(SchedClasses[Idx].ProcIndices.begin(), 1022243830Sdim SchedClasses[Idx].ProcIndices.end(), 1023243830Sdim ProcIndices.begin(), ProcIndices.end(), 1024243830Sdim std::back_inserter(PI)); 1025341825Sdim SchedClasses[Idx].ProcIndices = std::move(PI); 1026243830Sdim return Idx; 1027243830Sdim } 1028243830Sdim Idx = SchedClasses.size(); 1029341825Sdim SchedClasses.emplace_back(Idx, 1030341825Sdim createSchedClassName(ItinClassDef, OperWrites, 1031341825Sdim OperReads), 1032341825Sdim ItinClassDef); 1033243830Sdim CodeGenSchedClass &SC = SchedClasses.back(); 1034243830Sdim SC.Writes = OperWrites; 1035243830Sdim SC.Reads = OperReads; 1036243830Sdim SC.ProcIndices = ProcIndices; 1037243830Sdim 1038243830Sdim return Idx; 1039243830Sdim} 1040243830Sdim 1041243830Sdim// Create classes for each set of opcodes that are in the same InstReadWrite 1042243830Sdim// definition across all processors. 1043243830Sdimvoid CodeGenSchedModels::createInstRWClass(Record *InstRWDef) { 1044243830Sdim // ClassInstrs will hold an entry for each subset of Instrs in InstRWDef that 1045243830Sdim // intersects with an existing class via a previous InstRWDef. Instrs that do 1046243830Sdim // not intersect with an existing class refer back to their former class as 1047243830Sdim // determined from ItinDef or SchedRW. 1048341825Sdim SmallMapVector<unsigned, SmallVector<Record *, 8>, 4> ClassInstrs; 1049243830Sdim // Sort Instrs into sets. 1050243830Sdim const RecVec *InstDefs = Sets.expand(InstRWDef); 1051243830Sdim if (InstDefs->empty()) 1052243830Sdim PrintFatalError(InstRWDef->getLoc(), "No matching instruction opcodes"); 1053243830Sdim 1054341825Sdim for (Record *InstDef : *InstDefs) { 1055327952Sdim InstClassMapTy::const_iterator Pos = InstrClassMap.find(InstDef); 1056249423Sdim if (Pos == InstrClassMap.end()) 1057327952Sdim PrintFatalError(InstDef->getLoc(), "No sched class for instruction."); 1058249423Sdim unsigned SCIdx = Pos->second; 1059341825Sdim ClassInstrs[SCIdx].push_back(InstDef); 1060239310Sdim } 1061243830Sdim // For each set of Instrs, create a new class if necessary, and map or remap 1062243830Sdim // the Instrs to it. 1063341825Sdim for (auto &Entry : ClassInstrs) { 1064341825Sdim unsigned OldSCIdx = Entry.first; 1065341825Sdim ArrayRef<Record*> InstDefs = Entry.second; 1066243830Sdim // If the all instrs in the current class are accounted for, then leave 1067243830Sdim // them mapped to their old class. 1068261991Sdim if (OldSCIdx) { 1069261991Sdim const RecVec &RWDefs = SchedClasses[OldSCIdx].InstRWs; 1070261991Sdim if (!RWDefs.empty()) { 1071261991Sdim const RecVec *OrigInstDefs = Sets.expand(RWDefs[0]); 1072341825Sdim unsigned OrigNumInstrs = 1073341825Sdim count_if(*OrigInstDefs, [&](Record *OIDef) { 1074341825Sdim return InstrClassMap[OIDef] == OldSCIdx; 1075341825Sdim }); 1076261991Sdim if (OrigNumInstrs == InstDefs.size()) { 1077261991Sdim assert(SchedClasses[OldSCIdx].ProcIndices[0] == 0 && 1078261991Sdim "expected a generic SchedClass"); 1079341825Sdim Record *RWModelDef = InstRWDef->getValueAsDef("SchedModel"); 1080341825Sdim // Make sure we didn't already have a InstRW containing this 1081341825Sdim // instruction on this model. 1082341825Sdim for (Record *RWD : RWDefs) { 1083341825Sdim if (RWD->getValueAsDef("SchedModel") == RWModelDef && 1084341825Sdim RWModelDef->getValueAsBit("FullInstRWOverlapCheck")) { 1085341825Sdim for (Record *Inst : InstDefs) { 1086360784Sdim PrintFatalError 1087360784Sdim (InstRWDef->getLoc(), 1088360784Sdim "Overlapping InstRW definition for \"" + 1089360784Sdim Inst->getName() + 1090360784Sdim "\" also matches previous \"" + 1091360784Sdim RWD->getValue("Instrs")->getValue()->getAsString() + 1092360784Sdim "\"."); 1093341825Sdim } 1094341825Sdim } 1095341825Sdim } 1096341825Sdim LLVM_DEBUG(dbgs() << "InstRW: Reuse SC " << OldSCIdx << ":" 1097341825Sdim << SchedClasses[OldSCIdx].Name << " on " 1098341825Sdim << RWModelDef->getName() << "\n"); 1099261991Sdim SchedClasses[OldSCIdx].InstRWs.push_back(InstRWDef); 1100261991Sdim continue; 1101261991Sdim } 1102261991Sdim } 1103243830Sdim } 1104243830Sdim unsigned SCIdx = SchedClasses.size(); 1105341825Sdim SchedClasses.emplace_back(SCIdx, createSchedClassName(InstDefs), nullptr); 1106243830Sdim CodeGenSchedClass &SC = SchedClasses.back(); 1107341825Sdim LLVM_DEBUG(dbgs() << "InstRW: New SC " << SCIdx << ":" << SC.Name << " on " 1108341825Sdim << InstRWDef->getValueAsDef("SchedModel")->getName() 1109341825Sdim << "\n"); 1110261991Sdim 1111243830Sdim // Preserve ItinDef and Writes/Reads for processors without an InstRW entry. 1112243830Sdim SC.ItinClassDef = SchedClasses[OldSCIdx].ItinClassDef; 1113243830Sdim SC.Writes = SchedClasses[OldSCIdx].Writes; 1114243830Sdim SC.Reads = SchedClasses[OldSCIdx].Reads; 1115243830Sdim SC.ProcIndices.push_back(0); 1116341825Sdim // If we had an old class, copy it's InstRWs to this new class. 1117341825Sdim if (OldSCIdx) { 1118341825Sdim Record *RWModelDef = InstRWDef->getValueAsDef("SchedModel"); 1119341825Sdim for (Record *OldRWDef : SchedClasses[OldSCIdx].InstRWs) { 1120341825Sdim if (OldRWDef->getValueAsDef("SchedModel") == RWModelDef) { 1121341825Sdim for (Record *InstDef : InstDefs) { 1122360784Sdim PrintFatalError 1123360784Sdim (InstRWDef->getLoc(), 1124360784Sdim "Overlapping InstRW definition for \"" + 1125360784Sdim InstDef->getName() + 1126360784Sdim "\" also matches previous \"" + 1127360784Sdim OldRWDef->getValue("Instrs")->getValue()->getAsString() + 1128360784Sdim "\"."); 1129243830Sdim } 1130243830Sdim } 1131341825Sdim assert(OldRWDef != InstRWDef && 1132341825Sdim "SchedClass has duplicate InstRW def"); 1133341825Sdim SC.InstRWs.push_back(OldRWDef); 1134243830Sdim } 1135243830Sdim } 1136341825Sdim // Map each Instr to this new class. 1137341825Sdim for (Record *InstDef : InstDefs) 1138341825Sdim InstrClassMap[InstDef] = SCIdx; 1139243830Sdim SC.InstRWs.push_back(InstRWDef); 1140243830Sdim } 1141243830Sdim} 1142243830Sdim 1143249423Sdim// True if collectProcItins found anything. 1144249423Sdimbool CodeGenSchedModels::hasItineraries() const { 1145341825Sdim for (const CodeGenProcModel &PM : make_range(procModelBegin(),procModelEnd())) 1146327952Sdim if (PM.hasItineraries()) 1147249423Sdim return true; 1148249423Sdim return false; 1149249423Sdim} 1150249423Sdim 1151243830Sdim// Gather the processor itineraries. 1152243830Sdimvoid CodeGenSchedModels::collectProcItins() { 1153341825Sdim LLVM_DEBUG(dbgs() << "\n+++ PROBLEM ITINERARIES (collectProcItins) +++\n"); 1154280031Sdim for (CodeGenProcModel &ProcModel : ProcModels) { 1155249423Sdim if (!ProcModel.hasItineraries()) 1156243830Sdim continue; 1157243830Sdim 1158249423Sdim RecVec ItinRecords = ProcModel.ItinsDef->getValueAsListOfDefs("IID"); 1159249423Sdim assert(!ItinRecords.empty() && "ProcModel.hasItineraries is incorrect"); 1160243830Sdim 1161249423Sdim // Populate ItinDefList with Itinerary records. 1162249423Sdim ProcModel.ItinDefList.resize(NumInstrSchedClasses); 1163249423Sdim 1164243830Sdim // Insert each itinerary data record in the correct position within 1165243830Sdim // the processor model's ItinDefList. 1166327952Sdim for (Record *ItinData : ItinRecords) { 1167341825Sdim const Record *ItinDef = ItinData->getValueAsDef("TheClass"); 1168249423Sdim bool FoundClass = false; 1169341825Sdim 1170341825Sdim for (const CodeGenSchedClass &SC : 1171341825Sdim make_range(schedClassBegin(), schedClassEnd())) { 1172249423Sdim // Multiple SchedClasses may share an itinerary. Update all of them. 1173341825Sdim if (SC.ItinClassDef == ItinDef) { 1174341825Sdim ProcModel.ItinDefList[SC.Index] = ItinData; 1175249423Sdim FoundClass = true; 1176249423Sdim } 1177249423Sdim } 1178249423Sdim if (!FoundClass) { 1179341825Sdim LLVM_DEBUG(dbgs() << ProcModel.ItinsDef->getName() 1180341825Sdim << " missing class for itinerary " 1181341825Sdim << ItinDef->getName() << '\n'); 1182243830Sdim } 1183243830Sdim } 1184243830Sdim // Check for missing itinerary entries. 1185243830Sdim assert(!ProcModel.ItinDefList[0] && "NoItinerary class can't have rec"); 1186341825Sdim LLVM_DEBUG( 1187341825Sdim for (unsigned i = 1, N = ProcModel.ItinDefList.size(); i < N; ++i) { 1188341825Sdim if (!ProcModel.ItinDefList[i]) 1189341825Sdim dbgs() << ProcModel.ItinsDef->getName() 1190341825Sdim << " missing itinerary for class " << SchedClasses[i].Name 1191341825Sdim << '\n'; 1192341825Sdim }); 1193243830Sdim } 1194243830Sdim} 1195243830Sdim 1196243830Sdim// Gather the read/write types for each itinerary class. 1197243830Sdimvoid CodeGenSchedModels::collectProcItinRW() { 1198243830Sdim RecVec ItinRWDefs = Records.getAllDerivedDefinitions("ItinRW"); 1199344779Sdim llvm::sort(ItinRWDefs, LessRecord()); 1200327952Sdim for (Record *RWDef : ItinRWDefs) { 1201327952Sdim if (!RWDef->getValueInit("SchedModel")->isComplete()) 1202327952Sdim PrintFatalError(RWDef->getLoc(), "SchedModel is undefined"); 1203327952Sdim Record *ModelDef = RWDef->getValueAsDef("SchedModel"); 1204243830Sdim ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef); 1205243830Sdim if (I == ProcModelMap.end()) { 1206327952Sdim PrintFatalError(RWDef->getLoc(), "Undefined SchedMachineModel " 1207243830Sdim + ModelDef->getName()); 1208243830Sdim } 1209327952Sdim ProcModels[I->second].ItinRWDefs.push_back(RWDef); 1210243830Sdim } 1211243830Sdim} 1212243830Sdim 1213309124Sdim// Gather the unsupported features for processor models. 1214309124Sdimvoid CodeGenSchedModels::collectProcUnsupportedFeatures() { 1215309124Sdim for (CodeGenProcModel &ProcModel : ProcModels) { 1216309124Sdim for (Record *Pred : ProcModel.ModelDef->getValueAsListOfDefs("UnsupportedFeatures")) { 1217309124Sdim ProcModel.UnsupportedFeaturesDefs.push_back(Pred); 1218309124Sdim } 1219309124Sdim } 1220309124Sdim} 1221309124Sdim 1222243830Sdim/// Infer new classes from existing classes. In the process, this may create new 1223243830Sdim/// SchedWrites from sequences of existing SchedWrites. 1224243830Sdimvoid CodeGenSchedModels::inferSchedClasses() { 1225341825Sdim LLVM_DEBUG( 1226341825Sdim dbgs() << "\n+++ INFERRING SCHED CLASSES (inferSchedClasses) +++\n"); 1227341825Sdim LLVM_DEBUG(dbgs() << NumInstrSchedClasses << " instr sched classes.\n"); 1228249423Sdim 1229243830Sdim // Visit all existing classes and newly created classes. 1230243830Sdim for (unsigned Idx = 0; Idx != SchedClasses.size(); ++Idx) { 1231249423Sdim assert(SchedClasses[Idx].Index == Idx && "bad SCIdx"); 1232249423Sdim 1233243830Sdim if (SchedClasses[Idx].ItinClassDef) 1234243830Sdim inferFromItinClass(SchedClasses[Idx].ItinClassDef, Idx); 1235249423Sdim if (!SchedClasses[Idx].InstRWs.empty()) 1236243830Sdim inferFromInstRWs(Idx); 1237249423Sdim if (!SchedClasses[Idx].Writes.empty()) { 1238243830Sdim inferFromRW(SchedClasses[Idx].Writes, SchedClasses[Idx].Reads, 1239243830Sdim Idx, SchedClasses[Idx].ProcIndices); 1240243830Sdim } 1241243830Sdim assert(SchedClasses.size() < (NumInstrSchedClasses*6) && 1242243830Sdim "too many SchedVariants"); 1243243830Sdim } 1244243830Sdim} 1245243830Sdim 1246243830Sdim/// Infer classes from per-processor itinerary resources. 1247243830Sdimvoid CodeGenSchedModels::inferFromItinClass(Record *ItinClassDef, 1248243830Sdim unsigned FromClassIdx) { 1249243830Sdim for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) { 1250243830Sdim const CodeGenProcModel &PM = ProcModels[PIdx]; 1251243830Sdim // For all ItinRW entries. 1252243830Sdim bool HasMatch = false; 1253341825Sdim for (const Record *Rec : PM.ItinRWDefs) { 1254341825Sdim RecVec Matched = Rec->getValueAsListOfDefs("MatchedItinClasses"); 1255243830Sdim if (!std::count(Matched.begin(), Matched.end(), ItinClassDef)) 1256243830Sdim continue; 1257243830Sdim if (HasMatch) 1258341825Sdim PrintFatalError(Rec->getLoc(), "Duplicate itinerary class " 1259243830Sdim + ItinClassDef->getName() 1260243830Sdim + " in ItinResources for " + PM.ModelName); 1261243830Sdim HasMatch = true; 1262243830Sdim IdxVec Writes, Reads; 1263341825Sdim findRWs(Rec->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads); 1264341825Sdim inferFromRW(Writes, Reads, FromClassIdx, PIdx); 1265243830Sdim } 1266243830Sdim } 1267243830Sdim} 1268243830Sdim 1269243830Sdim/// Infer classes from per-processor InstReadWrite definitions. 1270243830Sdimvoid CodeGenSchedModels::inferFromInstRWs(unsigned SCIdx) { 1271261991Sdim for (unsigned I = 0, E = SchedClasses[SCIdx].InstRWs.size(); I != E; ++I) { 1272261991Sdim assert(SchedClasses[SCIdx].InstRWs.size() == E && "InstrRWs was mutated!"); 1273261991Sdim Record *Rec = SchedClasses[SCIdx].InstRWs[I]; 1274261991Sdim const RecVec *InstDefs = Sets.expand(Rec); 1275243830Sdim RecIter II = InstDefs->begin(), IE = InstDefs->end(); 1276243830Sdim for (; II != IE; ++II) { 1277243830Sdim if (InstrClassMap[*II] == SCIdx) 1278243830Sdim break; 1279243830Sdim } 1280243830Sdim // If this class no longer has any instructions mapped to it, it has become 1281243830Sdim // irrelevant. 1282243830Sdim if (II == IE) 1283243830Sdim continue; 1284243830Sdim IdxVec Writes, Reads; 1285261991Sdim findRWs(Rec->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads); 1286261991Sdim unsigned PIdx = getProcModel(Rec->getValueAsDef("SchedModel")).Index; 1287341825Sdim inferFromRW(Writes, Reads, SCIdx, PIdx); // May mutate SchedClasses. 1288243830Sdim } 1289243830Sdim} 1290243830Sdim 1291243830Sdimnamespace { 1292314564Sdim 1293243830Sdim// Helper for substituteVariantOperand. 1294243830Sdimstruct TransVariant { 1295243830Sdim Record *VarOrSeqDef; // Variant or sequence. 1296243830Sdim unsigned RWIdx; // Index of this variant or sequence's matched type. 1297243830Sdim unsigned ProcIdx; // Processor model index or zero for any. 1298243830Sdim unsigned TransVecIdx; // Index into PredTransitions::TransVec. 1299243830Sdim 1300243830Sdim TransVariant(Record *def, unsigned rwi, unsigned pi, unsigned ti): 1301243830Sdim VarOrSeqDef(def), RWIdx(rwi), ProcIdx(pi), TransVecIdx(ti) {} 1302243830Sdim}; 1303243830Sdim 1304243830Sdim// Associate a predicate with the SchedReadWrite that it guards. 1305243830Sdim// RWIdx is the index of the read/write variant. 1306243830Sdimstruct PredCheck { 1307243830Sdim bool IsRead; 1308243830Sdim unsigned RWIdx; 1309243830Sdim Record *Predicate; 1310243830Sdim 1311243830Sdim PredCheck(bool r, unsigned w, Record *p): IsRead(r), RWIdx(w), Predicate(p) {} 1312243830Sdim}; 1313243830Sdim 1314243830Sdim// A Predicate transition is a list of RW sequences guarded by a PredTerm. 1315243830Sdimstruct PredTransition { 1316243830Sdim // A predicate term is a conjunction of PredChecks. 1317243830Sdim SmallVector<PredCheck, 4> PredTerm; 1318243830Sdim SmallVector<SmallVector<unsigned,4>, 16> WriteSequences; 1319243830Sdim SmallVector<SmallVector<unsigned,4>, 16> ReadSequences; 1320243830Sdim SmallVector<unsigned, 4> ProcIndices; 1321243830Sdim}; 1322243830Sdim 1323243830Sdim// Encapsulate a set of partially constructed transitions. 1324243830Sdim// The results are built by repeated calls to substituteVariants. 1325243830Sdimclass PredTransitions { 1326243830Sdim CodeGenSchedModels &SchedModels; 1327243830Sdim 1328243830Sdimpublic: 1329243830Sdim std::vector<PredTransition> TransVec; 1330243830Sdim 1331243830Sdim PredTransitions(CodeGenSchedModels &sm): SchedModels(sm) {} 1332243830Sdim 1333243830Sdim void substituteVariantOperand(const SmallVectorImpl<unsigned> &RWSeq, 1334243830Sdim bool IsRead, unsigned StartIdx); 1335243830Sdim 1336243830Sdim void substituteVariants(const PredTransition &Trans); 1337243830Sdim 1338243830Sdim#ifndef NDEBUG 1339243830Sdim void dump() const; 1340243830Sdim#endif 1341243830Sdim 1342243830Sdimprivate: 1343243830Sdim bool mutuallyExclusive(Record *PredDef, ArrayRef<PredCheck> Term); 1344243830Sdim void getIntersectingVariants( 1345243830Sdim const CodeGenSchedRW &SchedRW, unsigned TransIdx, 1346243830Sdim std::vector<TransVariant> &IntersectingVariants); 1347243830Sdim void pushVariant(const TransVariant &VInfo, bool IsRead); 1348243830Sdim}; 1349243830Sdim 1350314564Sdim} // end anonymous namespace 1351314564Sdim 1352243830Sdim// Return true if this predicate is mutually exclusive with a PredTerm. This 1353243830Sdim// degenerates into checking if the predicate is mutually exclusive with any 1354243830Sdim// predicate in the Term's conjunction. 1355243830Sdim// 1356243830Sdim// All predicates associated with a given SchedRW are considered mutually 1357243830Sdim// exclusive. This should work even if the conditions expressed by the 1358243830Sdim// predicates are not exclusive because the predicates for a given SchedWrite 1359243830Sdim// are always checked in the order they are defined in the .td file. Later 1360243830Sdim// conditions implicitly negate any prior condition. 1361243830Sdimbool PredTransitions::mutuallyExclusive(Record *PredDef, 1362243830Sdim ArrayRef<PredCheck> Term) { 1363327952Sdim for (const PredCheck &PC: Term) { 1364327952Sdim if (PC.Predicate == PredDef) 1365243830Sdim return false; 1366243830Sdim 1367327952Sdim const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(PC.RWIdx, PC.IsRead); 1368243830Sdim assert(SchedRW.HasVariants && "PredCheck must refer to a SchedVariant"); 1369243830Sdim RecVec Variants = SchedRW.TheDef->getValueAsListOfDefs("Variants"); 1370341825Sdim if (any_of(Variants, [PredDef](const Record *R) { 1371341825Sdim return R->getValueAsDef("Predicate") == PredDef; 1372341825Sdim })) 1373341825Sdim return true; 1374243830Sdim } 1375243830Sdim return false; 1376243830Sdim} 1377243830Sdim 1378243830Sdimstatic bool hasAliasedVariants(const CodeGenSchedRW &RW, 1379243830Sdim CodeGenSchedModels &SchedModels) { 1380243830Sdim if (RW.HasVariants) 1381243830Sdim return true; 1382243830Sdim 1383327952Sdim for (Record *Alias : RW.Aliases) { 1384243830Sdim const CodeGenSchedRW &AliasRW = 1385327952Sdim SchedModels.getSchedRW(Alias->getValueAsDef("AliasRW")); 1386243830Sdim if (AliasRW.HasVariants) 1387243830Sdim return true; 1388243830Sdim if (AliasRW.IsSequence) { 1389243830Sdim IdxVec ExpandedRWs; 1390243830Sdim SchedModels.expandRWSequence(AliasRW.Index, ExpandedRWs, AliasRW.IsRead); 1391341825Sdim for (unsigned SI : ExpandedRWs) { 1392341825Sdim if (hasAliasedVariants(SchedModels.getSchedRW(SI, AliasRW.IsRead), 1393341825Sdim SchedModels)) 1394243830Sdim return true; 1395243830Sdim } 1396243830Sdim } 1397243830Sdim } 1398243830Sdim return false; 1399243830Sdim} 1400243830Sdim 1401243830Sdimstatic bool hasVariant(ArrayRef<PredTransition> Transitions, 1402243830Sdim CodeGenSchedModels &SchedModels) { 1403341825Sdim for (const PredTransition &PTI : Transitions) { 1404341825Sdim for (const SmallVectorImpl<unsigned> &WSI : PTI.WriteSequences) 1405341825Sdim for (unsigned WI : WSI) 1406341825Sdim if (hasAliasedVariants(SchedModels.getSchedWrite(WI), SchedModels)) 1407243830Sdim return true; 1408341825Sdim 1409341825Sdim for (const SmallVectorImpl<unsigned> &RSI : PTI.ReadSequences) 1410341825Sdim for (unsigned RI : RSI) 1411341825Sdim if (hasAliasedVariants(SchedModels.getSchedRead(RI), SchedModels)) 1412243830Sdim return true; 1413243830Sdim } 1414243830Sdim return false; 1415243830Sdim} 1416243830Sdim 1417243830Sdim// Populate IntersectingVariants with any variants or aliased sequences of the 1418243830Sdim// given SchedRW whose processor indices and predicates are not mutually 1419249423Sdim// exclusive with the given transition. 1420243830Sdimvoid PredTransitions::getIntersectingVariants( 1421243830Sdim const CodeGenSchedRW &SchedRW, unsigned TransIdx, 1422243830Sdim std::vector<TransVariant> &IntersectingVariants) { 1423243830Sdim 1424249423Sdim bool GenericRW = false; 1425249423Sdim 1426243830Sdim std::vector<TransVariant> Variants; 1427243830Sdim if (SchedRW.HasVariants) { 1428243830Sdim unsigned VarProcIdx = 0; 1429243830Sdim if (SchedRW.TheDef->getValueInit("SchedModel")->isComplete()) { 1430243830Sdim Record *ModelDef = SchedRW.TheDef->getValueAsDef("SchedModel"); 1431243830Sdim VarProcIdx = SchedModels.getProcModel(ModelDef).Index; 1432243830Sdim } 1433243830Sdim // Push each variant. Assign TransVecIdx later. 1434243830Sdim const RecVec VarDefs = SchedRW.TheDef->getValueAsListOfDefs("Variants"); 1435327952Sdim for (Record *VarDef : VarDefs) 1436341825Sdim Variants.emplace_back(VarDef, SchedRW.Index, VarProcIdx, 0); 1437249423Sdim if (VarProcIdx == 0) 1438249423Sdim GenericRW = true; 1439243830Sdim } 1440243830Sdim for (RecIter AI = SchedRW.Aliases.begin(), AE = SchedRW.Aliases.end(); 1441243830Sdim AI != AE; ++AI) { 1442243830Sdim // If either the SchedAlias itself or the SchedReadWrite that it aliases 1443243830Sdim // to is defined within a processor model, constrain all variants to 1444243830Sdim // that processor. 1445243830Sdim unsigned AliasProcIdx = 0; 1446243830Sdim if ((*AI)->getValueInit("SchedModel")->isComplete()) { 1447243830Sdim Record *ModelDef = (*AI)->getValueAsDef("SchedModel"); 1448243830Sdim AliasProcIdx = SchedModels.getProcModel(ModelDef).Index; 1449243830Sdim } 1450243830Sdim const CodeGenSchedRW &AliasRW = 1451243830Sdim SchedModels.getSchedRW((*AI)->getValueAsDef("AliasRW")); 1452243830Sdim 1453243830Sdim if (AliasRW.HasVariants) { 1454243830Sdim const RecVec VarDefs = AliasRW.TheDef->getValueAsListOfDefs("Variants"); 1455327952Sdim for (Record *VD : VarDefs) 1456341825Sdim Variants.emplace_back(VD, AliasRW.Index, AliasProcIdx, 0); 1457243830Sdim } 1458341825Sdim if (AliasRW.IsSequence) 1459341825Sdim Variants.emplace_back(AliasRW.TheDef, SchedRW.Index, AliasProcIdx, 0); 1460249423Sdim if (AliasProcIdx == 0) 1461249423Sdim GenericRW = true; 1462243830Sdim } 1463327952Sdim for (TransVariant &Variant : Variants) { 1464243830Sdim // Don't expand variants if the processor models don't intersect. 1465243830Sdim // A zero processor index means any processor. 1466261991Sdim SmallVectorImpl<unsigned> &ProcIndices = TransVec[TransIdx].ProcIndices; 1467327952Sdim if (ProcIndices[0] && Variant.ProcIdx) { 1468243830Sdim unsigned Cnt = std::count(ProcIndices.begin(), ProcIndices.end(), 1469243830Sdim Variant.ProcIdx); 1470243830Sdim if (!Cnt) 1471243830Sdim continue; 1472243830Sdim if (Cnt > 1) { 1473243830Sdim const CodeGenProcModel &PM = 1474243830Sdim *(SchedModels.procModelBegin() + Variant.ProcIdx); 1475243830Sdim PrintFatalError(Variant.VarOrSeqDef->getLoc(), 1476243830Sdim "Multiple variants defined for processor " + 1477243830Sdim PM.ModelName + 1478243830Sdim " Ensure only one SchedAlias exists per RW."); 1479243830Sdim } 1480243830Sdim } 1481243830Sdim if (Variant.VarOrSeqDef->isSubClassOf("SchedVar")) { 1482243830Sdim Record *PredDef = Variant.VarOrSeqDef->getValueAsDef("Predicate"); 1483243830Sdim if (mutuallyExclusive(PredDef, TransVec[TransIdx].PredTerm)) 1484243830Sdim continue; 1485243830Sdim } 1486243830Sdim if (IntersectingVariants.empty()) { 1487243830Sdim // The first variant builds on the existing transition. 1488243830Sdim Variant.TransVecIdx = TransIdx; 1489243830Sdim IntersectingVariants.push_back(Variant); 1490243830Sdim } 1491243830Sdim else { 1492243830Sdim // Push another copy of the current transition for more variants. 1493243830Sdim Variant.TransVecIdx = TransVec.size(); 1494243830Sdim IntersectingVariants.push_back(Variant); 1495243830Sdim TransVec.push_back(TransVec[TransIdx]); 1496243830Sdim } 1497243830Sdim } 1498249423Sdim if (GenericRW && IntersectingVariants.empty()) { 1499249423Sdim PrintFatalError(SchedRW.TheDef->getLoc(), "No variant of this type has " 1500249423Sdim "a matching predicate on any processor"); 1501249423Sdim } 1502243830Sdim} 1503243830Sdim 1504243830Sdim// Push the Reads/Writes selected by this variant onto the PredTransition 1505243830Sdim// specified by VInfo. 1506243830Sdimvoid PredTransitions:: 1507243830SdimpushVariant(const TransVariant &VInfo, bool IsRead) { 1508243830Sdim PredTransition &Trans = TransVec[VInfo.TransVecIdx]; 1509243830Sdim 1510243830Sdim // If this operand transition is reached through a processor-specific alias, 1511243830Sdim // then the whole transition is specific to this processor. 1512243830Sdim if (VInfo.ProcIdx != 0) 1513243830Sdim Trans.ProcIndices.assign(1, VInfo.ProcIdx); 1514243830Sdim 1515243830Sdim IdxVec SelectedRWs; 1516243830Sdim if (VInfo.VarOrSeqDef->isSubClassOf("SchedVar")) { 1517243830Sdim Record *PredDef = VInfo.VarOrSeqDef->getValueAsDef("Predicate"); 1518341825Sdim Trans.PredTerm.emplace_back(IsRead, VInfo.RWIdx,PredDef); 1519243830Sdim RecVec SelectedDefs = VInfo.VarOrSeqDef->getValueAsListOfDefs("Selected"); 1520243830Sdim SchedModels.findRWs(SelectedDefs, SelectedRWs, IsRead); 1521243830Sdim } 1522239310Sdim else { 1523243830Sdim assert(VInfo.VarOrSeqDef->isSubClassOf("WriteSequence") && 1524243830Sdim "variant must be a SchedVariant or aliased WriteSequence"); 1525243830Sdim SelectedRWs.push_back(SchedModels.getSchedRWIdx(VInfo.VarOrSeqDef, IsRead)); 1526239310Sdim } 1527239310Sdim 1528243830Sdim const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(VInfo.RWIdx, IsRead); 1529239310Sdim 1530314564Sdim SmallVectorImpl<SmallVector<unsigned,4>> &RWSequences = IsRead 1531243830Sdim ? Trans.ReadSequences : Trans.WriteSequences; 1532243830Sdim if (SchedRW.IsVariadic) { 1533243830Sdim unsigned OperIdx = RWSequences.size()-1; 1534243830Sdim // Make N-1 copies of this transition's last sequence. 1535341825Sdim RWSequences.insert(RWSequences.end(), SelectedRWs.size() - 1, 1536341825Sdim RWSequences[OperIdx]); 1537243830Sdim // Push each of the N elements of the SelectedRWs onto a copy of the last 1538243830Sdim // sequence (split the current operand into N operands). 1539243830Sdim // Note that write sequences should be expanded within this loop--the entire 1540243830Sdim // sequence belongs to a single operand. 1541243830Sdim for (IdxIter RWI = SelectedRWs.begin(), RWE = SelectedRWs.end(); 1542243830Sdim RWI != RWE; ++RWI, ++OperIdx) { 1543243830Sdim IdxVec ExpandedRWs; 1544243830Sdim if (IsRead) 1545243830Sdim ExpandedRWs.push_back(*RWI); 1546243830Sdim else 1547243830Sdim SchedModels.expandRWSequence(*RWI, ExpandedRWs, IsRead); 1548243830Sdim RWSequences[OperIdx].insert(RWSequences[OperIdx].end(), 1549243830Sdim ExpandedRWs.begin(), ExpandedRWs.end()); 1550243830Sdim } 1551243830Sdim assert(OperIdx == RWSequences.size() && "missed a sequence"); 1552243830Sdim } 1553243830Sdim else { 1554243830Sdim // Push this transition's expanded sequence onto this transition's last 1555243830Sdim // sequence (add to the current operand's sequence). 1556243830Sdim SmallVectorImpl<unsigned> &Seq = RWSequences.back(); 1557243830Sdim IdxVec ExpandedRWs; 1558243830Sdim for (IdxIter RWI = SelectedRWs.begin(), RWE = SelectedRWs.end(); 1559243830Sdim RWI != RWE; ++RWI) { 1560243830Sdim if (IsRead) 1561243830Sdim ExpandedRWs.push_back(*RWI); 1562243830Sdim else 1563243830Sdim SchedModels.expandRWSequence(*RWI, ExpandedRWs, IsRead); 1564243830Sdim } 1565243830Sdim Seq.insert(Seq.end(), ExpandedRWs.begin(), ExpandedRWs.end()); 1566243830Sdim } 1567243830Sdim} 1568239310Sdim 1569243830Sdim// RWSeq is a sequence of all Reads or all Writes for the next read or write 1570243830Sdim// operand. StartIdx is an index into TransVec where partial results 1571243830Sdim// starts. RWSeq must be applied to all transitions between StartIdx and the end 1572243830Sdim// of TransVec. 1573243830Sdimvoid PredTransitions::substituteVariantOperand( 1574243830Sdim const SmallVectorImpl<unsigned> &RWSeq, bool IsRead, unsigned StartIdx) { 1575243830Sdim 1576243830Sdim // Visit each original RW within the current sequence. 1577243830Sdim for (SmallVectorImpl<unsigned>::const_iterator 1578243830Sdim RWI = RWSeq.begin(), RWE = RWSeq.end(); RWI != RWE; ++RWI) { 1579243830Sdim const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(*RWI, IsRead); 1580243830Sdim // Push this RW on all partial PredTransitions or distribute variants. 1581243830Sdim // New PredTransitions may be pushed within this loop which should not be 1582243830Sdim // revisited (TransEnd must be loop invariant). 1583243830Sdim for (unsigned TransIdx = StartIdx, TransEnd = TransVec.size(); 1584243830Sdim TransIdx != TransEnd; ++TransIdx) { 1585243830Sdim // In the common case, push RW onto the current operand's sequence. 1586243830Sdim if (!hasAliasedVariants(SchedRW, SchedModels)) { 1587243830Sdim if (IsRead) 1588243830Sdim TransVec[TransIdx].ReadSequences.back().push_back(*RWI); 1589243830Sdim else 1590243830Sdim TransVec[TransIdx].WriteSequences.back().push_back(*RWI); 1591243830Sdim continue; 1592243830Sdim } 1593243830Sdim // Distribute this partial PredTransition across intersecting variants. 1594243830Sdim // This will push a copies of TransVec[TransIdx] on the back of TransVec. 1595243830Sdim std::vector<TransVariant> IntersectingVariants; 1596243830Sdim getIntersectingVariants(SchedRW, TransIdx, IntersectingVariants); 1597243830Sdim // Now expand each variant on top of its copy of the transition. 1598243830Sdim for (std::vector<TransVariant>::const_iterator 1599243830Sdim IVI = IntersectingVariants.begin(), 1600243830Sdim IVE = IntersectingVariants.end(); 1601243830Sdim IVI != IVE; ++IVI) { 1602243830Sdim pushVariant(*IVI, IsRead); 1603243830Sdim } 1604243830Sdim } 1605243830Sdim } 1606239310Sdim} 1607239310Sdim 1608243830Sdim// For each variant of a Read/Write in Trans, substitute the sequence of 1609243830Sdim// Read/Writes guarded by the variant. This is exponential in the number of 1610243830Sdim// variant Read/Writes, but in practice detection of mutually exclusive 1611243830Sdim// predicates should result in linear growth in the total number variants. 1612243830Sdim// 1613243830Sdim// This is one step in a breadth-first search of nested variants. 1614243830Sdimvoid PredTransitions::substituteVariants(const PredTransition &Trans) { 1615243830Sdim // Build up a set of partial results starting at the back of 1616243830Sdim // PredTransitions. Remember the first new transition. 1617243830Sdim unsigned StartIdx = TransVec.size(); 1618341825Sdim TransVec.emplace_back(); 1619243830Sdim TransVec.back().PredTerm = Trans.PredTerm; 1620243830Sdim TransVec.back().ProcIndices = Trans.ProcIndices; 1621243830Sdim 1622243830Sdim // Visit each original write sequence. 1623314564Sdim for (SmallVectorImpl<SmallVector<unsigned,4>>::const_iterator 1624243830Sdim WSI = Trans.WriteSequences.begin(), WSE = Trans.WriteSequences.end(); 1625243830Sdim WSI != WSE; ++WSI) { 1626243830Sdim // Push a new (empty) write sequence onto all partial Transitions. 1627243830Sdim for (std::vector<PredTransition>::iterator I = 1628243830Sdim TransVec.begin() + StartIdx, E = TransVec.end(); I != E; ++I) { 1629341825Sdim I->WriteSequences.emplace_back(); 1630243830Sdim } 1631243830Sdim substituteVariantOperand(*WSI, /*IsRead=*/false, StartIdx); 1632243830Sdim } 1633243830Sdim // Visit each original read sequence. 1634314564Sdim for (SmallVectorImpl<SmallVector<unsigned,4>>::const_iterator 1635243830Sdim RSI = Trans.ReadSequences.begin(), RSE = Trans.ReadSequences.end(); 1636243830Sdim RSI != RSE; ++RSI) { 1637243830Sdim // Push a new (empty) read sequence onto all partial Transitions. 1638243830Sdim for (std::vector<PredTransition>::iterator I = 1639243830Sdim TransVec.begin() + StartIdx, E = TransVec.end(); I != E; ++I) { 1640341825Sdim I->ReadSequences.emplace_back(); 1641243830Sdim } 1642243830Sdim substituteVariantOperand(*RSI, /*IsRead=*/true, StartIdx); 1643243830Sdim } 1644243830Sdim} 1645243830Sdim 1646243830Sdim// Create a new SchedClass for each variant found by inferFromRW. Pass 1647243830Sdimstatic void inferFromTransitions(ArrayRef<PredTransition> LastTransitions, 1648243830Sdim unsigned FromClassIdx, 1649243830Sdim CodeGenSchedModels &SchedModels) { 1650243830Sdim // For each PredTransition, create a new CodeGenSchedTransition, which usually 1651243830Sdim // requires creating a new SchedClass. 1652243830Sdim for (ArrayRef<PredTransition>::iterator 1653243830Sdim I = LastTransitions.begin(), E = LastTransitions.end(); I != E; ++I) { 1654243830Sdim IdxVec OperWritesVariant; 1655341825Sdim transform(I->WriteSequences, std::back_inserter(OperWritesVariant), 1656341825Sdim [&SchedModels](ArrayRef<unsigned> WS) { 1657341825Sdim return SchedModels.findOrInsertRW(WS, /*IsRead=*/false); 1658341825Sdim }); 1659243830Sdim IdxVec OperReadsVariant; 1660341825Sdim transform(I->ReadSequences, std::back_inserter(OperReadsVariant), 1661341825Sdim [&SchedModels](ArrayRef<unsigned> RS) { 1662341825Sdim return SchedModels.findOrInsertRW(RS, /*IsRead=*/true); 1663341825Sdim }); 1664243830Sdim CodeGenSchedTransition SCTrans; 1665243830Sdim SCTrans.ToClassIdx = 1666276479Sdim SchedModels.addSchedClass(/*ItinClassDef=*/nullptr, OperWritesVariant, 1667341825Sdim OperReadsVariant, I->ProcIndices); 1668341825Sdim SCTrans.ProcIndices.assign(I->ProcIndices.begin(), I->ProcIndices.end()); 1669243830Sdim // The final PredTerm is unique set of predicates guarding the transition. 1670243830Sdim RecVec Preds; 1671341825Sdim transform(I->PredTerm, std::back_inserter(Preds), 1672341825Sdim [](const PredCheck &P) { 1673341825Sdim return P.Predicate; 1674341825Sdim }); 1675341825Sdim Preds.erase(std::unique(Preds.begin(), Preds.end()), Preds.end()); 1676341825Sdim SCTrans.PredTerm = std::move(Preds); 1677341825Sdim SchedModels.getSchedClass(FromClassIdx) 1678341825Sdim .Transitions.push_back(std::move(SCTrans)); 1679243830Sdim } 1680243830Sdim} 1681243830Sdim 1682243830Sdim// Create new SchedClasses for the given ReadWrite list. If any of the 1683243830Sdim// ReadWrites refers to a SchedVariant, create a new SchedClass for each variant 1684243830Sdim// of the ReadWrite list, following Aliases if necessary. 1685296417Sdimvoid CodeGenSchedModels::inferFromRW(ArrayRef<unsigned> OperWrites, 1686296417Sdim ArrayRef<unsigned> OperReads, 1687243830Sdim unsigned FromClassIdx, 1688296417Sdim ArrayRef<unsigned> ProcIndices) { 1689341825Sdim LLVM_DEBUG(dbgs() << "INFER RW proc("; dumpIdxVec(ProcIndices); 1690341825Sdim dbgs() << ") "); 1691243830Sdim 1692243830Sdim // Create a seed transition with an empty PredTerm and the expanded sequences 1693243830Sdim // of SchedWrites for the current SchedClass. 1694243830Sdim std::vector<PredTransition> LastTransitions; 1695341825Sdim LastTransitions.emplace_back(); 1696243830Sdim LastTransitions.back().ProcIndices.append(ProcIndices.begin(), 1697243830Sdim ProcIndices.end()); 1698243830Sdim 1699296417Sdim for (unsigned WriteIdx : OperWrites) { 1700243830Sdim IdxVec WriteSeq; 1701296417Sdim expandRWSequence(WriteIdx, WriteSeq, /*IsRead=*/false); 1702341825Sdim LastTransitions[0].WriteSequences.emplace_back(); 1703341825Sdim SmallVectorImpl<unsigned> &Seq = LastTransitions[0].WriteSequences.back(); 1704341825Sdim Seq.append(WriteSeq.begin(), WriteSeq.end()); 1705341825Sdim LLVM_DEBUG(dbgs() << "("; dumpIdxVec(Seq); dbgs() << ") "); 1706243830Sdim } 1707341825Sdim LLVM_DEBUG(dbgs() << " Reads: "); 1708296417Sdim for (unsigned ReadIdx : OperReads) { 1709243830Sdim IdxVec ReadSeq; 1710296417Sdim expandRWSequence(ReadIdx, ReadSeq, /*IsRead=*/true); 1711341825Sdim LastTransitions[0].ReadSequences.emplace_back(); 1712341825Sdim SmallVectorImpl<unsigned> &Seq = LastTransitions[0].ReadSequences.back(); 1713341825Sdim Seq.append(ReadSeq.begin(), ReadSeq.end()); 1714341825Sdim LLVM_DEBUG(dbgs() << "("; dumpIdxVec(Seq); dbgs() << ") "); 1715243830Sdim } 1716341825Sdim LLVM_DEBUG(dbgs() << '\n'); 1717243830Sdim 1718243830Sdim // Collect all PredTransitions for individual operands. 1719243830Sdim // Iterate until no variant writes remain. 1720243830Sdim while (hasVariant(LastTransitions, *this)) { 1721243830Sdim PredTransitions Transitions(*this); 1722341825Sdim for (const PredTransition &Trans : LastTransitions) 1723341825Sdim Transitions.substituteVariants(Trans); 1724341825Sdim LLVM_DEBUG(Transitions.dump()); 1725243830Sdim LastTransitions.swap(Transitions.TransVec); 1726243830Sdim } 1727243830Sdim // If the first transition has no variants, nothing to do. 1728243830Sdim if (LastTransitions[0].PredTerm.empty()) 1729239310Sdim return; 1730239310Sdim 1731243830Sdim // WARNING: We are about to mutate the SchedClasses vector. Do not refer to 1732243830Sdim // OperWrites, OperReads, or ProcIndices after calling inferFromTransitions. 1733243830Sdim inferFromTransitions(LastTransitions, FromClassIdx, *this); 1734243830Sdim} 1735239310Sdim 1736251662Sdim// Check if any processor resource group contains all resource records in 1737251662Sdim// SubUnits. 1738251662Sdimbool CodeGenSchedModels::hasSuperGroup(RecVec &SubUnits, CodeGenProcModel &PM) { 1739251662Sdim for (unsigned i = 0, e = PM.ProcResourceDefs.size(); i < e; ++i) { 1740251662Sdim if (!PM.ProcResourceDefs[i]->isSubClassOf("ProcResGroup")) 1741251662Sdim continue; 1742251662Sdim RecVec SuperUnits = 1743251662Sdim PM.ProcResourceDefs[i]->getValueAsListOfDefs("Resources"); 1744251662Sdim RecIter RI = SubUnits.begin(), RE = SubUnits.end(); 1745251662Sdim for ( ; RI != RE; ++RI) { 1746314564Sdim if (!is_contained(SuperUnits, *RI)) { 1747251662Sdim break; 1748251662Sdim } 1749251662Sdim } 1750251662Sdim if (RI == RE) 1751251662Sdim return true; 1752251662Sdim } 1753251662Sdim return false; 1754251662Sdim} 1755251662Sdim 1756251662Sdim// Verify that overlapping groups have a common supergroup. 1757251662Sdimvoid CodeGenSchedModels::verifyProcResourceGroups(CodeGenProcModel &PM) { 1758251662Sdim for (unsigned i = 0, e = PM.ProcResourceDefs.size(); i < e; ++i) { 1759251662Sdim if (!PM.ProcResourceDefs[i]->isSubClassOf("ProcResGroup")) 1760251662Sdim continue; 1761251662Sdim RecVec CheckUnits = 1762251662Sdim PM.ProcResourceDefs[i]->getValueAsListOfDefs("Resources"); 1763251662Sdim for (unsigned j = i+1; j < e; ++j) { 1764251662Sdim if (!PM.ProcResourceDefs[j]->isSubClassOf("ProcResGroup")) 1765251662Sdim continue; 1766251662Sdim RecVec OtherUnits = 1767251662Sdim PM.ProcResourceDefs[j]->getValueAsListOfDefs("Resources"); 1768251662Sdim if (std::find_first_of(CheckUnits.begin(), CheckUnits.end(), 1769251662Sdim OtherUnits.begin(), OtherUnits.end()) 1770251662Sdim != CheckUnits.end()) { 1771251662Sdim // CheckUnits and OtherUnits overlap 1772251662Sdim OtherUnits.insert(OtherUnits.end(), CheckUnits.begin(), 1773251662Sdim CheckUnits.end()); 1774251662Sdim if (!hasSuperGroup(OtherUnits, PM)) { 1775251662Sdim PrintFatalError((PM.ProcResourceDefs[i])->getLoc(), 1776251662Sdim "proc resource group overlaps with " 1777251662Sdim + PM.ProcResourceDefs[j]->getName() 1778251662Sdim + " but no supergroup contains both."); 1779251662Sdim } 1780251662Sdim } 1781251662Sdim } 1782251662Sdim } 1783251662Sdim} 1784251662Sdim 1785341825Sdim// Collect all the RegisterFile definitions available in this target. 1786341825Sdimvoid CodeGenSchedModels::collectRegisterFiles() { 1787341825Sdim RecVec RegisterFileDefs = Records.getAllDerivedDefinitions("RegisterFile"); 1788341825Sdim 1789341825Sdim // RegisterFiles is the vector of CodeGenRegisterFile. 1790341825Sdim for (Record *RF : RegisterFileDefs) { 1791341825Sdim // For each register file definition, construct a CodeGenRegisterFile object 1792341825Sdim // and add it to the appropriate scheduling model. 1793341825Sdim CodeGenProcModel &PM = getProcModel(RF->getValueAsDef("SchedModel")); 1794341825Sdim PM.RegisterFiles.emplace_back(CodeGenRegisterFile(RF->getName(),RF)); 1795341825Sdim CodeGenRegisterFile &CGRF = PM.RegisterFiles.back(); 1796344779Sdim CGRF.MaxMovesEliminatedPerCycle = 1797344779Sdim RF->getValueAsInt("MaxMovesEliminatedPerCycle"); 1798344779Sdim CGRF.AllowZeroMoveEliminationOnly = 1799344779Sdim RF->getValueAsBit("AllowZeroMoveEliminationOnly"); 1800341825Sdim 1801341825Sdim // Now set the number of physical registers as well as the cost of registers 1802341825Sdim // in each register class. 1803341825Sdim CGRF.NumPhysRegs = RF->getValueAsInt("NumPhysRegs"); 1804344779Sdim if (!CGRF.NumPhysRegs) { 1805344779Sdim PrintFatalError(RF->getLoc(), 1806344779Sdim "Invalid RegisterFile with zero physical registers"); 1807344779Sdim } 1808344779Sdim 1809341825Sdim RecVec RegisterClasses = RF->getValueAsListOfDefs("RegClasses"); 1810341825Sdim std::vector<int64_t> RegisterCosts = RF->getValueAsListOfInts("RegCosts"); 1811344779Sdim ListInit *MoveElimInfo = RF->getValueAsListInit("AllowMoveElimination"); 1812341825Sdim for (unsigned I = 0, E = RegisterClasses.size(); I < E; ++I) { 1813341825Sdim int Cost = RegisterCosts.size() > I ? RegisterCosts[I] : 1; 1814341825Sdim 1815344779Sdim bool AllowMoveElim = false; 1816344779Sdim if (MoveElimInfo->size() > I) { 1817344779Sdim BitInit *Val = cast<BitInit>(MoveElimInfo->getElement(I)); 1818344779Sdim AllowMoveElim = Val->getValue(); 1819344779Sdim } 1820344779Sdim 1821344779Sdim CGRF.Costs.emplace_back(RegisterClasses[I], Cost, AllowMoveElim); 1822341825Sdim } 1823341825Sdim } 1824341825Sdim} 1825341825Sdim 1826243830Sdim// Collect and sort WriteRes, ReadAdvance, and ProcResources. 1827243830Sdimvoid CodeGenSchedModels::collectProcResources() { 1828309124Sdim ProcResourceDefs = Records.getAllDerivedDefinitions("ProcResourceUnits"); 1829309124Sdim ProcResGroups = Records.getAllDerivedDefinitions("ProcResGroup"); 1830309124Sdim 1831243830Sdim // Add any subtarget-specific SchedReadWrites that are directly associated 1832243830Sdim // with processor resources. Refer to the parent SchedClass's ProcIndices to 1833243830Sdim // determine which processors they apply to. 1834341825Sdim for (const CodeGenSchedClass &SC : 1835341825Sdim make_range(schedClassBegin(), schedClassEnd())) { 1836341825Sdim if (SC.ItinClassDef) { 1837341825Sdim collectItinProcResources(SC.ItinClassDef); 1838341825Sdim continue; 1839249423Sdim } 1840341825Sdim 1841341825Sdim // This class may have a default ReadWrite list which can be overriden by 1842341825Sdim // InstRW definitions. 1843341825Sdim for (Record *RW : SC.InstRWs) { 1844341825Sdim Record *RWModelDef = RW->getValueAsDef("SchedModel"); 1845341825Sdim unsigned PIdx = getProcModel(RWModelDef).Index; 1846341825Sdim IdxVec Writes, Reads; 1847341825Sdim findRWs(RW->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads); 1848341825Sdim collectRWResources(Writes, Reads, PIdx); 1849341825Sdim } 1850341825Sdim 1851341825Sdim collectRWResources(SC.Writes, SC.Reads, SC.ProcIndices); 1852243830Sdim } 1853243830Sdim // Add resources separately defined by each subtarget. 1854243830Sdim RecVec WRDefs = Records.getAllDerivedDefinitions("WriteRes"); 1855327952Sdim for (Record *WR : WRDefs) { 1856327952Sdim Record *ModelDef = WR->getValueAsDef("SchedModel"); 1857327952Sdim addWriteRes(WR, getProcModel(ModelDef).Index); 1858243830Sdim } 1859276479Sdim RecVec SWRDefs = Records.getAllDerivedDefinitions("SchedWriteRes"); 1860327952Sdim for (Record *SWR : SWRDefs) { 1861327952Sdim Record *ModelDef = SWR->getValueAsDef("SchedModel"); 1862327952Sdim addWriteRes(SWR, getProcModel(ModelDef).Index); 1863276479Sdim } 1864243830Sdim RecVec RADefs = Records.getAllDerivedDefinitions("ReadAdvance"); 1865327952Sdim for (Record *RA : RADefs) { 1866327952Sdim Record *ModelDef = RA->getValueAsDef("SchedModel"); 1867327952Sdim addReadAdvance(RA, getProcModel(ModelDef).Index); 1868243830Sdim } 1869276479Sdim RecVec SRADefs = Records.getAllDerivedDefinitions("SchedReadAdvance"); 1870327952Sdim for (Record *SRA : SRADefs) { 1871327952Sdim if (SRA->getValueInit("SchedModel")->isComplete()) { 1872327952Sdim Record *ModelDef = SRA->getValueAsDef("SchedModel"); 1873327952Sdim addReadAdvance(SRA, getProcModel(ModelDef).Index); 1874276479Sdim } 1875276479Sdim } 1876261991Sdim // Add ProcResGroups that are defined within this processor model, which may 1877261991Sdim // not be directly referenced but may directly specify a buffer size. 1878261991Sdim RecVec ProcResGroups = Records.getAllDerivedDefinitions("ProcResGroup"); 1879327952Sdim for (Record *PRG : ProcResGroups) { 1880327952Sdim if (!PRG->getValueInit("SchedModel")->isComplete()) 1881261991Sdim continue; 1882327952Sdim CodeGenProcModel &PM = getProcModel(PRG->getValueAsDef("SchedModel")); 1883327952Sdim if (!is_contained(PM.ProcResourceDefs, PRG)) 1884327952Sdim PM.ProcResourceDefs.push_back(PRG); 1885261991Sdim } 1886341825Sdim // Add ProcResourceUnits unconditionally. 1887341825Sdim for (Record *PRU : Records.getAllDerivedDefinitions("ProcResourceUnits")) { 1888341825Sdim if (!PRU->getValueInit("SchedModel")->isComplete()) 1889341825Sdim continue; 1890341825Sdim CodeGenProcModel &PM = getProcModel(PRU->getValueAsDef("SchedModel")); 1891341825Sdim if (!is_contained(PM.ProcResourceDefs, PRU)) 1892341825Sdim PM.ProcResourceDefs.push_back(PRU); 1893341825Sdim } 1894243830Sdim // Finalize each ProcModel by sorting the record arrays. 1895280031Sdim for (CodeGenProcModel &PM : ProcModels) { 1896344779Sdim llvm::sort(PM.WriteResDefs, LessRecord()); 1897344779Sdim llvm::sort(PM.ReadAdvanceDefs, LessRecord()); 1898344779Sdim llvm::sort(PM.ProcResourceDefs, LessRecord()); 1899341825Sdim LLVM_DEBUG( 1900341825Sdim PM.dump(); 1901341825Sdim dbgs() << "WriteResDefs: "; for (RecIter RI = PM.WriteResDefs.begin(), 1902341825Sdim RE = PM.WriteResDefs.end(); 1903341825Sdim RI != RE; ++RI) { 1904341825Sdim if ((*RI)->isSubClassOf("WriteRes")) 1905341825Sdim dbgs() << (*RI)->getValueAsDef("WriteType")->getName() << " "; 1906341825Sdim else 1907341825Sdim dbgs() << (*RI)->getName() << " "; 1908341825Sdim } dbgs() << "\nReadAdvanceDefs: "; 1909341825Sdim for (RecIter RI = PM.ReadAdvanceDefs.begin(), 1910341825Sdim RE = PM.ReadAdvanceDefs.end(); 1911341825Sdim RI != RE; ++RI) { 1912341825Sdim if ((*RI)->isSubClassOf("ReadAdvance")) 1913341825Sdim dbgs() << (*RI)->getValueAsDef("ReadType")->getName() << " "; 1914341825Sdim else 1915341825Sdim dbgs() << (*RI)->getName() << " "; 1916341825Sdim } dbgs() 1917341825Sdim << "\nProcResourceDefs: "; 1918341825Sdim for (RecIter RI = PM.ProcResourceDefs.begin(), 1919341825Sdim RE = PM.ProcResourceDefs.end(); 1920341825Sdim RI != RE; ++RI) { dbgs() << (*RI)->getName() << " "; } dbgs() 1921341825Sdim << '\n'); 1922251662Sdim verifyProcResourceGroups(PM); 1923243830Sdim } 1924309124Sdim 1925309124Sdim ProcResourceDefs.clear(); 1926309124Sdim ProcResGroups.clear(); 1927243830Sdim} 1928239310Sdim 1929309124Sdimvoid CodeGenSchedModels::checkCompleteness() { 1930309124Sdim bool Complete = true; 1931309124Sdim bool HadCompleteModel = false; 1932309124Sdim for (const CodeGenProcModel &ProcModel : procModels()) { 1933341825Sdim const bool HasItineraries = ProcModel.hasItineraries(); 1934309124Sdim if (!ProcModel.ModelDef->getValueAsBit("CompleteModel")) 1935309124Sdim continue; 1936309124Sdim for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) { 1937309124Sdim if (Inst->hasNoSchedulingInfo) 1938309124Sdim continue; 1939309124Sdim if (ProcModel.isUnsupported(*Inst)) 1940309124Sdim continue; 1941309124Sdim unsigned SCIdx = getSchedClassIdx(*Inst); 1942309124Sdim if (!SCIdx) { 1943309124Sdim if (Inst->TheDef->isValueUnset("SchedRW") && !HadCompleteModel) { 1944353358Sdim PrintError(Inst->TheDef->getLoc(), 1945353358Sdim "No schedule information for instruction '" + 1946353358Sdim Inst->TheDef->getName() + "' in SchedMachineModel '" + 1947353358Sdim ProcModel.ModelDef->getName() + "'"); 1948309124Sdim Complete = false; 1949309124Sdim } 1950309124Sdim continue; 1951309124Sdim } 1952309124Sdim 1953309124Sdim const CodeGenSchedClass &SC = getSchedClass(SCIdx); 1954309124Sdim if (!SC.Writes.empty()) 1955309124Sdim continue; 1956341825Sdim if (HasItineraries && SC.ItinClassDef != nullptr && 1957314564Sdim SC.ItinClassDef->getName() != "NoItinerary") 1958309124Sdim continue; 1959309124Sdim 1960309124Sdim const RecVec &InstRWs = SC.InstRWs; 1961314564Sdim auto I = find_if(InstRWs, [&ProcModel](const Record *R) { 1962314564Sdim return R->getValueAsDef("SchedModel") == ProcModel.ModelDef; 1963314564Sdim }); 1964309124Sdim if (I == InstRWs.end()) { 1965353358Sdim PrintError(Inst->TheDef->getLoc(), "'" + ProcModel.ModelName + 1966353358Sdim "' lacks information for '" + 1967353358Sdim Inst->TheDef->getName() + "'"); 1968309124Sdim Complete = false; 1969309124Sdim } 1970309124Sdim } 1971309124Sdim HadCompleteModel = true; 1972309124Sdim } 1973309124Sdim if (!Complete) { 1974309124Sdim errs() << "\n\nIncomplete schedule models found.\n" 1975309124Sdim << "- Consider setting 'CompleteModel = 0' while developing new models.\n" 1976309124Sdim << "- Pseudo instructions can be marked with 'hasNoSchedulingInfo = 1'.\n" 1977309124Sdim << "- Instructions should usually have Sched<[...]> as a superclass, " 1978309124Sdim "you may temporarily use an empty list.\n" 1979309124Sdim << "- Instructions related to unsupported features can be excluded with " 1980309124Sdim "list<Predicate> UnsupportedFeatures = [HasA,..,HasY]; in the " 1981309124Sdim "processor model.\n\n"; 1982309124Sdim PrintFatalError("Incomplete schedule model"); 1983309124Sdim } 1984309124Sdim} 1985309124Sdim 1986243830Sdim// Collect itinerary class resources for each processor. 1987243830Sdimvoid CodeGenSchedModels::collectItinProcResources(Record *ItinClassDef) { 1988243830Sdim for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) { 1989243830Sdim const CodeGenProcModel &PM = ProcModels[PIdx]; 1990243830Sdim // For all ItinRW entries. 1991243830Sdim bool HasMatch = false; 1992243830Sdim for (RecIter II = PM.ItinRWDefs.begin(), IE = PM.ItinRWDefs.end(); 1993243830Sdim II != IE; ++II) { 1994243830Sdim RecVec Matched = (*II)->getValueAsListOfDefs("MatchedItinClasses"); 1995243830Sdim if (!std::count(Matched.begin(), Matched.end(), ItinClassDef)) 1996243830Sdim continue; 1997243830Sdim if (HasMatch) 1998243830Sdim PrintFatalError((*II)->getLoc(), "Duplicate itinerary class " 1999243830Sdim + ItinClassDef->getName() 2000243830Sdim + " in ItinResources for " + PM.ModelName); 2001243830Sdim HasMatch = true; 2002243830Sdim IdxVec Writes, Reads; 2003243830Sdim findRWs((*II)->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads); 2004341825Sdim collectRWResources(Writes, Reads, PIdx); 2005239310Sdim } 2006239310Sdim } 2007243830Sdim} 2008243830Sdim 2009243830Sdimvoid CodeGenSchedModels::collectRWResources(unsigned RWIdx, bool IsRead, 2010296417Sdim ArrayRef<unsigned> ProcIndices) { 2011243830Sdim const CodeGenSchedRW &SchedRW = getSchedRW(RWIdx, IsRead); 2012243830Sdim if (SchedRW.TheDef) { 2013243830Sdim if (!IsRead && SchedRW.TheDef->isSubClassOf("SchedWriteRes")) { 2014296417Sdim for (unsigned Idx : ProcIndices) 2015296417Sdim addWriteRes(SchedRW.TheDef, Idx); 2016243830Sdim } 2017243830Sdim else if (IsRead && SchedRW.TheDef->isSubClassOf("SchedReadAdvance")) { 2018296417Sdim for (unsigned Idx : ProcIndices) 2019296417Sdim addReadAdvance(SchedRW.TheDef, Idx); 2020243830Sdim } 2021243830Sdim } 2022243830Sdim for (RecIter AI = SchedRW.Aliases.begin(), AE = SchedRW.Aliases.end(); 2023243830Sdim AI != AE; ++AI) { 2024243830Sdim IdxVec AliasProcIndices; 2025243830Sdim if ((*AI)->getValueInit("SchedModel")->isComplete()) { 2026243830Sdim AliasProcIndices.push_back( 2027243830Sdim getProcModel((*AI)->getValueAsDef("SchedModel")).Index); 2028243830Sdim } 2029243830Sdim else 2030243830Sdim AliasProcIndices = ProcIndices; 2031243830Sdim const CodeGenSchedRW &AliasRW = getSchedRW((*AI)->getValueAsDef("AliasRW")); 2032243830Sdim assert(AliasRW.IsRead == IsRead && "cannot alias reads to writes"); 2033243830Sdim 2034243830Sdim IdxVec ExpandedRWs; 2035243830Sdim expandRWSequence(AliasRW.Index, ExpandedRWs, IsRead); 2036243830Sdim for (IdxIter SI = ExpandedRWs.begin(), SE = ExpandedRWs.end(); 2037243830Sdim SI != SE; ++SI) { 2038243830Sdim collectRWResources(*SI, IsRead, AliasProcIndices); 2039243830Sdim } 2040243830Sdim } 2041243830Sdim} 2042243830Sdim 2043243830Sdim// Collect resources for a set of read/write types and processor indices. 2044296417Sdimvoid CodeGenSchedModels::collectRWResources(ArrayRef<unsigned> Writes, 2045296417Sdim ArrayRef<unsigned> Reads, 2046296417Sdim ArrayRef<unsigned> ProcIndices) { 2047296417Sdim for (unsigned Idx : Writes) 2048296417Sdim collectRWResources(Idx, /*IsRead=*/false, ProcIndices); 2049243830Sdim 2050296417Sdim for (unsigned Idx : Reads) 2051296417Sdim collectRWResources(Idx, /*IsRead=*/true, ProcIndices); 2052243830Sdim} 2053243830Sdim 2054243830Sdim// Find the processor's resource units for this kind of resource. 2055243830SdimRecord *CodeGenSchedModels::findProcResUnits(Record *ProcResKind, 2056327952Sdim const CodeGenProcModel &PM, 2057327952Sdim ArrayRef<SMLoc> Loc) const { 2058243830Sdim if (ProcResKind->isSubClassOf("ProcResourceUnits")) 2059243830Sdim return ProcResKind; 2060243830Sdim 2061276479Sdim Record *ProcUnitDef = nullptr; 2062309124Sdim assert(!ProcResourceDefs.empty()); 2063309124Sdim assert(!ProcResGroups.empty()); 2064243830Sdim 2065327952Sdim for (Record *ProcResDef : ProcResourceDefs) { 2066327952Sdim if (ProcResDef->getValueAsDef("Kind") == ProcResKind 2067327952Sdim && ProcResDef->getValueAsDef("SchedModel") == PM.ModelDef) { 2068243830Sdim if (ProcUnitDef) { 2069327952Sdim PrintFatalError(Loc, 2070243830Sdim "Multiple ProcessorResourceUnits associated with " 2071243830Sdim + ProcResKind->getName()); 2072243830Sdim } 2073327952Sdim ProcUnitDef = ProcResDef; 2074243830Sdim } 2075243830Sdim } 2076327952Sdim for (Record *ProcResGroup : ProcResGroups) { 2077327952Sdim if (ProcResGroup == ProcResKind 2078327952Sdim && ProcResGroup->getValueAsDef("SchedModel") == PM.ModelDef) { 2079249423Sdim if (ProcUnitDef) { 2080327952Sdim PrintFatalError(Loc, 2081249423Sdim "Multiple ProcessorResourceUnits associated with " 2082249423Sdim + ProcResKind->getName()); 2083249423Sdim } 2084327952Sdim ProcUnitDef = ProcResGroup; 2085249423Sdim } 2086249423Sdim } 2087243830Sdim if (!ProcUnitDef) { 2088327952Sdim PrintFatalError(Loc, 2089243830Sdim "No ProcessorResources associated with " 2090243830Sdim + ProcResKind->getName()); 2091243830Sdim } 2092243830Sdim return ProcUnitDef; 2093243830Sdim} 2094243830Sdim 2095243830Sdim// Iteratively add a resource and its super resources. 2096243830Sdimvoid CodeGenSchedModels::addProcResource(Record *ProcResKind, 2097327952Sdim CodeGenProcModel &PM, 2098327952Sdim ArrayRef<SMLoc> Loc) { 2099314564Sdim while (true) { 2100327952Sdim Record *ProcResUnits = findProcResUnits(ProcResKind, PM, Loc); 2101243830Sdim 2102243830Sdim // See if this ProcResource is already associated with this processor. 2103314564Sdim if (is_contained(PM.ProcResourceDefs, ProcResUnits)) 2104243830Sdim return; 2105243830Sdim 2106243830Sdim PM.ProcResourceDefs.push_back(ProcResUnits); 2107249423Sdim if (ProcResUnits->isSubClassOf("ProcResGroup")) 2108249423Sdim return; 2109249423Sdim 2110243830Sdim if (!ProcResUnits->getValueInit("Super")->isComplete()) 2111243830Sdim return; 2112243830Sdim 2113243830Sdim ProcResKind = ProcResUnits->getValueAsDef("Super"); 2114243830Sdim } 2115243830Sdim} 2116243830Sdim 2117243830Sdim// Add resources for a SchedWrite to this processor if they don't exist. 2118243830Sdimvoid CodeGenSchedModels::addWriteRes(Record *ProcWriteResDef, unsigned PIdx) { 2119243830Sdim assert(PIdx && "don't add resources to an invalid Processor model"); 2120243830Sdim 2121243830Sdim RecVec &WRDefs = ProcModels[PIdx].WriteResDefs; 2122314564Sdim if (is_contained(WRDefs, ProcWriteResDef)) 2123243830Sdim return; 2124243830Sdim WRDefs.push_back(ProcWriteResDef); 2125243830Sdim 2126243830Sdim // Visit ProcResourceKinds referenced by the newly discovered WriteRes. 2127243830Sdim RecVec ProcResDefs = ProcWriteResDef->getValueAsListOfDefs("ProcResources"); 2128243830Sdim for (RecIter WritePRI = ProcResDefs.begin(), WritePRE = ProcResDefs.end(); 2129243830Sdim WritePRI != WritePRE; ++WritePRI) { 2130327952Sdim addProcResource(*WritePRI, ProcModels[PIdx], ProcWriteResDef->getLoc()); 2131243830Sdim } 2132243830Sdim} 2133243830Sdim 2134243830Sdim// Add resources for a ReadAdvance to this processor if they don't exist. 2135243830Sdimvoid CodeGenSchedModels::addReadAdvance(Record *ProcReadAdvanceDef, 2136243830Sdim unsigned PIdx) { 2137243830Sdim RecVec &RADefs = ProcModels[PIdx].ReadAdvanceDefs; 2138314564Sdim if (is_contained(RADefs, ProcReadAdvanceDef)) 2139243830Sdim return; 2140243830Sdim RADefs.push_back(ProcReadAdvanceDef); 2141243830Sdim} 2142243830Sdim 2143243830Sdimunsigned CodeGenProcModel::getProcResourceIdx(Record *PRDef) const { 2144314564Sdim RecIter PRPos = find(ProcResourceDefs, PRDef); 2145243830Sdim if (PRPos == ProcResourceDefs.end()) 2146243830Sdim PrintFatalError(PRDef->getLoc(), "ProcResource def is not included in " 2147243830Sdim "the ProcResources list for " + ModelName); 2148243830Sdim // Idx=0 is reserved for invalid. 2149243830Sdim return 1 + (PRPos - ProcResourceDefs.begin()); 2150243830Sdim} 2151243830Sdim 2152309124Sdimbool CodeGenProcModel::isUnsupported(const CodeGenInstruction &Inst) const { 2153309124Sdim for (const Record *TheDef : UnsupportedFeaturesDefs) { 2154309124Sdim for (const Record *PredDef : Inst.TheDef->getValueAsListOfDefs("Predicates")) { 2155309124Sdim if (TheDef->getName() == PredDef->getName()) 2156309124Sdim return true; 2157309124Sdim } 2158309124Sdim } 2159309124Sdim return false; 2160309124Sdim} 2161309124Sdim 2162239310Sdim#ifndef NDEBUG 2163243830Sdimvoid CodeGenProcModel::dump() const { 2164243830Sdim dbgs() << Index << ": " << ModelName << " " 2165243830Sdim << (ModelDef ? ModelDef->getName() : "inferred") << " " 2166243830Sdim << (ItinsDef ? ItinsDef->getName() : "no itinerary") << '\n'; 2167243830Sdim} 2168243830Sdim 2169243830Sdimvoid CodeGenSchedRW::dump() const { 2170243830Sdim dbgs() << Name << (IsVariadic ? " (V) " : " "); 2171243830Sdim if (IsSequence) { 2172243830Sdim dbgs() << "("; 2173243830Sdim dumpIdxVec(Sequence); 2174243830Sdim dbgs() << ")"; 2175239310Sdim } 2176239310Sdim} 2177243830Sdim 2178243830Sdimvoid CodeGenSchedClass::dump(const CodeGenSchedModels* SchedModels) const { 2179249423Sdim dbgs() << "SCHEDCLASS " << Index << ":" << Name << '\n' 2180243830Sdim << " Writes: "; 2181243830Sdim for (unsigned i = 0, N = Writes.size(); i < N; ++i) { 2182243830Sdim SchedModels->getSchedWrite(Writes[i]).dump(); 2183243830Sdim if (i < N-1) { 2184243830Sdim dbgs() << '\n'; 2185243830Sdim dbgs().indent(10); 2186243830Sdim } 2187243830Sdim } 2188243830Sdim dbgs() << "\n Reads: "; 2189243830Sdim for (unsigned i = 0, N = Reads.size(); i < N; ++i) { 2190243830Sdim SchedModels->getSchedRead(Reads[i]).dump(); 2191243830Sdim if (i < N-1) { 2192243830Sdim dbgs() << '\n'; 2193243830Sdim dbgs().indent(10); 2194243830Sdim } 2195243830Sdim } 2196243830Sdim dbgs() << "\n ProcIdx: "; dumpIdxVec(ProcIndices); dbgs() << '\n'; 2197249423Sdim if (!Transitions.empty()) { 2198249423Sdim dbgs() << "\n Transitions for Proc "; 2199327952Sdim for (const CodeGenSchedTransition &Transition : Transitions) { 2200327952Sdim dumpIdxVec(Transition.ProcIndices); 2201249423Sdim } 2202249423Sdim } 2203243830Sdim} 2204243830Sdim 2205243830Sdimvoid PredTransitions::dump() const { 2206243830Sdim dbgs() << "Expanded Variants:\n"; 2207243830Sdim for (std::vector<PredTransition>::const_iterator 2208243830Sdim TI = TransVec.begin(), TE = TransVec.end(); TI != TE; ++TI) { 2209243830Sdim dbgs() << "{"; 2210243830Sdim for (SmallVectorImpl<PredCheck>::const_iterator 2211243830Sdim PCI = TI->PredTerm.begin(), PCE = TI->PredTerm.end(); 2212243830Sdim PCI != PCE; ++PCI) { 2213243830Sdim if (PCI != TI->PredTerm.begin()) 2214243830Sdim dbgs() << ", "; 2215243830Sdim dbgs() << SchedModels.getSchedRW(PCI->RWIdx, PCI->IsRead).Name 2216243830Sdim << ":" << PCI->Predicate->getName(); 2217243830Sdim } 2218243830Sdim dbgs() << "},\n => {"; 2219314564Sdim for (SmallVectorImpl<SmallVector<unsigned,4>>::const_iterator 2220243830Sdim WSI = TI->WriteSequences.begin(), WSE = TI->WriteSequences.end(); 2221243830Sdim WSI != WSE; ++WSI) { 2222243830Sdim dbgs() << "("; 2223243830Sdim for (SmallVectorImpl<unsigned>::const_iterator 2224243830Sdim WI = WSI->begin(), WE = WSI->end(); WI != WE; ++WI) { 2225243830Sdim if (WI != WSI->begin()) 2226243830Sdim dbgs() << ", "; 2227243830Sdim dbgs() << SchedModels.getSchedWrite(*WI).Name; 2228243830Sdim } 2229243830Sdim dbgs() << "),"; 2230243830Sdim } 2231243830Sdim dbgs() << "}\n"; 2232243830Sdim } 2233243830Sdim} 2234243830Sdim#endif // NDEBUG 2235