DeltaTree.cpp Source File (original) (raw)

15#include

16#include

18using namespace llvm;

35namespace {

40struct SourceDelta {

41 unsigned FileLoc;

42 int Delta;

44 static SourceDelta get(unsigned Loc, int D) {

45 SourceDelta Delta;

47 Delta.Delta = D;

48 return Delta;

49 }

50};

54class DeltaTreeNode {

55public:

56 struct InsertResult {

57 DeltaTreeNode *LHS, *RHS;

58 SourceDelta Split;

59 };

61private:

62 friend class DeltaTreeInteriorNode;

68 enum { WidthFactor = 8 };

71 SourceDelta Values[2 * WidthFactor - 1];

75 unsigned char NumValuesUsed = 0;

79 bool IsLeaf;

83 int FullDelta = 0;

85public:

86 DeltaTreeNode(bool isLeaf = true) : IsLeaf(isLeaf) {}

88 bool isLeaf() const { return IsLeaf; }

89 int getFullDelta() const { return FullDelta; }

90 bool isFull() const { return NumValuesUsed == 2 * WidthFactor - 1; }

92 unsigned getNumValuesUsed() const { return NumValuesUsed; }

94 const SourceDelta &getValue(unsigned i) const {

95 assert(i < NumValuesUsed && "Invalid value #");

96 return Values[i];

97 }

99 SourceDelta &getValue(unsigned i) {

100 assert(i < NumValuesUsed && "Invalid value #");

101 return Values[i];

102 }

103

104

105

106

107

108 bool DoInsertion(unsigned FileIndex, int Delta, InsertResult *InsertRes);

109

110 void DoSplit(InsertResult &InsertRes);

111

112

113

114 void RecomputeFullDeltaLocally();

115

116 void Destroy();

117};

118

119

120

121class DeltaTreeInteriorNode : public DeltaTreeNode {

122 friend class DeltaTreeNode;

123

124 DeltaTreeNode *Children[2 * WidthFactor];

125

126 ~DeltaTreeInteriorNode() {

127 for (unsigned i = 0, e = NumValuesUsed + 1; i != e; ++i)

128 Children[i]->Destroy();

129 }

130

131public:

132 DeltaTreeInteriorNode() : DeltaTreeNode(false ) {}

133

134 DeltaTreeInteriorNode(const InsertResult &IR)

135 : DeltaTreeNode(false ) {

136 Children[0] = IR.LHS;

137 Children[1] = IR.RHS;

138 Values[0] = IR.Split;

139 FullDelta =

140 IR.LHS->getFullDelta() + IR.RHS->getFullDelta() + IR.Split.Delta;

141 NumValuesUsed = 1;

142 }

143

144 const DeltaTreeNode *getChild(unsigned i) const {

145 assert(i < getNumValuesUsed() + 1 && "Invalid child");

146 return Children[i];

147 }

148

149 DeltaTreeNode *getChild(unsigned i) {

150 assert(i < getNumValuesUsed() + 1 && "Invalid child");

151 return Children[i];

152 }

153

154 static bool classof(const DeltaTreeNode *N) { return ->isLeaf(); }

155};

156

157}

158

159

160void DeltaTreeNode::Destroy() {

161 if (isLeaf())

162 delete this;

163 else

165}

166

167

168

169void DeltaTreeNode::RecomputeFullDeltaLocally() {

170 int NewFullDelta = 0;

171 for (unsigned i = 0, e = getNumValuesUsed(); i != e; ++i)

172 NewFullDelta += Values[i].Delta;

174 for (unsigned i = 0, e = getNumValuesUsed() + 1; i != e; ++i)

175 NewFullDelta += IN->getChild(i)->getFullDelta();

176 FullDelta = NewFullDelta;

177}

178

179

180

181

182

183bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta,

