[Peephole-Opt][X86] Enhance peephole opt to see through SUBREG_TO_REG (following AND) and eliminates redundant TEST instruction.

[mingmingl]

Summary

The goal of this patch is to optimize away the test instruction in the following pattern

%reg = and ... EFLAGS set
... EFLAGS not changed.
%extended_reg = subreg_to_reg 0, %reg, %subreg.sub_index. EFLAGS not changed
testrr %extended_reg, %extended_reg, implicit-def $eflags. This could be optimized away.

Before this patch, the optimization wasn't carried out, since extended_reg is defined by SUBREG_TO_REG, which is not handled by isDefConvertible in X86InstrInfo.cpp.

The implementation optimize away the test if the bits used by TEST readers are already set by AND.

[davidxl]

I suspect there is something else going on.

The following case works fine without the patch.

define dso_local noundef i64 @_Z3fooPlll(ptr nocapture noundef %0, i64 noundef %1, i64 noundef %2) local_unnamed_addr #0 {

%4 = load i64, ptr %0, align 8
%5 = and i64 %4, 3
%6 = icmp eq i64 %5, 0
%7 = select i1 %6, i64 %1, i64 %2
store i64 %7, ptr %0, align 8
ret i64 %5

}

However a simple change below to replace the operand %2 in the select with %5 (output of and operation), then it stops working.

define dso_local noundef i64 @_Z3fooPlll(ptr nocapture noundef %0, i64 noundef %1, i64 noundef %2) local_unnamed_addr #0 {

%4 = load i64, ptr %0, align 8
%5 = and i64 %4, 3
%6 = icmp eq i64 %5, 0
%7 = select i1 %6, i64 %1, i64 %5
store i64 %7, ptr %0, align 8
ret i64 %5

}

Can you investigate the difference? The behavior difference on ARM is also worth comparing with.

[craig.topper]

llvm/test/CodeGen/X86/peephole-test-after-add.mir

30

Are the other basic blocks important?

108

Please use update_mir_test_checks.py

[craig.topper]

llvm/lib/Target/X86/X86InstrInfo.cpp

986

SUBREG_TO_REG is only used for i32->i64 conversions. So the only TEST it could ever be is TEST64rr.

997

This is making a copy of the a MachineOperand. Can you use a const reference?

999

It's not necessary.

1010

This is making a copy of the MachineOperand

1015

Drop curly braces

1020

Variable names should be capitalized

1058

Another copy

4343

AND/OR/XOR set the OF flag to 0.

4344

If you look through SUBREG_TO_REG then the width changed. The TEST64rr would have calculated the sign flag from bit 63(which is 0 due to the SUBREG_TO_REG), but the AND32 calculated it from bit 31 which is unknown.

[craig.topper]

In D124118#3463205, @davidxl wrote:

I suspect there is something else going on.

The following case works fine without the patch.

define dso_local noundef i64 @_Z3fooPlll(ptr nocapture noundef %0, i64 noundef %1, i64 noundef %2) local_unnamed_addr #0 {

%4 = load i64, ptr %0, align 8
%5 = and i64 %4, 3
%6 = icmp eq i64 %5, 0
%7 = select i1 %6, i64 %1, i64 %2
store i64 %7, ptr %0, align 8
ret i64 %5

}

However a simple change below to replace the operand %2 in the select with %5 (output of and operation), then it stops working.

define dso_local noundef i64 @_Z3fooPlll(ptr nocapture noundef %0, i64 noundef %1, i64 noundef %2) local_unnamed_addr #0 {

%4 = load i64, ptr %0, align 8
%5 = and i64 %4, 3
%6 = icmp eq i64 %5, 0
%7 = select i1 %6, i64 %1, i64 %5
store i64 %7, ptr %0, align 8
ret i64 %5

}

Can you investigate the difference? The behavior difference on ARM is also worth comparing with.

There's a peephole in X86DAGToDAGISel::Select and PostProcessISelDAG that both fail if the AND has users other than the TEST.

[davidxl]

In D124118#3463462, @craig.topper wrote:

In D124118#3463205, @davidxl wrote:

I suspect there is something else going on.

The following case works fine without the patch.

define dso_local noundef i64 @_Z3fooPlll(ptr nocapture noundef %0, i64 noundef %1, i64 noundef %2) local_unnamed_addr #0 {

%4 = load i64, ptr %0, align 8
%5 = and i64 %4, 3
%6 = icmp eq i64 %5, 0
%7 = select i1 %6, i64 %1, i64 %2
store i64 %7, ptr %0, align 8
ret i64 %5

}

However a simple change below to replace the operand %2 in the select with %5 (output of and operation), then it stops working.

define dso_local noundef i64 @_Z3fooPlll(ptr nocapture noundef %0, i64 noundef %1, i64 noundef %2) local_unnamed_addr #0 {

%4 = load i64, ptr %0, align 8
%5 = and i64 %4, 3
%6 = icmp eq i64 %5, 0
%7 = select i1 %6, i64 %1, i64 %5
store i64 %7, ptr %0, align 8
ret i64 %5

}

