[JumpThreading] Fix opcode bonus in getJumpThreadDuplicationCost()

[gberry]

Summary

The code that was meant to adjust the duplication cost based on the
terminator opcode was not being executed in cases where the initial
threshold was hit inside the loop.

[gberry]

Updated description

[gberry]

Nadav, could you review this? It appears that a change of yours introduced this change in behavior:

c6990869 (Nadav Rotem 2012-12-03 17:34:44 +0000 294) // Stop scanning the block if we've reached the threshold.
c6990869 (Nadav Rotem 2012-12-03 17:34:44 +0000 295) if (Size > Threshold)
c6990869 (Nadav Rotem 2012-12-03 17:34:44 +0000 296) return Size;

[gberry]

Benchmarking results (on AArch64 A57-like processor):

spec2006/bzip2: improves 1.7%
no other significant changes in spec2000/2006

testsuite:
no significant changes
clamscan has similar static code changes as spec2006/bzip2 (it looks like it has a copy bzip2 in it), but these changes don't effect runtime performance

[mcrosier]

This looks like a straight forward fix to unintended behavior. LGTM with one minor suggestion.

lib/Transforms/Scalar/JumpThreading.cpp

346 ↗

(On Diff #42881)

How about just:

return Size > Bonus ? Size - Bonus : 0;

[gberry]

Will do, thanks.

[nadav]

LGTM.

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

 static unsigned getJumpThreadDuplicationCost(const BasicBlock *BB,
                                              unsigned Threshold) {
   /// Ignore PHI nodes, these will be flattened when duplication happens.
   BasicBlock::const_iterator I(BB->getFirstNonPHI());
 
   // FIXME: THREADING will delete values that are just used to compute the
   // branch, so they shouldn't count against the duplication cost.
 
+  unsigned Bonus = 0;
+  const TerminatorInst *BBTerm = BB->getTerminator();
+  // Threading through a switch statement is particularly profitable.  If this
+  // block ends in a switch, decrease its cost to make it more likely to happen.
+  if (isa<SwitchInst>(BBTerm))
+    Bonus = 6;
+
+  // The same holds for indirect branches, but slightly more so.
+  if (isa<IndirectBrInst>(BBTerm))
+    Bonus = 8;
+
+  // Bump the threshold up so the early exit from the loop doesn't skip the
+  // terminator-based Size adjustment at the end.
+  Threshold += Bonus;
+
   // Sum up the cost of each instruction until we get to the terminator.  Don't
   // include the terminator because the copy won't include it.
   unsigned Size = 0;
   for (; !isa<TerminatorInst>(I); ++I) {
 
     // Stop scanning the block if we've reached the threshold.
     if (Size > Threshold)
       return Size;
if (const CallInst *CI = dyn_cast<CallInst>(I)) {
         return ~0U;
       else if (!isa<IntrinsicInst>(CI))
         Size += 3;
       else if (!CI->getType()->isVectorTy())
         Size += 1;
     }
   }
 
-  // Threading through a switch statement is particularly profitable.  If this
-  // block ends in a switch, decrease its cost to make it more likely to happen.
-  if (isa<SwitchInst>(I))
-    Size = Size > 6 ? Size-6 : 0;
-
-  // The same holds for indirect branches, but slightly more so.
-  if (isa<IndirectBrInst>(I))
-    Size = Size > 8 ? Size-8 : 0;
-
-  return Size;
+  return Size > Bonus ? Size - Bonus : 0;
 }
 
 /// FindLoopHeaders - We do not want jump threading to turn proper loop
 /// structures into irreducible loops.  Doing this breaks up the loop nesting
 /// hierarchy and pessimizes later transformations.  To prevent this from
 /// happening, we first have to find the loop headers.  Here we approximate this
 /// by finding targets of backedges in the CFG.
 ///

llvm/trunk/test/Transforms/JumpThreading/select.ll

L2:
   call void @bar()
   ret void
 L3:
   call void @baz()
   ret void
 }
 
 
+; Jump threading of indirectbr with select as address.  Test increased
+; duplication threshold for cases where indirectbr is being threaded
+; through.
+
+; CHECK-LABEL: @test_indirectbr_thresh(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: br i1 %cond, label %L1, label %L3
+; CHECK-NOT: indirectbr
+define void @test_indirectbr_thresh(i1 %cond, i8* %address) nounwind {
+entry:
+  br i1 %cond, label %L0, label %L3
+L0:
+  %indirect.goto.dest = select i1 %cond, i8* blockaddress(@test_indirectbr_thresh, %L1), i8* %address
+  call void @quux()
+  call void @quux()
+  call void @quux()
+  indirectbr i8* %indirect.goto.dest, [label %L1, label %L2, label %L3]
+
+L1:
+  call void @foo()
+  ret void
+L2:
+  call void @bar()
+  ret void
+L3:
+  call void @baz()
+  ret void
+}
+
+
 ; A more complicated case: the condition is a select based on a comparison.
 
 ; CHECK-LABEL: @test_switch_cmp(
 ; CHECK-NEXT: entry:
 ; CHECK-NEXT: br i1 %cond, label %L0, label %[[THREADED:[A-Za-z.0-9]+]]
 ; CHECK: [[THREADED]]:
 ; CHECK-NEXT: call void @quux
 ; CHECK-NEXT: br label %L1