[AArch64] Enhance rematerialization by adding a new API isAsCheapAsAMove in TargetInstroInfo

[Jiangning]

Summary

This patch moves isAsCheapAsAMove to be a new API defined in TargetInstroInfo, so different targets could override it by customizing micro-architecture specific versions. For AArch64, this patch only adds cortex-a57 and cortex-a53 support so far. In LLVM, register coalesce pass is leveraging this API to help rematerialization.

With this patch applied, we would have some performance changes on cortex-a57. Below is running time change data

spec.cpu2000.ref.252_eon -1.26%
spec.cpu2000.ref.253_perlbmk -5.61%
spec.cpu2000.ref.254_gap 1.29%
eembc.automotive.cacheb01 1.82%
eembc.automotive.rspeed01 -5.44%
eembc.consumer.cjpeg -2.08%
eembc.telecom.conven00 -6.42%

Thanks,
-Jiangning

[qcolombet]

Hi Jiangning,

Thanks for working on this. That looks promising.

This is kind of strange that the patch introduces a target hook for isAsCheapAsMove, whereas it uses the flag isRematerializable to mark the interesting instructions.
Indeed, it seems kind of arbitrary which instructions are marked rematerializable and which instructions are not. If we want to pursue this way, I believe that we have to clarify the semantic of this flag.

The isRematerializable flag is also in a weird situation. Indeed, according to the documentation, it is deprecated:

/// isRematerializable - Returns true if this instruction is a candidate for
/// remat.  This flag is deprecated, please don't use it anymore.  If this
/// flag is set, the isReallyTriviallyReMaterializable() method is called to
/// verify the instruction is really rematable.

But it is used in TargetInstrInfo::isTriviallyRematerializable.

Since, you are touching this part, I believe that we should either fix the implementation of isTrivallyRematerializable and really deprecate this flag, or update the comment to reflect the actual semantic (which needs to be defined) of this flag.

Thanks,
-Quentin

lib/Target/AArch64/AArch64InstrInfo.cpp

564

Trying to rematerialize the S variant seems wrong to me. Those define the flags, so it is not safe to move them around.

Currently, it may not cause any problem as isTriviallyRematerializable checks that the instruction only defines one virtual register IIRC.
Anyway the logic looks wrong.

568

I believe that the shifter immediate is at index 3, not 2:
def0 = ADDXri arg1, imm2, shifter3

> Simply "return MI->getOperand(3).getImm() == 0;"?

BTW, is that test even correct from a performance perspective?
Indeed, in your example, you are rematerializing stack adjustments, but the value for stack adjustments is known way after register coalescing (which does the re-materialization in your case). Therefore, something that seems cheap, may not be cheap after all.

[Jiangning]

Hi Quentin,

Thanks for your review!

This is kind of strange that the patch introduces a target hook for
isAsCheapAsMove, whereas it uses the flag isRematerializable to mark the
interesting instructions.
Indeed, it seems kind of arbitrary which instructions are marked
rematerializable and which instructions are not. If we want to pursue this
way, I believe that we have to clarify the semantic of this flag.

The isRematerializable flag is also in a weird situation. Indeed,
according to the documentation, it is deprecated:

/// isRematerializable - Returns true if this instruction is a candidate

for

/// remat.  This flag is deprecated, please don't use it anymore.  If

this

/// flag is set, the isReallyTriviallyReMaterializable() method is

called to

/// verify the instruction is really rematable.

But it is used in TargetInstrInfo::isTriviallyRematerializable.

Since, you are touching this part, I believe that we should either fix the
implementation of isTrivallyRematerializable and really deprecate this
flag, or update the comment to reflect the actual semantic (which needs to
be defined) of this flag.

Sorry that I really didn't notice that this flag is deprecated. I can see
isReMaterializable flag is being used in a lot of .td files. Do you mean
because this flag is being used in an arbitrary manner everywhere, we want
to work out another more centralized solution to describe rematerializable
attribute? Or we needn't this flag at all, and the algorithm of
rematerialization should just check cost like the info provided by
isAsCheapAsMove?

