Merge branch 'main' into irbuilder-ompregionusers/meinersbur/irbuilder-ompregion

7 files changed, 239 insertions, 33 deletions

diff --git a/llvm/tools/llvm-reduce/CMakeLists.txt b/llvm/tools/llvm-reduce/CMakeLists.txt
index 6588fd8..88229d6 100644
--- a/llvm/tools/llvm-reduce/CMakeLists.txt
+++ b/llvm/tools/llvm-reduce/CMakeLists.txt
@@ -39,6 +39,7 @@ add_llvm_tool(llvm-reduce
   deltas/ReduceOperandsSkip.cpp
   deltas/ReduceOperandsToArgs.cpp
   deltas/ReduceInstructionsMIR.cpp
+  deltas/ReduceIRReferences.cpp
   llvm-reduce.cpp
 
   DEPENDS
diff --git a/llvm/tools/llvm-reduce/DeltaManager.cpp b/llvm/tools/llvm-reduce/DeltaManager.cpp
index 4abdf38..d3e8740 100644
--- a/llvm/tools/llvm-reduce/DeltaManager.cpp
+++ b/llvm/tools/llvm-reduce/DeltaManager.cpp
@@ -24,6 +24,7 @@
 #include "deltas/ReduceGlobalValues.h"
 #include "deltas/ReduceGlobalVarInitializers.h"
 #include "deltas/ReduceGlobalVars.h"
+#include "deltas/ReduceIRReferences.h"
 #include "deltas/ReduceInstructions.h"
 #include "deltas/ReduceInstructionsMIR.h"
 #include "deltas/ReduceMetadata.h"
@@ -67,7 +68,11 @@ static cl::opt<std::string>
   DELTA_PASS("module-data", reduceModuleDataDeltaPass)
 
 #define DELTA_PASSES_MIR                                                       \
-  DELTA_PASS("instructions", reduceInstructionsMIRDeltaPass)
+  DELTA_PASS("instructions", reduceInstructionsMIRDeltaPass)                   \
+  DELTA_PASS("ir-instruction-references",                                      \
+             reduceIRInstructionReferencesDeltaPass)                           \
+  DELTA_PASS("ir-block-references", reduceIRBlockReferencesDeltaPass)          \
+  DELTA_PASS("ir-function-references", reduceIRFunctionReferencesDeltaPass)
 
 static void runAllDeltaPasses(TestRunner &Tester) {
 #define DELTA_PASS(NAME, FUNC) FUNC(Tester);
@@ -105,18 +110,8 @@ void llvm::printDeltaPasses(raw_ostream &OS) {
 #undef DELTA_PASS
 }
 
-// FIXME: We might want to use a different metric than "number of
-// bytes in serialized IR" to detect non-progress of the main delta
-// loop
-static int getIRSize(TestRunner &Tester) {
-  std::string Str;
-  raw_string_ostream SS(Str);
-  Tester.getProgram().print(SS, /*AnnotationWriter=*/nullptr);
-  return Str.length();
-}
-
 void llvm::runDeltaPasses(TestRunner &Tester, int MaxPassIterations) {
-  int OldSize = getIRSize(Tester);
+  uint64_t OldComplexity = Tester.getProgram().getComplexityScore();
   for (int Iter = 0; Iter < MaxPassIterations; ++Iter) {
     if (DeltaPasses.empty()) {
       runAllDeltaPasses(Tester);
@@ -128,9 +123,9 @@ void llvm::runDeltaPasses(TestRunner &Tester, int MaxPassIterations) {
         Passes = Split.second;
       }
     }
-    int NewSize = getIRSize(Tester);
-    if (NewSize >= OldSize)
+    uint64_t NewComplexity = Tester.getProgram().getComplexityScore();
+    if (NewComplexity >= OldComplexity)
       break;
-    OldSize = NewSize;
+    OldComplexity = NewComplexity;
   }
 }
diff --git a/llvm/tools/llvm-reduce/ReducerWorkItem.cpp b/llvm/tools/llvm-reduce/ReducerWorkItem.cpp
index 01786a4..91ea752 100644
--- a/llvm/tools/llvm-reduce/ReducerWorkItem.cpp
+++ b/llvm/tools/llvm-reduce/ReducerWorkItem.cpp
@@ -473,3 +473,80 @@ void ReducerWorkItem::print(raw_ostream &ROS, void *p) const {
              /*ShouldPreserveUseListOrder=*/true);
   }
 }