184 InsertResult *InsertRes) {

185

186 FullDelta += Delta;

187

188

189 unsigned i = 0, e = getNumValuesUsed();

190 while (i != e && FileIndex > getValue(i).FileLoc)

191 ++i;

192

193

194

195 if (i != e && getValue(i).FileLoc == FileIndex) {

196

197

198

199

200 Values[i].Delta += Delta;

201 return false;

202 }

203

204

205

206 if (isLeaf()) {

207 if (!isFull()) {

208

209

210 if (i != e)

211 memmove(&Values[i + 1], &Values[i], sizeof(Values[0]) * (e - i));

212 Values[i] = SourceDelta::get(FileIndex, Delta);

213 ++NumValuesUsed;

214 return false;

215 }

216

217

218

219 assert(InsertRes && "No result location specified");

220 DoSplit(*InsertRes);

221

222 if (InsertRes->Split.FileLoc > FileIndex)

223 InsertRes->LHS->DoInsertion(FileIndex, Delta, nullptr );

224 else

225 InsertRes->RHS->DoInsertion(FileIndex, Delta, nullptr );

226 return true;

227 }

228

229

231 if (!IN->Children[i]->DoInsertion(FileIndex, Delta, InsertRes))

232 return false;

233

234

235

236 if (!isFull()) {

237

238

239

240 if (i != e)

241 memmove(&IN->Children[i + 2], &IN->Children[i + 1],

242 (e - i) * sizeof(IN->Children[0]));

243 IN->Children[i] = InsertRes->LHS;

244 IN->Children[i + 1] = InsertRes->RHS;

245

246 if (e != i)

247 memmove(&Values[i + 1], &Values[i], (e - i) * sizeof(Values[0]));

248 Values[i] = InsertRes->Split;

249 ++NumValuesUsed;

250 return false;

251 }

252

253

254

255

256 IN->Children[i] = InsertRes->LHS;

257 DeltaTreeNode *SubRHS = InsertRes->RHS;

258 SourceDelta SubSplit = InsertRes->Split;

259

260

261 DoSplit(*InsertRes);

262

263

264 DeltaTreeInteriorNode *InsertSide;

265 if (SubSplit.FileLoc < InsertRes->Split.FileLoc)

267 else

269

270

271

272

273

274 i = 0;

275 e = InsertSide->getNumValuesUsed();

276 while (i != e && SubSplit.FileLoc > InsertSide->getValue(i).FileLoc)

277 ++i;

278

279

280

281 if (i != e)

282 memmove(&InsertSide->Children[i + 2], &InsertSide->Children[i + 1],

283 (e - i) * sizeof(IN->Children[0]));

284 InsertSide->Children[i + 1] = SubRHS;

285

286 if (e != i)

287 memmove(&InsertSide->Values[i + 1], &InsertSide->Values[i],

288 (e - i) * sizeof(Values[0]));

289 InsertSide->Values[i] = SubSplit;

290 ++InsertSide->NumValuesUsed;

291 InsertSide->FullDelta += SubSplit.Delta + SubRHS->getFullDelta();

292 return true;

293}

294

295

296

297

298void DeltaTreeNode::DoSplit(InsertResult &InsertRes) {

299 assert(isFull() && "Why split a non-full node?");

300

301

302

303

304

305

306

307 DeltaTreeNode *NewNode;

309

310

311 DeltaTreeInteriorNode *New = new DeltaTreeInteriorNode();

312 memcpy(&New->Children[0], &IN->Children[WidthFactor],

313 WidthFactor * sizeof(IN->Children[0]));

314 NewNode = New;

315 } else {

316

317 NewNode = new DeltaTreeNode();

318 }

319

320

321 memcpy(&NewNode->Values[0], &Values[WidthFactor],

322 (WidthFactor - 1) * sizeof(Values[0]));

323

324

325 NewNode->NumValuesUsed = NumValuesUsed = WidthFactor - 1;

326

327

328 NewNode->RecomputeFullDeltaLocally();

329 RecomputeFullDeltaLocally();

330

331 InsertRes.LHS = this;

332 InsertRes.RHS = NewNode;

333 InsertRes.Split = Values[WidthFactor - 1];

334}

335

336

337

338

339

340

341

342#ifdef VERIFY_TREE

343

344