Thanks,
-Jiangning

Thanks,
-Quentin

[qcolombet]

Sorry that I really didn't notice that this flag is deprecated.

Well at this point, I think the documentation is just wrong :).

Do you mean because this flag is being used in an arbitrary manner everywhere, we want to work out another more centralized solution to describe rematerializable attribute?

More or less. What I am saying is that we should either:

• Really deprecate this flag, and thus update the implement of isTriviallyRematerializable, e.g., isAsCheapAsMove or
• Update the comments to express what isRematerialize really means.

Indeed, in this patch, it is not clear to me why we choose to mark some instruction rematerializable and some others not (e.g., if add immediate is rematerializable, why mul immediate is not... the notion of cost seems relevant). But you are right, this may be something general.

Or we needn't this flag at all, and the algorithm of rematerialization should just check cost like the info provided by isAsCheapAsMove?

That might be a livable option. Honestly, I haven't thought a lot about that, it is just that this patch highlights two strange things: the use of isRematerializable flag, and its semantic.

What would you suggest?

Thanks,
-Quentin

[echristo]

Few inline comments.

lib/Target/AArch64/AArch64InstrInfo.cpp

544

Since this is ascii, just use the word "micro-architecture" :)

553

This should query the subtarget, not the target machine.

[Jiangning]

Hi Quentin,

Do you mean because this flag is being used in an arbitrary manner everywhere, we want to work out another more centralized solution to describe rematerializable attribute?

More or less. What I am saying is that we should either:

• Really deprecate this flag, and thus update the implement of isTriviallyRematerializable, e.g., isAsCheapAsMove or
• Update the comments to express what isRematerialize really means.

OK. I will update the comments of isRematerializable, and it looks much simpler than update the implement of isTriviallyRematerializable.
I tried to move the check of isAsCheapAsMove to be insde isReallyTriviallyReMaterializable(), but this semantic change obviously could introduce a lot of "make check-all" regressions. I think, even if we want to change this, it would be much better we do it separately.

Indeed, in this patch, it is not clear to me why we choose to mark some instruction rematerializable and some others not (e.g., if add immediate is rematerializable, why mul immediate is not... the notion of cost seems relevant). But you are right, this may be something general.

I see your point now. I admit the connection between isAsCheapAsMove interface and rematerizable is not very clear from this patch. The root cause is RegisterCoalescer pass has the following checks,

if (!TII->isAsCheapAsAMove(DefMI))
  return false;
if (!TII->isTriviallyReMaterializable(DefMI, AA))
  return false;

Yes, I simply mark the intrstuctions that could be as cheap as move with isRematerializable flag, and just because they have low cost for cortex-a57 and cortex-a53.

Actually we can add more instructions, but I only want to conservatively add those instructions in this patch at the moment. And then later, we can add more with performance data. In particular, I will try ADRP rematerializaiton here later on.

Or we needn't this flag at all, and the algorithm of rematerialization should just check cost like the info provided by isAsCheapAsMove?

That might be a livable option. Honestly, I haven't thought a lot about that, it is just that this patch highlights two strange things: the use of isRematerializable flag, and its semantic.

isTriviallyReMaterializable is being used in four back-end places at the moment.

• Live Range Analysis
• Machine LCIM
• Register Coalesce
• Calculate SpillWeights

In theory, I think we can make this change, but we need to carefully check those algorithms. isRematerializable depends on cost, so it is a micro-architecture dependent attribute. At this point, it seems not good to add them in xxxInstroxxx.td file, because those .td files describing instructions look more like a ISA level stuff.

Thanks,
-Jiangning

What would you suggest?

Thanks,
-Quentin

http://reviews.llvm.org/D4361

lib/Target/AArch64/AArch64InstrInfo.cpp

544

OK. I will fix that.

553

OK. I will fix that.

564

OK. I will remove them.

568

Ah! This is my mistake and I will fix that.

Yes. it's possible not cheap at all if the stack is huge.

I rerun the benchmark, and it seems I still can observe the running time of spec2000/perlbmk is reduced a lot.

[qcolombet]

Hi Jiangning,

