Mercurial > hg > CbC > CbC_llvm

comparison lib/CodeGen/TwoAddressInstructionPass.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
33 #include "llvm/ADT/SmallVector.h" 33 #include "llvm/ADT/SmallVector.h"
34 #include "llvm/ADT/Statistic.h" 34 #include "llvm/ADT/Statistic.h"
35 #include "llvm/ADT/iterator_range.h" 35 #include "llvm/ADT/iterator_range.h"
36 #include "llvm/Analysis/AliasAnalysis.h" 36 #include "llvm/Analysis/AliasAnalysis.h"
37 #include "llvm/CodeGen/LiveInterval.h" 37 #include "llvm/CodeGen/LiveInterval.h"
38 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 38 #include "llvm/CodeGen/LiveIntervals.h"
39 #include "llvm/CodeGen/LiveVariables.h" 39 #include "llvm/CodeGen/LiveVariables.h"
40 #include "llvm/CodeGen/MachineBasicBlock.h" 40 #include "llvm/CodeGen/MachineBasicBlock.h"
41 #include "llvm/CodeGen/MachineFunction.h" 41 #include "llvm/CodeGen/MachineFunction.h"
42 #include "llvm/CodeGen/MachineFunctionPass.h" 42 #include "llvm/CodeGen/MachineFunctionPass.h"
43 #include "llvm/CodeGen/MachineInstr.h" 43 #include "llvm/CodeGen/MachineInstr.h"
44 #include "llvm/CodeGen/MachineInstrBuilder.h" 44 #include "llvm/CodeGen/MachineInstrBuilder.h"
45 #include "llvm/CodeGen/MachineOperand.h" 45 #include "llvm/CodeGen/MachineOperand.h"
46 #include "llvm/CodeGen/MachineRegisterInfo.h" 46 #include "llvm/CodeGen/MachineRegisterInfo.h"
47 #include "llvm/CodeGen/Passes.h" 47 #include "llvm/CodeGen/Passes.h"
48 #include "llvm/CodeGen/SlotIndexes.h" 48 #include "llvm/CodeGen/SlotIndexes.h"
49 #include "llvm/CodeGen/TargetInstrInfo.h"
50 #include "llvm/CodeGen/TargetOpcodes.h"
51 #include "llvm/CodeGen/TargetRegisterInfo.h"
52 #include "llvm/CodeGen/TargetSubtargetInfo.h"
49 #include "llvm/MC/MCInstrDesc.h" 53 #include "llvm/MC/MCInstrDesc.h"
50 #include "llvm/MC/MCInstrItineraries.h" 54 #include "llvm/MC/MCInstrItineraries.h"
51 #include "llvm/Pass.h" 55 #include "llvm/Pass.h"
52 #include "llvm/Support/CodeGen.h" 56 #include "llvm/Support/CodeGen.h"
53 #include "llvm/Support/CommandLine.h" 57 #include "llvm/Support/CommandLine.h"
54 #include "llvm/Support/Debug.h" 58 #include "llvm/Support/Debug.h"
55 #include "llvm/Support/ErrorHandling.h" 59 #include "llvm/Support/ErrorHandling.h"
56 #include "llvm/Support/raw_ostream.h" 60 #include "llvm/Support/raw_ostream.h"
57 #include "llvm/Target/TargetInstrInfo.h"
58 #include "llvm/Target/TargetMachine.h" 61 #include "llvm/Target/TargetMachine.h"
59 #include "llvm/Target/TargetOpcodes.h"
60 #include "llvm/Target/TargetRegisterInfo.h"
61 #include "llvm/Target/TargetSubtargetInfo.h"
62 #include <cassert> 62 #include <cassert>
63 #include <iterator> 63 #include <iterator>
64 #include <utility> 64 #include <utility>
65 65
66 using namespace llvm; 66 using namespace llvm;
107 // Keep track the distance of a MI from the start of the current basic block. 107 // Keep track the distance of a MI from the start of the current basic block.
108 DenseMap<MachineInstr*, unsigned> DistanceMap; 108 DenseMap<MachineInstr*, unsigned> DistanceMap;
109 109
110 // Set of already processed instructions in the current block. 110 // Set of already processed instructions in the current block.
111 SmallPtrSet<MachineInstr*, 8> Processed; 111 SmallPtrSet<MachineInstr*, 8> Processed;
112
113 // Set of instructions converted to three-address by target and then sunk
114 // down current basic block.
115 SmallPtrSet<MachineInstr*, 8> SunkInstrs;
112 116
113 // A map from virtual registers to physical registers which are likely targets 117 // A map from virtual registers to physical registers which are likely targets
114 // to be coalesced to due to copies from physical registers to virtual 118 // to be coalesced to due to copies from physical registers to virtual
115 // registers. e.g. v1024 = move r0. 119 // registers. e.g. v1024 = move r0.
116 DenseMap<unsigned, unsigned> SrcRegMap; 120 DenseMap<unsigned, unsigned> SrcRegMap;
452 /// coalescable copies to see if the original value is potentially not killed. 456 /// coalescable copies to see if the original value is potentially not killed.
453 /// 457 ///
454 /// For example, in this code: 458 /// For example, in this code:
455 /// 459 ///
456 /// %reg1034 = copy %reg1024 460 /// %reg1034 = copy %reg1024
457 /// %reg1035 = copy %reg1025<kill> 461 /// %reg1035 = copy killed %reg1025
458 /// %reg1036 = add %reg1034<kill>, %reg1035<kill> 462 /// %reg1036 = add killed %reg1034, killed %reg1035
459 /// 463 ///
460 /// %reg1034 is not considered to be killed, since it is copied from a 464 /// %reg1034 is not considered to be killed, since it is copied from a
461 /// register which is not killed. Treating it as not killed lets the 465 /// register which is not killed. Treating it as not killed lets the
462 /// normal heuristics commute the (two-address) add, which lets 466 /// normal heuristics commute the (two-address) add, which lets
463 /// coalescing eliminate the extra copy. 467 /// coalescing eliminate the extra copy.
585 589
586 // Determine if it's profitable to commute this two address instruction. In 590 // Determine if it's profitable to commute this two address instruction. In
587 // general, we want no uses between this instruction and the definition of 591 // general, we want no uses between this instruction and the definition of
588 // the two-address register. 592 // the two-address register.
589 // e.g. 593 // e.g.
590 // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1 594 // %reg1028 = EXTRACT_SUBREG killed %reg1027, 1
591 // %reg1029<def> = MOV8rr %reg1028 595 // %reg1029 = MOV8rr %reg1028
592 // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead> 596 // %reg1029 = SHR8ri %reg1029, 7, implicit dead %eflags
593 // insert => %reg1030<def> = MOV8rr %reg1028 597 // insert => %reg1030 = MOV8rr %reg1028
594 // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead> 598 // %reg1030 = ADD8rr killed %reg1028, killed %reg1029, implicit dead %eflags
595 // In this case, it might not be possible to coalesce the second MOV8rr 599 // In this case, it might not be possible to coalesce the second MOV8rr
596 // instruction if the first one is coalesced. So it would be profitable to 600 // instruction if the first one is coalesced. So it would be profitable to
597 // commute it: 601 // commute it:
598 // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1 602 // %reg1028 = EXTRACT_SUBREG killed %reg1027, 1
599 // %reg1029<def> = MOV8rr %reg1028 603 // %reg1029 = MOV8rr %reg1028
600 // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead> 604 // %reg1029 = SHR8ri %reg1029, 7, implicit dead %eflags
601 // insert => %reg1030<def> = MOV8rr %reg1029 605 // insert => %reg1030 = MOV8rr %reg1029
602 // %reg1030<def> = ADD8rr %reg1029<kill>, %reg1028<kill>, %EFLAGS<imp-def,dead> 606 // %reg1030 = ADD8rr killed %reg1029, killed %reg1028, implicit dead %eflags
603 607
604 if (!isPlainlyKilled(MI, regC, LIS)) 608 if (!isPlainlyKilled(MI, regC, LIS))
605 return false; 609 return false;
606 610
607 // Ok, we have something like: 611 // Ok, we have something like:
608 // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead> 612 // %reg1030 = ADD8rr killed %reg1028, killed %reg1029, implicit dead %eflags
609 // let's see if it's worth commuting it. 613 // let's see if it's worth commuting it.
610 614
611 // Look for situations like this: 615 // Look for situations like this:
612 // %reg1024<def> = MOV r1 616 // %reg1024 = MOV r1
613 // %reg1025<def> = MOV r0 617 // %reg1025 = MOV r0
614 // %reg1026<def> = ADD %reg1024, %reg1025 618 // %reg1026 = ADD %reg1024, %reg1025
615 // r0 = MOV %reg1026 619 // r0 = MOV %reg1026
616 // Commute the ADD to hopefully eliminate an otherwise unavoidable copy. 620 // Commute the ADD to hopefully eliminate an otherwise unavoidable copy.
617 unsigned ToRegA = getMappedReg(regA, DstRegMap); 621 unsigned ToRegA = getMappedReg(regA, DstRegMap);
618 if (ToRegA) { 622 if (ToRegA) {
619 unsigned FromRegB = getMappedReg(regB, SrcRegMap); 623 unsigned FromRegB = getMappedReg(regB, SrcRegMap);
707 /// Return true if it is profitable to convert the given 2-address instruction 711 /// Return true if it is profitable to convert the given 2-address instruction
708 /// to a 3-address one. 712 /// to a 3-address one.
709 bool 713 bool
710 TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA,unsigned RegB){ 714 TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA,unsigned RegB){
711 // Look for situations like this: 715 // Look for situations like this:
712 // %reg1024<def> = MOV r1 716 // %reg1024 = MOV r1
713 // %reg1025<def> = MOV r0 717 // %reg1025 = MOV r0
714 // %reg1026<def> = ADD %reg1024, %reg1025 718 // %reg1026 = ADD %reg1024, %reg1025
715 // r2 = MOV %reg1026 719 // r2 = MOV %reg1026
716 // Turn ADD into a 3-address instruction to avoid a copy. 720 // Turn ADD into a 3-address instruction to avoid a copy.
717 unsigned FromRegB = getMappedReg(RegB, SrcRegMap); 721 unsigned FromRegB = getMappedReg(RegB, SrcRegMap);
718 if (!FromRegB) 722 if (!FromRegB)
719 return false; 723 return false;
754 if (!Sunk) { 758 if (!Sunk) {
755 DistanceMap.insert(std::make_pair(NewMI, Dist)); 759 DistanceMap.insert(std::make_pair(NewMI, Dist));
756 mi = NewMI; 760 mi = NewMI;
757 nmi = std::next(mi); 761 nmi = std::next(mi);
758 } 762 }
763 else
764 SunkInstrs.insert(NewMI);
759 765
760 // Update source and destination register maps. 766 // Update source and destination register maps.
761 SrcRegMap.erase(RegA); 767 SrcRegMap.erase(RegA);
762 DstRegMap.erase(RegB); 768 DstRegMap.erase(RegB);
763 return true; 769 return true;
1458 if (SrcReg == DstReg) 1464 if (SrcReg == DstReg)
1459 continue; 1465 continue;
1460 1466
1461 assert(SrcReg && SrcMO.isUse() && "two address instruction invalid"); 1467 assert(SrcReg && SrcMO.isUse() && "two address instruction invalid");
1462 1468
1463 // Deal with <undef> uses immediately - simply rewrite the src operand. 1469 // Deal with undef uses immediately - simply rewrite the src operand.
1464 if (SrcMO.isUndef() && !DstMO.getSubReg()) { 1470 if (SrcMO.isUndef() && !DstMO.getSubReg()) {
1465 // Constrain the DstReg register class if required. 1471 // Constrain the DstReg register class if required.
1466 if (TargetRegisterInfo::isVirtualRegister(DstReg)) 1472 if (TargetRegisterInfo::isVirtualRegister(DstReg))
1467 if (const TargetRegisterClass *RC = TII->getRegClass(MCID, SrcIdx, 1473 if (const TargetRegisterClass *RC = TII->getRegClass(MCID, SrcIdx,
1468 TRI, *MF)) 1474 TRI, *MF))
1653 if (auto *AAPass = getAnalysisIfAvailable<AAResultsWrapperPass>()) 1659 if (auto *AAPass = getAnalysisIfAvailable<AAResultsWrapperPass>())
1654 AA = &AAPass->getAAResults(); 1660 AA = &AAPass->getAAResults();
1655 else 1661 else
1656 AA = nullptr; 1662 AA = nullptr;
1657 OptLevel = TM.getOptLevel(); 1663 OptLevel = TM.getOptLevel();
1664 // Disable optimizations if requested. We cannot skip the whole pass as some
1665 // fixups are necessary for correctness.
1666 if (skipFunction(Func.getFunction()))
1667 OptLevel = CodeGenOpt::None;
1658 1668
1659 bool MadeChange = false; 1669 bool MadeChange = false;
1660 1670
1661 DEBUG(dbgs() << "********** REWRITING TWO-ADDR INSTRS **********\n"); 1671 DEBUG(dbgs() << "********** REWRITING TWO-ADDR INSTRS **********\n");
1662 DEBUG(dbgs() << "********** Function: " 1672 DEBUG(dbgs() << "********** Function: "
1672 unsigned Dist = 0; 1682 unsigned Dist = 0;
1673 DistanceMap.clear(); 1683 DistanceMap.clear();
1674 SrcRegMap.clear(); 1684 SrcRegMap.clear();
1675 DstRegMap.clear(); 1685 DstRegMap.clear();
1676 Processed.clear(); 1686 Processed.clear();
1687 SunkInstrs.clear();
1677 for (MachineBasicBlock::iterator mi = MBB->begin(), me = MBB->end(); 1688 for (MachineBasicBlock::iterator mi = MBB->begin(), me = MBB->end();
1678 mi != me; ) { 1689 mi != me; ) {
1679 MachineBasicBlock::iterator nmi = std::next(mi); 1690 MachineBasicBlock::iterator nmi = std::next(mi);
1680 if (mi->isDebugValue()) { 1691 // Don't revisit an instruction previously converted by target. It may
1692 // contain undef register operands (%noreg), which are not handled.
1693 if (mi->isDebugValue() || SunkInstrs.count(&*mi)) {
1681 mi = nmi; 1694 mi = nmi;
1682 continue; 1695 continue;
1683 } 1696 }
1684 1697
1685 // Expand REG_SEQUENCE instructions. This will position mi at the first 1698 // Expand REG_SEQUENCE instructions. This will position mi at the first
1763 /// 1776 ///
1764 /// %dst = REG_SEQUENCE %v1, ssub0, %v2, ssub1 1777 /// %dst = REG_SEQUENCE %v1, ssub0, %v2, ssub1
1765 /// 1778 ///
1766 /// Becomes: 1779 /// Becomes:
1767 /// 1780 ///
1768 /// %dst:ssub0<def,undef> = COPY %v1 1781 /// undef %dst:ssub0 = COPY %v1
1769 /// %dst:ssub1<def> = COPY %v2 1782 /// %dst:ssub1 = COPY %v2
1770 void TwoAddressInstructionPass:: 1783 void TwoAddressInstructionPass::
1771 eliminateRegSequence(MachineBasicBlock::iterator &MBBI) { 1784 eliminateRegSequence(MachineBasicBlock::iterator &MBBI) {
1772 MachineInstr &MI = *MBBI; 1785 MachineInstr &MI = *MBBI;
1773 unsigned DstReg = MI.getOperand(0).getReg(); 1786 unsigned DstReg = MI.getOperand(0).getReg();
1774 if (MI.getOperand(0).getSubReg() || 1787 if (MI.getOperand(0).getSubReg() ||
1788 bool DefEmitted = false; 1801 bool DefEmitted = false;
1789 for (unsigned i = 1, e = MI.getNumOperands(); i < e; i += 2) { 1802 for (unsigned i = 1, e = MI.getNumOperands(); i < e; i += 2) {
1790 MachineOperand &UseMO = MI.getOperand(i); 1803 MachineOperand &UseMO = MI.getOperand(i);
1791 unsigned SrcReg = UseMO.getReg(); 1804 unsigned SrcReg = UseMO.getReg();
1792 unsigned SubIdx = MI.getOperand(i+1).getImm(); 1805 unsigned SubIdx = MI.getOperand(i+1).getImm();
1793 // Nothing needs to be inserted for <undef> operands. 1806 // Nothing needs to be inserted for undef operands.
1794 if (UseMO.isUndef()) 1807 if (UseMO.isUndef())
1795 continue; 1808 continue;
1796 1809
1797 // Defer any kill flag to the last operand using SrcReg. Otherwise, we 1810 // Defer any kill flag to the last operand using SrcReg. Otherwise, we
1798 // might insert a COPY that uses SrcReg after is was killed. 1811 // might insert a COPY that uses SrcReg after is was killed.
1810 MachineInstr *CopyMI = BuildMI(*MI.getParent(), MI, MI.getDebugLoc(), 1823 MachineInstr *CopyMI = BuildMI(*MI.getParent(), MI, MI.getDebugLoc(),
1811 TII->get(TargetOpcode::COPY)) 1824 TII->get(TargetOpcode::COPY))
1812 .addReg(DstReg, RegState::Define, SubIdx) 1825 .addReg(DstReg, RegState::Define, SubIdx)
1813 .add(UseMO); 1826 .add(UseMO);
1814 1827
1815 // The first def needs an <undef> flag because there is no live register 1828 // The first def needs an undef flag because there is no live register
1816 // before it. 1829 // before it.
1817 if (!DefEmitted) { 1830 if (!DefEmitted) {
1818 CopyMI->getOperand(0).setIsUndef(true); 1831 CopyMI->getOperand(0).setIsUndef(true);
1819 // Return an iterator pointing to the first inserted instr. 1832 // Return an iterator pointing to the first inserted instr.
1820 MBBI = CopyMI; 1833 MBBI = CopyMI;