Allowing MC backends to decide relaxation based on fixup resolution

[colinl]

Summary

Currently, a failure to resolve a fixup implies instruction relaxation; this policy may not be correct on some targets.

MCAssembler::fixupNeedsRelaxation()

if (!evaluateFixup(Layout, Fixup, DF, Target, Value)) <-- Fixup failed to resolve
  return true; <-- This fixup needs relaxation

In Hexagon, failing to resolve a fixup does not imply relaxation in all cases.

This change adds a parameter to MCAsmBackend::fixupNeedsRelaxation() indicating whether the fixup was resolved and allows the backend to make the full relaxation decision.

Backends that do not use relaxation only have their function signatures changed.

[colinl]

Ping.

[• rafael]

Can you provide examples of when this is needed?

In particular, if a fixup cannot be resolved, the value can be
anything and we need to relax the code to make sure it fits, no?

[colinl]

Sure. The constraints we have on Hexagon are instructions are always 32bit words and there's a limit of 4 words per instruction packet. Extending calls and jumps requires adding an additional 32bit word which increases image size and decreases instructions per packet.

The alternate we sometimes use is letting the linker generate a trampoline which saves 1/2 the instruction size for every call site at the expense of an indirection.

For our 22bit jumps we never extend and for our 7, 9, 13, and 15bit jumps we extend if there's space in the packet. We've brainstormed some new and interesting ways to put some more smarts in to this process in the future but this heuristic has worked fairly well so far.

[grosbach]

I don't follow. From your description, it's still true that a fixup won't need relaxation if it's already been resolved. It's only if it hasn't that you need to ask more questions to decide what to do. That is exactly what information the code currently provides to the backend. That is, the AsmBacked::fixupNeedsRelaxation() is only called if the fixup was not resolved. You can still decide how much relaxation to do (or not do) however you want.

[colinl]

Correct, the case I'm trying to allow is where it's not resolved but we do not want to relax.

[grosbach]

Then why do you need this patch? If AsmBackend::fixupNeedsRelaxation() function is called, you know the fixup has not been resolved. Perhaps we just need to clarify the documentation of that interface to make that explicit?

[colinl]

On the lines:

if (!evaluateFixup(Layout, Fixup, DF, Target, Value))

return true; <-- I don't always want to relax

It seems like if the fixup does not evaluate, we must relax. I'm not seeing a way to signal do not relax if !evaluateFixup.

[colinl]

In D8217#144209, @grosbach wrote:

If AsmBackend::fixupNeedsRelaxation() function is called, you know the fixup has not been resolved.

