This is a complete mess, what aarch64 backend does is completely incompatible with optimize attribute.  I've tried to fix this up:
--- gcc/config/aarch64/aarch64.opt.jj	2014-01-20 14:50:22.000000000 +0100
+++ gcc/config/aarch64/aarch64.opt	2014-03-19 11:52:29.963772607 +0100
@@ -59,6 +59,11 @@ const char *aarch64_cpu_string
 Variable
 const char *aarch64_tune_string
 
+; Did we set flag_omit_frame_pointer just so aarch64_frame_pointer_required
+; would be called?
+Variable
+bool faked_omit_frame_pointer
+
 mbig-endian
 Target Report RejectNegative Mask(BIG_END)
 Assume target CPU is configured as big endian
--- gcc/config/aarch64/aarch64.c.jj	2014-03-18 12:26:13.000000000 +0100
+++ gcc/config/aarch64/aarch64.c	2014-03-19 12:20:19.471504562 +0100
@@ -315,10 +315,6 @@ static GTY(()) int gty_dummy;
 #define AARCH64_NUM_BITMASKS  5334
 static unsigned HOST_WIDE_INT aarch64_bitmasks[AARCH64_NUM_BITMASKS];
 
-/* Did we set flag_omit_frame_pointer just so
-   aarch64_frame_pointer_required would be called? */
-static bool faked_omit_frame_pointer;
-
 typedef enum aarch64_cond_code
 {
   AARCH64_EQ = 0, AARCH64_NE, AARCH64_CS, AARCH64_CC, AARCH64_MI, AARCH64_PL,
@@ -5278,7 +5274,11 @@ aarch64_override_options (void)
 static void
 aarch64_override_options_after_change (void)
 {
-  faked_omit_frame_pointer = false;
+  if (global_options_set.x_flag_omit_frame_pointer)
+    {
+      faked_omit_frame_pointer = false;
+      global_options_set.x_faked_omit_frame_pointer = false;
+    }
 
   /* To omit leaf frame pointers, we need to turn flag_omit_frame_pointer on so
      that aarch64_frame_pointer_required will be called.  We need to remember
@@ -5288,6 +5288,9 @@ aarch64_override_options_after_change (v
     {
       flag_omit_frame_pointer = true;
       faked_omit_frame_pointer = true;
+      global_options_set.x_faked_omit_frame_pointer
+	= global_options_set.x_flag_omit_frame_pointer;
+      global_options_set.x_flag_omit_frame_pointer = false;
     }
 }
 
but while that fixes some of the cases, it doesn't fix everything, the problem is that the non-TargetVariable Variables aren't actually Saved.

Now, i386 backend seems to handle it differently, instead of adding a faked_omit_frame_pointer variable (which, as this PR suggests would need to be handled as an Optimization Saved variable, but supposedly the opts framework doesn't allow it yet), it clears omit_leaf_frame_pointer flag if flag_omit_frame_pointer is true:
  /* Keep nonleaf frame pointers.  */
  if (opts->x_flag_omit_frame_pointer)
    opts->x_target_flags &= ~MASK_OMIT_LEAF_FRAME_POINTER;
  else if (TARGET_OMIT_LEAF_FRAME_POINTER_P (opts->x_target_flags))
    opts->x_flag_omit_frame_pointer = 1;
but does that only in in override_options hook.  That means that
say for -fomit-frame-pointer -momit-leaf-frame-pointer on the command line
supposedly that turns off TARGET_OMIT_LEAF_FRAME_POINTER and when some function
has __attribute__((optimize ("no-omit-frame-pointer"))) and is leaf, frame pointer will not be omitted there.  But for -fno-omit-frame-pointer -momit-leaf-frame-pointer on the command line and __attribute__((optimize ("no-omit-frame-pointer"))) supposedly it will not have frame pointer if it is leaf.
The primary issue is that flag_omit_frame_pointer is Optimization Save flag,
while omit-leaf-frame-pointer is typcially Target Save, the former optimize attribute thing, the latter target attribute thing.

Not sure what is the best way out of this, but I guess doing in aarch64 what i386 does would be significant progress.

I think following what i386 does is reasonable for now.

I'm a bit dubious of the whole Save design - logically it would be cleaner 
if the gcc_options structures were saved just before finish_options, and 
then use of option-changing attributes were to process options with a copy 
of that structure (if this hadn't already been done for that particular 
attribute value), with finish_options and subsequent processing then being 
done for the new copy.  But that would be quite a lot of work, to complete 
a clean separation of option processing working on such structures from 
options processing that actually needs global effects, and then you'd need 
to work out how to represent things for LTO.

I'm not going to hack on this any time soon, so if aarch64 maintainers could take it over, it would be appreciated.

Confirmed.

Patch applied to trunk r208862

Marcus, can this be closed off?

I'd take this for long term, hopefully could find a acceptable solution.

X86 is default with -fomit-frame-pointer which makes the logic a little bit simpler, and thus X86 could survive in more normal case, but still fail in some corner cases.

the fundamental problem is aarch64 and also x86 want to implement a finer control of frame pointer which let leaf function be possible without setting up frame record even under -fno-omit-frame-pointer. While gcc generic code is not aware of that.

(In reply to Jiong Wang from comment #7)
> I'd take this for long term, hopefully could find a acceptable solution.
> 
> X86 is default with -fomit-frame-pointer which makes the logic a little bit
> simpler, and thus X86 could survive in more normal case, but still fail in
> some corner cases.
> 
> the fundamental problem is aarch64 and also x86 want to implement a finer
> control of frame pointer which let leaf function be possible without setting
> up frame record even under -fno-omit-frame-pointer. While gcc generic code
> is not aware of that.

Besides the solutions we discussed on the list to fix the underlying issues in the mid-end, a workaround may be possible in the backend. If we can guarantee a callback is made to the backend at the end of compilation of each function, then we can restore the original value of the omit-frame-pointer variable. This means the options code will never see the fake value, and attributes will work as expected.

In principle any callback would work as long as the frame pointer variable is not used for that function again, and it happens before entering the options code again.

Obviously this is a nasty hack, but at least it works.

Author: wilco
Date: Tue Oct 24 16:58:02 2017
New Revision: 254052

URL: https://gcc.gnu.org/viewcvs?rev=254052&root=gcc&view=rev
Log:
PR60580: Fix frame pointer option magic

To fix PR60580 simplify the logic in aarch64_override_options_after_change_1 (). 
If the frame pointer is enabled, set it to a special value that behaves similar
to frame pointer omission.  If we don't do this all leaf functions will get a
frame pointer even if flag_omit_leaf_frame_pointer is set.

If flag_omit_frame_pointer has this special value, we must force the frame
pointer if not in a leaf function.  We also need to force it in a leaf function
if flag_omit_frame_pointer is not set or if LR is used.

Doing this allows both -fomit-frame-pointer and -fomit-leaf-frame-pointer to be
independently set and changed in each function with the expected behaviour.

    gcc/
	PR middle-end/60580
	* config/aarch64/aarch64.c (aarch64_frame_pointer_required)
	Check special value of flag_omit_frame_pointer.
	(aarch64_can_eliminate): Likewise.
	(aarch64_override_options_after_change_1): Simplify handling of
	-fomit-frame-pointer and -fomit-leaf-frame-pointer.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/config/aarch64/aarch64.c

Author: wilco
Date: Fri Nov  3 15:01:10 2017
New Revision: 254377

URL: https://gcc.gnu.org/viewcvs?rev=254377&root=gcc&view=rev
Log:
PR60580: Fix frame pointer option magic

To fix PR60580 simplify the logic in aarch64_override_options_after_change_1 (). 
If the frame pointer is enabled, set it to a special value that behaves similar
to frame pointer omission.  If we don't do this all leaf functions will get a
frame pointer even if flag_omit_leaf_frame_pointer is set.

If flag_omit_frame_pointer has this special value, we must force the frame
pointer if not in a leaf function.  We also need to force it in a leaf function
if flag_omit_frame_pointer is not set or if LR is used.

Doing this allows both -fomit-frame-pointer and -fomit-leaf-frame-pointer to be
independently set and changed in each function with the expected behaviour.

    gcc/
	PR middle-end/60580
	* config/aarch64/aarch64.c (aarch64_frame_pointer_required)
	Check special value of flag_omit_frame_pointer.
	(aarch64_can_eliminate): Likewise.
	(aarch64_override_options_after_change_1): Simplify handling of
	-fomit-frame-pointer and -fomit-leaf-frame-pointer.

Modified:
    branches/gcc-7-branch/gcc/ChangeLog
    branches/gcc-7-branch/gcc/config/aarch64/aarch64.c

Fixed from 7.2 onwards - I've verified the failing cases now work. Backporting to earlier versions seems too risky so close as fixed (generated code is correct in all cases).