EarlyIfConversion.cpp revision 47730a774dd6392744ee62c7385665c780e1c4e1
133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen//===-- EarlyIfConversion.cpp - If-conversion on SSA form machine code ----===// 233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// 333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// The LLVM Compiler Infrastructure 433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// 533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// License. See LICENSE.TXT for details. 733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// 833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// 1033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// Early if-conversion is for out-of-order CPUs that don't have a lot of 1133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// predicable instructions. The goal is to eliminate conditional branches that 1233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// may mispredict. 1333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// 1433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// Instructions from both sides of the branch are executed specutatively, and a 1533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// cmov instruction selects the result. 1633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// 1733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 1933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen#define DEBUG_TYPE "early-ifcvt" 2033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen#include "llvm/Function.h" 2133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen#include "llvm/ADT/BitVector.h" 221f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen#include "llvm/ADT/PostOrderIterator.h" 2333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen#include "llvm/ADT/SetVector.h" 2433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen#include "llvm/ADT/SmallPtrSet.h" 2533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen#include "llvm/ADT/SparseSet.h" 2633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 271f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen#include "llvm/CodeGen/MachineDominators.h" 2833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen#include "llvm/CodeGen/MachineFunction.h" 2933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen#include "llvm/CodeGen/MachineFunctionPass.h" 3047730a774dd6392744ee62c7385665c780e1c4e1Jakob Stoklund Olesen#include "llvm/CodeGen/MachineLoopInfo.h" 3133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 3233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen#include "llvm/CodeGen/Passes.h" 3333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen#include "llvm/Target/TargetInstrInfo.h" 3433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen#include "llvm/Target/TargetRegisterInfo.h" 3533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen#include "llvm/Support/CommandLine.h" 3633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen#include "llvm/Support/Debug.h" 3733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 3833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 3933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesenusing namespace llvm; 4033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 4133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// Absolute maximum number of instructions allowed per speculated block. 4233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// This bypasses all other heuristics, so it should be set fairly high. 4333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesenstatic cl::opt<unsigned> 4433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund OlesenBlockInstrLimit("early-ifcvt-limit", cl::init(30), cl::Hidden, 4533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen cl::desc("Maximum number of instructions per speculated block.")); 4633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 4733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// Stress testing mode - disable heuristics. 4833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesenstatic cl::opt<bool> Stress("stress-early-ifcvt", cl::Hidden, 4933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen cl::desc("Turn all knobs to 11")); 5033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 5133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesentypedef SmallSetVector<MachineBasicBlock*, 8> BlockSetVector; 5233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 5333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 5433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// SSAIfConv 5533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 5633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// 5733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// The SSAIfConv class performs if-conversion on SSA form machine code after 5800f43076a3d9cc76ef4736cf3e7215e19b05f6d5Matt Beaumont-Gay// determining if it is possible. The class contains no heuristics; external 5933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// code should be used to determine when if-conversion is a good idea. 6033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// 6100f43076a3d9cc76ef4736cf3e7215e19b05f6d5Matt Beaumont-Gay// SSAIfConv can convert both triangles and diamonds: 6233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// 6333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// Triangle: Head Diamond: Head 6400f43076a3d9cc76ef4736cf3e7215e19b05f6d5Matt Beaumont-Gay// | \ / \_ 6500f43076a3d9cc76ef4736cf3e7215e19b05f6d5Matt Beaumont-Gay// | \ / | 6633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// | [TF]BB FBB TBB 6733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// | / \ / 6833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// | / \ / 6933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// Tail Tail 7033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// 7133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// Instructions in the conditional blocks TBB and/or FBB are spliced into the 7200f43076a3d9cc76ef4736cf3e7215e19b05f6d5Matt Beaumont-Gay// Head block, and phis in the Tail block are converted to select instructions. 7333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// 7433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesennamespace { 7533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesenclass SSAIfConv { 7633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen const TargetInstrInfo *TII; 7733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen const TargetRegisterInfo *TRI; 7833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MachineRegisterInfo *MRI; 7933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 801f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesenpublic: 8133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen /// The block containing the conditional branch. 8233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MachineBasicBlock *Head; 8333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 8433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen /// The block containing phis after the if-then-else. 8533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MachineBasicBlock *Tail; 8633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 8733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen /// The 'true' conditional block as determined by AnalyzeBranch. 8833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MachineBasicBlock *TBB; 8933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 9033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen /// The 'false' conditional block as determined by AnalyzeBranch. 9133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MachineBasicBlock *FBB; 9233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 9333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen /// isTriangle - When there is no 'else' block, either TBB or FBB will be 9433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen /// equal to Tail. 9533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen bool isTriangle() const { return TBB == Tail || FBB == Tail; } 9633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 9733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen /// Information about each phi in the Tail block. 9833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen struct PHIInfo { 9933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MachineInstr *PHI; 10033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen unsigned TReg, FReg; 10133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Latencies from Cond+Branch, TReg, and FReg to DstReg. 10233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen int CondCycles, TCycles, FCycles; 10333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 10433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen PHIInfo(MachineInstr *phi) 10533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen : PHI(phi), TReg(0), FReg(0), CondCycles(0), TCycles(0), FCycles(0) {} 10633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen }; 10733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 10833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen SmallVector<PHIInfo, 8> PHIs; 10933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 1101f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesenprivate: 1111f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen /// The branch condition determined by AnalyzeBranch. 1121f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen SmallVector<MachineOperand, 4> Cond; 1131f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen 11433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen /// Instructions in Head that define values used by the conditional blocks. 11533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen /// The hoisted instructions must be inserted after these instructions. 11633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen SmallPtrSet<MachineInstr*, 8> InsertAfter; 11733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 11833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen /// Register units clobbered by the conditional blocks. 11933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen BitVector ClobberedRegUnits; 12033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 12133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Scratch pad for findInsertionPoint. 12233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen SparseSet<unsigned> LiveRegUnits; 12333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 12433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen /// Insertion point in Head for speculatively executed instructions form TBB 12533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen /// and FBB. 12633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MachineBasicBlock::iterator InsertionPoint; 12733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 12833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen /// Return true if all non-terminator instructions in MBB can be safely 12933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen /// speculated. 13033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen bool canSpeculateInstrs(MachineBasicBlock *MBB); 13133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 13233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen /// Find a valid insertion point in Head. 13333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen bool findInsertionPoint(); 13433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 13533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesenpublic: 13633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen /// runOnMachineFunction - Initialize per-function data structures. 13733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen void runOnMachineFunction(MachineFunction &MF) { 13833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen TII = MF.getTarget().getInstrInfo(); 13933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen TRI = MF.getTarget().getRegisterInfo(); 14033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MRI = &MF.getRegInfo(); 14133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen LiveRegUnits.clear(); 14233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen LiveRegUnits.setUniverse(TRI->getNumRegUnits()); 14333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen ClobberedRegUnits.clear(); 14433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen ClobberedRegUnits.resize(TRI->getNumRegUnits()); 14533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 14633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 14733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen /// canConvertIf - If the sub-CFG headed by MBB can be if-converted, 14833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen /// initialize the internal state, and return true. 14933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen bool canConvertIf(MachineBasicBlock *MBB); 15033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 15133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen /// convertIf - If-convert the last block passed to canConvertIf(), assuming 1521f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen /// it is possible. Add any erased blocks to RemovedBlocks. 1531f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen void convertIf(SmallVectorImpl<MachineBasicBlock*> &RemovedBlocks); 15433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen}; 15533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen} // end anonymous namespace 15633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 15733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 15833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// canSpeculateInstrs - Returns true if all the instructions in MBB can safely 15933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// be speculated. The terminators are not considered. 16033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// 16133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// If instructions use any values that are defined in the head basic block, 16233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// the defining instructions are added to InsertAfter. 16333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// 16433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// Any clobbered regunits are added to ClobberedRegUnits. 16533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// 16633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesenbool SSAIfConv::canSpeculateInstrs(MachineBasicBlock *MBB) { 16733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to 16833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // get right. 16933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (!MBB->livein_empty()) { 17033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << MBB->getNumber() << " has live-ins.\n"); 17133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 17233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 17333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 17433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen unsigned InstrCount = 0; 17586fc3100b552c8d400160581c2a00f2fd7b83b45Jakob Stoklund Olesen 17686fc3100b552c8d400160581c2a00f2fd7b83b45Jakob Stoklund Olesen // Check all instructions, except the terminators. It is assumed that 17786fc3100b552c8d400160581c2a00f2fd7b83b45Jakob Stoklund Olesen // terminators never have side effects or define any used register values. 17833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen for (MachineBasicBlock::iterator I = MBB->begin(), 17933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen E = MBB->getFirstTerminator(); I != E; ++I) { 18033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (I->isDebugValue()) 18133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen continue; 18233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 18333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (++InstrCount > BlockInstrLimit && !Stress) { 18433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << MBB->getNumber() << " has more than " 18533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen << BlockInstrLimit << " instructions.\n"); 18633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 18733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 18833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 18933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // There shouldn't normally be any phis in a single-predecessor block. 19033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (I->isPHI()) { 19133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "Can't hoist: " << *I); 19233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 19333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 19433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 19533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Don't speculate loads. Note that it may be possible and desirable to 19633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // speculate GOT or constant pool loads that are guaranteed not to trap, 19733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // but we don't support that for now. 19833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (I->mayLoad()) { 19933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "Won't speculate load: " << *I); 20033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 20133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 20233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 20333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // We never speculate stores, so an AA pointer isn't necessary. 20433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen bool DontMoveAcrossStore = true; 20533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (!I->isSafeToMove(TII, 0, DontMoveAcrossStore)) { 20633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "Can't speculate: " << *I); 20733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 20833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 20933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 21033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Check for any dependencies on Head instructions. 21133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen for (MIOperands MO(I); MO.isValid(); ++MO) { 21233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (MO->isRegMask()) { 21333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "Won't speculate regmask: " << *I); 21433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 21533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 21633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (!MO->isReg()) 21733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen continue; 21833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen unsigned Reg = MO->getReg(); 21933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 22033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Remember clobbered regunits. 22133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (MO->isDef() && TargetRegisterInfo::isPhysicalRegister(Reg)) 22233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) 22333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen ClobberedRegUnits.set(*Units); 22433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 22533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (!MO->readsReg() || !TargetRegisterInfo::isVirtualRegister(Reg)) 22633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen continue; 22733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MachineInstr *DefMI = MRI->getVRegDef(Reg); 22833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (!DefMI || DefMI->getParent() != Head) 22933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen continue; 23033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (InsertAfter.insert(DefMI)) 23133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "BB#" << MBB->getNumber() << " depends on " << *DefMI); 23233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (DefMI->isTerminator()) { 23333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "Can't insert instructions below terminator.\n"); 23433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 23533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 23633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 23733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 23833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return true; 23933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen} 24033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 24133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 24233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// Find an insertion point in Head for the speculated instructions. The 24333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// insertion point must be: 24433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// 24533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// 1. Before any terminators. 24633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// 2. After any instructions in InsertAfter. 24733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// 3. Not have any clobbered regunits live. 24833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// 24933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// This function sets InsertionPoint and returns true when successful, it 25033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// returns false if no valid insertion point could be found. 25133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// 25233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesenbool SSAIfConv::findInsertionPoint() { 25333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Keep track of live regunits before the current position. 25433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Only track RegUnits that are also in ClobberedRegUnits. 25533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen LiveRegUnits.clear(); 25633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen SmallVector<unsigned, 8> Reads; 25733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); 25833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MachineBasicBlock::iterator I = Head->end(); 25933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MachineBasicBlock::iterator B = Head->begin(); 26033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen while (I != B) { 26133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen --I; 26233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Some of the conditional code depends in I. 26333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (InsertAfter.count(I)) { 26433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "Can't insert code after " << *I); 26533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 26633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 26733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 26833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Update live regunits. 26933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen for (MIOperands MO(I); MO.isValid(); ++MO) { 27033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // We're ignoring regmask operands. That is conservatively correct. 27133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (!MO->isReg()) 27233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen continue; 27333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen unsigned Reg = MO->getReg(); 27433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (!TargetRegisterInfo::isPhysicalRegister(Reg)) 27533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen continue; 27633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // I clobbers Reg, so it isn't live before I. 27733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (MO->isDef()) 27833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) 27933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen LiveRegUnits.erase(*Units); 28033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Unless I reads Reg. 28133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (MO->readsReg()) 28233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen Reads.push_back(Reg); 28333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 28433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Anything read by I is live before I. 28533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen while (!Reads.empty()) 28633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen for (MCRegUnitIterator Units(Reads.pop_back_val(), TRI); Units.isValid(); 28733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen ++Units) 28833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (ClobberedRegUnits.test(*Units)) 28933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen LiveRegUnits.insert(*Units); 29033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 29133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // We can't insert before a terminator. 29233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (I != FirstTerm && I->isTerminator()) 29333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen continue; 29433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 29533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Some of the clobbered registers are live before I, not a valid insertion 29633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // point. 29733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (!LiveRegUnits.empty()) { 29833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG({ 29933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen dbgs() << "Would clobber"; 30033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen for (SparseSet<unsigned>::const_iterator 30133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen i = LiveRegUnits.begin(), e = LiveRegUnits.end(); i != e; ++i) 30233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen dbgs() << ' ' << PrintRegUnit(*i, TRI); 30333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen dbgs() << " live before " << *I; 30433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen }); 30533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen continue; 30633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 30733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 30833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // This is a valid insertion point. 30933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen InsertionPoint = I; 31033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "Can insert before " << *I); 31133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return true; 31233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 31333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "No legal insertion point found.\n"); 31433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 31533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen} 31633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 31733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 31833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 31933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// canConvertIf - analyze the sub-cfg rooted in MBB, and return true if it is 32033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// a potential candidate for if-conversion. Fill out the internal state. 32133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// 32233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesenbool SSAIfConv::canConvertIf(MachineBasicBlock *MBB) { 32333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen Head = MBB; 32433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen TBB = FBB = Tail = 0; 32533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 32633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (Head->succ_size() != 2) 32733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 32833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MachineBasicBlock *Succ0 = Head->succ_begin()[0]; 32933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MachineBasicBlock *Succ1 = Head->succ_begin()[1]; 33033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 33133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Canonicalize so Succ0 has MBB as its single predecessor. 33233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (Succ0->pred_size() != 1) 33333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen std::swap(Succ0, Succ1); 33433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 33533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (Succ0->pred_size() != 1 || Succ0->succ_size() != 1) 33633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 33733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 33833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // We could support additional Tail predecessors by updating phis instead of 33933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // eliminating them. Let's see an example where it matters first. 34033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen Tail = Succ0->succ_begin()[0]; 34133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (Tail->pred_size() != 2) 34233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 34333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 34433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // This is not a triangle. 34533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (Tail != Succ1) { 34633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Check for a diamond. We won't deal with any critical edges. 34733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (Succ1->pred_size() != 1 || Succ1->succ_size() != 1 || 34833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen Succ1->succ_begin()[0] != Tail) 34933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 35033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "\nDiamond: BB#" << Head->getNumber() 35133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen << " -> BB#" << Succ0->getNumber() 35233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen << "/BB#" << Succ1->getNumber() 35333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen << " -> BB#" << Tail->getNumber() << '\n'); 35433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 35533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Live-in physregs are tricky to get right when speculating code. 35633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (!Tail->livein_empty()) { 35733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "Tail has live-ins.\n"); 35833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 35933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 36033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } else { 36133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "\nTriangle: BB#" << Head->getNumber() 36233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen << " -> BB#" << Succ0->getNumber() 36333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen << " -> BB#" << Tail->getNumber() << '\n'); 36433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 36533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 36633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // This is a triangle or a diamond. 36733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // If Tail doesn't have any phis, there must be side effects. 36833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (Tail->empty() || !Tail->front().isPHI()) { 36933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "No phis in tail.\n"); 37033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 37133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 37233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 37333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // The branch we're looking to eliminate must be analyzable. 37433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen Cond.clear(); 37533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (TII->AnalyzeBranch(*Head, TBB, FBB, Cond)) { 37633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "Branch not analyzable.\n"); 37733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 37833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 37933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 38033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // This is weird, probably some sort of degenerate CFG. 38133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (!TBB) { 38233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "AnalyzeBranch didn't find conditional branch.\n"); 38333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 38433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 38533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 38633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // AnalyzeBranch doesn't set FBB on a fall-through branch. 38733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Make sure it is always set. 38833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen FBB = TBB == Succ0 ? Succ1 : Succ0; 38933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 39033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Any phis in the tail block must be convertible to selects. 39133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen PHIs.clear(); 39233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MachineBasicBlock *TPred = TBB == Tail ? Head : TBB; 39333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MachineBasicBlock *FPred = FBB == Tail ? Head : FBB; 39433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen for (MachineBasicBlock::iterator I = Tail->begin(), E = Tail->end(); 39533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen I != E && I->isPHI(); ++I) { 39633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen PHIs.push_back(&*I); 39733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen PHIInfo &PI = PHIs.back(); 39833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Find PHI operands corresponding to TPred and FPred. 39933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen for (unsigned i = 1; i != PI.PHI->getNumOperands(); i += 2) { 40033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (PI.PHI->getOperand(i+1).getMBB() == TPred) 40133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen PI.TReg = PI.PHI->getOperand(i).getReg(); 40233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (PI.PHI->getOperand(i+1).getMBB() == FPred) 40333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen PI.FReg = PI.PHI->getOperand(i).getReg(); 40433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 40533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(PI.TReg) && "Bad PHI"); 40633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(PI.FReg) && "Bad PHI"); 40733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 40833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Get target information. 40933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (!TII->canInsertSelect(*Head, Cond, PI.TReg, PI.FReg, 41033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen PI.CondCycles, PI.TCycles, PI.FCycles)) { 41133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "Can't convert: " << *PI.PHI); 41233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 41333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 41433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 41533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 41633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Check that the conditional instructions can be speculated. 41733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen InsertAfter.clear(); 41833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen ClobberedRegUnits.reset(); 41933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (TBB != Tail && !canSpeculateInstrs(TBB)) 42033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 42133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (FBB != Tail && !canSpeculateInstrs(FBB)) 42233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 42333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 42433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Try to find a valid insertion point for the speculated instructions in the 42533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // head basic block. 42633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (!findInsertionPoint()) 42733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return false; 42833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 42933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return true; 43033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen} 43133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 43233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 43333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// convertIf - Execute the if conversion after canConvertIf has determined the 43433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// feasibility. 43533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// 4361f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen/// Any basic blocks erased will be added to RemovedBlocks. 43733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// 4381f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesenvoid SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock*> &RemovedBlocks) { 43933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen assert(Head && Tail && TBB && FBB && "Call canConvertIf first."); 44033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 44133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Move all instructions into Head, except for the terminators. 44233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (TBB != Tail) 44333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen Head->splice(InsertionPoint, TBB, TBB->begin(), TBB->getFirstTerminator()); 44433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (FBB != Tail) 44533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen Head->splice(InsertionPoint, FBB, FBB->begin(), FBB->getFirstTerminator()); 44633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 44733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); 44833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen assert(FirstTerm != Head->end() && "No terminators"); 44933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DebugLoc HeadDL = FirstTerm->getDebugLoc(); 45033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 45133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Convert all PHIs to select instructions inserted before FirstTerm. 45233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen for (unsigned i = 0, e = PHIs.size(); i != e; ++i) { 45333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen PHIInfo &PI = PHIs[i]; 45433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "If-converting " << *PI.PHI); 45533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen assert(PI.PHI->getNumOperands() == 5 && "Unexpected PHI operands."); 45633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen unsigned DstReg = PI.PHI->getOperand(0).getReg(); 45733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, PI.FReg); 45833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << " --> " << *llvm::prior(FirstTerm)); 45933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen PI.PHI->eraseFromParent(); 46033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen PI.PHI = 0; 46133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 46233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 46333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Fix up the CFG, temporarily leave Head without any successors. 46433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen Head->removeSuccessor(TBB); 46533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen Head->removeSuccessor(FBB); 46633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (TBB != Tail) 46733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen TBB->removeSuccessor(Tail); 46833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (FBB != Tail) 46933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen FBB->removeSuccessor(Tail); 47033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 47133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Fix up Head's terminators. 47233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // It should become a single branch or a fallthrough. 47333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen TII->RemoveBranch(*Head); 47433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 47533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Erase the now empty conditional blocks. It is likely that Head can fall 47633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // through to Tail, and we can join the two blocks. 4771f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen if (TBB != Tail) { 4781f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen RemovedBlocks.push_back(TBB); 4791f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen TBB->eraseFromParent(); 4801f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen } 4811f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen if (FBB != Tail) { 4821f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen RemovedBlocks.push_back(FBB); 4831f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen FBB->eraseFromParent(); 4841f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen } 48533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 48633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen assert(Head->succ_empty() && "Additional head successors?"); 48733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen if (Head->isLayoutSuccessor(Tail)) { 48833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // Splice Tail onto the end of Head. 48933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "Joining tail BB#" << Tail->getNumber() 49033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen << " into head BB#" << Head->getNumber() << '\n'); 49133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen Head->splice(Head->end(), Tail, 49233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen Tail->begin(), Tail->end()); 49333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen Head->transferSuccessorsAndUpdatePHIs(Tail); 4941f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen RemovedBlocks.push_back(Tail); 4951f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen Tail->eraseFromParent(); 49633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } else { 49733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen // We need a branch to Tail, let code placement work it out later. 49833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "Converting to unconditional branch.\n"); 49933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen SmallVector<MachineOperand, 0> EmptyCond; 50033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen TII->InsertBranch(*Head, Tail, 0, EmptyCond, HeadDL); 50133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen Head->addSuccessor(Tail); 50233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen } 50333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << *Head); 50433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen} 50533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 50633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 50733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 50833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen// EarlyIfConverter Pass 50933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 51033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 51133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesennamespace { 51233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesenclass EarlyIfConverter : public MachineFunctionPass { 51333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen const TargetInstrInfo *TII; 51433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen const TargetRegisterInfo *TRI; 51533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MachineRegisterInfo *MRI; 5161f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen MachineDominatorTree *DomTree; 51747730a774dd6392744ee62c7385665c780e1c4e1Jakob Stoklund Olesen MachineLoopInfo *Loops; 51833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen SSAIfConv IfConv; 51933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 52033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesenpublic: 52133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen static char ID; 52233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen EarlyIfConverter() : MachineFunctionPass(ID) {} 52333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen void getAnalysisUsage(AnalysisUsage &AU) const; 52433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen bool runOnMachineFunction(MachineFunction &MF); 52533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 52633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesenprivate: 52733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen bool tryConvertIf(MachineBasicBlock*); 5281f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen void updateDomTree(ArrayRef<MachineBasicBlock*> Removed); 52947730a774dd6392744ee62c7385665c780e1c4e1Jakob Stoklund Olesen void updateLoops(ArrayRef<MachineBasicBlock*> Removed); 53033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen}; 53133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen} // end anonymous namespace 53233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 53333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesenchar EarlyIfConverter::ID = 0; 53433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesenchar &llvm::EarlyIfConverterID = EarlyIfConverter::ID; 53533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 53633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund OlesenINITIALIZE_PASS_BEGIN(EarlyIfConverter, 53733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen "early-ifcvt", "Early If Converter", false, false) 53833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund OlesenINITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 5391f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund OlesenINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 54033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund OlesenINITIALIZE_PASS_END(EarlyIfConverter, 54133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen "early-ifcvt", "Early If Converter", false, false) 54233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 54333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesenvoid EarlyIfConverter::getAnalysisUsage(AnalysisUsage &AU) const { 54433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen AU.addRequired<MachineBranchProbabilityInfo>(); 5451f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen AU.addRequired<MachineDominatorTree>(); 5461f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen AU.addPreserved<MachineDominatorTree>(); 54747730a774dd6392744ee62c7385665c780e1c4e1Jakob Stoklund Olesen AU.addRequired<MachineLoopInfo>(); 54847730a774dd6392744ee62c7385665c780e1c4e1Jakob Stoklund Olesen AU.addPreserved<MachineLoopInfo>(); 54933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 55033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen} 55133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 5521f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen/// Update the dominator tree after if-conversion erased some blocks. 5531f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesenvoid EarlyIfConverter::updateDomTree(ArrayRef<MachineBasicBlock*> Removed) { 5541f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen // convertIf can remove TBB, FBB, and Tail can be merged into Head. 5551f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen // TBB and FBB should not dominate any blocks. 5561f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen // Tail children should be transferred to Head. 5571f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen MachineDomTreeNode *HeadNode = DomTree->getNode(IfConv.Head); 5581f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen for (unsigned i = 0, e = Removed.size(); i != e; ++i) { 5591f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen MachineDomTreeNode *Node = DomTree->getNode(Removed[i]); 5601f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen assert(Node != HeadNode && "Cannot erase the head node"); 5611f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen while (Node->getNumChildren()) { 5621f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen assert(Node->getBlock() == IfConv.Tail && "Unexpected children"); 5631f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen DomTree->changeImmediateDominator(Node->getChildren().back(), HeadNode); 5641f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen } 5651f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen DomTree->eraseNode(Removed[i]); 5661f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen } 5671f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen} 5681f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen 56947730a774dd6392744ee62c7385665c780e1c4e1Jakob Stoklund Olesen/// Update LoopInfo after if-conversion. 57047730a774dd6392744ee62c7385665c780e1c4e1Jakob Stoklund Olesenvoid EarlyIfConverter::updateLoops(ArrayRef<MachineBasicBlock*> Removed) { 57147730a774dd6392744ee62c7385665c780e1c4e1Jakob Stoklund Olesen if (!Loops) 57247730a774dd6392744ee62c7385665c780e1c4e1Jakob Stoklund Olesen return; 57347730a774dd6392744ee62c7385665c780e1c4e1Jakob Stoklund Olesen // If-conversion doesn't change loop structure, and it doesn't mess with back 57447730a774dd6392744ee62c7385665c780e1c4e1Jakob Stoklund Olesen // edges, so updating LoopInfo is simply removing the dead blocks. 57547730a774dd6392744ee62c7385665c780e1c4e1Jakob Stoklund Olesen for (unsigned i = 0, e = Removed.size(); i != e; ++i) 57647730a774dd6392744ee62c7385665c780e1c4e1Jakob Stoklund Olesen Loops->removeBlock(Removed[i]); 57747730a774dd6392744ee62c7385665c780e1c4e1Jakob Stoklund Olesen} 57847730a774dd6392744ee62c7385665c780e1c4e1Jakob Stoklund Olesen 57933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// Attempt repeated if-conversion on MBB, return true if successful. 58033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen/// 58133242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesenbool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) { 5821f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen bool Changed = false; 5831f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen while (IfConv.canConvertIf(MBB)) { 5841f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen // If-convert MBB and update analyses. 5851f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen SmallVector<MachineBasicBlock*, 4> RemovedBlocks; 5861f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen IfConv.convertIf(RemovedBlocks); 5871f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen Changed = true; 5881f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen updateDomTree(RemovedBlocks); 58947730a774dd6392744ee62c7385665c780e1c4e1Jakob Stoklund Olesen updateLoops(RemovedBlocks); 5901f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen } 5911f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen return Changed; 59233242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen} 59333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 59433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesenbool EarlyIfConverter::runOnMachineFunction(MachineFunction &MF) { 59533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n" 59633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen << "********** Function: " 59733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen << ((Value*)MF.getFunction())->getName() << '\n'); 59833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen TII = MF.getTarget().getInstrInfo(); 59933242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen TRI = MF.getTarget().getRegisterInfo(); 60033242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MRI = &MF.getRegInfo(); 6011f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen DomTree = &getAnalysis<MachineDominatorTree>(); 60247730a774dd6392744ee62c7385665c780e1c4e1Jakob Stoklund Olesen Loops = getAnalysisIfAvailable<MachineLoopInfo>(); 60333242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 60433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen bool Changed = false; 60533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen IfConv.runOnMachineFunction(MF); 60633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 6071f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen // Visit blocks in dominator tree post-order. The post-order enables nested 6081f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen // if-conversion in a single pass. The tryConvertIf() function may erase 6091f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen // blocks, but only blocks dominated by the head block. This makes it safe to 6101f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen // update the dominator tree while the post-order iterator is still active. 6111f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen for (po_iterator<MachineDominatorTree*> 6121f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen I = po_begin(DomTree), E = po_end(DomTree); I != E; ++I) 6131f523dc45e29874bf8101e50b42ba707ffc8aff9Jakob Stoklund Olesen if (tryConvertIf(I->getBlock())) 61433242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen Changed = true; 61533242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen 61633242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen MF.verify(this, "After early if-conversion"); 61733242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen return Changed; 61833242fd3ed5586091e73254b58dd1825e9d53c60Jakob Stoklund Olesen} 619