WebAssemblyRegColoring.cpp Source File (original) (raw)

27using namespace llvm;

29#define DEBUG_TYPE "wasm-reg-coloring"

31namespace {

33public:

34 static char ID;

37 StringRef getPassName() const override {

38 return "WebAssembly Register Coloring";

39 }

41 void getAnalysisUsage(AnalysisUsage &AU) const override {

48 }

52private:

53};

54}

56char WebAssemblyRegColoring::ID = 0;

58 "Minimize number of registers used", false, false)

61 return new WebAssemblyRegColoring();

62}

67 unsigned VReg) {

68 float Weight = 0.0f;

71 *MO.getParent());

72 return Weight;

73}

82 DbgVRegToValues;

88 auto CloseNewDVRange = [&DbgVRegToValues, &ToInsert](SlotIndex Slot) {

89 for (auto *X : ToInsert) {

90 for (const auto &Op : X->debug_operands()) {

91 if (Op.isReg() && Op.getReg().isVirtual())

92 DbgVRegToValues[Op.getReg()].push_back({Slot, X});

93 }

94 }

96 ToInsert.clear();

97 };

100

101

102 for (auto &MBB : MF) {

104

105 for (auto &MI : MBB) {

106 if (MI.isDebugValue()) {

108 return MO.isReg() && MO.getReg().isVirtual();

109 }))

111 } else if (.isDebugOrPseudoInstr()) {

113 CloseNewDVRange(CurrentSlot);

114 }

115 }

116

117

119 }

120

121

122 for (auto &Pair : DbgVRegToValues)

124 return DbgVRegToValues;

125}

126

127

128

129

133 DenseMap<Register, std::vector<std::pair<SlotIndex, MachineInstr *>>>

134 &DbgVRegToValues) {

135#ifndef NDEBUG

137#endif

138 for (const auto &CoalescedIntervals : Assignments) {

139 if (CoalescedIntervals.empty())

140 continue;

141 for (LiveInterval *LI : CoalescedIntervals) {

143#ifndef NDEBUG

144

146#endif

147 auto RegMapIt = DbgVRegToValues.find(Reg);

148 if (RegMapIt == DbgVRegToValues.end())

149 continue;

151 bool LastUndefResult = false;

152 for (auto [Slot, DbgValue] : RegMapIt->second) {

153

154

155

156

157

158

159

160

161 if (Slot == LastSlot) {

162 if (LastUndefResult) {

164 DbgValue->setDebugValueUndef();

165 }

166 continue;

167 }

168 LastSlot = Slot;

169 LastUndefResult = false;

170 for (LiveInterval *OtherLI : CoalescedIntervals) {

171 if (LI == OtherLI)

172 continue;

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207 auto *SegmentIt = OtherLI->find(Slot);

208 if (SegmentIt != OtherLI->end() && SegmentIt->contains(Slot)) {

210 DbgValue->setDebugValueUndef();

211 LastUndefResult = true;

212 break;

213 }

214 }

215 }

216 }

217 }

218}

219

220bool WebAssemblyRegColoring::runOnMachineFunction(MachineFunction &MF) {

222 dbgs() << "********** Register Coloring **********\n"

223 << "********** Function: " << MF.getName() << '\n';

224 });

225

226

227

228

229

231 return false;

232

234 LiveIntervals *Liveness = &getAnalysis().getLIS();

235 const MachineBlockFrequencyInfo *MBFI =

236 &getAnalysis().getMBFI();

237 WebAssemblyFunctionInfo &MFI = *MF.getInfo();

238

239

240 MRI->leaveSSA();

241

242

243 unsigned NumVRegs = MRI->getNumVirtRegs();

245 SortedIntervals.reserve(NumVRegs);

246

247

249

250 LLVM_DEBUG(dbgs() << "Interesting register intervals:\n");

251 for (unsigned I = 0; I < NumVRegs; ++I) {

252 Register VReg = Register::index2VirtReg(I);

254 continue;

255

256 if (MRI->use_empty(VReg))

257 continue;

258

259 LiveInterval *LI = &Liveness->getInterval(VReg);

264 }

266

267

268

269

270

271 llvm::sort(SortedIntervals, [MRI](LiveInterval *LHS, LiveInterval *RHS) {

272 if (MRI->isLiveIn(LHS->reg()) != MRI->isLiveIn(RHS->reg()))

273 return MRI->isLiveIn(LHS->reg());

274 if (LHS->weight() != RHS->weight())

275 return LHS->weight() > RHS->weight();

276 if (LHS->empty() || RHS->empty())

277 return LHS ->empty() && RHS->empty();

279 });

280

281 LLVM_DEBUG(dbgs() << "Coloring register intervals:\n");

282 SmallVector<unsigned, 16> SlotMapping(SortedIntervals.size(), -1u);