Thanks for the updated version.

Inline a few comments.

Cheers,
-Quentin

include/llvm/Target/TargetInstrInfo.h

206

Like Eric said:
u-archs => microarchitectures

lib/Target/AArch64/AArch64InstrFormats.td

1615

Since we are overriding the behavior of isAsCheapAsMove, I think it would make sense to set the isAsCheapAsMove flag as well as the isRematerializable flag.

What do you think?

Also, we may want to check the uses of isAsCheapAsMove to see if we should "promote" them to the new target hook.

1681

I believe this is a remaining of the rematerialization of the S variants. This should be removed.

1954

Same here: Shouldn't be rematerializable.

2001

Ditto.

lib/Target/AArch64/AArch64InstrInfo.cpp

558

Simply: return MI->getOperand(3).getImm() == 0

[t.p.northover]

Just one comment on Quentin's comments:

lib/Target/AArch64/AArch64InstrFormats.td

1615

Careful if you do that, I don't think it is as cheap as a move on Cyclone.

[Jiangning]

Hi Quentin,

The issues you mentioned are all fixed except adding isAsCheapAsMove flag in .td file.

Thanks,
-Jiangning

include/llvm/Target/TargetInstrInfo.h

206

Fixed in new version.

lib/Target/AArch64/AArch64InstrFormats.td

1681

Removed in new version.

1954

Removed in new version.

2001

Removed in new version.

[qcolombet]

lib/Target/AArch64/AArch64InstrFormats.td

1615

Indeed!
That's why isAsCheapAsMove queries the subtarget to decide whether or not this is true.

If we go into the "promote" direction I was talking about, perhaps we should update the comment in MCDescInstr.h for isAsCheapAsMove to make the fact that this flag will be checked by the subtarget more obvious.

Jiangning, Tim, what do you think?

lib/Target/AArch64/AArch64InstrInfo.cpp

558

This if/else construction should be replaced by a simpler:
return MI->getOperand(3).getImm() == 0;

If you do not like this construction, you should at least remove the "else" to match LLVM guidelines.

[echristo]

You could also split the patch into adding the API and using it in the next commit. I.e. there's no reason why isRematerializable can't be set for the instructions separate from adding TII->isCheapAsAMove()

[Jiangning]

lib/Target/AArch64/AArch64InstrFormats.td

1615

OK. I can add one more sentence to highlight this.

lib/Target/AArch64/AArch64InstrInfo.cpp

558

OK. I will make the change.

[Jiangning]

Hi Eric,

OK. Attached are two separate patches.

Hi Qunentin,

I modified the code following your new comments.

Since I don't know how phabaricator will work for two patches uploaded, I'm
simply reply this mail by attached two separate patches. I don't want to
create a new review entry in phabaricator to confuse the people who want to
review the patch.

Thanks,
-Jiangning

2014-07-08 5:25 GMT+08:00 Eric Christopher <[e-mail]>:

You could also split the patch into adding the API and using it in the
next commit. I.e. there's no reason why isRematerializable can't be set for
the instructions separate from adding TII->isCheapAsAMove()

http://reviews.llvm.org/D4361

• 0001-Add-TargetInstrInfo-interface-isAsCheapAsAMove.patch3 KBDownload
• 0002-Implement-AArch64-TTI-interface-isAsCheapAsAMove.patch5 KBDownload

[qcolombet]

Hi Jiangning,

A few comments on the second patch (the first one looks good).

