• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- BranchRelaxation.cpp -----------------------------------------------===//
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 #include "llvm/ADT/SmallVector.h"
11 #include "llvm/ADT/Statistic.h"
12 #include "llvm/CodeGen/LivePhysRegs.h"
13 #include "llvm/CodeGen/MachineBasicBlock.h"
14 #include "llvm/CodeGen/MachineFunction.h"
15 #include "llvm/CodeGen/MachineFunctionPass.h"
16 #include "llvm/CodeGen/MachineInstr.h"
17 #include "llvm/CodeGen/RegisterScavenging.h"
18 #include "llvm/CodeGen/TargetInstrInfo.h"
19 #include "llvm/CodeGen/TargetRegisterInfo.h"
20 #include "llvm/CodeGen/TargetSubtargetInfo.h"
21 #include "llvm/Config/llvm-config.h"
22 #include "llvm/IR/DebugLoc.h"
23 #include "llvm/Pass.h"
24 #include "llvm/Support/Compiler.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Support/Format.h"
27 #include "llvm/Support/MathExtras.h"
28 #include "llvm/Support/raw_ostream.h"
29 #include <cassert>
30 #include <cstdint>
31 #include <iterator>
32 #include <memory>
33 
34 using namespace llvm;
35 
36 #define DEBUG_TYPE "branch-relaxation"
37 
38 STATISTIC(NumSplit, "Number of basic blocks split");
39 STATISTIC(NumConditionalRelaxed, "Number of conditional branches relaxed");
40 STATISTIC(NumUnconditionalRelaxed, "Number of unconditional branches relaxed");
41 
42 #define BRANCH_RELAX_NAME "Branch relaxation pass"
43 
44 namespace {
45 
46 class BranchRelaxation : public MachineFunctionPass {
47   /// BasicBlockInfo - Information about the offset and size of a single
48   /// basic block.
49   struct BasicBlockInfo {
50     /// Offset - Distance from the beginning of the function to the beginning
51     /// of this basic block.
52     ///
53     /// The offset is always aligned as required by the basic block.
54     unsigned Offset = 0;
55 
56     /// Size - Size of the basic block in bytes.  If the block contains
57     /// inline assembly, this is a worst case estimate.
58     ///
59     /// The size does not include any alignment padding whether from the
60     /// beginning of the block, or from an aligned jump table at the end.
61     unsigned Size = 0;
62 
63     BasicBlockInfo() = default;
64 
65     /// Compute the offset immediately following this block. \p MBB is the next
66     /// block.
postOffset__anon8333fdfc0111::BranchRelaxation::BasicBlockInfo67     unsigned postOffset(const MachineBasicBlock &MBB) const {
68       unsigned PO = Offset + Size;
69       unsigned Align = MBB.getAlignment();
70       if (Align == 0)
71         return PO;
72 
73       unsigned AlignAmt = 1 << Align;
74       unsigned ParentAlign = MBB.getParent()->getAlignment();
75       if (Align <= ParentAlign)
76         return PO + OffsetToAlignment(PO, AlignAmt);
77 
78       // The alignment of this MBB is larger than the function's alignment, so we
79       // can't tell whether or not it will insert nops. Assume that it will.
80       return PO + AlignAmt + OffsetToAlignment(PO, AlignAmt);
81     }
82   };
83 
84   SmallVector<BasicBlockInfo, 16> BlockInfo;
85   std::unique_ptr<RegScavenger> RS;
86   LivePhysRegs LiveRegs;
87 
88   MachineFunction *MF;
89   const TargetRegisterInfo *TRI;
90   const TargetInstrInfo *TII;
91 
92   bool relaxBranchInstructions();
93   void scanFunction();
94 
95   MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &BB);
96 
97   MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI,
98                                            MachineBasicBlock *DestBB);
99   void adjustBlockOffsets(MachineBasicBlock &Start);
100   bool isBlockInRange(const MachineInstr &MI, const MachineBasicBlock &BB) const;
101 
102   bool fixupConditionalBranch(MachineInstr &MI);
103   bool fixupUnconditionalBranch(MachineInstr &MI);
104   uint64_t computeBlockSize(const MachineBasicBlock &MBB) const;
105   unsigned getInstrOffset(const MachineInstr &MI) const;
106   void dumpBBs();
107   void verify();
108 
109 public:
110   static char ID;
111 
BranchRelaxation()112   BranchRelaxation() : MachineFunctionPass(ID) {}
113 
114   bool runOnMachineFunction(MachineFunction &MF) override;
115 
getPassName() const116   StringRef getPassName() const override { return BRANCH_RELAX_NAME; }
117 };
118 
119 } // end anonymous namespace
120 
121 char BranchRelaxation::ID = 0;
122 
123 char &llvm::BranchRelaxationPassID = BranchRelaxation::ID;
124 
INITIALIZE_PASS(BranchRelaxation,DEBUG_TYPE,BRANCH_RELAX_NAME,false,false)125 INITIALIZE_PASS(BranchRelaxation, DEBUG_TYPE, BRANCH_RELAX_NAME, false, false)
126 
127 /// verify - check BBOffsets, BBSizes, alignment of islands
128 void BranchRelaxation::verify() {
129 #ifndef NDEBUG
130   unsigned PrevNum = MF->begin()->getNumber();
131   for (MachineBasicBlock &MBB : *MF) {
132     unsigned Align = MBB.getAlignment();
133     unsigned Num = MBB.getNumber();
134     assert(BlockInfo[Num].Offset % (1u << Align) == 0);
135     assert(!Num || BlockInfo[PrevNum].postOffset(MBB) <= BlockInfo[Num].Offset);
136     assert(BlockInfo[Num].Size == computeBlockSize(MBB));
137     PrevNum = Num;
138   }
139 #endif
140 }
141 
142 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
143 /// print block size and offset information - debugging
dumpBBs()144 LLVM_DUMP_METHOD void BranchRelaxation::dumpBBs() {
145   for (auto &MBB : *MF) {
146     const BasicBlockInfo &BBI = BlockInfo[MBB.getNumber()];
147     dbgs() << format("%bb.%u\toffset=%08x\t", MBB.getNumber(), BBI.Offset)
148            << format("size=%#x\n", BBI.Size);
149   }
150 }
151 #endif
152 
153 /// scanFunction - Do the initial scan of the function, building up
154 /// information about each block.
scanFunction()155 void BranchRelaxation::scanFunction() {
156   BlockInfo.clear();
157   BlockInfo.resize(MF->getNumBlockIDs());
158 
159   // First thing, compute the size of all basic blocks, and see if the function
160   // has any inline assembly in it. If so, we have to be conservative about
161   // alignment assumptions, as we don't know for sure the size of any
162   // instructions in the inline assembly.
163   for (MachineBasicBlock &MBB : *MF)
164     BlockInfo[MBB.getNumber()].Size = computeBlockSize(MBB);
165 
166   // Compute block offsets and known bits.
167   adjustBlockOffsets(*MF->begin());
168 }
169 
170 /// computeBlockSize - Compute the size for MBB.
computeBlockSize(const MachineBasicBlock & MBB) const171 uint64_t BranchRelaxation::computeBlockSize(const MachineBasicBlock &MBB) const {
172   uint64_t Size = 0;
173   for (const MachineInstr &MI : MBB)
174     Size += TII->getInstSizeInBytes(MI);
175   return Size;
176 }
177 
178 /// getInstrOffset - Return the current offset of the specified machine
179 /// instruction from the start of the function.  This offset changes as stuff is
180 /// moved around inside the function.
getInstrOffset(const MachineInstr & MI) const181 unsigned BranchRelaxation::getInstrOffset(const MachineInstr &MI) const {
182   const MachineBasicBlock *MBB = MI.getParent();
183 
184   // The offset is composed of two things: the sum of the sizes of all MBB's
185   // before this instruction's block, and the offset from the start of the block
186   // it is in.
187   unsigned Offset = BlockInfo[MBB->getNumber()].Offset;
188 
189   // Sum instructions before MI in MBB.
190   for (MachineBasicBlock::const_iterator I = MBB->begin(); &*I != &MI; ++I) {
191     assert(I != MBB->end() && "Didn't find MI in its own basic block?");
192     Offset += TII->getInstSizeInBytes(*I);
193   }
194 
195   return Offset;
196 }
197 
adjustBlockOffsets(MachineBasicBlock & Start)198 void BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start) {
199   unsigned PrevNum = Start.getNumber();
200   for (auto &MBB : make_range(MachineFunction::iterator(Start), MF->end())) {
201     unsigned Num = MBB.getNumber();
202     if (!Num) // block zero is never changed from offset zero.
203       continue;
204     // Get the offset and known bits at the end of the layout predecessor.
205     // Include the alignment of the current block.
206     BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(MBB);
207 
208     PrevNum = Num;
209   }
210 }
211 
212 /// Insert a new empty basic block and insert it after \BB
createNewBlockAfter(MachineBasicBlock & BB)213 MachineBasicBlock *BranchRelaxation::createNewBlockAfter(MachineBasicBlock &BB) {
214   // Create a new MBB for the code after the OrigBB.
215   MachineBasicBlock *NewBB =
216       MF->CreateMachineBasicBlock(BB.getBasicBlock());
217   MF->insert(++BB.getIterator(), NewBB);
218 
219   // Insert an entry into BlockInfo to align it properly with the block numbers.
220   BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
221 
222   return NewBB;
223 }
224 
225 /// Split the basic block containing MI into two blocks, which are joined by
226 /// an unconditional branch.  Update data structures and renumber blocks to
227 /// account for this change and returns the newly created block.
splitBlockBeforeInstr(MachineInstr & MI,MachineBasicBlock * DestBB)228 MachineBasicBlock *BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI,
229                                                            MachineBasicBlock *DestBB) {
230   MachineBasicBlock *OrigBB = MI.getParent();
231 
232   // Create a new MBB for the code after the OrigBB.
233   MachineBasicBlock *NewBB =
234       MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
235   MF->insert(++OrigBB->getIterator(), NewBB);
236 
237   // Splice the instructions starting with MI over to NewBB.
238   NewBB->splice(NewBB->end(), OrigBB, MI.getIterator(), OrigBB->end());
239 
240   // Add an unconditional branch from OrigBB to NewBB.
241   // Note the new unconditional branch is not being recorded.
242   // There doesn't seem to be meaningful DebugInfo available; this doesn't
243   // correspond to anything in the source.
244   TII->insertUnconditionalBranch(*OrigBB, NewBB, DebugLoc());
245 
246   // Insert an entry into BlockInfo to align it properly with the block numbers.
247   BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
248 
249   NewBB->transferSuccessors(OrigBB);
250   OrigBB->addSuccessor(NewBB);
251   OrigBB->addSuccessor(DestBB);
252 
253   // Cleanup potential unconditional branch to successor block.
254   // Note that updateTerminator may change the size of the blocks.
255   NewBB->updateTerminator();
256   OrigBB->updateTerminator();
257 
258   // Figure out how large the OrigBB is.  As the first half of the original
259   // block, it cannot contain a tablejump.  The size includes
260   // the new jump we added.  (It should be possible to do this without
261   // recounting everything, but it's very confusing, and this is rarely
262   // executed.)
263   BlockInfo[OrigBB->getNumber()].Size = computeBlockSize(*OrigBB);
264 
265   // Figure out how large the NewMBB is. As the second half of the original
266   // block, it may contain a tablejump.
267   BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);
268 
269   // All BBOffsets following these blocks must be modified.
270   adjustBlockOffsets(*OrigBB);
271 
272   // Need to fix live-in lists if we track liveness.
273   if (TRI->trackLivenessAfterRegAlloc(*MF))
274     computeAndAddLiveIns(LiveRegs, *NewBB);
275 
276   ++NumSplit;
277 
278   return NewBB;
279 }
280 
281 /// isBlockInRange - Returns true if the distance between specific MI and
282 /// specific BB can fit in MI's displacement field.
isBlockInRange(const MachineInstr & MI,const MachineBasicBlock & DestBB) const283 bool BranchRelaxation::isBlockInRange(
284   const MachineInstr &MI, const MachineBasicBlock &DestBB) const {
285   int64_t BrOffset = getInstrOffset(MI);
286   int64_t DestOffset = BlockInfo[DestBB.getNumber()].Offset;
287 
288   if (TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - BrOffset))
289     return true;
290 
291   LLVM_DEBUG(dbgs() << "Out of range branch to destination "
292                     << printMBBReference(DestBB) << " from "
293                     << printMBBReference(*MI.getParent()) << " to "
294                     << DestOffset << " offset " << DestOffset - BrOffset << '\t'
295                     << MI);
296 
297   return false;
298 }
299 
300 /// fixupConditionalBranch - Fix up a conditional branch whose destination is
301 /// too far away to fit in its displacement field. It is converted to an inverse
302 /// conditional branch + an unconditional branch to the destination.
fixupConditionalBranch(MachineInstr & MI)303 bool BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) {
304   DebugLoc DL = MI.getDebugLoc();
305   MachineBasicBlock *MBB = MI.getParent();
306   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
307   MachineBasicBlock *NewBB = nullptr;
308   SmallVector<MachineOperand, 4> Cond;
309 
310   auto insertUncondBranch = [&](MachineBasicBlock *MBB,
311                                 MachineBasicBlock *DestBB) {
312     unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
313     int NewBrSize = 0;
314     TII->insertUnconditionalBranch(*MBB, DestBB, DL, &NewBrSize);
315     BBSize += NewBrSize;
316   };
317   auto insertBranch = [&](MachineBasicBlock *MBB, MachineBasicBlock *TBB,
318                           MachineBasicBlock *FBB,
319                           SmallVectorImpl<MachineOperand>& Cond) {
320     unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
321     int NewBrSize = 0;
322     TII->insertBranch(*MBB, TBB, FBB, Cond, DL, &NewBrSize);
323     BBSize += NewBrSize;
324   };
325   auto removeBranch = [&](MachineBasicBlock *MBB) {
326     unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
327     int RemovedSize = 0;
328     TII->removeBranch(*MBB, &RemovedSize);
329     BBSize -= RemovedSize;
330   };
331 
332   auto finalizeBlockChanges = [&](MachineBasicBlock *MBB,
333                                   MachineBasicBlock *NewBB) {
334     // Keep the block offsets up to date.
335     adjustBlockOffsets(*MBB);
336 
337     // Need to fix live-in lists if we track liveness.
338     if (NewBB && TRI->trackLivenessAfterRegAlloc(*MF))
339       computeAndAddLiveIns(LiveRegs, *NewBB);
340   };
341 
342   bool Fail = TII->analyzeBranch(*MBB, TBB, FBB, Cond);
343   assert(!Fail && "branches to be relaxed must be analyzable");
344   (void)Fail;
345 
346   // Add an unconditional branch to the destination and invert the branch
347   // condition to jump over it:
348   // tbz L1
349   // =>
350   // tbnz L2
351   // b   L1
352   // L2:
353 
354   bool ReversedCond = !TII->reverseBranchCondition(Cond);
355   if (ReversedCond) {
356     if (FBB && isBlockInRange(MI, *FBB)) {
357       // Last MI in the BB is an unconditional branch. We can simply invert the
358       // condition and swap destinations:
359       // beq L1
360       // b   L2
361       // =>
362       // bne L2
363       // b   L1
364       LLVM_DEBUG(dbgs() << "  Invert condition and swap "
365                            "its destination with "
366                         << MBB->back());
367 
368       removeBranch(MBB);
369       insertBranch(MBB, FBB, TBB, Cond);
370       finalizeBlockChanges(MBB, nullptr);
371       return true;
372     }
373     if (FBB) {
374       // We need to split the basic block here to obtain two long-range
375       // unconditional branches.
376       NewBB = createNewBlockAfter(*MBB);
377 
378       insertUncondBranch(NewBB, FBB);
379       // Update the succesor lists according to the transformation to follow.
380       // Do it here since if there's no split, no update is needed.
381       MBB->replaceSuccessor(FBB, NewBB);
382       NewBB->addSuccessor(FBB);
383     }
384 
385     // We now have an appropriate fall-through block in place (either naturally or
386     // just created), so we can use the inverted the condition.
387     MachineBasicBlock &NextBB = *std::next(MachineFunction::iterator(MBB));
388 
389     LLVM_DEBUG(dbgs() << "  Insert B to " << printMBBReference(*TBB)
390                       << ", invert condition and change dest. to "
391                       << printMBBReference(NextBB) << '\n');
392 
393     removeBranch(MBB);
394     // Insert a new conditional branch and a new unconditional branch.
395     insertBranch(MBB, &NextBB, TBB, Cond);
396 
397     finalizeBlockChanges(MBB, NewBB);
398     return true;
399   }
400   // Branch cond can't be inverted.
401   // In this case we always add a block after the MBB.
402   LLVM_DEBUG(dbgs() << "  The branch condition can't be inverted. "
403                     << "  Insert a new BB after " << MBB->back());
404 
405   if (!FBB)
406     FBB = &(*std::next(MachineFunction::iterator(MBB)));
407 
408   // This is the block with cond. branch and the distance to TBB is too long.
409   //    beq L1
410   // L2:
411 
412   // We do the following transformation:
413   //    beq NewBB
414   //    b L2
415   // NewBB:
416   //    b L1
417   // L2:
418 
419   NewBB = createNewBlockAfter(*MBB);
420   insertUncondBranch(NewBB, TBB);
421 
422   LLVM_DEBUG(dbgs() << "  Insert cond B to the new BB "
423                     << printMBBReference(*NewBB)
424                     << "  Keep the exiting condition.\n"
425                     << "  Insert B to " << printMBBReference(*FBB) << ".\n"
426                     << "  In the new BB: Insert B to "
427                     << printMBBReference(*TBB) << ".\n");
428 
429   // Update the successor lists according to the transformation to follow.
430   MBB->replaceSuccessor(TBB, NewBB);
431   NewBB->addSuccessor(TBB);
432 
433   // Replace branch in the current (MBB) block.
434   removeBranch(MBB);
435   insertBranch(MBB, NewBB, FBB, Cond);
436 
437   finalizeBlockChanges(MBB, NewBB);
438   return true;
439 }
440 
fixupUnconditionalBranch(MachineInstr & MI)441 bool BranchRelaxation::fixupUnconditionalBranch(MachineInstr &MI) {
442   MachineBasicBlock *MBB = MI.getParent();
443 
444   unsigned OldBrSize = TII->getInstSizeInBytes(MI);
445   MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
446 
447   int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset;
448   int64_t SrcOffset = getInstrOffset(MI);
449 
450   assert(!TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - SrcOffset));
451 
452   BlockInfo[MBB->getNumber()].Size -= OldBrSize;
453 
454   MachineBasicBlock *BranchBB = MBB;
455 
456   // If this was an expanded conditional branch, there is already a single
457   // unconditional branch in a block.
458   if (!MBB->empty()) {
459     BranchBB = createNewBlockAfter(*MBB);
460 
461     // Add live outs.
462     for (const MachineBasicBlock *Succ : MBB->successors()) {
463       for (const MachineBasicBlock::RegisterMaskPair &LiveIn : Succ->liveins())
464         BranchBB->addLiveIn(LiveIn);
465     }
466 
467     BranchBB->sortUniqueLiveIns();
468     BranchBB->addSuccessor(DestBB);
469     MBB->replaceSuccessor(DestBB, BranchBB);
470   }
471 
472   DebugLoc DL = MI.getDebugLoc();
473   MI.eraseFromParent();
474   BlockInfo[BranchBB->getNumber()].Size += TII->insertIndirectBranch(
475     *BranchBB, *DestBB, DL, DestOffset - SrcOffset, RS.get());
476 
477   adjustBlockOffsets(*MBB);
478   return true;
479 }
480 
relaxBranchInstructions()481 bool BranchRelaxation::relaxBranchInstructions() {
482   bool Changed = false;
483 
484   // Relaxing branches involves creating new basic blocks, so re-eval
485   // end() for termination.
486   for (MachineFunction::iterator I = MF->begin(); I != MF->end(); ++I) {
487     MachineBasicBlock &MBB = *I;
488 
489     // Empty block?
490     MachineBasicBlock::iterator Last = MBB.getLastNonDebugInstr();
491     if (Last == MBB.end())
492       continue;
493 
494     // Expand the unconditional branch first if necessary. If there is a
495     // conditional branch, this will end up changing the branch destination of
496     // it to be over the newly inserted indirect branch block, which may avoid
497     // the need to try expanding the conditional branch first, saving an extra
498     // jump.
499     if (Last->isUnconditionalBranch()) {
500       // Unconditional branch destination might be unanalyzable, assume these
501       // are OK.
502       if (MachineBasicBlock *DestBB = TII->getBranchDestBlock(*Last)) {
503         if (!isBlockInRange(*Last, *DestBB)) {
504           fixupUnconditionalBranch(*Last);
505           ++NumUnconditionalRelaxed;
506           Changed = true;
507         }
508       }
509     }
510 
511     // Loop over the conditional branches.
512     MachineBasicBlock::iterator Next;
513     for (MachineBasicBlock::iterator J = MBB.getFirstTerminator();
514          J != MBB.end(); J = Next) {
515       Next = std::next(J);
516       MachineInstr &MI = *J;
517 
518       if (MI.isConditionalBranch()) {
519         MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
520         if (!isBlockInRange(MI, *DestBB)) {
521           if (Next != MBB.end() && Next->isConditionalBranch()) {
522             // If there are multiple conditional branches, this isn't an
523             // analyzable block. Split later terminators into a new block so
524             // each one will be analyzable.
525 
526             splitBlockBeforeInstr(*Next, DestBB);
527           } else {
528             fixupConditionalBranch(MI);
529             ++NumConditionalRelaxed;
530           }
531 
532           Changed = true;
533 
534           // This may have modified all of the terminators, so start over.
535           Next = MBB.getFirstTerminator();
536         }
537       }
538     }
539   }
540 
541   return Changed;
542 }
543 
runOnMachineFunction(MachineFunction & mf)544 bool BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
545   MF = &mf;
546 
547   LLVM_DEBUG(dbgs() << "***** BranchRelaxation *****\n");
548 
549   const TargetSubtargetInfo &ST = MF->getSubtarget();
550   TII = ST.getInstrInfo();
551 
552   TRI = ST.getRegisterInfo();
553   if (TRI->trackLivenessAfterRegAlloc(*MF))
554     RS.reset(new RegScavenger());
555 
556   // Renumber all of the machine basic blocks in the function, guaranteeing that
557   // the numbers agree with the position of the block in the function.
558   MF->RenumberBlocks();
559 
560   // Do the initial scan of the function, building up information about the
561   // sizes of each block.
562   scanFunction();
563 
564   LLVM_DEBUG(dbgs() << "  Basic blocks before relaxation\n"; dumpBBs(););
565 
566   bool MadeChange = false;
567   while (relaxBranchInstructions())
568     MadeChange = true;
569 
570   // After a while, this might be made debug-only, but it is not expensive.
571   verify();
572 
573   LLVM_DEBUG(dbgs() << "  Basic blocks after relaxation\n\n"; dumpBBs());
574 
575   BlockInfo.clear();
576 
577   return MadeChange;
578 }
579