1651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng//===-- MachineSSAUpdater.h - Unstructured SSA Update Tool ------*- C++ -*-===// 2651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng// 3651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng// The LLVM Compiler Infrastructure 4651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng// 5651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng// This file is distributed under the University of Illinois Open Source 6651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng// License. See LICENSE.TXT for details. 7651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng// 8651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng//===----------------------------------------------------------------------===// 9651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng// 10651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng// This file declares the MachineSSAUpdater class. 11651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng// 12651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng//===----------------------------------------------------------------------===// 13651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng 14651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng#ifndef LLVM_CODEGEN_MACHINESSAUPDATER_H 15651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng#define LLVM_CODEGEN_MACHINESSAUPDATER_H 16651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng 17001d3dc976d7cda8a3dd8c7fd4020b0b96033f4eCraig Topper#include "llvm/Support/Compiler.h" 18001d3dc976d7cda8a3dd8c7fd4020b0b96033f4eCraig Topper 19651ea5376c57c061ebe183375974e7333d2e0ec3Evan Chengnamespace llvm { 20651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng class MachineBasicBlock; 21229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng class MachineFunction; 22651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng class MachineInstr; 23229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng class MachineOperand; 24229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng class MachineRegisterInfo; 25229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng class TargetInstrInfo; 26229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng class TargetRegisterClass; 27651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng template<typename T> class SmallVectorImpl; 284aad88d1fd88413029dd05255306b07cb19396eeBob Wilson template<typename T> class SSAUpdaterTraits; 29211678a0d761942578970fc78a72c56d69ed36dbBob Wilson class BumpPtrAllocator; 30651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng 31229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng/// MachineSSAUpdater - This class updates SSA form for a set of virtual 32229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng/// registers defined in multiple blocks. This is used when code duplication 33229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng/// or another unstructured transformation wants to rewrite a set of uses of one 34229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng/// vreg with uses of a set of vregs. 35651ea5376c57c061ebe183375974e7333d2e0ec3Evan Chengclass MachineSSAUpdater { 364aad88d1fd88413029dd05255306b07cb19396eeBob Wilson friend class SSAUpdaterTraits<MachineSSAUpdater>; 37211678a0d761942578970fc78a72c56d69ed36dbBob Wilson 38211678a0d761942578970fc78a72c56d69ed36dbBob Wilsonprivate: 39651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// AvailableVals - This keeps track of which value to use on a per-block 40651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// basis. When we insert PHI nodes, we keep track of them here. 41651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng //typedef DenseMap<MachineBasicBlock*, unsigned > AvailableValsTy; 42651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng void *AV; 43651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng 44229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng /// VR - Current virtual register whose uses are being updated. 45229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng unsigned VR; 46229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng 47229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng /// VRC - Register class of the current virtual register. 48229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng const TargetRegisterClass *VRC; 49229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng 50651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// InsertedPHIs - If this is non-null, the MachineSSAUpdater adds all PHI 51651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// nodes that it creates to the vector. 52651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng SmallVectorImpl<MachineInstr*> *InsertedPHIs; 53229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng 54229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng const TargetInstrInfo *TII; 55229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng MachineRegisterInfo *MRI; 56651ea5376c57c061ebe183375974e7333d2e0ec3Evan Chengpublic: 57651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// MachineSSAUpdater constructor. If InsertedPHIs is specified, it will be 58651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// filled in with all PHI Nodes created by rewriting. 59229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng explicit MachineSSAUpdater(MachineFunction &MF, 60229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng SmallVectorImpl<MachineInstr*> *InsertedPHIs = 0); 61651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng ~MachineSSAUpdater(); 62651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng 63651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// Initialize - Reset this object to get ready for a new set of SSA 64651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// updates. 65229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng void Initialize(unsigned V); 66651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng 67651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// AddAvailableValue - Indicate that a rewritten value is available at the 68651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// end of the specified block with the specified value. 69651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng void AddAvailableValue(MachineBasicBlock *BB, unsigned V); 70651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng 71651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// HasValueForBlock - Return true if the MachineSSAUpdater already has a 72651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// value for the specified block. 73651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng bool HasValueForBlock(MachineBasicBlock *BB) const; 74651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng 75651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is 76651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// live at the end of the specified block. 77651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng unsigned GetValueAtEndOfBlock(MachineBasicBlock *BB); 78651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng 79651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that 80651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// is live in the middle of the specified block. 81651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// 82651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one 83651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// important case: if there is a definition of the rewritten value after the 84651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// 'use' in BB. Consider code like this: 85651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// 86651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// X1 = ... 87651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// SomeBB: 88651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// use(X) 89651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// X2 = ... 90651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// br Cond, SomeBB, OutBB 91651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// 92651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// In this case, there are two values (X1 and X2) added to the AvailableVals 93651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// set by the client of the rewriter, and those values are both live out of 94651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// their respective blocks. However, the use of X happens in the *middle* of 95651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// a block. Because of this, we need to insert a new PHI node in SomeBB to 96651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// merge the appropriate values, and this value isn't live out of the block. 97651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// 98651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng unsigned GetValueInMiddleOfBlock(MachineBasicBlock *BB); 99651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng 100651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, 101651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// which use their value in the corresponding predecessor. Note that this 102651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// will not work if the use is supposed to be rewritten to a value defined in 103651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// the same block as the use, but above it. Any 'AddAvailableValue's added 104651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng /// for the use's block will be considered to be below it. 105229694f0ee630ceabe96a8bd48952f6740f928b2Evan Cheng void RewriteUse(MachineOperand &U); 106651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng 107651ea5376c57c061ebe183375974e7333d2e0ec3Evan Chengprivate: 10875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng void ReplaceRegWith(unsigned OldReg, unsigned NewReg); 109651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng unsigned GetValueAtEndOfBlockInternal(MachineBasicBlock *BB); 110211678a0d761942578970fc78a72c56d69ed36dbBob Wilson 111001d3dc976d7cda8a3dd8c7fd4020b0b96033f4eCraig Topper void operator=(const MachineSSAUpdater&) LLVM_DELETED_FUNCTION; 112001d3dc976d7cda8a3dd8c7fd4020b0b96033f4eCraig Topper MachineSSAUpdater(const MachineSSAUpdater&) LLVM_DELETED_FUNCTION; 113651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng}; 114651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng 115651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng} // End llvm namespace 116651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng 117651ea5376c57c061ebe183375974e7333d2e0ec3Evan Cheng#endif 118