LLVM  6.0.0svn
LegalizerCombiner.h
Go to the documentation of this file.
1 //===-- llvm/CodeGen/GlobalISel/LegalizerCombiner.h --===========//
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 // This file contains some helper functions which try to cleanup artifacts
10 // such as G_TRUNCs/G_[ZSA]EXTENDS that were created during legalization to make
11 // the types match. This file also contains some combines of merges that happens
12 // at the end of the legalization.
13 //===----------------------------------------------------------------------===//
14 
20 #include "llvm/Support/Debug.h"
21 
22 #define DEBUG_TYPE "legalizer"
23 
24 namespace llvm {
26  MachineIRBuilder &Builder;
28  const LegalizerInfo &LI;
29 
30 public:
32  const LegalizerInfo &LI)
33  : Builder(B), MRI(MRI), LI(LI) {}
34 
37  if (MI.getOpcode() != TargetOpcode::G_ANYEXT)
38  return false;
40  if (DefMI->getOpcode() == TargetOpcode::G_TRUNC) {
41  DEBUG(dbgs() << ".. Combine MI: " << MI;);
42  unsigned DstReg = MI.getOperand(0).getReg();
43  unsigned SrcReg = DefMI->getOperand(1).getReg();
44  Builder.setInstr(MI);
45  // We get a copy/trunc/extend depending on the sizes
46  Builder.buildAnyExtOrTrunc(DstReg, SrcReg);
47  markInstAndDefDead(MI, *DefMI, DeadInsts);
48  return true;
49  }
50  return false;
51  }
52 
55 
56  if (MI.getOpcode() != TargetOpcode::G_ZEXT)
57  return false;
59  if (DefMI->getOpcode() == TargetOpcode::G_TRUNC) {
60  unsigned DstReg = MI.getOperand(0).getReg();
61  LLT DstTy = MRI.getType(DstReg);
62  if (isInstUnsupported(TargetOpcode::G_AND, DstTy) ||
63  isInstUnsupported(TargetOpcode::G_CONSTANT, DstTy))
64  return false;
65  DEBUG(dbgs() << ".. Combine MI: " << MI;);
66  Builder.setInstr(MI);
67  unsigned ZExtSrc = MI.getOperand(1).getReg();
68  LLT ZExtSrcTy = MRI.getType(ZExtSrc);
70  auto MaskCstMIB = Builder.buildConstant(DstTy, Mask.getZExtValue());
71  unsigned TruncSrc = DefMI->getOperand(1).getReg();
72  // We get a copy/trunc/extend depending on the sizes
73  auto SrcCopyOrTrunc = Builder.buildAnyExtOrTrunc(DstTy, TruncSrc);
74  Builder.buildAnd(DstReg, SrcCopyOrTrunc, MaskCstMIB);
75  markInstAndDefDead(MI, *DefMI, DeadInsts);
76  return true;
77  }
78  return false;
79  }
80 
83 
84  if (MI.getOpcode() != TargetOpcode::G_SEXT)
85  return false;
87  if (DefMI->getOpcode() == TargetOpcode::G_TRUNC) {
88  unsigned DstReg = MI.getOperand(0).getReg();
89  LLT DstTy = MRI.getType(DstReg);
90  if (isInstUnsupported(TargetOpcode::G_SHL, DstTy) ||
91  isInstUnsupported(TargetOpcode::G_ASHR, DstTy) ||
92  isInstUnsupported(TargetOpcode::G_CONSTANT, DstTy))
93  return false;
94  DEBUG(dbgs() << ".. Combine MI: " << MI;);
95  Builder.setInstr(MI);
96  unsigned SExtSrc = MI.getOperand(1).getReg();
97  LLT SExtSrcTy = MRI.getType(SExtSrc);
98  unsigned SizeDiff = DstTy.getSizeInBits() - SExtSrcTy.getSizeInBits();
99  auto SizeDiffMIB = Builder.buildConstant(DstTy, SizeDiff);
100  unsigned TruncSrcReg = DefMI->getOperand(1).getReg();
101  // We get a copy/trunc/extend depending on the sizes
102  auto SrcCopyExtOrTrunc = Builder.buildAnyExtOrTrunc(DstTy, TruncSrcReg);
103  auto ShlMIB = Builder.buildInstr(TargetOpcode::G_SHL, DstTy,
104  SrcCopyExtOrTrunc, SizeDiffMIB);
105  Builder.buildInstr(TargetOpcode::G_ASHR, DstReg, ShlMIB, SizeDiffMIB);
106  markInstAndDefDead(MI, *DefMI, DeadInsts);
107  return true;
108  }
109  return false;
110  }
111 
113  SmallVectorImpl<MachineInstr *> &DeadInsts) {
114 
115  if (MI.getOpcode() != TargetOpcode::G_UNMERGE_VALUES)
116  return false;
117 
118  unsigned NumDefs = MI.getNumOperands() - 1;
119  unsigned SrcReg = MI.getOperand(NumDefs).getReg();
120  MachineInstr *MergeI = MRI.getVRegDef(SrcReg);
121  if (!MergeI || (MergeI->getOpcode() != TargetOpcode::G_MERGE_VALUES))
122  return false;
123 
124  const unsigned NumMergeRegs = MergeI->getNumOperands() - 1;
125 
126  if (NumMergeRegs < NumDefs) {
127  if (NumDefs % NumMergeRegs != 0)
128  return false;
129 
130  Builder.setInstr(MI);
131  // Transform to UNMERGEs, for example
132  // %1 = G_MERGE_VALUES %4, %5
133  // %9, %10, %11, %12 = G_UNMERGE_VALUES %1
134  // to
135  // %9, %10 = G_UNMERGE_VALUES %4
136  // %11, %12 = G_UNMERGE_VALUES %5
137 
138  const unsigned NewNumDefs = NumDefs / NumMergeRegs;
139  for (unsigned Idx = 0; Idx < NumMergeRegs; ++Idx) {
140  SmallVector<unsigned, 2> DstRegs;
141  for (unsigned j = 0, DefIdx = Idx * NewNumDefs; j < NewNumDefs;
142  ++j, ++DefIdx)
143  DstRegs.push_back(MI.getOperand(DefIdx).getReg());
144 
145  Builder.buildUnmerge(DstRegs, MergeI->getOperand(Idx + 1).getReg());
146  }
147 
148  } else if (NumMergeRegs > NumDefs) {
149  if (NumMergeRegs % NumDefs != 0)
150  return false;
151 
152  Builder.setInstr(MI);
153  // Transform to MERGEs
154  // %6 = G_MERGE_VALUES %17, %18, %19, %20
155  // %7, %8 = G_UNMERGE_VALUES %6
156  // to
157  // %7 = G_MERGE_VALUES %17, %18
158  // %8 = G_MERGE_VALUES %19, %20
159 
160  const unsigned NumRegs = NumMergeRegs / NumDefs;
161  for (unsigned DefIdx = 0; DefIdx < NumDefs; ++DefIdx) {
163  for (unsigned j = 0, Idx = NumRegs * DefIdx + 1; j < NumRegs;
164  ++j, ++Idx)
165  Regs.push_back(MergeI->getOperand(Idx).getReg());
166 
167  Builder.buildMerge(MI.getOperand(DefIdx).getReg(), Regs);
168  }
169 
170  } else {
171  // FIXME: is a COPY appropriate if the types mismatch? We know both
172  // registers are allocatable by now.
173  if (MRI.getType(MI.getOperand(0).getReg()) !=
174  MRI.getType(MergeI->getOperand(1).getReg()))
175  return false;
176 
177  for (unsigned Idx = 0; Idx < NumDefs; ++Idx)
178  MRI.replaceRegWith(MI.getOperand(Idx).getReg(),
179  MergeI->getOperand(Idx + 1).getReg());
180  }
181 
182  markInstAndDefDead(MI, *MergeI, DeadInsts);
183  return true;
184  }
185 
186  /// Try to combine away MI.
187  /// Returns true if it combined away the MI.
188  /// Adds instructions that are dead as a result of the combine
189  /// into DeadInsts, which can include MI.
191  SmallVectorImpl<MachineInstr *> &DeadInsts) {
192  switch (MI.getOpcode()) {
193  default:
194  return false;
195  case TargetOpcode::G_ANYEXT:
196  return tryCombineAnyExt(MI, DeadInsts);
197  case TargetOpcode::G_ZEXT:
198  return tryCombineZExt(MI, DeadInsts);
199  case TargetOpcode::G_SEXT:
200  return tryCombineSExt(MI, DeadInsts);
201  case TargetOpcode::G_UNMERGE_VALUES:
202  return tryCombineMerges(MI, DeadInsts);
203  }
204  }
205 
206 private:
207  /// Mark MI as dead. If a def of one of MI's operands, DefMI, would also be
208  /// dead due to MI being killed, then mark DefMI as dead too.
209  void markInstAndDefDead(MachineInstr &MI, MachineInstr &DefMI,
210  SmallVectorImpl<MachineInstr *> &DeadInsts) {
211  DeadInsts.push_back(&MI);
212  if (MRI.hasOneUse(DefMI.getOperand(0).getReg()))
213  DeadInsts.push_back(&DefMI);
214  }
215  /// Checks if the target legalizer info has specified anything about the
216  /// instruction, or if unsupported.
217  bool isInstUnsupported(unsigned Opcode, const LLT &DstTy) const {
218  auto Action = LI.getAction({Opcode, 0, DstTy});
219  return Action.first == LegalizerInfo::LegalizeAction::Unsupported ||
220  Action.first == LegalizerInfo::LegalizeAction::NotFound;
221  }
222 };
223 
224 } // namespace llvm
void push_back(const T &Elt)
Definition: SmallVector.h:212
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1542
static APInt getAllOnesValue(unsigned numBits)
Get the all-ones value.
Definition: APInt.h:555
bool tryCombineMerges(MachineInstr &MI, SmallVectorImpl< MachineInstr *> &DeadInsts)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
unsigned getReg() const
getReg - Returns the register number.
MachineInstrBuilder buildAnyExtOrTrunc(DstTy &&Dst, UseArgTy &&Use)
Res = COPY Op depending on the differing sizes of Res and Op.
bool tryCombineAnyExt(MachineInstr &MI, SmallVectorImpl< MachineInstr *> &DeadInsts)
std::pair< LegalizeAction, LLT > getAction(const InstrAspect &Aspect) const
Determine what action should be taken to legalize the given generic instruction opcode, type-index and type.
unsigned getNumOperands() const
Access to explicit operands of the instruction.
Definition: MachineInstr.h:293
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:290
MachineInstr * getVRegDef(unsigned Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
const RegList & Regs
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
MachineInstrBuilder buildInstr(unsigned Opcode)
Build and insert <empty> = Opcode <empty>.
Helper class to build MachineInstr.
void setInstr(MachineInstr &MI)
Set the insertion point to before MI.
bool tryCombineSExt(MachineInstr &MI, SmallVectorImpl< MachineInstr *> &DeadInsts)
MachineInstrBuilder MachineInstrBuilder & DefMI
unsigned getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
This file declares the MachineIRBuilder class.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
LegalizerCombiner(MachineIRBuilder &B, MachineRegisterInfo &MRI, const LegalizerInfo &LI)
Class for arbitrary precision integers.
Definition: APInt.h:69
void replaceRegWith(unsigned FromReg, unsigned ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:59
bool hasOneUse(unsigned RegNo) const
hasOneUse - Return true if there is exactly one instruction using the specified register.
MachineInstrBuilder buildConstant(unsigned Res, const ConstantInt &Val)
Build and insert Res = G_CONSTANT Val.
LLT getType(unsigned VReg) const
Get the low-level type of VReg or LLT{} if VReg is not a generic (target independent) virtual registe...
MachineInstrBuilder buildUnmerge(ArrayRef< unsigned > Res, unsigned Op)
Build and insert Res0<def>, ...
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:81
#define DEBUG(X)
Definition: Debug.h:118
IRTranslator LLVM IR MI
bool tryCombineInstruction(MachineInstr &MI, SmallVectorImpl< MachineInstr *> &DeadInsts)
Try to combine away MI.
bool tryCombineZExt(MachineInstr &MI, SmallVectorImpl< MachineInstr *> &DeadInsts)
MachineInstrBuilder buildAnd(DstTy &&Dst, UseArgsTy &&... UseArgs)
Build and insert Res<def> = G_AND Op0, Op1.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:295
MachineInstrBuilder buildMerge(unsigned Res, ArrayRef< unsigned > Ops)
Build and insert Res<def> = G_MERGE_VALUES Op0, ...