[MC][PredicateExpander] Extend the grammar to support simple switch and return statements.

[andreadb]

Summary

This patch introduces tablegen class MCStatement.

Currently, an MCStatement can be either a return statement, or a switch statement.

MCStatement:
   MCReturnStatement
   MCOpcodeSwitchStatement

A MCReturnStatement expands to a return statement, and the boolean expression associated with the return statement is described by a MCInstPredicate.

An MCOpcodeSwitchStatement is a switch statement where the condition is a check on the machine opcode. It allows the definition of multiple checks, as well as a default case. More details on the grammar implemented by these two new constructs can be found in the diff for TargetInstrPredicates.td.

With this patch, method "isThreeOperandsLEA" becomes more readable (see below):

static bool isThreeOperandsLEA(const MachineInstr &MI) {
  switch(MI.getOpcode()) {
  case X86::LEA32r :
  case X86::LEA64r :
  case X86::LEA64_32r :
  case X86::LEA16r :
    return (
      MI.getOperand(1).isReg()
      && MI.getOperand(1).getReg() != 0
      && MI.getOperand(3).isReg()
      && MI.getOperand(3).getReg() != 0
      && (
        (
          MI.getOperand(4).isImm()
          && MI.getOperand(4).getImm() != 0
        )
        || (MI.getOperand(4).isGlobal())
      )
    );
  default :
    return false;
  } // end of switch-stmt
}

Before it was like this:

static bool isThreeOperandsLEA(const MachineInstr &MI) {
  return (
    (
      MI.getOpcode() == X86::LEA32r
      || MI.getOpcode() == X86::LEA64r
      || MI.getOpcode() == X86::LEA64_32r
      || MI.getOpcode() == X86::LEA16r
    )
    && MI.getOperand(1).isReg()
    && MI.getOperand(1).getReg() != 0
    && MI.getOperand(3).isReg()
    && MI.getOperand(3).getReg() != 0
    && (
      (
        MI.getOperand(4).isImm()
        && MI.getOperand(4).getImm() != 0
      )
      || (MI.getOperand(4).isGlobal())
    )
  );
}

This patch makes it easier to read the body of auto-generated TargetInstrInfo predicates.

I also plan to reuse/extend the grammar of MCStatements to enable the definition of more complex TII hooks.

For example, I'd like in future to expand this framework to better expose dependency-breaking instructions and also instructions that have an implicit (often undocumented) false dependency on the output register (I will raise a PR for this last task). Knowledge about dep-breaking instructions (and false-deps on the output registers) could then be used by tools like llvm-mca to perform a more accurate data dependency analysis. We could also expose that knowledge to machine schedulers (for example: to tweak the data dependency graph) to improve the schedule at the end of the process.
For now, this is just a first step (mostly a minor cosmetic change to polish the new predicates framework).

Please let me know what you think.

Thanks,
-Andrea

[mattd]

I really like this change! The result is easier to read.

utils/TableGen/PredicateExpander.cpp

186

I'm curious, do we assume all cases are fall-through? I don't see a break statement being generated, perhaps I overlooked that?

utils/TableGen/PredicateExpander.h

82

nit: Don't really need this whitespace.

[andreadb]

utils/TableGen/PredicateExpander.cpp

186

Your analysis is correct.
By construction, this new grammar only allows structures that end with return statements. Since there cannot be a fall-through, I avoided to generate a redundant break at the end of each case.

utils/TableGen/PredicateExpander.h

82

I will fix it. Thanks.

[mattd]

utils/TableGen/PredicateExpander.cpp

186

Ah, yep. That makes sense, thanks!

[mattd]

Thanks for this patch! LGTM.

include/llvm/Target/TargetInstrPredicate.td

 // Check that all of the predicates in `Preds` evaluate to true.
 class CheckAll<list<MCInstPredicate> Sequence>
     : CheckPredicateSequence<Sequence>;
 
 // Check that at least one of the predicates in `Preds` evaluates to true.
 class CheckAny<list<MCInstPredicate> Sequence>
     : CheckPredicateSequence<Sequence>;
 
+
+// Used to expand the body of a function predicate. See the definition of
+// TIIPredicate below.
+class MCStatement;
+
+// Expands to a return statement. The return expression is a boolean expression
+// described by a MCInstPredicate.
+class MCReturnStatement<MCInstPredicate predicate> : MCStatement {
+  MCInstPredicate Pred = predicate;
+}
+
+// Used to automatically construct cases of a switch statement where the switch
+// variable is an instruction opcode. There is a 'case' for every opcode in the
+// `opcodes` list, and each case is associated with MCStatement `caseStmt`.
+class MCOpcodeSwitchCase<list<Instruction> opcodes, MCStatement caseStmt> {
+  list<Instruction> Opcodes = opcodes;
+  MCStatement CaseStmt = caseStmt;
+}
+
+// Expands to a switch statement. The switch variable is an instruction opcode.
+// The auto-generated switch is populated by a number of cases based on the
+// `cases` list in input. A default case is automatically generated, and it
+// evaluates to `default`.
+class MCOpcodeSwitchStatement<list<MCOpcodeSwitchCase> cases,
+                              MCStatement default> : MCStatement {
+  list<MCOpcodeSwitchCase> Cases = cases;
+  MCStatement DefaultCase = default;
+}
+
 // Check that a call to method `Name` in class "XXXGenInstrInfo" (where XXX is
 // the `Target` name) returns true.
 //
 // TIIPredicate definitions are used to model calls to the target-specific
 // InstrInfo. A TIIPredicate is treated specially by the InstrInfoEmitter
 // tablegen backend, which will use it to automatically generate a definition in
 // the target specific `GenInstrInfo` class.