345static void VerifyTree(const DeltaTreeNode *N) {

347 if (IN == 0) {

348

349

350 int FullDelta = 0;

351 for (unsigned i = 0, e = N->getNumValuesUsed(); i != e; ++i) {

352 if (i)

353 assert(N->getValue(i - 1).FileLoc < N->getValue(i).FileLoc);

354 FullDelta += N->getValue(i).Delta;

355 }

356 assert(FullDelta == N->getFullDelta());

357 return;

358 }

359

360

361

362 int FullDelta = 0;

363 for (unsigned i = 0, e = IN->getNumValuesUsed(); i != e; ++i) {

364 const SourceDelta &IVal = N->getValue(i);

365 const DeltaTreeNode *IChild = IN->getChild(i);

366 if (i)

367 assert(IN->getValue(i - 1).FileLoc < IVal.FileLoc);

368 FullDelta += IVal.Delta;

369 FullDelta += IChild->getFullDelta();

370

371

372 assert(IChild->getValue(IChild->getNumValuesUsed() - 1).FileLoc <

373 IVal.FileLoc);

374

375

376 assert(IN->getChild(i + 1)->getValue(0).FileLoc > IVal.FileLoc);

377 VerifyTree(IChild);

378 }

379

380 FullDelta += IN->getChild(IN->getNumValuesUsed())->getFullDelta();

381

382 assert(FullDelta == N->getFullDelta());

383}

384#endif

385

386static DeltaTreeNode *getRoot(void *Root) { return (DeltaTreeNode *)Root; }

387

389

391

392 assert(getRoot(RHS.Root)->getNumValuesUsed() == 0 &&

393 "Can only copy empty tree");

394 Root = new DeltaTreeNode();

395}

396

398

399

400

401

403 const DeltaTreeNode *Node = getRoot(Root);

404

405 int Result = 0;

406

407

408 while (true) {

409

410

411

412 unsigned NumValsGreater = 0;

413 for (unsigned e = Node->getNumValuesUsed(); NumValsGreater != e;

414 ++NumValsGreater) {

415 const SourceDelta &Val = Node->getValue(NumValsGreater);

416

417 if (Val.FileLoc >= FileIndex)

418 break;

419 Result += Val.Delta;

420 }

421

422

423

425 if (!IN)

426 return Result;

427

428

429

430 for (unsigned i = 0; i != NumValsGreater; ++i)

431 Result += IN->getChild(i)->getFullDelta();

432

433

434

435

436 if (NumValsGreater != Node->getNumValuesUsed() &&

437 Node->getValue(NumValsGreater).FileLoc == FileIndex)

438 return Result + IN->getChild(NumValsGreater)->getFullDelta();

439

440

441

442 Node = IN->getChild(NumValsGreater);

443 }

444

445}

446

447

448

449

451 assert(Delta && "Adding a noop?");

452 DeltaTreeNode *MyRoot = getRoot(Root);

453

454 DeltaTreeNode::InsertResult InsertRes;

455 if (MyRoot->DoInsertion(FileIndex, Delta, &InsertRes)) {

456 Root = new DeltaTreeInteriorNode(InsertRes);

457#ifdef VERIFY_TREE

458 MyRoot = Root;

459#endif

460 }

461

462#ifdef VERIFY_TREE

463 VerifyTree(MyRoot);

464#endif

465}

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

Function Alias Analysis false

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

static DeltaTreeNode * getRoot(void *Root)

Definition DeltaTree.cpp:386

Legalize the Machine IR a function s Machine IR

LLVM_ABI void AddDelta(unsigned FileIndex, int Delta)

AddDelta - When a change is made that shifts around the text buffer, this method is used to record th...

Definition DeltaTree.cpp:450

LLVM_ABI DeltaTree()

Definition DeltaTree.cpp:388

LLVM_ABI int getDeltaAt(unsigned FileIndex) const

getDeltaAt - Return the accumulated delta at the specified file offset.

Definition DeltaTree.cpp:402

LLVM_ABI ~DeltaTree()

Definition DeltaTree.cpp:397

This is an optimization pass for GlobalISel generic memory operations.

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

Struct holding Line:Column location.