[TableGen] Add generation of argument register lists

[void]

Summary

There are cases, like with -fzero-call-used-regs, where we need to know
which registers can be used by a certain calling convention. This change
generates a list of registers used by each calling convention defined in
*CallingConv.td.

Calling conventions that use registers conditioned on Swift have those
registers placed in a separate list. This allows us to be flexible about
whether to use the Swift registers or not.

[nickdesaulniers]

llvm/utils/TableGen/CallingConvEmitter.cpp

29

I know the current code is using std::string without explicitly including <string>, but would you mind please cleaning that up here (in this patch)?

Also curious if we should be preferring containers from ADT?

73

What is this code doing? Trying to create a key without an subsequent entry? Suspicious.

105–110

Can you clarify in the commit message why CCIfSwift needs special/distinct handling? Swift seems to be introducing a bit of complexity to the feature, and I don't yet understand precisely why.

330

This is a common case for just using auto & in your range for loops.

334–381

All of this code would be more readable if you took references to Entry.first and Entry.second and gave them meaningful identifiers. C++ code heavy on map entries makes it a PITA to keep track without looking at the type definition of the map what types the keys and values even are. For example:

for (auto &Entry : AssignedRegsMap) {
  StringRef Regname = Entry.first;
  std::set<std::string> &Registers = Entry.second;

  if (Regname.empty())
    continue;

  O << "const MCRegister " << Regname << "_ArgRegs[] = { ";
  
  if (Registers.empty()) {
    ...

[void]

Update with better documentation and variable names.

llvm/utils/TableGen/CallingConvEmitter.cpp

29

I *really* hate adding headers that aren't necessary. Is this some kind of style guide violation?

73

Yes. I want it to have an entry, even if empty, for all actions that we're processing. I'll make the comment clearer.

330

I wish people would make up their minds about whether I should use auto or not. One day I shouldn't use it then the next I should. I don't see why I would suddenly use it here.

[nickdesaulniers]

llvm/utils/TableGen/CallingConvEmitter.cpp

29

It's definitely a google3 style violation.
https://google.github.io/styleguide/cppguide.html#Include_What_You_Use

Looks like it's not though for LLVM:
https://llvm.org/docs/CodingStandards.html#include-as-little-as-possible

You must include all of the header files that you are using — you can include them either directly or indirectly through another header file.

There's also https://llvm.org/docs/CodingStandards.html#include-style, but that doesn't seem to make a call either way either.

OK, I'll let that slide, but the comment still stands about using containers from ADT. We have a StringMap and StringSet
https://llvm.org/docs/ProgrammersManual.html#llvm-adt-stringmap-h
https://llvm.org/docs/ProgrammersManual.html#llvm-adt-stringset-h

330

https://llvm.org/docs/CodingStandards.html#use-auto-type-deduction-to-make-code-more-readable
Encourages the use of auto when the type doesn't already appear in the RHS of an assignment using a cast (in which case the type would be specified twice) or for iteration variable types.

[void]

Use better variable names and StringMap.

llvm/utils/TableGen/CallingConvEmitter.cpp

29

Looks like it's not though for LLVM:

Right. LLVM does things very differently from Google.

330

Using auto during in a for loop is exactly the complaint I got last time. The type of Entry, et al, isn't an iterator but the actual elements. So instead of going back and forth arguing about this, I'm keeping it as is.

[nickdesaulniers]

llvm/utils/TableGen/CallingConvEmitter.cpp

73

Can you do something like:

AssignedRegsMap[CurrentAction] = {};

Instead to insert an empty set?

[void]

Use a better method to create an empty entry.

[nickdesaulniers]

llvm/utils/TableGen/CallingConvEmitter.cpp

29

OK, I'll let that slide, but the comment still stands about using containers from ADT. We have a StringMap and StringSet

Though, looking at that goto...

https://llvm.org/docs/ProgrammersManual.html#llvm-adt-stringmap-h

StringMap iteration order, however, is not guaranteed to be deterministic, so any uses which require that should instead use a std::map.

We iterate all three of these; I'm guessing it might be nice to do so deterministically? Otherwise rebuilding LLVM might produce a different order of these registers?

Further, I think std::map provides iterator invalidation guarantees on erasure that might help you avoid goto if you used the old fashioned non-range for loop.

71–75

Can we sink these two statements

CurrentAction = CC->getName().str();
AssignedRegsMap[CurrentAction] = {};

into the definition of EmitCallingConv?

107–109

StringRef Name = Class.first->getNameInitAsString();
return Name.startswith("CCIfSwift");

Not sure if that would fit on one line if it was a single statement?

333–354

i.e. I _think_ you could avoid the goto here with:

for (auto *It = DelgateToMap.begin(), E = DelegateToMap.end(); Entry != E; ++E) {
  StringRef Regname = It->first();
  ...
  DelegateToMap.erase(RegName.str());
}

if DelegateToMap was a std::map.
https://stackoverflow.com/a/54004916
(Iterator invalidation being the weak point to range-for)

392–393

If Registers is empty, do we need to insert an explicit 0 like we do for the non-swift AssignedRegsMap? Or do no work if RegName is empty?

The two cases seem pretty similar otherwise; am curious if they can be DRY'd up?

[nickdesaulniers]

llvm/utils/TableGen/CallingConvEmitter.cpp

333–354

for (auto *It = DelgateToMap.begin(), E = DelegateToMap.end(); Entry != E; ++E) {

Sorry, only renamed one of the expressions, should have been

for (auto *It = DelgateToMap.begin(), E = DelegateToMap.end(); It != E; ++It) {

[void]

Remove the "{ 0 }" initialier since we don't need the "0" there.

llvm/utils/TableGen/CallingConvEmitter.cpp

29

It's not iterator invalidation that I'm concerned about. It needs to continually go through the list and process the sets in a specific way---that is the sets in
AssignedRegsMap are modified with the newer information. It removes the entry from the map when we no longer need to consider it. There may be ways to get around using a goto, but they're much clunkier than simply using one (i.e. using a flag or a convoluted use of a worklist).

71–75

Okay, but could we keep the review to issues about the algorithm and not coding style please?

107–109

It goes over 80 columns.

333–354

See comment about goto above.

392–393

At one point, it was giving me a diagnostic about that type of initialization being a C++17 feature. I guess I changed the code enough that it went away. Done.

[void]

Avoid warning about zero-sized arrays:

lib/Target/AArch64/AArch64GenCallingConv.inc:1266:64: warning: zero size arrays are an extension [-Wzero-length-array]
const MCRegister CC_AArch64_DarwinPCS_ILP32_VarArg_ArgRegs[] = {  };

[void]

Friendly ping. :)

[nickdesaulniers]

llvm/utils/TableGen/CallingConvEmitter.cpp

29

What about my concern about deterministic iteration order?

71–75

Whatever. Code style is an inseparable part of code review. Otherwise it makes my review approval just a rubber stamp. And if it's just a rubber stamp, why even waste my time asking for review?

107–109

I still think the pair of expressions need not make any mention of std::string if you just construct a StringRef from the get go.

333–354

I still think this could be rewritten to avoid the use of goto.

[nickdesaulniers]

llvm/utils/TableGen/CallingConvEmitter.cpp

107–109

s/expressions/statements/

[void]

llvm/utils/TableGen/CallingConvEmitter.cpp

71–75

But you ask for changes that make no real difference in the code. It's like you're doing it because you think you MUST find something to comment on, otherwise it'll be a "rubber stamp", which isn't true. I'm not a junior level programmer. When I do things it's for a reason. I put these two statements where they were because the information is global, so it made more sense to me to place them in a global setting and not sink them down into a called function. You may disagree with that, but that's just what it is, a disagreement.

What I need from a review is someone to look at the code and say, "Oh! this could be better done this way," or "You forgot to account for this." I'm not really looking for someone to say, "This line of code could use this format and not this format," when the result is the same. If there's an egregious violation of the style guide, then sure point that out. But otherwise, it's okay to allow people to program in their own fashion.

107–109

Oh, sorry. I misunderstood what you wanted. Done.

333–354

You were right. Sorry about that. Done.

[void]

Remove "goto" for a worklist.

[void]

Fix up worklist loop.

[void]

llvm/utils/TableGen/CallingConvEmitter.cpp

107–109

The reason I did that initially was to avoid this warning:

/home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/llvm-project/llvm/utils/TableGen/CallingConvEmitter.cpp:108:38: error: object backing the pointer will be destroyed at the end of the full-expression [-Werror,-Wdangling-gsl]
                                     Class.first->getNameInitAsString();
                                     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

llvm/utils/TableGen/CallingConvEmitter.cpp

 #include "llvm/TableGen/Error.h"
 #include "llvm/TableGen/Record.h"
 #include "llvm/TableGen/TableGenBackend.h"
 using namespace llvm;
 
 namespace {
 class CallingConvEmitter {
   RecordKeeper &Records;
+  unsigned Counter;
+  std::string CurrentAction;
+  bool SwiftAction;
+
+  StringMap<std::set<std::string>> AssignedRegsMap;
+  StringMap<std::set<std::string>> AssignedSwiftRegsMap;
+  StringMap<std::set<std::string>> DelegateToMap;
+
 public:
   explicit CallingConvEmitter(RecordKeeper &R) : Records(R) {}
 
   void run(raw_ostream &o);
 
 private:
   void EmitCallingConv(Record *CC, raw_ostream &O);
   void EmitAction(Record *Action, unsigned Indent, raw_ostream &O);
-  unsigned Counter;
+  void EmitArgRegisterLists(raw_ostream &O);
 };
 } // End anonymous namespace
 
 void CallingConvEmitter::run(raw_ostream &O) {
   std::vector<Record*> CCs = Records.getAllDerivedDefinitions("CallingConv");
 
   // Emit prototypes for all of the non-custom CC's so that they can forward ref
   // each other.
   Records.startTimer("Emit prototypes");
+  O << "#ifndef GET_CC_REGISTER_LISTS\n\n";
   for (Record *CC : CCs) {
     if (!CC->getValueAsBit("Custom")) {
       unsigned Pad = CC->getName().size();
       if (CC->getValueAsBit("Entry")) {
         O << "bool llvm::";
         Pad += 12;
       } else {
         O << "static bool ";
         Pad += 13;
       }
       O << CC->getName() << "(unsigned ValNo, MVT ValVT,\n"
         << std::string(Pad, ' ') << "MVT LocVT, CCValAssign::LocInfo LocInfo,\n"
         << std::string(Pad, ' ')
         << "ISD::ArgFlagsTy ArgFlags, CCState &State);\n";
     }
   }
 
   // Emit each non-custom calling convention description in full.
   Records.startTimer("Emit full descriptions");
   for (Record *CC : CCs) {
-    if (!CC->getValueAsBit("Custom"))
+    if (!CC->getValueAsBit("Custom")) {
       EmitCallingConv(CC, O);
     }
   }
 
+  EmitArgRegisterLists(O);
+
+  O << "\n#endif // CC_REGISTER_LIST\n";
+}
 
 void CallingConvEmitter::EmitCallingConv(Record *CC, raw_ostream &O) {
   ListInit *CCActions = CC->getValueAsListInit("Actions");
   Counter = 0;
 
+  CurrentAction = CC->getName().str();
+  // Call upon the creation of a map entry from the void!
+  // We want an entry in AssignedRegsMap for every action, even if that
+  // entry is empty.
+  AssignedRegsMap[CurrentAction] = {};
+
   O << "\n\n";
-  unsigned Pad = CC->getName().size();
+  unsigned Pad = CurrentAction.size();
   if (CC->getValueAsBit("Entry")) {
     O << "bool llvm::";
     Pad += 12;
   } else {
     O << "static bool ";
     Pad += 13;
   }
-  O << CC->getName() << "(unsigned ValNo, MVT ValVT,\n"
+  O << CurrentAction << "(unsigned ValNo, MVT ValVT,\n"
     << std::string(Pad, ' ') << "MVT LocVT, CCValAssign::LocInfo LocInfo,\n"
     << std::string(Pad, ' ') << "ISD::ArgFlagsTy ArgFlags, CCState &State) {\n";
   // Emit all of the actions, in order.
   for (unsigned i = 0, e = CCActions->size(); i != e; ++i) {
+    Record *Action = CCActions->getElementAsRecord(i);
+    SwiftAction = llvm::any_of(Action->getSuperClasses(),
+                               [](const std::pair<Record *, SMRange> &Class) {
+                                 std::string Name =
+                                     Class.first->getNameInitAsString();
+                                 return StringRef(Name).startswith("CCIfSwift");
+                               });
+
     O << "\n";
-    EmitAction(CCActions->getElementAsRecord(i), 2, O);
+    EmitAction(Action, 2, O);
   }
   
   O << "\n  return true; // CC didn't match.\n";
   O << "}\n";
 }
 
 void CallingConvEmitter::EmitAction(Record *Action,
                                     unsigned Indent, raw_ostream &O) {
   std::string IndentStr = std::string(Indent, ' ');
-  
   if (Action->isSubClassOf("CCPredicateAction")) {
     O << IndentStr << "if (";
     
     if (Action->isSubClassOf("CCIfType")) {
       ListInit *VTs = Action->getValueAsListInit("VTs");
       for (unsigned i = 0, e = VTs->size(); i != e; ++i) {
         Record *VT = VTs->getElementAsRecord(i);
         if (i != 0) O << " ||\n    " << IndentStr;
if (Action->isSubClassOf("CCPredicateAction")) {
     EmitAction(Action->getValueAsDef("SubAction"), Indent+2, O);
     O << IndentStr << "}\n";
   } else {
     if (Action->isSubClassOf("CCDelegateTo")) {
       Record *CC = Action->getValueAsDef("CC");
       O << IndentStr << "if (!" << CC->getName()
         << "(ValNo, ValVT, LocVT, LocInfo, ArgFlags, State))\n"
         << IndentStr << "  return false;\n";
+      DelegateToMap[CurrentAction].insert(CC->getName().str());
     } else if (Action->isSubClassOf("CCAssignToReg")) {
       ListInit *RegList = Action->getValueAsListInit("RegList");
       if (RegList->size() == 1) {
-        O << IndentStr << "if (unsigned Reg = State.AllocateReg(";
-        O << getQualifiedName(RegList->getElementAsRecord(0)) << ")) {\n";
+        std::string Name = getQualifiedName(RegList->getElementAsRecord(0));
+        O << IndentStr << "if (unsigned Reg = State.AllocateReg(" << Name
+          << ")) {\n";
+        if (SwiftAction)
+          AssignedSwiftRegsMap[CurrentAction].insert(Name);
+        else
+          AssignedRegsMap[CurrentAction].insert(Name);
       } else {
         O << IndentStr << "static const MCPhysReg RegList" << ++Counter
           << "[] = {\n";
         O << IndentStr << "  ";
         ListSeparator LS;
-        for (unsigned i = 0, e = RegList->size(); i != e; ++i)
-          O << LS << getQualifiedName(RegList->getElementAsRecord(i));
+        for (unsigned i = 0, e = RegList->size(); i != e; ++i) {
+          std::string Name = getQualifiedName(RegList->getElementAsRecord(i));
+          if (SwiftAction)
+            AssignedSwiftRegsMap[CurrentAction].insert(Name);
+          else
+            AssignedRegsMap[CurrentAction].insert(Name);
+          O << LS << Name;
+        }
         O << "\n" << IndentStr << "};\n";
         O << IndentStr << "if (unsigned Reg = State.AllocateReg(RegList"
           << Counter << ")) {\n";
       }
       O << IndentStr << "  State.addLoc(CCValAssign::getReg(ValNo, ValVT, "
         << "Reg, LocVT, LocInfo));\n";
       O << IndentStr << "  return false;\n";
       O << IndentStr << "}\n";
if (Action->isSubClassOf("CCDelegateTo")) {
       O << IndentStr << "  return false;\n";
     } else {
       errs() << *Action;
       PrintFatalError(Action->getLoc(), "Unknown CCAction!");
     }
   }
 }
 
+void CallingConvEmitter::EmitArgRegisterLists(raw_ostream &O) {
+  using EntryTy = StringMap<std::set<std::string>>::MapEntryTy;
+
+  // Transitively merge all delegated CCs into AssignedRegsMap.
+restart:
+  for (EntryTy &Entry : DelegateToMap) {
+    StringRef RegName = Entry.first();
+    std::set<std::string> &Registers = Entry.second;
+    if (!Registers.empty())
+      continue;
+
+    for (EntryTy &InnerEntry : DelegateToMap) {
+      StringRef InnerRegName = InnerEntry.first();
+      std::set<std::string> &InnerRegisters = InnerEntry.second;
+
+      if (InnerRegisters.find(RegName.str()) != InnerRegisters.end()) {
+        AssignedRegsMap[InnerRegName].insert(
+            AssignedRegsMap[RegName].begin(),
+            AssignedRegsMap[RegName].end());
+        InnerRegisters.erase(RegName.str());
+      }
+    }
+
+    DelegateToMap.erase(RegName.str());
+    goto restart;
+  }
+
+  if (AssignedRegsMap.empty())
+    return;
+
+  O << "\n#else\n\n";
+
+  for (EntryTy &Entry : AssignedRegsMap) {
+    StringRef RegName = Entry.first();
+    std::set<std::string> &Registers = Entry.second;
+
+    if (RegName.empty())
+      continue;
+
+    O << "const MCRegister " << Entry.first() << "_ArgRegs[] = { ";
+
+    ListSeparator LS;
+    for (const std::string &Reg : Registers)
+      O << LS << Reg;
+
+    O << " };\n";
+  }
+
+  if (AssignedSwiftRegsMap.empty())
+    return;
+
+  O << "\n// Registers used by Swift.\n";
+  for (EntryTy &Entry : AssignedSwiftRegsMap) {
+    StringRef RegName = Entry.first();
+    std::set<std::string> &Registers = Entry.second;
+
+    O << "const MCRegister " << RegName << "_Swift_ArgRegs[] = { ";
+
+    ListSeparator LS;
+    for (const std::string &Reg : Registers)
+      O << LS << Reg;
+
+    O << " };\n";
+  }
+}
+
 namespace llvm {
 
 void EmitCallingConv(RecordKeeper &RK, raw_ostream &OS) {
   emitSourceFileHeader("Calling Convention Implementation Fragment", OS);
   CallingConvEmitter(RK).run(OS);
 }
 
 } // End llvm namespace