From: Peter Collingbourne Date: Thu, 21 May 2015 23:20:55 +0000 (+0000) Subject: Revert r237590, "ARM: allow jump tables to be placed as constant islands." X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=66811d9817cd683e5f382705e98e6262f62dcb97;hp=41cf9ae1b8900610fdf422f62913c6885906ddc2 Revert r237590, "ARM: allow jump tables to be placed as constant islands." Caused a miscompile of the Android port of Chromium, details forthcoming. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@237972 91177308-0d34-0410-b5e6-96231b3b80d8 --- diff --git a/lib/Target/ARM/ARMAsmPrinter.cpp b/lib/Target/ARM/ARMAsmPrinter.cpp index 8cb553feb68..86ef4804f76 100644 --- a/lib/Target/ARM/ARMAsmPrinter.cpp +++ b/lib/Target/ARM/ARMAsmPrinter.cpp @@ -922,14 +922,17 @@ EmitMachineConstantPoolValue(MachineConstantPoolValue *MCPV) { OutStreamer->EmitValue(Expr, Size); } -void ARMAsmPrinter::EmitJumpTableAddrs(const MachineInstr *MI) { - const MachineOperand &MO1 = MI->getOperand(1); +void ARMAsmPrinter::EmitJumpTable(const MachineInstr *MI) { + unsigned Opcode = MI->getOpcode(); + int OpNum = 1; + if (Opcode == ARM::BR_JTadd) + OpNum = 2; + else if (Opcode == ARM::BR_JTm) + OpNum = 3; + + const MachineOperand &MO1 = MI->getOperand(OpNum); unsigned JTI = MO1.getIndex(); - // Make sure the Thumb jump table is 4-byte aligned. This will be a nop for - // ARM mode tables. - EmitAlignment(2); - // Emit a label for the jump table. MCSymbol *JTISymbol = GetARMJTIPICJumpTableLabel(JTI); OutStreamer->EmitLabel(JTISymbol); @@ -969,8 +972,10 @@ void ARMAsmPrinter::EmitJumpTableAddrs(const MachineInstr *MI) { OutStreamer->EmitDataRegion(MCDR_DataRegionEnd); } -void ARMAsmPrinter::EmitJumpTableInsts(const MachineInstr *MI) { - const MachineOperand &MO1 = MI->getOperand(1); +void ARMAsmPrinter::EmitJump2Table(const MachineInstr *MI) { + unsigned Opcode = MI->getOpcode(); + int OpNum = (Opcode == ARM::t2BR_JT) ? 2 : 1; + const MachineOperand &MO1 = MI->getOperand(OpNum); unsigned JTI = MO1.getIndex(); MCSymbol *JTISymbol = GetARMJTIPICJumpTableLabel(JTI); @@ -980,56 +985,42 @@ void ARMAsmPrinter::EmitJumpTableInsts(const MachineInstr *MI) { const MachineJumpTableInfo *MJTI = MF->getJumpTableInfo(); const std::vector &JT = MJTI->getJumpTables(); const std::vector &JTBBs = JT[JTI].MBBs; + unsigned OffsetWidth = 4; + if (MI->getOpcode() == ARM::t2TBB_JT) { + OffsetWidth = 1; + // Mark the jump table as data-in-code. + OutStreamer->EmitDataRegion(MCDR_DataRegionJT8); + } else if (MI->getOpcode() == ARM::t2TBH_JT) { + OffsetWidth = 2; + // Mark the jump table as data-in-code. + OutStreamer->EmitDataRegion(MCDR_DataRegionJT16); + } for (unsigned i = 0, e = JTBBs.size(); i != e; ++i) { MachineBasicBlock *MBB = JTBBs[i]; const MCExpr *MBBSymbolExpr = MCSymbolRefExpr::Create(MBB->getSymbol(), OutContext); // If this isn't a TBB or TBH, the entries are direct branch instructions. - EmitToStreamer(*OutStreamer, MCInstBuilder(ARM::t2B) + if (OffsetWidth == 4) { + EmitToStreamer(*OutStreamer, MCInstBuilder(ARM::t2B) .addExpr(MBBSymbolExpr) .addImm(ARMCC::AL) .addReg(0)); - } -} - -void ARMAsmPrinter::EmitJumpTableTBInst(const MachineInstr *MI, - unsigned OffsetWidth) { - assert((OffsetWidth == 1 || OffsetWidth == 2) && "invalid tbb/tbh width"); - const MachineOperand &MO1 = MI->getOperand(1); - unsigned JTI = MO1.getIndex(); - - MCSymbol *JTISymbol = GetARMJTIPICJumpTableLabel(JTI); - OutStreamer->EmitLabel(JTISymbol); - - // Emit each entry of the table. - const MachineJumpTableInfo *MJTI = MF->getJumpTableInfo(); - const std::vector &JT = MJTI->getJumpTables(); - const std::vector &JTBBs = JT[JTI].MBBs; - - // Mark the jump table as data-in-code. - OutStreamer->EmitDataRegion(OffsetWidth == 1 ? MCDR_DataRegionJT8 - : MCDR_DataRegionJT16); - - for (auto MBB : JTBBs) { - const MCExpr *MBBSymbolExpr = MCSymbolRefExpr::Create(MBB->getSymbol(), - OutContext); + continue; + } // Otherwise it's an offset from the dispatch instruction. Construct an // MCExpr for the entry. We want a value of the form: - // (BasicBlockAddr - TBBInstAddr + 4) / 2 + // (BasicBlockAddr - TableBeginAddr) / 2 // // For example, a TBB table with entries jumping to basic blocks BB0 and BB1 // would look like: // LJTI_0_0: - // .byte (LBB0 - (LCPI0_0 + 4)) / 2 - // .byte (LBB1 - (LCPI0_0 + 4)) / 2 - // where LCPI0_0 is a label defined just before the TBB instruction using - // this table. - MCSymbol *TBInstPC = GetCPISymbol(MI->getOperand(0).getImm()); - const MCExpr *Expr = MCBinaryExpr::CreateAdd( - MCSymbolRefExpr::Create(TBInstPC, OutContext), - MCConstantExpr::Create(4, OutContext), OutContext); - Expr = MCBinaryExpr::CreateSub(MBBSymbolExpr, Expr, OutContext); + // .byte (LBB0 - LJTI_0_0) / 2 + // .byte (LBB1 - LJTI_0_0) / 2 + const MCExpr *Expr = + MCBinaryExpr::CreateSub(MBBSymbolExpr, + MCSymbolRefExpr::Create(JTISymbol, OutContext), + OutContext); Expr = MCBinaryExpr::CreateDiv(Expr, MCConstantExpr::Create(2, OutContext), OutContext); OutStreamer->EmitValue(Expr, OffsetWidth); @@ -1037,10 +1028,8 @@ void ARMAsmPrinter::EmitJumpTableTBInst(const MachineInstr *MI, // Mark the end of jump table data-in-code region. 32-bit offsets use // actual branch instructions here, so we don't mark those as a data-region // at all. - OutStreamer->EmitDataRegion(MCDR_DataRegionEnd); - - // Make sure the next instruction is 2-byte aligned. - EmitAlignment(1); + if (OffsetWidth != 4) + OutStreamer->EmitDataRegion(MCDR_DataRegionEnd); } void ARMAsmPrinter::EmitUnwindingInstruction(const MachineInstr *MI) { @@ -1512,16 +1501,6 @@ void ARMAsmPrinter::EmitInstruction(const MachineInstr *MI) { EmitGlobalConstant(MCPE.Val.ConstVal); return; } - case ARM::JUMPTABLE_ADDRS: - EmitJumpTableAddrs(MI); - return; - case ARM::JUMPTABLE_INSTS: - EmitJumpTableInsts(MI); - return; - case ARM::JUMPTABLE_TBB: - case ARM::JUMPTABLE_TBH: - EmitJumpTableTBInst(MI, MI->getOpcode() == ARM::JUMPTABLE_TBB ? 1 : 2); - return; case ARM::t2BR_JT: { // Lower and emit the instruction itself, then the jump table following it. EmitToStreamer(*OutStreamer, MCInstBuilder(ARM::tMOVr) @@ -1530,19 +1509,37 @@ void ARMAsmPrinter::EmitInstruction(const MachineInstr *MI) { // Add predicate operands. .addImm(ARMCC::AL) .addReg(0)); + + // Output the data for the jump table itself + EmitJump2Table(MI); + return; + } + case ARM::t2TBB_JT: { + // Lower and emit the instruction itself, then the jump table following it. + EmitToStreamer(*OutStreamer, MCInstBuilder(ARM::t2TBB) + .addReg(ARM::PC) + .addReg(MI->getOperand(0).getReg()) + // Add predicate operands. + .addImm(ARMCC::AL) + .addReg(0)); + + // Output the data for the jump table itself + EmitJump2Table(MI); + // Make sure the next instruction is 2-byte aligned. + EmitAlignment(1); return; } - case ARM::t2TBB_JT: case ARM::t2TBH_JT: { - unsigned Opc = MI->getOpcode() == ARM::t2TBB_JT ? ARM::t2TBB : ARM::t2TBH; - // Lower and emit the PC label, then the instruction itself. - OutStreamer->EmitLabel(GetCPISymbol(MI->getOperand(3).getImm())); - EmitToStreamer(*OutStreamer, MCInstBuilder(Opc) - .addReg(MI->getOperand(0).getReg()) - .addReg(MI->getOperand(1).getReg()) - // Add predicate operands. - .addImm(ARMCC::AL) - .addReg(0)); + // Lower and emit the instruction itself, then the jump table following it. + EmitToStreamer(*OutStreamer, MCInstBuilder(ARM::t2TBH) + .addReg(ARM::PC) + .addReg(MI->getOperand(0).getReg()) + // Add predicate operands. + .addImm(ARMCC::AL) + .addReg(0)); + + // Output the data for the jump table itself + EmitJump2Table(MI); return; } case ARM::tBR_JTr: @@ -1562,6 +1559,13 @@ void ARMAsmPrinter::EmitInstruction(const MachineInstr *MI) { if (Opc == ARM::MOVr) TmpInst.addOperand(MCOperand::createReg(0)); EmitToStreamer(*OutStreamer, TmpInst); + + // Make sure the Thumb jump table is 4-byte aligned. + if (Opc == ARM::tMOVr) + EmitAlignment(2); + + // Output the data for the jump table itself + EmitJumpTable(MI); return; } case ARM::BR_JTm: { @@ -1585,6 +1589,9 @@ void ARMAsmPrinter::EmitInstruction(const MachineInstr *MI) { TmpInst.addOperand(MCOperand::createImm(ARMCC::AL)); TmpInst.addOperand(MCOperand::createReg(0)); EmitToStreamer(*OutStreamer, TmpInst); + + // Output the data for the jump table itself + EmitJumpTable(MI); return; } case ARM::BR_JTadd: { @@ -1599,6 +1606,9 @@ void ARMAsmPrinter::EmitInstruction(const MachineInstr *MI) { .addReg(0) // Add 's' bit operand (always reg0 for this) .addReg(0)); + + // Output the data for the jump table itself + EmitJumpTable(MI); return; } case ARM::SPACE: diff --git a/lib/Target/ARM/ARMAsmPrinter.h b/lib/Target/ARM/ARMAsmPrinter.h index a6bc3683c8b..7bfb9447818 100644 --- a/lib/Target/ARM/ARMAsmPrinter.h +++ b/lib/Target/ARM/ARMAsmPrinter.h @@ -71,9 +71,8 @@ public: void emitInlineAsmEnd(const MCSubtargetInfo &StartInfo, const MCSubtargetInfo *EndInfo) const override; - void EmitJumpTableAddrs(const MachineInstr *MI); - void EmitJumpTableInsts(const MachineInstr *MI); - void EmitJumpTableTBInst(const MachineInstr *MI, unsigned OffsetWidth); + void EmitJumpTable(const MachineInstr *MI); + void EmitJump2Table(const MachineInstr *MI); void EmitInstruction(const MachineInstr *MI) override; bool runOnMachineFunction(MachineFunction &F) override; diff --git a/lib/Target/ARM/ARMBaseInstrInfo.cpp b/lib/Target/ARM/ARMBaseInstrInfo.cpp index d1be5a87047..8bb43632572 100644 --- a/lib/Target/ARM/ARMBaseInstrInfo.cpp +++ b/lib/Target/ARM/ARMBaseInstrInfo.cpp @@ -627,10 +627,6 @@ unsigned ARMBaseInstrInfo::GetInstSizeInBytes(const MachineInstr *MI) const { case ARM::t2MOVi32imm: return 8; case ARM::CONSTPOOL_ENTRY: - case ARM::JUMPTABLE_INSTS: - case ARM::JUMPTABLE_ADDRS: - case ARM::JUMPTABLE_TBB: - case ARM::JUMPTABLE_TBH: // If this machine instr is a constant pool entry, its size is recorded as // operand #2. return MI->getOperand(2).getImm(); @@ -645,6 +641,42 @@ unsigned ARMBaseInstrInfo::GetInstSizeInBytes(const MachineInstr *MI) const { case ARM::t2Int_eh_sjlj_setjmp: case ARM::t2Int_eh_sjlj_setjmp_nofp: return 12; + case ARM::BR_JTr: + case ARM::BR_JTm: + case ARM::BR_JTadd: + case ARM::tBR_JTr: + case ARM::t2BR_JT: + case ARM::t2TBB_JT: + case ARM::t2TBH_JT: { + // These are jumptable branches, i.e. a branch followed by an inlined + // jumptable. The size is 4 + 4 * number of entries. For TBB, each + // entry is one byte; TBH two byte each. + unsigned EntrySize = (Opc == ARM::t2TBB_JT) + ? 1 : ((Opc == ARM::t2TBH_JT) ? 2 : 4); + unsigned NumOps = MCID.getNumOperands(); + MachineOperand JTOP = + MI->getOperand(NumOps - (MI->isPredicable() ? 2 : 1)); + unsigned JTI = JTOP.getIndex(); + const MachineJumpTableInfo *MJTI = MF->getJumpTableInfo(); + assert(MJTI != nullptr); + const std::vector &JT = MJTI->getJumpTables(); + assert(JTI < JT.size()); + // Thumb instructions are 2 byte aligned, but JT entries are 4 byte + // 4 aligned. The assembler / linker may add 2 byte padding just before + // the JT entries. The size does not include this padding; the + // constant islands pass does separate bookkeeping for it. + // FIXME: If we know the size of the function is less than (1 << 16) *2 + // bytes, we can use 16-bit entries instead. Then there won't be an + // alignment issue. + unsigned InstSize = (Opc == ARM::tBR_JTr || Opc == ARM::t2BR_JT) ? 2 : 4; + unsigned NumEntries = JT[JTI].MBBs.size(); + if (Opc == ARM::t2TBB_JT && (NumEntries & 1)) + // Make sure the instruction that follows TBB is 2-byte aligned. + // FIXME: Constant island pass should insert an "ALIGN" instruction + // instead. + ++NumEntries; + return NumEntries * EntrySize + InstSize; + } case ARM::SPACE: return MI->getOperand(1).getImm(); } diff --git a/lib/Target/ARM/ARMConstantIslandPass.cpp b/lib/Target/ARM/ARMConstantIslandPass.cpp index 83378daed5c..6fa5ad7d052 100644 --- a/lib/Target/ARM/ARMConstantIslandPass.cpp +++ b/lib/Target/ARM/ARMConstantIslandPass.cpp @@ -180,7 +180,9 @@ namespace { MachineInstr *MI; MachineInstr *CPEMI; MachineBasicBlock *HighWaterMark; + private: unsigned MaxDisp; + public: bool NegOk; bool IsSoImm; bool KnownAlignment; @@ -214,24 +216,12 @@ namespace { }; /// CPEntries - Keep track of all of the constant pool entry machine - /// instructions. For each original constpool index (i.e. those that existed - /// upon entry to this pass), it keeps a vector of entries. Original - /// elements are cloned as we go along; the clones are put in the vector of - /// the original element, but have distinct CPIs. - /// - /// The first half of CPEntries contains generic constants, the second half - /// contains jump tables. Use getCombinedIndex on a generic CPEMI to look up - /// which vector it will be in here. + /// instructions. For each original constpool index (i.e. those that + /// existed upon entry to this pass), it keeps a vector of entries. + /// Original elements are cloned as we go along; the clones are + /// put in the vector of the original element, but have distinct CPIs. std::vector > CPEntries; - /// Maps a JT index to the offset in CPEntries containing copies of that - /// table. The equivalent map for a CONSTPOOL_ENTRY is the identity. - DenseMap JumpTableEntryIndices; - - /// Maps a JT index to the LEA that actually uses the index to calculate its - /// base address. - DenseMap JumpTableUserIndices; - /// ImmBranch - One per immediate branch, keeping the machine instruction /// pointer, conditional or unconditional, the max displacement, /// and (if isCond is true) the corresponding unconditional branch @@ -279,8 +269,7 @@ namespace { } private: - void doInitialConstPlacement(std::vector &CPEMIs); - void doInitialJumpTablePlacement(std::vector &CPEMIs); + void doInitialPlacement(std::vector &CPEMIs); bool BBHasFallthrough(MachineBasicBlock *MBB); CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI); unsigned getCPELogAlign(const MachineInstr *CPEMI); @@ -290,7 +279,6 @@ namespace { void updateForInsertedWaterBlock(MachineBasicBlock *NewBB); void adjustBBOffsetsAfter(MachineBasicBlock *BB); bool decrementCPEReferenceCount(unsigned CPI, MachineInstr* CPEMI); - unsigned getCombinedIndex(const MachineInstr *CPEMI); int findInRangeCPEntry(CPUser& U, unsigned UserOffset); bool findAvailableWater(CPUser&U, unsigned UserOffset, water_iterator &WaterIter); @@ -425,10 +413,7 @@ bool ARMConstantIslands::runOnMachineFunction(MachineFunction &mf) { // we put them all at the end of the function. std::vector CPEMIs; if (!MCP->isEmpty()) - doInitialConstPlacement(CPEMIs); - - if (MF->getJumpTableInfo()) - doInitialJumpTablePlacement(CPEMIs); + doInitialPlacement(CPEMIs); /// The next UID to take is the first unused one. AFI->initPICLabelUId(CPEMIs.size()); @@ -493,8 +478,7 @@ bool ARMConstantIslands::runOnMachineFunction(MachineFunction &mf) { for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) { for (unsigned j = 0, je = CPEntries[i].size(); j != je; ++j) { const CPEntry & CPE = CPEntries[i][j]; - if (CPE.CPEMI && CPE.CPEMI->getOperand(1).isCPI()) - AFI->recordCPEClone(i, CPE.CPI); + AFI->recordCPEClone(i, CPE.CPI); } } @@ -504,8 +488,6 @@ bool ARMConstantIslands::runOnMachineFunction(MachineFunction &mf) { WaterList.clear(); CPUsers.clear(); CPEntries.clear(); - JumpTableEntryIndices.clear(); - JumpTableUserIndices.clear(); ImmBranches.clear(); PushPopMIs.clear(); T2JumpTables.clear(); @@ -513,10 +495,10 @@ bool ARMConstantIslands::runOnMachineFunction(MachineFunction &mf) { return MadeChange; } -/// \brief Perform the initial placement of the regular constant pool entries. -/// To start with, we put them all at the end of the function. +/// doInitialPlacement - Perform the initial placement of the constant pool +/// entries. To start with, we put them all at the end of the function. void -ARMConstantIslands::doInitialConstPlacement(std::vector &CPEMIs) { +ARMConstantIslands::doInitialPlacement(std::vector &CPEMIs) { // Create the basic block to hold the CPE's. MachineBasicBlock *BB = MF->CreateMachineBasicBlock(); MF->push_back(BB); @@ -574,66 +556,6 @@ ARMConstantIslands::doInitialConstPlacement(std::vector &CPEMIs) DEBUG(BB->dump()); } -/// \brief Do initial placement of the jump tables. Because Thumb2's TBB and TBH -/// instructions can be made more efficient if the jump table immediately -/// follows the instruction, it's best to place them immediately next to their -/// jumps to begin with. In almost all cases they'll never be moved from that -/// position. -void ARMConstantIslands::doInitialJumpTablePlacement( - std::vector &CPEMIs) { - unsigned i = CPEntries.size(); - auto MJTI = MF->getJumpTableInfo(); - const std::vector &JT = MJTI->getJumpTables(); - - MachineBasicBlock *LastCorrectlyNumberedBB = nullptr; - for (MachineBasicBlock &MBB : *MF) { - auto MI = MBB.getLastNonDebugInstr(); - - unsigned JTOpcode; - switch (MI->getOpcode()) { - default: - continue; - case ARM::BR_JTadd: - case ARM::BR_JTr: - case ARM::tBR_JTr: - case ARM::BR_JTm: - JTOpcode = ARM::JUMPTABLE_ADDRS; - break; - case ARM::t2BR_JT: - JTOpcode = ARM::JUMPTABLE_INSTS; - break; - case ARM::t2TBB_JT: - JTOpcode = ARM::JUMPTABLE_TBB; - break; - case ARM::t2TBH_JT: - JTOpcode = ARM::JUMPTABLE_TBH; - break; - } - - unsigned NumOps = MI->getDesc().getNumOperands(); - MachineOperand JTOp = - MI->getOperand(NumOps - (MI->isPredicable() ? 2 : 1)); - unsigned JTI = JTOp.getIndex(); - unsigned Size = JT[JTI].MBBs.size() * sizeof(uint32_t); - MachineBasicBlock *JumpTableBB = MF->CreateMachineBasicBlock(); - MF->insert(std::next(MachineFunction::iterator(MBB)), JumpTableBB); - MachineInstr *CPEMI = BuildMI(*JumpTableBB, JumpTableBB->begin(), - DebugLoc(), TII->get(JTOpcode)) - .addImm(i++) - .addJumpTableIndex(JTI) - .addImm(Size); - CPEMIs.push_back(CPEMI); - CPEntries.emplace_back(1, CPEntry(CPEMI, JTI)); - JumpTableEntryIndices.insert(std::make_pair(JTI, CPEntries.size() - 1)); - if (!LastCorrectlyNumberedBB) - LastCorrectlyNumberedBB = &MBB; - } - - // If we did anything then we need to renumber the subsequent blocks. - if (LastCorrectlyNumberedBB) - MF->RenumberBlocks(LastCorrectlyNumberedBB); -} - /// BBHasFallthrough - Return true if the specified basic block can fallthrough /// into the block immediately after it. bool ARMConstantIslands::BBHasFallthrough(MachineBasicBlock *MBB) { @@ -673,21 +595,9 @@ ARMConstantIslands::CPEntry /// getCPELogAlign - Returns the required alignment of the constant pool entry /// represented by CPEMI. Alignment is measured in log2(bytes) units. unsigned ARMConstantIslands::getCPELogAlign(const MachineInstr *CPEMI) { - switch (CPEMI->getOpcode()) { - case ARM::CONSTPOOL_ENTRY: - break; - case ARM::JUMPTABLE_TBB: - return 0; - case ARM::JUMPTABLE_TBH: - case ARM::JUMPTABLE_INSTS: - return 1; - case ARM::JUMPTABLE_ADDRS: - return 2; - default: - llvm_unreachable("unknown constpool entry kind"); - } + assert(CPEMI && CPEMI->getOpcode() == ARM::CONSTPOOL_ENTRY); - unsigned CPI = getCombinedIndex(CPEMI); + unsigned CPI = CPEMI->getOperand(1).getIndex(); assert(CPI < MCP->getConstants().size() && "Invalid constant pool index."); unsigned Align = MCP->getConstants()[CPI].getAlignment(); assert(isPowerOf2_32(Align) && "Invalid CPE alignment"); @@ -796,14 +706,12 @@ initializeFunctionInfo(const std::vector &CPEMIs) { if (Opc == ARM::tPUSH || Opc == ARM::tPOP_RET) PushPopMIs.push_back(I); - if (Opc == ARM::CONSTPOOL_ENTRY || Opc == ARM::JUMPTABLE_ADDRS || - Opc == ARM::JUMPTABLE_INSTS || Opc == ARM::JUMPTABLE_TBB || - Opc == ARM::JUMPTABLE_TBH) + if (Opc == ARM::CONSTPOOL_ENTRY) continue; // Scan the instructions for constant pool operands. for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) - if (I->getOperand(op).isCPI() || I->getOperand(op).isJTI()) { + if (I->getOperand(op).isCPI()) { // We found one. The addressing mode tells us the max displacement // from the PC that this instruction permits. @@ -819,7 +727,6 @@ initializeFunctionInfo(const std::vector &CPEMIs) { // Taking the address of a CP entry. case ARM::LEApcrel: - case ARM::LEApcrelJT: // This takes a SoImm, which is 8 bit immediate rotated. We'll // pretend the maximum offset is 255 * 4. Since each instruction // 4 byte wide, this is always correct. We'll check for other @@ -830,12 +737,10 @@ initializeFunctionInfo(const std::vector &CPEMIs) { IsSoImm = true; break; case ARM::t2LEApcrel: - case ARM::t2LEApcrelJT: Bits = 12; NegOk = true; break; case ARM::tLEApcrel: - case ARM::tLEApcrelJT: Bits = 8; Scale = 4; break; @@ -863,11 +768,6 @@ initializeFunctionInfo(const std::vector &CPEMIs) { // Remember that this is a user of a CP entry. unsigned CPI = I->getOperand(op).getIndex(); - if (I->getOperand(op).isJTI()) { - JumpTableUserIndices.insert(std::make_pair(CPI, CPUsers.size())); - CPI = JumpTableEntryIndices[CPI]; - } - MachineInstr *CPEMI = CPEMIs[CPI]; unsigned MaxOffs = ((1 << Bits)-1) * Scale; CPUsers.push_back(CPUser(I, CPEMI, MaxOffs, NegOk, IsSoImm)); @@ -1201,13 +1101,6 @@ bool ARMConstantIslands::decrementCPEReferenceCount(unsigned CPI, return false; } -unsigned ARMConstantIslands::getCombinedIndex(const MachineInstr *CPEMI) { - if (CPEMI->getOperand(1).isCPI()) - return CPEMI->getOperand(1).getIndex(); - - return JumpTableEntryIndices[CPEMI->getOperand(1).getIndex()]; -} - /// LookForCPEntryInRange - see if the currently referenced CPE is in range; /// if not, see if an in-range clone of the CPE is in range, and if so, /// change the data structures so the user references the clone. Returns: @@ -1227,7 +1120,7 @@ int ARMConstantIslands::findInRangeCPEntry(CPUser& U, unsigned UserOffset) } // No. Look for previously created clones of the CPE that are in range. - unsigned CPI = getCombinedIndex(CPEMI); + unsigned CPI = CPEMI->getOperand(1).getIndex(); std::vector &CPEs = CPEntries[CPI]; for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { // We already tried this one @@ -1472,7 +1365,7 @@ bool ARMConstantIslands::handleConstantPoolUser(unsigned CPUserIndex) { CPUser &U = CPUsers[CPUserIndex]; MachineInstr *UserMI = U.MI; MachineInstr *CPEMI = U.CPEMI; - unsigned CPI = getCombinedIndex(CPEMI); + unsigned CPI = CPEMI->getOperand(1).getIndex(); unsigned Size = CPEMI->getOperand(2).getImm(); // Compute this only once, it's expensive. unsigned UserOffset = getUserOffset(U); @@ -1536,17 +1429,17 @@ bool ARMConstantIslands::handleConstantPoolUser(unsigned CPUserIndex) { // Update internal data structures to account for the newly inserted MBB. updateForInsertedWaterBlock(NewIsland); + // Decrement the old entry, and remove it if refcount becomes 0. + decrementCPEReferenceCount(CPI, CPEMI); + // Now that we have an island to add the CPE to, clone the original CPE and // add it to the island. U.HighWaterMark = NewIsland; - U.CPEMI = BuildMI(NewIsland, DebugLoc(), CPEMI->getDesc()) - .addImm(ID).addOperand(CPEMI->getOperand(1)).addImm(Size); + U.CPEMI = BuildMI(NewIsland, DebugLoc(), TII->get(ARM::CONSTPOOL_ENTRY)) + .addImm(ID).addConstantPoolIndex(CPI).addImm(Size); CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1)); ++NumCPEs; - // Decrement the old entry, and remove it if refcount becomes 0. - decrementCPEReferenceCount(CPI, CPEMI); - // Mark the basic block as aligned as required by the const-pool entry. NewIsland->setAlignment(getCPELogAlign(U.CPEMI)); @@ -2024,19 +1917,6 @@ unsigned ARMConstantIslands::removeDeadDefinitions(MachineInstr *MI, return BytesRemoved; } -/// \brief Returns whether CPEMI is the first instruction in the block -/// immediately following JTMI (assumed to be a TBB or TBH terminator). If so, -/// we can switch the first register to PC and usually remove the address -/// calculation that preceeded it. -static bool jumpTableFollowsTB(MachineInstr *JTMI, MachineInstr *CPEMI) { - MachineFunction::iterator MBB = JTMI->getParent(); - MachineFunction *MF = MBB->getParent(); - ++MBB; - - return MBB != MF->end() && MBB->begin() != MBB->end() && - &*MBB->begin() == CPEMI; -} - /// optimizeThumb2JumpTables - Use tbb / tbh instructions to generate smaller /// jumptables when it's possible. bool ARMConstantIslands::optimizeThumb2JumpTables() { @@ -2075,73 +1955,37 @@ bool ARMConstantIslands::optimizeThumb2JumpTables() { break; } - if (!ByteOk && !HalfWordOk) - continue; + if (ByteOk || HalfWordOk) { + MachineBasicBlock *MBB = MI->getParent(); + unsigned BaseReg = MI->getOperand(0).getReg(); + bool BaseRegKill = MI->getOperand(0).isKill(); + if (!BaseRegKill) + continue; + unsigned IdxReg = MI->getOperand(1).getReg(); + bool IdxRegKill = MI->getOperand(1).isKill(); - MachineBasicBlock *MBB = MI->getParent(); - unsigned BaseReg = MI->getOperand(0).getReg(); - bool BaseRegKill = MI->getOperand(0).isKill(); - if (!BaseRegKill) - continue; - unsigned IdxReg = MI->getOperand(1).getReg(); - bool IdxRegKill = MI->getOperand(1).isKill(); - - DEBUG(dbgs() << "Shrink JT: " << *MI); - CPUser &User = CPUsers[JumpTableUserIndices[JTI]]; - MachineInstr *CPEMI = User.CPEMI; - unsigned Opc = ByteOk ? ARM::t2TBB_JT : ARM::t2TBH_JT; - MachineBasicBlock::iterator MI_JT = MI; - MachineInstr *NewJTMI = + DEBUG(dbgs() << "Shrink JT: " << *MI); + unsigned Opc = ByteOk ? ARM::t2TBB_JT : ARM::t2TBH_JT; + MachineBasicBlock::iterator MI_JT = MI; + MachineInstr *NewJTMI = BuildMI(*MBB, MI_JT, MI->getDebugLoc(), TII->get(Opc)) - .addReg(BaseReg, getKillRegState(BaseRegKill)) - .addReg(IdxReg, getKillRegState(IdxRegKill)) - .addJumpTableIndex(JTI, JTOP.getTargetFlags()) - .addImm(CPEMI->getOperand(0).getImm()); - DEBUG(dbgs() << "BB#" << MBB->getNumber() << ": " << *NewJTMI); - - unsigned JTOpc = ByteOk ? ARM::JUMPTABLE_TBB : ARM::JUMPTABLE_TBH; - CPEMI->setDesc(TII->get(JTOpc)); - - // Now we need to determine whether the actual jump table has been moved - // from immediately after this instruction. If not, we can replace BaseReg - // with PC and probably eliminate the BaseReg calculations. - unsigned DeadSize = 0; - if (jumpTableFollowsTB(NewJTMI, User.CPEMI)) { - NewJTMI->getOperand(0).setReg(ARM::PC); - NewJTMI->getOperand(0).setIsKill(false); - - DeadSize = removeDeadDefinitions(MI, BaseReg, IdxReg); - if (!User.MI->getParent()) { - // The LEA was eliminated, the TBB instruction becomes the only new user - // of the jump table. - User.MI = NewJTMI; - User.MaxDisp = 4; - User.NegOk = false; - User.IsSoImm = false; - User.KnownAlignment = false; - } else { - // The LEA couldn't be eliminated, so we must add another CPUser to - // record the TBB or TBH use. - int CPEntryIdx = JumpTableEntryIndices[JTI]; - auto &CPEs = CPEntries[CPEntryIdx]; - auto Entry = std::find_if(CPEs.begin(), CPEs.end(), [&](CPEntry &E) { - return E.CPEMI == User.CPEMI; - }); - ++Entry->RefCount; - CPUsers.emplace_back(CPUser(NewJTMI, User.CPEMI, 4, false, false)); - } - } - - unsigned NewSize = TII->GetInstSizeInBytes(NewJTMI); - unsigned OrigSize = TII->GetInstSizeInBytes(MI); - MI->eraseFromParent(); + .addReg(IdxReg, getKillRegState(IdxRegKill)) + .addJumpTableIndex(JTI, JTOP.getTargetFlags()); + DEBUG(dbgs() << "BB#" << MBB->getNumber() << ": " << *NewJTMI); + // FIXME: Insert an "ALIGN" instruction to ensure the next instruction + // is 2-byte aligned. For now, asm printer will fix it up. + unsigned NewSize = TII->GetInstSizeInBytes(NewJTMI); + unsigned OrigSize = TII->GetInstSizeInBytes(MI); + unsigned DeadSize = removeDeadDefinitions(MI, BaseReg, IdxReg); + MI->eraseFromParent(); - int Delta = OrigSize - NewSize + DeadSize; - BBInfo[MBB->getNumber()].Size -= Delta; - adjustBBOffsetsAfter(MBB); + int delta = OrigSize - NewSize + DeadSize; + BBInfo[MBB->getNumber()].Size -= delta; + adjustBBOffsetsAfter(MBB); - ++NumTBs; - MadeChange = true; + ++NumTBs; + MadeChange = true; + } } return MadeChange; diff --git a/lib/Target/ARM/ARMInstrInfo.td b/lib/Target/ARM/ARMInstrInfo.td index f9d4d1ef727..778fd17137f 100644 --- a/lib/Target/ARM/ARMInstrInfo.td +++ b/lib/Target/ARM/ARMInstrInfo.td @@ -1826,32 +1826,6 @@ def CONSTPOOL_ENTRY : PseudoInst<(outs), (ins cpinst_operand:$instid, cpinst_operand:$cpidx, i32imm:$size), NoItinerary, []>; -/// A jumptable consisting of direct 32-bit addresses of the destination basic -/// blocks (either absolute, or relative to the start of the jump-table in PIC -/// mode). Used mostly in ARM and Thumb-1 modes. -def JUMPTABLE_ADDRS : -PseudoInst<(outs), (ins cpinst_operand:$instid, cpinst_operand:$cpidx, - i32imm:$size), NoItinerary, []>; - -/// A jumptable consisting of 32-bit jump instructions. Used for Thumb-2 tables -/// that cannot be optimised to use TBB or TBH. -def JUMPTABLE_INSTS : -PseudoInst<(outs), (ins cpinst_operand:$instid, cpinst_operand:$cpidx, - i32imm:$size), NoItinerary, []>; - -/// A jumptable consisting of 8-bit unsigned integers representing offsets from -/// a TBB instruction. -def JUMPTABLE_TBB : -PseudoInst<(outs), (ins cpinst_operand:$instid, cpinst_operand:$cpidx, - i32imm:$size), NoItinerary, []>; - -/// A jumptable consisting of 16-bit unsigned integers representing offsets from -/// a TBH instruction. -def JUMPTABLE_TBH : -PseudoInst<(outs), (ins cpinst_operand:$instid, cpinst_operand:$cpidx, - i32imm:$size), NoItinerary, []>; - - // FIXME: Marking these as hasSideEffects is necessary to prevent machine DCE // from removing one half of the matched pairs. That breaks PEI, which assumes // these will always be in pairs, and asserts if it finds otherwise. Better way? @@ -2250,7 +2224,7 @@ let isBranch = 1, isTerminator = 1 in { [(br bb:$target)], (Bcc br_target:$target, (ops 14, zero_reg))>, Sched<[WriteBr]>; - let Size = 4, isNotDuplicable = 1, isIndirectBranch = 1 in { + let isNotDuplicable = 1, isIndirectBranch = 1 in { def BR_JTr : ARMPseudoInst<(outs), (ins GPR:$target, i32imm:$jt), 0, IIC_Br, diff --git a/lib/Target/ARM/ARMInstrThumb.td b/lib/Target/ARM/ARMInstrThumb.td index 40414da3ca8..0fecfa1319d 100644 --- a/lib/Target/ARM/ARMInstrThumb.td +++ b/lib/Target/ARM/ARMInstrThumb.td @@ -526,7 +526,6 @@ let isBranch = 1, isTerminator = 1, isBarrier = 1 in { 0, IIC_Br, [(ARMbrjt tGPR:$target, tjumptable:$jt)]>, Sched<[WriteBrTbl]> { - let Size = 2; list Predicates = [IsThumb, IsThumb1Only]; } } diff --git a/lib/Target/ARM/ARMInstrThumb2.td b/lib/Target/ARM/ARMInstrThumb2.td index 51a82c2d866..814b524b2bc 100644 --- a/lib/Target/ARM/ARMInstrThumb2.td +++ b/lib/Target/ARM/ARMInstrThumb2.td @@ -3531,20 +3531,20 @@ def t2B : T2I<(outs), (ins uncondbrtarget:$target), IIC_Br, let AsmMatchConverter = "cvtThumbBranches"; } -let Size = 4, isNotDuplicable = 1, isIndirectBranch = 1 in { +let isNotDuplicable = 1, isIndirectBranch = 1 in { def t2BR_JT : t2PseudoInst<(outs), (ins GPR:$target, GPR:$index, i32imm:$jt), 0, IIC_Br, [(ARMbr2jt GPR:$target, GPR:$index, tjumptable:$jt)]>, Sched<[WriteBr]>; -// FIXME: Add a case that can be predicated. +// FIXME: Add a non-pc based case that can be predicated. def t2TBB_JT : t2PseudoInst<(outs), - (ins GPR:$base, GPR:$index, i32imm:$jt, i32imm:$pclbl), 0, IIC_Br, []>, + (ins GPR:$index, i32imm:$jt), 0, IIC_Br, []>, Sched<[WriteBr]>; def t2TBH_JT : t2PseudoInst<(outs), - (ins GPR:$base, GPR:$index, i32imm:$jt, i32imm:$pclbl), 0, IIC_Br, []>, + (ins GPR:$index, i32imm:$jt), 0, IIC_Br, []>, Sched<[WriteBr]>; def t2TBB : T2I<(outs), (ins addrmode_tbb:$addr), IIC_Br, diff --git a/test/CodeGen/ARM/jump-table-islands.ll b/test/CodeGen/ARM/jump-table-islands.ll deleted file mode 100644 index 6b4f174c092..00000000000 --- a/test/CodeGen/ARM/jump-table-islands.ll +++ /dev/null @@ -1,40 +0,0 @@ -; RUN: llc -mtriple=armv7-apple-ios8.0 -o - %s | FileCheck %s - -%BigInt = type i5500 - -define %BigInt @test_moved_jumptable(i1 %tst, i32 %sw, %BigInt %l) { -; CHECK-LABEL: test_moved_jumptable: - -; CHECK: adr {{r[0-9]+}}, [[JUMP_TABLE:LJTI[0-9]+_[0-9]+]] -; CHECK: b [[SKIP_TABLE:LBB[0-9]+_[0-9]+]] - -; CHECK: [[JUMP_TABLE]]: -; CHECK: .data_region jt32 -; CHECK: .long LBB{{[0-9]+_[0-9]+}}-[[JUMP_TABLE]] - -; CHECK: [[SKIP_TABLE]]: -; CHECK: add pc, {{r[0-9]+}}, {{r[0-9]+}} - br i1 %tst, label %simple, label %complex - -simple: - br label %end - -complex: - switch i32 %sw, label %simple [ i32 0, label %other - i32 1, label %third - i32 5, label %end - i32 6, label %other ] - -third: - ret %BigInt 0 - -other: - call void @bar() - unreachable - -end: - %val = phi %BigInt [ %l, %complex ], [ -1, %simple ] - ret %BigInt %val -} - -declare void @bar() diff --git a/test/CodeGen/ARM/jumptable-label.ll b/test/CodeGen/ARM/jumptable-label.ll index 2ba90dc9736..49d698672f8 100644 --- a/test/CodeGen/ARM/jumptable-label.ll +++ b/test/CodeGen/ARM/jumptable-label.ll @@ -2,8 +2,8 @@ ; test that we print the label of a bb that is only used in a jump table. -; CHECK: .long [[JUMPTABLE_DEST:LBB[0-9]+_[0-9]+]] -; CHECK: [[JUMPTABLE_DEST]]: +; CHECK: .long LBB0_2 +; CHECK: LBB0_2: define i32 @calculate() { entry: diff --git a/test/CodeGen/Thumb2/constant-islands-jump-table.ll b/test/CodeGen/Thumb2/constant-islands-jump-table.ll index 5ffe1f9b09f..0dd7092291b 100644 --- a/test/CodeGen/Thumb2/constant-islands-jump-table.ll +++ b/test/CodeGen/Thumb2/constant-islands-jump-table.ll @@ -1,7 +1,7 @@ ; RUN: llc < %s -mtriple=thumbv7-linux-gnueabihf -O1 %s -o - | FileCheck %s ; CHECK-LABEL: test_jump_table: -; CHECK: b{{.*}} .LBB +; CHECK: b .LBB ; CHECK-NOT: tbh define i32 @test_jump_table(i32 %x, float %in) { diff --git a/test/CodeGen/Thumb2/thumb2-tbh.ll b/test/CodeGen/Thumb2/thumb2-tbh.ll index 0761ed589a2..a5a5ed0c8da 100644 --- a/test/CodeGen/Thumb2/thumb2-tbh.ll +++ b/test/CodeGen/Thumb2/thumb2-tbh.ll @@ -14,19 +14,9 @@ declare void @Z_fatal(i8*) noreturn nounwind declare noalias i8* @calloc(i32, i32) nounwind -; Jump tables are not anchored next to the TBB/TBH any more. Make sure the -; correct address is still calculated (i.e. via a PC-relative symbol *at* the -; TBB/TBH). define i32 @main(i32 %argc, i8** nocapture %argv) nounwind { ; CHECK-LABEL: main: -; CHECK-NOT: adr {{r[0-9]+}}, LJTI -; CHECK: [[PCREL_ANCHOR:LCPI[0-9]+_[0-9]+]]: -; CHECK-NEXT: tbb [pc, {{r[0-9]+}}] - -; CHECK: LJTI0_0: -; CHECK-NEXT: .data_region jt8 -; CHECK-NEXT: .byte (LBB{{[0-9]+_[0-9]+}}-([[PCREL_ANCHOR]]+4))/2 - +; CHECK: tbb entry: br label %bb42.i