Can you investigate the difference? The behavior difference on ARM is also worth comparing with.

There's a peephole in X86DAGToDAGISel::Select and PostProcessISelDAG that both fail if the AND has users other than the TEST.

thanks. That explains it.

For this case, the subreg_to_reg is indeed the reason blocking the peephole-opt from cleaning it up (as can be seen in the case if the AND operand is changed to 0x1ffffffff where subreg_to_reg is not generated)

llvm/lib/Target/X86/X86InstrInfo.cpp

1043

Is there need to handle OR and XOR here? It seems we won't see code patterns with OR followed by subreg_to_reg.

[mingmingl]

Resolve the comments.

[mingmingl]

llvm/lib/Target/X86/X86InstrInfo.cpp

986

It looks like when SUBREG_TO_REG is used in SSE, the result type is not 64 bit [1]. So revised this helper function to

1. only handle the case when CmpInstr is TEST64rr and SUBREG_TO_REG is using sub_32bit as subregister index
2. returns false early for the rest of cases.

[1] https://github.com/llvm/llvm-project/blob/334522ca58aa6d6703405e479de8f5bf310ddbe2/llvm/lib/Target/X86/X86InstrSSE.td#L289

1043

(After reading this, it occurred to me existing definitions in td files in llvm/lib/Target/X86 are useful to find out how operands of SUBREG_TO-REG are generated).

Revised to handle AND only, considering

1. SUBREG_TO_REG almost always use 0 as immediate number.
2. it's hard to know the SF bit for OR, or XOR given 0 is the immediate number.

p.s. It seems [1] is where pattern (add64 -> and32 + subreg_to_reg) is given a higher priority, and I assume removing this from td and looking at the result could verify.

[1] https://github.com/llvm/llvm-project/blob/334522ca58aa6d6703405e479de8f5bf310ddbe2/llvm/lib/Target/X86/X86InstrCompiler.td#L1619

4343

ah.. thanks for the catch! corrected it.

4344

thanks for the catch!

Fix it by adding helper function isSFZero, and only optimize away the TEST64rr when SF is known to be zero.

llvm/test/CodeGen/X86/peephole-test-after-add.mir

30

Merge two IR functions into one file and by using the example from David.

[mingmingl]

In D124118#3463778, @davidxl wrote:

In D124118#3463462, @craig.topper wrote:

In D124118#3463205, @davidxl wrote:

I suspect there is something else going on.

The following case works fine without the patch.

define dso_local noundef i64 @_Z3fooPlll(ptr nocapture noundef %0, i64 noundef %1, i64 noundef %2) local_unnamed_addr #0 {

%4 = load i64, ptr %0, align 8
%5 = and i64 %4, 3
%6 = icmp eq i64 %5, 0
%7 = select i1 %6, i64 %1, i64 %2
store i64 %7, ptr %0, align 8
ret i64 %5

}

However a simple change below to replace the operand %2 in the select with %5 (output of and operation), then it stops working.

define dso_local noundef i64 @_Z3fooPlll(ptr nocapture noundef %0, i64 noundef %1, i64 noundef %2) local_unnamed_addr #0 {

%4 = load i64, ptr %0, align 8
%5 = and i64 %4, 3
%6 = icmp eq i64 %5, 0
%7 = select i1 %6, i64 %1, i64 %5
store i64 %7, ptr %0, align 8
ret i64 %5

}

Can you investigate the difference? The behavior difference on ARM is also worth comparing with.

There's a peephole in X86DAGToDAGISel::Select and PostProcessISelDAG that both fail if the AND has users other than the TEST.

thanks. That explains it.

For this case, the subreg_to_reg is indeed the reason blocking the peephole-opt from cleaning it up (as can be seen in the case if the AND operand is changed to 0x1ffffffff where subreg_to_reg is not generated)

Besides peephole-opt in X86ISelDAGToDAG that looks for (X86cmp (and $op, $imm), 0)[1], another significance is in legalization

Using llc -O3 -debug -debug-only=isel,x86-isel,selectiondag,legalizedag,peephole-opt,x86-instr-info <file.ll> gives the following log respectively

• https://gist.github.com/minglotus-6/39fb318886ae8deaf34a6f2f0d03fceb for the good case (TEST64rr erased)
• https://gist.github.com/minglotus-6/fcd07bc00d9bc362b7bd5675ba131740 for the bad case (TEST64rr kept)

To elaborate,

• for the good case
  • https://gist.github.com/minglotus-6/39fb318886ae8deaf34a6f2f0d03fceb#file-first-log-L96-L104 show legalization doesn't generate CMP.
• for the bad case
  • https://gist.github.com/minglotus-6/fcd07bc00d9bc362b7bd5675ba131740#file-second-log-L93-L101 shows legalization generates CMP

Tracking the implementation, X86TargetLowering::emitFlagsForSetcc has different paths

• when AND has one use (around line 24366), no cmp is emit
• for the bad case, will call EmitCmp around line 24426

(X86ISelLowering.cpp is too large to display in Github, or generate a permanent link, so add the line number)