+
+// FIXME: We might want to use a different metric than "number of
+// bytes in serialized IR" to detect non-progress of the main delta
+// loop
+uint64_t ReducerWorkItem::getIRSize() const {
+  std::string Str;
+  raw_string_ostream SS(Str);
+  print(SS, /*AnnotationWriter=*/nullptr);
+  return Str.length();
+}
+
+/// Try to produce some number that indicates a function is getting smaller /
+/// simpler.
+static uint64_t computeMIRComplexityScoreImpl(const MachineFunction &MF) {
+  uint64_t Score = 0;
+  const MachineFrameInfo &MFI = MF.getFrameInfo();
+
+  // Add for stack objects
+  Score += MFI.getNumObjects();
+
+  // Add in the block count.
+  Score += 2 * MF.size();
+
+  for (const MachineBasicBlock &MBB : MF) {
+    for (const MachineInstr &MI : MBB) {
+      const unsigned Opc = MI.getOpcode();
+
+      // Reductions may want or need to introduce implicit_defs, so don't count
+      // them.
+      // TODO: These probably should count in some way.
+      if (Opc == TargetOpcode::IMPLICIT_DEF ||
+          Opc == TargetOpcode::G_IMPLICIT_DEF)
+        continue;
+
+      // Each instruction adds to the score
+      Score += 4;
+
+      if (Opc == TargetOpcode::PHI || Opc == TargetOpcode::G_PHI ||
+          Opc == TargetOpcode::INLINEASM || Opc == TargetOpcode::INLINEASM_BR)
+        ++Score;
+
+      if (MI.getFlags() != 0)
+        ++Score;
+
+      // Increase weight for more operands.
+      for (const MachineOperand &MO : MI.operands()) {
+        ++Score;
+
+        // Treat registers as more complex.
+        if (MO.isReg()) {
+          ++Score;
+
+          // And subregisters as even more complex.
+          if (MO.getSubReg()) {
+            ++Score;
+            if (MO.isDef())
+              ++Score;
+          }
+        } else if (MO.isRegMask())
+          ++Score;
+      }
+    }
+  }
+
+  return Score;
+}
+
+uint64_t ReducerWorkItem::computeMIRComplexityScore() const {
+  uint64_t Score = 0;
+
+  for (const Function &F : getModule()) {
+    if (auto *MF = MMI->getMachineFunction(F))
+      Score += computeMIRComplexityScoreImpl(*MF);
+  }
+
+  return Score;
+}
diff --git a/llvm/tools/llvm-reduce/ReducerWorkItem.h b/llvm/tools/llvm-reduce/ReducerWorkItem.h
index d20ca18..89330d2b 100644
--- a/llvm/tools/llvm-reduce/ReducerWorkItem.h
+++ b/llvm/tools/llvm-reduce/ReducerWorkItem.h
@@ -27,6 +27,15 @@ public:
 
   void print(raw_ostream &ROS, void *p = nullptr) const;
   operator Module &() const { return *M; }
+
+  /// Return a number to indicate whether there was any reduction progress.
+  uint64_t getComplexityScore() const {
+    return isMIR() ? computeMIRComplexityScore() : getIRSize();
+  }
+
+private:
+  uint64_t computeMIRComplexityScore() const;
+  uint64_t getIRSize() const;
 };
 
 std::unique_ptr<ReducerWorkItem>
