1c5707112e7635d1dd2f2cc9c4f42e79a51302ccaJia Liu//===-- MipsAnalyzeImmediate.cpp - Analyze Immediates ---------------------===// 2dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka// 3dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka// The LLVM Compiler Infrastructure 4dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka// 5dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka// This file is distributed under the University of Illinois Open Source 6dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka// License. See LICENSE.TXT for details. 7dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka// 8dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka//===----------------------------------------------------------------------===// 9dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka#include "MipsAnalyzeImmediate.h" 10dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka#include "Mips.h" 11dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka#include "llvm/Support/MathExtras.h" 12dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 13dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanakausing namespace llvm; 14dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 15dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira HatanakaMipsAnalyzeImmediate::Inst::Inst(unsigned O, unsigned I) : Opc(O), ImmOpnd(I) {} 16dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 17dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka// Add I to the instruction sequences. 18dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanakavoid MipsAnalyzeImmediate::AddInstr(InstSeqLs &SeqLs, const Inst &I) { 19dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka // Add an instruction seqeunce consisting of just I. 20dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka if (SeqLs.empty()) { 21dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka SeqLs.push_back(InstSeq(1, I)); 22dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka return; 23dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka } 24dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 25dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka for (InstSeqLs::iterator Iter = SeqLs.begin(); Iter != SeqLs.end(); ++Iter) 26dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka Iter->push_back(I); 27dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka} 28dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 29e38ec24758bf88f68159ced232c371ffe031de00Ahmed Charlesvoid MipsAnalyzeImmediate::GetInstSeqLsADDiu(uint64_t Imm, unsigned RemSize, 30dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka InstSeqLs &SeqLs) { 31e38ec24758bf88f68159ced232c371ffe031de00Ahmed Charles GetInstSeqLs((Imm + 0x8000ULL) & 0xffffffffffff0000ULL, RemSize, SeqLs); 32e38ec24758bf88f68159ced232c371ffe031de00Ahmed Charles AddInstr(SeqLs, Inst(ADDiu, Imm & 0xffffULL)); 33dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka} 34dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 35e38ec24758bf88f68159ced232c371ffe031de00Ahmed Charlesvoid MipsAnalyzeImmediate::GetInstSeqLsORi(uint64_t Imm, unsigned RemSize, 36dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka InstSeqLs &SeqLs) { 37e38ec24758bf88f68159ced232c371ffe031de00Ahmed Charles GetInstSeqLs(Imm & 0xffffffffffff0000ULL, RemSize, SeqLs); 38e38ec24758bf88f68159ced232c371ffe031de00Ahmed Charles AddInstr(SeqLs, Inst(ORi, Imm & 0xffffULL)); 39dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka} 40dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 41e38ec24758bf88f68159ced232c371ffe031de00Ahmed Charlesvoid MipsAnalyzeImmediate::GetInstSeqLsSLL(uint64_t Imm, unsigned RemSize, 42dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka InstSeqLs &SeqLs) { 43dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka unsigned Shamt = CountTrailingZeros_64(Imm); 44dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka GetInstSeqLs(Imm >> Shamt, RemSize - Shamt, SeqLs); 45dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka AddInstr(SeqLs, Inst(SLL, Shamt)); 46dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka} 47dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 48e38ec24758bf88f68159ced232c371ffe031de00Ahmed Charlesvoid MipsAnalyzeImmediate::GetInstSeqLs(uint64_t Imm, unsigned RemSize, 49dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka InstSeqLs &SeqLs) { 50e38ec24758bf88f68159ced232c371ffe031de00Ahmed Charles uint64_t MaskedImm = Imm & (0xffffffffffffffffULL >> (64 - Size)); 51dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 52dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka // Do nothing if Imm is 0. 53dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka if (!MaskedImm) 54dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka return; 55dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 56dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka // A single ADDiu will do if RemSize <= 16. 57dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka if (RemSize <= 16) { 58dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka AddInstr(SeqLs, Inst(ADDiu, MaskedImm)); 59dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka return; 60dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka } 61dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 62dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka // Shift if the lower 16-bit is cleared. 63dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka if (!(Imm & 0xffff)) { 64dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka GetInstSeqLsSLL(Imm, RemSize, SeqLs); 65dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka return; 66dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka } 67dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 68dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka GetInstSeqLsADDiu(Imm, RemSize, SeqLs); 69dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 70dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka // If bit 15 is cleared, it doesn't make a difference whether the last 71dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka // instruction is an ADDiu or ORi. In that case, do not call GetInstSeqLsORi. 72dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka if (Imm & 0x8000) { 73dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka InstSeqLs SeqLsORi; 74dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka GetInstSeqLsORi(Imm, RemSize, SeqLsORi); 75dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka SeqLs.insert(SeqLs.end(), SeqLsORi.begin(), SeqLsORi.end()); 76dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka } 77dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka} 78dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 79dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka// Replace a ADDiu & SLL pair with a LUi. 80bb481f882093fb738d2bb15610c79364bada5496Jia Liu// e.g. the following two instructions 81dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka// ADDiu 0x0111 82dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka// SLL 18 83dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka// are replaced with 84dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka// LUi 0x444 85dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanakavoid MipsAnalyzeImmediate::ReplaceADDiuSLLWithLUi(InstSeq &Seq) { 86dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka // Check if the first two instructions are ADDiu and SLL and the shift amount 87dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka // is at least 16. 88dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka if ((Seq.size() < 2) || (Seq[0].Opc != ADDiu) || 89dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka (Seq[1].Opc != SLL) || (Seq[1].ImmOpnd < 16)) 90dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka return; 91dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 92dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka // Sign-extend and shift operand of ADDiu and see if it still fits in 16-bit. 935990bd7ba645d6fd067d9f015f4f48a9b8bf872bAkira Hatanaka int64_t Imm = SignExtend64<16>(Seq[0].ImmOpnd); 941144af3c9b4da48cd581156e05b24261c8de366aRichard Smith int64_t ShiftedImm = (uint64_t)Imm << (Seq[1].ImmOpnd - 16); 95dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 96dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka if (!isInt<16>(ShiftedImm)) 97dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka return; 98dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 99dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka // Replace the first instruction and erase the second. 100dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka Seq[0].Opc = LUi; 101dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka Seq[0].ImmOpnd = (unsigned)(ShiftedImm & 0xffff); 102dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka Seq.erase(Seq.begin() + 1); 103dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka} 104dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 105dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanakavoid MipsAnalyzeImmediate::GetShortestSeq(InstSeqLs &SeqLs, InstSeq &Insts) { 106dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka InstSeqLs::iterator ShortestSeq = SeqLs.end(); 107dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka // The length of an instruction sequence is at most 7. 108dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka unsigned ShortestLength = 8; 109dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 110dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka for (InstSeqLs::iterator S = SeqLs.begin(); S != SeqLs.end(); ++S) { 111dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka ReplaceADDiuSLLWithLUi(*S); 112dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka assert(S->size() <= 7); 113dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 114dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka if (S->size() < ShortestLength) { 115dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka ShortestSeq = S; 116dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka ShortestLength = S->size(); 117dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka } 118dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka } 119dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 120dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka Insts.clear(); 121dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka Insts.append(ShortestSeq->begin(), ShortestSeq->end()); 122dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka} 123dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 124dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanakaconst MipsAnalyzeImmediate::InstSeq 125e38ec24758bf88f68159ced232c371ffe031de00Ahmed Charles&MipsAnalyzeImmediate::Analyze(uint64_t Imm, unsigned Size, 126dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka bool LastInstrIsADDiu) { 127dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka this->Size = Size; 128dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 129dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka if (Size == 32) { 130dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka ADDiu = Mips::ADDiu; 131dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka ORi = Mips::ORi; 132dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka SLL = Mips::SLL; 133dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka LUi = Mips::LUi; 134dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka } else { 135dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka ADDiu = Mips::DADDiu; 136dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka ORi = Mips::ORi64; 137dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka SLL = Mips::DSLL; 138dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka LUi = Mips::LUi64; 139dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka } 140dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 141dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka InstSeqLs SeqLs; 142dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 143dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka // Get the list of instruction sequences. 144dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka if (LastInstrIsADDiu | !Imm) 145dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka GetInstSeqLsADDiu(Imm, Size, SeqLs); 146dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka else 147dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka GetInstSeqLs(Imm, Size, SeqLs); 148dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 149dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka // Set Insts to the shortest instruction sequence. 150dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka GetShortestSeq(SeqLs, Insts); 151dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka 152bb481f882093fb738d2bb15610c79364bada5496Jia Liu return Insts; 153dc81eae9d276b83b5d5e2f9b53ddbd5267cfcb8eAkira Hatanaka} 154