This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Loop invariant motion from cold block


It appears to me that both loop invariant motion passes (tree/rtl) don't look at basic block frequencies and will gladly hoist invariant code from a cold block within a loop. This can impact performance by executing (possibly costly) code that would otherwise not be executed, adds another register that is live through the loop, and possibly increases number of callee-saved registers used in the procedure (which require save/restore) if there is a call in the loop. Following simplified test was patterned after code observed in Boost library, which apparently has a fair number of asserts sprinkled throughout.

volatile int x;
void assert_fail(int, char *, char *);
void foo(int *a, int n, int k) {
  int i;

  for(i=0; i<n; i++) {
    if (__builtin_expect(x,0))
      assert_fail(k / 5, "one", "two");
    a[i] = k;
  }
}

Compiling the above with -O2, tree-LIM (tree-ssa-loop-im.c) will yank the 'k/5' expression out of the loop and rtl-LIM (loop-invariant.c) will yank the address computations for the 2 strings out of the loop. The default probability for __builtin_expect is 90%, but even adding --param builtin-expect-probability=100 to the compile such that the block containing the call looks to never be executed still results in invariant hoisting.

A simple change like the following prevents the hoisting in the rtl pass, I assume something similar could also be added to the tree pass. But I'd like to hear others thoughts on whether this is an acceptable approach/issue that should be fixed. The code below prevents motion if the block containing it is executed <= 10% of the time the loop header is. Is there a better approach there instead of another magic number? Should it be based on PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY)? Basing on BUILTIN_EXPECT_PROBABILITY seems to make sense to me for the above case, but what about the more general case where __builtin_expect() isn't used and branch probabilities are guessed based on other heurstics?

Index: loop-invariant.c
===================================================================
--- loop-invariant.c    (revision 216843)
+++ loop-invariant.c    (working copy)
@@ -1000,6 +1000,11 @@ find_invariants_bb (basic_block bb, bool
 {
   rtx_insn *insn;

+
+  /* Don't move invariants from cold block inside the loop. */
+  if (bb->frequency <= (bb->loop_father->header->frequency / 10) )
+    return;
+
   FOR_BB_INSNS (bb, insn)
     {
       if (!NONDEBUG_INSN_P (insn))


Thanks for any feedback,
Pat




Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]