contrib/llvm-project/llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

   1 //===-- lib/CodeGen/GlobalISel/GICombinerHelper.cpp -----------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 #include "llvm/CodeGen/GlobalISel/CombinerHelper.h"
   9 #include "llvm/CodeGen/GlobalISel/Combiner.h"
  10 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
  11 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
  12 #include "llvm/CodeGen/GlobalISel/Utils.h"
  13 #include "llvm/CodeGen/MachineInstr.h"
  14 #include "llvm/CodeGen/MachineRegisterInfo.h"
  15 #include "llvm/CodeGen/TargetInstrInfo.h"
  16
  17 #define DEBUG_TYPE "gi-combiner"
  18
  19 using namespace llvm;
  20
  21 CombinerHelper::CombinerHelper(GISelChangeObserver &Observer,
  22                                MachineIRBuilder &B)
  23     : Builder(B), MRI(Builder.getMF().getRegInfo()), Observer(Observer) {}
  24
  25 void CombinerHelper::replaceRegWith(MachineRegisterInfo &MRI, Register FromReg,
  26                                     Register ToReg) const {
  27   Observer.changingAllUsesOfReg(MRI, FromReg);
  28
  29   if (MRI.constrainRegAttrs(ToReg, FromReg))
  30     MRI.replaceRegWith(FromReg, ToReg);
  31   else
  32     Builder.buildCopy(ToReg, FromReg);
  33
  34   Observer.finishedChangingAllUsesOfReg();
  35 }
  36
  37 void CombinerHelper::replaceRegOpWith(MachineRegisterInfo &MRI,
  38                                       MachineOperand &FromRegOp,
  39                                       Register ToReg) const {
  40   assert(FromRegOp.getParent() && "Expected an operand in an MI");
  41   Observer.changingInstr(*FromRegOp.getParent());
  42
  43   FromRegOp.setReg(ToReg);
  44
  45   Observer.changedInstr(*FromRegOp.getParent());
  46 }
  47
  48 bool CombinerHelper::tryCombineCopy(MachineInstr &MI) {
  49   if (matchCombineCopy(MI)) {
  50     applyCombineCopy(MI);
  51     return true;
  52   }
  53   return false;
  54 }
  55 bool CombinerHelper::matchCombineCopy(MachineInstr &MI) {
  56   if (MI.getOpcode() != TargetOpcode::COPY)
  57     return false;
  58   unsigned DstReg = MI.getOperand(0).getReg();
  59   unsigned SrcReg = MI.getOperand(1).getReg();
  60   LLT DstTy = MRI.getType(DstReg);
  61   LLT SrcTy = MRI.getType(SrcReg);
  62   // Simple Copy Propagation.
  63   // a(sx) = COPY b(sx) -> Replace all uses of a with b.
  64   if (DstTy.isValid() && SrcTy.isValid() && DstTy == SrcTy)
  65     return true;
  66   return false;
  67 }
  68 void CombinerHelper::applyCombineCopy(MachineInstr &MI) {
  69   unsigned DstReg = MI.getOperand(0).getReg();
  70   unsigned SrcReg = MI.getOperand(1).getReg();
  71   MI.eraseFromParent();
  72   replaceRegWith(MRI, DstReg, SrcReg);
  73 }
  74
  75 namespace {
  76
  77 /// Select a preference between two uses. CurrentUse is the current preference
  78 /// while *ForCandidate is attributes of the candidate under consideration.
  79 PreferredTuple ChoosePreferredUse(PreferredTuple &CurrentUse,
  80                                   const LLT &TyForCandidate,
  81                                   unsigned OpcodeForCandidate,
  82                                   MachineInstr *MIForCandidate) {
  83   if (!CurrentUse.Ty.isValid()) {
  84     if (CurrentUse.ExtendOpcode == OpcodeForCandidate ||
  85         CurrentUse.ExtendOpcode == TargetOpcode::G_ANYEXT)
  86       return {TyForCandidate, OpcodeForCandidate, MIForCandidate};
  87     return CurrentUse;
  88   }
  89
  90   // We permit the extend to hoist through basic blocks but this is only
  91   // sensible if the target has extending loads. If you end up lowering back
  92   // into a load and extend during the legalizer then the end result is
  93   // hoisting the extend up to the load.
  94
  95   // Prefer defined extensions to undefined extensions as these are more
  96   // likely to reduce the number of instructions.
  97   if (OpcodeForCandidate == TargetOpcode::G_ANYEXT &&
  98       CurrentUse.ExtendOpcode != TargetOpcode::G_ANYEXT)
  99     return CurrentUse;
 100   else if (CurrentUse.ExtendOpcode == TargetOpcode::G_ANYEXT &&
 101            OpcodeForCandidate != TargetOpcode::G_ANYEXT)
 102     return {TyForCandidate, OpcodeForCandidate, MIForCandidate};
 103
 104   // Prefer sign extensions to zero extensions as sign-extensions tend to be
 105   // more expensive.
 106   if (CurrentUse.Ty == TyForCandidate) {
 107     if (CurrentUse.ExtendOpcode == TargetOpcode::G_SEXT &&
 108         OpcodeForCandidate == TargetOpcode::G_ZEXT)
 109       return CurrentUse;
 110     else if (CurrentUse.ExtendOpcode == TargetOpcode::G_ZEXT &&
 111              OpcodeForCandidate == TargetOpcode::G_SEXT)
 112       return {TyForCandidate, OpcodeForCandidate, MIForCandidate};
 113   }
 114
 115   // This is potentially target specific. We've chosen the largest type
 116   // because G_TRUNC is usually free. One potential catch with this is that
 117   // some targets have a reduced number of larger registers than smaller
 118   // registers and this choice potentially increases the live-range for the
 119   // larger value.
 120   if (TyForCandidate.getSizeInBits() > CurrentUse.Ty.getSizeInBits()) {
 121     return {TyForCandidate, OpcodeForCandidate, MIForCandidate};
 122   }
 123   return CurrentUse;
 124 }
 125
 126 /// Find a suitable place to insert some instructions and insert them. This
 127 /// function accounts for special cases like inserting before a PHI node.
 128 /// The current strategy for inserting before PHI's is to duplicate the
 129 /// instructions for each predecessor. However, while that's ok for G_TRUNC
 130 /// on most targets since it generally requires no code, other targets/cases may
 131 /// want to try harder to find a dominating block.
 132 static void InsertInsnsWithoutSideEffectsBeforeUse(
 133     MachineIRBuilder &Builder, MachineInstr &DefMI, MachineOperand &UseMO,
 134     std::function<void(MachineBasicBlock *, MachineBasicBlock::iterator,
 135                        MachineOperand &UseMO)>
 136         Inserter) {
 137   MachineInstr &UseMI = *UseMO.getParent();
 138
 139   MachineBasicBlock *InsertBB = UseMI.getParent();
 140
 141   // If the use is a PHI then we want the predecessor block instead.
 142   if (UseMI.isPHI()) {
 143     MachineOperand *PredBB = std::next(&UseMO);
 144     InsertBB = PredBB->getMBB();
 145   }
 146
 147   // If the block is the same block as the def then we want to insert just after
 148   // the def instead of at the start of the block.
 149   if (InsertBB == DefMI.getParent()) {
 150     MachineBasicBlock::iterator InsertPt = &DefMI;
 151     Inserter(InsertBB, std::next(InsertPt), UseMO);
 152     return;
 153   }
 154
 155   // Otherwise we want the start of the BB
 156   Inserter(InsertBB, InsertBB->getFirstNonPHI(), UseMO);
 157 }
 158 } // end anonymous namespace
 159
 160 bool CombinerHelper::tryCombineExtendingLoads(MachineInstr &MI) {
 161   PreferredTuple Preferred;
 162   if (matchCombineExtendingLoads(MI, Preferred)) {
 163     applyCombineExtendingLoads(MI, Preferred);
 164     return true;
 165   }
 166   return false;
 167 }
 168
 169 bool CombinerHelper::matchCombineExtendingLoads(MachineInstr &MI,
 170                                                 PreferredTuple &Preferred) {
 171   // We match the loads and follow the uses to the extend instead of matching
 172   // the extends and following the def to the load. This is because the load
 173   // must remain in the same position for correctness (unless we also add code
 174   // to find a safe place to sink it) whereas the extend is freely movable.
 175   // It also prevents us from duplicating the load for the volatile case or just
 176   // for performance.
 177
 178   if (MI.getOpcode() != TargetOpcode::G_LOAD &&
 179       MI.getOpcode() != TargetOpcode::G_SEXTLOAD &&
 180       MI.getOpcode() != TargetOpcode::G_ZEXTLOAD)
 181     return false;
 182
 183   auto &LoadValue = MI.getOperand(0);
 184   assert(LoadValue.isReg() && "Result wasn't a register?");
 185
 186   LLT LoadValueTy = MRI.getType(LoadValue.getReg());
 187   if (!LoadValueTy.isScalar())
 188     return false;
 189
 190   // Most architectures are going to legalize <s8 loads into at least a 1 byte
 191   // load, and the MMOs can only describe memory accesses in multiples of bytes.
 192   // If we try to perform extload combining on those, we can end up with
 193   // %a(s8) = extload %ptr (load 1 byte from %ptr)
 194   // ... which is an illegal extload instruction.
 195   if (LoadValueTy.getSizeInBits() < 8)
 196     return false;
 197
 198   // For non power-of-2 types, they will very likely be legalized into multiple
 199   // loads. Don't bother trying to match them into extending loads.
 200   if (!isPowerOf2_32(LoadValueTy.getSizeInBits()))
 201     return false;
 202
 203   // Find the preferred type aside from the any-extends (unless it's the only
 204   // one) and non-extending ops. We'll emit an extending load to that type and
 205   // and emit a variant of (extend (trunc X)) for the others according to the
 206   // relative type sizes. At the same time, pick an extend to use based on the
 207   // extend involved in the chosen type.
 208   unsigned PreferredOpcode = MI.getOpcode() == TargetOpcode::G_LOAD
 209                                  ? TargetOpcode::G_ANYEXT
 210                                  : MI.getOpcode() == TargetOpcode::G_SEXTLOAD
 211                                        ? TargetOpcode::G_SEXT
 212                                        : TargetOpcode::G_ZEXT;
 213   Preferred = {LLT(), PreferredOpcode, nullptr};
 214   for (auto &UseMI : MRI.use_instructions(LoadValue.getReg())) {
 215     if (UseMI.getOpcode() == TargetOpcode::G_SEXT ||
 216         UseMI.getOpcode() == TargetOpcode::G_ZEXT ||
 217         UseMI.getOpcode() == TargetOpcode::G_ANYEXT) {
 218       Preferred = ChoosePreferredUse(Preferred,
 219                                      MRI.getType(UseMI.getOperand(0).getReg()),
 220                                      UseMI.getOpcode(), &UseMI);
 221     }
 222   }
 223
 224   // There were no extends
 225   if (!Preferred.MI)
 226     return false;
 227   // It should be impossible to chose an extend without selecting a different
 228   // type since by definition the result of an extend is larger.
 229   assert(Preferred.Ty != LoadValueTy && "Extending to same type?");
 230
 231   LLVM_DEBUG(dbgs() << "Preferred use is: " << *Preferred.MI);
 232   return true;
 233 }
 234
 235 void CombinerHelper::applyCombineExtendingLoads(MachineInstr &MI,
 236                                                 PreferredTuple &Preferred) {
 237   // Rewrite the load to the chosen extending load.
 238   Register ChosenDstReg = Preferred.MI->getOperand(0).getReg();
 239
 240   // Inserter to insert a truncate back to the original type at a given point
 241   // with some basic CSE to limit truncate duplication to one per BB.
 242   DenseMap<MachineBasicBlock *, MachineInstr *> EmittedInsns;
 243   auto InsertTruncAt = [&](MachineBasicBlock *InsertIntoBB,
 244                            MachineBasicBlock::iterator InsertBefore,
 245                            MachineOperand &UseMO) {
 246     MachineInstr *PreviouslyEmitted = EmittedInsns.lookup(InsertIntoBB);
 247     if (PreviouslyEmitted) {
 248       Observer.changingInstr(*UseMO.getParent());
 249       UseMO.setReg(PreviouslyEmitted->getOperand(0).getReg());
 250       Observer.changedInstr(*UseMO.getParent());
 251       return;
 252     }
 253
 254     Builder.setInsertPt(*InsertIntoBB, InsertBefore);
 255     Register NewDstReg = MRI.cloneVirtualRegister(MI.getOperand(0).getReg());
 256     MachineInstr *NewMI = Builder.buildTrunc(NewDstReg, ChosenDstReg);
 257     EmittedInsns[InsertIntoBB] = NewMI;
 258     replaceRegOpWith(MRI, UseMO, NewDstReg);
 259   };
 260
 261   Observer.changingInstr(MI);
 262   MI.setDesc(
 263       Builder.getTII().get(Preferred.ExtendOpcode == TargetOpcode::G_SEXT
 264                                ? TargetOpcode::G_SEXTLOAD
 265                                : Preferred.ExtendOpcode == TargetOpcode::G_ZEXT
 266                                      ? TargetOpcode::G_ZEXTLOAD
 267                                      : TargetOpcode::G_LOAD));
 268
 269   // Rewrite all the uses to fix up the types.
 270   auto &LoadValue = MI.getOperand(0);
 271   SmallVector<MachineOperand *, 4> Uses;
 272   for (auto &UseMO : MRI.use_operands(LoadValue.getReg()))
 273     Uses.push_back(&UseMO);
 274
 275   for (auto *UseMO : Uses) {
 276     MachineInstr *UseMI = UseMO->getParent();
 277
 278     // If the extend is compatible with the preferred extend then we should fix
 279     // up the type and extend so that it uses the preferred use.
 280     if (UseMI->getOpcode() == Preferred.ExtendOpcode ||
 281         UseMI->getOpcode() == TargetOpcode::G_ANYEXT) {
 282       unsigned UseDstReg = UseMI->getOperand(0).getReg();
 283       MachineOperand &UseSrcMO = UseMI->getOperand(1);
 284       const LLT &UseDstTy = MRI.getType(UseDstReg);
 285       if (UseDstReg != ChosenDstReg) {
 286         if (Preferred.Ty == UseDstTy) {
 287           // If the use has the same type as the preferred use, then merge
 288           // the vregs and erase the extend. For example:
 289           //    %1:_(s8) = G_LOAD ...
 290           //    %2:_(s32) = G_SEXT %1(s8)
 291           //    %3:_(s32) = G_ANYEXT %1(s8)
 292           //    ... = ... %3(s32)
 293           // rewrites to:
 294           //    %2:_(s32) = G_SEXTLOAD ...
 295           //    ... = ... %2(s32)
 296           replaceRegWith(MRI, UseDstReg, ChosenDstReg);
 297           Observer.erasingInstr(*UseMO->getParent());
 298           UseMO->getParent()->eraseFromParent();
 299         } else if (Preferred.Ty.getSizeInBits() < UseDstTy.getSizeInBits()) {
 300           // If the preferred size is smaller, then keep the extend but extend
 301           // from the result of the extending load. For example:
 302           //    %1:_(s8) = G_LOAD ...
 303           //    %2:_(s32) = G_SEXT %1(s8)
 304           //    %3:_(s64) = G_ANYEXT %1(s8)
 305           //    ... = ... %3(s64)
 306           /// rewrites to:
 307           //    %2:_(s32) = G_SEXTLOAD ...
 308           //    %3:_(s64) = G_ANYEXT %2:_(s32)
 309           //    ... = ... %3(s64)
 310           replaceRegOpWith(MRI, UseSrcMO, ChosenDstReg);
 311         } else {
 312           // If the preferred size is large, then insert a truncate. For
 313           // example:
 314           //    %1:_(s8) = G_LOAD ...
 315           //    %2:_(s64) = G_SEXT %1(s8)
 316           //    %3:_(s32) = G_ZEXT %1(s8)
 317           //    ... = ... %3(s32)
 318           /// rewrites to:
 319           //    %2:_(s64) = G_SEXTLOAD ...
 320           //    %4:_(s8) = G_TRUNC %2:_(s32)
 321           //    %3:_(s64) = G_ZEXT %2:_(s8)
 322           //    ... = ... %3(s64)
 323           InsertInsnsWithoutSideEffectsBeforeUse(Builder, MI, *UseMO,
 324                                                  InsertTruncAt);
 325         }
 326         continue;
 327       }
 328       // The use is (one of) the uses of the preferred use we chose earlier.
 329       // We're going to update the load to def this value later so just erase
 330       // the old extend.
 331       Observer.erasingInstr(*UseMO->getParent());
 332       UseMO->getParent()->eraseFromParent();
 333       continue;
 334     }
 335
 336     // The use isn't an extend. Truncate back to the type we originally loaded.
 337     // This is free on many targets.
 338     InsertInsnsWithoutSideEffectsBeforeUse(Builder, MI, *UseMO, InsertTruncAt);
 339   }
 340
 341   MI.getOperand(0).setReg(ChosenDstReg);
 342   Observer.changedInstr(MI);
 343 }
 344
 345 bool CombinerHelper::matchCombineBr(MachineInstr &MI) {
 346   assert(MI.getOpcode() == TargetOpcode::G_BR && "Expected a G_BR");
 347   // Try to match the following:
 348   // bb1:
 349   //   %c(s32) = G_ICMP pred, %a, %b
 350   //   %c1(s1) = G_TRUNC %c(s32)
 351   //   G_BRCOND %c1, %bb2
 352   //   G_BR %bb3
 353   // bb2:
 354   // ...
 355   // bb3:
 356
 357   // The above pattern does not have a fall through to the successor bb2, always
 358   // resulting in a branch no matter which path is taken. Here we try to find
 359   // and replace that pattern with conditional branch to bb3 and otherwise
 360   // fallthrough to bb2.
 361
 362   MachineBasicBlock *MBB = MI.getParent();
 363   MachineBasicBlock::iterator BrIt(MI);
 364   if (BrIt == MBB->begin())
 365     return false;
 366   assert(std::next(BrIt) == MBB->end() && "expected G_BR to be a terminator");
 367
 368   MachineInstr *BrCond = &*std::prev(BrIt);
 369   if (BrCond->getOpcode() != TargetOpcode::G_BRCOND)
 370     return false;
 371
 372   // Check that the next block is the conditional branch target.
 373   if (!MBB->isLayoutSuccessor(BrCond->getOperand(1).getMBB()))
 374     return false;
 375
 376   MachineInstr *CmpMI = MRI.getVRegDef(BrCond->getOperand(0).getReg());
 377   if (!CmpMI || CmpMI->getOpcode() != TargetOpcode::G_ICMP ||
 378       !MRI.hasOneUse(CmpMI->getOperand(0).getReg()))
 379     return false;
 380   return true;
 381 }
 382
 383 bool CombinerHelper::tryCombineBr(MachineInstr &MI) {
 384   if (!matchCombineBr(MI))
 385     return false;
 386   MachineBasicBlock *BrTarget = MI.getOperand(0).getMBB();
 387   MachineBasicBlock::iterator BrIt(MI);
 388   MachineInstr *BrCond = &*std::prev(BrIt);
 389   MachineInstr *CmpMI = MRI.getVRegDef(BrCond->getOperand(0).getReg());
 390
 391   CmpInst::Predicate InversePred = CmpInst::getInversePredicate(
 392       (CmpInst::Predicate)CmpMI->getOperand(1).getPredicate());
 393
 394   // Invert the G_ICMP condition.
 395   Observer.changingInstr(*CmpMI);
 396   CmpMI->getOperand(1).setPredicate(InversePred);
 397   Observer.changedInstr(*CmpMI);
 398
 399   // Change the conditional branch target.
 400   Observer.changingInstr(*BrCond);
 401   BrCond->getOperand(1).setMBB(BrTarget);
 402   Observer.changedInstr(*BrCond);
 403   MI.eraseFromParent();
 404   return true;
 405 }
 406
 407 bool CombinerHelper::tryCombine(MachineInstr &MI) {
 408   if (tryCombineCopy(MI))
 409     return true;
 410   return tryCombineExtendingLoads(MI);
 411 }