blob: 923fa213e7bab48224f65369330e6ec2bb57b47c [file] [log] [blame]
Chris Lattnercab0b442003-01-13 20:01:16 +00001//===-- PhiElimination.cpp - Eliminate PHI nodes by inserting copies ------===//
Misha Brukman835702a2005-04-21 22:36:52 +00002//
John Criswell482202a2003-10-20 19:43:21 +00003// The LLVM Compiler Infrastructure
4//
Chris Lattnerf3ebc3f2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Misha Brukman835702a2005-04-21 22:36:52 +00007//
John Criswell482202a2003-10-20 19:43:21 +00008//===----------------------------------------------------------------------===//
Chris Lattnercab0b442003-01-13 20:01:16 +00009//
10// This pass eliminates machine instruction PHI nodes by inserting copy
11// instructions. This destroys SSA information, but is the desired input for
12// some register allocators.
13//
14//===----------------------------------------------------------------------===//
15
Chris Lattneraee775a2006-12-19 22:41:21 +000016#define DEBUG_TYPE "phielim"
Cameron Zwarichda592a9e2010-12-05 19:51:05 +000017#include "PHIEliminationUtils.h"
Misha Brukman584ed832005-05-05 23:45:17 +000018#include "llvm/CodeGen/LiveVariables.h"
Chris Lattner43df6c22004-02-23 18:38:20 +000019#include "llvm/CodeGen/Passes.h"
Jakob Stoklund Olesen15ca0092009-11-14 00:38:06 +000020#include "llvm/CodeGen/MachineDominators.h"
Chris Lattnercab0b442003-01-13 20:01:16 +000021#include "llvm/CodeGen/MachineInstr.h"
Evan Cheng33281862008-04-11 17:54:45 +000022#include "llvm/CodeGen/MachineInstrBuilder.h"
Evan Chengf259efd2010-08-17 01:20:36 +000023#include "llvm/CodeGen/MachineLoopInfo.h"
Chris Lattnera10fff52007-12-31 04:13:23 +000024#include "llvm/CodeGen/MachineRegisterInfo.h"
Chris Lattnerb06015a2010-02-09 19:54:29 +000025#include "llvm/Target/TargetInstrInfo.h"
Jakob Stoklund Olesen4f7fd3b2009-11-11 19:31:31 +000026#include "llvm/Function.h"
Chris Lattnercab0b442003-01-13 20:01:16 +000027#include "llvm/Target/TargetMachine.h"
Evan Chengaacf4f12008-04-03 16:38:20 +000028#include "llvm/ADT/SmallPtrSet.h"
Reid Spencer7c16caa2004-09-01 22:55:40 +000029#include "llvm/ADT/STLExtras.h"
Chris Lattner57b21f92005-10-03 07:22:07 +000030#include "llvm/ADT/Statistic.h"
Chris Lattner3d27be12006-08-27 12:54:02 +000031#include "llvm/Support/Compiler.h"
Jakob Stoklund Olesen4453dc92009-11-10 22:01:05 +000032#include "llvm/Support/Debug.h"
Chris Lattner57b21f92005-10-03 07:22:07 +000033#include <algorithm>
Evan Chengbe3d44c2008-04-02 17:23:50 +000034#include <map>
Chris Lattner43df6c22004-02-23 18:38:20 +000035using namespace llvm;
Brian Gaeke960707c2003-11-11 22:41:34 +000036
Cameron Zwaricha3fb8cb2010-12-05 21:39:42 +000037namespace {
38 class PHIElimination : public MachineFunctionPass {
39 MachineRegisterInfo *MRI; // Machine register information
40
41 public:
42 static char ID; // Pass identification, replacement for typeid
43 PHIElimination() : MachineFunctionPass(ID) {
44 initializePHIEliminationPass(*PassRegistry::getPassRegistry());
45 }
46
47 virtual bool runOnMachineFunction(MachineFunction &Fn);
48 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
49
50 private:
51 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
52 /// in predecessor basic blocks.
53 ///
54 bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB);
55 void LowerAtomicPHINode(MachineBasicBlock &MBB,
56 MachineBasicBlock::iterator AfterPHIsIt);
57
58 /// analyzePHINodes - Gather information about the PHI nodes in
59 /// here. In particular, we want to map the number of uses of a virtual
60 /// register which is used in a PHI node. We map that to the BB the
61 /// vreg is coming from. This is used later to determine when the vreg
62 /// is killed in the BB.
63 ///
64 void analyzePHINodes(const MachineFunction& Fn);
65
66 /// Split critical edges where necessary for good coalescer performance.
67 bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB,
68 LiveVariables &LV, MachineLoopInfo *MLI);
69
70 typedef std::pair<unsigned, unsigned> BBVRegPair;
71 typedef DenseMap<BBVRegPair, unsigned> VRegPHIUse;
72
73 VRegPHIUse VRegPHIUseCount;
74
75 // Defs of PHI sources which are implicit_def.
76 SmallPtrSet<MachineInstr*, 4> ImpDefs;
77
78 // Map reusable lowered PHI node -> incoming join register.
79 typedef DenseMap<MachineInstr*, unsigned,
80 MachineInstrExpressionTrait> LoweredPHIMap;
81 LoweredPHIMap LoweredPHIs;
82 };
83}
84
Chris Lattneraee775a2006-12-19 22:41:21 +000085STATISTIC(NumAtomic, "Number of atomic phis lowered");
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +000086STATISTIC(NumReused, "Number of reused lowered phis");
Jakob Stoklund Olesen4453dc92009-11-10 22:01:05 +000087
Lang Hamesaa037752009-07-21 23:47:33 +000088char PHIElimination::ID = 0;
Owen Andersond31d82d2010-08-23 17:52:01 +000089INITIALIZE_PASS(PHIElimination, "phi-node-elimination",
Owen Andersondf7a4f22010-10-07 22:25:06 +000090 "Eliminate PHI nodes for register allocation", false, false)
Dan Gohmand78c4002008-05-13 00:00:25 +000091
Cameron Zwaricha3fb8cb2010-12-05 21:39:42 +000092char& llvm::PHIEliminationID = PHIElimination::ID;
Chris Lattnercab0b442003-01-13 20:01:16 +000093
Cameron Zwaricha3fb8cb2010-12-05 21:39:42 +000094void PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
Dan Gohman04023152009-07-31 23:37:33 +000095 AU.addPreserved<LiveVariables>();
Jakob Stoklund Olesen15ca0092009-11-14 00:38:06 +000096 AU.addPreserved<MachineDominatorTree>();
Evan Cheng16bfe5b2010-08-17 21:00:37 +000097 AU.addPreserved<MachineLoopInfo>();
Dan Gohman04023152009-07-31 23:37:33 +000098 MachineFunctionPass::getAnalysisUsage(AU);
99}
Lang Hamesaa037752009-07-21 23:47:33 +0000100
Cameron Zwaricha3fb8cb2010-12-05 21:39:42 +0000101bool PHIElimination::runOnMachineFunction(MachineFunction &MF) {
Evan Chenga5c0cc32010-05-04 17:12:26 +0000102 MRI = &MF.getRegInfo();
Evan Chengaacf4f12008-04-03 16:38:20 +0000103
Evan Chengaacf4f12008-04-03 16:38:20 +0000104 bool Changed = false;
105
Jakob Stoklund Olesen4f7fd3b2009-11-11 19:31:31 +0000106 // Split critical edges to help the coalescer
Evan Cheng16bfe5b2010-08-17 21:00:37 +0000107 if (LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>()) {
108 MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
Evan Chenga5c0cc32010-05-04 17:12:26 +0000109 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
Evan Cheng16bfe5b2010-08-17 21:00:37 +0000110 Changed |= SplitPHIEdges(MF, *I, *LV, MLI);
111 }
Jakob Stoklund Olesen4f7fd3b2009-11-11 19:31:31 +0000112
113 // Populate VRegPHIUseCount
Evan Chenga5c0cc32010-05-04 17:12:26 +0000114 analyzePHINodes(MF);
Jakob Stoklund Olesen4f7fd3b2009-11-11 19:31:31 +0000115
Evan Chengaacf4f12008-04-03 16:38:20 +0000116 // Eliminate PHI instructions by inserting copies into predecessor blocks.
Evan Chenga5c0cc32010-05-04 17:12:26 +0000117 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
118 Changed |= EliminatePHINodes(MF, *I);
Evan Chengaacf4f12008-04-03 16:38:20 +0000119
120 // Remove dead IMPLICIT_DEF instructions.
Bill Wendling819c3562009-12-17 23:42:32 +0000121 for (SmallPtrSet<MachineInstr*, 4>::iterator I = ImpDefs.begin(),
Evan Chengaacf4f12008-04-03 16:38:20 +0000122 E = ImpDefs.end(); I != E; ++I) {
123 MachineInstr *DefMI = *I;
124 unsigned DefReg = DefMI->getOperand(0).getReg();
Evan Chengeae56b52010-03-25 01:01:37 +0000125 if (MRI->use_nodbg_empty(DefReg))
Evan Chengaacf4f12008-04-03 16:38:20 +0000126 DefMI->eraseFromParent();
127 }
128
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +0000129 // Clean up the lowered PHI instructions.
130 for (LoweredPHIMap::iterator I = LoweredPHIs.begin(), E = LoweredPHIs.end();
131 I != E; ++I)
Evan Chenga5c0cc32010-05-04 17:12:26 +0000132 MF.DeleteMachineInstr(I->first);
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +0000133
Bill Wendling819c3562009-12-17 23:42:32 +0000134 LoweredPHIs.clear();
Evan Chengaacf4f12008-04-03 16:38:20 +0000135 ImpDefs.clear();
136 VRegPHIUseCount.clear();
Evan Chenga5c0cc32010-05-04 17:12:26 +0000137
Evan Chengaacf4f12008-04-03 16:38:20 +0000138 return Changed;
139}
140
Chris Lattnercab0b442003-01-13 20:01:16 +0000141/// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
142/// predecessor basic blocks.
143///
Cameron Zwaricha3fb8cb2010-12-05 21:39:42 +0000144bool PHIElimination::EliminatePHINodes(MachineFunction &MF,
Lang Hamesaa037752009-07-21 23:47:33 +0000145 MachineBasicBlock &MBB) {
Chris Lattnerb06015a2010-02-09 19:54:29 +0000146 if (MBB.empty() || !MBB.front().isPHI())
Chris Lattner5f096e22005-10-03 04:47:08 +0000147 return false; // Quick exit for basic blocks without PHIs.
Chris Lattnercab0b442003-01-13 20:01:16 +0000148
Chris Lattnera2f7b9b2004-05-10 18:47:18 +0000149 // Get an iterator to the first instruction after the last PHI node (this may
Chris Lattner5f096e22005-10-03 04:47:08 +0000150 // also be the end of the basic block).
Cameron Zwarichfbd47dc2010-12-04 20:40:15 +0000151 MachineBasicBlock::iterator AfterPHIsIt = MBB.SkipPHIsAndLabels(MBB.begin());
Chris Lattnera2f7b9b2004-05-10 18:47:18 +0000152
Chris Lattnerb06015a2010-02-09 19:54:29 +0000153 while (MBB.front().isPHI())
Bill Wendling5d409822006-09-28 07:10:24 +0000154 LowerAtomicPHINode(MBB, AfterPHIsIt);
155
Chris Lattner5f096e22005-10-03 04:47:08 +0000156 return true;
157}
Misha Brukman835702a2005-04-21 22:36:52 +0000158
Evan Cheng18e46d42008-06-19 01:21:26 +0000159/// isSourceDefinedByImplicitDef - Return true if all sources of the phi node
160/// are implicit_def's.
Bill Wendling6b8bd512008-05-12 22:15:05 +0000161static bool isSourceDefinedByImplicitDef(const MachineInstr *MPhi,
Evan Cheng18e46d42008-06-19 01:21:26 +0000162 const MachineRegisterInfo *MRI) {
Evan Chengbec201f2008-05-10 00:17:50 +0000163 for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) {
164 unsigned SrcReg = MPhi->getOperand(i).getReg();
Bill Wendling6b8bd512008-05-12 22:15:05 +0000165 const MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
Chris Lattnerb06015a2010-02-09 19:54:29 +0000166 if (!DefMI || !DefMI->isImplicitDef())
Evan Chengbec201f2008-05-10 00:17:50 +0000167 return false;
168 }
169 return true;
Evan Cheng33281862008-04-11 17:54:45 +0000170}
171
Evan Cheng94419d62009-03-13 22:59:14 +0000172
Evan Cheng94419d62009-03-13 22:59:14 +0000173
Chris Lattner5f096e22005-10-03 04:47:08 +0000174/// LowerAtomicPHINode - Lower the PHI node at the top of the specified block,
175/// under the assuption that it needs to be lowered in a way that supports
176/// atomic execution of PHIs. This lowering method is always correct all of the
177/// time.
Jakob Stoklund Olesen19f235e2009-11-10 22:00:56 +0000178///
Cameron Zwaricha3fb8cb2010-12-05 21:39:42 +0000179void PHIElimination::LowerAtomicPHINode(
Lang Hamesaa037752009-07-21 23:47:33 +0000180 MachineBasicBlock &MBB,
181 MachineBasicBlock::iterator AfterPHIsIt) {
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +0000182 ++NumAtomic;
Chris Lattner5f096e22005-10-03 04:47:08 +0000183 // Unlink the PHI node from the basic block, but don't delete the PHI yet.
184 MachineInstr *MPhi = MBB.remove(MBB.begin());
Chris Lattnercab0b442003-01-13 20:01:16 +0000185
Evan Cheng33281862008-04-11 17:54:45 +0000186 unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2;
Chris Lattner5f096e22005-10-03 04:47:08 +0000187 unsigned DestReg = MPhi->getOperand(0).getReg();
Jakob Stoklund Olesen952a6212010-08-18 16:09:47 +0000188 assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs");
Evan Cheng7d98a482008-07-03 09:09:37 +0000189 bool isDead = MPhi->getOperand(0).isDead();
Misha Brukman835702a2005-04-21 22:36:52 +0000190
Bill Wendling5d409822006-09-28 07:10:24 +0000191 // Create a new register for the incoming PHI arguments.
Chris Lattner5f096e22005-10-03 04:47:08 +0000192 MachineFunction &MF = *MBB.getParent();
Evan Cheng7d98a482008-07-03 09:09:37 +0000193 unsigned IncomingReg = 0;
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +0000194 bool reusedIncoming = false; // Is IncomingReg reused from an earlier PHI?
Chris Lattnercab0b442003-01-13 20:01:16 +0000195
Bill Wendling6b8bd512008-05-12 22:15:05 +0000196 // Insert a register to register copy at the top of the current block (but
Chris Lattner5f096e22005-10-03 04:47:08 +0000197 // after any remaining phi nodes) which copies the new incoming register
198 // into the phi node destination.
Owen Anderson7a73ae92007-12-31 06:32:00 +0000199 const TargetInstrInfo *TII = MF.getTarget().getInstrInfo();
Evan Chengbec201f2008-05-10 00:17:50 +0000200 if (isSourceDefinedByImplicitDef(MPhi, MRI))
Evan Cheng7d98a482008-07-03 09:09:37 +0000201 // If all sources of a PHI node are implicit_def, just emit an
202 // implicit_def instead of a copy.
Bill Wendling67cd3952009-02-03 02:29:34 +0000203 BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
Chris Lattnerb06015a2010-02-09 19:54:29 +0000204 TII->get(TargetOpcode::IMPLICIT_DEF), DestReg);
Evan Cheng7d98a482008-07-03 09:09:37 +0000205 else {
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +0000206 // Can we reuse an earlier PHI node? This only happens for critical edges,
207 // typically those created by tail duplication.
208 unsigned &entry = LoweredPHIs[MPhi];
209 if (entry) {
210 // An identical PHI node was already lowered. Reuse the incoming register.
211 IncomingReg = entry;
212 reusedIncoming = true;
213 ++NumReused;
Jakob Stoklund Olesen1331a152011-01-09 03:05:53 +0000214 DEBUG(dbgs() << "Reusing " << PrintReg(IncomingReg) << " for " << *MPhi);
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +0000215 } else {
Jakob Stoklund Olesene50d30d2010-07-10 19:08:25 +0000216 const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg);
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +0000217 entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC);
218 }
Jakob Stoklund Olesene50d30d2010-07-10 19:08:25 +0000219 BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
220 TII->get(TargetOpcode::COPY), DestReg)
221 .addReg(IncomingReg);
Evan Cheng7d98a482008-07-03 09:09:37 +0000222 }
Chris Lattner5f096e22005-10-03 04:47:08 +0000223
Bill Wendling6b8bd512008-05-12 22:15:05 +0000224 // Update live variable information if there is any.
Duncan Sands5a913d62009-01-28 13:14:17 +0000225 LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>();
Chris Lattner5f096e22005-10-03 04:47:08 +0000226 if (LV) {
227 MachineInstr *PHICopy = prior(AfterPHIsIt);
228
Evan Cheng7d98a482008-07-03 09:09:37 +0000229 if (IncomingReg) {
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +0000230 LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg);
231
Evan Cheng7d98a482008-07-03 09:09:37 +0000232 // Increment use count of the newly created virtual register.
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +0000233 VI.NumUses++;
Jakob Stoklund Olesen38b76e22010-02-23 22:43:58 +0000234 LV->setPHIJoin(IncomingReg);
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +0000235
236 // When we are reusing the incoming register, it may already have been
237 // killed in this block. The old kill will also have been inserted at
238 // AfterPHIsIt, so it appears before the current PHICopy.
239 if (reusedIncoming)
240 if (MachineInstr *OldKill = VI.findKill(&MBB)) {
David Greene25552922010-01-05 01:24:24 +0000241 DEBUG(dbgs() << "Remove old kill from " << *OldKill);
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +0000242 LV->removeVirtualRegisterKilled(IncomingReg, OldKill);
243 DEBUG(MBB.dump());
244 }
Evan Chenga5a0c7c2007-04-18 00:36:11 +0000245
Evan Cheng7d98a482008-07-03 09:09:37 +0000246 // Add information to LiveVariables to know that the incoming value is
247 // killed. Note that because the value is defined in several places (once
248 // each for each incoming block), the "def" block and instruction fields
249 // for the VarInfo is not filled in.
250 LV->addVirtualRegisterKilled(IncomingReg, PHICopy);
Evan Cheng7d98a482008-07-03 09:09:37 +0000251 }
Misha Brukman835702a2005-04-21 22:36:52 +0000252
Bill Wendling6b8bd512008-05-12 22:15:05 +0000253 // Since we are going to be deleting the PHI node, if it is the last use of
254 // any registers, or if the value itself is dead, we need to move this
Chris Lattner5f096e22005-10-03 04:47:08 +0000255 // information over to the new copy we just inserted.
Chris Lattner5f096e22005-10-03 04:47:08 +0000256 LV->removeVirtualRegistersKilled(MPhi);
Chris Lattnercab0b442003-01-13 20:01:16 +0000257
Chris Lattner57b21f92005-10-03 07:22:07 +0000258 // If the result is dead, update LV.
Evan Cheng7d98a482008-07-03 09:09:37 +0000259 if (isDead) {
Chris Lattner57b21f92005-10-03 07:22:07 +0000260 LV->addVirtualRegisterDead(DestReg, PHICopy);
Evan Cheng7d98a482008-07-03 09:09:37 +0000261 LV->removeVirtualRegisterDead(DestReg, MPhi);
Chris Lattner5f096e22005-10-03 04:47:08 +0000262 }
263 }
Chris Lattnercab0b442003-01-13 20:01:16 +0000264
Bill Wendling6b8bd512008-05-12 22:15:05 +0000265 // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
Chris Lattner5f096e22005-10-03 04:47:08 +0000266 for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2)
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +0000267 --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i+1).getMBB()->getNumber(),
Chris Lattnera5bb3702007-12-30 23:10:15 +0000268 MPhi->getOperand(i).getReg())];
Chris Lattner51ae8172003-05-12 14:28:28 +0000269
Bill Wendling6b8bd512008-05-12 22:15:05 +0000270 // Now loop over all of the incoming arguments, changing them to copy into the
271 // IncomingReg register in the corresponding predecessor basic block.
Evan Chengaacf4f12008-04-03 16:38:20 +0000272 SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto;
Evan Cheng33281862008-04-11 17:54:45 +0000273 for (int i = NumSrcs - 1; i >= 0; --i) {
274 unsigned SrcReg = MPhi->getOperand(i*2+1).getReg();
Jakob Stoklund Olesen952a6212010-08-18 16:09:47 +0000275 unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg();
276
Dan Gohman3a4be0f2008-02-10 18:45:23 +0000277 assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
Chris Lattner57b21f92005-10-03 07:22:07 +0000278 "Machine PHI Operands must all be virtual registers!");
Chris Lattner5f096e22005-10-03 04:47:08 +0000279
Lang Hamesa77a3c32009-07-23 04:34:03 +0000280 // Get the MachineBasicBlock equivalent of the BasicBlock that is the source
281 // path the PHI.
282 MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB();
283
Bill Wendling6b8bd512008-05-12 22:15:05 +0000284 // If source is defined by an implicit def, there is no need to insert a
Evan Cheng7d98a482008-07-03 09:09:37 +0000285 // copy.
Evan Chengaacf4f12008-04-03 16:38:20 +0000286 MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
Chris Lattnerb06015a2010-02-09 19:54:29 +0000287 if (DefMI->isImplicitDef()) {
Evan Chengaacf4f12008-04-03 16:38:20 +0000288 ImpDefs.insert(DefMI);
289 continue;
290 }
291
Chris Lattner5f096e22005-10-03 04:47:08 +0000292 // Check to make sure we haven't already emitted the copy for this block.
Bill Wendling6b8bd512008-05-12 22:15:05 +0000293 // This can happen because PHI nodes may have multiple entries for the same
294 // basic block.
Evan Chengaacf4f12008-04-03 16:38:20 +0000295 if (!MBBsInsertedInto.insert(&opBlock))
Chris Lattner57b21f92005-10-03 07:22:07 +0000296 continue; // If the copy has already been emitted, we're done.
Jakob Stoklund Olesen19f235e2009-11-10 22:00:56 +0000297
Bill Wendling6b8bd512008-05-12 22:15:05 +0000298 // Find a safe location to insert the copy, this may be the first terminator
299 // in the block (or end()).
Jakob Stoklund Olesenad205d62009-11-13 21:56:15 +0000300 MachineBasicBlock::iterator InsertPos =
Cameron Zwarichda592a9e2010-12-05 19:51:05 +0000301 findPHICopyInsertPoint(&opBlock, &MBB, SrcReg);
Evan Cheng94419d62009-03-13 22:59:14 +0000302
Chris Lattner57b21f92005-10-03 07:22:07 +0000303 // Insert the copy.
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +0000304 if (!reusedIncoming && IncomingReg)
Jakob Stoklund Olesene50d30d2010-07-10 19:08:25 +0000305 BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
Jakob Stoklund Olesen952a6212010-08-18 16:09:47 +0000306 TII->get(TargetOpcode::COPY), IncomingReg).addReg(SrcReg, 0, SrcSubReg);
Chris Lattner5f096e22005-10-03 04:47:08 +0000307
Chris Lattner57b21f92005-10-03 07:22:07 +0000308 // Now update live variable information if we have it. Otherwise we're done
309 if (!LV) continue;
Jakob Stoklund Olesen19f235e2009-11-10 22:00:56 +0000310
Bill Wendling6b8bd512008-05-12 22:15:05 +0000311 // We want to be able to insert a kill of the register if this PHI (aka, the
312 // copy we just inserted) is the last use of the source value. Live
313 // variable analysis conservatively handles this by saying that the value is
314 // live until the end of the block the PHI entry lives in. If the value
315 // really is dead at the PHI copy, there will be no successor blocks which
316 // have the value live-in.
Chris Lattner57b21f92005-10-03 07:22:07 +0000317
Bill Wendling6b8bd512008-05-12 22:15:05 +0000318 // Also check to see if this register is in use by another PHI node which
319 // has not yet been eliminated. If so, it will be killed at an appropriate
320 // point later.
Chris Lattner57b21f92005-10-03 07:22:07 +0000321
322 // Is it used by any PHI instructions in this block?
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +0000323 bool ValueIsUsed = VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)];
Chris Lattner57b21f92005-10-03 07:22:07 +0000324
Bill Wendling6b8bd512008-05-12 22:15:05 +0000325 // Okay, if we now know that the value is not live out of the block, we can
326 // add a kill marker in this block saying that it kills the incoming value!
Jakob Stoklund Olesendefc4702009-12-01 17:13:31 +0000327 if (!ValueIsUsed && !LV->isLiveOut(SrcReg, opBlock)) {
Chris Lattner227e9362006-01-04 07:12:21 +0000328 // In our final twist, we have to decide which instruction kills the
Bill Wendling6b8bd512008-05-12 22:15:05 +0000329 // register. In most cases this is the copy, however, the first
Chris Lattner227e9362006-01-04 07:12:21 +0000330 // terminator instruction at the end of the block may also use the value.
331 // In this case, we should mark *it* as being the killing block, not the
332 // copy.
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +0000333 MachineBasicBlock::iterator KillInst;
Evan Chengaacf4f12008-04-03 16:38:20 +0000334 MachineBasicBlock::iterator Term = opBlock.getFirstTerminator();
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +0000335 if (Term != opBlock.end() && Term->readsRegister(SrcReg)) {
336 KillInst = Term;
Jakob Stoklund Olesen19f235e2009-11-10 22:00:56 +0000337
Chris Lattner227e9362006-01-04 07:12:21 +0000338 // Check that no other terminators use values.
339#ifndef NDEBUG
Chris Lattnera48f44d2009-12-03 00:50:42 +0000340 for (MachineBasicBlock::iterator TI = llvm::next(Term);
341 TI != opBlock.end(); ++TI) {
Evan Chengaacf4f12008-04-03 16:38:20 +0000342 assert(!TI->readsRegister(SrcReg) &&
Chris Lattner227e9362006-01-04 07:12:21 +0000343 "Terminator instructions cannot use virtual registers unless"
344 "they are the first terminator in a block!");
345 }
346#endif
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +0000347 } else if (reusedIncoming || !IncomingReg) {
348 // We may have to rewind a bit if we didn't insert a copy this time.
349 KillInst = Term;
350 while (KillInst != opBlock.begin())
351 if ((--KillInst)->readsRegister(SrcReg))
352 break;
353 } else {
354 // We just inserted this copy.
355 KillInst = prior(InsertPos);
Chris Lattner227e9362006-01-04 07:12:21 +0000356 }
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +0000357 assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction");
Jakob Stoklund Olesen19f235e2009-11-10 22:00:56 +0000358
Chris Lattner227e9362006-01-04 07:12:21 +0000359 // Finally, mark it killed.
360 LV->addVirtualRegisterKilled(SrcReg, KillInst);
Chris Lattner57b21f92005-10-03 07:22:07 +0000361
362 // This vreg no longer lives all of the way through opBlock.
363 unsigned opBlockNum = opBlock.getNumber();
Jakob Stoklund Olesen19f235e2009-11-10 22:00:56 +0000364 LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);
Chris Lattnercab0b442003-01-13 20:01:16 +0000365 }
Chris Lattnercab0b442003-01-13 20:01:16 +0000366 }
Jakob Stoklund Olesen19f235e2009-11-10 22:00:56 +0000367
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +0000368 // Really delete the PHI instruction now, if it is not in the LoweredPHIs map.
369 if (reusedIncoming || !IncomingReg)
370 MF.DeleteMachineInstr(MPhi);
Chris Lattnercab0b442003-01-13 20:01:16 +0000371}
Bill Wendling5d409822006-09-28 07:10:24 +0000372
373/// analyzePHINodes - Gather information about the PHI nodes in here. In
374/// particular, we want to map the number of uses of a virtual register which is
375/// used in a PHI node. We map that to the BB the vreg is coming from. This is
376/// used later to determine when the vreg is killed in the BB.
377///
Cameron Zwaricha3fb8cb2010-12-05 21:39:42 +0000378void PHIElimination::analyzePHINodes(const MachineFunction& MF) {
Evan Chenga5c0cc32010-05-04 17:12:26 +0000379 for (MachineFunction::const_iterator I = MF.begin(), E = MF.end();
Bill Wendling5d409822006-09-28 07:10:24 +0000380 I != E; ++I)
381 for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end();
Chris Lattnerb06015a2010-02-09 19:54:29 +0000382 BBI != BBE && BBI->isPHI(); ++BBI)
Bill Wendling5d409822006-09-28 07:10:24 +0000383 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
Jakob Stoklund Olesenec20a882009-12-16 18:55:53 +0000384 ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i+1).getMBB()->getNumber(),
Chris Lattnera5bb3702007-12-30 23:10:15 +0000385 BBI->getOperand(i).getReg())];
Bill Wendling5d409822006-09-28 07:10:24 +0000386}
Jakob Stoklund Olesen19f235e2009-11-10 22:00:56 +0000387
Cameron Zwaricha3fb8cb2010-12-05 21:39:42 +0000388bool PHIElimination::SplitPHIEdges(MachineFunction &MF,
Jakob Stoklund Olesen736888f2009-11-18 18:01:35 +0000389 MachineBasicBlock &MBB,
Evan Cheng16bfe5b2010-08-17 21:00:37 +0000390 LiveVariables &LV,
391 MachineLoopInfo *MLI) {
Chris Lattnerb06015a2010-02-09 19:54:29 +0000392 if (MBB.empty() || !MBB.front().isPHI() || MBB.isLandingPad())
Jakob Stoklund Olesen4f7fd3b2009-11-11 19:31:31 +0000393 return false; // Quick exit for basic blocks without PHIs.
Jakob Stoklund Olesen736888f2009-11-18 18:01:35 +0000394
Evan Chengf259efd2010-08-17 01:20:36 +0000395 bool Changed = false;
Jakob Stoklund Olesen4453dc92009-11-10 22:01:05 +0000396 for (MachineBasicBlock::const_iterator BBI = MBB.begin(), BBE = MBB.end();
Chris Lattnerb06015a2010-02-09 19:54:29 +0000397 BBI != BBE && BBI->isPHI(); ++BBI) {
Jakob Stoklund Olesen4453dc92009-11-10 22:01:05 +0000398 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
399 unsigned Reg = BBI->getOperand(i).getReg();
400 MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
401 // We break edges when registers are live out from the predecessor block
Jakob Stoklund Olesen4f7fd3b2009-11-11 19:31:31 +0000402 // (not considering PHI nodes). If the register is live in to this block
403 // anyway, we would gain nothing from splitting.
Evan Cheng647c5592010-08-17 17:43:50 +0000404 // Avoid splitting backedges of loops. It would introduce small
405 // out-of-line blocks into the loop which is very bad for code placement.
406 if (PreMBB != &MBB &&
407 !LV.isLiveIn(Reg, MBB) && LV.isLiveOut(Reg, *PreMBB)) {
Evan Cheng16bfe5b2010-08-17 21:00:37 +0000408 if (!MLI ||
409 !(MLI->getLoopFor(PreMBB) == MLI->getLoopFor(&MBB) &&
Evan Cheng647c5592010-08-17 17:43:50 +0000410 MLI->isLoopHeader(&MBB)))
411 Changed |= PreMBB->SplitCriticalEdge(&MBB, this) != 0;
412 }
Jakob Stoklund Olesen4453dc92009-11-10 22:01:05 +0000413 }
414 }
Jakob Stoklund Olesen4f7fd3b2009-11-11 19:31:31 +0000415 return true;
Jakob Stoklund Olesen4453dc92009-11-10 22:01:05 +0000416}