There seems to be multiple issues here.

One is a bug in the TARGET_RELOCATABLE handling in the powerpc backend, it emits the LCL and LCF symbols in the IL, but then emits them into the actual assembly only if some conditions are satisfied.  If they make it through into debug insns for some reason, that obviously results in the undefined references.
Perhaps the target address legitimization should handle those, or if the backend determines that it won't emit the symbols it should scan the IL for any possible debug uses and reset them.  I'm afraid there is nothing dwarf2out can do for this.

And another thing is why valtrack during DSE2 emits a debug instruction containing this.
At *.split2 we have:
(insn 36 35 37 2 (set (reg/v:SI 0 0 [orig:239 s2 ] [239])
        (lshiftrt:SI (reg/v:SI 3 3 [orig:265 adler ] [265])
            (const_int 16 [0x10]))) ../../../../../../../../../rtems/c/src/lib/libbsp/powerpc/motorola_powerpc/bootloader/../../../powerpc/shared/b
     (nil))
(debug_insn 37 36 39 2 (var_location:SI s2 (reg/v:SI 0 0 [orig:239 s2 ] [239])) ../../../../../../../../../rtems/c/src/lib/libbsp/powerpc/motorola_
     (nil))
which LGTM.
But then during pro_and_epilogue pass, the insn 36 is removed (perhaps some kind of fast DCE?), and instead a code in the prologue that uses register 0 for something completely different is added, which results in the wrong-debug because the debug insns weren't reset.

As a workaround, -fno-var-tracking-assignments should cure this.

The underlying problem here is that this sequence setting up the GOT/TOC pointer in adler32():

(insn 358 357 359 2 (parallel [                                                 
            (set (reg:SI 65 lr)                                                 
                (symbol_ref:SI ("*.LCF2")))                                     
            (use (unspec [                                                      
                        (symbol_ref:SI ("*.LCF2"))                              
                    ] UNSPEC_TOC))                                              
        ]) ../../../../../../../../../rtems/c/src/lib/libbsp/powerpc/motorola_p\
owerpc/bootloader/../../../powerpc/shared/bootloader/zlib.c:2081 -1             
     (nil))                                                                     
(insn 359 358 360 2 (set (reg:SI 30 30)                                         
        (reg:SI 65 lr)) ../../../../../../../../../rtems/c/src/lib/libbsp/power\
pc/motorola_powerpc/bootloader/../../../powerpc/shared/bootloader/zlib.c:2081 -\
1                                                                               
     (expr_list:REG_DEAD (reg:SI 65 lr)                                         
        (nil)))                                                                 
(insn 360 359 376 2 (set (reg:SI 0 0)                                           
        (mem:SI (plus:SI (reg:SI 30 30)                                         
                (minus:SI (symbol_ref:SI ("*.LCL2"))                            
                    (symbol_ref:SI ("*.LCF2")))) [0  S4 A8])) ../../../../../..\
/../../../rtems/c/src/lib/libbsp/powerpc/motorola_powerpc/bootloader/../../../p\
owerpc/shared/bootloader/zlib.c:2081 -1                                         
     (nil))                                                                     
(debug_insn 376 360 361 2 (var_location:SI D#37 (reg/v:SI 0 0 [orig:239 s2 ] [2\
39])) -1                                                                        
     (nil))                                                                     
(insn 361 376 362 2 (set (reg:SI 30 30)                                         
        (plus:SI (reg:SI 0 0)                                                   
            (reg:SI 30 30))) ../../../../../../../../../rtems/c/src/lib/libbsp/\
powerpc/motorola_powerpc/bootloader/../../../powerpc/shared/bootloader/zlib.c:2\
081 -1                                                                          
     (expr_list:REG_DEAD (reg:SI 0 0)                                           
        (expr_list:REG_UNUSED (reg:SI 30 30)                                    
            (nil))))

is deleted by peephole2