This is the inverse. MCAsmBackend::fixupNeedsRelaxation is called if the fixup has been resolved i.e. `Value' has meaning.

[grosbach]

Ah, right. I see what you're saying now.

So, the concern I have here is that because some targets have more complicated relaxation decisions to make, all targets need to have additional logic inserted into their backend hooks. It's simple logic "if (!Resolved) return true;" but if it's not there, things will go badly wrong. That is, this approach complicates the interface for every target in order to support a subset. That's suboptimal.

Instead, have you considered making the logic in relaxInstruction() smarter? It's unconditional right now, but what if that were changed so that AsmBackend::relaxInstruction() so that it can cleanly choose to do nothing. What it's really for is to say to the backend, "do whatever you need to do here for an instruction that we can't statically determine the optimal size for." If we do that, everything for current targets stays the same (possibly modulo adding a constant return value to their relaxInstruction() implementations depending on implementation details). The complexity for handling more options will go in the target independent code in MCAssembler::relaxInstruction() and in the targets themselves that need the additional logic. MCAssembler::relaxInstruction()'s caller MCAssembler::layoutSectionOnce() is already set up to handle things correctly if relaxInstruction() doesn't actually make any changes.

[colinl]

I'm definitely open to cleaner implementations.

The issue with not doing anything in relaxInstruction() is relaxation will get stuck in an infinite loop. The relaxation loop assumes that relaxInstruction will eventually change fixupNeedsRelaxation or mayNeedRelaxation to false.

[grosbach]

In D8217#144272, @colinl wrote:

I'm definitely open to cleaner implementations.

The issue with not doing anything in relaxInstruction() is relaxation will get stuck in an infinite loop. The relaxation loop assumes that relaxInstruction will eventually change fixupNeedsRelaxation or mayNeedRelaxation to false.

Yeah, we'll likely need to do something there. My inclination is do something with the target-specific fixups. Perhaps use a different fixup kind which isn't relaxable?

[colinl]

In D8217#146472, @grosbach wrote:

In D8217#144272, @colinl wrote:

I'm definitely open to cleaner implementations.

The issue with not doing anything in relaxInstruction() is relaxation will get stuck in an infinite loop. The relaxation loop assumes that relaxInstruction will eventually change fixupNeedsRelaxation or mayNeedRelaxation to false.

Yeah, we'll likely need to do something there. My inclination is do something with the target-specific fixups. Perhaps use a different fixup kind which isn't relaxable?

That's a possibility I hadn't considered before. One concern is we wouldn't want to lose the target specific MCFixupKind so it seems like it would have to be a flag instead of a new enumeration.

One method I thought of instead of using a bool flag would simply be to pass is a maximum for Value when calling Backend::fixupNeedsRelaxation. Conceptually this is what we're saying anyway, we don't know where this value is so it could be anywhere up to the maximum value away.

If we were to pass in some maximum value we'd have to consider if it's going to me max int64_t or max uint64_t. During evaluateFixup it looks like the first place Value is assigned is from an int64_t and later some unsigned offsets get added but the whole value is converted to an uint64_t but what we're really expressing is a signed displacement.

Another way I didn't care for as much was having Backend::relaxInstruction return whether it relaxed the instruction. This would still have the drawbacks of requiring all backends to change their interface and it's weird that fixupNeedsRelaxation would return true but relaxInstruction would say something different.

[• rafael]

If the issue is just having to change every backend, you could use a
solution with two virtual functions:

virtual bool simpleFixupNeedsRelaxation(const MCFixup &Fixup,

uint64_t Value,
const MCRelaxableFragment *DF,
const MCAsmLayout &Layout) const = 0;

virtual bool fixupNeedsRelaxation(const MCFixup &Fixup, bool Resolved,

uint64_t Value,
const MCRelaxableFragment *DF,
const MCAsmLayout &Layout) const {

if(!Resolved)

  return true;

return simpleFixupNeedsRelaxation(Fixup, Value, DF, Layout);

}

That way Hexagon overrides fixupNeedsRelaxation and other targets
override simpleFixupNeedsRelaxation.

[colinl]

I like the new virtual function suggestion, it makes this patch far easier.

llvm/trunk/include/llvm/MC/MCAsmBackend.h

public:
 
   /// Check whether the given instruction may need relaxation.
   ///
   /// \param Inst - The instruction to test.
   virtual bool mayNeedRelaxation(const MCInst &Inst) const = 0;
 
   /// Target specific predicate for whether a given fixup requires the
   /// associated instruction to be relaxed.
+  virtual bool fixupNeedsRelaxationAdvanced(const MCFixup &Fixup, bool Resolved,
+                                            uint64_t Value,
+                                            const MCRelaxableFragment *DF,
+                                            const MCAsmLayout &Layout) const;
+
+  /// Simple predicate for targets where !Resolved implies requiring relaxation
   virtual bool fixupNeedsRelaxation(const MCFixup &Fixup, uint64_t Value,
                                     const MCRelaxableFragment *DF,
                                     const MCAsmLayout &Layout) const = 0;
 
   /// Relax the instruction in the given fragment to the next wider instruction.
   ///
   /// \param Inst The instruction to relax, which may be the same as the
   /// output.

llvm/trunk/lib/MC/MCAsmBackend.cpp

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/MC/MCFixupKindInfo.h"
 using namespace llvm;
 
 MCAsmBackend::MCAsmBackend() : HasDataInCodeSupport(false) {}
 
 MCAsmBackend::~MCAsmBackend() {}
 
-const MCFixupKindInfo &
-MCAsmBackend::getFixupKindInfo(MCFixupKind Kind) const {
+const MCFixupKindInfo &MCAsmBackend::getFixupKindInfo(MCFixupKind Kind) const {
   static const MCFixupKindInfo Builtins[] = {
-    { "FK_Data_1",  0,  8, 0 },
-    { "FK_Data_2",  0, 16, 0 },
-    { "FK_Data_4",  0, 32, 0 },
-    { "FK_Data_8",  0, 64, 0 },
-    { "FK_PCRel_1", 0,  8, MCFixupKindInfo::FKF_IsPCRel },
-    { "FK_PCRel_2", 0, 16, MCFixupKindInfo::FKF_IsPCRel },
-    { "FK_PCRel_4", 0, 32, MCFixupKindInfo::FKF_IsPCRel },
-    { "FK_PCRel_8", 0, 64, MCFixupKindInfo::FKF_IsPCRel },
-    { "FK_GPRel_1", 0,  8, 0 },
-    { "FK_GPRel_2", 0, 16, 0 },
-    { "FK_GPRel_4", 0, 32, 0 },
-    { "FK_GPRel_8", 0, 64, 0 },
-    { "FK_SecRel_1", 0,  8, 0 },
-    { "FK_SecRel_2", 0, 16, 0 },
-    { "FK_SecRel_4", 0, 32, 0 },
-    { "FK_SecRel_8", 0, 64, 0 }
-  };
+      {"FK_Data_1", 0, 8, 0},
+      {"FK_Data_2", 0, 16, 0},
+      {"FK_Data_4", 0, 32, 0},
+      {"FK_Data_8", 0, 64, 0},
+      {"FK_PCRel_1", 0, 8, MCFixupKindInfo::FKF_IsPCRel},
+      {"FK_PCRel_2", 0, 16, MCFixupKindInfo::FKF_IsPCRel},
+      {"FK_PCRel_4", 0, 32, MCFixupKindInfo::FKF_IsPCRel},
+      {"FK_PCRel_8", 0, 64, MCFixupKindInfo::FKF_IsPCRel},
+      {"FK_GPRel_1", 0, 8, 0},
+      {"FK_GPRel_2", 0, 16, 0},
+      {"FK_GPRel_4", 0, 32, 0},
+      {"FK_GPRel_8", 0, 64, 0},
+      {"FK_SecRel_1", 0, 8, 0},
+      {"FK_SecRel_2", 0, 16, 0},
+      {"FK_SecRel_4", 0, 32, 0},
+      {"FK_SecRel_8", 0, 64, 0}};
 
   assert((size_t)Kind <= array_lengthof(Builtins) && "Unknown fixup kind");
   return Builtins[Kind];
 }
+
+bool MCAsmBackend::fixupNeedsRelaxationAdvanced(
+    const MCFixup &Fixup, bool Resolved, uint64_t Value,
+    const MCRelaxableFragment *DF, const MCAsmLayout &Layout) const {
+  if (!Resolved)
+    return true;
+  return fixupNeedsRelaxation(Fixup, Value, DF, Layout);
+}

llvm/trunk/lib/MC/MCAssembler.cpp

void MCAssembler::Finish() {
   getWriter().WriteObject(*this, Layout);
 
   stats::ObjectBytes += OS.tell() - StartOffset;
 }
 
 bool MCAssembler::fixupNeedsRelaxation(const MCFixup &Fixup,
                                        const MCRelaxableFragment *DF,
                                        const MCAsmLayout &Layout) const {
-  // If we cannot resolve the fixup value, it requires relaxation.
   MCValue Target;
   uint64_t Value;
-  if (!evaluateFixup(Layout, Fixup, DF, Target, Value))
-    return true;
-
-  return getBackend().fixupNeedsRelaxation(Fixup, Value, DF, Layout);
+  bool Resolved = evaluateFixup(Layout, Fixup, DF, Target, Value);
+  return getBackend().fixupNeedsRelaxationAdvanced(Fixup, Resolved, Value, DF,
+                                                   Layout);
 }
 
 bool MCAssembler::fragmentNeedsRelaxation(const MCRelaxableFragment *F,
                                           const MCAsmLayout &Layout) const {
   // If this inst doesn't ever need relaxation, ignore it. This occurs when we
   // are intentionally pushing out inst fragments, or because we relaxed a
   // previous instruction to one that doesn't need relaxation.
   if (!getBackend().mayNeedRelaxation(F->getInst()))