-class TIIPredicate<string Target, string Name, MCInstPredicate P> : MCInstPredicate {
+class TIIPredicate<string Target, string Name, MCStatement body>
+    : MCInstPredicate {
   string TargetName = Target;
   string FunctionName = Name;
-  MCInstPredicate Pred = P;
+  MCStatement Body = body;
 }
 
 // A function predicate that takes as input a machine instruction, and returns
 // a boolean value.
 //
 // This predicate is expanded into a function call by the PredicateExpander.
 // In particular, the PredicateExpander would either expand this predicate into
 // a call to `MCInstFn`, or into a call to`MachineInstrFn` depending on whether
 // it is lowering predicates for MCInst or MachineInstr.
 //
 // In this context, `MCInstFn` and `MachineInstrFn` are both function names.
 class CheckFunctionPredicate<string MCInstFn, string MachineInstrFn> : MCInstPredicate {
   string MCInstFnName = MCInstFn;
   string MachineInstrFnName = MachineInstrFn;
 }

lib/Target/X86/X86SchedPredicates.td

 
 // A predicate used to identify dependency-breaking instructions that clear the
 // content of the destination register. Note that this predicate only checks if
 // input registers are the same. This predicate doesn't make any assumptions on
 // the expected instruction opcodes, because different processors may implement
 // different zero-idioms.
 def ZeroIdiomPredicate : CheckSameRegOperand<1, 2>;
 
-// A predicate used to check if an instruction is a LEA, and if it uses all
-// three source operands: base, index, and offset.
+// A predicate used to check if a LEA instruction uses all three source
+// operands: base, index, and offset.
 def IsThreeOperandsLEAPredicate: CheckAll<[
-  CheckOpcode<[LEA32r, LEA64r, LEA64_32r, LEA16r]>,
-
   // isRegOperand(Base)
   CheckIsRegOperand<1>,
   CheckNot<CheckInvalidRegOperand<1>>,
 
   // isRegOperand(Index)
   CheckIsRegOperand<3>,
   CheckNot<CheckInvalidRegOperand<3>>,
 
   // hasLEAOffset(Offset)
   CheckAny<[
     CheckAll<[
       CheckIsImmOperand<4>,
       CheckNot<CheckZeroOperand<4>>
     ]>,
     CheckNonPortable<"MI.getOperand(4).isGlobal()">
   ]>
 ]>;
 
+def LEACases : MCOpcodeSwitchCase<
+    [LEA32r, LEA64r, LEA64_32r, LEA16r],
+    MCReturnStatement<IsThreeOperandsLEAPredicate>
+>;
+
+// Used to generate the body of a TII member function.
+def IsThreeOperandsLEABody :
+    MCOpcodeSwitchStatement<[LEACases], MCReturnStatement<FalsePred>>;
+
 // This predicate evaluates to true only if the input machine instruction is a
 // 3-operands LEA.  Tablegen automatically generates a new method for it in
 // X86GenInstrInfo.
 def IsThreeOperandsLEAFn :
-    TIIPredicate<"X86", "isThreeOperandsLEA", IsThreeOperandsLEAPredicate>;
+    TIIPredicate<"X86", "isThreeOperandsLEA", IsThreeOperandsLEABody>;

utils/TableGen/InstrInfoEmitter.cpp

void InstrInfoEmitter::emitMCIIHelperMethods(raw_ostream &OS) {
   FOS << "namespace llvm {\n";
   FOS << "namespace " << TargetName << "_MC {\n\n";
 
   PredicateExpander PE;
   PE.setExpandForMC(true);
   for (const Record *Rec : TIIPredicates) {
     FOS << "bool " << Rec->getValueAsString("FunctionName");
     FOS << "(const MCInst &MI) {\n";
-    FOS << "  return ";
-    PE.expandPredicate(FOS, Rec->getValueAsDef("Pred"));
-    FOS << ";\n}\n";
+    PE.expandStatement(FOS, Rec->getValueAsDef("Body"));
+    FOS << "\n}\n";
   }
 
   FOS << "\n} // end " << TargetName << "_MC namespace\n";
   FOS << "} // end llvm namespace\n\n";
 
   FOS << "#endif // GET_GENISTRINFO_MC_HELPERS\n";
 }
 
 void InstrInfoEmitter::emitTIIHelperMethods(raw_ostream &OS) {
   RecVec TIIPredicates = Records.getAllDerivedDefinitions("TIIPredicate");
   if (TIIPredicates.empty())
     return;
 
   formatted_raw_ostream FOS(OS);
   PredicateExpander PE;
   PE.setExpandForMC(false);
   PE.setIndentLevel(2);
 
   for (const Record *Rec : TIIPredicates) {
     FOS << "\n  static bool " << Rec->getValueAsString("FunctionName");
     FOS << "(const MachineInstr &MI) {\n";
-    FOS << "    return ";
-    PE.expandPredicate(FOS, Rec->getValueAsDef("Pred"));
-    FOS << ";\n  }\n";
+    PE.expandStatement(FOS, Rec->getValueAsDef("Body"));
+    FOS << "\n  }\n";
   }
 }
 
 //===----------------------------------------------------------------------===//
 // Main Output.
 //===----------------------------------------------------------------------===//
 
 // run - Emit the main instruction description records for the target...

utils/TableGen/PredicateExpander.h

public:
   void expandCheckIsRegOperand(formatted_raw_ostream &OS, int OpIndex);
   void expandCheckIsImmOperand(formatted_raw_ostream &OS, int OpIndex);
   void expandCheckInvalidRegOperand(formatted_raw_ostream &OS, int OpIndex);
   void expandCheckFunctionPredicate(formatted_raw_ostream &OS,
                                     StringRef MCInstFn,
                                     StringRef MachineInstrFn);
   void expandCheckNonPortable(formatted_raw_ostream &OS, StringRef CodeBlock);
   void expandPredicate(formatted_raw_ostream &OS, const Record *Rec);
+
+  void expandReturnStatement(formatted_raw_ostream &OS, const Record *Rec);
+  void expandOpcodeSwitchCase(formatted_raw_ostream &OS, const Record *Rec);
+  void expandOpcodeSwitchStatement(formatted_raw_ostream &OS,
+                                   const RecVec &Cases, const Record *Default);
+  void expandStatement(formatted_raw_ostream &OS, const Record *Rec);
 };
 
 } // namespace llvm
 
 #endif

