[ARM] Fix perf regression in compare optimization.

[jgalenson]

Summary

Fix a performance regression caused by r322737.

While trying to make it easier to replace compares with existing adds and subtracts, I accidentally stopped it from doing so in some cases. This should fix that. I'm also fixing another potential bug in that commit.

[jgalenson]

The problem was the "--E" in my previous commit (about 25 lines above the changed line). That caused the loop just below it (containing this line) to run in some cases it did not before. If I is the first instruction in the block, it now enters the loop and then returns false at the line I changed. I modified that to break out of the loop instead, which allows us to still consider MI as a candidate.

[efriedma]

lib/Target/ARM/ARMBaseInstrInfo.cpp

2743

Is there some reason to expect that --E is a valid, given E could be the first instruction in its basic block?

2750

This loop is confusing. The initial value of I is the compare. You're looping until it equals E... but you also have an early exit if you hit the beginning of the basic block.

Could you fix the loop to explicitly compute its exit condition in some more intuitive way? Maybe you could express this more clearly using MachineBasicBlock::reverse_iterator. And ideally you could use range-based for loop with "make_range" rather an explicit increment/decrement.

[jgalenson]

lib/Target/ARM/ARMBaseInstrInfo.cpp

2743

Good catch. I'll guard this.

2750

I agree that the loop is confusing, but I'd rather make that change as part of a separate commit, since doing so is surprisingly non-trivial and could well introduce new bugs.

[jgalenson]

This guards the potential bug Eli pointed out.

This isn't a perfect solution, since if E is the first statement in the block, the loop won't search it (and the loop structure is confusing). Hopefully we can fix that in a follow-up commit.

[efriedma]

LGTM with the comment fixed.

lib/Target/ARM/ARMBaseInstrInfo.cpp

2750

Okay.

2766

Please fix this comment; there is no 'and', and instructions after the comparison are irrelevant.

[jgalenson]

Thanks.

lib/Target/ARM/ARMBaseInstrInfo.cpp

2766

For what it's worth, I believe the 'and' refers to the block at the beginning of the function, which can set MI to be equal to an 'and'. But I agree that this comment is confusing, so I'll remove it.

[eastig]

Hi Joel,

I have benchmarked the patch. It fixes the regressions.

Thanks,
Evgeny Astigeevich

[jgalenson]

Thanks, Evgeny! I'll fix the comment and commit it now and then continue to work on cleaning up this loop.

[eastig]

In D42263#982004, @jgalenson wrote:

Thanks, Evgeny! I'll fix the comment and commit it now and then continue to work on cleaning up this loop.

Let me know if you need some benchmarking.

Thanks,
Evgeny

lib/Target/ARM/ARMBaseInstrInfo.cpp

if (HasStmts && CanReorder) {
       CmpInstr.getParent()->insert(E, MI);
     }
     I = CmpInstr;
     E = MI;
   } else {
     // Allow the loop below to search E (which was initially MI).  Since MI and
     // SubAdd have different tests, even if that instruction could not be MI, it
     // could still potentially be SubAdd.
     --E;
   }
 
   // Check that CPSR isn't set between the comparison instruction and the one we
   // want to change. At the same time, search for SubAdd.
   const TargetRegisterInfo *TRI = &getRegisterInfo();
   --I;
   for (; I != E; --I) {
     const MachineInstr &Instr = *I;
 
     // Check whether CmpInstr can be made redundant by the current instruction.
     if (isRedundantFlagInstr(&CmpInstr, SrcReg, SrcReg2, CmpValue, &*I)) {
       SubAdd = &*I;
       break;
     }
 
     if (Instr.modifiesRegister(ARM::CPSR, TRI) ||
         Instr.readsRegister(ARM::CPSR, TRI))
       // This instruction modifies or uses CPSR after the one we want to
       // change. We can't do this transformation.
       return false;
 
     if (I == B)
       // The 'and' is below the comparison instruction.
-      return false;
+      break;
   }
 
   // Return false if no candidates exist.
   if (!MI && !SubAdd)
     return false;
 
   // The single candidate is called MI.
   if (!MI) MI = SubAdd;

test/CodeGen/ARM/overflow-intrinsic-optimizations.ll

 cont1:
   %5 = extractvalue { i32, i1 } %3, 0
   %cmp = icmp slt i32 %5, %2
   br i1 %cmp, label %for.body, label %for.cond.cleanup
 }
 
 declare void @external_fn(...) local_unnamed_addr #0
 
+define i32 @are_equal(i32* nocapture readonly %a1, i32* nocapture readonly %a2, i32 %n) local_unnamed_addr #0 {
+; CHECK-LABEL: are_equal
+; CHECK: subs r{{[0-9]+}}, r{{[0-9]+}}, #1
+; CHECK-NEXT: bne
+entry:
+  %tobool7 = icmp eq i32 %n, 0
+  br i1 %tobool7, label %while.end, label %land.rhs.preheader
+
+land.rhs.preheader:
+  br label %land.rhs
+
+while.cond:
+  %tobool = icmp eq i32 %dec9, 0
+  br i1 %tobool, label %while.end, label %land.rhs
+
+land.rhs:
+  %dec9.in = phi i32 [ %dec9, %while.cond ], [ %n, %land.rhs.preheader ]
+  %dec9 = add nsw i32 %dec9.in, -1
+  %arrayidx = getelementptr inbounds i32, i32* %a1, i32 %dec9
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx1 = getelementptr inbounds i32, i32* %a2, i32 %dec9
+  %1 = load i32, i32* %arrayidx1, align 4
+  %cmp = icmp eq i32 %0, %1
+  br i1 %cmp, label %while.cond, label %while.end
+
+while.end:
+  %n.addr.0.lcssa = phi i32 [ 0, %entry ], [ 0, %while.cond ], [ %dec9.in, %land.rhs ]
+  %cmp2 = icmp slt i32 %n.addr.0.lcssa, 1
+  %conv = zext i1 %cmp2 to i32
+  ret i32 %conv
+}
+
 declare void @llvm.trap() #2
 declare { i32, i1 } @llvm.sadd.with.overflow.i32(i32, i32) #1
 declare { i32, i1 } @llvm.uadd.with.overflow.i32(i32, i32) #1
 declare { i32, i1 } @llvm.ssub.with.overflow.i32(i32, i32) #1
 declare { i32, i1 } @llvm.usub.with.overflow.i32(i32, i32) #1
 declare { i32, i1 } @llvm.smul.with.overflow.i32(i32, i32) #1
 declare { i32, i1 } @llvm.umul.with.overflow.i32(i32, i32) #1