[x86] Refactor the CMOV conversion pass to be more flexible.

[chandlerc]

Summary

The primary thing that this accomplishes is to allow future re-use of
these routines in more contexts and clarify the behavior w.r.t. loops.
For example, if handling outer loops is desirable, doing so in
a inside-out order becomes straight forward because it walks the loop
nest itself (rather than walking the function's basic blocks) and
de-couples the CMOV rewriting from the loop structure as there isn't
actually anything loop-specific about this transformation.

This patch should be essentially a no-op. It potentially changes the
order in which we visit the inner loops, but otherwise should merely set
the stage for subsequent changes.

[RKSimon]

Adding people from D36711

[aaboud]

The code looks good, just few comments need to be fixed/added (see below)

lib/Target/X86/X86CmovConversion.cpp

100 ↗

(On Diff #111315)

need to fix the "param" comment.

109 ↗

(On Diff #111315)

need to fix the "param" comment.

169 ↗

(On Diff #111315)

You are calling "Loops.size()" every iteration intentionally, as you want to handle the just new added sub-loops.
Do not you think we should comment on that, so nobody will optimize this by saving the initial "size()" once and check against it later?

[chandlerc]

Improve comments based on code review.

[chandlerc]

Thanks for the review, updated!

lib/Target/X86/X86CmovConversion.cpp

169 ↗

(On Diff #111315)

Sure.

[aaboud]

LGTM.

llvm/trunk/lib/Target/X86/X86CmovConversion.cpp

private:
 
   /// List of consecutive CMOV instructions.
   typedef SmallVector<MachineInstr *, 2> CmovGroup;
   typedef SmallVector<CmovGroup, 2> CmovGroups;
 
   /// Collect all CMOV-group-candidates in \p CurrLoop and update \p
   /// CmovInstGroups accordingly.
   ///
-  /// \param CurrLoop Loop being processed.
+  /// \param Blocks List of blocks to process.
   /// \param CmovInstGroups List of consecutive CMOV instructions in CurrLoop.
   /// \returns true iff it found any CMOV-group-candidate.
-  bool collectCmovCandidates(MachineLoop *CurrLoop, CmovGroups &CmovInstGroups);
+  bool collectCmovCandidates(ArrayRef<MachineBasicBlock *> Blocks,
+                             CmovGroups &CmovInstGroups);
 
   /// Check if it is profitable to transform each CMOV-group-candidates into
   /// branch. Remove all groups that are not profitable from \p CmovInstGroups.
   ///
-  /// \param CurrLoop Loop being processed.
+  /// \param Blocks List of blocks to process.
   /// \param CmovInstGroups List of consecutive CMOV instructions in CurrLoop.
   /// \returns true iff any CMOV-group-candidate remain.
-  bool checkForProfitableCmovCandidates(MachineLoop *CurrLoop,
+  bool checkForProfitableCmovCandidates(ArrayRef<MachineBasicBlock *> Blocks,
                                         CmovGroups &CmovInstGroups);
 
   /// Convert the given list of consecutive CMOV instructions into a branch.
   ///
   /// \param Group Consecutive CMOV instructions to be converted into branch.
   void convertCmovInstsToBranches(SmallVectorImpl<MachineInstr *> &Group) const;
 };
 
bool X86CmovConverterPass::runOnMachineFunction(MachineFunction &MF) {
   //     For each profitable CMOV-group-candidate
   //       convertCmovInstsToBranches() {
   //           * Create FalseBB, SinkBB, Conditional branch to SinkBB.
   //           * Replace each CMOV instruction with a PHI instruction in SinkBB.
   //       }
   //
   // Note: For more details, see each function description.
   //===--------------------------------------------------------------------===//
-  for (MachineBasicBlock &MBB : MF) {
-    MachineLoop *CurrLoop = MLI.getLoopFor(&MBB);
 
+  // Build up the loops in pre-order.
+  SmallVector<MachineLoop *, 4> Loops(MLI.begin(), MLI.end());
+  // Note that we need to check size on each iteration as we accumulate child
+  // loops.
+  for (int i = 0; i < (int)Loops.size(); ++i)
+    for (MachineLoop *Child : Loops[i]->getSubLoops())
+      Loops.push_back(Child);
+
+  for (MachineLoop *CurrLoop : Loops) {
     // Optimize only inner most loops.
-    if (!CurrLoop || CurrLoop->getHeader() != &MBB ||
-        !CurrLoop->getSubLoops().empty())
+    if (!CurrLoop->getSubLoops().empty())
       continue;
 
     // List of consecutive CMOV instructions to be processed.
     CmovGroups CmovInstGroups;
 
-    if (!collectCmovCandidates(CurrLoop, CmovInstGroups))
+    if (!collectCmovCandidates(CurrLoop->getBlocks(), CmovInstGroups))
       continue;
 
-    if (!checkForProfitableCmovCandidates(CurrLoop, CmovInstGroups))
+    if (!checkForProfitableCmovCandidates(CurrLoop->getBlocks(),
+                                          CmovInstGroups))
       continue;
 
     Changed = true;
     for (auto &Group : CmovInstGroups)
       convertCmovInstsToBranches(Group);
   }
   return Changed;
 }
 
-bool X86CmovConverterPass::collectCmovCandidates(MachineLoop *CurrLoop,
-                                                 CmovGroups &CmovInstGroups) {
+bool X86CmovConverterPass::collectCmovCandidates(
+    ArrayRef<MachineBasicBlock *> Blocks, CmovGroups &CmovInstGroups) {
   //===--------------------------------------------------------------------===//
   // Collect all CMOV-group-candidates and add them into CmovInstGroups.
   //
   // CMOV-group:
   //   CMOV instructions, in same MBB, that uses same EFLAGS def instruction.
   //
   // CMOV-group-candidate:
   //   CMOV-group where all the CMOV instructions are
   //     1. consecutive.
   //     2. have same condition code or opposite one.
   //     3. have only operand registers (X86::CMOVrr).
   //===--------------------------------------------------------------------===//
   // List of possible improvement (TODO's):
   // --------------------------------------
   //   TODO: Add support for X86::CMOVrm instructions.
   //   TODO: Add support for X86::SETcc instructions.
   //   TODO: Add support for CMOV-groups with non consecutive CMOV instructions.
   //===--------------------------------------------------------------------===//
 
   // Current processed CMOV-Group.
   CmovGroup Group;
-  for (auto *MBB : CurrLoop->getBlocks()) {
+  for (auto *MBB : Blocks) {
     Group.clear();
     // Condition code of first CMOV instruction current processed range and its
     // opposite condition code.
     X86::CondCode FirstCC, FirstOppCC;
     // Indicator of a non CMOVrr instruction in the current processed range.
     bool FoundNonCMOVInst = false;
     // Indicator for current processed CMOV-group if it should be skipped.
     bool SkipGroup = false;
static unsigned getDepthOfOptCmov(unsigned TrueOpDepth, unsigned FalseOpDepth) {
   // With no info about branch weight, we assume 50% for each value operand.
   // Thus, depth of optimized CMOV instruction is the rounded up average of
   // its True-Operand-Value-Depth and False-Operand-Value-Depth.
   //===--------------------------------------------------------------------===//
   return (TrueOpDepth + FalseOpDepth + 1) / 2;
 }
 
 bool X86CmovConverterPass::checkForProfitableCmovCandidates(
-    MachineLoop *CurrLoop, CmovGroups &CmovInstGroups) {
+    ArrayRef<MachineBasicBlock *> Blocks, CmovGroups &CmovInstGroups) {
   struct DepthInfo {
     /// Depth of original loop.
     unsigned Depth;
     /// Depth of optimized loop.
     unsigned OptDepth;
   };
   /// Number of loop iterations to calculate depth for ?!
   static const unsigned LoopIterations = 2;
bool X86CmovConverterPass::checkForProfitableCmovCandidates(
   //   Loop-Depth calculated for first `i` iterations.
   //   Note: it is enough to calculate depth for up to two iterations.
   //
   // Depth-Diff[i]:
   //   Number of cycles saved in first 'i` iterations by optimizing the loop.
   //===--------------------------------------------------------------------===//
   for (unsigned I = 0; I < LoopIterations; ++I) {
     DepthInfo &MaxDepth = LoopDepth[I];
-    for (auto *MBB : CurrLoop->getBlocks()) {
+    for (auto *MBB : Blocks) {
       // Clear physical registers Def map.
       RegDefMaps[PhyRegType].clear();
       for (MachineInstr &MI : *MBB) {
         unsigned MIDepth = 0;
         unsigned MIDepthOpt = 0;
         bool IsCMOV = CmovInstructions.count(&MI);
         for (auto &MO : MI.uses()) {
           // Checks for "isUse()" as "uses()" returns also implicit definitions.