1c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem//===-- StackColoring.cpp -------------------------------------------------===// 2c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// 3c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// The LLVM Compiler Infrastructure 4c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// 5c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// This file is distributed under the University of Illinois Open Source 6c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// License. See LICENSE.TXT for details. 7c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// 8c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem//===----------------------------------------------------------------------===// 9c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// 10c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// This pass implements the stack-coloring optimization that looks for 11c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// lifetime markers machine instructions (LIFESTART_BEGIN and LIFESTART_END), 12c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// which represent the possible lifetime of stack slots. It attempts to 13c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// merge disjoint stack slots and reduce the used stack space. 14c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// NOTE: This pass is not StackSlotColoring, which optimizes spill slots. 15c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// 16c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// TODO: In the future we plan to improve stack coloring in the following ways: 17c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// 1. Allow merging multiple small slots into a single larger slot at different 18c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// offsets. 19c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// 2. Merge this pass with StackSlotColoring and allow merging of allocas with 20c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// spill slots. 21c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// 22c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem//===----------------------------------------------------------------------===// 23c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 24c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#define DEBUG_TYPE "stackcoloring" 25d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/Passes.h" 26c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/BitVector.h" 27c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/DepthFirstIterator.h" 28c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/PostOrderIterator.h" 29c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/SetVector.h" 30c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/SmallPtrSet.h" 31c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/SparseSet.h" 32c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/Statistic.h" 33d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/Dominators.h" 34d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/ValueTracking.h" 35c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/LiveInterval.h" 36d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineBasicBlock.h" 37c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 38c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/MachineDominators.h" 39d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineFrameInfo.h" 40c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/MachineFunctionPass.h" 41d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineLoopInfo.h" 42d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineMemOperand.h" 43c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/MachineModuleInfo.h" 44c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/MachineRegisterInfo.h" 45c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/SlotIndexes.h" 46c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/DebugInfo.h" 470b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 480b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 490b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 50c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/MC/MCInstrItineraries.h" 51c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/Support/CommandLine.h" 52c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/Support/Debug.h" 53c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/Support/raw_ostream.h" 54d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetInstrInfo.h" 55d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetRegisterInfo.h" 56c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 57c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemusing namespace llvm; 58c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 59c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemstatic cl::opt<bool> 60c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemDisableColoring("no-stack-coloring", 61d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem cl::init(false), cl::Hidden, 62d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem cl::desc("Disable stack coloring")); 63c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 6418e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem/// The user may write code that uses allocas outside of the declared lifetime 6518e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem/// zone. This can happen when the user returns a reference to a local 6618e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem/// data-structure. We can detect these cases and decide not to optimize the 6718e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem/// code. If this flag is enabled, we try to save the user. 68d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotemstatic cl::opt<bool> 6918e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav RotemProtectFromEscapedAllocas("protect-from-escaped-allocas", 70a26cadc58d32a739ccf99423922bfc542c1026b1Nadav Rotem cl::init(false), cl::Hidden, 7118e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem cl::desc("Do not optimize lifetime zones that are broken")); 72d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem 73d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav RotemSTATISTIC(NumMarkerSeen, "Number of lifetime markers found."); 74c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemSTATISTIC(StackSpaceSaved, "Number of bytes saved due to merging slots."); 75c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemSTATISTIC(StackSlotMerged, "Number of stack slot merged."); 76d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav RotemSTATISTIC(EscapedAllocas, 77d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem "Number of allocas that escaped the lifetime region"); 78d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem 79c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem//===----------------------------------------------------------------------===// 80c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// StackColoring Pass 81c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem//===----------------------------------------------------------------------===// 82c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 83c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemnamespace { 84c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem/// StackColoring - A machine pass for merging disjoint stack allocations, 85c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem/// marked by the LIFETIME_START and LIFETIME_END pseudo instructions. 86c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemclass StackColoring : public MachineFunctionPass { 87c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineFrameInfo *MFI; 88c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineFunction *MF; 89c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 90c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// A class representing liveness information for a single basic block. 91c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Each bit in the BitVector represents the liveness property 92c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// for a different stack slot. 93c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem struct BlockLifetimeInfo { 94c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Which slots BEGINs in each basic block. 95c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BitVector Begin; 96c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Which slots ENDs in each basic block. 97c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BitVector End; 98c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Which slots are marked as LIVE_IN, coming into each basic block. 99c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BitVector LiveIn; 100c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Which slots are marked as LIVE_OUT, coming out of each basic block. 101c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BitVector LiveOut; 102c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem }; 103c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 104c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Maps active slots (per bit) for each basic block. 10504fbcb59432c085bb284501dcea9693f435a417bCraig Topper typedef DenseMap<const MachineBasicBlock*, BlockLifetimeInfo> LivenessMap; 10604fbcb59432c085bb284501dcea9693f435a417bCraig Topper LivenessMap BlockLiveness; 107c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 108c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Maps serial numbers to basic blocks. 10904fbcb59432c085bb284501dcea9693f435a417bCraig Topper DenseMap<const MachineBasicBlock*, int> BasicBlocks; 110c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Maps basic blocks to a serial number. 11104fbcb59432c085bb284501dcea9693f435a417bCraig Topper SmallVector<const MachineBasicBlock*, 8> BasicBlockNumbering; 112c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 113c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Maps liveness intervals for each slot. 114c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SmallVector<LiveInterval*, 16> Intervals; 115c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// VNInfo is used for the construction of LiveIntervals. 116c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem VNInfo::Allocator VNInfoAllocator; 117c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// SlotIndex analysis object. 118d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem SlotIndexes *Indexes; 119c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 120c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// The list of lifetime markers found. These markers are to be removed 121c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// once the coloring is done. 122c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SmallVector<MachineInstr*, 8> Markers; 123c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 124c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// SlotSizeSorter - A Sort utility for arranging stack slots according 125c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// to their size. 126c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem struct SlotSizeSorter { 127c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineFrameInfo *MFI; 128c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SlotSizeSorter(MachineFrameInfo *mfi) : MFI(mfi) { } 129c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem bool operator()(int LHS, int RHS) { 130c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // We use -1 to denote a uninteresting slot. Place these slots at the end. 131c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (LHS == -1) return false; 132c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (RHS == -1) return true; 133c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Sort according to size. 134c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return MFI->getObjectSize(LHS) > MFI->getObjectSize(RHS); 135c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 136c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem}; 137c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 138c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotempublic: 139c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem static char ID; 140c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem StackColoring() : MachineFunctionPass(ID) { 141c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem initializeStackColoringPass(*PassRegistry::getPassRegistry()); 142c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 143c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem void getAnalysisUsage(AnalysisUsage &AU) const; 144c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem bool runOnMachineFunction(MachineFunction &MF); 145c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 146c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemprivate: 147c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Debug. 148cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper void dump() const; 149c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 150c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Removes all of the lifetime marker instructions from the function. 151c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// \returns true if any markers were removed. 152c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem bool removeAllMarkers(); 153c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 154c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Scan the machine function and find all of the lifetime markers. 155c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Record the findings in the BEGIN and END vectors. 156c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// \returns the number of markers found. 157c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned collectMarkers(unsigned NumSlot); 158c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 159c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Perform the dataflow calculation and calculate the lifetime for each of 160c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// the slots, based on the BEGIN/END vectors. Set the LifetimeLIVE_IN and 161c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// LifetimeLIVE_OUT maps that represent which stack slots are live coming 162c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// in and out blocks. 163c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem void calculateLocalLiveness(); 164c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 165c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Construct the LiveIntervals for the slots. 166c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem void calculateLiveIntervals(unsigned NumSlots); 167c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 168c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Go over the machine function and change instructions which use stack 169c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// slots to use the joint slots. 170c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem void remapInstructions(DenseMap<int, int> &SlotRemap); 171c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 1720a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem /// The input program may contain intructions which are not inside lifetime 1730a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem /// markers. This can happen due to a bug in the compiler or due to a bug in 1740a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem /// user code (for example, returning a reference to a local variable). 1750a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem /// This procedure checks all of the instructions in the function and 1760a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem /// invalidates lifetime ranges which do not contain all of the instructions 1770a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem /// which access that frame slot. 1780a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem void removeInvalidSlotRanges(); 1790a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 180c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Map entries which point to other entries to their destination. 181c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// A->B->C becomes A->C. 182c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem void expungeSlotMap(DenseMap<int, int> &SlotRemap, unsigned NumSlots); 183c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem}; 184c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} // end anonymous namespace 185c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 186c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemchar StackColoring::ID = 0; 187c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemchar &llvm::StackColoringID = StackColoring::ID; 188c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 189c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemINITIALIZE_PASS_BEGIN(StackColoring, 190c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem "stack-coloring", "Merge disjoint stack slots", false, false) 191c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 192c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 193c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemINITIALIZE_PASS_END(StackColoring, 194c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem "stack-coloring", "Merge disjoint stack slots", false, false) 195c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 196c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemvoid StackColoring::getAnalysisUsage(AnalysisUsage &AU) const { 197c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem AU.addRequired<MachineDominatorTree>(); 198c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem AU.addPreserved<MachineDominatorTree>(); 199c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem AU.addRequired<SlotIndexes>(); 200c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineFunctionPass::getAnalysisUsage(AU); 201c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 202c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 203cbc6d797054a2bf2a641031f270d38804a6f2295Craig Toppervoid StackColoring::dump() const { 204c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (df_iterator<MachineFunction*> FI = df_begin(MF), FE = df_end(MF); 205c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem FI != FE; ++FI) { 206cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper DEBUG(dbgs()<<"Inspecting block #"<<BasicBlocks.lookup(*FI)<< 207f1af1feeee0f0ec797410762c006211f9c1e2a0fEdwin Vane " ["<<FI->getName()<<"]\n"); 208cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper 20904fbcb59432c085bb284501dcea9693f435a417bCraig Topper LivenessMap::const_iterator BI = BlockLiveness.find(*FI); 210cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper assert(BI != BlockLiveness.end() && "Block not found"); 211cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper const BlockLifetimeInfo &BlockInfo = BI->second; 212cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper 213c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"BEGIN : {"); 214cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper for (unsigned i=0; i < BlockInfo.Begin.size(); ++i) 215cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper DEBUG(dbgs()<<BlockInfo.Begin.test(i)<<" "); 216c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"}\n"); 217c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 218c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"END : {"); 219cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper for (unsigned i=0; i < BlockInfo.End.size(); ++i) 220cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper DEBUG(dbgs()<<BlockInfo.End.test(i)<<" "); 221c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 222c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"}\n"); 223c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 224c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"LIVE_IN: {"); 225cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper for (unsigned i=0; i < BlockInfo.LiveIn.size(); ++i) 226cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper DEBUG(dbgs()<<BlockInfo.LiveIn.test(i)<<" "); 227c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 228c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"}\n"); 229c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"LIVEOUT: {"); 230cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper for (unsigned i=0; i < BlockInfo.LiveOut.size(); ++i) 231cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper DEBUG(dbgs()<<BlockInfo.LiveOut.test(i)<<" "); 232c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"}\n"); 233c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 234c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 235c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 236c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemunsigned StackColoring::collectMarkers(unsigned NumSlot) { 237c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned MarkersFound = 0; 238c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Scan the function to find all lifetime markers. 239c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // NOTE: We use the a reverse-post-order iteration to ensure that we obtain a 240c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // deterministic numbering, and because we'll need a post-order iteration 241c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // later for solving the liveness dataflow problem. 242c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (df_iterator<MachineFunction*> FI = df_begin(MF), FE = df_end(MF); 243c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem FI != FE; ++FI) { 244c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 245c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Assign a serial number to this basic block. 2462de0572caec55e3779857cae0bbcd962af2e495dDmitri Gribenko BasicBlocks[*FI] = BasicBlockNumbering.size(); 247c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BasicBlockNumbering.push_back(*FI); 248c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 249252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper // Keep a reference to avoid repeated lookups. 250252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper BlockLifetimeInfo &BlockInfo = BlockLiveness[*FI]; 251252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper 252252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper BlockInfo.Begin.resize(NumSlot); 253252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper BlockInfo.End.resize(NumSlot); 254c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 255c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (MachineBasicBlock::iterator BI = (*FI)->begin(), BE = (*FI)->end(); 256c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BI != BE; ++BI) { 257c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 258c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (BI->getOpcode() != TargetOpcode::LIFETIME_START && 259c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BI->getOpcode() != TargetOpcode::LIFETIME_END) 260c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 261c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 262c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Markers.push_back(BI); 263c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 264c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem bool IsStart = BI->getOpcode() == TargetOpcode::LIFETIME_START; 265261abf5f4011e5b1e8949d7404190a4f4eaff8d8Craig Topper const MachineOperand &MI = BI->getOperand(0); 266c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned Slot = MI.getIndex(); 267c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 268c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MarkersFound++; 269c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 27083ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop const AllocaInst *Allocation = MFI->getObjectAllocation(Slot); 271c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (Allocation) { 2720cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem DEBUG(dbgs()<<"Found a lifetime marker for slot #"<<Slot<< 2730cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem " with allocation: "<< Allocation->getName()<<"\n"); 274c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 275c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 276c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (IsStart) { 277252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper BlockInfo.Begin.set(Slot); 278c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } else { 279252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper if (BlockInfo.Begin.test(Slot)) { 280c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Allocas that start and end within a single block are handled 281c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // specially when computing the LiveIntervals to avoid pessimizing 282c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // the liveness propagation. 283252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper BlockInfo.Begin.reset(Slot); 284c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } else { 285252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper BlockInfo.End.set(Slot); 286c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 287c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 288c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 289c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 290c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 291c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Update statistics. 292c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem NumMarkerSeen += MarkersFound; 293c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return MarkersFound; 294c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 295c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 296c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemvoid StackColoring::calculateLocalLiveness() { 297c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Perform a standard reverse dataflow computation to solve for 298c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // global liveness. The BEGIN set here is equivalent to KILL in the standard 299c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // formulation, and END is equivalent to GEN. The result of this computation 300c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // is a map from blocks to bitvectors where the bitvectors represent which 301c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // allocas are live in/out of that block. 30204fbcb59432c085bb284501dcea9693f435a417bCraig Topper SmallPtrSet<const MachineBasicBlock*, 8> BBSet(BasicBlockNumbering.begin(), 30304fbcb59432c085bb284501dcea9693f435a417bCraig Topper BasicBlockNumbering.end()); 304c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned NumSSMIters = 0; 305c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem bool changed = true; 306c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem while (changed) { 307c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem changed = false; 308c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem ++NumSSMIters; 309c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 31004fbcb59432c085bb284501dcea9693f435a417bCraig Topper SmallPtrSet<const MachineBasicBlock*, 8> NextBBSet; 311c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 31204fbcb59432c085bb284501dcea9693f435a417bCraig Topper for (SmallVector<const MachineBasicBlock*, 8>::iterator 313c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem PI = BasicBlockNumbering.begin(), PE = BasicBlockNumbering.end(); 314c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem PI != PE; ++PI) { 315c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 31604fbcb59432c085bb284501dcea9693f435a417bCraig Topper const MachineBasicBlock *BB = *PI; 317c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (!BBSet.count(BB)) continue; 318c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 319cede03886712e18b697f9ec91311d4a8df60c734Craig Topper // Use an iterator to avoid repeated lookups. 32004fbcb59432c085bb284501dcea9693f435a417bCraig Topper LivenessMap::iterator BI = BlockLiveness.find(BB); 321cede03886712e18b697f9ec91311d4a8df60c734Craig Topper assert(BI != BlockLiveness.end() && "Block not found"); 322cede03886712e18b697f9ec91311d4a8df60c734Craig Topper BlockLifetimeInfo &BlockInfo = BI->second; 323cede03886712e18b697f9ec91311d4a8df60c734Craig Topper 324c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BitVector LocalLiveIn; 325c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BitVector LocalLiveOut; 326c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 327c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Forward propagation from begins to ends. 328cede03886712e18b697f9ec91311d4a8df60c734Craig Topper for (MachineBasicBlock::const_pred_iterator PI = BB->pred_begin(), 329cede03886712e18b697f9ec91311d4a8df60c734Craig Topper PE = BB->pred_end(); PI != PE; ++PI) { 33004fbcb59432c085bb284501dcea9693f435a417bCraig Topper LivenessMap::const_iterator I = BlockLiveness.find(*PI); 331cede03886712e18b697f9ec91311d4a8df60c734Craig Topper assert(I != BlockLiveness.end() && "Predecessor not found"); 332cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveIn |= I->second.LiveOut; 333cede03886712e18b697f9ec91311d4a8df60c734Craig Topper } 334cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveIn |= BlockInfo.End; 335cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveIn.reset(BlockInfo.Begin); 336c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 337c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Reverse propagation from ends to begins. 338cede03886712e18b697f9ec91311d4a8df60c734Craig Topper for (MachineBasicBlock::const_succ_iterator SI = BB->succ_begin(), 339cede03886712e18b697f9ec91311d4a8df60c734Craig Topper SE = BB->succ_end(); SI != SE; ++SI) { 34004fbcb59432c085bb284501dcea9693f435a417bCraig Topper LivenessMap::const_iterator I = BlockLiveness.find(*SI); 341cede03886712e18b697f9ec91311d4a8df60c734Craig Topper assert(I != BlockLiveness.end() && "Successor not found"); 342cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveOut |= I->second.LiveIn; 343cede03886712e18b697f9ec91311d4a8df60c734Craig Topper } 344cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveOut |= BlockInfo.Begin; 345cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveOut.reset(BlockInfo.End); 346c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 347c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem LocalLiveIn |= LocalLiveOut; 348c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem LocalLiveOut |= LocalLiveIn; 349c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 350c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // After adopting the live bits, we need to turn-off the bits which 351c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // are de-activated in this block. 352cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveOut.reset(BlockInfo.End); 353cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveIn.reset(BlockInfo.Begin); 354c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 3556165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // If we have both BEGIN and END markers in the same basic block then 3566165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // we know that the BEGIN marker comes after the END, because we already 3576165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // handle the case where the BEGIN comes before the END when collecting 3586165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // the markers (and building the BEGIN/END vectore). 3596165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // Want to enable the LIVE_IN and LIVE_OUT of slots that have both 3606165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // BEGIN and END because it means that the value lives before and after 3616165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // this basic block. 362cede03886712e18b697f9ec91311d4a8df60c734Craig Topper BitVector LocalEndBegin = BlockInfo.End; 363cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalEndBegin &= BlockInfo.Begin; 3646165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem LocalLiveIn |= LocalEndBegin; 3656165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem LocalLiveOut |= LocalEndBegin; 3666165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem 367cede03886712e18b697f9ec91311d4a8df60c734Craig Topper if (LocalLiveIn.test(BlockInfo.LiveIn)) { 368c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem changed = true; 369cede03886712e18b697f9ec91311d4a8df60c734Craig Topper BlockInfo.LiveIn |= LocalLiveIn; 370c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 37104fbcb59432c085bb284501dcea9693f435a417bCraig Topper for (MachineBasicBlock::const_pred_iterator PI = BB->pred_begin(), 372c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem PE = BB->pred_end(); PI != PE; ++PI) 373c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem NextBBSet.insert(*PI); 374c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 375c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 376cede03886712e18b697f9ec91311d4a8df60c734Craig Topper if (LocalLiveOut.test(BlockInfo.LiveOut)) { 377c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem changed = true; 378cede03886712e18b697f9ec91311d4a8df60c734Craig Topper BlockInfo.LiveOut |= LocalLiveOut; 379c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 38004fbcb59432c085bb284501dcea9693f435a417bCraig Topper for (MachineBasicBlock::const_succ_iterator SI = BB->succ_begin(), 381c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SE = BB->succ_end(); SI != SE; ++SI) 382c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem NextBBSet.insert(*SI); 383c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 384c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 385c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 386c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BBSet = NextBBSet; 387c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem }// while changed. 388c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 389c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 390c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemvoid StackColoring::calculateLiveIntervals(unsigned NumSlots) { 391c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SmallVector<SlotIndex, 16> Starts; 392c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SmallVector<SlotIndex, 16> Finishes; 393c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 394c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // For each block, find which slots are active within this block 395c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // and update the live intervals. 396c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (MachineFunction::iterator MBB = MF->begin(), MBBe = MF->end(); 397c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MBB != MBBe; ++MBB) { 398c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Starts.clear(); 399c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Starts.resize(NumSlots); 400c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Finishes.clear(); 401c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Finishes.resize(NumSlots); 402c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 403e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem // Create the interval for the basic blocks with lifetime markers in them. 404261abf5f4011e5b1e8949d7404190a4f4eaff8d8Craig Topper for (SmallVectorImpl<MachineInstr*>::const_iterator it = Markers.begin(), 405c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem e = Markers.end(); it != e; ++it) { 406261abf5f4011e5b1e8949d7404190a4f4eaff8d8Craig Topper const MachineInstr *MI = *it; 407e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem if (MI->getParent() != MBB) 408e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem continue; 409e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem 410c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem assert((MI->getOpcode() == TargetOpcode::LIFETIME_START || 411c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MI->getOpcode() == TargetOpcode::LIFETIME_END) && 412c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem "Invalid Lifetime marker"); 413c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 414e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem bool IsStart = MI->getOpcode() == TargetOpcode::LIFETIME_START; 415261abf5f4011e5b1e8949d7404190a4f4eaff8d8Craig Topper const MachineOperand &Mo = MI->getOperand(0); 416e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem int Slot = Mo.getIndex(); 417e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem assert(Slot >= 0 && "Invalid slot"); 418e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem 419e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem SlotIndex ThisIndex = Indexes->getInstructionIndex(MI); 420e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem 421e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem if (IsStart) { 422e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem if (!Starts[Slot].isValid() || Starts[Slot] > ThisIndex) 423e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem Starts[Slot] = ThisIndex; 424e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem } else { 425e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem if (!Finishes[Slot].isValid() || Finishes[Slot] < ThisIndex) 426e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem Finishes[Slot] = ThisIndex; 427e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem } 428e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem } 429e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem 430e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem // Create the interval of the blocks that we previously found to be 'alive'. 431e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem BitVector Alive = BlockLiveness[MBB].LiveIn; 432e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem Alive |= BlockLiveness[MBB].LiveOut; 433e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem 434e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem if (Alive.any()) { 435e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem for (int pos = Alive.find_first(); pos != -1; 436e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem pos = Alive.find_next(pos)) { 437e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem if (!Starts[pos].isValid()) 438e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem Starts[pos] = Indexes->getMBBStartIdx(MBB); 439e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem if (!Finishes[pos].isValid()) 440e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem Finishes[pos] = Indexes->getMBBEndIdx(MBB); 441c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 442c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 443c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 444c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned i = 0; i < NumSlots; ++i) { 445e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem assert(Starts[i].isValid() == Finishes[i].isValid() && "Unmatched range"); 446e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem if (!Starts[i].isValid()) 447c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 448c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 449c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem assert(Starts[i] && Finishes[i] && "Invalid interval"); 450c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem VNInfo *ValNum = Intervals[i]->getValNumInfo(0); 451c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SlotIndex S = Starts[i]; 452c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SlotIndex F = Finishes[i]; 453c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (S < F) { 454c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // We have a single consecutive region. 455c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Intervals[i]->addRange(LiveRange(S, F, ValNum)); 456c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } else { 457c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // We have two non consecutive regions. This happens when 458c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // LIFETIME_START appears after the LIFETIME_END marker. 459c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SlotIndex NewStart = Indexes->getMBBStartIdx(MBB); 460c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SlotIndex NewFin = Indexes->getMBBEndIdx(MBB); 461c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Intervals[i]->addRange(LiveRange(NewStart, F, ValNum)); 462c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Intervals[i]->addRange(LiveRange(S, NewFin, ValNum)); 463c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 464c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 465c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 466c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 467c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 468c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotembool StackColoring::removeAllMarkers() { 469c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned Count = 0; 470c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned i = 0; i < Markers.size(); ++i) { 471c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Markers[i]->eraseFromParent(); 472c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Count++; 473c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 474c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Markers.clear(); 475c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 476c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Removed "<<Count<<" markers.\n"); 477c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return Count; 478c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 479c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 480c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemvoid StackColoring::remapInstructions(DenseMap<int, int> &SlotRemap) { 481c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned FixedInstr = 0; 482c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned FixedMemOp = 0; 483c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned FixedDbg = 0; 484c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineModuleInfo *MMI = &MF->getMMI(); 485c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 486c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Remap debug information that refers to stack slots. 487c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineModuleInfo::VariableDbgInfoMapTy &VMap = MMI->getVariableDbgInfo(); 488c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (MachineModuleInfo::VariableDbgInfoMapTy::iterator VI = VMap.begin(), 489c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem VE = VMap.end(); VI != VE; ++VI) { 490c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem const MDNode *Var = VI->first; 491c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (!Var) continue; 492c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem std::pair<unsigned, DebugLoc> &VP = VI->second; 493c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (SlotRemap.count(VP.first)) { 494c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Remapping debug info for ["<<Var->getName()<<"].\n"); 495c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem VP.first = SlotRemap[VP.first]; 496c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem FixedDbg++; 497c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 498c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 499c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 500c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Keep a list of *allocas* which need to be remapped. 50183ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop DenseMap<const AllocaInst*, const AllocaInst*> Allocas; 502261abf5f4011e5b1e8949d7404190a4f4eaff8d8Craig Topper for (DenseMap<int, int>::const_iterator it = SlotRemap.begin(), 503c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem e = SlotRemap.end(); it != e; ++it) { 50483ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop const AllocaInst *From = MFI->getObjectAllocation(it->first); 50583ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop const AllocaInst *To = MFI->getObjectAllocation(it->second); 506c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem assert(To && From && "Invalid allocation object"); 507c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Allocas[From] = To; 508c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 509c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 510c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Remap all instructions to the new stack slots. 511c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineFunction::iterator BB, BBE; 512c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineBasicBlock::iterator I, IE; 513c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (BB = MF->begin(), BBE = MF->end(); BB != BBE; ++BB) 514c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (I = BB->begin(), IE = BB->end(); I != IE; ++I) { 515c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 5160aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem // Skip lifetime markers. We'll remove them soon. 5170aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem if (I->getOpcode() == TargetOpcode::LIFETIME_START || 5180aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem I->getOpcode() == TargetOpcode::LIFETIME_END) 5190aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem continue; 5200aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem 521c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Update the MachineMemOperand to use the new alloca. 522c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (MachineInstr::mmo_iterator MM = I->memoperands_begin(), 523c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem E = I->memoperands_end(); MM != E; ++MM) { 524c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineMemOperand *MMO = *MM; 525c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 526c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem const Value *V = MMO->getValue(); 527c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 528c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (!V) 529c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 530c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 531c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Climb up and find the original alloca. 532c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem V = GetUnderlyingObject(V); 533c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // If we did not find one, or if the one that we found is not in our 534c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // map, then move on. 53583ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop if (!V || !isa<AllocaInst>(V)) { 53683ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop // Clear mem operand since we don't know for sure that it doesn't 53783ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop // alias a merged alloca. 53883ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop MMO->setValue(0); 53983ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop continue; 54083ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop } 54183ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop const AllocaInst *AI= cast<AllocaInst>(V); 54283ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop if (!Allocas.count(AI)) 543c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 544c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 54583ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop MMO->setValue(Allocas[AI]); 546c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem FixedMemOp++; 547c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 548c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 549c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Update all of the machine instruction operands. 550c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned i = 0 ; i < I->getNumOperands(); ++i) { 551c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineOperand &MO = I->getOperand(i); 552c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 553c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (!MO.isFI()) 554c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 555c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem int FromSlot = MO.getIndex(); 556c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 557c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Don't touch arguments. 558c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (FromSlot<0) 559c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 560c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 561c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Only look at mapped slots. 562c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (!SlotRemap.count(FromSlot)) 563c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 564c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 5658cc14949053ea4fcba34afc68b30137eff408d66Nadav Rotem // In a debug build, check that the instruction that we are modifying is 5668cc14949053ea4fcba34afc68b30137eff408d66Nadav Rotem // inside the expected live range. If the instruction is not inside 5670aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem // the calculated range then it means that the alloca usage moved 56818e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem // outside of the lifetime markers, or that the user has a bug. 5690cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // NOTE: Alloca address calculations which happen outside the lifetime 5700cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // zone are are okay, despite the fact that we don't have a good way 5710cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // for validating all of the usages of the calculation. 5720aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem#ifndef NDEBUG 5730cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem bool TouchesMemory = I->mayLoad() || I->mayStore(); 57418e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem // If we *don't* protect the user from escaped allocas, don't bother 57518e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem // validating the instructions. 57618e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem if (!I->isDebugValue() && TouchesMemory && ProtectFromEscapedAllocas) { 5778754bbbe672450689a5bdc8a198af90144e56f31Nadav Rotem SlotIndex Index = Indexes->getInstructionIndex(I); 578d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem LiveInterval *Interval = Intervals[FromSlot]; 5798754bbbe672450689a5bdc8a198af90144e56f31Nadav Rotem assert(Interval->find(Index) != Interval->end() && 5800aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem "Found instruction usage outside of live range."); 5818754bbbe672450689a5bdc8a198af90144e56f31Nadav Rotem } 5820aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem#endif 5830aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem 584c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Fix the machine instructions. 585c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem int ToSlot = SlotRemap[FromSlot]; 586c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MO.setIndex(ToSlot); 587c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem FixedInstr++; 588c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 589c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 590c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 591c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Fixed "<<FixedMemOp<<" machine memory operands.\n"); 592c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Fixed "<<FixedDbg<<" debug locations.\n"); 593c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Fixed "<<FixedInstr<<" machine instructions.\n"); 594c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 595c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 5960a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotemvoid StackColoring::removeInvalidSlotRanges() { 597261abf5f4011e5b1e8949d7404190a4f4eaff8d8Craig Topper MachineFunction::const_iterator BB, BBE; 598261abf5f4011e5b1e8949d7404190a4f4eaff8d8Craig Topper MachineBasicBlock::const_iterator I, IE; 5990a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem for (BB = MF->begin(), BBE = MF->end(); BB != BBE; ++BB) 6000a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem for (I = BB->begin(), IE = BB->end(); I != IE; ++I) { 6010a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 6020a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem if (I->getOpcode() == TargetOpcode::LIFETIME_START || 6030a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem I->getOpcode() == TargetOpcode::LIFETIME_END || I->isDebugValue()) 6040a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem continue; 6050a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 6060cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // Some intervals are suspicious! In some cases we find address 6070cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // calculations outside of the lifetime zone, but not actual memory 6080cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // read or write. Memory accesses outside of the lifetime zone are a clear 6090cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // violation, but address calculations are okay. This can happen when 6100cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // GEPs are hoisted outside of the lifetime zone. 611faf31d01db913b477b749c9f11f18a9471c0a672Nadav Rotem // So, in here we only check instructions which can read or write memory. 6120cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem if (!I->mayLoad() && !I->mayStore()) 6130cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem continue; 6140cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem 6150a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem // Check all of the machine operands. 6160a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem for (unsigned i = 0 ; i < I->getNumOperands(); ++i) { 617261abf5f4011e5b1e8949d7404190a4f4eaff8d8Craig Topper const MachineOperand &MO = I->getOperand(i); 6180a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 6190a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem if (!MO.isFI()) 6200a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem continue; 6210a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 6220a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem int Slot = MO.getIndex(); 6230a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 6240a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem if (Slot<0) 6250a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem continue; 6260a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 6270a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem if (Intervals[Slot]->empty()) 6280a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem continue; 6290a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 6300a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem // Check that the used slot is inside the calculated lifetime range. 6310a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem // If it is not, warn about it and invalidate the range. 6320a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem LiveInterval *Interval = Intervals[Slot]; 6330a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem SlotIndex Index = Indexes->getInstructionIndex(I); 6340a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem if (Interval->find(Index) == Interval->end()) { 6350a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem Intervals[Slot]->clear(); 6360a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem DEBUG(dbgs()<<"Invalidating range #"<<Slot<<"\n"); 637d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem EscapedAllocas++; 6380a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem } 6390a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem } 6400a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem } 6410a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem} 6420a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 643c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemvoid StackColoring::expungeSlotMap(DenseMap<int, int> &SlotRemap, 644c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned NumSlots) { 645c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Expunge slot remap map. 646c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned i=0; i < NumSlots; ++i) { 647c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // If we are remapping i 648c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (SlotRemap.count(i)) { 649c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem int Target = SlotRemap[i]; 650c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // As long as our target is mapped to something else, follow it. 651c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem while (SlotRemap.count(Target)) { 652c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Target = SlotRemap[Target]; 653c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SlotRemap[i] = Target; 654c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 655c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 656c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 657c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 658c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 659c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotembool StackColoring::runOnMachineFunction(MachineFunction &Func) { 660c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs() << "********** Stack Coloring **********\n" 661c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem << "********** Function: " 6625177b3a8c48adec2acf284fcb8e00775a705a7e2Roman Divacky << ((const Value*)Func.getFunction())->getName() << '\n'); 663c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MF = &Func; 664c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MFI = MF->getFrameInfo(); 665c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Indexes = &getAnalysis<SlotIndexes>(); 666c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BlockLiveness.clear(); 667c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BasicBlocks.clear(); 668c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BasicBlockNumbering.clear(); 669c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Markers.clear(); 670c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Intervals.clear(); 671c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem VNInfoAllocator.Reset(); 672c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 673c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned NumSlots = MFI->getObjectIndexEnd(); 674c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 675c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // If there are no stack slots then there are no markers to remove. 676c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (!NumSlots) 677c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return false; 678c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 679c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SmallVector<int, 8> SortedSlots; 680c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 681c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SortedSlots.reserve(NumSlots); 682c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Intervals.reserve(NumSlots); 683c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 684c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned NumMarkers = collectMarkers(NumSlots); 685c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 686c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned TotalSize = 0; 687c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Found "<<NumMarkers<<" markers and "<<NumSlots<<" slots\n"); 688c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Slot structure:\n"); 689c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 690c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (int i=0; i < MFI->getObjectIndexEnd(); ++i) { 691c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Slot #"<<i<<" - "<<MFI->getObjectSize(i)<<" bytes.\n"); 692c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem TotalSize += MFI->getObjectSize(i); 693c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 694c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 695c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Total Stack size: "<<TotalSize<<" bytes\n\n"); 696c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 697c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Don't continue because there are not enough lifetime markers, or the 6980cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // stack is too small, or we are told not to optimize the slots. 699c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (NumMarkers < 2 || TotalSize < 16 || DisableColoring) { 700c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Will not try to merge slots.\n"); 701c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return removeAllMarkers(); 702c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 703c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 704c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned i=0; i < NumSlots; ++i) { 705c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem LiveInterval *LI = new LiveInterval(i, 0); 706c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Intervals.push_back(LI); 707c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem LI->getNextValue(Indexes->getZeroIndex(), VNInfoAllocator); 708c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SortedSlots.push_back(i); 709c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 710c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 711c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Calculate the liveness of each block. 712c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem calculateLocalLiveness(); 713c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 714c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Propagate the liveness information. 715c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem calculateLiveIntervals(NumSlots); 716c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 717d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem // Search for allocas which are used outside of the declared lifetime 718d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem // markers. 71918e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem if (ProtectFromEscapedAllocas) 720d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem removeInvalidSlotRanges(); 7210a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 722c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Maps old slots to new slots. 723c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DenseMap<int, int> SlotRemap; 724c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned RemovedSlots = 0; 725c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned ReducedSize = 0; 726c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 727c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Do not bother looking at empty intervals. 728c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned I = 0; I < NumSlots; ++I) { 729c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (Intervals[SortedSlots[I]]->empty()) 730c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SortedSlots[I] = -1; 731c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 732c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 733c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // This is a simple greedy algorithm for merging allocas. First, sort the 734c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // slots, placing the largest slots first. Next, perform an n^2 scan and look 735c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // for disjoint slots. When you find disjoint slots, merge the samller one 736c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // into the bigger one and update the live interval. Remove the small alloca 737c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // and continue. 738c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 739c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Sort the slots according to their size. Place unused slots at the end. 740f38aa4272c2fcebae4ad10b21ea29874d0edef80Ulrich Weigand // Use stable sort to guarantee deterministic code generation. 741f38aa4272c2fcebae4ad10b21ea29874d0edef80Ulrich Weigand std::stable_sort(SortedSlots.begin(), SortedSlots.end(), 742f38aa4272c2fcebae4ad10b21ea29874d0edef80Ulrich Weigand SlotSizeSorter(MFI)); 743c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 744c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem bool Chanded = true; 745c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem while (Chanded) { 746c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Chanded = false; 747c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned I = 0; I < NumSlots; ++I) { 748c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (SortedSlots[I] == -1) 749c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 750c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 751a7de8a61dfae69885203137f3c712ab3d0cd75a4Nadav Rotem for (unsigned J=I+1; J < NumSlots; ++J) { 752c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (SortedSlots[J] == -1) 753c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 754c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 755c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem int FirstSlot = SortedSlots[I]; 756c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem int SecondSlot = SortedSlots[J]; 757c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem LiveInterval *First = Intervals[FirstSlot]; 758c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem LiveInterval *Second = Intervals[SecondSlot]; 759c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem assert (!First->empty() && !Second->empty() && "Found an empty range"); 760c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 761c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Merge disjoint slots. 762c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (!First->overlaps(*Second)) { 763c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Chanded = true; 764c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem First->MergeRangesInAsValue(*Second, First->getValNumInfo(0)); 765c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SlotRemap[SecondSlot] = FirstSlot; 766c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SortedSlots[J] = -1; 7679438d1e3514ab8801e9c488d9723241af7f4dc91Nadav Rotem DEBUG(dbgs()<<"Merging #"<<FirstSlot<<" and slots #"<< 7689438d1e3514ab8801e9c488d9723241af7f4dc91Nadav Rotem SecondSlot<<" together.\n"); 769c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned MaxAlignment = std::max(MFI->getObjectAlignment(FirstSlot), 770c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MFI->getObjectAlignment(SecondSlot)); 771c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 772c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem assert(MFI->getObjectSize(FirstSlot) >= 773c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MFI->getObjectSize(SecondSlot) && 774c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem "Merging a small object into a larger one"); 775c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 776c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem RemovedSlots+=1; 777c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem ReducedSize += MFI->getObjectSize(SecondSlot); 778c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MFI->setObjectAlignment(FirstSlot, MaxAlignment); 779c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MFI->RemoveStackObject(SecondSlot); 780c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 781c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 782c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 783c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem }// While changed. 784c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 785c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Record statistics. 786c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem StackSpaceSaved += ReducedSize; 787c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem StackSlotMerged += RemovedSlots; 788c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Merge "<<RemovedSlots<<" slots. Saved "<< 789c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem ReducedSize<<" bytes\n"); 790c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 791c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Scan the entire function and update all machine operands that use frame 792c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // indices to use the remapped frame index. 793c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem expungeSlotMap(SlotRemap, NumSlots); 794c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem remapInstructions(SlotRemap); 795c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 796c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Release the intervals. 797c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned I = 0; I < NumSlots; ++I) { 798c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem delete Intervals[I]; 799c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 800c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 801c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return removeAllMarkers(); 802c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 803