MachineSSAUpdater.cpp revision fde18e5eff86b5055d7ed541fa87cde5aa1ab31c
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===- MachineSSAUpdater.cpp - Unstructured SSA Update Tool ---------------===// 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The LLVM Compiler Infrastructure 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file is distributed under the University of Illinois Open Source 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// License. See LICENSE.TXT for details. 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===----------------------------------------------------------------------===// 92a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 107d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// This file implements the MachineSSAUpdater class. It's based on SSAUpdater 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// class in lib/Transforms/Utils. 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 14eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/CodeGen/MachineSSAUpdater.h" 16f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)#include "llvm/CodeGen/MachineInstr.h" 17c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/CodeGen/MachineInstrBuilder.h" 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/CodeGen/MachineRegisterInfo.h" 19c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/Target/TargetInstrInfo.h" 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Target/TargetMachine.h" 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Target/TargetRegisterInfo.h" 222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/ADT/DenseMap.h" 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/SmallVector.h" 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Support/AlignOf.h" 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Support/Allocator.h" 26c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/Support/Debug.h" 27868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "llvm/Support/ErrorHandling.h" 28c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/Support/raw_ostream.h" 29c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/Transforms/Utils/SSAUpdaterImpl.h" 30c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)using namespace llvm; 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)typedef DenseMap<MachineBasicBlock*, unsigned> AvailableValsTy; 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)static AvailableValsTy &getAvailableVals(void *AV) { 34c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return *static_cast<AvailableValsTy*>(AV); 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 36a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)MachineSSAUpdater::MachineSSAUpdater(MachineFunction &MF, 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SmallVectorImpl<MachineInstr*> *NewPHI) 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : AV(0), InsertedPHIs(NewPHI) { 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TII = MF.getTarget().getInstrInfo(); 41868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) MRI = &MF.getRegInfo(); 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)MachineSSAUpdater::~MachineSSAUpdater() { 455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) delete &getAvailableVals(AV); 465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// Initialize - Reset this object to get ready for a new set of SSA 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// updates. ProtoValue is the value used to name PHI nodes. 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void MachineSSAUpdater::Initialize(unsigned V) { 515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (AV == 0) 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AV = new AvailableValsTy(); 53868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) else 54868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) getAvailableVals(AV).clear(); 55868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VR = V; 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VRC = MRI->getRegClass(VR); 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// HasValueForBlock - Return true if the MachineSSAUpdater already has a value for 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// the specified block. 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool MachineSSAUpdater::HasValueForBlock(MachineBasicBlock *BB) const { 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return getAvailableVals(AV).count(BB); 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// AddAvailableValue - Indicate that a rewritten value is available in the 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// specified block with the specified value. 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void MachineSSAUpdater::AddAvailableValue(MachineBasicBlock *BB, unsigned V) { 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) getAvailableVals(AV)[BB] = V; 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// live at the end of the specified block. 74558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdochunsigned MachineSSAUpdater::GetValueAtEndOfBlock(MachineBasicBlock *BB) { 75a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) return GetValueAtEndOfBlockInternal(BB); 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 77868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 78868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)static 79868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)unsigned LookForIdenticalPHI(MachineBasicBlock *BB, 80868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) SmallVector<std::pair<MachineBasicBlock*, unsigned>, 8> &PredValues) { 81868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (BB->empty()) 82868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return 0; 83868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 84868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) MachineBasicBlock::iterator I = BB->front(); 854e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) if (!I->isPHI()) 864e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) return 0; 874e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) 882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) AvailableValsTy AVals; 894e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) for (unsigned i = 0, e = PredValues.size(); i != e; ++i) 904e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) AVals[PredValues[i].first] = PredValues[i].second; 914e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) while (I != BB->end() && I->isPHI()) { 924e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) bool Same = true; 934e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) for (unsigned i = 1, e = I->getNumOperands(); i != e; i += 2) { 944e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) unsigned SrcReg = I->getOperand(i).getReg(); 952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) MachineBasicBlock *SrcBB = I->getOperand(i+1).getMBB(); 964e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) if (AVals[SrcBB] != SrcReg) { 972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Same = false; 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 100c2db58bd994c04d98e4ee2cd7565b71548655fe3Ben Murdoch } 101c2db58bd994c04d98e4ee2cd7565b71548655fe3Ben Murdoch if (Same) 102c2db58bd994c04d98e4ee2cd7565b71548655fe3Ben Murdoch return I->getOperand(0).getReg(); 103c2db58bd994c04d98e4ee2cd7565b71548655fe3Ben Murdoch ++I; 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// InsertNewDef - Insert an empty PHI or IMPLICIT_DEF instruction which define 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// a value of the given register class at the start of the specified basic 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// block. It returns the virtual register defined by the instruction. 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)MachineInstr *InsertNewDef(unsigned Opcode, 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *BB, MachineBasicBlock::iterator I, 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const TargetRegisterClass *RC, 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineRegisterInfo *MRI, 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const TargetInstrInfo *TII) { 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned NewVR = MRI->createVirtualRegister(RC); 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return BuildMI(*BB, I, DebugLoc(), TII->get(Opcode), NewVR); 1195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that 1222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// is live in the middle of the specified block. 1232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// 1245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)/// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one 1252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// important case: if there is a definition of the rewritten value after the 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// 'use' in BB. Consider code like this: 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// 1282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// X1 = ... 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// SomeBB: 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// use(X) 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// X2 = ... 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// br Cond, SomeBB, OutBB 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// In this case, there are two values (X1 and X2) added to the AvailableVals 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// set by the client of the rewriter, and those values are both live out of 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// their respective blocks. However, the use of X happens in the *middle* of 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// a block. Because of this, we need to insert a new PHI node in SomeBB to 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// merge the appropriate values, and this value isn't live out of the block. 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)unsigned MachineSSAUpdater::GetValueInMiddleOfBlock(MachineBasicBlock *BB) { 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If there is no definition of the renamed variable in this block, just use 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // GetValueAtEndOfBlock to do our work. 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!HasValueForBlock(BB)) 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return GetValueAtEndOfBlockInternal(BB); 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If there are no predecessors, just return undef. 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (BB->pred_empty()) { 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Insert an implicit_def to represent an undef value. 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF, 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BB, BB->getFirstTerminator(), 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VRC, MRI, TII); 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NewDef->getOperand(0).getReg(); 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Otherwise, we have the hard case. Get the live-in values for each 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // predecessor. 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SmallVector<std::pair<MachineBasicBlock*, unsigned>, 8> PredValues; 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned SingularValue = 0; 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool isFirstPred = true; 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) E = BB->pred_end(); PI != E; ++PI) { 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *PredBB = *PI; 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned PredVal = GetValueAtEndOfBlockInternal(PredBB); 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PredValues.push_back(std::make_pair(PredBB, PredVal)); 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Compute SingularValue. 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (isFirstPred) { 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SingularValue = PredVal; 1702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) isFirstPred = false; 1715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } else if (PredVal != SingularValue) 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SingularValue = 0; 1730f1bc08d4cfcc34181b0b5cbf065c40f687bf740Torne (Richard Coles) } 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Otherwise, if all the merged values are the same, just use it. 176c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (SingularValue != 0) 177c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return SingularValue; 178868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If an identical PHI is already in BB, just reuse it. 180a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) unsigned DupPHI = LookForIdenticalPHI(BB, PredValues); 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (DupPHI) 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return DupPHI; 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Otherwise, we do need a PHI: insert one now. 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->front(); 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineInstr *InsertedPHI = InsertNewDef(TargetOpcode::PHI, BB, 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Loc, VRC, MRI, TII); 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Fill in all the predecessors of the PHI. 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineInstrBuilder MIB(InsertedPHI); 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned i = 0, e = PredValues.size(); i != e; ++i) 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MIB.addReg(PredValues[i].second).addMBB(PredValues[i].first); 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // See if the PHI node can be merged to a single value. This can happen in 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // loop cases when we get a PHI of itself and one other value. 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (unsigned ConstVal = InsertedPHI->isConstantValuePHI()) { 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) InsertedPHI->eraseFromParent(); 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return ConstVal; 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the client wants to know about all new instructions, tell it. 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); 203c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 204c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n"); 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return InsertedPHI->getOperand(0).getReg(); 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static 209c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)MachineBasicBlock *findCorrespondingPred(const MachineInstr *MI, 210c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) MachineOperand *U) { 211c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 212c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (&MI->getOperand(i) == U) 213c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return MI->getOperand(i+1).getMBB(); 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 215a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 216868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) llvm_unreachable("MachineOperand::getParent() failure?"); 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// which use their value in the corresponding predecessor. 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void MachineSSAUpdater::RewriteUse(MachineOperand &U) { 223c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) MachineInstr *UseMI = U.getParent(); 224c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) unsigned NewVR = 0; 225c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (UseMI->isPHI()) { 226c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) MachineBasicBlock *SourceBB = findCorrespondingPred(UseMI, &U); 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NewVR = GetValueAtEndOfBlockInternal(SourceBB); 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NewVR = GetValueInMiddleOfBlock(UseMI->getParent()); 2305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 2315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) U.setReg(NewVR); 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void MachineSSAUpdater::ReplaceRegWith(unsigned OldReg, unsigned NewReg) { 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MRI->replaceRegWith(OldReg, NewReg); 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AvailableValsTy &AvailableVals = getAvailableVals(AV); 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (DenseMap<MachineBasicBlock*, unsigned>::iterator 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) I = AvailableVals.begin(), E = AvailableVals.end(); I != E; ++I) 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (I->second == OldReg) 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) I->second = NewReg; 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// MachinePHIiter - Iterator for PHI operands. This is used for the 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// PHI_iterator in the SSAUpdaterImpl template. 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class MachinePHIiter { 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineInstr *PHI; 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned idx; 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit MachinePHIiter(MachineInstr *P) // begin iterator 2552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) : PHI(P), idx(1) {} 256f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) MachinePHIiter(MachineInstr *P, bool) // end iterator 2571e9bf3e0803691d0a228da41fc608347b6db4340Torne (Richard Coles) : PHI(P), idx(PHI->getNumOperands()) {} 2585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) MachinePHIiter &operator++() { idx += 2; return *this; } 2605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bool operator==(const MachinePHIiter& x) const { return idx == x.idx; } 2612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool operator!=(const MachinePHIiter& x) const { return !operator==(x); } 262a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) unsigned getIncomingValue() { return PHI->getOperand(idx).getReg(); } 263a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) MachineBasicBlock *getIncomingBlock() { 264b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) return PHI->getOperand(idx+1).getMBB(); 2652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) }; 2672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 2682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// SSAUpdaterTraits<MachineSSAUpdater> - Traits for the SSAUpdaterImpl 2704e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles)/// template, specialized for MachineSSAUpdater. 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace llvm { 272f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)template<> 273f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)class SSAUpdaterTraits<MachineSSAUpdater> { 274f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)public: 275f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) typedef MachineBasicBlock BlkT; 276f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) typedef unsigned ValT; 277f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) typedef MachineInstr PhiT; 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef MachineBasicBlock::succ_iterator BlkSucc_iterator; 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); } 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); } 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 283c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) typedef MachinePHIiter PHI_iterator; 284c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); } 285c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) static inline PHI_iterator PHI_end(PhiT *PHI) { 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return PHI_iterator(PHI, true); 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// FindPredecessorBlocks - Put the predecessors of BB into the Preds 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// vector. 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static void FindPredecessorBlocks(MachineBasicBlock *BB, 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SmallVectorImpl<MachineBasicBlock*> *Preds){ 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) E = BB->pred_end(); PI != E; ++PI) 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Preds->push_back(*PI); 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// GetUndefVal - Create an IMPLICIT_DEF instruction with a new register. 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// Add it into the specified block and return the register. 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static unsigned GetUndefVal(MachineBasicBlock *BB, 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineSSAUpdater *Updater) { 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Insert an implicit_def to represent an undef value. 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF, 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BB, BB->getFirstTerminator(), 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Updater->VRC, Updater->MRI, 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Updater->TII); 3072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return NewDef->getOperand(0).getReg(); 3082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// CreateEmptyPHI - Create a PHI instruction that defines a new register. 3115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) /// Add it into the specified block and return the register. 3125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) static unsigned CreateEmptyPHI(MachineBasicBlock *BB, unsigned NumPreds, 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineSSAUpdater *Updater) { 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->front(); 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineInstr *PHI = InsertNewDef(TargetOpcode::PHI, BB, Loc, 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Updater->VRC, Updater->MRI, 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Updater->TII); 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return PHI->getOperand(0).getReg(); 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 320c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 321c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) /// AddPHIOperand - Add the specified value as an operand of the PHI for 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// the specified predecessor block. 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static void AddPHIOperand(MachineInstr *PHI, unsigned Val, 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *Pred) { 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PHI->addOperand(MachineOperand::CreateReg(Val, false)); 3268bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles) PHI->addOperand(MachineOperand::CreateMBB(Pred)); 3278bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles) } 3288bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles) 3298bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles) /// InstrIsPHI - Check if an instruction is a PHI. 3308bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles) /// 3318bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles) static MachineInstr *InstrIsPHI(MachineInstr *I) { 332e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch if (I && I->isPHI()) 333e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch return I; 3348bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles) return 0; 3358bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles) } 3368bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles) 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// ValueIsPHI - Check if the instruction that defines the specified register 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// is a PHI instruction. 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static MachineInstr *ValueIsPHI(unsigned Val, MachineSSAUpdater *Updater) { 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return InstrIsPHI(Updater->MRI->getVRegDef(Val)); 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 343 /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source 344 /// operands, i.e., it was just added. 345 static MachineInstr *ValueIsNewPHI(unsigned Val, MachineSSAUpdater *Updater) { 346 MachineInstr *PHI = ValueIsPHI(Val, Updater); 347 if (PHI && PHI->getNumOperands() <= 1) 348 return PHI; 349 return 0; 350 } 351 352 /// GetPHIValue - For the specified PHI instruction, return the register 353 /// that it defines. 354 static unsigned GetPHIValue(MachineInstr *PHI) { 355 return PHI->getOperand(0).getReg(); 356 } 357}; 358 359} // End llvm namespace 360 361/// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry 362/// for the specified BB and if so, return it. If not, construct SSA form by 363/// first calculating the required placement of PHIs and then inserting new 364/// PHIs where needed. 365unsigned MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB){ 366 AvailableValsTy &AvailableVals = getAvailableVals(AV); 367 if (unsigned V = AvailableVals[BB]) 368 return V; 369 370 SSAUpdaterImpl<MachineSSAUpdater> Impl(this, &AvailableVals, InsertedPHIs); 371 return Impl.GetValue(BB); 372} 373