[GISel]: ConstantFold operations when building MIR

[aditya_nandakumar]

Summary

Initial implementation.
Based on feedback, I'll add support for FPConstants.

[Gerolf]

Thanks for working on this! Please add comments and show off one or two examples that highlight the benefits of your extensions.

Cheers
Gerolf

[aditya_nandakumar]

This is helpful in cases where you try to build a generic operation on a constant.
For e.g.,
vreg1(s16) = G_CONSTANT 0
Builder.buildZExt(s32, vreg1) would result in
vreg1(s16) = G_CONSTANT 0
vreg2(s16) = G_ZEXT vreg1

Instead - we can constant fold operations and instead generate
vreg2(s32) = G_CONSTANT i32 0

Similarly we can constant fold binary operations such as Add/sub/or/and/xor/mul.

We also can constant fold intrinsics FABS/FLOG... (constant) -> constant.

[aditya_nandakumar]

Ping?

[dsanders]

Could you run clang-format on this patch? There's a few indentation and style nits in this patch. There's also a few in the neighbouring code which we should deal with separately

Similarly we can constant fold binary operations such as Add/sub/or/and/xor/mul.

I don't see XOR in this patch

In D35594#813925, @Gerolf wrote:

Thanks for working on this! Please add comments and show off one or two examples that highlight the benefits of your extensions.

Cheers
Gerolf

! In D35594#814884, @aditya_nandakumar wrote:

This is helpful in cases where you try to build a generic operation on a constant.
For e.g.,
vreg1(s16) = G_CONSTANT 0
Builder.buildZExt(s32, vreg1) would result in
vreg1(s16) = G_CONSTANT 0
vreg2(s16) = G_ZEXT vreg1

Instead - we can constant fold operations and instead generate
vreg2(s32) = G_CONSTANT i32 0

Similarly we can constant fold binary operations such as Add/sub/or/and/xor/mul.

We also can constant fold intrinsics FABS/FLOG... (constant) -> constant.

I think Gerolf intended the comments and examples to be added to the patch itself.

In my opinion, the main thing this patch is missing is the test case. Is it possible to extend one (preferably a few) of the select-*.mir tests to cover a constant folding case?

include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h

81–87

This will need refreshing to account for the updates to one of your other patches.

lib/CodeGen/GlobalISel/MachineIRBuilder.cpp

184–185

XOR seems to be missing

[aditya_nandakumar]

I can try changing one of IRTranslator's build methods to use this API instead and then I should be able to write a test case.

include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h

81–87

This is not needed anymore. The other patch went in.

lib/CodeGen/GlobalISel/MachineIRBuilder.cpp

184–185

Missed that. Thanks.

[aditya_nandakumar]

Updated diff . Added some test cases by making IRTranslator use buildInstr for binary opcodes.

[aditya_nandakumar]

Added remaining IntegerOps + test cases for them.

[Gerolf]

include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h

94

How do you sort the opcodes? The order here is different from other functions (ConstantFoldBinop) in your code? Why not be consistent and eg. order all arithmetic (alphabetical), then all logical (alphabetical) or all alphabetical or ...

126

What about G_TRUNC?

lib/CodeGen/GlobalISel/MachineIRBuilder.cpp

200

BoolValue? Should that be an explicit check for zero instead?

398

For AnyExt ConstandFoldUnaryOp() uses Zext, here you use Sext?

408