diff --git a/llvm/tools/llvm-reduce/deltas/ReduceIRReferences.cpp b/llvm/tools/llvm-reduce/deltas/ReduceIRReferences.cpp
new file mode 100644
index 0000000..975bdc2
--- /dev/null
+++ b/llvm/tools/llvm-reduce/deltas/ReduceIRReferences.cpp
@@ -0,0 +1,82 @@
+//===- ReduceIRReferences.cpp - Specialized Delta Pass --------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a function which calls the Generic Delta pass in order
+// to remove backreferences to the IR from MIR. In particular, this will remove
+// the Value references in MachineMemOperands.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ReduceIRReferences.h"
+#include "Delta.h"
+#include "llvm/CodeGen/MachineFrameInfo.h"
+
+using namespace llvm;
+
+static void dropIRReferencesFromInstructions(Oracle &O, MachineFunction &MF) {
+  for (MachineBasicBlock &MBB : MF) {
+    for (MachineInstr &MI : MBB) {
+      if (!O.shouldKeep()) {
+        for (MachineMemOperand *MMO : MI.memoperands()) {
+          // Leave behind pseudo source values.
+          // TODO: Removing all MemOperand values is a further reduction step.
+          if (MMO->getPointerInfo().V.is<const Value *>())
+            MMO->setValue(static_cast<const Value *>(nullptr));
+        }
+
+        // TODO: Try to remove GlobalValue references and metadata
+      }
+    }
+  }
+}
+
+static void stripIRFromInstructions(Oracle &O, ReducerWorkItem &WorkItem) {
+  for (const Function &F : WorkItem.getModule()) {
+    if (auto *MF = WorkItem.MMI->getMachineFunction(F))
+      dropIRReferencesFromInstructions(O, *MF);
+  }
+}
+
+static void stripIRFromBlocks(Oracle &O, ReducerWorkItem &WorkItem) {
+  for (const Function &F : WorkItem.getModule()) {
+    if (auto *MF = WorkItem.MMI->getMachineFunction(F)) {
+      for (MachineBasicBlock &MBB : *MF) {
+        if (!O.shouldKeep())
+          MBB.clearBasicBlock();
+      }
+    }
+  }
+}
+
+static void stripIRFromFunctions(Oracle &O, ReducerWorkItem &WorkItem) {
+  for (const Function &F : WorkItem.getModule()) {
+    if (!O.shouldKeep()) {
+      if (auto *MF = WorkItem.MMI->getMachineFunction(F)) {
+        MachineFrameInfo &MFI = MF->getFrameInfo();
+        for (int I = MFI.getObjectIndexBegin(), E = MFI.getObjectIndexEnd();
+             I != E; ++I)
+          MFI.clearObjectAllocation(I);
+      }
+    }
+  }
+}
+
+void llvm::reduceIRInstructionReferencesDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing IR references from instructions...\n";
+  runDeltaPass(Test, stripIRFromInstructions);
+}
+
+void llvm::reduceIRBlockReferencesDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing IR references from blocks...\n";
+  runDeltaPass(Test, stripIRFromBlocks);
+}
+
+void llvm::reduceIRFunctionReferencesDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing IR references from functions...\n";
+  runDeltaPass(Test, stripIRFromFunctions);
+}
diff --git a/llvm/tools/llvm-reduce/deltas/ReduceIRReferences.h b/llvm/tools/llvm-reduce/deltas/ReduceIRReferences.h
new file mode 100644
index 0000000..548559a
--- /dev/null
+++ b/llvm/tools/llvm-reduce/deltas/ReduceIRReferences.h
@@ -0,0 +1,31 @@
+//===- ReduceIRReferences.h  - Specialized Delta Pass -----------*- c++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a function which calls the Generic Delta pass in order
+// to reduce uninteresting IR references from the MachineFunction.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEIRREFERENCES_MIR_H
+#define LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEIRREFERENCES_MIR_H
+
+namespace llvm {
+class TestRunner;
+
+/// Remove IR references from instructions (i.e. from memory operands)
+void reduceIRInstructionReferencesDeltaPass(TestRunner &Test);
+
+/// Remove IR BasicBlock references (the block names)
+void reduceIRBlockReferencesDeltaPass(TestRunner &Test);
+
+/// Remove IR references from function level fields (e.g. frame object names)
+void reduceIRFunctionReferencesDeltaPass(TestRunner &Test);
+
+} // namespace llvm
+
+#endif
diff --git a/llvm/tools/llvm-reduce/deltas/ReduceInstructionsMIR.cpp b/llvm/tools/llvm-reduce/deltas/ReduceInstructionsMIR.cpp
index 3be2eae..f5486cf 100644
--- a/llvm/tools/llvm-reduce/deltas/ReduceInstructionsMIR.cpp
+++ b/llvm/tools/llvm-reduce/deltas/ReduceInstructionsMIR.cpp
@@ -45,6 +45,21 @@ static Register getPrevDefOfRCInMBB(MachineBasicBlock &MBB,
   return 0;
 }
 
