Remove redundent register mov by improving TwoAddressInstructionPass

[wmi]

Summary

Hi,

We found a problem in TwoAddressInstructionPass which could generate redundent register mov insns in loop, and proposed a patch to fix it.

Here is the small testcase:

1.c:

int M, total;

void foo() {

int i;
for (i = 0; i < M; i++) {
  total = total + i / 2;
}

}

~/workarea/llvm-r230041/build/bin/clang -O2 -fno-vectorize -fno-unroll-loops -S 1.c

This is the kernel loop in 1.s:

.LBB0_2: # %for.body

1. =>This Inner Loop Header: Depth=1 movl %edx, %esi movl %ecx, %edx shrl $31, %edx addl %ecx, %edx sarl %edx addl %esi, %edx incl %ecx cmpl %eax, %ecx jl .LBB0_2 --------------------------

The first mov insn "movl %edx, %esi" could be removed if we change "addl %esi, %edx" to "addl %edx, %esi".

The IR before TwoAddressInstructionPass is:
BB#2: derived from LLVM BB %for.body

Predecessors according to CFG: BB#1 BB#2
    %vreg3<def> = COPY %vreg12<kill>; GR32:%vreg3,%vreg12
    %vreg2<def> = COPY %vreg11<kill>; GR32:%vreg2,%vreg11
    %vreg7<def,tied1> = SHR32ri %vreg3<tied0>, 31, %EFLAGS<imp-def,dead>; GR32:%vreg7,%vreg3
    %vreg8<def,tied1> = ADD32rr %vreg3<tied0>, %vreg7<kill>, %EFLAGS<imp-def,dead>; GR32:%vreg8,%vreg3,%vreg7
    %vreg9<def,tied1> = SAR32r1 %vreg8<kill,tied0>, %EFLAGS<imp-def,dead>; GR32:%vreg9,%vreg8
    %vreg4<def,tied1> = ADD32rr %vreg9<kill,tied0>, %vreg2<kill>, %EFLAGS<imp-def,dead>; GR32:%vreg4,%vreg9,%vreg2
    %vreg5<def,tied1> = INC64_32r %vreg3<kill,tied0>, %EFLAGS<imp-def,dead>; GR32:%vreg5,%vreg3
    CMP32rr %vreg5, %vreg0, %EFLAGS<imp-def>; GR32:%vreg5,%vreg0
    %vreg11<def> = COPY %vreg4; GR32:%vreg11,%vreg4
    %vreg12<def> = COPY %vreg5<kill>; GR32:%vreg12,%vreg5
    JL_4 <BB#2>, %EFLAGS<imp-use,kill>

Now TwoAddressInstructionPass will choose vreg9 to be tied with vreg4. However, it doesn't see that there is copy from vreg4 to vreg11 and another copy from vreg11 to vreg2 inside the loop body. To remove those copies, it is necessary to choose vreg2 to be tied with vreg4 instead of vreg9. This code pattern commonly appears when there is reduction operation in a loop.

The patch fixed the problem and improved O2 performance of google internal benchmarks by 0.74% on average (The biggest improvement for a benchmark is 5%)

Wei.

[qcolombet]

Hi Wei,

Inlined a couple of comments.
The main problem is that I believe my miss the general case here.

Thanks,
-Quentin

lib/CodeGen/TwoAddressInstructionPass.cpp

318

Use the API of MachineRegisterInfo to achieve this.
E.g, MRI has getUniqueVRegDef and use_nodgb_instructions.

626

Have you experiment with several users?
I.e., this code wouldn’t catch this:

// %reg101 = MOV %reg100
// %reg102 = ...
// %reg103 = ADD %reg102, %reg101
// %reg104 = <something> %reg103
// %reg100 = MOV %reg103

Whereas this is fundamentally the same problem.

The bottom line is that this looks like a narrow case of a more general problem.
I’m fine moving incrementally, as long as you commit that you will working on this.

635

I would refactor this code a bit differently.