DCE: Deleting insn 361                                                          
deleting insn with uid = 361.                                                   
DCE: Deleting insn 360                                                          
deleting insn with uid = 360.                                                   
DCE: Deleting insn 359                                                          
deleting insn with uid = 359.                                                   
DCE: Deleting insn 358                                                          
deleting insn with uid = 358.

resulting in uses_TOC() returning false due to not finding UNSPEC_TOC, and thus not emitting the labels.  Deleting the insns is correct; we don't need the GOI pointer set up in adler32().  gcc-4.9 also does the same thing, but doesn't leak the labels into debug insns.

Re comment #1, insn 36 is not removed, but moved later to bb3

(insn 363 364 41 3 (set (reg/v:SI 0 0 [orig:239 s2 ] [239])                     
        (lshiftrt:SI (reg/v:SI 3 3 [orig:265 adler ] [265])                     
            (const_int 16 [0x10]))) 270 {lshrsi3}                               
     (nil))                                                                     
(debug_insn 41 363 42 3 (var_location:SI s2 (reg/v:SI 0 0 [orig:239 s2 ] [239])\
) -1                                                                            
     (nil))

The trouble is that the original debug insn is not removed.  We still have
(debug_insn 37 35 39 2 (var_location:SI s2 (reg/v:SI 0 0 [orig:239 s2 ] [239]))\
 ../../../../../../../../../rtems/c/src/lib/libbsp/powerpc/motorola_powerpc/boo\
tloader/../../../powerpc/shared/bootloader/zlib.c:2083 -1                       
     (nil))                                                                     
but this is not valid.  s2 does *not* live in reg:SI 0 at this point.

Created attachment 35342 [details]
prototype patch

This seems to cure the testcase.  I haven't bootstrapped it, and it probably isn't ideal since I haven't poked at debug insns a lot..
Still, it points out where the problem is, in move_insn_for_shrink_wrap.

Hmm, the bootstrap didn't get very far.  Seems I need a
df_insn_rescan_debug_internal (dinsn);
after setting INSN_VAR_LOCATION_LOC.  Maybe the debug insn in this case can be deleted?

