Mercurial > hg > CbC > CbC_llvm

comparison lib/CodeGen/BranchFolding.cpp @ 134:3a76565eade5 LLVM5.0.1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update 5.0.1
author mir3636
date Sat, 17 Feb 2018 09:57:20 +0900
parents 803732b1fca8
children c2174574ed3a
comparison
equal deleted inserted replaced
133:c60214abe0e8 134:3a76565eade5
37 #include "llvm/CodeGen/MachineJumpTableInfo.h" 37 #include "llvm/CodeGen/MachineJumpTableInfo.h"
38 #include "llvm/CodeGen/MachineLoopInfo.h" 38 #include "llvm/CodeGen/MachineLoopInfo.h"
39 #include "llvm/CodeGen/MachineModuleInfo.h" 39 #include "llvm/CodeGen/MachineModuleInfo.h"
40 #include "llvm/CodeGen/MachineOperand.h" 40 #include "llvm/CodeGen/MachineOperand.h"
41 #include "llvm/CodeGen/MachineRegisterInfo.h" 41 #include "llvm/CodeGen/MachineRegisterInfo.h"
42 #include "llvm/CodeGen/TargetInstrInfo.h"
43 #include "llvm/CodeGen/TargetOpcodes.h"
42 #include "llvm/CodeGen/TargetPassConfig.h" 44 #include "llvm/CodeGen/TargetPassConfig.h"
45 #include "llvm/CodeGen/TargetRegisterInfo.h"
46 #include "llvm/CodeGen/TargetSubtargetInfo.h"
43 #include "llvm/IR/DebugInfoMetadata.h" 47 #include "llvm/IR/DebugInfoMetadata.h"
44 #include "llvm/IR/DebugLoc.h" 48 #include "llvm/IR/DebugLoc.h"
45 #include "llvm/IR/Function.h" 49 #include "llvm/IR/Function.h"
46 #include "llvm/MC/LaneBitmask.h" 50 #include "llvm/MC/LaneBitmask.h"
47 #include "llvm/MC/MCRegisterInfo.h" 51 #include "llvm/MC/MCRegisterInfo.h"
50 #include "llvm/Support/BranchProbability.h" 54 #include "llvm/Support/BranchProbability.h"
51 #include "llvm/Support/CommandLine.h" 55 #include "llvm/Support/CommandLine.h"
52 #include "llvm/Support/Debug.h" 56 #include "llvm/Support/Debug.h"
53 #include "llvm/Support/ErrorHandling.h" 57 #include "llvm/Support/ErrorHandling.h"
54 #include "llvm/Support/raw_ostream.h" 58 #include "llvm/Support/raw_ostream.h"
55 #include "llvm/Target/TargetInstrInfo.h"
56 #include "llvm/Target/TargetMachine.h" 59 #include "llvm/Target/TargetMachine.h"
57 #include "llvm/Target/TargetOpcodes.h"
58 #include "llvm/Target/TargetRegisterInfo.h"
59 #include "llvm/Target/TargetSubtargetInfo.h"
60 #include <cassert> 60 #include <cassert>
61 #include <cstddef> 61 #include <cstddef>
62 #include <iterator> 62 #include <iterator>
63 #include <numeric> 63 #include <numeric>
64 #include <vector> 64 #include <vector>
116 116
117 INITIALIZE_PASS(BranchFolderPass, DEBUG_TYPE, 117 INITIALIZE_PASS(BranchFolderPass, DEBUG_TYPE,
118 "Control Flow Optimizer", false, false) 118 "Control Flow Optimizer", false, false)
119 119
120 bool BranchFolderPass::runOnMachineFunction(MachineFunction &MF) { 120 bool BranchFolderPass::runOnMachineFunction(MachineFunction &MF) {
121 if (skipFunction(*MF.getFunction())) 121 if (skipFunction(MF.getFunction()))
122 return false; 122 return false;
123 123
124 TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>(); 124 TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
125 // TailMerge can create jump into if branches that make CFG irreducible for 125 // TailMerge can create jump into if branches that make CFG irreducible for
126 // HW that requires structurized CFG. 126 // HW that requires structurized CFG.
611 } 611 }
612 612
613 CommonTailLen = ComputeCommonTailLength(MBB1, MBB2, I1, I2); 613 CommonTailLen = ComputeCommonTailLength(MBB1, MBB2, I1, I2);
614 if (CommonTailLen == 0) 614 if (CommonTailLen == 0)
615 return false; 615 return false;
616 DEBUG(dbgs() << "Common tail length of BB#" << MBB1->getNumber() 616 DEBUG(dbgs() << "Common tail length of " << printMBBReference(*MBB1)
617 << " and BB#" << MBB2->getNumber() << " is " << CommonTailLen 617 << " and " << printMBBReference(*MBB2) << " is " << CommonTailLen
618 << '\n'); 618 << '\n');
619 619
620 // It's almost always profitable to merge any number of non-terminator 620 // It's almost always profitable to merge any number of non-terminator
621 // instructions with the block that falls through into the common successor. 621 // instructions with the block that falls through into the common successor.
622 // This is true only for a single successor. For multiple successors, we are 622 // This is true only for a single successor. For multiple successors, we are
683 // If we are optimizing for code size, 2 instructions in common is enough if 683 // If we are optimizing for code size, 2 instructions in common is enough if
684 // we don't have to split a block. At worst we will be introducing 1 new 684 // we don't have to split a block. At worst we will be introducing 1 new
685 // branch instruction, which is likely to be smaller than the 2 685 // branch instruction, which is likely to be smaller than the 2
686 // instructions that would be deleted in the merge. 686 // instructions that would be deleted in the merge.
687 MachineFunction *MF = MBB1->getParent(); 687 MachineFunction *MF = MBB1->getParent();
688 return EffectiveTailLen >= 2 && MF->getFunction()->optForSize() && 688 return EffectiveTailLen >= 2 && MF->getFunction().optForSize() &&
689 (I1 == MBB1->begin() || I2 == MBB2->begin()); 689 (I1 == MBB1->begin() || I2 == MBB2->begin());
690 } 690 }
691 691
692 unsigned BranchFolder::ComputeSameTails(unsigned CurHash, 692 unsigned BranchFolder::ComputeSameTails(unsigned CurHash,
693 unsigned MinCommonTailLength, 693 unsigned MinCommonTailLength,
768 768
769 MachineBasicBlock::iterator BBI = 769 MachineBasicBlock::iterator BBI =
770 SameTails[commonTailIndex].getTailStartPos(); 770 SameTails[commonTailIndex].getTailStartPos();
771 MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock(); 771 MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
772 772
773 DEBUG(dbgs() << "\nSplitting BB#" << MBB->getNumber() << ", size " 773 DEBUG(dbgs() << "\nSplitting " << printMBBReference(*MBB) << ", size "
774 << maxCommonTailLength); 774 << maxCommonTailLength);
775 775
776 // If the split block unconditionally falls-thru to SuccBB, it will be 776 // If the split block unconditionally falls-thru to SuccBB, it will be
777 // merged. In control flow terms it should then take SuccBB's name. e.g. If 777 // merged. In control flow terms it should then take SuccBB's name. e.g. If
778 // SuccBB is an inner loop, the common tail is still part of the inner loop. 778 // SuccBB is an inner loop, the common tail is still part of the inner loop.
918 MachineBasicBlock *PredBB, 918 MachineBasicBlock *PredBB,
919 unsigned MinCommonTailLength) { 919 unsigned MinCommonTailLength) {
920 bool MadeChange = false; 920 bool MadeChange = false;
921 921
922 DEBUG(dbgs() << "\nTryTailMergeBlocks: "; 922 DEBUG(dbgs() << "\nTryTailMergeBlocks: ";
923 for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i) 923 for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i) dbgs()
924 dbgs() << "BB#" << MergePotentials[i].getBlock()->getNumber() 924 << printMBBReference(*MergePotentials[i].getBlock())
925 << (i == e-1 ? "" : ", "); 925 << (i == e - 1 ? "" : ", ");
926 dbgs() << "\n"; 926 dbgs() << "\n"; if (SuccBB) {
927 if (SuccBB) { 927 dbgs() << " with successor " << printMBBReference(*SuccBB) << '\n';
928 dbgs() << " with successor BB#" << SuccBB->getNumber() << '\n';
929 if (PredBB) 928 if (PredBB)
930 dbgs() << " which has fall-through from BB#" 929 dbgs() << " which has fall-through from "
931 << PredBB->getNumber() << "\n"; 930 << printMBBReference(*PredBB) << "\n";
932 } 931 } dbgs() << "Looking for common tails of at least "
933 dbgs() << "Looking for common tails of at least " 932 << MinCommonTailLength << " instruction"
934 << MinCommonTailLength << " instruction" 933 << (MinCommonTailLength == 1 ? "" : "s") << '\n';);
935 << (MinCommonTailLength == 1 ? "" : "s") << '\n';
936 );
937 934
938 // Sort by hash value so that blocks with identical end sequences sort 935 // Sort by hash value so that blocks with identical end sequences sort
939 // together. 936 // together.
940 array_pod_sort(MergePotentials.begin(), MergePotentials.end()); 937 array_pod_sort(MergePotentials.begin(), MergePotentials.end());
941 938
1011 // for common tail. 1008 // for common tail.
1012 mergeCommonTails(commonTailIndex); 1009 mergeCommonTails(commonTailIndex);
1013 1010
1014 // MBB is common tail. Adjust all other BB's to jump to this one. 1011 // MBB is common tail. Adjust all other BB's to jump to this one.
1015 // Traversal must be forwards so erases work. 1012 // Traversal must be forwards so erases work.
1016 DEBUG(dbgs() << "\nUsing common tail in BB#" << MBB->getNumber() 1013 DEBUG(dbgs() << "\nUsing common tail in " << printMBBReference(*MBB)
1017 << " for "); 1014 << " for ");
1018 for (unsigned int i=0, e = SameTails.size(); i != e; ++i) { 1015 for (unsigned int i=0, e = SameTails.size(); i != e; ++i) {
1019 if (commonTailIndex == i) 1016 if (commonTailIndex == i)
1020 continue; 1017 continue;
1021 DEBUG(dbgs() << "BB#" << SameTails[i].getBlock()->getNumber() 1018 DEBUG(dbgs() << printMBBReference(*SameTails[i].getBlock())
1022 << (i == e-1 ? "" : ", ")); 1019 << (i == e - 1 ? "" : ", "));
1023 // Hack the end off BB i, making it jump to BB commonTailIndex instead. 1020 // Hack the end off BB i, making it jump to BB commonTailIndex instead.
1024 replaceTailWithBranchTo(SameTails[i].getTailStartPos(), *MBB); 1021 replaceTailWithBranchTo(SameTails[i].getTailStartPos(), *MBB);
1025 // BB i is no longer a predecessor of SuccBB; remove it from the worklist. 1022 // BB i is no longer a predecessor of SuccBB; remove it from the worklist.
1026 MergePotentials.erase(SameTails[i].getMPIter()); 1023 MergePotentials.erase(SameTails[i].getMPIter());
1027 } 1024 }
1512 } 1509 }
1513 } 1510 }
1514 } 1511 }
1515 1512
1516 if (!IsEmptyBlock(MBB) && MBB->pred_size() == 1 && 1513 if (!IsEmptyBlock(MBB) && MBB->pred_size() == 1 &&
1517 MF.getFunction()->optForSize()) { 1514 MF.getFunction().optForSize()) {
1518 // Changing "Jcc foo; foo: jmp bar;" into "Jcc bar;" might change the branch 1515 // Changing "Jcc foo; foo: jmp bar;" into "Jcc bar;" might change the branch
1519 // direction, thereby defeating careful block placement and regressing 1516 // direction, thereby defeating careful block placement and regressing
1520 // performance. Therefore, only consider this for optsize functions. 1517 // performance. Therefore, only consider this for optsize functions.
1521 MachineInstr &TailCall = *MBB->getFirstNonDebugInstr(); 1518 MachineInstr &TailCall = *MBB->getFirstNonDebugInstr();
1522 if (TII->isUnconditionalTailCall(TailCall)) { 1519 if (TII->isUnconditionalTailCall(TailCall)) {
1969 // r1, eflag = op1 r2, r3 1966 // r1, eflag = op1 r2, r3
1970 // brcc eflag 1967 // brcc eflag
1971 // 1968 //
1972 // BB2: 1969 // BB2:
1973 // r1 = op2, ... 1970 // r1 = op2, ...
1974 // = op3, r1<kill> 1971 // = op3, killed r1
1975 IsSafe = false; 1972 IsSafe = false;
1976 break; 1973 break;
1977 } 1974 }
1978 } else if (!ActiveDefsSet.count(Reg)) { 1975 } else if (!ActiveDefsSet.count(Reg)) {
1979 if (Defs.count(Reg)) { 1976 if (Defs.count(Reg)) {