lib/Target/Hexagon/HexagonGenExtract.cpp

   1 //===- HexagonGenExtract.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
   9 #include "llvm/ADT/APInt.h"
  10 #include "llvm/ADT/GraphTraits.h"
  11 #include "llvm/IR/BasicBlock.h"
  12 #include "llvm/IR/CFG.h"
  13 #include "llvm/IR/Constants.h"
  14 #include "llvm/IR/Dominators.h"
  15 #include "llvm/IR/Function.h"
  16 #include "llvm/IR/IRBuilder.h"
  17 #include "llvm/IR/Instruction.h"
  18 #include "llvm/IR/Instructions.h"
  19 #include "llvm/IR/Intrinsics.h"
  20 #include "llvm/IR/PatternMatch.h"
  21 #include "llvm/IR/Type.h"
  22 #include "llvm/IR/Value.h"
  23 #include "llvm/Pass.h"
  24 #include "llvm/Support/CommandLine.h"
  25 #include <algorithm>
  26 #include <cstdint>
  27 #include <iterator>
  28
  29 using namespace llvm;
  30
  31 static cl::opt<unsigned> ExtractCutoff("extract-cutoff", cl::init(~0U),
  32   cl::Hidden, cl::desc("Cutoff for generating \"extract\""
  33   " instructions"));
  34
  35 // This prevents generating extract instructions that have the offset of 0.
  36 // One of the reasons for "extract" is to put a sequence of bits in a regis-
  37 // ter, starting at offset 0 (so that these bits can then be used by an
  38 // "insert"). If the bits are already at offset 0, it is better not to gene-
  39 // rate "extract", since logical bit operations can be merged into compound
  40 // instructions (as opposed to "extract").
  41 static cl::opt<bool> NoSR0("extract-nosr0", cl::init(true), cl::Hidden,
  42   cl::desc("No extract instruction with offset 0"));
  43
  44 static cl::opt<bool> NeedAnd("extract-needand", cl::init(true), cl::Hidden,
  45   cl::desc("Require & in extract patterns"));
  46
  47 namespace llvm {
  48
  49 void initializeHexagonGenExtractPass(PassRegistry&);
  50 FunctionPass *createHexagonGenExtract();
  51
  52 } // end namespace llvm
  53
  54 namespace {
  55
  56   class HexagonGenExtract : public FunctionPass {
  57   public:
  58     static char ID;
  59
  60     HexagonGenExtract() : FunctionPass(ID) {
  61       initializeHexagonGenExtractPass(*PassRegistry::getPassRegistry());
  62     }
  63
  64     StringRef getPassName() const override {
  65       return "Hexagon generate \"extract\" instructions";
  66     }
  67
  68     bool runOnFunction(Function &F) override;
  69
  70     void getAnalysisUsage(AnalysisUsage &AU) const override {
  71       AU.addRequired<DominatorTreeWrapperPass>();
  72       AU.addPreserved<DominatorTreeWrapperPass>();
  73       FunctionPass::getAnalysisUsage(AU);
  74     }
  75
  76   private:
  77     bool visitBlock(BasicBlock *B);
  78     bool convert(Instruction *In);
  79
  80     unsigned ExtractCount = 0;
  81     DominatorTree *DT;
  82   };
  83
  84 } // end anonymous namespace
  85
  86 char HexagonGenExtract::ID = 0;
  87
  88 INITIALIZE_PASS_BEGIN(HexagonGenExtract, "hextract", "Hexagon generate "
  89   "\"extract\" instructions", false, false)
  90 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
  91 INITIALIZE_PASS_END(HexagonGenExtract, "hextract", "Hexagon generate "
  92   "\"extract\" instructions", false, false)
  93
  94 bool HexagonGenExtract::convert(Instruction *In) {
  95   using namespace PatternMatch;
  96
  97   Value *BF = nullptr;
  98   ConstantInt *CSL = nullptr, *CSR = nullptr, *CM = nullptr;
  99   BasicBlock *BB = In->getParent();
 100   LLVMContext &Ctx = BB->getContext();
 101   bool LogicalSR;
 102
 103   // (and (shl (lshr x, #sr), #sl), #m)
 104   LogicalSR = true;
 105   bool Match = match(In, m_And(m_Shl(m_LShr(m_Value(BF), m_ConstantInt(CSR)),
 106                                m_ConstantInt(CSL)),
 107                          m_ConstantInt(CM)));
 108
 109   if (!Match) {
 110     // (and (shl (ashr x, #sr), #sl), #m)
 111     LogicalSR = false;
 112     Match = match(In, m_And(m_Shl(m_AShr(m_Value(BF), m_ConstantInt(CSR)),
 113                             m_ConstantInt(CSL)),
 114                       m_ConstantInt(CM)));
 115   }
 116   if (!Match) {
 117     // (and (shl x, #sl), #m)
 118     LogicalSR = true;
 119     CSR = ConstantInt::get(Type::getInt32Ty(Ctx), 0);
 120     Match = match(In, m_And(m_Shl(m_Value(BF), m_ConstantInt(CSL)),
 121                       m_ConstantInt(CM)));
 122     if (Match && NoSR0)
 123       return false;
 124   }
 125   if (!Match) {
 126     // (and (lshr x, #sr), #m)
 127     LogicalSR = true;
 128     CSL = ConstantInt::get(Type::getInt32Ty(Ctx), 0);
 129     Match = match(In, m_And(m_LShr(m_Value(BF), m_ConstantInt(CSR)),
 130                             m_ConstantInt(CM)));
 131   }
 132   if (!Match) {
 133     // (and (ashr x, #sr), #m)
 134     LogicalSR = false;
 135     CSL = ConstantInt::get(Type::getInt32Ty(Ctx), 0);
 136     Match = match(In, m_And(m_AShr(m_Value(BF), m_ConstantInt(CSR)),
 137                             m_ConstantInt(CM)));
 138   }
 139   if (!Match) {
 140     CM = nullptr;
 141     // (shl (lshr x, #sr), #sl)
 142     LogicalSR = true;
 143     Match = match(In, m_Shl(m_LShr(m_Value(BF), m_ConstantInt(CSR)),
 144                             m_ConstantInt(CSL)));
 145   }
 146   if (!Match) {
 147     CM = nullptr;
 148     // (shl (ashr x, #sr), #sl)
 149     LogicalSR = false;
 150     Match = match(In, m_Shl(m_AShr(m_Value(BF), m_ConstantInt(CSR)),
 151                             m_ConstantInt(CSL)));
 152   }
 153   if (!Match)
 154     return false;
 155
 156   Type *Ty = BF->getType();
 157   if (!Ty->isIntegerTy())
 158     return false;
 159   unsigned BW = Ty->getPrimitiveSizeInBits();
 160   if (BW != 32 && BW != 64)
 161     return false;
 162
 163   uint32_t SR = CSR->getZExtValue();
 164   uint32_t SL = CSL->getZExtValue();
 165
 166   if (!CM) {
 167     // If there was no and, and the shift left did not remove all potential
 168     // sign bits created by the shift right, then extractu cannot reproduce
 169     // this value.
 170     if (!LogicalSR && (SR > SL))
 171       return false;
 172     APInt A = APInt(BW, ~0ULL).lshr(SR).shl(SL);
 173     CM = ConstantInt::get(Ctx, A);
 174   }
 175
 176   // CM is the shifted-left mask. Shift it back right to remove the zero
 177   // bits on least-significant positions.
 178   APInt M = CM->getValue().lshr(SL);
 179   uint32_t T = M.countTrailingOnes();
 180
 181   // During the shifts some of the bits will be lost. Calculate how many
 182   // of the original value will remain after shift right and then left.
 183   uint32_t U = BW - std::max(SL, SR);
 184   // The width of the extracted field is the minimum of the original bits
 185   // that remain after the shifts and the number of contiguous 1s in the mask.
 186   uint32_t W = std::min(U, T);
 187   if (W == 0 || W == 1)
 188     return false;
 189
 190   // Check if the extracted bits are contained within the mask that it is
 191   // and-ed with. The extract operation will copy these bits, and so the
 192   // mask cannot any holes in it that would clear any of the bits of the
 193   // extracted field.
 194   if (!LogicalSR) {
 195     // If the shift right was arithmetic, it could have included some 1 bits.
 196     // It is still ok to generate extract, but only if the mask eliminates
 197     // those bits (i.e. M does not have any bits set beyond U).
 198     APInt C = APInt::getHighBitsSet(BW, BW-U);
 199     if (M.intersects(C) || !M.isMask(W))
 200       return false;
 201   } else {
 202     // Check if M starts with a contiguous sequence of W times 1 bits. Get
 203     // the low U bits of M (which eliminates the 0 bits shifted in on the
 204     // left), and check if the result is APInt's "mask":
 205     if (!M.getLoBits(U).isMask(W))
 206       return false;
 207   }
 208
 209   IRBuilder<> IRB(In);
 210   Intrinsic::ID IntId = (BW == 32) ? Intrinsic::hexagon_S2_extractu
 211                                    : Intrinsic::hexagon_S2_extractup;
 212   Module *Mod = BB->getParent()->getParent();
 213   Function *ExtF = Intrinsic::getDeclaration(Mod, IntId);
 214   Value *NewIn = IRB.CreateCall(ExtF, {BF, IRB.getInt32(W), IRB.getInt32(SR)});
 215   if (SL != 0)
 216     NewIn = IRB.CreateShl(NewIn, SL, CSL->getName());
 217   In->replaceAllUsesWith(NewIn);
 218   return true;
 219 }
 220
 221 bool HexagonGenExtract::visitBlock(BasicBlock *B) {
 222   // Depth-first, bottom-up traversal.
 223   for (auto *DTN : children<DomTreeNode*>(DT->getNode(B)))
 224     visitBlock(DTN->getBlock());
 225
 226   // Allow limiting the number of generated extracts for debugging purposes.
 227   bool HasCutoff = ExtractCutoff.getPosition();
 228   unsigned Cutoff = ExtractCutoff;
 229
 230   bool Changed = false;
 231   BasicBlock::iterator I = std::prev(B->end()), NextI, Begin = B->begin();
 232   while (true) {
 233     if (HasCutoff && (ExtractCount >= Cutoff))
 234       return Changed;
 235     bool Last = (I == Begin);
 236     if (!Last)
 237       NextI = std::prev(I);
 238     Instruction *In = &*I;
 239     bool Done = convert(In);
 240     if (HasCutoff && Done)
 241       ExtractCount++;
 242     Changed |= Done;
 243     if (Last)
 244       break;
 245     I = NextI;
 246   }
 247   return Changed;
 248 }
 249
 250 bool HexagonGenExtract::runOnFunction(Function &F) {
 251   if (skipFunction(F))
 252     return false;
 253
 254   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 255   bool Changed;
 256
 257   // Traverse the function bottom-up, to see super-expressions before their
 258   // sub-expressions.
 259   BasicBlock *Entry = GraphTraits<Function*>::getEntryNode(&F);
 260   Changed = visitBlock(Entry);
 261
 262   return Changed;
 263 }
 264
 265 FunctionPass *llvm::createHexagonGenExtract() {
 266   return new HexagonGenExtract();
 267 }