+static bool shouldNotRemoveInstruction(const TargetInstrInfo &TII,
+                                       const MachineInstr &MI) {
+  if (MI.isTerminator())
+    return true;
+
+  // The MIR is almost certainly going to be invalid if frame instructions are
+  // deleted individually since they need to come in balanced pairs, so don't
+  // try to delete them.
+  if (MI.getOpcode() == TII.getCallFrameSetupOpcode() ||
+      MI.getOpcode() == TII.getCallFrameDestroyOpcode())
+    return true;
+
+  return false;
+}
+
 static void extractInstrFromFunction(Oracle &O, MachineFunction &MF) {
   MachineDominatorTree MDT;
   MDT.runOnMachineFunction(MF);
@@ -52,17 +67,17 @@ static void extractInstrFromFunction(Oracle &O, MachineFunction &MF) {
   auto MRI = &MF.getRegInfo();
   SetVector<MachineInstr *> ToDelete;
 
-  MachineInstr *TopMI = nullptr;
+  const TargetSubtargetInfo &STI = MF.getSubtarget();
+  const TargetInstrInfo *TII = STI.getInstrInfo();
+  MachineBasicBlock *EntryMBB = &*MF.begin();
+  MachineBasicBlock::iterator EntryInsPt =
+      EntryMBB->SkipPHIsLabelsAndDebug(EntryMBB->begin());
 
   // Mark MIs for deletion according to some criteria.
   for (auto &MBB : MF) {
     for (auto &MI : MBB) {
-      if (MI.isTerminator())
-        continue;
-      if (MBB.isEntryBlock() && !TopMI) {
-        TopMI = &MI;
+      if (shouldNotRemoveInstruction(*TII, MI))
         continue;
-      }
       if (!O.shouldKeep())
         ToDelete.insert(&MI);
     }
@@ -101,19 +116,15 @@ static void extractInstrFromFunction(Oracle &O, MachineFunction &MF) {
         }
       }
 
-      // If no dominating definition was found then add an implicit one to the
-      // first instruction in the entry block.
-
-      // FIXME: This should really insert IMPLICIT_DEF or G_IMPLICIT_DEF. We
-      // need to refine the reduction quality metric from number of serialized
-      // bytes to continue progressing if we're going to introduce new
-      // instructions.
-      if (!NewReg && TopMI) {
+      // If no dominating definition was found then add an implicit def to the
+      // top of the entry block.
+      if (!NewReg) {
         NewReg = MRI->cloneVirtualRegister(Reg);
-        TopMI->addOperand(MachineOperand::CreateReg(
-            NewReg, true /*IsDef*/, true /*IsImp*/, false /*IsKill*/,
-            MO.isDead(), MO.isUndef(), MO.isEarlyClobber(), MO.getSubReg(),
-            /*IsDebug*/ false, MO.isInternalRead()));
+        bool IsGeneric = MRI->getRegClassOrNull(Reg) == nullptr;
+        unsigned ImpDef = IsGeneric ? TargetOpcode::G_IMPLICIT_DEF
+                                    : TargetOpcode::IMPLICIT_DEF;
+        BuildMI(*EntryMBB, EntryInsPt, DebugLoc(), TII->get(ImpDef))
+          .addReg(NewReg, getRegState(MO), MO.getSubReg());
       }
 
       // Update all uses.