[1] https://github.com/llvm/llvm-project/blob/360d44e86defea94fb5608765fbdbfdb2a36f4c6/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp#L5608

[mingmingl]

resolve a build failure due to conflicting function name (same return type, different argument list)

[craig.topper]

llvm/lib/Target/X86/X86InstrInfo.cpp

980

iz->is

[mingmingl]

Resolve the comment.

[mingmingl]

resolve comments

[mingmingl]

Remove new lines added by editor.

[mingmingl]

Mix two local branches.

Corrected it.

[mingmingl]

a gentle ping!~

[craig.topper]

llvm/lib/Target/X86/X86InstrInfo.cpp

970

I don't know if this is necessary. If the SUBREG_TO_REG was used, the sign bit of the full 64 bit value was provably zero during SelectionDAG. I hope any branch, setcc, cmov would have been folded away based on it.

Can't we just set NoSignFlag=true?

[mingmingl]

thanks for reviews!

llvm/lib/Target/X86/X86InstrInfo.cpp

970

isSFZero is used to tell the difference of following two scenarios, and (if I read correctly) NoSignFlag (as well as ClearsOverflowFlag) indicate whether the EFLAG bit is set (as opposed to the value of bit), so for AND operation, we want to set NoSignFlag to false.

AND32ri8 reg, 0x9  # signed bit is 1, so after sign extension, the SF bit could be 1 or 0 depending on reg value
SUBREG_TO_REG 0, extended_reg, reg , sub_32bit
TEST64rr extended_reg, extended_reg,  # SF bit is 0 since higher 32 bit of extended_reg is 0

AND32ri8 reg, 0x7  # signed bit is 0, so after sign extension, the SF bit is known to be 0
SUBREG_TO_REG 0, extended_reg, reg , sub_32bit
TEST64rr extended_reg, extended_reg,  # SF bit is 0 since higher 32 bit of extended_reg is 0

We want to optimize away test for 2) but keep test for 1).

Let me know if I miss anything!

[craig.topper]

llvm/lib/Target/X86/X86InstrInfo.cpp

970

If the instructions that use the flags from the TEST don't look at the SF flag then it doesn't matter. Setting NoSignFlag = true will disable the optimization if the SF flag is used. Your motivating test case doesn't use the sign flag so this should be sufficient.

[mingmingl]

Set NoSignFlag to false (to poison SF bit for readers), and get rid of isSFZero helper function.

[mingmingl]

llvm/lib/Target/X86/X86InstrInfo.cpp

970

I see your point now. Updated. PTAL.

[mingmingl]

Correct the auto-format a little bit

Before

// The reason to poison SF bit is that SF bit value could be different
// in the `AND` and `TEST` operation
//
// dest_reg = AND32ri8 src_reg, #imm  # signed bit is not known without
// peeking at #imm. extended_dest_reg = SUBREG_TO_REG 0, dest_reg, sub_32bit

After

// The reason to poison SF bit is that SF bit value could be different
// in the `AND` and `TEST` operation; signed bit is not known for `AND`
// without peeking at #imm, and is known to be 0 as a result of
// `TEST64rr`.
// dest_reg = AND32ri8 src_reg, #imm
// extended_dest_reg = SUBREG_TO_REG 0, dest_reg, sub_32bit
// TEST64rr extended_dest_reg, extended_dest_reg,

[mingmingl]

A gentle ping!~

[skan]

As to the desciption, maybe it should not be called a heuristic optimization?

llvm/lib/Target/X86/X86InstrInfo.cpp

970

Remove inline?

988–993

Could we remove these assert? I think they're not useful.

1004

Useless assert

1026

And32->and32

1027–1031

The format of comments here seems weird?

1032

And32->AND32

1048–1050

"The optimizatin will be disasbled"
I think this is not covered by your test yet?

1054

Why don't we peek at imm here? It's possible to set NoSignFlag to false.

1056–1058

Could you uniform the instruction name in your comments? You use SUBREG_TO_REG here while subreg_to_reg somewhere.

[skan]

llvm/test/CodeGen/X86/peephole-test-after-add.mir

3

Minor suggestion -o - %s -> < %s

[skan]

llvm/lib/Target/X86/X86InstrInfo.cpp

1054

Never mind. I missed craig's comments

[skan]

llvm/test/CodeGen/X86/peephole-test-after-add.mir

3

Never mind. I didn't realize that "< %s" does not work for "--run-pass".

[craig.topper]

llvm/test/CodeGen/X86/peephole-test-after-add.mir

3

I think it doesn't work for .mir input because llc uses the extension of the file name is used to determine file type. If you use re-direction llc can't see the extension so just assumes .ll.

[mingmingl]

Address the style comments, and add a regression test to gate the behavior that TEST is retained if SF bit is read.

llvm/lib/Target/X86/X86InstrInfo.cpp

970

Removed inline.

For my understanding, is it because of lengthy function body and long argument list that inline hint doesn't make much sense here?

988–993

Could we remove these assert? I think they're not useful.

Removed the second assert(CmpValDefInstr.getNumOperands() == 4).

I wonder if the 1st assert (assert(MRI->getVRegDef(CmpInstr.getOperand(0).getReg()) == &CmpValDefInstr)) helps in the sense that