utils/TableGen/PredicateExpander.cpp

 void PredicateExpander::expandCheckNonPortable(formatted_raw_ostream &OS,
                                                StringRef Code) {
   if (shouldExpandForMC())
     return expandFalse(OS);
 
   OS << '(' << Code << ')';
 }
 
+void PredicateExpander::expandReturnStatement(formatted_raw_ostream &OS,
+                                              const Record *Rec) {
+  OS << "return ";
+  expandPredicate(OS, Rec);
+  OS << ";";
+}
+
+void PredicateExpander::expandOpcodeSwitchCase(formatted_raw_ostream &OS,
+                                         const Record *Rec) {
+  const RecVec &Opcodes = Rec->getValueAsListOfDefs("Opcodes");
+  for (const Record *Opcode : Opcodes) {
+    OS.PadToColumn(getIndentLevel() * 2);
+    OS << "case " << Opcode->getValueAsString("Namespace") << "::"
+       << Opcode->getName() << " :\n";
+  }
+
+  increaseIndentLevel();
+  expandStatement(OS, Rec->getValueAsDef("CaseStmt"));
+  decreaseIndentLevel();
+}
+
+void PredicateExpander::expandOpcodeSwitchStatement(formatted_raw_ostream &OS,
+                                                    const RecVec &Cases,
+                                                    const Record *Default) {
+  OS << "switch(MI" << (isByRef() ? "." : "->") << "getOpcode()) {\n";
+
+  for (const Record *Rec : Cases) {
+    expandOpcodeSwitchCase(OS, Rec);
+    OS << '\n';
+  }
+
+  unsigned ColNum = getIndentLevel() * 2;
+  OS.PadToColumn(ColNum);
+
+  // Expand the default case.
+  OS << "default :\n";
+  increaseIndentLevel();
+  expandStatement(OS, Default);
+  decreaseIndentLevel();
+  OS << '\n';
+
+  OS.PadToColumn(ColNum);
+  OS << "} // end of switch-stmt"; 
+}
+
+void PredicateExpander::expandStatement(formatted_raw_ostream &OS,
+                                        const Record *Rec) {
+  OS.flush();
+  unsigned ColNum = getIndentLevel() * 2;
+  if (OS.getColumn() < ColNum)
+    OS.PadToColumn(ColNum);
+
+  if (Rec->isSubClassOf("MCOpcodeSwitchStatement")) {
+    expandOpcodeSwitchStatement(OS, Rec->getValueAsListOfDefs("Cases"),
+                                Rec->getValueAsDef("DefaultCase"));
+    return;
+  }
+
+  if (Rec->isSubClassOf("MCReturnStatement")) {
+    expandReturnStatement(OS, Rec->getValueAsDef("Pred"));
+    return;
+  }
+
+  llvm_unreachable("No known rules to expand this MCStatement");
+}
+
 void PredicateExpander::expandPredicate(formatted_raw_ostream &OS,
                                         const Record *Rec) {
   OS.flush();
   unsigned ColNum = getIndentLevel() * 2;
   if (OS.getColumn() < ColNum)
     OS.PadToColumn(ColNum);
 
   if (Rec->isSubClassOf("MCTrue")) {