(In reply to Alan Modra from comment #4)
> Created attachment 35342 [details]
> prototype patch
> 
> This seems to cure the testcase.  I haven't bootstrapped it, and it probably
> isn't ideal since I haven't poked at debug insns a lot..
> Still, it points out where the problem is, in move_insn_for_shrink_wrap.

Can't you use DF infrastructure for that (before actually moving the insn)?
I think pro_and_epilogue pass doesn't compute DF_DU_CHAINs, but perhaps something along the lines of DCE reset_unmarked_insns_debug_uses?
I.e. not perform it at all if !MAY_HAVE_DEBUG_INSNS, and use DF infrastructure to find out if the debug insn references the register.  Of course, unlike DCE, we aren't looking at debug instructions referencing unmarked insns, but debug instructions referencing a particular hard register.  Note that live_edge_for_reg is called multiple times and thus could move across more than one basic block, so perhaps you'd need to remember the sequence of basic blocks to scan during the
  /* At this point we are committed to moving INSN, but let's try to
     move it as far as we can.  */
loop.

GCC 5.1 has been released.

GCC 5.2 is being released, adjusting target milestone to 5.3.

(In reply to Jakub Jelinek from comment #6)
>> I.e. not perform it at all if !MAY_HAVE_DEBUG_INSNS, and use D

There are some regression test cases would check if the generated RTL are same with or without debug option enabled(like gcc.dg/pr45055.c), so if we perform optimization depend on if there is debug instructions, these test cases would fail. Will GCC community accept such patch with these regressions? I have a fix that could fix this issue but with regression on pr45055.c, so far I am hesitate if I can post it for review.

This is my fix for this issue, any comment is welcome.

---
10	 gcc/function.c |    5 +++--
11	 1 files changed, 3 insertions(+), 2 deletions(-)
12	 
13	diff --git a/gcc/function.c b/gcc/function.c
14	index 1a8682b..a9df397 100644
15	--- a/gcc/function.c
16	+++ b/gcc/function.c
17	@@ -5561,8 +5561,9 @@ prepare_shrink_wrap (basic_block entry_block)
18	   CLEAR_HARD_REG_SET (uses);
19	   CLEAR_HARD_REG_SET (defs);
20	   FOR_BB_INSNS_REVERSE_SAFE (entry_block, insn, curr)
21	-    if (NONDEBUG_INSN_P (insn)
22	-   && ​!move_insn_for_shrink_wrap (entry_block, insn, uses, defs))
23	+    if (INSN_P(insn) &&
24	+   (DEBUG_INSN_P (insn)
25	+    || ​!move_insn_for_shrink_wrap (entry_block, insn, uses, defs)))
26	       {
27	    /* Add all defined registers to DEFs.  */
28	    for (ref = DF_INSN_DEFS (insn); *ref; ref++)

I suspect this was fixed for GCC 6 with the patch that fixed bug 67789 (which is the more correct patch).

(In reply to Andrew Pinski from comment #11)
> I suspect this was fixed for GCC 6 with the patch that fixed bug 67789
> (which is the more correct patch).

I think they are two different issues. 67789 is duplicate label defined, this is undefined label.

Yes, not the same thing as PR67789.

GCC 5.3 is being released, adjusting target milestone.

Created attachment 37389 [details]
gcc6-pr65779.patch

Untested fix.

Author: jakub
Date: Tue Jan 19 13:21:04 2016
New Revision: 232558

URL: https://gcc.gnu.org/viewcvs?rev=232558&root=gcc&view=rev
Log:
	PR debug/65779
	* shrink-wrap.c: Include valtrack.h.
	(move_insn_for_shrink_wrap): Add DEBUG argument.  If
	MAY_HAVE_DEBUG_INSNS, call dead_debug_add on DEBUG_INSNs
	in between insn and where it will be moved to.  Call
	dead_debug_insert_temp.
	(prepare_shrink_wrap): Adjust caller.  Call dead_debug_local_init
	first and dead_debug_local_finish at the end.
	For uses and defs bitmap, handle all regs in between REGNO and
	END_REGNO, not just the first one.

	* gcc.dg/pr65779.c: New test.

Added:
    trunk/gcc/testsuite/gcc.dg/pr65779.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/shrink-wrap.c
    trunk/gcc/testsuite/ChangeLog

Fixed on the trunk so far.

(In reply to Jakub Jelinek from comment #17)
> Fixed on the trunk so far.

I can confirm that the originally reported problem is fixed by this change.  Works with 6.0.0 20160124, fails with 6.0.0 20160117.

Author: jakub
Date: Wed Feb 10 18:36:53 2016
New Revision: 233294

URL: https://gcc.gnu.org/viewcvs?rev=233294&root=gcc&view=rev
Log:
	Backported from mainline
	2016-01-19  Jakub Jelinek  <jakub@redhat.com>

	PR debug/65779
	* shrink-wrap.c: Include valtrack.h.
	(move_insn_for_shrink_wrap): Add DEBUG argument.  If
	MAY_HAVE_DEBUG_INSNS, call dead_debug_add on DEBUG_INSNs
	in between insn and where it will be moved to.  Call
	dead_debug_insert_temp.
	(prepare_shrink_wrap): Adjust caller.  Call dead_debug_local_init
	first and dead_debug_local_finish at the end.
	For uses and defs bitmap, handle all regs in between REGNO and
	END_REGNO, not just the first one.

	* gcc.dg/pr65779.c: New test.

Added:
    branches/gcc-5-branch/gcc/testsuite/gcc.dg/pr65779.c
Modified:
    branches/gcc-5-branch/gcc/ChangeLog
    branches/gcc-5-branch/gcc/shrink-wrap.c
    branches/gcc-5-branch/gcc/testsuite/ChangeLog

Fixed.