[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

need to fix the "param" comment.

109

need to fix the "param" comment.

169

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

Sure.

[aaboud]

LGTM.

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.