-Oz: Reuse constants in registers instead of canonicalizing operations that use a different constant

[ramred01]

Summary

This patch fixes an issue with -Oz and -Os compilation where it is profitable to reuse constants that are already in registers rather than canonicalizing an operation that changes the constant used, thereby having to materialize the constant again.

e.g:
int test(int* x)
{

if (x > (int)655360000L)
   return *x - (int)655360000L;
return x;

}

In the above code, although the constant used in the compare is reused in the subtraction, LLVM canonicalizes the subtraction to an addition with a negative constant. That means that the constant that was materialized in a register for the compare cannot be reused for the subsequent operation and another constant (which is the negative of the first one) is materialized.

We solve this by tracking the constants that are used in a function and wherever we see a new constant, we check is it is the negative of an earlier used constant or just one off from an earlier used constant. If so, then we reverse the canonicalization for that instruction so as to use the same constant as was used before.

[ostannard]

include/llvm/CodeGen/TargetInstrInfo.h

580

This name shouldn't mention AArch64 if it can be implemented for other targets, and shouldn't be here if it is AArch64 specific. It should also mention _what_ it does, not just "change".

lib/CodeGen/MachineCSE.cpp

62

What if the value doesn't fit into an int (on the host system)?

509

AC6?

516

This name tells me nothing about what the function does.

523

I don't think we can guarantee that operands 0 and 1 are used consistently across all targets.

531

If both positive and negative versions of the same immediate exist in the function, isn't this going to swap them both, and we'll still have both constants?

Why do we want to allow an offset of one? I don't see any code below which adjusts for this, so isn't this going to change the constant?

559

Why? Also, this check will only detect global isel compare instructions, not target-specific ones.

593

Duplicated call

595

Again, this is making assumptions about operands which might not be true for all targets.

599

This is going to replace every use of the register, not just the one we have checked is safe.

I don't see any checks to make sure the add/sub instruction is dominated by the immediate move which we are re-using.

623

Why is this done here? It should be either properly integrated into the CSE algorithm, or made a separate pass.

include/llvm/CodeGen/TargetInstrInfo.h

public:
   /// before calling this function.
   virtual bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
                              MachineBasicBlock *&FBB,
                              SmallVectorImpl<MachineOperand> &Cond,
                              bool AllowModify = false) const {
     return true;
   }
 