+ FIXME: this implementation should be micro-architecture dependent, so a
+ micro-architecture target hook should be introduced here in future.
+bool AArch64InstrInfo::isAsCheapAsAMove(const MachineInstr *MI) const {
+ if (Subtarget.isCortexA57() || Subtarget.isCortexA53()) {
+ switch (MI->getOpcode()) {
+ default:
+ return false;
[…]
+ }
+
+ return MI->isAsCheapAsAMove();
+}
+

To match LLVM guidelines, use an early exit when the subtarget does not match:
if (!Subtarget.isCortexA57() && !Subtarget.isCortexA53())

return MI->isAsCheapAsAMove();

switch (MI->getOpcode()) {
[…]

+ case AArch64::ANDSWri:
+ case AArch64::ANDSXri:

I believe this is a remaining of the initial patch. The S variant are not rematerializable.

Thanks,
-Quentin

[echristo]

Hi Quentin, Jiangning,

I'm not sure about this patch (though I love the results!) -

It looks like we're just conflating isRematerializable and
isAsCheapAsAMove, especially in the somewhat random addition of
isRematerializable to some of the instructions and then adding the
rest to isAsCheapAsAMove (and are they universally cheap or is it
really subtarget dependent here?) and I haven't really seen an answer
to Quentin's question about that? Are these actually rematerializable
or is it just cheaper/etc?

Thanks!

-eric

[Jiangning]

Hi Eric,

It looks like we're just conflating isRematerializable and

isAsCheapAsAMove, especially in the somewhat random addition of
isRematerializable to some of the instructions and then adding the
rest to isAsCheapAsAMove (and are they universally cheap or is it
really subtarget dependent here?) and I haven't really seen an answer
to Quentin's question about that? Are these actually rematerializable
or is it just cheaper/etc?

I think I answered this question previously. RegisterCoalescer pass has

the following checks,

if (!TII->isAsCheapAsAMove(DefMI))
  return false;
if (!TII->isTriviallyReMaterializable(DefMI, AA))
  return false;

They are cheap, so they are rematerializable.

isAsCheapAsAMove is overridden to make sure those instructions are cheap as
move.
isTriviallyReMaterializable is check if they are rematerializable, so
isRematerializable flag is added in .td file.

"I tried to move the check of isAsCheapAsMove to be insde
isReallyTriviallyReMaterializable(), but this semantic change obviously
could introduce a lot of "make check-all" regressions. I think, even if we
want to change this, it would be much better we do it separately."

Thanks,
-Jiangning

Thanks!

-eric

http://reviews.llvm.org/D4361

[Jiangning]

Hi Quentin,

Updated with the latest comments.

BTW, for instructions updating NCZV flags, actually I think it still make
sense to mark them as rematerializable. Essentially the algorithm of
rematerialization should take care of the final decision. For example, an
adds instruction can still be rematerialized if only the flag is not really
used by any instruction at all on control flow, or the flag may be
overridden by another adds instruction. But I think it's OK to do it
conservatively at this moment, so I agree to remove all instructions
updating flags.

Thanks,
-Jiangning

2014-07-09 22:28 GMT+08:00 Quentin Colombet <[e-mail]>:

Hi Jiangning,

A few comments on the second patch (the first one looks good).

+ FIXME: this implementation should be micro-architecture dependent, so a
+ micro-architecture target hook should be introduced here in future.
+bool AArch64InstrInfo::isAsCheapAsAMove(const MachineInstr *MI) const {
+ if (Subtarget.isCortexA57() || Subtarget.isCortexA53()) {
+ switch (MI->getOpcode()) {
+ default:
+ return false;
[…]
+ }
+
+ return MI->isAsCheapAsAMove();
+}
+

To match LLVM guidelines, use an early exit when the subtarget does not
match:
if (!Subtarget.isCortexA57() && !Subtarget.isCortexA53())

return MI->isAsCheapAsAMove();

switch (MI->getOpcode()) {
[…]

+ case AArch64::ANDSWri:
+ case AArch64::ANDSXri:

I believe this is a remaining of the initial patch. The S variant are not
rematerializable.

Thanks,
-Quentin

http://reviews.llvm.org/D4361

• 0002-Implement-AArch64-TTI-interface-isAsCheapAsAMove.patch5 KBDownload

[qcolombet]

Hi Jiangning,

The patch looks good with one nitpick however, I think we need a bit more discussion before we commit both patches.

First the nitpick:
+ case AArch64::ORNWrr:
+ case AArch64::ORNXrr:
+ case AArch64::ORRWrr:
+ case AArch64::ORRXrr:
+ return true;
+ }
// <— use llvm_unreachable here, just to make sure we do not miss that when updating the code.
+}

Going back to the concern that we are conflating isRematerializable and isAsCheapAsAMove, I can see why we want to keep both. That said, I still think that if we are overriding isAsCheapAsMove with this new hook for isRematerializable instructions, those instructions should be marked as isAsCheapAsMove too.

This means two things:

1. All the uses of MachineInstr::isAsCheapAsMove should be promoted to use of TargetInstrInfo::isAsCheapAsMove.
2. If an instruction is rematerializable but not as cheap as move, then it shouldn’t appear in the isAsCheapAsMove target hook.

If you have an instruction matching #2 and still want to make it appear in TargetInstrInfo::isAsCheapAsMove, it means you are trying to abuse the register coalescer to do rematerialization and that’s probably not the right solution.

What do you think?

Cheers,
-Quentin

include/llvm/CodeGen/MachineInstr.h

   /// are not marking copies from and to the same register class with this flag.
   bool isAsCheapAsAMove(QueryType Type = AllInBundle) const {
     // Only returns true for a bundle if all bundled instructions are cheap.
-    // FIXME: This probably requires a target hook.
     return hasProperty(MCID::CheapAsAMove, Type);
   }
 

include/llvm/MC/MCInstrDesc.h

   }
 
   /// isRematerializable - Returns true if this instruction is a candidate for
-  /// remat.  This flag is deprecated, please don't use it anymore.  If this
-  /// flag is set, the isReallyTriviallyReMaterializable() method is called to
-  /// verify the instruction is really rematable.
+  /// remat. This flag is only used in TargetInstrInfo method
+  /// isTriviallyRematerializable.
+  ///
+  /// If this flag is set, the isReallyTriviallyReMaterializable()
+  /// or isReallyTriviallyReMaterializableGeneric methods are called to verify
+  /// the instruction is really rematable.
   bool isRematerializable() const {
     return Flags & (1 << MCID::Rematerializable);
   }

include/llvm/Target/TargetInstrInfo.h

                                  unsigned &Size, unsigned &Offset,
                                  const TargetMachine *TM) const;
 