284 SortedIntervals.size());

285 BitVector UsedColors(SortedIntervals.size());

287 for (size_t I = 0, E = SortedIntervals.size(); I < E; ++I) {

288 LiveInterval *LI = SortedIntervals[I];

290 size_t Color = I;

291 const TargetRegisterClass *RC = MRI->getRegClass(Old);

292

293

294 if ( MRI ->isLiveIn(Old))

295 for (unsigned C : UsedColors.set_bits()) {

296 if (MRI->getRegClass(SortedIntervals[C]->reg()) != RC)

297 continue;

298 for (LiveInterval *OtherLI : Assignments[C])

299 if (!OtherLI->empty() && OtherLI->overlaps(*LI))

300 goto continue_outer;

301 Color = C;

302 break;

303 continue_outer:;

304 }

305

306 Register New = SortedIntervals[Color]->reg();

307 SlotMapping[I] = New;

309 UsedColors.set(Color);

310 Assignments[Color].push_back(LI);

311

316 }

318 return false;

319

320

322

323

324 for (size_t I = 0, E = SortedIntervals.size(); I < E; ++I) {

325 Register Old = SortedIntervals[I]->reg();

326 unsigned New = SlotMapping[I];

327 if (Old != New)

328 MRI->replaceRegWith(Old, New);

329 }

330 return true;

331}

unsigned const MachineRegisterInfo * MRI

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

Promote Memory to Register

#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)

static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")

This file declares WebAssembly-specific per-machine-function information.

static void undefInvalidDbgValues(const LiveIntervals *Liveness, ArrayRef< SmallVector< LiveInterval *, 4 > > Assignments, DenseMap< Register, std::vector< std::pair< SlotIndex, MachineInstr * > > > &DbgVRegToValues)

Definition WebAssemblyRegColoring.cpp:130

static DenseMap< Register, std::vector< std::pair< SlotIndex, MachineInstr * > > > buildVRegToDbgValueMap(MachineFunction &MF, const LiveIntervals *Liveness)

Definition WebAssemblyRegColoring.cpp:80

static float computeWeight(const MachineRegisterInfo *MRI, const MachineBlockFrequencyInfo *MBFI, unsigned VReg)

Definition WebAssemblyRegColoring.cpp:65

This file contains the entry points for global functions defined in the LLVM WebAssembly back-end.

Class recording the (high level) value of a variable.

Represent the analysis usage information of a pass.

AnalysisUsage & addPreservedID(const void *ID)

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

Add the specified Pass class to the set of analyses preserved by this pass.

LLVM_ABI void setPreservesCFG()

This function should be called by the pass, iff they do not:

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

Implements a dense probed hash-table based set.

FunctionPass class - This class is used to implement most global optimizations.

LiveInterval - This class represents the liveness of a register, or stack slot.

LLVM_ABI void dump() const

void setWeight(float Value)

SlotIndexes * getSlotIndexes() const

static LLVM_ABI float getSpillWeight(bool isDef, bool isUse, const MachineBlockFrequencyInfo *MBFI, const MachineInstr &MI, ProfileSummaryInfo *PSI=nullptr)

Calculate the spill weight to assign to a single instruction.

LiveInterval & getInterval(Register Reg)

MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...

MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

StringRef getName() const

getName - Return the name of the corresponding LLVM function.

bool exposesReturnsTwice() const

exposesReturnsTwice - Returns true if the function calls setjmp or any other similar functions with a...

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

Ty * getInfo()

getInfo - Keep track of various per-function pieces of information for backends that would like to do...

MachineOperand class - Representation of each machine instruction operand.

MachineRegisterInfo - Keep track of information for virtual and physical registers,...

Wrapper class representing virtual and physical registers.

SlotIndex - An opaque wrapper around machine indexes.

SlotIndex getMBBEndIdx(unsigned Num) const

Returns the index past the last valid index in the given basic block.

SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const

Returns the base index for the given instruction.

SlotIndex getMBBStartIdx(unsigned Num) const

Returns the first index in the given basic block number.

void reserve(size_type N)

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

StringRef - Represent a constant reference to a string, i.e.

void setFrameBaseVreg(unsigned Reg)

unsigned getFrameBaseVreg() const

bool isVRegStackified(Register VReg) const

bool isFrameBaseVirtual() const

std::pair< iterator, bool > insert(const ValueT &V)

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

@ C

The default llvm calling convention, compatible with C.

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ABI char & MachineDominatorsID

MachineDominators - This pass is a machine dominators analysis pass.

bool any_of(R &&range, UnaryPredicate P)

Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.

void sort(IteratorTy Start, IteratorTy End)

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

DWARFExpression::Operation Op

FunctionPass * createWebAssemblyRegColoring()

LLVM_ABI Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)

Prints virtual and physical registers with or without a TRI instance.