+  virtual unsigned changeAArch64Opcode(MachineInstr *MInstr) const {
+    return 0;
+  }
+
   /// Represents a predicate at the MachineFunction level.  The control flow a
   /// MachineBranchPredicate represents is:
   ///
   ///  Reg = LHS `Predicate` RHS         == ConditionDef
   ///  if Reg then goto TrueDest else goto FalseDest
   ///
   struct MachineBranchPredicate {
     enum ComparePredicate {

lib/CodeGen/MachineCSE.cpp

 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/MC/MCInstrDesc.h"
 #include "llvm/MC/MCRegisterInfo.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/RecyclingAllocator.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
 #include <cassert>
 #include <iterator>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "machine-cse"
 
 STATISTIC(NumCoalesces, "Number of copies coalesced");
 STATISTIC(NumCSEs,      "Number of common subexpression eliminated");
 STATISTIC(NumPhysCSEs,
           "Number of physreg referencing common subexpr eliminated");
 STATISTIC(NumCrossBBCSEs,
           "Number of cross-MBB physreg referencing CS eliminated");
 STATISTIC(NumCommutes,  "Number of copies coalesced after commuting");
 
 namespace {
+  // struct for storing constant value information like value, register and instruction.
+  struct ConstMInst {
+    int OriginalValue = 0;
+    unsigned RegValue;
+    MachineInstr *ConstMInstr;
+  };
 
   class MachineCSE : public MachineFunctionPass {
     const TargetInstrInfo *TII;
     const TargetRegisterInfo *TRI;
     AliasAnalysis *AA;
     MachineDominatorTree *DT;
     MachineRegisterInfo *MRI;
+    SmallVector<ConstMInst, 32> constMInstVec;
 
   public:
     static char ID; // Pass identification
 
     MachineCSE() : MachineFunctionPass(ID) {
       initializeMachineCSEPass(*PassRegistry::getPassRegistry());
     }
 
private:
     bool isProfitableToCSE(unsigned CSReg, unsigned Reg,
                            MachineInstr *CSMI, MachineInstr *MI);
     void EnterScope(MachineBasicBlock *MBB);
     void ExitScope(MachineBasicBlock *MBB);
     bool ProcessBlock(MachineBasicBlock *MBB);
     void ExitScopeIfDone(MachineDomTreeNode *Node,
                          DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren);
     bool PerformCSE(MachineDomTreeNode *Node);
+    void AnalyseConstValueUses(MachineFunction &MF);
+    void updateRegInfoAndInstr(MachineBasicBlock *MBB);
   };
 
 } // end anonymous namespace
 
 char MachineCSE::ID = 0;
 
 char &llvm::MachineCSEID = MachineCSE::ID;
 

 void MachineCSE::ExitScope(MachineBasicBlock *MBB) {
   LLVM_DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n');
   DenseMap<MachineBasicBlock*, ScopeType*>::iterator SI = ScopeMap.find(MBB);
   assert(SI != ScopeMap.end());
   delete SI->second;
   ScopeMap.erase(SI);
 }
 
+// e.g:  int test(int* x)
+//       {
+//         if(x > (int)655360000L)
+//           return *x - (int)655360000L;
+//         return x;
+//       }
+
+// The above code uses the constant 655360000, once in a compare, once in a subtract.
+// AC6 will convert the subtract to an addition by a negative, which means
+// that it needs to materialise both the constant and the negative constant.
+
+// To fix this issue, we keep track of the constants used and if the same
+// constant or its negative is used in more than one place, we replace the
+// next use register with previous const reg and change the instruction 
+// from Add to Sub.
+void MachineCSE::updateRegInfoAndInstr(MachineBasicBlock *MBB)
+{
+  for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) {
+    MachineInstr *MI = &*I;
+    ++I;
+    // checking if instruction is Move immediate or not
+    if (MI->isMoveImmediate()) {
+      int ConstNum = MI->getOperand(1).getImm();
+      // iterate through all the constant values list in current function 
+      for (SmallVector<ConstMInst, 32>::iterator it = constMInstVec.begin();
+          it != constMInstVec.end(); ++it) {
+        // if current instruction(MI) and instruction from list(it->ConstMInstr)
+        // both are same continue.
+        if(it->ConstMInstr == MI)
+          continue;
+        // serching current move instruction constant value is using in any where 
+        // in current function or constant value +1 or -1 or negative of that value.
+        // if it's have uses in this function have to iterate through 
+        // the instruction and find out the def register.
+        if (it->OriginalValue == ConstNum ||
+            it->OriginalValue == ConstNum + 1 ||
+            it->OriginalValue == ConstNum - 1 ||
+            it->OriginalValue == -ConstNum ||
+            it->OriginalValue == -ConstNum + 1 ||
+            it->OriginalValue == -ConstNum - 1) {
+          for (MachineInstr::mop_iterator MOI = it->ConstMInstr->operands_begin(),
+               MOE = it->ConstMInstr->operands_end();
+               MOI != MOE; ++MOI) {
+            // if operand is not register and operand is not def then continue.
+            if (!MOI->isReg())
+              continue;
+            if (!MOI->isDef())
+              continue;
+            
+            unsigned Newreg = MI->getOperand(0).getReg();
+            unsigned Reg = MOI->getReg();
+            // find out the uses of def register(from it->ConstMInstr) and 
+            // iterate through all the use instructions.
+            for (MachineRegisterInfo::use_instr_iterator
+                 UI = MRI->use_instr_begin(Reg),
+                 E = MRI->use_instr_end(); UI != E; ) {
+              MachineInstr *UseMI = &*(UI++);
+              MachineBasicBlock *MBBL = UseMI->getParent();
+              // if have any instruction is cmp inst in Machine Basic Block
+              // dont do this transformation.
+              MachineBasicBlock::instr_iterator Inst;
+              for (Inst = MBBL->instr_begin();
+                   Inst != MBBL->instr_end(); ++Inst)
+                if (Inst->getOpcode() == TargetOpcode::G_ICMP)
+                  return;
+
+              // iterate through the first move instruction and find out the uses of def register.
+              // if def reg is killed in first use and we want use this 
+              // def reg in below instructions have same const value uses,
+              // have reset the kill as false. and in final use it will kill this def reg after all uses.
+              for (MachineRegisterInfo::use_instr_iterator
+                   RegUI = MRI->use_instr_begin(Newreg),
+                   RegE = MRI->use_instr_end(); RegUI != RegE; ) {
+                   MachineInstr *RegUseMI = &*(RegUI++);
+                for (MachineInstr::mop_iterator MO = RegUseMI->operands_begin(),
+                     ME = RegUseMI->operands_end();
+                     MO != ME; ++MO) {
+                  if (!MO->isReg())
+                    continue;
+                  if (MO->isDef())
+                    continue;
+                  if(Newreg == MO->getReg()) {
+                    if(MO->isKill())
+                      MO->setIsKill(false);
+                  }
+                }
+              }
+              const DebugLoc DL = UseMI->getDebugLoc();
+              MachineBasicBlock::iterator InstIter = UseMI->getIterator();
+              unsigned TargetOpc = TII->changeAArch64Opcode(UseMI);
+              // if instruction is either Add or SUb,
+              // then the instruction is add change to sub and vice versa.
+              if (TII->changeAArch64Opcode(UseMI)) {
+                BuildMI(*MBBL, InstIter, DL, TII->get(TargetOpc))
+                        .add(UseMI->getOperand(0))
+                        .add(UseMI->getOperand(1))
+                        .add(UseMI->getOperand(2));
+                // replace the constant uses reg with top const num use reg value.
+                MRI->replaceRegWith(Reg, Newreg);
+                // erase the second move instruction from  parent basic block.
+                it->ConstMInstr->eraseFromParent();
+                // remove old instruction (Add or Sub) from Basic Block.
+                UseMI->eraseFromParent();
+              }
+            }
+          }
+        }
+      }
+    }
+  }    
+}
+
 bool MachineCSE::ProcessBlock(MachineBasicBlock *MBB) {
   bool Changed = false;
 
   SmallVector<std::pair<unsigned, unsigned>, 8> CSEPairs;
   SmallVector<unsigned, 2> ImplicitDefsToUpdate;
   SmallVector<unsigned, 2> ImplicitDefs;
+
+  // if opt level is either -Oz or -Os, call updateRegInfoAndInstr() API.
+  // if able to change add to sub or sub to add.
+  if (MBB->getParent()->getFunction().optForSize()) {
+    updateRegInfoAndInstr(MBB); 
+  }
+  
   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) {
     MachineInstr *MI = &*I;
     ++I;
 
     if (!isCSECandidate(MI))
       continue;
 
     bool FoundCSE = VNT.count(MI);
for (MachineDomTreeNode *Node : Scopes) {
     Changed |= ProcessBlock(MBB);
     // If it's a leaf node, it's done. Traverse upwards to pop ancestors.
     ExitScopeIfDone(Node, OpenChildren);
   }
 
   return Changed;
 }
 
+// iterate through current function and find out the constant values and uses
+// of those values, and store those constant values and instructions into list.
+void MachineCSE::AnalyseConstValueUses(MachineFunction &MF) {
+  for (MachineBasicBlock &MI : MF) {
+    for (MachineInstr &I : MI) {
+      if (I.isMoveImmediate()) {
+        int ConstNum = I.getOperand(1).getImm();
+        ConstMInst constObj;
+        constObj.OriginalValue = ConstNum;
+        constObj.RegValue = I.getOperand(0).getReg();
+        constObj.ConstMInstr = &I;
+
+        constMInstVec.push_back(constObj);
+      }
+    }
+  }
+}
+
 bool MachineCSE::runOnMachineFunction(MachineFunction &MF) {
+
   if (skipFunction(MF.getFunction()))
     return false;
   
   TII = MF.getSubtarget().getInstrInfo();
   TRI = MF.getSubtarget().getRegisterInfo();
   MRI = &MF.getRegInfo();
   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
   DT = &getAnalysis<MachineDominatorTree>();
   LookAheadLimit = TII->getMachineCSELookAheadLimit();
+
+  // if optimization level is Oz or Os, then we are analyzing the instructions for constant values and the uses of those values.
+  if (MF.getFunction().optForSize()) {
+   constMInstVec.clear();
+   AnalyseConstValueUses(MF);
+  }
   return PerformCSE(DT->getRootNode());
 }

lib/Target/AArch64/AArch64InstrInfo.h

bool isBranchOffsetInRange(unsigned BranchOpc,
                              int64_t BrOffset) const override;
 
   MachineBasicBlock *getBranchDestBlock(const MachineInstr &MI) const override;
 
   bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
                      MachineBasicBlock *&FBB,
                      SmallVectorImpl<MachineOperand> &Cond,
                      bool AllowModify = false) const override;
