This also produces a crash in wine (using FEAR demo) on r600g. Commenting out the opt_copy_propagation_elements pass solves the problem and the crash is gone.

Stack trace from the crash:
 0 0x7d8f9c6d _ZN36ir_copy_propagation_elements_visitor4killEP10kill_entry+0x7d() in r600_dri.so (0x00f9e454)
 1 0x7d8fa4fa _ZN36ir_copy_propagation_elements_visitor11visit_leaveEP13ir_assignment+0xc9() in r600_dri.so (0x00f9e484)
 2 0x7d9b8d32 _ZN13ir_assignment6acceptEP23ir_hierarchical_visitor+0xb1() in r600_dri.so (0x00f9e4b4)
 3 0x7d9b8715 visit_list_elements+0x34(v=0xf9e5b4, l=0x6d188130) [/root/git-mesa/src/glsl/ir_hv_accept.cpp:48] in r600_dri.so (0x00f9e4f4)
 4 0x7d8f9f85 _ZN36ir_copy_propagation_elements_visitor11visit_enterEP21ir_function_signature+0x94() in r600_dri.so (0x00f9e514)
 5 0x7d9b884e _ZN21ir_function_signature6acceptEP23ir_hierarchical_visitor+0x1d() in r600_dri.so (0x00f9e544)
 6 0x7d9b8715 visit_list_elements+0x34(v=0xf9e5b4, l=0x6d1880e0) [/root/git-mesa/src/glsl/ir_hv_accept.cpp:48] in r600_dri.so (0x00f9e564)
 7 0x7d9b88ff _ZN11ir_function6acceptEP23ir_hierarchical_visitor+0x4e() in r600_dri.so (0x00f9e594)
 8 0x7d9b8715 visit_list_elements+0x34(v=0xf9e5b4, l=0x6d16c7b8) [/root/git-mesa/src/glsl/ir_hv_accept.cpp:48] in r600_dri.so (0x00f9e5f4)
 9 0x7d8fa3d0 do_copy_propagation_elements+0x9f(instructions=0x6d16c7b8) [/root/git-mesa/src/glsl/opt_copy_propagation_elements.cpp:455] in r600_dri.so (0x00f9e644)
10 0x7d8ee646 do_common_optimization+0x85(ir=0x6d16c7b8, linked=true, max_unroll_iterations=0x20) [/root/git-mesa/src/glsl/glsl_parser_extras.cpp:767] in r600_dri.so (0x00f9e694)
11 0x7d9c26ef link_shaders+0x26e(ctx=0x7d6ed0f0, prog=0x6d31d2c8) [/root/git-mesa/src/glsl/linker.cpp:1630] in r600_dri.so (0x00f9e6d4)
12 0x7d98e96f _mesa_glsl_link_shader+0x20e(ctx=0x7d6ed0f0, prog=0x6d31d2c8) [/root/git-mesa/src/mesa/program/ir_to_mesa.cpp:3211] in r600_dri.so (0x00f9e834)
13 0x7d94bb39 link_program+0x78() in r600_dri.so (0x00f9e8c4)
14 0x7ea843b0 in wined3d (+0x843af) (0x00f9e8f4)
15 0x7ea28a95 in wined3d (+0x28a94) (0x00f9e954)
16 0x7ea64a65 in wined3d (+0x64a64) (0x00f9ebd4)
17 0x7ea39331 in wined3d (+0x39330) (0x00f9ec24)
18 0x7eb38e86 in d3d9 (+0x8e85) (0x00f9ec84)
19 0x0050f688 in fearspdemo (+0x10f687) (0x19e22598)
20 0x19e22598 (0x19e27af8)

The problem seems to be that entry->remove() is called twice in certain cases.

Replacing the member function with something like this fixes the crash:
/* Remove any entries currently in the ACP for this kill. */
void
ir_copy_propagation_elements_visitor::kill(kill_entry *k)
{
   bool remove_var;

   foreach_list_safe(node, acp) {
      acp_entry *entry = (acp_entry *)node;
      remove_var = false;

      if (entry->lhs == k->var) {
	 entry->write_mask = entry->write_mask & ~k->write_mask;
	 if (entry->write_mask == 0)
	    remove_var = true;
      }
      if (entry->rhs == k->var) {
	 remove_var = true;
      }

      if (remove_var) entry->remove();
   }

   /* If we were on a list, remove ourselves before inserting */
   if (k->next)
      k->remove();

   this->kills->push_tail(k);
}

