The problem appears in revision 200588 in version 4.9. In method "find_reloads()" in gcc/reload.c, the loop on line 3324 should break immediately after "badop" is set to "1". All the iterations after "badop" set to "1" do not perform any useful work, at best they just set "badop" again to "1". Similar problem also appears in the same method "find_reloads()" in line 4641. The loop should break immediately after "ok" is set to "0".
Created attachment 30442 [details] Suggested patch for loop at line 3324
Created attachment 30444 [details] Suggested patch for loop at line 3324
Created attachment 30445 [details] Suggested patch for loop at line 4641
Patch sent to gcc-patches@ http://gcc.gnu.org/ml/gcc-patches/2013-07/msg00930.html
Fixed in mainline.