[X86] Improved X86::CMOV to Branch heuristic

[aaboud]

Summary

Resolved PR33954.
This patch contains two more constraint that aim to reduce the noise cases where we convert CMOV into branch for small gain, and spending more cycles due to overhead.

[RKSimon]

Is there any way that you can get test cases from PR33954?

[aaboud]

Added couple of tests that represents the bug in PR33954 and cover the change in the patch.
Notice that I needed to modify one of the previous tests.
I measured the performance manually on a small manually written main function, and noticed improvement with the new decision - as explained in the LIT test pr33954.ll.

[aaboud]

In D36081#825907, @RKSimon wrote:

Is there any way that you can get test cases from PR33954?

Hi Simon,
Are the below tests good enough?
Do you have other comments?

Thanks,
Amjad

[zvi]

lib/Target/X86/X86CmovConversion.cpp

409

Would this be a bit more readable?

if (diff[i] < GainCycleThreashold)
  return false;

bool WorthOptLoop = false;
if (Diff[1] == Diff[0])
    WorthOptLoop = Diff[0] * 8 >= LoopDepth[0].Depth;
else if (Diff[1] > Diff[0])
    WorthOptLoop =
        (Diff[1] - Diff[0]) * 2 >= (LoopDepth[1].Depth - LoopDepth[0].Depth) &&
        (Diff[1] * 8 >= LoopDepth[1].Depth);

test/CodeGen/X86/pr33954.ll

1 ↗

(On Diff #108946)

Since the -x86-cmov-converter is invoked explicitly, should the -x86-cmov-converter-threshold=4 flag be added too?

test/CodeGen/X86/x86-cmov-converter.ll

29 ↗

(On Diff #108946)

Maybe emphasize that in this case we bail out due to a low absolute gain in *cycles*, despite the *relative* gain being acceptable.

99 ↗

(On Diff #108946)

if (t *a> b)

[aaboud]

Addressed Zvi comments.

[aaboud]

Thanks Zvi for the comments.
Please see answers below.

test/CodeGen/X86/pr33954.ll

1 ↗

(On Diff #108946)

Actually, I want to guard the threshold, whoever change it, should revisit this test.
However, this test is not guarding against turning off the CMOV optimization., it is just verifying that the optimization itself works as expected.

test/CodeGen/X86/x86-cmov-converter.ll

99 ↗

(On Diff #108946)

Why is this important?

[oren_ben_simhon]

LGTM

lib/Target/X86/X86CmovConversion.cpp

 
 namespace {
 // This internal switch can be used to turn off the cmov/branch optimization.
 static cl::opt<bool>
     EnableCmovConverter("x86-cmov-converter",
                         cl::desc("Enable the X86 cmov-to-branch optimization."),
                         cl::init(true), cl::Hidden);
 
+static cl::opt<unsigned>
+    GainCycleThreshold("x86-cmov-converter-threshold",
+                       cl::desc("Minimum gain per loop (in cycles) threshold."),
+                       cl::init(4), cl::Hidden);
+
 /// Converts X86 cmov instructions into branches when profitable.
 class X86CmovConverterPass : public MachineFunctionPass {
 public:
   X86CmovConverterPass() : MachineFunctionPass(ID) {}
   ~X86CmovConverterPass() {}
 
   StringRef getPassName() const override { return "X86 cmov Conversion"; }
   bool runOnMachineFunction(MachineFunction &MF) override;
bool X86CmovConverterPass::checkForProfitableCmovCandidates(
   //           Thus, it is enough to check gain percent of 1st iteration -
   //           To be conservative, the optimized loop need to have a depth of
   //           12.5% cycles less than original loop, per iteration.
   //
   //   case 2: Diff[1] > Diff[0]
   //           Critical-path is iteration dependent - there is dependency of
   //           critical-path instructions on critical-path instructions of
   //           previous iteration.
-  //           Thus, it is required to check the gradient of the gain - the
-  //           change in Depth-Diff compared to the change in Loop-Depth between
-  //           1st and 2nd iterations.
+  //           Thus, check the gain percent of the 2nd iteration (similar to the
+  //           previous case), but it is also required to check the gradient of
+  //           the gain - the change in Depth-Diff compared to the change in
+  //           Loop-Depth between 1st and 2nd iterations.
   //           To be conservative, the gradient need to be at least 50%.
   //
+  //   In addition, In order not to optimize loops with very small gain, the
+  //   gain (in cycles) after 2nd iteration should not be less than a given
+  //   threshold. Thus, the check (Diff[1] >= GainCycleThreshold) must apply.
+  //
   // If loop is not worth optimizing, remove all CMOV-group-candidates.
   //===--------------------------------------------------------------------===//
   bool WorthOptLoop = false;
-  if (Diff[1] == Diff[0])
+  if (Diff[1] < GainCycleThreshold)
+    ; // Keep WorthOptLoop false
+  else if (Diff[1] == Diff[0])
     WorthOptLoop = Diff[0] * 8 >= LoopDepth[0].Depth;
   else if (Diff[1] > Diff[0])
     WorthOptLoop =
-        (Diff[1] - Diff[0]) * 2 >= (LoopDepth[1].Depth - LoopDepth[0].Depth);
+        (Diff[1] - Diff[0]) * 2 >= (LoopDepth[1].Depth - LoopDepth[0].Depth) &&
+        (Diff[1] * 8 >= LoopDepth[1].Depth);
 
   if (!WorthOptLoop)
     return false;
 
   ++NumOfLoopCandidate;
 
   //===--------------------------------------------------------------------===//
   // Step 3: Check for each CMOV-group-candidate if it worth to be optimized.