X86AsmInstrumentation.cpp: Dissolve initializer-ranged-for. MSC17 disliked it.
[oota-llvm.git] / lib / Target / AArch64 / AArch64BranchRelaxation.cpp
1 //===-- AArch64BranchRelaxation.cpp - AArch64 branch relaxation -----------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 //===----------------------------------------------------------------------===//
11
12 #include "AArch64.h"
13 #include "AArch64InstrInfo.h"
14 #include "AArch64MachineFunctionInfo.h"
15 #include "AArch64Subtarget.h"
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/ADT/Statistic.h"
18 #include "llvm/CodeGen/MachineFunctionPass.h"
19 #include "llvm/CodeGen/MachineInstrBuilder.h"
20 #include "llvm/Support/CommandLine.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/ErrorHandling.h"
23 #include "llvm/Support/Format.h"
24 #include "llvm/Support/raw_ostream.h"
25 using namespace llvm;
26
27 #define DEBUG_TYPE "aarch64-branch-relax"
28
29 static cl::opt<bool>
30 BranchRelaxation("aarch64-branch-relax", cl::Hidden, cl::init(true),
31                  cl::desc("Relax out of range conditional branches"));
32
33 static cl::opt<unsigned>
34 TBZDisplacementBits("aarch64-tbz-offset-bits", cl::Hidden, cl::init(14),
35                     cl::desc("Restrict range of TB[N]Z instructions (DEBUG)"));
36
37 static cl::opt<unsigned>
38 CBZDisplacementBits("aarch64-cbz-offset-bits", cl::Hidden, cl::init(19),
39                     cl::desc("Restrict range of CB[N]Z instructions (DEBUG)"));
40
41 static cl::opt<unsigned>
42 BCCDisplacementBits("aarch64-bcc-offset-bits", cl::Hidden, cl::init(19),
43                     cl::desc("Restrict range of Bcc instructions (DEBUG)"));
44
45 STATISTIC(NumSplit, "Number of basic blocks split");
46 STATISTIC(NumRelaxed, "Number of conditional branches relaxed");
47
48 namespace {
49 class AArch64BranchRelaxation : public MachineFunctionPass {
50   /// BasicBlockInfo - Information about the offset and size of a single
51   /// basic block.
52   struct BasicBlockInfo {
53     /// Offset - Distance from the beginning of the function to the beginning
54     /// of this basic block.
55     ///
56     /// The offset is always aligned as required by the basic block.
57     unsigned Offset;
58
59     /// Size - Size of the basic block in bytes.  If the block contains
60     /// inline assembly, this is a worst case estimate.
61     ///
62     /// The size does not include any alignment padding whether from the
63     /// beginning of the block, or from an aligned jump table at the end.
64     unsigned Size;
65
66     BasicBlockInfo() : Offset(0), Size(0) {}
67
68     /// Compute the offset immediately following this block.  If LogAlign is
69     /// specified, return the offset the successor block will get if it has
70     /// this alignment.
71     unsigned postOffset(unsigned LogAlign = 0) const {
72       unsigned PO = Offset + Size;
73       unsigned Align = 1 << LogAlign;
74       return (PO + Align - 1) / Align * Align;
75     }
76   };
77
78   SmallVector<BasicBlockInfo, 16> BlockInfo;
79
80   MachineFunction *MF;
81   const AArch64InstrInfo *TII;
82
83   bool relaxBranchInstructions();
84   void scanFunction();
85   MachineBasicBlock *splitBlockBeforeInstr(MachineInstr *MI);
86   void adjustBlockOffsets(MachineBasicBlock &MBB);
87   bool isBlockInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp);
88   bool fixupConditionalBranch(MachineInstr *MI);
89   void computeBlockSize(const MachineBasicBlock &MBB);
90   unsigned getInstrOffset(MachineInstr *MI) const;
91   void dumpBBs();
92   void verify();
93
94 public:
95   static char ID;
96   AArch64BranchRelaxation() : MachineFunctionPass(ID) {}
97
98   bool runOnMachineFunction(MachineFunction &MF) override;
99
100   const char *getPassName() const override {
101     return "AArch64 branch relaxation pass";
102   }
103 };
104 char AArch64BranchRelaxation::ID = 0;
105 }
106
107 /// verify - check BBOffsets, BBSizes, alignment of islands
108 void AArch64BranchRelaxation::verify() {
109 #ifndef NDEBUG
110   unsigned PrevNum = MF->begin()->getNumber();
111   for (MachineBasicBlock &MBB : *MF) {
112     unsigned Align = MBB.getAlignment();
113     unsigned Num = MBB.getNumber();
114     assert(BlockInfo[Num].Offset % (1u << Align) == 0);
115     assert(!Num || BlockInfo[PrevNum].postOffset() <= BlockInfo[Num].Offset);
116     PrevNum = Num;
117   }
118 #endif
119 }
120
121 /// print block size and offset information - debugging
122 void AArch64BranchRelaxation::dumpBBs() {
123   for (auto &MBB : *MF) {
124     const BasicBlockInfo &BBI = BlockInfo[MBB.getNumber()];
125     dbgs() << format("BB#%u\toffset=%08x\t", MBB.getNumber(), BBI.Offset)
126            << format("size=%#x\n", BBI.Size);
127   }
128 }
129
130 /// BBHasFallthrough - Return true if the specified basic block can fallthrough
131 /// into the block immediately after it.
132 static bool BBHasFallthrough(MachineBasicBlock *MBB) {
133   // Get the next machine basic block in the function.
134   MachineFunction::iterator MBBI = MBB;
135   // Can't fall off end of function.
136   MachineBasicBlock *NextBB = std::next(MBBI);
137   if (NextBB == MBB->getParent()->end())
138     return false;
139
140   for (MachineBasicBlock *S : MBB->successors())
141     if (S == NextBB)
142       return true;
143
144   return false;
145 }
146
147 /// scanFunction - Do the initial scan of the function, building up
148 /// information about each block.
149 void AArch64BranchRelaxation::scanFunction() {
150   BlockInfo.clear();
151   BlockInfo.resize(MF->getNumBlockIDs());
152
153   // First thing, compute the size of all basic blocks, and see if the function
154   // has any inline assembly in it. If so, we have to be conservative about
155   // alignment assumptions, as we don't know for sure the size of any
156   // instructions in the inline assembly.
157   for (MachineBasicBlock &MBB : *MF)
158     computeBlockSize(MBB);
159
160   // Compute block offsets and known bits.
161   adjustBlockOffsets(*MF->begin());
162 }
163
164 /// computeBlockSize - Compute the size for MBB.
165 /// This function updates BlockInfo directly.
166 void AArch64BranchRelaxation::computeBlockSize(const MachineBasicBlock &MBB) {
167   unsigned Size = 0;
168   for (const MachineInstr &MI : MBB)
169     Size += TII->GetInstSizeInBytes(&MI);
170   BlockInfo[MBB.getNumber()].Size = Size;
171 }
172
173 /// getInstrOffset - Return the current offset of the specified machine
174 /// instruction from the start of the function.  This offset changes as stuff is
175 /// moved around inside the function.
176 unsigned AArch64BranchRelaxation::getInstrOffset(MachineInstr *MI) const {
177   MachineBasicBlock *MBB = MI->getParent();
178
179   // The offset is composed of two things: the sum of the sizes of all MBB's
180   // before this instruction's block, and the offset from the start of the block
181   // it is in.
182   unsigned Offset = BlockInfo[MBB->getNumber()].Offset;
183
184   // Sum instructions before MI in MBB.
185   for (MachineBasicBlock::iterator I = MBB->begin(); &*I != MI; ++I) {
186     assert(I != MBB->end() && "Didn't find MI in its own basic block?");
187     Offset += TII->GetInstSizeInBytes(I);
188   }
189   return Offset;
190 }
191
192 void AArch64BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start) {
193   unsigned PrevNum = Start.getNumber();
194   for (auto &MBB : make_range(MachineFunction::iterator(Start), MF->end())) {
195     unsigned Num = MBB.getNumber();
196     if (!Num) // block zero is never changed from offset zero.
197       continue;
198     // Get the offset and known bits at the end of the layout predecessor.
199     // Include the alignment of the current block.
200     unsigned LogAlign = MBB.getAlignment();
201     BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(LogAlign);
202     PrevNum = Num;
203   }
204 }
205
206 /// Split the basic block containing MI into two blocks, which are joined by
207 /// an unconditional branch.  Update data structures and renumber blocks to
208 /// account for this change and returns the newly created block.
209 /// NOTE: Successor list of the original BB is out of date after this function,
210 /// and must be updated by the caller! Other transforms follow using this
211 /// utility function, so no point updating now rather than waiting.
212 MachineBasicBlock *
213 AArch64BranchRelaxation::splitBlockBeforeInstr(MachineInstr *MI) {
214   MachineBasicBlock *OrigBB = MI->getParent();
215
216   // Create a new MBB for the code after the OrigBB.
217   MachineBasicBlock *NewBB =
218       MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
219   MachineFunction::iterator MBBI = OrigBB;
220   ++MBBI;
221   MF->insert(MBBI, NewBB);
222
223   // Splice the instructions starting with MI over to NewBB.
224   NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());
225
226   // Add an unconditional branch from OrigBB to NewBB.
227   // Note the new unconditional branch is not being recorded.
228   // There doesn't seem to be meaningful DebugInfo available; this doesn't
229   // correspond to anything in the source.
230   BuildMI(OrigBB, DebugLoc(), TII->get(AArch64::B)).addMBB(NewBB);
231
232   // Insert an entry into BlockInfo to align it properly with the block numbers.
233   BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
234
235   // Figure out how large the OrigBB is.  As the first half of the original
236   // block, it cannot contain a tablejump.  The size includes
237   // the new jump we added.  (It should be possible to do this without
238   // recounting everything, but it's very confusing, and this is rarely
239   // executed.)
240   computeBlockSize(*OrigBB);
241
242   // Figure out how large the NewMBB is.  As the second half of the original
243   // block, it may contain a tablejump.
244   computeBlockSize(*NewBB);
245
246   // All BBOffsets following these blocks must be modified.
247   adjustBlockOffsets(*OrigBB);
248
249   ++NumSplit;
250
251   return NewBB;
252 }
253
254 /// isBlockInRange - Returns true if the distance between specific MI and
255 /// specific BB can fit in MI's displacement field.
256 bool AArch64BranchRelaxation::isBlockInRange(MachineInstr *MI,
257                                              MachineBasicBlock *DestBB,
258                                              unsigned Bits) {
259   unsigned MaxOffs = ((1 << (Bits - 1)) - 1) << 2;
260   unsigned BrOffset = getInstrOffset(MI);
261   unsigned DestOffset = BlockInfo[DestBB->getNumber()].Offset;
262
263   DEBUG(dbgs() << "Branch of destination BB#" << DestBB->getNumber()
264                << " from BB#" << MI->getParent()->getNumber()
265                << " max delta=" << MaxOffs << " from " << getInstrOffset(MI)
266                << " to " << DestOffset << " offset "
267                << int(DestOffset - BrOffset) << "\t" << *MI);
268
269   // Branch before the Dest.
270   if (BrOffset <= DestOffset)
271     return (DestOffset - BrOffset <= MaxOffs);
272   return (BrOffset - DestOffset <= MaxOffs);
273 }
274
275 static bool isConditionalBranch(unsigned Opc) {
276   switch (Opc) {
277   default:
278     return false;
279   case AArch64::TBZW:
280   case AArch64::TBNZW:
281   case AArch64::TBZX:
282   case AArch64::TBNZX:
283   case AArch64::CBZW:
284   case AArch64::CBNZW:
285   case AArch64::CBZX:
286   case AArch64::CBNZX:
287   case AArch64::Bcc:
288     return true;
289   }
290 }
291
292 static MachineBasicBlock *getDestBlock(MachineInstr *MI) {
293   switch (MI->getOpcode()) {
294   default:
295     llvm_unreachable("unexpected opcode!");
296   case AArch64::TBZW:
297   case AArch64::TBNZW:
298   case AArch64::TBZX:
299   case AArch64::TBNZX:
300     return MI->getOperand(2).getMBB();
301   case AArch64::CBZW:
302   case AArch64::CBNZW:
303   case AArch64::CBZX:
304   case AArch64::CBNZX:
305   case AArch64::Bcc:
306     return MI->getOperand(1).getMBB();
307   }
308 }
309
310 static unsigned getOppositeConditionOpcode(unsigned Opc) {
311   switch (Opc) {
312   default:
313     llvm_unreachable("unexpected opcode!");
314   case AArch64::TBNZW:   return AArch64::TBZW;
315   case AArch64::TBNZX:   return AArch64::TBZX;
316   case AArch64::TBZW:    return AArch64::TBNZW;
317   case AArch64::TBZX:    return AArch64::TBNZX;
318   case AArch64::CBNZW:   return AArch64::CBZW;
319   case AArch64::CBNZX:   return AArch64::CBZX;
320   case AArch64::CBZW:    return AArch64::CBNZW;
321   case AArch64::CBZX:    return AArch64::CBNZX;
322   case AArch64::Bcc:     return AArch64::Bcc; // Condition is an operand for Bcc.
323   }
324 }
325
326 static unsigned getBranchDisplacementBits(unsigned Opc) {
327   switch (Opc) {
328   default:
329     llvm_unreachable("unexpected opcode!");
330   case AArch64::TBNZW:
331   case AArch64::TBZW:
332   case AArch64::TBNZX:
333   case AArch64::TBZX:
334     return TBZDisplacementBits;
335   case AArch64::CBNZW:
336   case AArch64::CBZW:
337   case AArch64::CBNZX:
338   case AArch64::CBZX:
339     return CBZDisplacementBits;
340   case AArch64::Bcc:
341     return BCCDisplacementBits;
342   }
343 }
344
345 static inline void invertBccCondition(MachineInstr *MI) {
346   assert(MI->getOpcode() == AArch64::Bcc && "Unexpected opcode!");
347   AArch64CC::CondCode CC = (AArch64CC::CondCode)MI->getOperand(0).getImm();
348   CC = AArch64CC::getInvertedCondCode(CC);
349   MI->getOperand(0).setImm((int64_t)CC);
350 }
351
352 /// fixupConditionalBranch - Fix up a conditional branch whose destination is
353 /// too far away to fit in its displacement field. It is converted to an inverse
354 /// conditional branch + an unconditional branch to the destination.
355 bool AArch64BranchRelaxation::fixupConditionalBranch(MachineInstr *MI) {
356   MachineBasicBlock *DestBB = getDestBlock(MI);
357
358   // Add an unconditional branch to the destination and invert the branch
359   // condition to jump over it:
360   // tbz L1
361   // =>
362   // tbnz L2
363   // b   L1
364   // L2:
365
366   // If the branch is at the end of its MBB and that has a fall-through block,
367   // direct the updated conditional branch to the fall-through block. Otherwise,
368   // split the MBB before the next instruction.
369   MachineBasicBlock *MBB = MI->getParent();
370   MachineInstr *BMI = &MBB->back();
371   bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB);
372
373   if (BMI != MI) {
374     if (std::next(MachineBasicBlock::iterator(MI)) ==
375             std::prev(MBB->getLastNonDebugInstr()) &&
376         BMI->getOpcode() == AArch64::B) {
377       // Last MI in the BB is an unconditional branch. Can we simply invert the
378       // condition and swap destinations:
379       // beq L1
380       // b   L2
381       // =>
382       // bne L2
383       // b   L1
384       MachineBasicBlock *NewDest = BMI->getOperand(0).getMBB();
385       if (isBlockInRange(MI, NewDest,
386                          getBranchDisplacementBits(MI->getOpcode()))) {
387         DEBUG(dbgs() << "  Invert condition and swap its destination with "
388                      << *BMI);
389         BMI->getOperand(0).setMBB(DestBB);
390         unsigned OpNum = (MI->getOpcode() == AArch64::TBZW ||
391                           MI->getOpcode() == AArch64::TBNZW ||
392                           MI->getOpcode() == AArch64::TBZX ||
393                           MI->getOpcode() == AArch64::TBNZX)
394                              ? 2
395                              : 1;
396         MI->getOperand(OpNum).setMBB(NewDest);
397         MI->setDesc(TII->get(getOppositeConditionOpcode(MI->getOpcode())));
398         if (MI->getOpcode() == AArch64::Bcc)
399           invertBccCondition(MI);
400         return true;
401       }
402     }
403   }
404
405   if (NeedSplit) {
406     // Analyze the branch so we know how to update the successor lists.
407     MachineBasicBlock *TBB, *FBB;
408     SmallVector<MachineOperand, 2> Cond;
409     TII->AnalyzeBranch(*MBB, TBB, FBB, Cond, false);
410
411     MachineBasicBlock *NewBB = splitBlockBeforeInstr(MI);
412     // No need for the branch to the next block. We're adding an unconditional
413     // branch to the destination.
414     int delta = TII->GetInstSizeInBytes(&MBB->back());
415     BlockInfo[MBB->getNumber()].Size -= delta;
416     MBB->back().eraseFromParent();
417     // BlockInfo[SplitBB].Offset is wrong temporarily, fixed below
418
419     // Update the successor lists according to the transformation to follow.
420     // Do it here since if there's no split, no update is needed.
421     MBB->replaceSuccessor(FBB, NewBB);
422     NewBB->addSuccessor(FBB);
423   }
424   MachineBasicBlock *NextBB = std::next(MachineFunction::iterator(MBB));
425
426   DEBUG(dbgs() << "  Insert B to BB#" << DestBB->getNumber()
427                << ", invert condition and change dest. to BB#"
428                << NextBB->getNumber() << "\n");
429
430   // Insert a new conditional branch and a new unconditional branch.
431   MachineInstrBuilder MIB = BuildMI(
432       MBB, DebugLoc(), TII->get(getOppositeConditionOpcode(MI->getOpcode())))
433                                 .addOperand(MI->getOperand(0));
434   if (MI->getOpcode() == AArch64::TBZW || MI->getOpcode() == AArch64::TBNZW ||
435       MI->getOpcode() == AArch64::TBZX || MI->getOpcode() == AArch64::TBNZX)
436     MIB.addOperand(MI->getOperand(1));
437   if (MI->getOpcode() == AArch64::Bcc)
438     invertBccCondition(MIB);
439   MIB.addMBB(NextBB);
440   BlockInfo[MBB->getNumber()].Size += TII->GetInstSizeInBytes(&MBB->back());
441   BuildMI(MBB, DebugLoc(), TII->get(AArch64::B)).addMBB(DestBB);
442   BlockInfo[MBB->getNumber()].Size += TII->GetInstSizeInBytes(&MBB->back());
443
444   // Remove the old conditional branch.  It may or may not still be in MBB.
445   BlockInfo[MI->getParent()->getNumber()].Size -= TII->GetInstSizeInBytes(MI);
446   MI->eraseFromParent();
447
448   // Finally, keep the block offsets up to date.
449   adjustBlockOffsets(*MBB);
450   return true;
451 }
452
453 bool AArch64BranchRelaxation::relaxBranchInstructions() {
454   bool Changed = false;
455   // Relaxing branches involves creating new basic blocks, so re-eval
456   // end() for termination.
457   for (auto &MBB : *MF) {
458     MachineInstr *MI = MBB.getFirstTerminator();
459     if (isConditionalBranch(MI->getOpcode()) &&
460         !isBlockInRange(MI, getDestBlock(MI),
461                         getBranchDisplacementBits(MI->getOpcode()))) {
462       fixupConditionalBranch(MI);
463       ++NumRelaxed;
464       Changed = true;
465     }
466   }
467   return Changed;
468 }
469
470 bool AArch64BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
471   MF = &mf;
472
473   // If the pass is disabled, just bail early.
474   if (!BranchRelaxation)
475     return false;
476
477   DEBUG(dbgs() << "***** AArch64BranchRelaxation *****\n");
478
479   TII = (const AArch64InstrInfo *)MF->getTarget()
480             .getSubtargetImpl()
481             ->getInstrInfo();
482
483   // Renumber all of the machine basic blocks in the function, guaranteeing that
484   // the numbers agree with the position of the block in the function.
485   MF->RenumberBlocks();
486
487   // Do the initial scan of the function, building up information about the
488   // sizes of each block.
489   scanFunction();
490
491   DEBUG(dbgs() << "  Basic blocks before relaxation\n");
492   DEBUG(dumpBBs());
493
494   bool MadeChange = false;
495   while (relaxBranchInstructions())
496     MadeChange = true;
497
498   // After a while, this might be made debug-only, but it is not expensive.
499   verify();
500
501   DEBUG(dbgs() << "  Basic blocks after relaxation\n");
502   DEBUG(dbgs() << '\n'; dumpBBs());
503
504   BlockInfo.clear();
505
506   return MadeChange;
507 }
508
509 /// createAArch64BranchRelaxation - returns an instance of the constpool
510 /// island pass.
511 FunctionPass *llvm::createAArch64BranchRelaxation() {
512   return new AArch64BranchRelaxation();
513 }