However I have no idea if that's the right fix. Eric?

*** Bug 38501 has been marked as a duplicate of this bug. ***

This pass was re-enabled a while back, but Regnum Online and Bioshock (running
in Wine) still suffers from an infinite loop.

I've seen this exact same issue with games in wine getting stuck in an infinite loop in libglsl. Commenting out the opt_copy_propagation_elements pass allows them to work again.

(In reply to comment #5)
> I've seen this exact same issue with games in wine getting stuck in an infinite
> loop in libglsl. Commenting out the opt_copy_propagation_elements pass allows
> them to work again.

Oh, since a version could be helpful: this was as of the xorg edgers PPA version 7.12.0~git20111125.dbf00812-0ubuntu0sarvatt~oneiric (up to dbf00812b073bd3f17cbbaadb14c6f603b83cd10).

I can't say I know very well what I am looking at it, so I may be completely wrong, but it appears as if this could be some accidental interaction with do_swizzle_swizzle. I stepped through do_common_optimization a number of times, and that is what seems to keep triggering it to loop again. 

Wine-dbg>
1: progress = 0
1038	   progress = do_swizzle_swizzle(ir) || progress;
Wine-dbg>
1: progress = 1
1039	   progress = do_noop_swizzle(ir) || progress;
Wine-dbg>

Created attachment 53924 [details]
a shader triggering the infinite loop

I've attached a shader that appears to trigger the infinite loop. Simply creating the shader, setting the source, compiling, creating and attaching to a program, and linking the program is enough to trigger it.

Created attachment 54480 [details]
IR states that do_swizzle_swizzle flips between

I've checked and commenting out do_swizzle_swizzle does also fix the issue. It seems to continually flip the ir between two states. The full ir dumps are attached from _mesa_print_ir, and here is the assign where it continually adds and removes a swiz wwww:

state 1:
      (assign  (xyzw) (var_ref _ret_val@107)  (expression vec4 max (expression vec4 min (swiz wwww (var_ref R0) )(constant float (1.000000)) ) (constant float (0.000000)) ) ) 

state 2:
      (assign  (xyzw) (var_ref _ret_val@108)  (expression vec4 max (expression vec4 min (swiz wwww (swiz wwww (var_ref R0) ))(constant float (1.000000)) ) (constant float (0.000000)) ) )

Created attachment 55097 [details] [review]
potential patch

I'm attaching a potential patch that fixes what might be a bug inopt_copy_propagation_elements.cpp. As it is now handle_rvalue will be called for both a swizzle and the swizzle's value. However handle_rvalue is written to handle both when passed a swizzle, so calling it only with the swizzle seems correct. If someone who knows better what is going on could review this I would much appreciate it.

Sorry for the excessive messages, though I forgot to add:

The proposed patch fixes the loop. It is copy_propagation_elements that adds the duplicate swizzle I mentioned in #9. So when handle_rvalue is passed (var_ref R0), it replaces it with (swiz wwww (var_ref R0)). Then swizzle_swizzle condenses it back to the single swizzle, and repeat.

Thanks for giving this bug some lovin'! 

The patch works for me, both Regnum Online and Bioshock no longer hangs on load. I haven't tried the FEAR demo yet.

I also made a piglit run with the patch applied and there are no regressions found. 

Any chance you can post the patch to the mailing list to get it reviewed and included for the upcoming release?
http://lists.freedesktop.org/mailman/listinfo/mesa-dev

Sent, thanks so much for the testing and encouragement. Since it is my first mesa patch it is comforting to know it works for you and doesn't break any tests before sending it off.

Thanks!  I've pushed your patch:

commit 6c29452f38dacace4f234e9526bfdc1e23fb5051
Author: Andy Clayton <q3aiml@gmail.com>
Date:   Thu Jan 5 21:17:53 2012 -0600

    glsl: fix glsl optimization infinite loop from copy_propagation_elements

And sent out a piglit testcase that's a trimmed-down version of the shader you had here.  That was really great to have for trying to understand this bug.