Something like.
if (useA && useA->isCopy) {

 unsigned DefCopyA = useA->getOperand(0).getReg();
// Where match is the check for isCopy and getOperand(1).getReg() == DefCopyA
 if (match(DefCopyA, defB)
  return false;
 if (match(DefCopyA, defC)
  return true;

}

test/CodeGen/X86/twoaddr-coalesce-3.ll

2

Use FileCheck and CHECK lines pleas.

8

Remove metadata and explain what this function is testing, so that future updates would be easier.

[chandlerc]

No real comments on the code, Quentin knows it much better than I do. =]

test/CodeGen/X86/twoaddr-coalesce-3.ll

8

In addition, if there is a way to fold this into an existing test, that would be much better. This is usually possible due to using FileCheck, and CHECK-LABEL bracketed assertions.

[wmi]

Thanks for the review. Will fix according to your comments, and will expand the code to handle the case you mentioned.

To solve the problem generally, I think it is best to implement it in register allocation phase, because it is possible that the choice made in Two Addr Instruction pass may not be the best in register allocation context. gcc removed the regmove pass (it is the correspondence to TwoAddrInst pass) and implemented the heuristic in register allocation, and got better performance. I am collecting testcases for which a better heuristic is necessary. This is a part I like to work on, however, I want to work on it incrementally as you suggest -- solve the common problem in TwoAddrInst pass for the first step.

[wmi]

I rewrite the code to expand the cases that can be handled.

Now for %reg103 = ADD %reg102, %reg101; I check whether there is a reversed copy chain from %reg102 to %reg103 or from %reg101 to %reg103. If there is a reversed copy chain from a src operand to a dest oeprand, that src operand will be choosen to be merged with the dest operand. In this way, the case Quentin suggested like the following will be handled.

%reg101 = MOV %reg100
%reg102 = ...
%reg103 = ADD %reg102, %reg101
%reg104 = <something> %reg103
// %reg100 = MOV %reg103

I still don't use getUniqueVRegDef to replace getSingleDef because getSingleDef can find out the def inside current BB when a use has multiple defs (one in current BB and one in predecessor BB). This is common because the IR in TwoAddrInstruction pass is already out-of-ssa form. getUniqueVRegDef will return NULL for that case.

Thanks,
Wei.

[chandlerc]

Minor style comments only.

lib/CodeGen/TwoAddressInstructionPass.cpp

314–315

Please use our modern doxygen comment style for new code. (I know a bunch of old code doesn't)

http://llvm.org/docs/CodingStandards.html#doxygen-use-in-documentation-comments

340–341

It would be good to document your idea for how to handle this more generally in a FIXME here and maybe file a PR to track it?

[wmi]

Address Chandler's comments:

1. change the comments to doxygen format.
2. Add a FIXME in the code and file a PR to track the problems that havn't been addressed: http://llvm.org/bugs/show_bug.cgi?id=22689

[majnemer]

lib/CodeGen/TwoAddressInstructionPass.cpp

316

Please use MachineInstr * instead of MachineInstr*.

318

Variable names are capitalized.

327

nullptr

[qcolombet]

lib/CodeGen/TwoAddressInstructionPass.cpp

319

Use def_instructions or def_operands instead.
That way, you wouldn’t have to check for isDef in the loop.

342

I would rather have a set of visited copies or reg instead of a magic constant.
If it turns out to be too expensive, then we can introduce parametrizable magic constant!

345

LLVM idiom would be the opposite:
if (!Def || !…)

return false;

625

nitpick:
"to *hopefully* eliminate an otherwise unavoidable copy.”

We do not have guarantee that copy will indeed be eliminated.

632

For the record, if you are interested into this, look into the register coalescer pass.

test/CodeGen/X86/twoaddr-coalesce-3.ll

45

No need for #0.

[echristo]

As a general comment you'll want to get into the habit of using clang-format on your patches. It'll solve the formatting side of the coding convention changes you'll need to get used to. :)

-eric

[wmi]

Addressed Quentin and Majnemer's comments.

As Eric suggested, I tried clang-format. It is great.

Thanks,
Wei.

[qcolombet]

Hi Wei,

Looks almost good :).

I should have pay more attention to the tests, sorry about that. Please make them more verbose and do not rely on basic block labels.

Thanks,
-Quentin

test/CodeGen/X86/twoaddr-coalesce-3.ll

23

I do not think we usually rely on basic block labels. Instead, check for branch instructions to know when you cross a basic block boundary.

24

Check the actual chain of computation, i.e., surrounding instruction + operands, to be sure we generate correct code.

[wmi]

Thanks. I rewrited the CHECKs for the test.

[qcolombet]

test/CodeGen/X86/twoaddr-coalesce-3.ll

23

Like I said, you shouldn’t use basic block labels, but rely on branch instruction on other block.
E.g, on my machine the label looks like this: LBB0_…, i.e., no leading ‘.’.

So, what I was saying was to use something like:

; End of the first block.
CHECK: jp
; We enter the loop
CHECK loop boby
; The loop body is done
CHECK jp

[wmi]

lib/CodeGen/TwoAddressInstructionPass.cpp

314–315

Fixed.

340–341

FIXME added. File a PR here: http://llvm.org/bugs/show_bug.cgi?id=22689

test/CodeGen/X86/twoaddr-coalesce-3.ll

23

Yes, I understand your concern. However using branch instruction in previous block as boundary will introduce extra code in loop preheader, including mov. Like the following movl total(%rip), ..., I can make the test right, but it introduces extra complexity.

jle .LBB0_4

BB#1: # %for.body.lr.ph

xorl %edx, %edx
movl total(%rip), %ecx
.align 16, 0x90
.LBB0_2: # %for.body

1. =>This Inner Loop Header: Depth=1

movl %edx, %esi
shrl $31, %esi
addl %edx, %esi
sarl %esi
addl %esi, %ecx
incl %edx
cmpl %eax, %edx
jl .LBB0_2

Do you like CHECK: [[LOOP:[.]?LBB0_[0-9]+]]; ? If not, I will follow your way to use last branch as the boundary.

[qcolombet]

test/CodeGen/X86/twoaddr-coalesce-3.ll

23

In that case, I would use 'movl total' as an anchor.

Another way to avoid this label problem is to specify a -mtriple instead of just a -march. Anyhow, I am not sure labels are stable between debug and assert builds. Same thing for the assembly comments, i.e., I am not sure your output will contain: # %for.body.

The bottom line is that I really think you shouldn't rely on labels, but I may be wrong of course!

[chandlerc]

test/CodeGen/X86/twoaddr-coalesce-3.ll

23

FWIW, I agree that relying on specific label naming isn't a great strategy. However, I think for assembly tests, the instruction comments are very valuable and we should always keep them stable. For example, all of the shuffle testing using the comments rather than checking magic numbers. So I would suggest

[[LOOP1:^[.\w]+:]]: # %for.body

Essentially, match the specific x86 pattern for labels, any label, and the comment to identify which one.

[wmi]

Follow Chandler's suggestion for the testcase since it is helpful for testcase readability. If it somehow doesn't work for certain platforms, I am ready to fix it using mov total(％rip), ... as an anchor.

Thanks,
Wei.

[qcolombet]

test/CodeGen/X86/twoaddr-coalesce-3.ll

23

Agreed.

I was not sure the comment were printed in release mode, but now that I think about this it happens only if the would pipeline is in release mode.

[qcolombet]

Thanks Wei.

LGTM.

Q.

[wmi]

Thanks for your patience! The comment is helpful!

Wei.

[echristo]

Applied thusly:

dzur:~/sources/llvm> git svn dcommit
Committing to https://llvm.org/svn/llvm-project/llvm/trunk ...
A test/CodeGen/X86/twoaddr-coalesce-3.ll
M lib/CodeGen/TwoAddressInstructionPass.cpp
Committed r231148

-eric

lib/CodeGen/TwoAddressInstructionPass.cpp

class TwoAddressInstructionPass : public MachineFunctionPass {
   // DstRegMap - A map from virtual registers to physical registers which are
   // likely targets to be coalesced to due to copies to physical registers from
   // virtual registers. e.g. r1 = move v1024.
   DenseMap<unsigned, unsigned> DstRegMap;
 
   bool sink3AddrInstruction(MachineInstr *MI, unsigned Reg,
                             MachineBasicBlock::iterator OldPos);
 
+  bool isRevCopyChain(unsigned FromReg, unsigned ToReg, int Maxlen);
+
   bool noUseAfterLastDef(unsigned Reg, unsigned Dist, unsigned &LastDef);
 
   bool isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC,
                              MachineInstr *MI, unsigned Dist);
 
   bool commuteInstruction(MachineBasicBlock::iterator &mi,
                           unsigned RegB, unsigned RegC, unsigned Dist);
 
sink3AddrInstruction(MachineInstr *MI, unsigned SavedReg,
 
   if (LIS)
     LIS->handleMove(MI);
 
   ++Num3AddrSunk;
   return true;
 }
 
+/// getSingleDef -- return the MachineInstr* if it is the single def of the Reg
+/// in current BB.
+static MachineInstr *getSingleDef(unsigned Reg, MachineBasicBlock *BB,
+                                  const MachineRegisterInfo *MRI) {
+  MachineInstr *Ret = nullptr;
+  for (MachineInstr &DefMI : MRI->def_instructions(Reg)) {
+    if (DefMI.getParent() != BB || DefMI.isDebugValue())
+      continue;
+    if (!Ret)
+      Ret = &DefMI;
+    else if (Ret != &DefMI)
+      return nullptr;
+  }
+  return Ret;
+}
+
+/// Check if there is a reversed copy chain from FromReg to ToReg:
+/// %Tmp1 = copy %Tmp2;
+/// %FromReg = copy %Tmp1;
+/// %ToReg = add %FromReg ...
+/// %Tmp2 = copy %ToReg;
+/// MaxLen specifies the maximum length of the copy chain the func
+/// can walk through.
+bool TwoAddressInstructionPass::isRevCopyChain(unsigned FromReg, unsigned ToReg,
+                                               int Maxlen) {
+  unsigned TmpReg = FromReg;
+  for (int i = 0; i < Maxlen; i++) {
+    MachineInstr *Def = getSingleDef(TmpReg, MBB, MRI);
+    if (!Def || !Def->isCopy())
+      return false;
+
+    TmpReg = Def->getOperand(1).getReg();
+
+    if (TmpReg == ToReg)
+      return true;
+  }
+  return false;
+}
+
 /// noUseAfterLastDef - Return true if there are no intervening uses between the
 /// last instruction in the MBB that defines the specified register and the
 /// two-address instruction which is being processed. It also returns the last
 /// def location by reference
 bool TwoAddressInstructionPass::noUseAfterLastDef(unsigned Reg, unsigned Dist,
                                                   unsigned &LastDef) {
   LastDef = 0;
   unsigned LastUse = Dist;
if (!noUseAfterLastDef(regC, Dist, LastDefC))
     return false;
 
   // If there is a use of regB between its last def (could be livein) and this
   // instruction, then go ahead and make this transformation.
   unsigned LastDefB = 0;
   if (!noUseAfterLastDef(regB, Dist, LastDefB))
     return true;
 
+  // Look for situation like this:
+  // %reg101 = MOV %reg100
+  // %reg102 = ...
+  // %reg103 = ADD %reg102, %reg101
+  // ... = %reg103 ...
+  // %reg100 = MOV %reg103
+  // If there is a reversed copy chain from reg101 to reg103, commute the ADD
+  // to eliminate an otherwise unavoidable copy.
+  // FIXME:
+  // We can extend the logic further: If an pair of operands in an insn has
+  // been merged, the insn could be regarded as a virtual copy, and the virtual
+  // copy could also be used to construct a copy chain.
+  // To more generally minimize register copies, ideally the logic of two addr
+  // instruction pass should be integrated with register allocation pass where
+  // interference graph is available.
+  if (isRevCopyChain(regC, regA, 3))
+    return true;
+
+  if (isRevCopyChain(regB, regA, 3))
+    return false;
+
   // Since there are no intervening uses for both registers, then commute
   // if the def of regC is closer. Its live interval is shorter.
   return LastDefB && LastDefC && LastDefC > LastDefB;
 }
 
 /// commuteInstruction - Commute a two-address instruction and update the basic
 /// block, distance map, and live variables if needed. Return true if it is
 /// successful.

test/CodeGen/X86/twoaddr-coalesce-3.ll

+; RUN: llc < %s -march=x86-64 | FileCheck %s
+; This test is to ensure TwoAddrInstruction pass choose the proper operands to merge and
+; generate less mov insns.
+
+@M = common global i32 0, align 4
+@total = common global i32 0, align 4
+@g = common global i32 0, align 4
+
+; Function Attrs: nounwind uwtable
+define void @foo() {
+entry:
+  %0 = load i32* @M, align 4
+  %cmp3 = icmp sgt i32 %0, 0
+  br i1 %cmp3, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry
+  %total.promoted = load i32* @total, align 4
+  br label %for.body
+
+; Check that only one mov will be generated in the kernel loop.
+; CHECK-LABEL: foo:
+; CHECK: [[LOOP1:^[a-zA-Z0-9_.]+]]: # %for.body
+; CHECK-NOT: mov
+; CHECK: movl {{.*}}, [[REG1:%[a-z0-9]+]]
+; CHECK-NOT: mov
+; CHECK: shrl $31, [[REG1]]
+; CHECK-NOT: mov
+; CHECK: jl [[LOOP1]]
+for.body:                                         ; preds = %for.body.lr.ph, %for.body
+  %add5 = phi i32 [ %total.promoted, %for.body.lr.ph ], [ %add, %for.body ]
+  %i.04 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.body ]
+  %div = sdiv i32 %i.04, 2
+  %add = add nsw i32 %div, %add5
+  %inc = add nuw nsw i32 %i.04, 1
+  %cmp = icmp slt i32 %inc, %0
+  br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:                       ; preds = %for.body
+  store i32 %add, i32* @total, align 4
+  br label %for.end
+
+for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
+  ret void
+}
+
+; Function Attrs: nounwind uwtable
+define void @goo() {
+entry:
+  %0 = load i32* @M, align 4
+  %cmp3 = icmp sgt i32 %0, 0
+  br i1 %cmp3, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry
+  %total.promoted = load i32* @total, align 4
+  br label %for.body
+
+; Check that only two mov will be generated in the kernel loop.
+; CHECK-LABEL: goo:
+; CHECK: [[LOOP2:^[a-zA-Z0-9_.]+]]: # %for.body
+; CHECK-NOT: mov
+; CHECK: movl {{.*}}, [[REG2:%[a-z0-9]+]]
+; CHECK-NOT: mov
+; CHECK: shrl $31, [[REG2]]
+; CHECK-NOT: mov
+; CHECK: movl {{.*}}, g(%rip)
+; CHECK: jl [[LOOP2]]
+for.body:                                         ; preds = %for.body.lr.ph, %for.body
+  %add5 = phi i32 [ %total.promoted, %for.body.lr.ph ], [ %add, %for.body ]
+  %i.04 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.body ]
+  %div = sdiv i32 %i.04, 2
+  %add = add nsw i32 %div, %add5
+  store volatile i32 %add, i32* @g, align 4
+  %inc = add nuw nsw i32 %i.04, 1
+  %cmp = icmp slt i32 %inc, %0
+  br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:                       ; preds = %for.body
+  store i32 %add, i32* @total, align 4
+  br label %for.end
+
+for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
+  ret void
+}
+