+
+  unsigned changeAArch64Opcode(MachineInstr *MInstr) const override;
+
   unsigned removeBranch(MachineBasicBlock &MBB,
                         int *BytesRemoved = nullptr) const override;
   unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB,
                         MachineBasicBlock *FBB, ArrayRef<MachineOperand> Cond,
                         const DebugLoc &DL,
                         int *BytesAdded = nullptr) const override;
   bool
   reverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const override;

lib/Target/AArch64/AArch64InstrInfo.cpp

if (AllowModify)
       I->eraseFromParent();
     return true;
   }
 
   // Otherwise, can't handle this.
   return true;
 }
 
+unsigned AArch64InstrInfo::changeAArch64Opcode(MachineInstr *MInstr) const {
+  switch (MInstr->getOpcode()) {
+    default:
+      return false;
+    case AArch64::ADDWrr:
+      return AArch64::SUBWrr;
+    case AArch64::ADDWrs:
+      return AArch64::SUBWrs;
+    case AArch64::ADDWrx:
+      return AArch64::SUBWrx;
+    case AArch64::ADDWri:
+      return AArch64::SUBWri;
+    case AArch64::ADDXri:
+      return AArch64::SUBXri;
+    case AArch64::ADDXrr:
+      return AArch64::SUBXrr;
+    case AArch64::ADDXrs:
+      return AArch64::SUBXrs;
+    case AArch64::ADDXrx:
+      return AArch64::SUBXrx;
+    case AArch64::SUBWri:
+      return AArch64::ADDWri;
+    case AArch64::SUBWrr:
+      return AArch64::ADDWrr;
+    case AArch64::SUBXri:
+      return AArch64::ADDXri;
+  }
+}
+
 bool AArch64InstrInfo::reverseBranchCondition(
     SmallVectorImpl<MachineOperand> &Cond) const {
   if (Cond[0].getImm() != -1) {
     // Regular Bcc
     AArch64CC::CondCode CC = (AArch64CC::CondCode)(int)Cond[0].getImm();
     Cond[0].setImm(AArch64CC::getInvertedCondCode(CC));
   } else {
     // Folded compare-and-branch

test/CodeGen/AArch64/better_use_of_existing_constants.ll

+; RUN: llc -verify-machineinstrs -enable-machine-outliner -mtriple=aarch64-apple-darwin -mcpu=cortex-a53 < %s | FileCheck %s
+; ModuleID = '../test_51313.c'
+source_filename = "../test_51313.c"
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64-arm-none-eabi"
+
+; Function Attrs: minsize norecurse nounwind optsize readonly
+;CHECK-LABEL: @test
+;CHECK: mov
+;CHECK-NEXT: movk
+;CHECK: ldr
+;CHECK-NEXT: sub
+;CHECK-NOT: add
+
+define dso_local i32 @test(i32*) local_unnamed_addr #0 {
+  %2 = icmp ugt i32* %0, inttoptr (i64 655360000 to i32*)
+  br i1 %2, label %3, label %6
+
+3:                                                ; preds = %1
+  %4 = load i32, i32* %0, align 4, !tbaa !2
+  %5 = add nsw i32 %4, -655360000
+  br label %9
+
+6:                                                ; preds = %1
+  %7 = ptrtoint i32* %0 to i64
+  %8 = trunc i64 %7 to i32
+  br label %9
+
+9:                                                ; preds = %6, %3
+  %10 = phi i32 [ %5, %3 ], [ %8, %6 ]
+  ret i32 %10
+}
+
+attributes #0 = { minsize norecurse nounwind optsize readonly "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="cortex-a53" "target-features"="+aes,+crc,+crypto,+fp-armv8,+neon,+sha2" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 9.0.0 (https://git.llvm.org/git/clang.git/ a67b0501cbbab83a4a0795365ef9c38f0a6473f6) (https://git.llvm.org/git/llvm.git/ 5b28ef618dab3056eb1ce524dd504f9031ab88dc)"}
+!2 = !{!3, !3, i64 0}
+!3 = !{!"int", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C/C++ TBAA"}