1f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar//===--- HexagonGenInsert.cpp ---------------------------------------------===// 2f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar// 3f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar// The LLVM Compiler Infrastructure 4f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar// 5f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar// This file is distributed under the University of Illinois Open Source 6f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar// License. See LICENSE.TXT for details. 7f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar// 8f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar//===----------------------------------------------------------------------===// 9f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 10f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#define DEBUG_TYPE "hexinsert" 11f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 12f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/ADT/BitVector.h" 13f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/ADT/DenseMap.h" 14f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/ADT/PostOrderIterator.h" 15f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/CodeGen/MachineDominators.h" 16f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/CodeGen/MachineFunction.h" 17f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/CodeGen/MachineFunctionPass.h" 18f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/CodeGen/MachineInstrBuilder.h" 19f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/CodeGen/MachineRegisterInfo.h" 20f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/IR/Constants.h" 21de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/Pass.h" 22de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/PassRegistry.h" 23f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/Support/CommandLine.h" 24f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/Support/Debug.h" 25f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/Support/Timer.h" 26de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/Support/raw_ostream.h" 27f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/Target/TargetMachine.h" 28f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/Target/TargetRegisterInfo.h" 29f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 30f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "Hexagon.h" 31f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "HexagonRegisterInfo.h" 32f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "HexagonTargetMachine.h" 33f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "HexagonBitTracker.h" 34f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 35f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include <vector> 36f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 37f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarusing namespace llvm; 38f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 39f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarstatic cl::opt<unsigned> VRegIndexCutoff("insert-vreg-cutoff", cl::init(~0U), 40f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar cl::Hidden, cl::ZeroOrMore, cl::desc("Vreg# cutoff for insert generation.")); 41f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar// The distance cutoff is selected based on the precheckin-perf results: 42f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar// cutoffs 20, 25, 35, and 40 are worse than 30. 43f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarstatic cl::opt<unsigned> VRegDistCutoff("insert-dist-cutoff", cl::init(30U), 44f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar cl::Hidden, cl::ZeroOrMore, cl::desc("Vreg distance cutoff for insert " 45f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar "generation.")); 46f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 47f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarstatic cl::opt<bool> OptTiming("insert-timing", cl::init(false), cl::Hidden, 48f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar cl::ZeroOrMore, cl::desc("Enable timing of insert generation")); 49f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarstatic cl::opt<bool> OptTimingDetail("insert-timing-detail", cl::init(false), 50f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar cl::Hidden, cl::ZeroOrMore, cl::desc("Enable detailed timing of insert " 51f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar "generation")); 52f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 53f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarstatic cl::opt<bool> OptSelectAll0("insert-all0", cl::init(false), cl::Hidden, 54f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar cl::ZeroOrMore); 55f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarstatic cl::opt<bool> OptSelectHas0("insert-has0", cl::init(false), cl::Hidden, 56f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar cl::ZeroOrMore); 57f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar// Whether to construct constant values via "insert". Could eliminate constant 58f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar// extenders, but often not practical. 59f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarstatic cl::opt<bool> OptConst("insert-const", cl::init(false), cl::Hidden, 60f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar cl::ZeroOrMore); 61f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 62f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarnamespace { 63f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // The preprocessor gets confused when the DEBUG macro is passed larger 64f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // chunks of code. Use this function to detect debugging. 65f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar inline bool isDebug() { 66f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#ifndef NDEBUG 67f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return ::llvm::DebugFlag && ::llvm::isCurrentDebugType(DEBUG_TYPE); 68f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#else 69f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 70f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#endif 71f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 72f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 73f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 74f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 75f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarnamespace { 76f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Set of virtual registers, based on BitVector. 77f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar struct RegisterSet : private BitVector { 78f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterSet() = default; 79f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar explicit RegisterSet(unsigned s, bool t = false) : BitVector(s, t) {} 80f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 81f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar using BitVector::clear; 82f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 83f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned find_first() const { 84f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar int First = BitVector::find_first(); 85f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (First < 0) 86f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return 0; 87f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return x2v(First); 88f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 89f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 90f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned find_next(unsigned Prev) const { 91f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar int Next = BitVector::find_next(v2x(Prev)); 92f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (Next < 0) 93f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return 0; 94f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return x2v(Next); 95f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 96f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 97f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterSet &insert(unsigned R) { 98f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned Idx = v2x(R); 99f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar ensure(Idx); 100f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return static_cast<RegisterSet&>(BitVector::set(Idx)); 101f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 102f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterSet &remove(unsigned R) { 103f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned Idx = v2x(R); 104f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (Idx >= size()) 105f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return *this; 106f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return static_cast<RegisterSet&>(BitVector::reset(Idx)); 107f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 108f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 109f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterSet &insert(const RegisterSet &Rs) { 110f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return static_cast<RegisterSet&>(BitVector::operator|=(Rs)); 111f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 112f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterSet &remove(const RegisterSet &Rs) { 113f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return static_cast<RegisterSet&>(BitVector::reset(Rs)); 114f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 115f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 116f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar reference operator[](unsigned R) { 117f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned Idx = v2x(R); 118f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar ensure(Idx); 119f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return BitVector::operator[](Idx); 120f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 121f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool operator[](unsigned R) const { 122f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned Idx = v2x(R); 123f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar assert(Idx < size()); 124f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return BitVector::operator[](Idx); 125f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 126f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool has(unsigned R) const { 127f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned Idx = v2x(R); 128f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (Idx >= size()) 129f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 130f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return BitVector::test(Idx); 131f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 132f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 133f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool empty() const { 134f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return !BitVector::any(); 135f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 136f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool includes(const RegisterSet &Rs) const { 137f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // A.BitVector::test(B) <=> A-B != {} 138f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return !Rs.BitVector::test(*this); 139f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 140f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool intersects(const RegisterSet &Rs) const { 141f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return BitVector::anyCommon(Rs); 142f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 143f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 144f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar private: 145f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void ensure(unsigned Idx) { 146f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (size() <= Idx) 147f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar resize(std::max(Idx+1, 32U)); 148f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 149f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar static inline unsigned v2x(unsigned v) { 150f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return TargetRegisterInfo::virtReg2Index(v); 151f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 152f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar static inline unsigned x2v(unsigned x) { 153f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return TargetRegisterInfo::index2VirtReg(x); 154f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 155f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar }; 156f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 157f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 158f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar struct PrintRegSet { 159f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PrintRegSet(const RegisterSet &S, const TargetRegisterInfo *RI) 160f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar : RS(S), TRI(RI) {} 161f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar friend raw_ostream &operator<< (raw_ostream &OS, 162f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const PrintRegSet &P); 163f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar private: 164f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const RegisterSet &RS; 165f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const TargetRegisterInfo *TRI; 166f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar }; 167f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 168f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar raw_ostream &operator<< (raw_ostream &OS, const PrintRegSet &P) { 169f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar OS << '{'; 170f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned R = P.RS.find_first(); R; R = P.RS.find_next(R)) 171f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar OS << ' ' << PrintReg(R, P.TRI); 172f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar OS << " }"; 173f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return OS; 174f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 175f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 176f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 177f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 178f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarnamespace { 179f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // A convenience class to associate unsigned numbers (such as virtual 180f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // registers) with unsigned numbers. 181f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar struct UnsignedMap : public DenseMap<unsigned,unsigned> { 182f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar UnsignedMap() : BaseType() {} 183f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar private: 184f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef DenseMap<unsigned,unsigned> BaseType; 185f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar }; 186f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 187f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // A utility to establish an ordering between virtual registers: 188f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // VRegA < VRegB <=> RegisterOrdering[VRegA] < RegisterOrdering[VRegB] 189f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // This is meant as a cache for the ordering of virtual registers defined 190f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // by a potentially expensive comparison function, or obtained by a proce- 191f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // dure that should not be repeated each time two registers are compared. 192f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar struct RegisterOrdering : public UnsignedMap { 193f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterOrdering() : UnsignedMap() {} 194f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned operator[](unsigned VR) const { 195f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const_iterator F = find(VR); 196f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar assert(F != end()); 197f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return F->second; 198f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 199f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Add operator(), so that objects of this class can be used as 200f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // comparators in std::sort et al. 201f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool operator() (unsigned VR1, unsigned VR2) const { 202f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return operator[](VR1) < operator[](VR2); 203f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 204f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar }; 205f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 206f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 207f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 208f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarnamespace { 209f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Ordering of bit values. This class does not have operator[], but 210f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // is supplies a comparison operator() for use in std:: algorithms. 211f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // The order is as follows: 212f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // - 0 < 1 < ref 213f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // - ref1 < ref2, if ord(ref1.Reg) < ord(ref2.Reg), 214f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // or ord(ref1.Reg) == ord(ref2.Reg), and ref1.Pos < ref2.Pos. 215f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar struct BitValueOrdering { 216f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar BitValueOrdering(const RegisterOrdering &RB) : BaseOrd(RB) {} 217f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool operator() (const BitTracker::BitValue &V1, 218f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitTracker::BitValue &V2) const; 219f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const RegisterOrdering &BaseOrd; 220f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar }; 221f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 222f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 223f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 224f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarbool BitValueOrdering::operator() (const BitTracker::BitValue &V1, 225f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitTracker::BitValue &V2) const { 226f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (V1 == V2) 227f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 228f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // V1==0 => true, V2==0 => false 229f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (V1.is(0) || V2.is(0)) 230f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return V1.is(0); 231f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Neither of V1,V2 is 0, and V1!=V2. 232f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // V2==1 => false, V1==1 => true 233f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (V2.is(1) || V1.is(1)) 234f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return !V2.is(1); 235f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Both V1,V2 are refs. 236f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned Ind1 = BaseOrd[V1.RefI.Reg], Ind2 = BaseOrd[V2.RefI.Reg]; 237f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (Ind1 != Ind2) 238f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return Ind1 < Ind2; 239f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // If V1.Pos==V2.Pos 240f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar assert(V1.RefI.Pos != V2.RefI.Pos && "Bit values should be different"); 241f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return V1.RefI.Pos < V2.RefI.Pos; 242f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 243f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 244f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 245f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarnamespace { 246f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Cache for the BitTracker's cell map. Map lookup has a logarithmic 247f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // complexity, this class will memoize the lookup results to reduce 248f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // the access time for repeated lookups of the same cell. 249f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar struct CellMapShadow { 250f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar CellMapShadow(const BitTracker &T) : BT(T) {} 251f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitTracker::RegisterCell &lookup(unsigned VR) { 252f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned RInd = TargetRegisterInfo::virtReg2Index(VR); 253f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Grow the vector to at least 32 elements. 254f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (RInd >= CVect.size()) 255f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar CVect.resize(std::max(RInd+16, 32U), 0); 256f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitTracker::RegisterCell *CP = CVect[RInd]; 257f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (CP == 0) 258f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar CP = CVect[RInd] = &BT.lookup(VR); 259f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return *CP; 260f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 261f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 262f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitTracker &BT; 263f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 264f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar private: 265f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef std::vector<const BitTracker::RegisterCell*> CellVectType; 266f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar CellVectType CVect; 267f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar }; 268f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 269f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 270f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 271f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarnamespace { 272f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Comparator class for lexicographic ordering of virtual registers 273f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // according to the corresponding BitTracker::RegisterCell objects. 274f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar struct RegisterCellLexCompare { 275f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterCellLexCompare(const BitValueOrdering &BO, CellMapShadow &M) 276f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar : BitOrd(BO), CM(M) {} 277f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool operator() (unsigned VR1, unsigned VR2) const; 278f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar private: 279f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitValueOrdering &BitOrd; 280f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar CellMapShadow &CM; 281f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar }; 282f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 283f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Comparator class for lexicographic ordering of virtual registers 284f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // according to the specified bits of the corresponding BitTracker:: 285f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // RegisterCell objects. 286f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Specifically, this class will be used to compare bit B of a register 287f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // cell for a selected virtual register R with bit N of any register 288f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // other than R. 289f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar struct RegisterCellBitCompareSel { 290f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterCellBitCompareSel(unsigned R, unsigned B, unsigned N, 291f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitValueOrdering &BO, CellMapShadow &M) 292f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar : SelR(R), SelB(B), BitN(N), BitOrd(BO), CM(M) {} 293f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool operator() (unsigned VR1, unsigned VR2) const; 294f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar private: 295f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const unsigned SelR, SelB; 296f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const unsigned BitN; 297f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitValueOrdering &BitOrd; 298f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar CellMapShadow &CM; 299f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar }; 300f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 301f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 302f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 303f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarbool RegisterCellLexCompare::operator() (unsigned VR1, unsigned VR2) const { 304f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Ordering of registers, made up from two given orderings: 305f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // - the ordering of the register numbers, and 306f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // - the ordering of register cells. 307f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Def. R1 < R2 if: 308f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // - cell(R1) < cell(R2), or 309f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // - cell(R1) == cell(R2), and index(R1) < index(R2). 310f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // 311f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // For register cells, the ordering is lexicographic, with index 0 being 312f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // the most significant. 313f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (VR1 == VR2) 314f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 315f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 316f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitTracker::RegisterCell &RC1 = CM.lookup(VR1), &RC2 = CM.lookup(VR2); 317f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar uint16_t W1 = RC1.width(), W2 = RC2.width(); 318f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (uint16_t i = 0, w = std::min(W1, W2); i < w; ++i) { 319f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitTracker::BitValue &V1 = RC1[i], &V2 = RC2[i]; 320f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (V1 != V2) 321f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return BitOrd(V1, V2); 322f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 323f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Cells are equal up until the common length. 324f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (W1 != W2) 325f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return W1 < W2; 326f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 327f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return BitOrd.BaseOrd[VR1] < BitOrd.BaseOrd[VR2]; 328f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 329f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 330f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 331f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarbool RegisterCellBitCompareSel::operator() (unsigned VR1, unsigned VR2) const { 332f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (VR1 == VR2) 333f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 334f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitTracker::RegisterCell &RC1 = CM.lookup(VR1); 335f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitTracker::RegisterCell &RC2 = CM.lookup(VR2); 336f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar uint16_t W1 = RC1.width(), W2 = RC2.width(); 337f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar uint16_t Bit1 = (VR1 == SelR) ? SelB : BitN; 338f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar uint16_t Bit2 = (VR2 == SelR) ? SelB : BitN; 339f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // If Bit1 exceeds the width of VR1, then: 340f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // - return false, if at the same time Bit2 exceeds VR2, or 341f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // - return true, otherwise. 342f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // (I.e. "a bit value that does not exist is less than any bit value 343f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // that does exist".) 344f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (W1 <= Bit1) 345f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return Bit2 < W2; 346f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // If Bit1 is within VR1, but Bit2 is not within VR2, return false. 347f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (W2 <= Bit2) 348f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 349f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 350f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitTracker::BitValue &V1 = RC1[Bit1], V2 = RC2[Bit2]; 351f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (V1 != V2) 352f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return BitOrd(V1, V2); 353f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 354f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 355f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 356f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 357f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarnamespace { 358f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar class OrderedRegisterList { 359f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef std::vector<unsigned> ListType; 360f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar public: 361f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar OrderedRegisterList(const RegisterOrdering &RO) : Ord(RO) {} 362f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void insert(unsigned VR); 363f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void remove(unsigned VR); 364f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned operator[](unsigned Idx) const { 365f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar assert(Idx < Seq.size()); 366f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return Seq[Idx]; 367f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 368f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned size() const { 369f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return Seq.size(); 370f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 371f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 372f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef ListType::iterator iterator; 373f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef ListType::const_iterator const_iterator; 374f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar iterator begin() { return Seq.begin(); } 375f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar iterator end() { return Seq.end(); } 376f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const_iterator begin() const { return Seq.begin(); } 377f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const_iterator end() const { return Seq.end(); } 378f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 379f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Convenience function to convert an iterator to the corresponding index. 380f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned idx(iterator It) const { return It-begin(); } 381f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar private: 382f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar ListType Seq; 383f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const RegisterOrdering &Ord; 384f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar }; 385f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 386f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 387f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar struct PrintORL { 388f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PrintORL(const OrderedRegisterList &L, const TargetRegisterInfo *RI) 389f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar : RL(L), TRI(RI) {} 390f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar friend raw_ostream &operator<< (raw_ostream &OS, const PrintORL &P); 391f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar private: 392f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const OrderedRegisterList &RL; 393f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const TargetRegisterInfo *TRI; 394f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar }; 395f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 396f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar raw_ostream &operator<< (raw_ostream &OS, const PrintORL &P) { 397f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar OS << '('; 398f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar OrderedRegisterList::const_iterator B = P.RL.begin(), E = P.RL.end(); 399f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (OrderedRegisterList::const_iterator I = B; I != E; ++I) { 400f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (I != B) 401f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar OS << ", "; 402f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar OS << PrintReg(*I, P.TRI); 403f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 404f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar OS << ')'; 405f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return OS; 406f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 407f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 408f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 409f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 410f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarvoid OrderedRegisterList::insert(unsigned VR) { 411f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar iterator L = std::lower_bound(Seq.begin(), Seq.end(), VR, Ord); 412f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (L == Seq.end()) 413f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Seq.push_back(VR); 414f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar else 415f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Seq.insert(L, VR); 416f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 417f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 418f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 419f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarvoid OrderedRegisterList::remove(unsigned VR) { 420f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar iterator L = std::lower_bound(Seq.begin(), Seq.end(), VR, Ord); 421f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar assert(L != Seq.end()); 422f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Seq.erase(L); 423f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 424f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 425f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 426f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarnamespace { 427f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // A record of the insert form. The fields correspond to the operands 428f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // of the "insert" instruction: 429f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // ... = insert(SrcR, InsR, #Wdh, #Off) 430f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar struct IFRecord { 431f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFRecord(unsigned SR = 0, unsigned IR = 0, uint16_t W = 0, uint16_t O = 0) 432f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar : SrcR(SR), InsR(IR), Wdh(W), Off(O) {} 433f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned SrcR, InsR; 434f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar uint16_t Wdh, Off; 435f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar }; 436f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 437f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar struct PrintIFR { 438f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PrintIFR(const IFRecord &R, const TargetRegisterInfo *RI) 439f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar : IFR(R), TRI(RI) {} 440f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar private: 441f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const IFRecord &IFR; 442f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const TargetRegisterInfo *TRI; 443f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar friend raw_ostream &operator<< (raw_ostream &OS, const PrintIFR &P); 444f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar }; 445f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 446f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar raw_ostream &operator<< (raw_ostream &OS, const PrintIFR &P) { 447f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned SrcR = P.IFR.SrcR, InsR = P.IFR.InsR; 448f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar OS << '(' << PrintReg(SrcR, P.TRI) << ',' << PrintReg(InsR, P.TRI) 449f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar << ",#" << P.IFR.Wdh << ",#" << P.IFR.Off << ')'; 450f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return OS; 451f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 452f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 453f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef std::pair<IFRecord,RegisterSet> IFRecordWithRegSet; 454f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 455f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 456f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 457f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarnamespace llvm { 458f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void initializeHexagonGenInsertPass(PassRegistry&); 459f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar FunctionPass *createHexagonGenInsert(); 460f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 461f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 462f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 463f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarnamespace { 464f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar class HexagonGenInsert : public MachineFunctionPass { 465f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar public: 466f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar static char ID; 467f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar HexagonGenInsert() : MachineFunctionPass(ID), HII(0), HRI(0) { 468f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar initializeHexagonGenInsertPass(*PassRegistry::getPassRegistry()); 469f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 470f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar virtual const char *getPassName() const { 471f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return "Hexagon generate \"insert\" instructions"; 472f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 473f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar virtual void getAnalysisUsage(AnalysisUsage &AU) const { 474f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AU.addRequired<MachineDominatorTree>(); 475f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AU.addPreserved<MachineDominatorTree>(); 476f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MachineFunctionPass::getAnalysisUsage(AU); 477f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 478f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar virtual bool runOnMachineFunction(MachineFunction &MF); 479f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 480f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar private: 481f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef DenseMap<std::pair<unsigned,unsigned>,unsigned> PairMapType; 482f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 483f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void buildOrderingMF(RegisterOrdering &RO) const; 484f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void buildOrderingBT(RegisterOrdering &RB, RegisterOrdering &RO) const; 485f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool isIntClass(const TargetRegisterClass *RC) const; 486f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool isConstant(unsigned VR) const; 487f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool isSmallConstant(unsigned VR) const; 488f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool isValidInsertForm(unsigned DstR, unsigned SrcR, unsigned InsR, 489f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar uint16_t L, uint16_t S) const; 490f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool findSelfReference(unsigned VR) const; 491f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool findNonSelfReference(unsigned VR) const; 492f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void getInstrDefs(const MachineInstr *MI, RegisterSet &Defs) const; 493f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void getInstrUses(const MachineInstr *MI, RegisterSet &Uses) const; 494f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned distance(const MachineBasicBlock *FromB, 495f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const MachineBasicBlock *ToB, const UnsignedMap &RPO, 496f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PairMapType &M) const; 497f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned distance(MachineBasicBlock::const_iterator FromI, 498f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MachineBasicBlock::const_iterator ToI, const UnsignedMap &RPO, 499f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PairMapType &M) const; 500f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool findRecordInsertForms(unsigned VR, OrderedRegisterList &AVs); 501f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void collectInBlock(MachineBasicBlock *B, OrderedRegisterList &AVs); 502f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void findRemovableRegisters(unsigned VR, IFRecord IF, 503f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterSet &RMs) const; 504f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void computeRemovableRegisters(); 505f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 506f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void pruneEmptyLists(); 507f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void pruneCoveredSets(unsigned VR); 508f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void pruneUsesTooFar(unsigned VR, const UnsignedMap &RPO, PairMapType &M); 509f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void pruneRegCopies(unsigned VR); 510f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void pruneCandidates(); 511f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void selectCandidates(); 512f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool generateInserts(); 513f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 514f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool removeDeadCode(MachineDomTreeNode *N); 515f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 516f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // IFRecord coupled with a set of potentially removable registers: 517f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef std::vector<IFRecordWithRegSet> IFListType; 518f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef DenseMap<unsigned,IFListType> IFMapType; // vreg -> IFListType 519f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 520f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void dump_map() const; 521f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 522f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const HexagonInstrInfo *HII; 523f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const HexagonRegisterInfo *HRI; 524f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 525f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MachineFunction *MFN; 526f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MachineRegisterInfo *MRI; 527f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MachineDominatorTree *MDT; 528f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar CellMapShadow *CMS; 529f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 530f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterOrdering BaseOrd; 531f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterOrdering CellOrd; 532f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFMapType IFMap; 533f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar }; 534f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 535f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar char HexagonGenInsert::ID = 0; 536f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 537f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 538f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 539f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarvoid HexagonGenInsert::dump_map() const { 540f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef IFMapType::const_iterator iterator; 541f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) { 542f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar dbgs() << " " << PrintReg(I->first, HRI) << ":\n"; 543f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const IFListType &LL = I->second; 544f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned i = 0, n = LL.size(); i < n; ++i) 545f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar dbgs() << " " << PrintIFR(LL[i].first, HRI) << ", " 546f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar << PrintRegSet(LL[i].second, HRI) << '\n'; 547f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 548f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 549f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 550f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 551f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarvoid HexagonGenInsert::buildOrderingMF(RegisterOrdering &RO) const { 552f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned Index = 0; 553f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef MachineFunction::const_iterator mf_iterator; 554f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (mf_iterator A = MFN->begin(), Z = MFN->end(); A != Z; ++A) { 555f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const MachineBasicBlock &B = *A; 556f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!CMS->BT.reached(&B)) 557f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 558f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef MachineBasicBlock::const_iterator mb_iterator; 559f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (mb_iterator I = B.begin(), E = B.end(); I != E; ++I) { 560f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const MachineInstr *MI = &*I; 561f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) { 562f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const MachineOperand &MO = MI->getOperand(i); 563f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (MO.isReg() && MO.isDef()) { 564f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned R = MO.getReg(); 565f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar assert(MO.getSubReg() == 0 && "Unexpected subregister in definition"); 566f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (TargetRegisterInfo::isVirtualRegister(R)) 567f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RO.insert(std::make_pair(R, Index++)); 568f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 569f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 570f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 571f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 572f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Since some virtual registers may have had their def and uses eliminated, 573f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // they are no longer referenced in the code, and so they will not appear 574f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // in the map. 575f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 576f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 577f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 578f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarvoid HexagonGenInsert::buildOrderingBT(RegisterOrdering &RB, 579f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterOrdering &RO) const { 580f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Create a vector of all virtual registers (collect them from the base 581f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // ordering RB), and then sort it using the RegisterCell comparator. 582f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar BitValueOrdering BVO(RB); 583f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterCellLexCompare LexCmp(BVO, *CMS); 584f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef std::vector<unsigned> SortableVectorType; 585f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar SortableVectorType VRs; 586f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (RegisterOrdering::iterator I = RB.begin(), E = RB.end(); I != E; ++I) 587f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar VRs.push_back(I->first); 588f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar std::sort(VRs.begin(), VRs.end(), LexCmp); 589f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Transfer the results to the outgoing register ordering. 590f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned i = 0, n = VRs.size(); i < n; ++i) 591f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RO.insert(std::make_pair(VRs[i], i)); 592f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 593f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 594f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 595f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarinline bool HexagonGenInsert::isIntClass(const TargetRegisterClass *RC) const { 596f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return RC == &Hexagon::IntRegsRegClass || RC == &Hexagon::DoubleRegsRegClass; 597f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 598f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 599f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 600f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarbool HexagonGenInsert::isConstant(unsigned VR) const { 601f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitTracker::RegisterCell &RC = CMS->lookup(VR); 602f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar uint16_t W = RC.width(); 603f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (uint16_t i = 0; i < W; ++i) { 604f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitTracker::BitValue &BV = RC[i]; 605f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (BV.is(0) || BV.is(1)) 606f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 607f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 608f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 609f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return true; 610f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 611f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 612f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 613f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarbool HexagonGenInsert::isSmallConstant(unsigned VR) const { 614f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitTracker::RegisterCell &RC = CMS->lookup(VR); 615f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar uint16_t W = RC.width(); 616f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (W > 64) 617f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 618f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar uint64_t V = 0, B = 1; 619f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (uint16_t i = 0; i < W; ++i) { 620f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitTracker::BitValue &BV = RC[i]; 621f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (BV.is(1)) 622f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar V |= B; 623f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar else if (!BV.is(0)) 624f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 625f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar B <<= 1; 626f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 627f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 628f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // For 32-bit registers, consider: Rd = #s16. 629f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (W == 32) 630f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return isInt<16>(V); 631f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 632f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // For 64-bit registers, it's Rdd = #s8 or Rdd = combine(#s8,#s8) 633f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return isInt<8>(Lo_32(V)) && isInt<8>(Hi_32(V)); 634f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 635f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 636f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 637f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarbool HexagonGenInsert::isValidInsertForm(unsigned DstR, unsigned SrcR, 638f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned InsR, uint16_t L, uint16_t S) const { 639f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const TargetRegisterClass *DstRC = MRI->getRegClass(DstR); 640f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const TargetRegisterClass *SrcRC = MRI->getRegClass(SrcR); 641f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const TargetRegisterClass *InsRC = MRI->getRegClass(InsR); 642f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Only integet (32-/64-bit) register classes. 643f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!isIntClass(DstRC) || !isIntClass(SrcRC) || !isIntClass(InsRC)) 644f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 645f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // The "source" register must be of the same class as DstR. 646f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (DstRC != SrcRC) 647f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 648f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (DstRC == InsRC) 649f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return true; 650f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // A 64-bit register can only be generated from other 64-bit registers. 651f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (DstRC == &Hexagon::DoubleRegsRegClass) 652f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 653f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Otherwise, the L and S cannot span 32-bit word boundary. 654f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (S < 32 && S+L > 32) 655f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 656f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return true; 657f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 658f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 659f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 660f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarbool HexagonGenInsert::findSelfReference(unsigned VR) const { 661f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitTracker::RegisterCell &RC = CMS->lookup(VR); 662f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (uint16_t i = 0, w = RC.width(); i < w; ++i) { 663f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitTracker::BitValue &V = RC[i]; 664f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (V.Type == BitTracker::BitValue::Ref && V.RefI.Reg == VR) 665f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return true; 666f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 667f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 668f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 669f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 670f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 671f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarbool HexagonGenInsert::findNonSelfReference(unsigned VR) const { 672f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar BitTracker::RegisterCell RC = CMS->lookup(VR); 673f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (uint16_t i = 0, w = RC.width(); i < w; ++i) { 674f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitTracker::BitValue &V = RC[i]; 675f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (V.Type == BitTracker::BitValue::Ref && V.RefI.Reg != VR) 676f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return true; 677f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 678f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 679f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 680f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 681f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 682f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarvoid HexagonGenInsert::getInstrDefs(const MachineInstr *MI, 683f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterSet &Defs) const { 684f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) { 685f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const MachineOperand &MO = MI->getOperand(i); 686f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!MO.isReg() || !MO.isDef()) 687f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 688f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned R = MO.getReg(); 689f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!TargetRegisterInfo::isVirtualRegister(R)) 690f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 691f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Defs.insert(R); 692f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 693f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 694f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 695f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 696f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarvoid HexagonGenInsert::getInstrUses(const MachineInstr *MI, 697f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterSet &Uses) const { 698f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) { 699f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const MachineOperand &MO = MI->getOperand(i); 700f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!MO.isReg() || !MO.isUse()) 701f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 702f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned R = MO.getReg(); 703f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!TargetRegisterInfo::isVirtualRegister(R)) 704f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 705f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Uses.insert(R); 706f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 707f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 708f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 709f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 710f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarunsigned HexagonGenInsert::distance(const MachineBasicBlock *FromB, 711f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const MachineBasicBlock *ToB, const UnsignedMap &RPO, 712f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PairMapType &M) const { 713f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Forward distance from the end of a block to the beginning of it does 714f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // not make sense. This function should not be called with FromB == ToB. 715f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar assert(FromB != ToB); 716f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 717f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned FromN = FromB->getNumber(), ToN = ToB->getNumber(); 718f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // If we have already computed it, return the cached result. 719f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PairMapType::iterator F = M.find(std::make_pair(FromN, ToN)); 720f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (F != M.end()) 721f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return F->second; 722f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned ToRPO = RPO.lookup(ToN); 723f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 724f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned MaxD = 0; 725f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef MachineBasicBlock::const_pred_iterator pred_iterator; 726f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (pred_iterator I = ToB->pred_begin(), E = ToB->pred_end(); I != E; ++I) { 727f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const MachineBasicBlock *PB = *I; 728f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Skip back edges. Also, if FromB is a predecessor of ToB, the distance 729f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // along that path will be 0, and we don't need to do any calculations 730f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // on it. 731f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (PB == FromB || RPO.lookup(PB->getNumber()) >= ToRPO) 732f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 733f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned D = PB->size() + distance(FromB, PB, RPO, M); 734f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (D > MaxD) 735f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MaxD = D; 736f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 737f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 738f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Memoize the result for later lookup. 739f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar M.insert(std::make_pair(std::make_pair(FromN, ToN), MaxD)); 740f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return MaxD; 741f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 742f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 743f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 744f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarunsigned HexagonGenInsert::distance(MachineBasicBlock::const_iterator FromI, 745f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MachineBasicBlock::const_iterator ToI, const UnsignedMap &RPO, 746f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PairMapType &M) const { 747f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const MachineBasicBlock *FB = FromI->getParent(), *TB = ToI->getParent(); 748f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (FB == TB) 749f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return std::distance(FromI, ToI); 750f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned D1 = std::distance(TB->begin(), ToI); 751f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned D2 = distance(FB, TB, RPO, M); 752f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned D3 = std::distance(FromI, FB->end()); 753f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return D1+D2+D3; 754f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 755f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 756f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 757f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarbool HexagonGenInsert::findRecordInsertForms(unsigned VR, 758f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar OrderedRegisterList &AVs) { 759f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (isDebug()) { 760f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar dbgs() << LLVM_FUNCTION_NAME << ": " << PrintReg(VR, HRI) 761f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar << " AVs: " << PrintORL(AVs, HRI) << "\n"; 762f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 763f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (AVs.size() == 0) 764f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 765f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 766f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef OrderedRegisterList::iterator iterator; 767f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar BitValueOrdering BVO(BaseOrd); 768f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitTracker::RegisterCell &RC = CMS->lookup(VR); 769f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar uint16_t W = RC.width(); 770f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 771f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef std::pair<unsigned,uint16_t> RSRecord; // (reg,shift) 772f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef std::vector<RSRecord> RSListType; 773f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Have a map, with key being the matching prefix length, and the value 774f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // being the list of pairs (R,S), where R's prefix matches VR at S. 775f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // (DenseMap<uint16_t,RSListType> fails to instantiate.) 776f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef DenseMap<unsigned,RSListType> LRSMapType; 777f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LRSMapType LM; 778f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 779f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Conceptually, rotate the cell RC right (i.e. towards the LSB) by S, 780f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // and find matching prefixes from AVs with the rotated RC. Such a prefix 781f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // would match a string of bits (of length L) in RC starting at S. 782f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (uint16_t S = 0; S < W; ++S) { 783f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar iterator B = AVs.begin(), E = AVs.end(); 784f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // The registers in AVs are ordered according to the lexical order of 785f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // the corresponding register cells. This means that the range of regis- 786f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // ters in AVs that match a prefix of length L+1 will be contained in 787f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // the range that matches a prefix of length L. This means that we can 788f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // keep narrowing the search space as the prefix length goes up. This 789f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // helps reduce the overall complexity of the search. 790f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar uint16_t L; 791f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (L = 0; L < W-S; ++L) { 792f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Compare against VR's bits starting at S, which emulates rotation 793f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // of VR by S. 794f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterCellBitCompareSel RCB(VR, S+L, L, BVO, *CMS); 795f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar iterator NewB = std::lower_bound(B, E, VR, RCB); 796f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar iterator NewE = std::upper_bound(NewB, E, VR, RCB); 797f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // For the registers that are eliminated from the next range, L is 798f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // the longest prefix matching VR at position S (their prefixes 799f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // differ from VR at S+L). If L>0, record this information for later 800f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // use. 801f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (L > 0) { 802f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (iterator I = B; I != NewB; ++I) 803f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LM[L].push_back(std::make_pair(*I, S)); 804f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (iterator I = NewE; I != E; ++I) 805f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LM[L].push_back(std::make_pair(*I, S)); 806f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 807f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar B = NewB, E = NewE; 808f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (B == E) 809f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar break; 810f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 811f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Record the final register range. If this range is non-empty, then 812f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // L=W-S. 813f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar assert(B == E || L == W-S); 814f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (B != E) { 815f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (iterator I = B; I != E; ++I) 816f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LM[L].push_back(std::make_pair(*I, S)); 817f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // If B!=E, then we found a range of registers whose prefixes cover the 818f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // rest of VR from position S. There is no need to further advance S. 819f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar break; 820f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 821f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 822f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 823f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (isDebug()) { 824f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar dbgs() << "Prefixes matching register " << PrintReg(VR, HRI) << "\n"; 825f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (LRSMapType::iterator I = LM.begin(), E = LM.end(); I != E; ++I) { 826f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar dbgs() << " L=" << I->first << ':'; 827f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const RSListType &LL = I->second; 828f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned i = 0, n = LL.size(); i < n; ++i) 829f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar dbgs() << " (" << PrintReg(LL[i].first, HRI) << ",@" 830f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar << LL[i].second << ')'; 831f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar dbgs() << '\n'; 832f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 833f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 834f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 835f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 836f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool Recorded = false; 837f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 838f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (iterator I = AVs.begin(), E = AVs.end(); I != E; ++I) { 839f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned SrcR = *I; 840f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar int FDi = -1, LDi = -1; // First/last different bit. 841f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const BitTracker::RegisterCell &AC = CMS->lookup(SrcR); 842f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar uint16_t AW = AC.width(); 843f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (uint16_t i = 0, w = std::min(W, AW); i < w; ++i) { 844f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (RC[i] == AC[i]) 845f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 846f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (FDi == -1) 847f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar FDi = i; 848f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LDi = i; 849f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 850f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (FDi == -1) 851f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; // TODO (future): Record identical registers. 852f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Look for a register whose prefix could patch the range [FD..LD] 853f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // where VR and SrcR differ. 854f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar uint16_t FD = FDi, LD = LDi; // Switch to unsigned type. 855f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar uint16_t MinL = LD-FD+1; 856f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (uint16_t L = MinL; L < W; ++L) { 857f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LRSMapType::iterator F = LM.find(L); 858f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (F == LM.end()) 859f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 860f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RSListType &LL = F->second; 861f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned i = 0, n = LL.size(); i < n; ++i) { 862f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar uint16_t S = LL[i].second; 863f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // MinL is the minimum length of the prefix. Any length above MinL 864f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // allows some flexibility as to where the prefix can start: 865f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // given the extra length EL=L-MinL, the prefix must start between 866f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // max(0,FD-EL) and FD. 867f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (S > FD) // Starts too late. 868f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 869f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar uint16_t EL = L-MinL; 870f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar uint16_t LowS = (EL < FD) ? FD-EL : 0; 871f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (S < LowS) // Starts too early. 872f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 873f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned InsR = LL[i].first; 874f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!isValidInsertForm(VR, SrcR, InsR, L, S)) 875f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 876f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (isDebug()) { 877f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar dbgs() << PrintReg(VR, HRI) << " = insert(" << PrintReg(SrcR, HRI) 878f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar << ',' << PrintReg(InsR, HRI) << ",#" << L << ",#" 879f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar << S << ")\n"; 880f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 881f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFRecordWithRegSet RR(IFRecord(SrcR, InsR, L, S), RegisterSet()); 882f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFMap[VR].push_back(RR); 883f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Recorded = true; 884f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 885f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 886f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 887f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 888f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return Recorded; 889f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 890f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 891f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 892f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarvoid HexagonGenInsert::collectInBlock(MachineBasicBlock *B, 893f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar OrderedRegisterList &AVs) { 894f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (isDebug()) 895f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar dbgs() << "visiting block BB#" << B->getNumber() << "\n"; 896f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 897f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // First, check if this block is reachable at all. If not, the bit tracker 898f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // will not have any information about registers in it. 899f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!CMS->BT.reached(B)) 900f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return; 901f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 902f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool DoConst = OptConst; 903f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Keep a separate set of registers defined in this block, so that we 904f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // can remove them from the list of available registers once all DT 905f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // successors have been processed. 906f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterSet BlockDefs, InsDefs; 907f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (MachineBasicBlock::iterator I = B->begin(), E = B->end(); I != E; ++I) { 908f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MachineInstr *MI = &*I; 909f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar InsDefs.clear(); 910f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar getInstrDefs(MI, InsDefs); 911f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Leave those alone. They are more transparent than "insert". 912f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool Skip = MI->isCopy() || MI->isRegSequence(); 913f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 914f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!Skip) { 915f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Visit all defined registers, and attempt to find the corresponding 916f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // "insert" representations. 917f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned VR = InsDefs.find_first(); VR; VR = InsDefs.find_next(VR)) { 918f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Do not collect registers that are known to be compile-time cons- 919f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // tants, unless requested. 920f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!DoConst && isConstant(VR)) 921f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 922f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // If VR's cell contains a reference to VR, then VR cannot be defined 923f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // via "insert". If VR is a constant that can be generated in a single 924f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // instruction (without constant extenders), generating it via insert 925f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // makes no sense. 926f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (findSelfReference(VR) || isSmallConstant(VR)) 927f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 928f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 929f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar findRecordInsertForms(VR, AVs); 930f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 931f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 932f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 933f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Insert the defined registers into the list of available registers 934f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // after they have been processed. 935f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned VR = InsDefs.find_first(); VR; VR = InsDefs.find_next(VR)) 936f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AVs.insert(VR); 937f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar BlockDefs.insert(InsDefs); 938f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 939f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 940f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MachineDomTreeNode *N = MDT->getNode(B); 941f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef GraphTraits<MachineDomTreeNode*> GTN; 942f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef GTN::ChildIteratorType ChildIter; 943f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (ChildIter I = GTN::child_begin(N), E = GTN::child_end(N); I != E; ++I) { 944f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MachineBasicBlock *SB = (*I)->getBlock(); 945f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar collectInBlock(SB, AVs); 946f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 947f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 948f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned VR = BlockDefs.find_first(); VR; VR = BlockDefs.find_next(VR)) 949f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AVs.remove(VR); 950f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 951f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 952f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 953f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarvoid HexagonGenInsert::findRemovableRegisters(unsigned VR, IFRecord IF, 954f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterSet &RMs) const { 955f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // For a given register VR and a insert form, find the registers that are 956f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // used by the current definition of VR, and which would no longer be 957f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // needed for it after the definition of VR is replaced with the insert 958f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // form. These are the registers that could potentially become dead. 959f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterSet Regs[2]; 960f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 961f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned S = 0; // Register set selector. 962f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Regs[S].insert(VR); 963f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 964f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar while (!Regs[S].empty()) { 965f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Breadth-first search. 966f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned OtherS = 1-S; 967f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Regs[OtherS].clear(); 968f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned R = Regs[S].find_first(); R; R = Regs[S].find_next(R)) { 969f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Regs[S].remove(R); 970f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (R == IF.SrcR || R == IF.InsR) 971f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 972f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Check if a given register has bits that are references to any other 973f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // registers. This is to detect situations where the instruction that 974f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // defines register R takes register Q as an operand, but R itself does 975f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // not contain any bits from Q. Loads are examples of how this could 976f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // happen: 977f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // R = load Q 978f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // In this case (assuming we do not have any knowledge about the loaded 979f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // value), we must not treat R as a "conveyance" of the bits from Q. 980f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // (The information in BT about R's bits would have them as constants, 981f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // in case of zero-extending loads, or refs to R.) 982f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!findNonSelfReference(R)) 983f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 984f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RMs.insert(R); 985f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const MachineInstr *DefI = MRI->getVRegDef(R); 986f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar assert(DefI); 987f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Do not iterate past PHI nodes to avoid infinite loops. This can 988f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // make the final set a bit less accurate, but the removable register 989f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // sets are an approximation anyway. 990f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (DefI->isPHI()) 991f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 992f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar getInstrUses(DefI, Regs[OtherS]); 993f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 994f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar S = OtherS; 995f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 996f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // The register VR is added to the list as a side-effect of the algorithm, 997f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // but it is not "potentially removable". A potentially removable register 998f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // is one that may become unused (dead) after conversion to the insert form 999f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // IF, and obviously VR (or its replacement) will not become dead by apply- 1000f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // ing IF. 1001f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RMs.remove(VR); 1002f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 1003f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1004f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1005f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarvoid HexagonGenInsert::computeRemovableRegisters() { 1006f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) { 1007f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFListType &LL = I->second; 1008f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned i = 0, n = LL.size(); i < n; ++i) 1009f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar findRemovableRegisters(I->first, LL[i].first, LL[i].second); 1010f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1011f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 1012f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1013f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1014f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarvoid HexagonGenInsert::pruneEmptyLists() { 1015f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Remove all entries from the map, where the register has no insert forms 1016f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // associated with it. 1017f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef SmallVector<IFMapType::iterator,16> IterListType; 1018f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IterListType Prune; 1019f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) { 1020f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (I->second.size() == 0) 1021f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Prune.push_back(I); 1022f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1023f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned i = 0, n = Prune.size(); i < n; ++i) 1024f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFMap.erase(Prune[i]); 1025f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 1026f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1027f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1028f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarvoid HexagonGenInsert::pruneCoveredSets(unsigned VR) { 1029f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFMapType::iterator F = IFMap.find(VR); 1030f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar assert(F != IFMap.end()); 1031f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFListType &LL = F->second; 1032f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1033f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // First, examine the IF candidates for register VR whose removable-regis- 1034f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // ter sets are empty. This means that a given candidate will not help eli- 1035f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // minate any registers, but since "insert" is not a constant-extendable 1036f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // instruction, using such a candidate may reduce code size if the defini- 1037f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // tion of VR is constant-extended. 1038f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // If there exists a candidate with a non-empty set, the ones with empty 1039f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // sets will not be used and can be removed. 1040f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MachineInstr *DefVR = MRI->getVRegDef(VR); 1041f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool DefEx = HII->isConstExtended(DefVR); 1042f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool HasNE = false; 1043f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned i = 0, n = LL.size(); i < n; ++i) { 1044f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (LL[i].second.empty()) 1045f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 1046f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar HasNE = true; 1047f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar break; 1048f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1049f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!DefEx || HasNE) { 1050f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // The definition of VR is not constant-extended, or there is a candidate 1051f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // with a non-empty set. Remove all candidates with empty sets. 1052f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar auto IsEmpty = [] (const IFRecordWithRegSet &IR) -> bool { 1053f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return IR.second.empty(); 1054f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar }; 1055f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar auto End = std::remove_if(LL.begin(), LL.end(), IsEmpty); 1056f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (End != LL.end()) 1057f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LL.erase(End, LL.end()); 1058f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } else { 1059f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // The definition of VR is constant-extended, and all candidates have 1060f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // empty removable-register sets. Pick the maximum candidate, and remove 1061f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // all others. The "maximum" does not have any special meaning here, it 1062f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // is only so that the candidate that will remain on the list is selec- 1063f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // ted deterministically. 1064f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFRecord MaxIF = LL[0].first; 1065f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned i = 1, n = LL.size(); i < n; ++i) { 1066f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // If LL[MaxI] < LL[i], then MaxI = i. 1067f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const IFRecord &IF = LL[i].first; 1068f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned M0 = BaseOrd[MaxIF.SrcR], M1 = BaseOrd[MaxIF.InsR]; 1069f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned R0 = BaseOrd[IF.SrcR], R1 = BaseOrd[IF.InsR]; 1070f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (M0 > R0) 1071f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 1072f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (M0 == R0) { 1073f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (M1 > R1) 1074f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 1075f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (M1 == R1) { 1076f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (MaxIF.Wdh > IF.Wdh) 1077f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 1078f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (MaxIF.Wdh == IF.Wdh && MaxIF.Off >= IF.Off) 1079f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 1080f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1081f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1082f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // MaxIF < IF. 1083f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MaxIF = IF; 1084f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1085f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Remove everything except the maximum candidate. All register sets 1086f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // are empty, so no need to preserve anything. 1087f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LL.clear(); 1088f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LL.push_back(std::make_pair(MaxIF, RegisterSet())); 1089f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1090f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1091f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Now, remove those whose sets of potentially removable registers are 1092f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // contained in another IF candidate for VR. For example, given these 1093f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // candidates for vreg45, 1094f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // %vreg45: 1095f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // (%vreg44,%vreg41,#9,#8), { %vreg42 } 1096f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // (%vreg43,%vreg41,#9,#8), { %vreg42 %vreg44 } 1097f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // remove the first one, since it is contained in the second one. 1098f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned i = 0, n = LL.size(); i < n; ) { 1099f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const RegisterSet &RMi = LL[i].second; 1100f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned j = 0; 1101f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar while (j < n) { 1102f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (j != i && LL[j].second.includes(RMi)) 1103f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar break; 1104f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar j++; 1105f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1106f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (j == n) { // RMi not contained in anything else. 1107f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar i++; 1108f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 1109f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1110f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LL.erase(LL.begin()+i); 1111f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar n = LL.size(); 1112f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1113f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 1114f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1115f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1116f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarvoid HexagonGenInsert::pruneUsesTooFar(unsigned VR, const UnsignedMap &RPO, 1117f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PairMapType &M) { 1118f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFMapType::iterator F = IFMap.find(VR); 1119f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar assert(F != IFMap.end()); 1120f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFListType &LL = F->second; 1121f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned Cutoff = VRegDistCutoff; 1122f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const MachineInstr *DefV = MRI->getVRegDef(VR); 1123f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1124f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned i = LL.size(); i > 0; --i) { 1125f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned SR = LL[i-1].first.SrcR, IR = LL[i-1].first.InsR; 1126f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const MachineInstr *DefS = MRI->getVRegDef(SR); 1127f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const MachineInstr *DefI = MRI->getVRegDef(IR); 1128f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned DSV = distance(DefS, DefV, RPO, M); 1129f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (DSV < Cutoff) { 1130f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned DIV = distance(DefI, DefV, RPO, M); 1131f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (DIV < Cutoff) 1132f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 1133f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1134f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LL.erase(LL.begin()+(i-1)); 1135f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1136f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 1137f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1138f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1139f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarvoid HexagonGenInsert::pruneRegCopies(unsigned VR) { 1140f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFMapType::iterator F = IFMap.find(VR); 1141f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar assert(F != IFMap.end()); 1142f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFListType &LL = F->second; 1143f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1144f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar auto IsCopy = [] (const IFRecordWithRegSet &IR) -> bool { 1145f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return IR.first.Wdh == 32 && (IR.first.Off == 0 || IR.first.Off == 32); 1146f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar }; 1147f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar auto End = std::remove_if(LL.begin(), LL.end(), IsCopy); 1148f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (End != LL.end()) 1149f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LL.erase(End, LL.end()); 1150f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 1151f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1152f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1153f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarvoid HexagonGenInsert::pruneCandidates() { 1154f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Remove candidates that are not beneficial, regardless of the final 1155f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // selection method. 1156f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // First, remove candidates whose potentially removable set is a subset 1157f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // of another candidate's set. 1158f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) 1159f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar pruneCoveredSets(I->first); 1160f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1161f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar UnsignedMap RPO; 1162f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef ReversePostOrderTraversal<const MachineFunction*> RPOTType; 1163f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RPOTType RPOT(MFN); 1164f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned RPON = 0; 1165f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (RPOTType::rpo_iterator I = RPOT.begin(), E = RPOT.end(); I != E; ++I) 1166f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RPO[(*I)->getNumber()] = RPON++; 1167f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1168f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PairMapType Memo; // Memoization map for distance calculation. 1169f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Remove candidates that would use registers defined too far away. 1170f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) 1171f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar pruneUsesTooFar(I->first, RPO, Memo); 1172f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1173f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar pruneEmptyLists(); 1174f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1175f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) 1176f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar pruneRegCopies(I->first); 1177f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 1178f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1179f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1180f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarnamespace { 1181f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Class for comparing IF candidates for registers that have multiple of 1182f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // them. The smaller the candidate, according to this ordering, the better. 1183f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // First, compare the number of zeros in the associated potentially remova- 1184f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // ble register sets. "Zero" indicates that the register is very likely to 1185f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // become dead after this transformation. 1186f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Second, compare "averages", i.e. use-count per size. The lower wins. 1187f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // After that, it does not really matter which one is smaller. Resolve 1188f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // the tie in some deterministic way. 1189f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar struct IFOrdering { 1190f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFOrdering(const UnsignedMap &UC, const RegisterOrdering &BO) 1191f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar : UseC(UC), BaseOrd(BO) {} 1192f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool operator() (const IFRecordWithRegSet &A, 1193f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const IFRecordWithRegSet &B) const; 1194f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar private: 1195f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar void stats(const RegisterSet &Rs, unsigned &Size, unsigned &Zero, 1196f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned &Sum) const; 1197f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const UnsignedMap &UseC; 1198f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const RegisterOrdering &BaseOrd; 1199f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar }; 1200f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 1201f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1202f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1203f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarbool IFOrdering::operator() (const IFRecordWithRegSet &A, 1204f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const IFRecordWithRegSet &B) const { 1205f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned SizeA = 0, ZeroA = 0, SumA = 0; 1206f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned SizeB = 0, ZeroB = 0, SumB = 0; 1207f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar stats(A.second, SizeA, ZeroA, SumA); 1208f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar stats(B.second, SizeB, ZeroB, SumB); 1209f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1210f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // We will pick the minimum element. The more zeros, the better. 1211f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (ZeroA != ZeroB) 1212f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return ZeroA > ZeroB; 1213f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Compare SumA/SizeA with SumB/SizeB, lower is better. 1214f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar uint64_t AvgA = SumA*SizeB, AvgB = SumB*SizeA; 1215f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (AvgA != AvgB) 1216f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return AvgA < AvgB; 1217f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1218f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // The sets compare identical so far. Resort to comparing the IF records. 1219f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // The actual values don't matter, this is only for determinism. 1220f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned OSA = BaseOrd[A.first.SrcR], OSB = BaseOrd[B.first.SrcR]; 1221f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (OSA != OSB) 1222f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return OSA < OSB; 1223f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned OIA = BaseOrd[A.first.InsR], OIB = BaseOrd[B.first.InsR]; 1224f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (OIA != OIB) 1225f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return OIA < OIB; 1226f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (A.first.Wdh != B.first.Wdh) 1227f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return A.first.Wdh < B.first.Wdh; 1228f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return A.first.Off < B.first.Off; 1229f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 1230f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1231f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1232f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarvoid IFOrdering::stats(const RegisterSet &Rs, unsigned &Size, unsigned &Zero, 1233f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned &Sum) const { 1234f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned R = Rs.find_first(); R; R = Rs.find_next(R)) { 1235f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar UnsignedMap::const_iterator F = UseC.find(R); 1236f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar assert(F != UseC.end()); 1237f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned UC = F->second; 1238f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (UC == 0) 1239f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Zero++; 1240f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Sum += UC; 1241f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Size++; 1242f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1243f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 1244f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1245f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1246f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarvoid HexagonGenInsert::selectCandidates() { 1247f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Some registers may have multiple valid candidates. Pick the best one 1248f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // (or decide not to use any). 1249f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1250f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Compute the "removability" measure of R: 1251f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // For each potentially removable register R, record the number of regis- 1252f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // ters with IF candidates, where R appears in at least one set. 1253f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterSet AllRMs; 1254f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar UnsignedMap UseC, RemC; 1255f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFMapType::iterator End = IFMap.end(); 1256f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1257f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) { 1258f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const IFListType &LL = I->second; 1259f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterSet TT; 1260f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned i = 0, n = LL.size(); i < n; ++i) 1261f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar TT.insert(LL[i].second); 1262f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned R = TT.find_first(); R; R = TT.find_next(R)) 1263f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RemC[R]++; 1264f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AllRMs.insert(TT); 1265f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1266f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1267f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned R = AllRMs.find_first(); R; R = AllRMs.find_next(R)) { 1268f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef MachineRegisterInfo::use_nodbg_iterator use_iterator; 1269f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef SmallSet<const MachineInstr*,16> InstrSet; 1270f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar InstrSet UIs; 1271f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Count as the number of instructions in which R is used, not the 1272f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // number of operands. 1273f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar use_iterator E = MRI->use_nodbg_end(); 1274f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (use_iterator I = MRI->use_nodbg_begin(R); I != E; ++I) 1275f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar UIs.insert(I->getParent()); 1276f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned C = UIs.size(); 1277f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Calculate a measure, which is the number of instructions using R, 1278f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // minus the "removability" count computed earlier. 1279f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned D = RemC[R]; 1280f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar UseC[R] = (C > D) ? C-D : 0; // doz 1281f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1282f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1283f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1284f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool SelectAll0 = OptSelectAll0, SelectHas0 = OptSelectHas0; 1285f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!SelectAll0 && !SelectHas0) 1286f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar SelectAll0 = true; 1287f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1288f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // The smaller the number UseC for a given register R, the "less used" 1289f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // R is aside from the opportunities for removal offered by generating 1290f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // "insert" instructions. 1291f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Iterate over the IF map, and for those registers that have multiple 1292f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // candidates, pick the minimum one according to IFOrdering. 1293f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFOrdering IFO(UseC, BaseOrd); 1294f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) { 1295f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFListType &LL = I->second; 1296f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (LL.empty()) 1297f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 1298f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Get the minimum element, remember it and clear the list. If the 1299f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // element found is adequate, we will put it back on the list, other- 1300f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // wise the list will remain empty, and the entry for this register 1301f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // will be removed (i.e. this register will not be replaced by insert). 1302f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFListType::iterator MinI = std::min_element(LL.begin(), LL.end(), IFO); 1303f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar assert(MinI != LL.end()); 1304f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFRecordWithRegSet M = *MinI; 1305f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LL.clear(); 1306f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1307f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // We want to make sure that this replacement will have a chance to be 1308f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // beneficial, and that means that we want to have indication that some 1309f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // register will be removed. The most likely registers to be eliminated 1310f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // are the use operands in the definition of I->first. Accept/reject a 1311f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // candidate based on how many of its uses it can potentially eliminate. 1312f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1313f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegisterSet Us; 1314f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const MachineInstr *DefI = MRI->getVRegDef(I->first); 1315f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar getInstrUses(DefI, Us); 1316f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool Accept = false; 1317f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1318f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (SelectAll0) { 1319f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool All0 = true; 1320f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned R = Us.find_first(); R; R = Us.find_next(R)) { 1321f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (UseC[R] == 0) 1322f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 1323f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar All0 = false; 1324f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar break; 1325f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1326f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Accept = All0; 1327f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } else if (SelectHas0) { 1328f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool Has0 = false; 1329f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned R = Us.find_first(); R; R = Us.find_next(R)) { 1330f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (UseC[R] != 0) 1331f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 1332f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Has0 = true; 1333f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar break; 1334f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1335f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Accept = Has0; 1336f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1337f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (Accept) 1338f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LL.push_back(M); 1339f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1340f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1341f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Remove candidates that add uses of removable registers, unless the 1342f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // removable registers are among replacement candidates. 1343f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Recompute the removable registers, since some candidates may have 1344f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // been eliminated. 1345f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AllRMs.clear(); 1346f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) { 1347f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const IFListType &LL = I->second; 1348f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (LL.size() > 0) 1349f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AllRMs.insert(LL[0].second); 1350f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1351f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) { 1352f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFListType &LL = I->second; 1353f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (LL.size() == 0) 1354f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 1355f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned SR = LL[0].first.SrcR, IR = LL[0].first.InsR; 1356f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (AllRMs[SR] || AllRMs[IR]) 1357f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LL.clear(); 1358f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1359f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1360f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar pruneEmptyLists(); 1361f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 1362f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1363f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1364f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarbool HexagonGenInsert::generateInserts() { 1365f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Create a new register for each one from IFMap, and store them in the 1366f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // map. 1367f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar UnsignedMap RegMap; 1368f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) { 1369f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned VR = I->first; 1370f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const TargetRegisterClass *RC = MRI->getRegClass(VR); 1371f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned NewVR = MRI->createVirtualRegister(RC); 1372f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RegMap[VR] = NewVR; 1373f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1374f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1375f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // We can generate the "insert" instructions using potentially stale re- 1376f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // gisters: SrcR and InsR for a given VR may be among other registers that 1377f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // are also replaced. This is fine, we will do the mass "rauw" a bit later. 1378f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) { 1379f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MachineInstr *MI = MRI->getVRegDef(I->first); 1380f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MachineBasicBlock &B = *MI->getParent(); 1381f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar DebugLoc DL = MI->getDebugLoc(); 1382f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned NewR = RegMap[I->first]; 1383f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool R32 = MRI->getRegClass(NewR) == &Hexagon::IntRegsRegClass; 1384f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const MCInstrDesc &D = R32 ? HII->get(Hexagon::S2_insert) 1385f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar : HII->get(Hexagon::S2_insertp); 1386f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFRecord IF = I->second[0].first; 1387f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned Wdh = IF.Wdh, Off = IF.Off; 1388f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned InsS = 0; 1389f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (R32 && MRI->getRegClass(IF.InsR) == &Hexagon::DoubleRegsRegClass) { 1390f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar InsS = Hexagon::subreg_loreg; 1391f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (Off >= 32) { 1392f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar InsS = Hexagon::subreg_hireg; 1393f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Off -= 32; 1394f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1395f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1396f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Advance to the proper location for inserting instructions. This could 1397f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // be B.end(). 1398f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MachineBasicBlock::iterator At = MI; 1399f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (MI->isPHI()) 1400f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar At = B.getFirstNonPHI(); 1401f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1402f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar BuildMI(B, At, DL, D, NewR) 1403f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar .addReg(IF.SrcR) 1404f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar .addReg(IF.InsR, 0, InsS) 1405f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar .addImm(Wdh) 1406f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar .addImm(Off); 1407f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1408f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MRI->clearKillFlags(IF.SrcR); 1409f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MRI->clearKillFlags(IF.InsR); 1410f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1411f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1412f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) { 1413f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MachineInstr *DefI = MRI->getVRegDef(I->first); 1414f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MRI->replaceRegWith(I->first, RegMap[I->first]); 1415f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar DefI->eraseFromParent(); 1416f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1417f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1418f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return true; 1419f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 1420f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1421f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1422f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarbool HexagonGenInsert::removeDeadCode(MachineDomTreeNode *N) { 1423f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool Changed = false; 1424f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef GraphTraits<MachineDomTreeNode*> GTN; 1425f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (auto I = GTN::child_begin(N), E = GTN::child_end(N); I != E; ++I) 1426f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Changed |= removeDeadCode(*I); 1427f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1428f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MachineBasicBlock *B = N->getBlock(); 1429f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar std::vector<MachineInstr*> Instrs; 1430f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (auto I = B->rbegin(), E = B->rend(); I != E; ++I) 1431f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Instrs.push_back(&*I); 1432f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1433f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (auto I = Instrs.begin(), E = Instrs.end(); I != E; ++I) { 1434f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MachineInstr *MI = *I; 1435f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned Opc = MI->getOpcode(); 1436f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Do not touch lifetime markers. This is why the target-independent DCE 1437f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // cannot be used. 1438f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (Opc == TargetOpcode::LIFETIME_START || 1439f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Opc == TargetOpcode::LIFETIME_END) 1440f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 1441f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool Store = false; 1442f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (MI->isInlineAsm() || !MI->isSafeToMove(nullptr, Store)) 1443f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 1444f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1445f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool AllDead = true; 1446f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar SmallVector<unsigned,2> Regs; 1447de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (ConstMIOperands Op(*MI); Op.isValid(); ++Op) { 1448f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!Op->isReg() || !Op->isDef()) 1449f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 1450f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned R = Op->getReg(); 1451f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!TargetRegisterInfo::isVirtualRegister(R) || 1452f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar !MRI->use_nodbg_empty(R)) { 1453f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AllDead = false; 1454f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar break; 1455f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1456f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Regs.push_back(R); 1457f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1458f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!AllDead) 1459f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 1460f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1461f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar B->erase(MI); 1462f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned I = 0, N = Regs.size(); I != N; ++I) 1463f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MRI->markUsesInDebugValueAsUndef(Regs[I]); 1464f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Changed = true; 1465f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1466f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1467f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return Changed; 1468f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 1469f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1470f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1471f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarbool HexagonGenInsert::runOnMachineFunction(MachineFunction &MF) { 1472de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (skipFunction(*MF.getFunction())) 1473de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 1474de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 1475f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool Timing = OptTiming, TimingDetail = Timing && OptTimingDetail; 1476f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar bool Changed = false; 1477f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar TimerGroup __G("hexinsert"); 1478f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar NamedRegionTimer __T("hexinsert", Timing && !TimingDetail); 1479f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1480f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Sanity check: one, but not both. 1481f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar assert(!OptSelectAll0 || !OptSelectHas0); 1482f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1483f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFMap.clear(); 1484f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar BaseOrd.clear(); 1485f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar CellOrd.clear(); 1486f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1487f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const auto &ST = MF.getSubtarget<HexagonSubtarget>(); 1488f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar HII = ST.getInstrInfo(); 1489f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar HRI = ST.getRegisterInfo(); 1490f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MFN = &MF; 1491f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MRI = &MF.getRegInfo(); 1492f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MDT = &getAnalysis<MachineDominatorTree>(); 1493f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1494f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Clean up before any further processing, so that dead code does not 1495f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // get used in a newly generated "insert" instruction. Have a custom 1496f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // version of DCE that preserves lifetime markers. Without it, merging 1497f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // of stack objects can fail to recognize and merge disjoint objects 1498f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // leading to unnecessary stack growth. 1499f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Changed = removeDeadCode(MDT->getRootNode()); 1500f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1501f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const HexagonEvaluator HE(*HRI, *MRI, *HII, MF); 1502f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar BitTracker BTLoc(HE, MF); 1503f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar BTLoc.trace(isDebug()); 1504f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar BTLoc.run(); 1505f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar CellMapShadow MS(BTLoc); 1506f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar CMS = &MS; 1507f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1508f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar buildOrderingMF(BaseOrd); 1509f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar buildOrderingBT(BaseOrd, CellOrd); 1510f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1511f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (isDebug()) { 1512f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar dbgs() << "Cell ordering:\n"; 1513f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (RegisterOrdering::iterator I = CellOrd.begin(), E = CellOrd.end(); 1514f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar I != E; ++I) { 1515f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned VR = I->first, Pos = I->second; 1516f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar dbgs() << PrintReg(VR, HRI) << " -> " << Pos << "\n"; 1517f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1518f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1519f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1520f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Collect candidates for conversion into the insert forms. 1521f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MachineBasicBlock *RootB = MDT->getRoot(); 1522f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar OrderedRegisterList AvailR(CellOrd); 1523f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1524f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar { 1525f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar NamedRegionTimer _T("collection", "hexinsert", TimingDetail); 1526f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar collectInBlock(RootB, AvailR); 1527f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Complete the information gathered in IFMap. 1528f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar computeRemovableRegisters(); 1529f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1530f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1531f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (isDebug()) { 1532f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar dbgs() << "Candidates after collection:\n"; 1533f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar dump_map(); 1534f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1535f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1536f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (IFMap.empty()) 1537f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return Changed; 1538f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1539f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar { 1540f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar NamedRegionTimer _T("pruning", "hexinsert", TimingDetail); 1541f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar pruneCandidates(); 1542f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1543f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1544f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (isDebug()) { 1545f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar dbgs() << "Candidates after pruning:\n"; 1546f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar dump_map(); 1547f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1548f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1549f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (IFMap.empty()) 1550f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return Changed; 1551f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1552f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar { 1553f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar NamedRegionTimer _T("selection", "hexinsert", TimingDetail); 1554f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar selectCandidates(); 1555f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1556f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1557f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (isDebug()) { 1558f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar dbgs() << "Candidates after selection:\n"; 1559f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar dump_map(); 1560f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1561f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1562f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Filter out vregs beyond the cutoff. 1563f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (VRegIndexCutoff.getPosition()) { 1564f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned Cutoff = VRegIndexCutoff; 1565f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar typedef SmallVector<IFMapType::iterator,16> IterListType; 1566f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IterListType Out; 1567f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) { 1568f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned Idx = TargetRegisterInfo::virtReg2Index(I->first); 1569f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (Idx >= Cutoff) 1570f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Out.push_back(I); 1571f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1572f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (unsigned i = 0, n = Out.size(); i < n; ++i) 1573f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar IFMap.erase(Out[i]); 1574f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1575f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (IFMap.empty()) 1576f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return Changed; 1577f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1578f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar { 1579f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar NamedRegionTimer _T("generation", "hexinsert", TimingDetail); 1580f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar generateInserts(); 1581f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 1582f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1583f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return true; 1584f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 1585f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1586f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1587f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga NainarFunctionPass *llvm::createHexagonGenInsert() { 1588f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return new HexagonGenInsert(); 1589f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 1590f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1591f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1592f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar//===----------------------------------------------------------------------===// 1593f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar// Public Constructor Functions 1594f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar//===----------------------------------------------------------------------===// 1595f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1596f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga NainarINITIALIZE_PASS_BEGIN(HexagonGenInsert, "hexinsert", 1597f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar "Hexagon generate \"insert\" instructions", false, false) 1598f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga NainarINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 1599f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga NainarINITIALIZE_PASS_END(HexagonGenInsert, "hexinsert", 1600f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar "Hexagon generate \"insert\" instructions", false, false) 1601