+  /// isAsCheapAsAMove - Return true if the instruction is as cheap as a move
+  /// instruction.
+  ///
+  /// Targets for different archs need to override this, and different
+  /// micro-architectures can also be finely tuned inside.
+  virtual bool isAsCheapAsAMove(const MachineInstr *MI) const {
+    return MI->isAsCheapAsAMove();
+  }
+
   /// reMaterialize - Re-issue the specified 'original' instruction at the
   /// specific location targeting a new destination register.
   /// The register in Orig->getOperand(0).getReg() will be substituted by

lib/CodeGen/RegisterCoalescer.cpp

     IsDefCopy = true;
     return false;
   }
-  if (!DefMI->isAsCheapAsAMove())
+  if (!TII->isAsCheapAsAMove(DefMI))
     return false;
   if (!TII->isTriviallyReMaterializable(DefMI, AA))
     return false;

lib/Target/AArch64/AArch64InstrFormats.td

 
 multiclass AddSub<bit isSub, string mnemonic,
                   SDPatternOperator OpNode = null_frag> {
-  let hasSideEffects = 0 in {
+  let hasSideEffects = 0, isReMaterializable = 1 in {
   // Add/Subtract immediate
   def Wri  : BaseAddSubImm<isSub, 0, GPR32sp, GPR32sp, addsub_shifted_imm32,
                            mnemonic, OpNode> {

     : InstAlias<asm#" $dst, $src1, $src2",
                 (inst regtype:$dst, regtype:$src1, regtype:$src2, 0)>;
 
-let AddedComplexity = 6 in
+let AddedComplexity = 6, isReMaterializable = 1 in
 multiclass LogicalImm<bits<2> opc, string mnemonic, SDNode OpNode> {
   def Wri : BaseLogicalImm<opc, GPR32sp, GPR32, logical_imm32, mnemonic,
                            [(set GPR32sp:$Rd, (OpNode GPR32:$Rn,

 // Split from LogicalImm as not all instructions have both.
 multiclass LogicalReg<bits<2> opc, bit N, string mnemonic,
                       SDPatternOperator OpNode> {
+  let isReMaterializable = 1 in {
   def Wrr : BaseLogicalRegPseudo<GPR32, OpNode>;
   def Xrr : BaseLogicalRegPseudo<GPR64, OpNode>;
+  }
 
   def Wrs : BaseLogicalSReg<opc, N, GPR32, logical_shifted_reg32, mnemonic,
                             [(set GPR32:$Rd, (OpNode GPR32:$Rn,

lib/Target/AArch64/AArch64InstrInfo.h

 
   unsigned GetInstSizeInBytes(const MachineInstr *MI) const;
 
+  bool isAsCheapAsAMove(const MachineInstr *MI) const override;
+
   bool isCoalescableExtInstr(const MachineInstr &MI, unsigned &SrcReg,
                              unsigned &DstReg, unsigned &SubIdx) const override;
 

lib/Target/AArch64/AArch64InstrInfo.cpp

       CC);
 }
 
+// FIXME: this implementation should be micro-architecture dependent, so a
+// micro-architecture target hook should be introduced here in future.
+bool AArch64InstrInfo::isAsCheapAsAMove(const MachineInstr *MI) const {
+  if (Subtarget.isCortexA57() || Subtarget.isCortexA53()) {
+    switch (MI->getOpcode()) {
+    default:
+      return false;
+
+    // add/sub on register without shift
+    case AArch64::ADDWri:
+    case AArch64::ADDXri:
+    case AArch64::SUBWri:
+    case AArch64::SUBXri:
+      if (MI->getOperand(3).getImm() != 0)
+        return false;
+      else
+        return true;
+
+    // logical ops on immediate
+    case AArch64::ANDSWri:
+    case AArch64::ANDSXri:
+    case AArch64::ANDWri:
+    case AArch64::ANDXri:
+    case AArch64::EORWri:
+    case AArch64::EORXri:
+    case AArch64::ORRWri:
+    case AArch64::ORRXri:
+      return true;
+
+    // logical ops on register without shift
+    case AArch64::ANDWrr:
+    case AArch64::ANDXrr:
+    case AArch64::BICWrr:
+    case AArch64::BICXrr:
+    case AArch64::EONWrr:
+    case AArch64::EONXrr:
+    case AArch64::EORWrr:
+    case AArch64::EORXrr:
+    case AArch64::ORNWrr:
+    case AArch64::ORNXrr:
+    case AArch64::ORRWrr:
+    case AArch64::ORRXrr:
+      return true;
+    }
+  }
+
+  return MI->isAsCheapAsAMove();
+}
+
 bool AArch64InstrInfo::isCoalescableExtInstr(const MachineInstr &MI,
                                              unsigned &SrcReg, unsigned &DstReg,
                                              unsigned &SubIdx) const {

lib/Target/AArch64/AArch64Subtarget.h

   bool isTargetMachO() const { return TargetTriple.isOSBinFormatMachO(); }
 
   bool isCyclone() const { return CPUString == "cyclone"; }
+  bool isCortexA57() const { return CPUString == "cortex-a57"; }
+  bool isCortexA53() const { return CPUString == "cortex-a53"; }
 
   /// getMaxInlineSizeThreshold - Returns the maximum memset / memcpy size
   /// that still makes it profitable to inline the call.

test/CodeGen/AArch64/remat.ll

+; RUN: llc -mtriple=aarch64-linux-gnuabi -mcpu=cortex-a57 -o - %s | FileCheck %s
+; RUN: llc -mtriple=aarch64-linux-gnuabi -mcpu=cortex-a53 -o - %s | FileCheck %s
+
+%X = type { i64, i64, i64 }
+declare void @f(%X*)
+define void @t() {
+entry:
+  %tmp = alloca %X
+  call void @f(%X* %tmp)
+; CHECK: add x0, sp, #8
+; CHECK-NEXT-NOT: mov
+  call void @f(%X* %tmp)               
+; CHECK: add x0, sp, #8
+; CHECK-NEXT-NOT: mov
+  ret void 
+}