1. the information asserted (def-use between this two instructions) are not explicitly mentioned in any comment
2. this information is important for the correctness

Nevertheless kept the 1st assert and added comment. Let me know what I miss.

1004

Since the function body getImm() or getReg() has asserts, it makes sense to just rely on that to give enough debugging information.

So removed three asserts (on MO3, MO2, MO1)

1027–1031

thanks for the catch! Fixed it.

1048–1050

it makes sense to add a test.

Added test_not_erased_when_sf_used in llvm/test/CodeGen/X86/peephole-test-after-add.mir, to cover the behavior that TEST64rr is retained if SF bit is used.

1054

Yeah I was initially thinking of peeking at imm, and later (upon Craig's comment) realized there is another way to do this.

1056–1058

Unified the instruction name in this patch.

p.s. I realized this sequence of instructions should be better placed around line 1024, so merge it with the sequence of instructions right after if (X86::isAND(VregDefInstr->getOpcode())) {

llvm/test/CodeGen/X86/peephole-test-after-add.mir

3

thanks for the discussion! I'll keep it the current way and reply first, before getting a better idea of the difference (between -o - %s and %s in this command) myself.

[mingmingl]

In D124118#3498831, @skan wrote:

As to the desciption, maybe it should not be called a heuristic optimization?

modified summary with diff

1. removed heurstic
2. optimize test away if EFLAG bits used as a result of test are already set by AND.

[mingmingl]

[Only two minor style changes]
Rename the .ll file in llvm/test/CodeGen/X86/peephole-test-after-add.mir, and remove braces on simple single statement bodies of if-else statements.

[skan]

llvm/lib/Target/X86/X86InstrInfo.cpp

970

Yes. In fact, I think it's useless to add inline to functions w/ internal linkage for non-peformance critical code. Compiler can decide whether it should be inlined.

995

What does the "Caller guranteed" mean here? Does it say that TEST64rr is the user of SUBREG_TO_REG?

1031

const MachineInstr &

[mingmingl]

Replied the comments.

Besides, in findRedundantFlagInstr, change from

  const MachineOperand& MO1 = CmpValDefInstr.getOperand(1);
// As seen in X86 td files, MO1 is typically
  // 0.
  if (.MO1.getImm() != 0)
    return false;

to

// As seen in X86 td files, CmpValDefInstr.getOperand(1).getImm() is typically
  // 0.
  if (CmpValDefInstr.getOperand(1).getImm() != 0)
    return false;

Same for MO2 and MO3.

[skan]

LGTM!

[mingmingl]

(I forgot to click "reply" to send out the inline comments... but going to do it now)

Thanks for all reviews and inputs!

Going to hold it for a while since other reviewers might have comments as well.

llvm/lib/Target/X86/X86InstrInfo.cpp

970

Compiler can decide whether it should be inlined.

This is true.

995

Does it say that TEST64rr is the user of SUBREG_TO_REG?

Yes this is correct. I think this assertion might prevent inadvertent misuse of findRedundantFlagInstr, yet I agree it's probably premature at this point.

Let me know if it's more idiomatic to just remove this assertion.

[davidxl]

llvm/test/CodeGen/X86/peephole-test-after-add.mir

24

The and instruction clears SF and upper bits of the value which means the test instruction later will also produce SF == 0. In other words, in this case, not only the test instruction, but also the CMOVErr can be optimized into a copy.

(this can be looked at in a follow up patch if it is the case).

[craig.topper]

llvm/test/CodeGen/X86/peephole-test-after-add.mir

24

Do we not figure that out in SelectionDAG?

[mingmingl]

llvm/test/CodeGen/X86/peephole-test-after-add.mir

24

The and instruction clears SF and upper bits of the value which means the test instruction later will also produce SF == 0. In other words, in this case, not only the test instruction, but also the CMOVErr can be optimized into a copy.

(this can be looked at in a follow up patch if it is the case).

Added a FIXME around line 1052 (inside findRedundantFlagInstr) to follow up on this.

Do we not figure that out in SelectionDAG?

Not sure if we could figure it out in SelectionDAG step. There is TargetInstrInfo::optimizeSelect virtual method for peephole-opt, and an implementation (ARMBaseInstrInfo::optimizeSelect) [1]. Will look into which pass to put this optimization later.

[1] https://github.com/llvm/llvm-project/blob/0353c2c996c5863463c356de97c9852f9330ed11/llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp#L2321

[mingmingl]

Add FIXME for a follow-up optimization.

[craig.topper]

llvm/test/CodeGen/X86/peephole-test-after-add.mir

24

I thought DAGCombiner for ISD::SETCC should be able to figure out that an AND with 3 guarantees the sign bit is 0, but it appears it does not. InstCombine does optimize it though.

[mingmingl]

llvm/test/CodeGen/X86/peephole-test-after-add.mir

24

Got it. DAGCombiner sounds a right place to look at a sequence of instructions and optimize.

[mingmingl]

Reopen so as to re-commit (upon request https://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20220509/1036289.html)

[mingmingl]

Reapply with a descriptive commit message.

[craig.topper]

Please put [X86] in the title.

[dim]

FYI https://github.com/llvm/llvm-project/issues/56103

llvm/lib/Target/X86/X86InstrInfo.cpp

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/Sequence.h"
 #include "llvm/CodeGen/LiveIntervals.h"
 #include "llvm/CodeGen/LivePhysRegs.h"
 #include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/MachineConstantPool.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
+#include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/StackMaps.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
+#include "llvm/IR/InstrTypes.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCExpr.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetOptions.h"
inline static bool isTruncatedShiftCountForLEA(unsigned ShAmt) {
   // Left shift instructions can be transformed into load-effective-address
   // instructions if we can encode them appropriately.
   // A LEA instruction utilizes a SIB byte to encode its scale factor.
   // The SIB.scale field is two bits wide which means that we can encode any
   // shift amount less than 4.
   return ShAmt < 4 && ShAmt > 0;
 }
 
+static bool findRedundantFlagInstr(MachineInstr &CmpInstr,
+                                   MachineInstr &CmpValDefInstr,
+                                   const MachineRegisterInfo *MRI,
+                                   MachineInstr **AndInstr,
+                                   const TargetRegisterInfo *TRI,
+                                   bool &NoSignFlag, bool &ClearsOverflowFlag) {
+  if (CmpValDefInstr.getOpcode() != X86::SUBREG_TO_REG)
+    return false;
+
+  if (CmpInstr.getOpcode() != X86::TEST64rr)
+    return false;
+
+  // CmpInstr is a TEST64rr instruction, and `X86InstrInfo::analyzeCompare`
+  // guarantees that it's analyzable only if two registers are identical.
+  assert(
+      (CmpInstr.getOperand(0).getReg() == CmpInstr.getOperand(1).getReg()) &&
+      "CmpInstr is an analyzable TEST64rr, and `X86InstrInfo::analyzeCompare` "
+      "requires two reg operands are the same.");
+
+  // Caller (`X86InstrInfo::optimizeCompareInstr`) guarantees that
+  // `CmpValDefInstr` defines the value that's used by `CmpInstr`; in this case
+  // if `CmpValDefInstr` sets the EFLAGS, it is likely that `CmpInstr` is
+  // redundant.
+  assert(
+      (MRI->getVRegDef(CmpInstr.getOperand(0).getReg()) == &CmpValDefInstr) &&
+      "Caller guarantees that TEST64rr is a user of SUBREG_TO_REG.");
+
+  // As seen in X86 td files, CmpValDefInstr.getOperand(1).getImm() is typically
+  // 0.
+  if (CmpValDefInstr.getOperand(1).getImm() != 0)
+    return false;
+
+  // As seen in X86 td files, CmpValDefInstr.getOperand(3) is typically
+  // sub_32bit or sub_xmm.
+  if (CmpValDefInstr.getOperand(3).getImm() != X86::sub_32bit)
+    return false;
+
+  MachineInstr *VregDefInstr =
+      MRI->getVRegDef(CmpValDefInstr.getOperand(2).getReg());
+
+  assert(VregDefInstr && "Must have a definition (SSA)");
+
+  // Requires `CmpValDefInstr` and `VregDefInstr` are from the same MBB
+  // to simplify the subsequent analysis.
+  //
+  // FIXME: If `VregDefInstr->getParent()` is the only predecessor of
+  // `CmpValDefInstr.getParent()`, this could be handled.
+  if (VregDefInstr->getParent() != CmpValDefInstr.getParent())
+    return false;
+
+  if (X86::isAND(VregDefInstr->getOpcode())) {
+    // Get a sequence of instructions like
+    //   %reg = and* ...                    // Set EFLAGS
+    //   ...                                // EFLAGS not changed
+    //   %extended_reg = subreg_to_reg 0, %reg, %subreg.sub_32bit
+    //   test64rr %extended_reg, %extended_reg, implicit-def $eflags
+    //
+    // If subsequent readers use a subset of bits that don't change
+    // after `and*` instructions, it's likely that the test64rr could
+    // be optimized away.
+    for (const MachineInstr &Instr :
+         make_range(std::next(MachineBasicBlock::iterator(VregDefInstr)),
+                    MachineBasicBlock::iterator(CmpValDefInstr))) {
+      // There are instructions between 'VregDefInstr' and
+      // 'CmpValDefInstr' that modifies EFLAGS.
+      if (Instr.modifiesRegister(X86::EFLAGS, TRI))
+        return false;
+    }
+
+    *AndInstr = VregDefInstr;
+
+    // AND instruction will essentially update SF and clear OF, so
+    // NoSignFlag should be false in the sense that SF is modified by `AND`.
+    //
+    // However, the implementation artifically sets `NoSignFlag` to true
+    // to poison the SF bit; that is to say, if SF is looked at later, the
+    // optimization (to erase TEST64rr) will be disabled.
+    //
+    // The reason to poison SF bit is that SF bit value could be different
+    // in the `AND` and `TEST` operation; signed bit is not known for `AND`,
+    // and is known to be 0 as a result of `TEST64rr`.
+    //
+    // FIXME: As opposed to poisoning the SF bit direclty, consider peeking into
+    // the AND instruction and using the static information to guide peephole optimization if possible.
+    // For example, it's possible to fold a conditional move into a copy
+    // if the relevant EFLAG bits could be deduced from an immediate operand of and operation.
+    // 
+    NoSignFlag = true;
+    // ClearsOverflowFlag is true for AND operation (no surprise).
+    ClearsOverflowFlag = true;
+    return true;
+  }
+  return false;
+}
+
 bool X86InstrInfo::classifyLEAReg(MachineInstr &MI, const MachineOperand &Src,
                                   unsigned Opc, bool AllowSP, Register &NewSrc,
                                   bool &isKill, MachineOperand &ImplicitOp,
                                   LiveVariables *LV, LiveIntervals *LIS) const {
   MachineFunction &MF = *MI.getParent()->getParent();
   const TargetRegisterClass *RC;
   if (AllowSP) {
     RC = Opc != X86::LEA32r ? &X86::GR64RegClass : &X86::GR32RegClass;
for (MachineInstr &Inst : make_range(From, MBB->rend())) {
       //     ...                // EFLAGS not changed
       //     testl %eax, %eax   // <-- can be removed
       if (&Inst == SrcRegDef) {
         if (IsCmpZero &&
             isDefConvertible(Inst, NoSignFlag, ClearsOverflowFlag)) {
           MI = &Inst;
           break;
         }
+
+        // Look back for the following pattern, in which case the test64rr
+        // instruction could be erased.
+        //
+        // Example:
+        //  %reg = and32ri %in_reg, 5
+        //  ...                         // EFLAGS not changed.
+        //  %src_reg = subreg_to_reg 0, %reg, %subreg.sub_index
+        //  test64rr %src_reg, %src_reg, implicit-def $eflags
+        MachineInstr *AndInstr = nullptr;
+        if (IsCmpZero &&
+            findRedundantFlagInstr(CmpInstr, Inst, MRI, &AndInstr, TRI,
+                                   NoSignFlag, ClearsOverflowFlag)) {
+          assert(AndInstr != nullptr && X86::isAND(AndInstr->getOpcode()));
+          MI = AndInstr;
+          break;
+        }
         // Cannot find other candidates before definition of SrcReg.
         return false;
       }
 
       if (Inst.modifiesRegister(X86::EFLAGS, TRI)) {
         // Try to use EFLAGS produced by an instruction reading %SrcReg.
         // Example:
         //      %eax = ...
         //      ...

llvm/test/CodeGen/X86/peephole-test-after-add.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -o - %s -mtriple=x86_64-unknown-linux-gnu --run-pass=peephole-opt | FileCheck %s
+
+# Test that TEST64rr is erased in `test_erased`, and kept in `test_not_erased_when_sf_used`
+# and `test_not_erased_when_eflags_change`.
+
+--- |
+  ; ModuleID = 'tmp.ll'
+  source_filename = "tmp.ll"
+  target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+
+  define i64 @test_erased(ptr %0, i64 %1, i64 %2) {
+    %4 = load i64, ptr %0, align 8
+    %5 = and i64 %4, 3
+    %6 = icmp eq i64 %5, 0
+    %7 = select i1 %6, i64 %1, i64 %5
+    store i64 %7, ptr %0, align 8
+    ret i64 %5
+  }
+
+  define i64 @test_not_erased_when_sf_used(ptr %0, i64 %1, i64 %2, i64 %3) {
+    %5 = load i64, ptr %0, align 8
+    %6 = and i64 %5, 3
+    %7 = icmp slt i64 %6, 0
+    %8 = select i1 %7, i64 %1, i64 %6
+    store i64 %8, ptr %0, align 8
+    ret i64 %5
+  }
+
+  define void @test_not_erased_when_eflags_change(ptr %0, i64 %1, i64 %2, i64 %3, ptr %4) {
+    %6 = load i64, ptr %0, align 8
+    %7 = and i64 %6, 3
+    %8 = xor i64 %3, 5
+    %9 = icmp eq i64 %7, 0
+    %10 = select i1 %9, i64 %1, i64 %7
+    store i64 %10, ptr %0, align 8
+    store i64 %8, ptr %4, align 8
+    ret void
+  }
+
+...
+---
+name:            test_erased
+alignment:       16
+tracksDebugUserValues: false
+registers:
+  - { id: 0, class: gr64, preferred-register: '' }
+  - { id: 1, class: gr64, preferred-register: '' }
+  - { id: 2, class: gr64, preferred-register: '' }
+  - { id: 3, class: gr64, preferred-register: '' }
+  - { id: 4, class: gr32, preferred-register: '' }
+  - { id: 5, class: gr32, preferred-register: '' }
+  - { id: 6, class: gr64, preferred-register: '' }
+  - { id: 7, class: gr64, preferred-register: '' }
+liveins:
+  - { reg: '$rdi', virtual-reg: '%0' }
+  - { reg: '$rsi', virtual-reg: '%1' }
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0 (%ir-block.3):
+    liveins: $rdi, $rsi
+
+    ; CHECK-LABEL: name: test_erased
+    ; CHECK: [[COPY:%[0-9]+]]:gr64 = COPY $rsi
+    ; CHECK-NEXT: [[COPY1:%[0-9]+]]:gr64 = COPY $rdi
+    ; CHECK-NEXT: [[MOV64rm:%[0-9]+]]:gr64 = MOV64rm [[COPY1]], 1, $noreg, 0, $noreg :: (load (s64) from %ir.0)
+    ; CHECK-NEXT: [[COPY2:%[0-9]+]]:gr32 = COPY [[MOV64rm]].sub_32bit
+    ; CHECK-NEXT: [[AND32ri8_:%[0-9]+]]:gr32 = AND32ri8 [[COPY2]], 3, implicit-def $eflags
+    ; CHECK-NEXT: [[SUBREG_TO_REG:%[0-9]+]]:gr64 = SUBREG_TO_REG 0, killed [[AND32ri8_]], %subreg.sub_32bit
+    ; CHECK-NEXT: [[CMOV64rr:%[0-9]+]]:gr64 = CMOV64rr [[SUBREG_TO_REG]], [[COPY]], 4, implicit $eflags
+    ; CHECK-NEXT: MOV64mr [[COPY1]], 1, $noreg, 0, $noreg, killed [[CMOV64rr]] :: (store (s64) into %ir.0)
+    ; CHECK-NEXT: $rax = COPY [[SUBREG_TO_REG]]
+    ; CHECK-NEXT: RET 0, $rax
+    %1:gr64 = COPY $rsi
+    %0:gr64 = COPY $rdi
+    %3:gr64 = MOV64rm %0, 1, $noreg, 0, $noreg :: (load (s64) from %ir.0)
+    %4:gr32 = COPY %3.sub_32bit
+    %5:gr32 = AND32ri8 %4, 3, implicit-def dead $eflags
+    %6:gr64 = SUBREG_TO_REG 0, killed %5, %subreg.sub_32bit
+    TEST64rr %6, %6, implicit-def $eflags
+    %7:gr64 = CMOV64rr %6, %1, 4, implicit $eflags
+    MOV64mr %0, 1, $noreg, 0, $noreg, killed %7 :: (store (s64) into %ir.0)
+    $rax = COPY %6
+    RET 0, $rax
+
+...
+---
+name:            test_not_erased_when_sf_used
+alignment:       16
+tracksDebugUserValues: false
+registers:
+  - { id: 0, class: gr64, preferred-register: '' }
+  - { id: 1, class: gr64, preferred-register: '' }
+  - { id: 2, class: gr64, preferred-register: '' }
+  - { id: 3, class: gr64, preferred-register: '' }
+  - { id: 4, class: gr64, preferred-register: '' }
+  - { id: 5, class: gr32, preferred-register: '' }
+  - { id: 6, class: gr32, preferred-register: '' }
+  - { id: 7, class: gr64, preferred-register: '' }
+  - { id: 8, class: gr64, preferred-register: '' }
+liveins:
+  - { reg: '$rdi', virtual-reg: '%0' }
+  - { reg: '$rsi', virtual-reg: '%1' }
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0 (%ir-block.4):
+    liveins: $rdi, $rsi
+
+    ; CHECK-LABEL: name: test_not_erased_when_sf_used
+    ; CHECK: [[COPY:%[0-9]+]]:gr64 = COPY $rsi
+    ; CHECK-NEXT: [[COPY1:%[0-9]+]]:gr64 = COPY $rdi
+    ; CHECK-NEXT: [[MOV64rm:%[0-9]+]]:gr64 = MOV64rm [[COPY1]], 1, $noreg, 0, $noreg :: (load (s64) from %ir.0)
+    ; CHECK-NEXT: [[COPY2:%[0-9]+]]:gr32 = COPY [[MOV64rm]].sub_32bit
+    ; CHECK-NEXT: [[AND32ri8_:%[0-9]+]]:gr32 = AND32ri8 [[COPY2]], 3, implicit-def dead $eflags
+    ; CHECK-NEXT: [[SUBREG_TO_REG:%[0-9]+]]:gr64 = SUBREG_TO_REG 0, killed [[AND32ri8_]], %subreg.sub_32bit
+    ; CHECK-NEXT: TEST64rr [[SUBREG_TO_REG]], [[SUBREG_TO_REG]], implicit-def $eflags
+    ; CHECK-NEXT: [[CMOV64rr:%[0-9]+]]:gr64 = CMOV64rr [[SUBREG_TO_REG]], [[COPY]], 8, implicit $eflags
+    ; CHECK-NEXT: MOV64mr [[COPY1]], 1, $noreg, 0, $noreg, killed [[CMOV64rr]] :: (store (s64) into %ir.0)
+    ; CHECK-NEXT: $rax = COPY [[MOV64rm]]
+    ; CHECK-NEXT: RET 0, $rax
+    %1:gr64 = COPY $rsi
+    %0:gr64 = COPY $rdi
+    %4:gr64 = MOV64rm %0, 1, $noreg, 0, $noreg :: (load (s64) from %ir.0)
+    %5:gr32 = COPY %4.sub_32bit
+    %6:gr32 = AND32ri8 %5, 3, implicit-def dead $eflags
+    %7:gr64 = SUBREG_TO_REG 0, killed %6, %subreg.sub_32bit
+    TEST64rr %7, %7, implicit-def $eflags
+    %8:gr64 = CMOV64rr %7, %1, 8, implicit $eflags
+    MOV64mr %0, 1, $noreg, 0, $noreg, killed %8 :: (store (s64) into %ir.0)
+    $rax = COPY %4
+    RET 0, $rax
+
+...
+---
+name:            test_not_erased_when_eflags_change
+alignment:       16
+tracksDebugUserValues: false
+registers:
+  - { id: 0, class: gr64, preferred-register: '' }
+  - { id: 1, class: gr64, preferred-register: '' }
+  - { id: 2, class: gr64, preferred-register: '' }
+  - { id: 3, class: gr64, preferred-register: '' }
+  - { id: 4, class: gr64, preferred-register: '' }
+  - { id: 5, class: gr64, preferred-register: '' }
+  - { id: 6, class: gr32, preferred-register: '' }
+  - { id: 7, class: gr32, preferred-register: '' }
+  - { id: 8, class: gr64, preferred-register: '' }
+  - { id: 9, class: gr64, preferred-register: '' }
+  - { id: 10, class: gr64, preferred-register: '' }
+liveins:
+  - { reg: '$rdi', virtual-reg: '%0' }
+  - { reg: '$rsi', virtual-reg: '%1' }
+  - { reg: '$rcx', virtual-reg: '%3' }
+  - { reg: '$r8', virtual-reg: '%4' }
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0 (%ir-block.5):
+    liveins: $rdi, $rsi, $rcx, $r8
+
+    ; CHECK-LABEL: name: test_not_erased_when_eflags_change
+    ; CHECK: [[COPY:%[0-9]+]]:gr64 = COPY $r8
+    ; CHECK-NEXT: [[COPY1:%[0-9]+]]:gr64 = COPY $rcx
+    ; CHECK-NEXT: [[COPY2:%[0-9]+]]:gr64 = COPY $rsi
+    ; CHECK-NEXT: [[COPY3:%[0-9]+]]:gr64 = COPY $rdi
+    ; CHECK-NEXT: [[MOV64rm:%[0-9]+]]:gr64 = MOV64rm [[COPY3]], 1, $noreg, 0, $noreg :: (load (s64) from %ir.0)
+    ; CHECK-NEXT: [[COPY4:%[0-9]+]]:gr32 = COPY [[MOV64rm]].sub_32bit
+    ; CHECK-NEXT: [[AND32ri8_:%[0-9]+]]:gr32 = AND32ri8 [[COPY4]], 3, implicit-def dead $eflags
+    ; CHECK-NEXT: [[SUBREG_TO_REG:%[0-9]+]]:gr64 = SUBREG_TO_REG 0, killed [[AND32ri8_]], %subreg.sub_32bit
+    ; CHECK-NEXT: [[XOR64ri8_:%[0-9]+]]:gr64 = XOR64ri8 [[COPY1]], 5, implicit-def dead $eflags
+    ; CHECK-NEXT: TEST64rr [[SUBREG_TO_REG]], [[SUBREG_TO_REG]], implicit-def $eflags
+    ; CHECK-NEXT: [[CMOV64rr:%[0-9]+]]:gr64 = CMOV64rr [[SUBREG_TO_REG]], [[COPY2]], 4, implicit $eflags
+    ; CHECK-NEXT: MOV64mr [[COPY3]], 1, $noreg, 0, $noreg, killed [[CMOV64rr]] :: (store (s64) into %ir.0)
+    ; CHECK-NEXT: MOV64mr [[COPY]], 1, $noreg, 0, $noreg, killed [[XOR64ri8_]] :: (store (s64) into %ir.4)
+    ; CHECK-NEXT: RET 0
+    %4:gr64 = COPY $r8
+    %3:gr64 = COPY $rcx
+    %1:gr64 = COPY $rsi
+    %0:gr64 = COPY $rdi
+    %5:gr64 = MOV64rm %0, 1, $noreg, 0, $noreg :: (load (s64) from %ir.0)
+    %6:gr32 = COPY %5.sub_32bit
+    %7:gr32 = AND32ri8 %6, 3, implicit-def dead $eflags
+    %8:gr64 = SUBREG_TO_REG 0, killed %7, %subreg.sub_32bit
+    %9:gr64 = XOR64ri8 %3, 5, implicit-def dead $eflags
+    TEST64rr %8, %8, implicit-def $eflags
+    %10:gr64 = CMOV64rr %8, %1, 4, implicit $eflags
+    MOV64mr %0, 1, $noreg, 0, $noreg, killed %10 :: (store (s64) into %ir.0)
+    MOV64mr %4, 1, $noreg, 0, $noreg, killed %9 :: (store (s64) into %ir.4)
+    RET 0
+
+...