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