Since ConstandFoldUnaryOp supports 4 opcodes, I had expected four calls to it in functions buildSExt, buildZext, buildAnyExt and *buildTrunc*. But the last one seems missing. If the function below (buildSExtorTrunc is covering that than I miss a call to ConstandFoldUnaryOp() there. So either way the code doesn't look quite kosher.

[aditya_nandakumar]

include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h

94

I hadn't thought about sorting. The order is mostly similar to the one in the DAG. I will alphabetically sort it here though.

126

I hadn't initially implemented all of them - as I thought I'd do that based on feedback. I'll certainly add G_TRUNC here.

lib/CodeGen/GlobalISel/MachineIRBuilder.cpp

200

That is how you check for zero in APInt.

/// This converts the APInt to a boolean value as a test against zero.
bool getBoolValue() const { return !!*this; }

398

Will change to Zext here. Not sure if it matters for any_ext though.

408

I hadn't hooked up G_TRUNC yet. Was planning to do it based on feedback.
I'll add it shortly.

[aditya_nandakumar]

Added more integer operations, along with tests.
Disabled constant folding cast instructions as MIR currently doesn't infer legality of constants of type that it creates.

[qcolombet]

Disabled constant folding cast instructions as MIR currently doesn't infer legality of constants of type that it creates.

Would it make sense to have a mode in the builder where combines are allow or not, just not type changes?
What I am thinking is every pass before legalization would run in combine mode and every pass after would run in non-combine mode.

[aditya_nandakumar]

Is that one flag that basically enables/disables all optimizations/folding ? Or we have some sort of API where the user opt's in/out into certain transformations..

[qcolombet]

Is that one flag that basically enables/disables all optimizations/folding ?

Yes, I would go with that for now. But I could see your concerns that we are going to generate crapy code for no good reason, thus you'd like more control.

Or we have some sort of API where the user opt's in/out into certain transformations..

Hi Aditya,

It feels to me that we are attacking the problem of the combine optimizations and I wouldn't want complicated APIs for this. Basically, the way I see it is with a dumb MachineIRBuilder base class that would be specialized with the combines that make sense for a target at a given point for a given optimization level. The challenge here is to define which combines are available and when they are valid to apply (e.g., ok before legalization, etc.) for each target. I can see a table gen path here.

To summarize, I'd like to keep the combiner logic as simple as possible (ideally none at all for O0) because I fear we are already touching something we haven't carefully thought yet.

Cheers,
-Quentin

[dsanders]

Hi Aditya,

Is there anything in this patch we still need? I believe you committed similar functionality along with a CSE'ing builder

[aditya_nandakumar]

Yes - this is not required any more.

include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h

class MachineIRBuilder {
   void addUseFromArg(MachineInstrBuilder &MIB, unsigned Reg) {
     MIB.addUse(Reg);
   }
 
   void addUseFromArg(MachineInstrBuilder &MIB, const MachineInstrBuilder &UseMIB) {
     MIB.addUse(UseMIB->getOperand(0).getReg());
   }
 
   void addUsesFromArgs(MachineInstrBuilder &MIB) { }
   template<typename UseArgTy, typename ... UseArgsTy>
   void addUsesFromArgs(MachineInstrBuilder &MIB, UseArgTy &&Arg1, UseArgsTy &&... Args) {
     addUseFromArg(MIB, Arg1);
     addUsesFromArgs(MIB, std::forward<UseArgsTy>(Args)...);
   }
+  unsigned getRegFromArg(unsigned Reg) { return Reg; }
+  unsigned getRegFromArg(MachineInstrBuilder &MIB) {
+    return MIB->getOperand(0).getReg();
+  }
+  template <typename DstTy, typename UseArg1, typename UseArg2>
+  MachineInstrBuilder buildInstrImpl(unsigned Opc, DstTy &&DstArg,
+                                     UseArg1 &&Arg1, UseArg2 &&Arg2) {
+    switch (Opc) {
+    case TargetOpcode::G_ADD:
+    case TargetOpcode::G_AND:
+    case TargetOpcode::G_ASHR:
+    case TargetOpcode::G_LSHR:
+    case TargetOpcode::G_MUL:
+    case TargetOpcode::G_OR:
+    case TargetOpcode::G_SDIV:
+    case TargetOpcode::G_SHL:
+    case TargetOpcode::G_SREM:
+    case TargetOpcode::G_SUB:
+    case TargetOpcode::G_UDIV:
+    case TargetOpcode::G_UREM:
+    case TargetOpcode::G_XOR:
+      return buildBinaryOp(Opc, getDestFromArg(DstArg), getRegFromArg(Arg1),
+                           getRegFromArg(Arg2));
+    }
+    auto MIB = buildInstr(Opc).addDef(getDestFromArg(DstArg));
+    addUsesFromArgs(MIB, std::forward<UseArg1>(Arg1),
+                    std::forward<UseArg2>(Arg2));
+    return MIB;
+  }
+  template <typename DstTy, typename... UseArgsTy>
+  MachineInstrBuilder buildInstrImpl(unsigned Opc, DstTy &&DstArg,
+                                     UseArgsTy &&... Args) {
+    auto MIB = buildInstr(Opc).addDef(getDestFromArg(DstArg));
+    addUsesFromArgs(MIB, std::forward<UseArgsTy>(Args)...);
+    return MIB;
+  }
+
 public:
   /// Getter for the function we currently build.
   MachineFunction &getMF() {
     assert(MF && "MachineFunction is not set");
     return *MF;
   }
 
   /// Getter for the basic block we currently build.
   MachineBasicBlock &getMBB() {
     assert(MBB && "MachineBasicBlock is not set");
     return *MBB;
public:
   MachineInstrBuilder buildInstr(unsigned Opcode);
 
   /// DAG like Generic method for building arbitrary instructions as above.
   /// \Opc opcode for the instruction.
   /// \Ty Either LLT/TargetRegisterClass/unsigned types for Dst
   /// \Args Variadic list of uses of types(unsigned/MachineInstrBuilder)
   /// Uses of type MachineInstrBuilder will perform
   /// getOperand(0).getReg() to convert to register.
+
   template <typename DstTy, typename... UseArgsTy>
-  MachineInstrBuilder buildInstr(unsigned Opc, DstTy &&Ty,
+  MachineInstrBuilder buildInstr(unsigned Opc, DstTy &&DstArg,
                                  UseArgsTy &&... Args) {
-    auto MIB = buildInstr(Opc).addDef(getDestFromArg(Ty));
-    addUsesFromArgs(MIB, std::forward<UseArgsTy>(Args)...);
-    return MIB;
+    return buildInstrImpl(Opc, std::forward<DstTy>(DstArg),
+                          std::forward<UseArgsTy>(Args)...);
   }
 
   /// Build but don't insert <empty> = \p Opcode <empty>.
   ///
   /// \pre setMF, setBasicBlock or setMI  must have been called.
   ///
   /// \return a MachineInstrBuilder for the newly created instruction.
   MachineInstrBuilder buildInstrNoInsert(unsigned Opcode);

lib/CodeGen/GlobalISel/IRTranslator.cpp

bool IRTranslator::translateBinaryOp(unsigned Opcode, const User &U,
 
   // Get or create a virtual register for each value.
   // Unless the value is a Constant => loadimm cst?
   // or inline constant each time?
   // Creation of a virtual register needs to have a size.
   unsigned Op0 = getOrCreateVReg(*U.getOperand(0));
   unsigned Op1 = getOrCreateVReg(*U.getOperand(1));
   unsigned Res = getOrCreateVReg(U);
-  MIRBuilder.buildInstr(Opcode).addDef(Res).addUse(Op0).addUse(Op1);
+  MIRBuilder.buildInstr(Opcode, Res, Op0, Op1);
   return true;
 }
 
 bool IRTranslator::translateFSub(const User &U, MachineIRBuilder &MIRBuilder) {
   // -0.0 - X --> G_FNEG
   if (isa<Constant>(U.getOperand(0)) &&
       U.getOperand(0) == ConstantFP::getZeroValueForNegation(U.getType())) {
     MIRBuilder.buildInstr(TargetOpcode::G_FNEG)

lib/CodeGen/GlobalISel/MachineIRBuilder.cpp

 //===-- llvm/CodeGen/GlobalISel/MachineIRBuilder.cpp - MIBuilder--*- C++ -*-==//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 /// \file
 /// This file implements the MachineIRBuidler class.
 //===----------------------------------------------------------------------===//
 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
+#include "llvm/CodeGen/GlobalISel/Utils.h"
 
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetOpcodes.h"
assert(MRI->getType(Res).getAddressSpace() ==
              GV->getType()->getAddressSpace() &&
          "address space mismatch");
 
   return buildInstr(TargetOpcode::G_GLOBAL_VALUE)
       .addDef(Res)
       .addGlobalAddress(GV);
 }
 
+static Optional<APInt> ConstantFoldBinOp(unsigned Opcode, const unsigned Op1,
+                                         const unsigned Op2,
+                                         const MachineRegisterInfo *MRI) {
+  auto MaybeOp1Cst = getConstantVRegVal(Op1, *MRI);
+  auto MaybeOp2Cst = getConstantVRegVal(Op2, *MRI);
+  if (MaybeOp1Cst && MaybeOp2Cst) {
+    LLT Ty = MRI->getType(Op1);
+    APInt C1(Ty.getSizeInBits(), *MaybeOp1Cst, true);
+    APInt C2(Ty.getSizeInBits(), *MaybeOp2Cst, true);
+    switch (Opcode) {
+    default:
+      break;
+    case TargetOpcode::G_ADD:
+      return C1 + C2;
+    case TargetOpcode::G_AND:
+      return C1 & C2;
+    case TargetOpcode::G_ASHR:
+      return C1.ashr(C2);
+    case TargetOpcode::G_LSHR:
+      return C1.lshr(C2);
+    case TargetOpcode::G_MUL:
+      return C1 * C2;
+    case TargetOpcode::G_OR:
+      return C1 | C2;
+    case TargetOpcode::G_SHL:
+      return C1 << C2;
+    case TargetOpcode::G_SUB:
+      return C1 - C2;
+    case TargetOpcode::G_XOR:
+      return C1 ^ C2;
+    case TargetOpcode::G_UDIV:
+      if (!C2.getBoolValue())
+        break;
+      return C1.udiv(C2);
+    case TargetOpcode::G_SDIV:
+      if (!C2.getBoolValue())
+        break;
+      return C1.sdiv(C2);
+    case TargetOpcode::G_UREM:
+      if (!C2.getBoolValue())
+        break;
+      return C1.urem(C2);
+    case TargetOpcode::G_SREM:
+      if (!C2.getBoolValue())
+        break;
+      return C1.srem(C2);
+    }
+  }
+  return None;
+}
+
 MachineInstrBuilder MachineIRBuilder::buildBinaryOp(unsigned Opcode, unsigned Res, unsigned Op0,
                                                unsigned Op1) {
   assert((MRI->getType(Res).isScalar() || MRI->getType(Res).isVector()) &&
          "invalid operand type");
   assert(MRI->getType(Res) == MRI->getType(Op0) &&
          MRI->getType(Res) == MRI->getType(Op1) && "type mismatch");
 
+  if (auto NewVal = ConstantFoldBinOp(Opcode, Op0, Op1, MRI))
+    return buildConstant(Res, NewVal->getSExtValue());
+
   return buildInstr(Opcode)
       .addDef(Res)
       .addUse(Op0)
       .addUse(Op1);
 }
 
 MachineInstrBuilder MachineIRBuilder::buildAdd(unsigned Res, unsigned Op0,
                                                unsigned Op1) {
return buildInstr(TargetOpcode::G_UADDE)
       .addUse(Op1)
       .addUse(CarryIn);
 }
 
 MachineInstrBuilder MachineIRBuilder::buildAnyExt(unsigned Res, unsigned Op) {
   validateTruncExt(Res, Op, true);
   return buildInstr(TargetOpcode::G_ANYEXT).addDef(Res).addUse(Op);
 }
 
 MachineInstrBuilder MachineIRBuilder::buildSExt(unsigned Res, unsigned Op) {
   validateTruncExt(Res, Op, true);
   return buildInstr(TargetOpcode::G_SEXT).addDef(Res).addUse(Op);
 }
 
 MachineInstrBuilder MachineIRBuilder::buildZExt(unsigned Res, unsigned Op) {
   validateTruncExt(Res, Op, true);
   return buildInstr(TargetOpcode::G_ZEXT).addDef(Res).addUse(Op);
 }
 
 MachineInstrBuilder MachineIRBuilder::buildSExtOrTrunc(unsigned Res,
                                                        unsigned Op) {
   assert(MRI->getType(Res).isScalar() || MRI->getType(Res).isVector());
   assert(MRI->getType(Res).isScalar() == MRI->getType(Op).isScalar());
 
   unsigned Opcode = TargetOpcode::COPY;
   if (MRI->getType(Res).getSizeInBits() > MRI->getType(Op).getSizeInBits())
     Opcode = TargetOpcode::G_SEXT;

test/CodeGen/AArch64/GlobalISel/arm64-irtranslator.ll

 
 next:
   %sum1 = add i32 %in, 1
   %sum2 = add i32 %in, 1
   %res = add i32 %sum1, %sum2
   ret i32 %res
 }
 
-; CHECK-LABEL: name: constant_int_start
-; CHECK: [[TWO:%[0-9]+]](s32) = G_CONSTANT i32 2
-; CHECK: [[ANSWER:%[0-9]+]](s32) = G_CONSTANT i32 42
-; CHECK: [[RES:%[0-9]+]](s32) = G_ADD [[TWO]], [[ANSWER]]
-define i32 @constant_int_start() {
+; CHECK-LABEL: name: constant_fold_add
+; CHECK: [[RES:%[0-9]+]](s32) = G_CONSTANT i32 44
+define i32 @constant_fold_add() {
   %res = add i32 2, 42
   ret i32 %res
 }
 
+; CHECK-LABEL: name: constant_fold_sub
+; CHECK: [[RES:%[0-9]+]](s32) = G_CONSTANT i32 40
+define i32 @constant_fold_sub() {
+  %res = sub i32 42, 2
+  ret i32 %res
+}
+
+; CHECK-LABEL: name: constant_fold_mul
+; CHECK: [[RES:%[0-9]+]](s32) = G_CONSTANT i32 84
+define i32 @constant_fold_mul() {
+  %res = mul i32 42, 2
+  ret i32 %res
+}
+
+; CHECK-LABEL: name: constant_fold_and
+; CHECK: [[RES:%[0-9]+]](s32) = G_CONSTANT i32 0
+define i32 @constant_fold_and() {
+  %res = and i32 2, 4
+  ret i32 %res
+}
+
+; CHECK-LABEL: name: constant_fold_or
+; CHECK: [[RES:%[0-9]+]](s32) = G_CONSTANT i32 3
+define i32 @constant_fold_or() {
+  %res = or i32 1, 2
+  ret i32 %res
+}
+
+; CHECK-LABEL: name: constant_fold_xor
+; CHECK: [[RES:%[0-9]+]](s32) = G_CONSTANT i32 2
+define i32 @constant_fold_xor() {
+  %res = xor i32 2, 3
+  ret i32 %res
+}
+
+; CHECK-LABEL: name: constant_fold_shl
+; CHECK: [[RES:%[0-9]+]](s32) = G_CONSTANT i32 4
+define i32 @constant_fold_shl() {
+  %res = shl i32 1, 2
+  ret i32 %res
+}
+
+; CHECK-LABEL: name: constant_fold_lshr
+; CHECK: [[RES:%[0-9]+]](s32) = G_CONSTANT i32 2
+define i32 @constant_fold_lshr() {
+  %res = lshr i32 4, 1
+  ret i32 %res
+}
+
+; CHECK-LABEL: name: constant_fold_udiv
+; CHECK: [[RES:%[0-9]+]](s32) = G_CONSTANT i32 2
+define i32 @constant_fold_udiv() {
+  %res = udiv i32 4, 2
+  ret i32 %res
+}
+
+; CHECK-LABEL: name: constant_fold_sdiv
+; CHECK: [[RES:%[0-9]+]](s32) = G_CONSTANT i32 -2
+define i32 @constant_fold_sdiv() {
+  %res = sdiv i32 -4, 2
+  ret i32 %res
+}
+
+; CHECK-LABEL: name: constant_fold_urem
+; CHECK: [[RES:%[0-9]+]](s32) = G_CONSTANT i32 1
+define i32 @constant_fold_urem() {
+  %res = urem i32 4, 3
+  ret i32 %res
+}
+
+; CHECK-LABEL: name: constant_fold_srem
+; CHECK: [[RES:%[0-9]+]](s32) = G_CONSTANT i32 1
+define i32 @constant_fold_srem() {
+  %res = srem i32 4, 3
+  ret i32 %res
+}
+
 ; CHECK-LABEL: name: test_undef
 ; CHECK: [[UNDEF:%[0-9]+]](s32) = G_IMPLICIT_DEF
 ; CHECK: %w0 = COPY [[UNDEF]]
 define i32 @test_undef() {
   ret i32 undef
 }
 
 ; CHECK-LABEL: name: test_constant_inttoptr