lib/Target/JSBackend/Relooper.cpp - Issue 1692803002: Remove Emscripten support

Side by Side Diff: lib/Target/JSBackend/Relooper.cpp

Issue 1692803002: Remove Emscripten support (Closed) Base URL: https://chromium.googlesource.com/a/native_client/pnacl-llvm.git@master

Patch Set: Created 4 years, 10 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

View unified diff | Download patch

OLD	NEW
	(Empty)
1 // We are implementing the Relooper C API, so always export from this file.

2 #ifndef RELOOPERDLL_EXPORTS

3 #define RELOOPERDLL_EXPORTS

4 #endif

5

6 #include "Relooper.h"

7

8 #include <string.h>

9 #include <stdlib.h>

10 #include <list>

11 #include <stack>

12

13 #if EMSCRIPTEN

14 #include "ministring.h"

15 #else

16 #include <string>

17 typedef std::string ministring;

18 #endif

19

20 // uncomment these out to get LLVM errs() debugging support

21 //#include <llvm/Support/raw_ostream.h>

22 //using namespace llvm;

23

24 template <class T, class U> static bool contains(const T& container, const U& co ntained) {

25 return container.count(contained);

26 }

27

28 #if DEBUG

29 static void PrintDebug(const char *Format, ...);

30 #define DebugDump(x, ...) Debugging::Dump(x, __VA_ARGS__)

31 #else

32 #define PrintDebug(x, ...)

33 #define DebugDump(x, ...)

34 #endif

35

36 #define INDENTATION 1

37

38 struct Indenter {

39 static int CurrIndent;

40

41 static void Indent() { CurrIndent++; }

42 static void Unindent() { CurrIndent--; }

43 };

44

45 static void PrintIndented(const char *Format, ...);

46 static void PutIndented(const char *String);

47

48 static char *OutputBufferRoot = NULL;

49 static char *OutputBuffer = NULL;

50 static int OutputBufferSize = 0;

51 static int OutputBufferOwned = false;

52

53 static int LeftInOutputBuffer() {

54 return OutputBufferSize - (OutputBuffer - OutputBufferRoot);

55 }

56

57 static bool EnsureOutputBuffer(int Needed) { // ensures the output buffer is suf ficient. returns true is no problem happened

58 Needed++; // ensure the trailing \0 is not forgotten

59 int Left = LeftInOutputBuffer();

60 if (!OutputBufferOwned) {

61 assert(Needed < Left);

62 } else {

63 // we own the buffer, and can resize if necessary

64 if (Needed >= Left) {

65 int Offset = OutputBuffer - OutputBufferRoot;

66 int TotalNeeded = OutputBufferSize + Needed - Left + 10240;

67 int NewSize = OutputBufferSize;

68 while (NewSize < TotalNeeded) NewSize = NewSize + (NewSize/2);

69 //printf("resize %d => %d\n", OutputBufferSize, NewSize);

70 OutputBufferRoot = (char*)realloc(OutputBufferRoot, NewSize);

71 assert(OutputBufferRoot);

72 OutputBuffer = OutputBufferRoot + Offset;

73 OutputBufferSize = NewSize;

74 return false;

75 }

76 }

77 return true;

78 }

79

80 void PrintIndented(const char *Format, ...) {

81 assert(OutputBuffer);

82 EnsureOutputBuffer(Indenter::CurrIndent*INDENTATION);

83 for (int i = 0; i < Indenter::CurrIndentINDENTATION; i++, OutputBuffer++) Ou tputBuffer = ' ';

84 int Written;

85 while (1) { // write and potentially resize buffer until we have enough room

86 int Left = LeftInOutputBuffer();

87 va_list Args;

88 va_start(Args, Format);

89 Written = vsnprintf(OutputBuffer, Left, Format, Args);

90 va_end(Args);

91 #ifdef _MSC_VER

92 // VC CRT specific: vsnprintf returns -1 on failure, other runtimes return t he number of characters that would have been

93 // written. On VC, if we get -1, count the number of characters manually.

94 if (Written < 0) {

95 va_start(Args, Format);

96 Written = _vscprintf(Format, Args);

97 va_end(Args);

98 }

99 #endif

100

101 if (EnsureOutputBuffer(Written)) break;

102 }

103 OutputBuffer += Written;

104 }

105

106 void PutIndented(const char *String) {

107 assert(OutputBuffer);

108 EnsureOutputBuffer(Indenter::CurrIndent*INDENTATION);

109 for (int i = 0; i < Indenter::CurrIndentINDENTATION; i++, OutputBuffer++) Ou tputBuffer = ' ';

110 int Needed = strlen(String)+1;

111 EnsureOutputBuffer(Needed);

112 strcpy(OutputBuffer, String);

113 OutputBuffer += strlen(String);

114 *OutputBuffer++ = '\n';

115 *OutputBuffer = 0;

116 }

117

118 static int AsmJS = 0;

119

120 // Indenter

121

122 int Indenter::CurrIndent = 1;

123

124 // Branch

125

126 Branch::Branch(const char ConditionInit, const char CodeInit) : Ancestor(NULL) , Labeled(true) {

127 Condition = ConditionInit ? strdup(ConditionInit) : NULL;

128 Code = CodeInit ? strdup(CodeInit) : NULL;

129 }

130

131 Branch::~Branch() {

132 if (Condition) free((void*)Condition);

133 if (Code) free((void*)Code);

134 }

135

136 void Branch::Render(Block *Target, bool SetLabel) {

137 if (Code) PrintIndented("%s\n", Code);

138 if (SetLabel) PrintIndented("label = %d;\n", Target->Id);

139 if (Ancestor) {

140 if (Type == Break \|\| Type == Continue) {

141 if (Labeled) {

142 PrintIndented("%s L%d;\n", Type == Break ? "break" : "continue", Ancesto r->Id);

143 } else {

144 PrintIndented("%s;\n", Type == Break ? "break" : "continue");

145 }

146 }

147 }

148 }

149

150 // Block

151

152 Block::Block(const char CodeInit, const char BranchVarInit) : Parent(NULL), Id (-1), IsCheckedMultipleEntry(false) {

153 Code = strdup(CodeInit);

154 BranchVar = BranchVarInit ? strdup(BranchVarInit) : NULL;

155 }

156

157 Block::~Block() {

158 if (Code) free((void*)Code);

159 if (BranchVar) free((void*)BranchVar);

160 for (BlockBranchMap::iterator iter = ProcessedBranchesOut.begin(); iter != Pro cessedBranchesOut.end(); iter++) {

161 delete iter->second;

162 }

163 // XXX If not reachable, expected to have branches here. But need to clean the m up to prevent leaks!

164 }

165

166 void Block::AddBranchTo(Block Target, const char Condition, const char *Code) {

167 assert(!contains(BranchesOut, Target)); // cannot add more than one branch to the same target

168 BranchesOut[Target] = new Branch(Condition, Code);

169 }

170

171 void Block::Render(bool InLoop) {

172 if (IsCheckedMultipleEntry && InLoop) {

173 PrintIndented("label = 0;\n");

174 }

175

176 if (Code) {

177 // Print code in an indented manner, even over multiple lines

178 char Start = const_cast<char>(Code);

179 while (*Start) {

180 char *End = strchr(Start, '\n');

181 if (End) *End = 0;

182 PutIndented(Start);

183 if (End) *End = '\n'; else break;

184 Start = End+1;

185 }

186 }

187

188 if (!ProcessedBranchesOut.size()) return;

189

190 bool SetLabel = true; // in some cases it is clear we can avoid setting label, see later

191 bool ForceSetLabel = Shape::IsEmulated(Parent);

192

193 // A setting of the label variable (label = x) is necessary if it can

194 // cause an impact. The main case is where we set label to x, then elsewhere

195 // we check if label is equal to that value, i.e., that label is an entry

196 // in a multiple block. We also need to reset the label when we enter

197 // that block, so that each setting is a one-time action: consider

198 //

199 // while (1) {

200 // if (check) label = 1;

201 // if (label == 1) { label = 0 }

202 // }

203 //

204 // (Note that this case is impossible due to fusing, but that is not

205 // material here.) So setting to 0 is important just to clear the 1 for

206 // future iterations.

207 // TODO: When inside a loop, if necessary clear the label variable

208 // once on the top, and never do settings that are in effect clears

209

210 // Fusing: If the next is a Multiple, we can fuse it with this block. Note

211 // that we must be the Inner of a Simple, so fusing means joining a Simple

212 // to a Multiple. What happens there is that all options in the Multiple

213 // must appear in the Simple (the Simple is the only one reaching the

214 // Multiple), so we can remove the Multiple and add its independent groups

215 // into the Simple's branches.

216 MultipleShape *Fused = Shape::IsMultiple(Parent->Next);

217 if (Fused) {

218 PrintDebug("Fusing Multiple to Simple\n", 0);

219 Parent->Next = Parent->Next->Next;

220 Fused->UseSwitch = false; // TODO: emit switches here

221 Fused->RenderLoopPrefix();

222

223 // When the Multiple has the same number of groups as we have branches,

224 // they will all be fused, so it is safe to not set the label at all

225 if (SetLabel && Fused->InnerMap.size() == ProcessedBranchesOut.size()) {

226 SetLabel = false;

227 }

228 }

229

230 Block *DefaultTarget(NULL); // The block we branch to without checking the con dition, if none of the other conditions held.

231

232 // Find the default target, the one without a condition

233 for (BlockBranchMap::iterator iter = ProcessedBranchesOut.begin(); iter != Pro cessedBranchesOut.end(); iter++) {

234 if (!iter->second->Condition) {

235 assert(!DefaultTarget); // Must be exactly one default

236 DefaultTarget = iter->first;

237 }

238 }

239 assert(DefaultTarget); // Since each block must branch somewhere, this must be set

240

241 bool useSwitch = BranchVar != NULL;

242

243 if (useSwitch) {

244 PrintIndented("switch (%s) {\n", BranchVar);

245 }

246

247 ministring RemainingConditions;

248 bool First = !useSwitch; // when using a switch, there is no special first

249 for (BlockBranchMap::iterator iter = ProcessedBranchesOut.begin();; iter++) {

250 Block *Target;

251 Branch *Details;

252 if (iter != ProcessedBranchesOut.end()) {

253 Target = iter->first;

254 if (Target == DefaultTarget) continue; // done at the end

255 Details = iter->second;

256 assert(Details->Condition); // must have a condition if this is not the de fault target

257 } else {

258 Target = DefaultTarget;

259 Details = ProcessedBranchesOut[DefaultTarget];

260 }

261 bool SetCurrLabel = (SetLabel && Target->IsCheckedMultipleEntry) \|\| ForceSet Label;

262 bool HasFusedContent = Fused && contains(Fused->InnerMap, Target->Id);

263 bool HasContent = SetCurrLabel \|\| Details->Type != Branch::Direct \|\| HasFuse dContent \|\| Details->Code;

264 if (iter != ProcessedBranchesOut.end()) {

265 // If there is nothing to show in this branch, omit the condition

266 if (useSwitch) {

267 PrintIndented("%s {\n", Details->Condition);

268 } else {

269 if (HasContent) {

270 PrintIndented("%sif (%s) {\n", First ? "" : "} else ", Details->Condit ion);

271 First = false;

272 } else {

273 if (RemainingConditions.size() > 0) RemainingConditions += " && ";

274 RemainingConditions += "!(";

275 if (BranchVar) {

276 RemainingConditions += BranchVar;

277 RemainingConditions += " == ";

278 }

279 RemainingConditions += Details->Condition;

280 RemainingConditions += ")";

281 }

282 }

283 } else {

284 // this is the default

285 if (useSwitch) {

286 PrintIndented("default: {\n");

287 } else {

288 if (HasContent) {

289 if (RemainingConditions.size() > 0) {

290 if (First) {

291 PrintIndented("if (%s) {\n", RemainingConditions.c_str());

292 First = false;

293 } else {

294 PrintIndented("} else if (%s) {\n", RemainingConditions.c_str());

295 }

296 } else if (!First) {

297 PrintIndented("} else {\n");

298 }

299 }

300 }

301 }

302 if (!First) Indenter::Indent();

303 Details->Render(Target, SetCurrLabel);

304 if (HasFusedContent) {

305 Fused->InnerMap.find(Target->Id)->second->Render(InLoop);

306 } else if (Details->Type == Branch::Nested) {

307 // Nest the parent content here, and remove it from showing up afterwards as Next

308 assert(Parent->Next);

309 Parent->Next->Render(InLoop);

310 Parent->Next = NULL;

311 }

312 if (useSwitch && iter != ProcessedBranchesOut.end()) {

313 PrintIndented("break;\n");

314 }

315 if (!First) Indenter::Unindent();

316 if (useSwitch) {

317 PrintIndented("}\n");

318 }

319 if (iter == ProcessedBranchesOut.end()) break;

320 }

321 if (!First) PrintIndented("}\n");

322

323 if (Fused) {

324 Fused->RenderLoopPostfix();

325 }

326 }

327

328 // MultipleShape

329

330 void MultipleShape::RenderLoopPrefix() {

331 if (Breaks) {

332 if (UseSwitch) {

333 if (Labeled) {

334 PrintIndented("L%d: ", Id);

335 }

336 } else {

337 if (Labeled) {

338 PrintIndented("L%d: do {\n", Id);

339 } else {

340 PrintIndented("do {\n");

341 }

342 Indenter::Indent();

343 }

344 }

345 }

346

347 void MultipleShape::RenderLoopPostfix() {

348 if (Breaks && !UseSwitch) {

349 Indenter::Unindent();

350 PrintIndented("} while(0);\n");

351 }

352 }

353

354 void MultipleShape::Render(bool InLoop) {

355 RenderLoopPrefix();

356

357 if (!UseSwitch) {

358 // emit an if-else chain

359 bool First = true;

360 for (IdShapeMap::iterator iter = InnerMap.begin(); iter != InnerMap.end(); i ter++) {

361 if (AsmJS) {

362 PrintIndented("%sif ((label\|0) == %d) {\n", First ? "" : "else ", iter-> first);

363 } else {

364 PrintIndented("%sif (label == %d) {\n", First ? "" : "else ", iter->firs t);

365 }

366 First = false;

367 Indenter::Indent();

368 iter->second->Render(InLoop);

369 Indenter::Unindent();

370 PrintIndented("}\n");

371 }

372 } else {

373 // emit a switch

374 if (AsmJS) {

375 PrintIndented("switch (label\|0) {\n");

376 } else {

377 PrintIndented("switch (label) {\n");

378 }

379 Indenter::Indent();

380 for (IdShapeMap::iterator iter = InnerMap.begin(); iter != InnerMap.end(); i ter++) {

381 PrintIndented("case %d: {\n", iter->first);

382 Indenter::Indent();

383 iter->second->Render(InLoop);

384 PrintIndented("break;\n");

385 Indenter::Unindent();

386 PrintIndented("}\n");

387 }

388 Indenter::Unindent();

389 PrintIndented("}\n");

390 }

391

392 RenderLoopPostfix();

393 if (Next) Next->Render(InLoop);

394 }

395

396 // LoopShape

397

398 void LoopShape::Render(bool InLoop) {

399 if (Labeled) {

400 PrintIndented("L%d: while(1) {\n", Id);

401 } else {

402 PrintIndented("while(1) {\n");

403 }

404 Indenter::Indent();

405 Inner->Render(true);

406 Indenter::Unindent();

407 PrintIndented("}\n");

408 if (Next) Next->Render(InLoop);

409 }

410

411 // EmulatedShape

412

413 void EmulatedShape::Render(bool InLoop) {

414 PrintIndented("label = %d;\n", Entry->Id);

415 if (Labeled) {

416 PrintIndented("L%d: ", Id);

417 }

418 PrintIndented("while(1) {\n");

419 Indenter::Indent();

420 PrintIndented("switch(label\|0) {\n");

421 Indenter::Indent();

422 for (BlockSet::iterator iter = Blocks.begin(); iter != Blocks.end(); iter++) {

423 Block Curr = iter;

424 PrintIndented("case %d: {\n", Curr->Id);

425 Indenter::Indent();

426 Curr->Render(InLoop);

427 PrintIndented("break;\n");

428 Indenter::Unindent();

429 PrintIndented("}\n");

430 }

431 Indenter::Unindent();

432 PrintIndented("}\n");

433 Indenter::Unindent();

434 PrintIndented("}\n");

435 if (Next) Next->Render(InLoop);

436 }

437

438 // Relooper

439

440 Relooper::Relooper() : Root(NULL), Emulate(false), MinSize(false), BlockIdCounte r(1), ShapeIdCounter(0) { // block ID 0 is reserved for clearings

441 }

442

443 Relooper::~Relooper() {

444 for (unsigned i = 0; i < Blocks.size(); i++) delete Blocks[i];

445 for (unsigned i = 0; i < Shapes.size(); i++) delete Shapes[i];

446 }

447

448 void Relooper::AddBlock(Block *New, int Id) {

449 New->Id = Id == -1 ? BlockIdCounter++ : Id;

450 Blocks.push_back(New);

451 }

452

453 struct RelooperRecursor {

454 Relooper *Parent;

455 RelooperRecursor(Relooper *ParentInit) : Parent(ParentInit) {}

456 };

457

458 typedef std::list<Block*> BlockList;

459

460 void Relooper::Calculate(Block *Entry) {

461 // Scan and optimize the input

462 struct PreOptimizer : public RelooperRecursor {

463 PreOptimizer(Relooper *Parent) : RelooperRecursor(Parent) {}

464 BlockSet Live;

465

466 void FindLive(Block *Root) {

467 BlockList ToInvestigate;

468 ToInvestigate.push_back(Root);

469 while (ToInvestigate.size() > 0) {

470 Block *Curr = ToInvestigate.front();

471 ToInvestigate.pop_front();

472 if (contains(Live, Curr)) continue;

473 Live.insert(Curr);

474 for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) {

475 ToInvestigate.push_back(iter->first);

476 }

477 }

478 }

479

480 // If a block has multiple entries but no exits, and it is small enough, it is useful to split it.

481 // A common example is a C++ function where everything ends up at a final ex it block and does some

482 // RAII cleanup. Without splitting, we will be forced to introduce labelled loops to allow

483 // reaching the final block

484 void SplitDeadEnds() {

485 unsigned TotalCodeSize = 0;

486 for (BlockSet::iterator iter = Live.begin(); iter != Live.end(); iter++) {

487 Block Curr = iter;

488 TotalCodeSize += strlen(Curr->Code);

489 }

490 BlockSet Splits;

491 BlockSet Removed;

492 //DebugDump(Live, "before");

493 for (BlockSet::iterator iter = Live.begin(); iter != Live.end(); iter++) {

494 Block Original = iter;

495 if (Original->BranchesIn.size() <= 1 \|\| Original->BranchesOut.size() > 0 ) continue; // only dead ends, for now

496 if (contains(Original->BranchesOut, Original)) continue; // cannot split a looping node

497 if (strlen(Original->Code)*(Original->BranchesIn.size()-1) > TotalCodeSi ze/5) continue; // if splitting increases raw code size by a significant amount, abort

498 // Split the node (for simplicity, we replace all the blocks, even thoug h we could have reused the original)

499 PrintDebug("Splitting block %d\n", Original->Id);

500 for (BlockSet::iterator iter = Original->BranchesIn.begin(); iter != Ori ginal->BranchesIn.end(); iter++) {

501 Block Prior = iter;

502 Block *Split = new Block(Original->Code, Original->BranchVar);

503 Parent->AddBlock(Split, Original->Id);

504 Split->BranchesIn.insert(Prior);

505 Branch *Details = Prior->BranchesOut[Original];

506 Prior->BranchesOut[Split] = new Branch(Details->Condition, Details->Co de);

507 Prior->BranchesOut.erase(Original);

508 for (BlockBranchMap::iterator iter = Original->BranchesOut.begin(); it er != Original->BranchesOut.end(); iter++) {

509 Block *Post = iter->first;

510 Branch *Details = iter->second;

511 Split->BranchesOut[Post] = new Branch(Details->Condition, Details->C ode);

512 Post->BranchesIn.insert(Split);

513 }

514 Splits.insert(Split);

515 Removed.insert(Original);

516 }

517 for (BlockBranchMap::iterator iter = Original->BranchesOut.begin(); iter != Original->BranchesOut.end(); iter++) {

518 Block *Post = iter->first;

519 Post->BranchesIn.erase(Original);

520 }

521 //DebugDump(Live, "mid");

522 }

523 for (BlockSet::iterator iter = Splits.begin(); iter != Splits.end(); iter+ +) {

524 Live.insert(*iter);

525 }

526 for (BlockSet::iterator iter = Removed.begin(); iter != Removed.end(); ite r++) {

527 Live.erase(*iter);

528 }

529 //DebugDump(Live, "after");

530 }

531 };

532 PreOptimizer Pre(this);

533 Pre.FindLive(Entry);

534

535 // Add incoming branches from live blocks, ignoring dead code

536 for (unsigned i = 0; i < Blocks.size(); i++) {

537 Block *Curr = Blocks[i];

538 if (!contains(Pre.Live, Curr)) continue;

539 for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr ->BranchesOut.end(); iter++) {

540 iter->first->BranchesIn.insert(Curr);

541 }

542 }

543

544 if (!Emulate && !MinSize) Pre.SplitDeadEnds();

545

546 // Recursively process the graph

547

548 struct Analyzer : public RelooperRecursor {

549 Analyzer(Relooper *Parent) : RelooperRecursor(Parent) {}

550

551 // Add a shape to the list of shapes in this Relooper calculation

552 void Notice(Shape *New) {

553 New->Id = Parent->ShapeIdCounter++;

554 Parent->Shapes.push_back(New);

555 }

556

557 // Create a list of entries from a block. If LimitTo is provided, only resul ts in that set

558 // will appear

559 void GetBlocksOut(Block Source, BlockSet& Entries, BlockSet LimitTo=NULL) {

560 for (BlockBranchMap::iterator iter = Source->BranchesOut.begin(); iter != Source->BranchesOut.end(); iter++) {

561 if (!LimitTo \|\| contains(*LimitTo, iter->first)) {

562 Entries.insert(iter->first);

563 }

564 }

565 }

566

567 // Converts/processes all branchings to a specific target

568 void Solipsize(Block Target, Branch::FlowType Type, Shape Ancestor, BlockS et &From) {

569 PrintDebug("Solipsizing branches into %d\n", Target->Id);

570 DebugDump(From, " relevant to solipsize: ");

571 for (BlockSet::iterator iter = Target->BranchesIn.begin(); iter != Target- >BranchesIn.end();) {

572 Block Prior = iter;

573 if (!contains(From, Prior)) {

574 iter++;

575 continue;

576 }

577 Branch *PriorOut = Prior->BranchesOut[Target];

578 PriorOut->Ancestor = Ancestor;

579 PriorOut->Type = Type;

580 if (MultipleShape *Multiple = Shape::IsMultiple(Ancestor)) {

581 Multiple->Breaks++; // We are breaking out of this Multiple, so need a loop

582 }

583 iter++; // carefully increment iter before erasing

584 Target->BranchesIn.erase(Prior);

585 Target->ProcessedBranchesIn.insert(Prior);

586 Prior->BranchesOut.erase(Target);

587 Prior->ProcessedBranchesOut[Target] = PriorOut;

588 PrintDebug(" eliminated branch from %d\n", Prior->Id);

589 }

590 }

591

592 Shape MakeSimple(BlockSet &Blocks, Block Inner, BlockSet &NextEntries) {

593 PrintDebug("creating simple block with block #%d\n", Inner->Id);

594 SimpleShape *Simple = new SimpleShape;

595 Notice(Simple);

596 Simple->Inner = Inner;

597 Inner->Parent = Simple;

598 if (Blocks.size() > 1) {

599 Blocks.erase(Inner);

600 GetBlocksOut(Inner, NextEntries, &Blocks);

601 BlockSet JustInner;

602 JustInner.insert(Inner);

603 for (BlockSet::iterator iter = NextEntries.begin(); iter != NextEntries. end(); iter++) {

604 Solipsize(*iter, Branch::Direct, Simple, JustInner);

605 }

606 }

607 return Simple;

608 }

609

610 Shape MakeEmulated(BlockSet &Blocks, Block Entry, BlockSet &NextEntries) {

611 PrintDebug("creating emulated block with entry #%d and everything it can r each, %d blocks\n", Entry->Id, Blocks.size());

612 EmulatedShape *Emulated = new EmulatedShape;

613 Notice(Emulated);

614 Emulated->Entry = Entry;

615 for (BlockSet::iterator iter = Blocks.begin(); iter != Blocks.end(); iter+ +) {

616 Block Curr = iter;

617 Emulated->Blocks.insert(Curr);

618 Curr->Parent = Emulated;

619 Solipsize(Curr, Branch::Continue, Emulated, Blocks);

620 }

621 Blocks.clear();

622 return Emulated;

623 }

624

625 Shape *MakeLoop(BlockSet &Blocks, BlockSet& Entries, BlockSet &NextEntries) {

626 // Find the inner blocks in this loop. Proceed backwards from the entries until

627 // you reach a seen block, collecting as you go.

628 BlockSet InnerBlocks;

629 BlockSet Queue = Entries;

630 while (Queue.size() > 0) {

631 Block Curr = (Queue.begin());

632 Queue.erase(Queue.begin());

633 if (!contains(InnerBlocks, Curr)) {

634 // This element is new, mark it as inner and remove from outer

635 InnerBlocks.insert(Curr);

636 Blocks.erase(Curr);

637 // Add the elements prior to it

638 for (BlockSet::iterator iter = Curr->BranchesIn.begin(); iter != Curr- >BranchesIn.end(); iter++) {

639 Queue.insert(*iter);

640 }

641 #if 0

642 // Add elements it leads to, if they are dead ends. There is no reason not to hoist dead ends

643 // into loops, as it can avoid multiple entries after the loop

644 for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter ! = Curr->BranchesOut.end(); iter++) {

645 Block *Target = iter->first;

646 if (Target->BranchesIn.size() <= 1 && Target->BranchesOut.size() == 0) {

647 Queue.insert(Target);

648 }

649 }

650 #endif

651 }

652 }

653 assert(InnerBlocks.size() > 0);

654

655 for (BlockSet::iterator iter = InnerBlocks.begin(); iter != InnerBlocks.en d(); iter++) {

656 Block Curr = iter;

657 for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) {

658 Block *Possible = iter->first;

659 if (!contains(InnerBlocks, Possible)) {

660 NextEntries.insert(Possible);

661 }

662 }

663 }

664

665 #if 0

666 // We can avoid multiple next entries by hoisting them into the loop.

667 if (NextEntries.size() > 1) {

668 BlockBlockSetMap IndependentGroups;

669 FindIndependentGroups(NextEntries, IndependentGroups, &InnerBlocks);

670

671 while (IndependentGroups.size() > 0 && NextEntries.size() > 1) {

672 Block *Min = NULL;

673 int MinSize = 0;

674 for (BlockBlockSetMap::iterator iter = IndependentGroups.begin(); iter != IndependentGroups.end(); iter++) {

675 Block *Entry = iter->first;

676 BlockSet &Blocks = iter->second;

677 if (!Min \|\| Blocks.size() < MinSize) { // TODO: code size, not # of blocks

678 Min = Entry;

679 MinSize = Blocks.size();

680 }

681 }

682 // check how many new entries this would cause

683 BlockSet &Hoisted = IndependentGroups[Min];

684 bool abort = false;

685 for (BlockSet::iterator iter = Hoisted.begin(); iter != Hoisted.end() && !abort; iter++) {

686 Block Curr = iter;

687 for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) {

688 Block *Target = iter->first;

689 if (!contains(Hoisted, Target) && !contains(NextEntries, Target)) {

690 // abort this hoisting

691 abort = true;

692 break;

693 }

694 }

695 }

696 if (abort) {

697 IndependentGroups.erase(Min);

698 continue;

699 }

700 // hoist this entry

701 PrintDebug("hoisting %d into loop\n", Min->Id);

702 NextEntries.erase(Min);

703 for (BlockSet::iterator iter = Hoisted.begin(); iter != Hoisted.end(); iter++) {

704 Block Curr = iter;

705 InnerBlocks.insert(Curr);

706 Blocks.erase(Curr);

707 }

708 IndependentGroups.erase(Min);

709 }

710 }

711 #endif

712

713 PrintDebug("creating loop block:\n", 0);

714 DebugDump(InnerBlocks, " inner blocks:");

715 DebugDump(Entries, " inner entries:");

716 DebugDump(Blocks, " outer blocks:");

717 DebugDump(NextEntries, " outer entries:");

718

719 LoopShape *Loop = new LoopShape();

720 Notice(Loop);

721

722 // Solipsize the loop, replacing with break/continue and marking branches as Processed (will not affect later calculations)

723 // A. Branches to the loop entries become a continue to this shape

724 for (BlockSet::iterator iter = Entries.begin(); iter != Entries.end(); ite r++) {

725 Solipsize(*iter, Branch::Continue, Loop, InnerBlocks);

726 }

727 // B. Branches to outside the loop (a next entry) become breaks on this sh ape

728 for (BlockSet::iterator iter = NextEntries.begin(); iter != NextEntries.en d(); iter++) {

729 Solipsize(*iter, Branch::Break, Loop, InnerBlocks);

730 }

731 // Finish up

732 Shape *Inner = Process(InnerBlocks, Entries, NULL);

733 Loop->Inner = Inner;

734 return Loop;

735 }

736

737 // For each entry, find the independent group reachable by it. The independe nt group is

738 // the entry itself, plus all the blocks it can reach that cannot be directl y reached by another entry. Note that we

739 // ignore directly reaching the entry itself by another entry.

740 // @param Ignore - previous blocks that are irrelevant

741 void FindIndependentGroups(BlockSet &Entries, BlockBlockSetMap& IndependentG roups, BlockSet *Ignore=NULL) {

742 typedef std::map<Block, Block> BlockBlockMap;

743

744 struct HelperClass {

745 BlockBlockSetMap& IndependentGroups;

746 BlockBlockMap Ownership; // For each block, which entry it belongs to. W e have reached it from there.

747

748 HelperClass(BlockBlockSetMap& IndependentGroupsInit) : IndependentGroups (IndependentGroupsInit) {}

749 void InvalidateWithChildren(Block *New) { // TODO: rename New

750 BlockList ToInvalidate; // Being in the list means you need to be inva lidated

751 ToInvalidate.push_back(New);

752 while (ToInvalidate.size() > 0) {

753 Block *Invalidatee = ToInvalidate.front();

754 ToInvalidate.pop_front();

755 Block *Owner = Ownership[Invalidatee];

756 if (contains(IndependentGroups, Owner)) { // Owner may have been inv alidated, do not add to IndependentGroups!

757 IndependentGroups[Owner].erase(Invalidatee);

758 }

759 if (Ownership[Invalidatee]) { // may have been seen before and inval idated already

760 Ownership[Invalidatee] = NULL;

761 for (BlockBranchMap::iterator iter = Invalidatee->BranchesOut.begi n(); iter != Invalidatee->BranchesOut.end(); iter++) {

762 Block *Target = iter->first;

763 BlockBlockMap::iterator Known = Ownership.find(Target);

764 if (Known != Ownership.end()) {

765 Block *TargetOwner = Known->second;

766 if (TargetOwner) {

767 ToInvalidate.push_back(Target);

768 }

769 }

770 }

771 }

772 }

773 }

774 };

775 HelperClass Helper(IndependentGroups);

776

777 // We flow out from each of the entries, simultaneously.

778 // When we reach a new block, we add it as belonging to the one we got to it from.

779 // If we reach a new block that is already marked as belonging to someone, it is reachable by

780 // two entries and is not valid for any of them. Remove it and all it can reach that have been

781 // visited.

782

783 BlockList Queue; // Being in the queue means we just added this item, and we need to add its children

784 for (BlockSet::iterator iter = Entries.begin(); iter != Entries.end(); ite r++) {

785 Block Entry = iter;

786 Helper.Ownership[Entry] = Entry;

787 IndependentGroups[Entry].insert(Entry);

788 Queue.push_back(Entry);

789 }

790 while (Queue.size() > 0) {

791 Block *Curr = Queue.front();

792 Queue.pop_front();

793 Block *Owner = Helper.Ownership[Curr]; // Curr must be in the ownership map if we are in the queue

794 if (!Owner) continue; // we have been invalidated meanwhile after being reached from two entries

795 // Add all children

796 for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) {

797 Block *New = iter->first;

798 BlockBlockMap::iterator Known = Helper.Ownership.find(New);

799 if (Known == Helper.Ownership.end()) {

800 // New node. Add it, and put it in the queue

801 Helper.Ownership[New] = Owner;

802 IndependentGroups[Owner].insert(New);

803 Queue.push_back(New);

804 continue;

805 }

806 Block *NewOwner = Known->second;

807 if (!NewOwner) continue; // We reached an invalidated node

808 if (NewOwner != Owner) {

809 // Invalidate this and all reachable that we have seen - we reached this from two locations

810 Helper.InvalidateWithChildren(New);

811 }

812 // otherwise, we have the same owner, so do nothing

813 }

814 }

815

816 // Having processed all the interesting blocks, we remain with just one po tential issue:

817 // If a->b, and a was invalidated, but then b was later reached by someone else, we must

818 // invalidate b. To check for this, we go over all elements in the indepen dent groups,

819 // if an element has a parent which does not have the same owner, we mus t remove it

820 // and all its children.

821

822 for (BlockSet::iterator iter = Entries.begin(); iter != Entries.end(); ite r++) {

823 BlockSet &CurrGroup = IndependentGroups[*iter];

824 BlockList ToInvalidate;

825 for (BlockSet::iterator iter = CurrGroup.begin(); iter != CurrGroup.end( ); iter++) {

826 Block Child = iter;

827 for (BlockSet::iterator iter = Child->BranchesIn.begin(); iter != Chil d->BranchesIn.end(); iter++) {

828 Block Parent = iter;

829 if (Ignore && contains(*Ignore, Parent)) continue;

830 if (Helper.Ownership[Parent] != Helper.Ownership[Child]) {

831 ToInvalidate.push_back(Child);

832 }

833 }

834 }

835 while (ToInvalidate.size() > 0) {

836 Block *Invalidatee = ToInvalidate.front();

837 ToInvalidate.pop_front();

838 Helper.InvalidateWithChildren(Invalidatee);

839 }

840 }

841

842 // Remove empty groups

843 for (BlockSet::iterator iter = Entries.begin(); iter != Entries.end(); ite r++) {

844 if (IndependentGroups[*iter].size() == 0) {

845 IndependentGroups.erase(*iter);

846 }

847 }

848

849 #if DEBUG

850 PrintDebug("Investigated independent groups:\n");

851 for (BlockBlockSetMap::iterator iter = IndependentGroups.begin(); iter != IndependentGroups.end(); iter++) {

852 DebugDump(iter->second, " group: ");

853 }

854 #endif

855 }

856

857 Shape MakeMultiple(BlockSet &Blocks, BlockSet& Entries, BlockBlockSetMap& I ndependentGroups, Shape Prev, BlockSet &NextEntries) {

858 PrintDebug("creating multiple block with %d inner groups\n", IndependentGr oups.size());

859 bool Fused = !!(Shape::IsSimple(Prev));

860 MultipleShape *Multiple = new MultipleShape();

861 Notice(Multiple);

862 BlockSet CurrEntries;

863 for (BlockBlockSetMap::iterator iter = IndependentGroups.begin(); iter != IndependentGroups.end(); iter++) {

864 Block *CurrEntry = iter->first;

865 BlockSet &CurrBlocks = iter->second;

866 PrintDebug(" multiple group with entry %d:\n", CurrEntry->Id);

867 DebugDump(CurrBlocks, " ");

868 // Create inner block

869 CurrEntries.clear();

870 CurrEntries.insert(CurrEntry);

871 for (BlockSet::iterator iter = CurrBlocks.begin(); iter != CurrBlocks.en d(); iter++) {

872 Block CurrInner = iter;

873 // Remove the block from the remaining blocks

874 Blocks.erase(CurrInner);

875 // Find new next entries and fix branches to them

876 for (BlockBranchMap::iterator iter = CurrInner->BranchesOut.begin(); i ter != CurrInner->BranchesOut.end();) {

877 Block *CurrTarget = iter->first;

878 BlockBranchMap::iterator Next = iter;

879 Next++;

880 if (!contains(CurrBlocks, CurrTarget)) {

881 NextEntries.insert(CurrTarget);

882 Solipsize(CurrTarget, Branch::Break, Multiple, CurrBlocks);

883 }

884 iter = Next; // increment carefully because Solipsize can remove us

885 }

886 }

887 Multiple->InnerMap[CurrEntry->Id] = Process(CurrBlocks, CurrEntries, NUL L);

888 // If we are not fused, then our entries will actually be checked

889 if (!Fused) {

890 CurrEntry->IsCheckedMultipleEntry = true;

891 }

892 }

893 DebugDump(Blocks, " remaining blocks after multiple:");

894 // Add entries not handled as next entries, they are deferred

895 for (BlockSet::iterator iter = Entries.begin(); iter != Entries.end(); ite r++) {

896 Block Entry = iter;

897 if (!contains(IndependentGroups, Entry)) {

898 NextEntries.insert(Entry);

899 }

900 }

901 // The multiple has been created, we can decide how to implement it

902 if (Multiple->InnerMap.size() >= 10) {

903 Multiple->UseSwitch = true;

904 Multiple->Breaks++; // switch captures breaks

905 }

906 return Multiple;

907 }

908

909 // Main function.

910 // Process a set of blocks with specified entries, returns a shape

911 // The Make* functions receive a NextEntries. If they fill it with data, tho se are the entries for the

912 // ->Next block on them, and the blocks are what remains in Blocks (which Make* modify). In this way

913 // we avoid recursing on Next (imagine a long chain of Simples, if we recu rsed we could blow the stack).

914 Shape Process(BlockSet &Blocks, BlockSet& InitialEntries, Shape Prev) {

915 PrintDebug("Process() called\n", 0);

916 BlockSet *Entries = &InitialEntries;

917 BlockSet TempEntries[2];

918 int CurrTempIndex = 0;

919 BlockSet *NextEntries;

920 Shape *Ret = NULL;

921 #define Make(call) \

922 Shape *Temp = call; \

923 if (Prev) Prev->Next = Temp; \

924 if (!Ret) Ret = Temp; \

925 if (!NextEntries->size()) { PrintDebug("Process() returning\n", 0); retu rn Ret; } \

926 Prev = Temp; \

927 Entries = NextEntries; \

928 continue;

929 while (1) {

930 PrintDebug("Process() running\n", 0);

931 DebugDump(Blocks, " blocks : ");

932 DebugDump(*Entries, " entries: ");

933

934 CurrTempIndex = 1-CurrTempIndex;

935 NextEntries = &TempEntries[CurrTempIndex];

936 NextEntries->clear();

937

938 if (Entries->size() == 0) return Ret;

939 if (Entries->size() == 1) {

940 Block Curr = (Entries->begin());

941 if (Parent->Emulate) {

942 Make(MakeEmulated(Blocks, Curr, *NextEntries));

943 }

944 if (Curr->BranchesIn.size() == 0) {

945 // One entry, no looping ==> Simple

946 Make(MakeSimple(Blocks, Curr, *NextEntries));

947 }

948 // One entry, looping ==> Loop

949 Make(MakeLoop(Blocks, Entries, NextEntries));

950 }

951

952 // More than one entry, try to eliminate through a Multiple groups of

953 // independent blocks from an entry/ies. It is important to remove throu gh

954 // multiples as opposed to looping since the former is more performant.

955 BlockBlockSetMap IndependentGroups;

956 FindIndependentGroups(*Entries, IndependentGroups);

957

958 PrintDebug("Independent groups: %d\n", IndependentGroups.size());

959

960 if (IndependentGroups.size() > 0) {

961 // We can handle a group in a multiple if its entry cannot be reached by another group.

962 // Note that it might be reachable by itself - a loop. But that is fin e, we will create

963 // a loop inside the multiple block (which is the performant order to do it).

964 for (BlockBlockSetMap::iterator iter = IndependentGroups.begin(); iter != IndependentGroups.end();) {

965 Block *Entry = iter->first;

966 BlockSet &Group = iter->second;

967 BlockBlockSetMap::iterator curr = iter++; // iterate carefully, we m ay delete

968 for (BlockSet::iterator iterBranch = Entry->BranchesIn.begin(); iter Branch != Entry->BranchesIn.end(); iterBranch++) {

969 Block Origin = iterBranch;

970 if (!contains(Group, Origin)) {

971 // Reached from outside the group, so we cannot handle this

972 PrintDebug("Cannot handle group with entry %d because of incomin g branch from %d\n", Entry->Id, Origin->Id);

973 IndependentGroups.erase(curr);

974 break;

975 }

976 }

977 }

978

979 // As an optimization, if we have 2 independent groups, and one is a s mall dead end, we can handle only that dead end.

980 // The other then becomes a Next - without nesting in the code and rec ursion in the analysis.

981 // TODO: if the larger is the only dead end, handle that too

982 // TODO: handle >2 groups

983 // TODO: handle not just dead ends, but also that do not branch to the NextEntries. However, must be careful

984 // there since we create a Next, and that Next can prevent elimi nating a break (since we no longer

985 // naturally reach the same place), which may necessitate a one- time loop, which makes the unnesting

986 // pointless.

987 if (IndependentGroups.size() == 2) {

988 // Find the smaller one

989 BlockBlockSetMap::iterator iter = IndependentGroups.begin();

990 Block *SmallEntry = iter->first;

991 int SmallSize = iter->second.size();

992 iter++;

993 Block *LargeEntry = iter->first;

994 int LargeSize = iter->second.size();

995 if (SmallSize != LargeSize) { // ignore the case where they are iden tical - keep things symmetrical there

996 if (SmallSize > LargeSize) {

997 Block *Temp = SmallEntry;

998 SmallEntry = LargeEntry;

999 LargeEntry = Temp; // Note: we did not flip the Sizes too, they are now invalid. TODO: use the smaller size as a limit?

1000 }

1001 // Check if dead end

1002 bool DeadEnd = true;

1003 BlockSet &SmallGroup = IndependentGroups[SmallEntry];

1004 for (BlockSet::iterator iter = SmallGroup.begin(); iter != SmallGr oup.end(); iter++) {

1005 Block Curr = iter;

1006 for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) {

1007 Block *Target = iter->first;

1008 if (!contains(SmallGroup, Target)) {

1009 DeadEnd = false;

1010 break;

1011 }

1012 }

1013 if (!DeadEnd) break;

1014 }

1015 if (DeadEnd) {

1016 PrintDebug("Removing nesting by not handling large group because small group is dead end\n", 0);

1017 IndependentGroups.erase(LargeEntry);

1018 }

1019 }

1020 }

1021

1022 PrintDebug("Handleable independent groups: %d\n", IndependentGroups.si ze());

1023

1024 if (IndependentGroups.size() > 0) {

1025 // Some groups removable ==> Multiple

1026 Make(MakeMultiple(Blocks, Entries, IndependentGroups, Prev, NextEn tries));

1027 }

1028 }

1029 // No independent groups, must be loopable ==> Loop

1030 Make(MakeLoop(Blocks, Entries, NextEntries));

1031 }

1032 }

1033 };

1034

1035 // Main

1036

1037 BlockSet AllBlocks;

1038 for (BlockSet::iterator iter = Pre.Live.begin(); iter != Pre.Live.end(); iter+ +) {

1039 Block Curr = iter;

1040 AllBlocks.insert(Curr);

1041 #if DEBUG

1042 PrintDebug("Adding block %d (%s)\n", Curr->Id, Curr->Code);

1043 #endif

1044 }

1045

1046 BlockSet Entries;

1047 Entries.insert(Entry);

1048 Root = Analyzer(this).Process(AllBlocks, Entries, NULL);

1049 assert(Root);

1050

1051 // Post optimizations

1052

1053 struct PostOptimizer {

1054 Relooper *Parent;

1055 void *Closure;

1056

1057 PostOptimizer(Relooper *ParentInit) : Parent(ParentInit), Closure(NULL) {}

1058

1059 #define RECURSE_Multiple(shape, func) \

1060 for (IdShapeMap::iterator iter = shape->InnerMap.begin(); iter != shape->I nnerMap.end(); iter++) { \

1061 func(iter->second); \

1062 }

1063 #define RECURSE_Loop(shape, func) \

1064 func(shape->Inner);

1065 #define RECURSE(shape, func) RECURSE_##shape(shape, func);

1066

1067 #define SHAPE_SWITCH(var, simple, multiple, loop) \

1068 if (SimpleShape *Simple = Shape::IsSimple(var)) { \

1069 (void)Simple; \

1070 simple; \

1071 } else if (MultipleShape *Multiple = Shape::IsMultiple(var)) { \

1072 (void)Multiple; \

1073 multiple; \

1074 } else if (LoopShape *Loop = Shape::IsLoop(var)) { \

1075 (void)Loop; \

1076 loop; \

1077 }

1078

1079 // Find the blocks that natural control flow can get us directly to, or thro ugh a multiple that we ignore

1080 void FollowNaturalFlow(Shape *S, BlockSet &Out) {

1081 SHAPE_SWITCH(S, {

1082 Out.insert(Simple->Inner);

1083 }, {

1084 for (IdShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Mul tiple->InnerMap.end(); iter++) {

1085 FollowNaturalFlow(iter->second, Out);

1086 }

1087 FollowNaturalFlow(Multiple->Next, Out);

1088 }, {

1089 FollowNaturalFlow(Loop->Inner, Out);

1090 });

1091 }

1092

1093 void FindNaturals(Shape Root, Shape Otherwise=NULL) {

1094 if (Root->Next) {

1095 Root->Natural = Root->Next;

1096 FindNaturals(Root->Next, Otherwise);

1097 } else {

1098 Root->Natural = Otherwise;

1099 }

1100

1101 SHAPE_SWITCH(Root, {

1102 }, {

1103 for (IdShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Mul tiple->InnerMap.end(); iter++) {

1104 FindNaturals(iter->second, Root->Natural);

1105 }

1106 }, {

1107 FindNaturals(Loop->Inner, Loop->Inner);

1108 });

1109 }

1110

1111 // Remove unneeded breaks and continues.

1112 // A flow operation is trivially unneeded if the shape we naturally get to b y normal code

1113 // execution is the same as the flow forces us to.

1114 void RemoveUnneededFlows(Shape Root, Shape Natural=NULL, LoopShape *LastLo op=NULL, unsigned Depth=0) {

1115 BlockSet NaturalBlocks;

1116 FollowNaturalFlow(Natural, NaturalBlocks);

1117 Shape *Next = Root;

1118 while (Next) {

1119 Root = Next;

1120 Next = NULL;

1121 SHAPE_SWITCH(Root, {

1122 if (Simple->Inner->BranchVar) LastLoop = NULL; // a switch clears out the loop (TODO: only for breaks, not continue)

1123

1124 if (Simple->Next) {

1125 if (!Simple->Inner->BranchVar && Simple->Inner->ProcessedBranchesOut .size() == 2 && Depth < 20) {

1126 // If there is a next block, we already know at Simple creation ti me to make direct branches,

1127 // and we can do nothing more in general. But, we try to optimize the case of a break and

1128 // a direct: This would normally be if (break?) { break; } .. bu t if we

1129 // make sure to nest the else, we can save the break, if (!break? ) { .. } . This is also

1130 // better because the more canonical nested form is easier to furt her optimize later. The

1131 // downside is more nesting, which adds to size in builds with whi tespace.

1132 // Note that we avoid switches, as it complicates control flow and is not relevant

1133 // for the common case we optimize here.

1134 bool Found = false;

1135 bool Abort = false;

1136 for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranc hesOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) {

1137 Block *Target = iter->first;

1138 Branch *Details = iter->second;

1139 if (Details->Type == Branch::Break) {

1140 Found = true;

1141 if (!contains(NaturalBlocks, Target)) Abort = true;

1142 } else if (Details->Type != Branch::Direct) {

1143 Abort = true;

1144 }

1145 }

1146 if (Found && !Abort) {

1147 for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBra nchesOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) {

1148 Branch *Details = iter->second;

1149 if (Details->Type == Branch::Break) {

1150 Details->Type = Branch::Direct;

1151 if (MultipleShape *Multiple = Shape::IsMultiple(Details->Anc estor)) {

1152 Multiple->Breaks--;

1153 }

1154 } else {

1155 assert(Details->Type == Branch::Direct);

1156 Details->Type = Branch::Nested;

1157 }

1158 }

1159 }

1160 Depth++; // this optimization increases depth, for us and all our next chain (i.e., until this call returns)

1161 }

1162 Next = Simple->Next;

1163 } else {

1164 // If there is no next then Natural is where we will

1165 // go to by doing nothing, so we can potentially optimize some branc hes to direct.

1166 for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranche sOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) {

1167 Block *Target = iter->first;

1168 Branch *Details = iter->second;

1169 if (Details->Type != Branch::Direct && contains(NaturalBlocks, Tar get)) { // note: cannot handle split blocks

1170 Details->Type = Branch::Direct;

1171 if (MultipleShape *Multiple = Shape::IsMultiple(Details->Ancesto r)) {

1172 Multiple->Breaks--;

1173 }

1174 } else if (Details->Type == Branch::Break && LastLoop && LastLoop- >Natural == Details->Ancestor->Natural) {

1175 // it is important to simplify breaks, as simpler breaks enable other optimizations

1176 Details->Labeled = false;

1177 if (MultipleShape *Multiple = Shape::IsMultiple(Details->Ancesto r)) {

1178 Multiple->Breaks--;

1179 }

1180 }

1181 }

1182 }

1183 }, {

1184 for (IdShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != M ultiple->InnerMap.end(); iter++) {

1185 RemoveUnneededFlows(iter->second, Multiple->Next, Multiple->Breaks ? NULL : LastLoop, Depth+1);

1186 }

1187 Next = Multiple->Next;

1188 }, {

1189 RemoveUnneededFlows(Loop->Inner, Loop->Inner, Loop, Depth+1);

1190 Next = Loop->Next;

1191 });

1192 }

1193 }

1194

1195 // After we know which loops exist, we can calculate which need to be labele d

1196 void FindLabeledLoops(Shape *Root) {

1197 bool First = Closure == NULL;

1198 if (First) {

1199 Closure = (void)(new std::stack<Shape>);

1200 }

1201 std::stack<Shape> &LoopStack = ((std::stack<Shape>)Closure);

1202

1203 Shape *Next = Root;

1204 while (Next) {

1205 Root = Next;

1206 Next = NULL;

1207

1208 SHAPE_SWITCH(Root, {

1209 MultipleShape *Fused = Shape::IsMultiple(Root->Next);

1210 // If we are fusing a Multiple with a loop into this Simple, then visi t it now

1211 if (Fused && Fused->Breaks) {

1212 LoopStack.push(Fused);

1213 }

1214 if (Simple->Inner->BranchVar) {

1215 LoopStack.push(NULL); // a switch means breaks are now useless, push a dummy

1216 }

1217 if (Fused) {

1218 if (Fused->UseSwitch) {

1219 LoopStack.push(NULL); // a switch means breaks are now useless, pu sh a dummy

1220 }

1221 RECURSE_Multiple(Fused, FindLabeledLoops);

1222 }

1223 for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranchesO ut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) {

1224 Branch *Details = iter->second;

1225 if (Details->Type == Branch::Break \|\| Details->Type == Branch::Conti nue) {

1226 assert(LoopStack.size() > 0);

1227 if (Details->Ancestor != LoopStack.top() && Details->Labeled) {

1228 LabeledShape *Labeled = Shape::IsLabeled(Details->Ancestor);

1229 Labeled->Labeled = true;

1230 } else {

1231 Details->Labeled = false;

1232 }

1233 }

1234 }

1235 if (Fused && Fused->UseSwitch) {

1236 LoopStack.pop();

1237 }

1238 if (Simple->Inner->BranchVar) {

1239 LoopStack.pop();

1240 }

1241 if (Fused && Fused->Breaks) {

1242 LoopStack.pop();

1243 }

1244 if (Fused) {

1245 Next = Fused->Next;

1246 } else {

1247 Next = Root->Next;

1248 }

1249 }, {

1250 if (Multiple->Breaks) {

1251 LoopStack.push(Multiple);

1252 }

1253 RECURSE(Multiple, FindLabeledLoops);

1254 if (Multiple->Breaks) {

1255 LoopStack.pop();

1256 }

1257 Next = Root->Next;

1258 }, {

1259 LoopStack.push(Loop);

1260 RECURSE(Loop, FindLabeledLoops);

1261 LoopStack.pop();

1262 Next = Root->Next;

1263 });

1264 }

1265

1266 if (First) {

1267 delete (std::stack<Shape>)Closure;

1268 }

1269 }

1270

1271 void Process(Shape *Root) {

1272 FindNaturals(Root);

1273 RemoveUnneededFlows(Root);

1274 FindLabeledLoops(Root);

1275 }

1276 };

1277

1278 PrintDebug("=== Optimizing shapes ===\n", 0);

1279

1280 PostOptimizer(this).Process(Root);

1281 }

1282

1283 void Relooper::Render() {

1284 OutputBuffer = OutputBufferRoot;

1285 assert(Root);

1286 Root->Render(false);

1287 }

1288

1289 void Relooper::SetOutputBuffer(char *Buffer, int Size) {

1290 OutputBufferRoot = OutputBuffer = Buffer;

1291 OutputBufferSize = Size;

1292 OutputBufferOwned = false;

1293 }

1294

1295 void Relooper::MakeOutputBuffer(int Size) {

1296 if (OutputBufferRoot && OutputBufferSize >= Size && OutputBufferOwned) return;

1297 OutputBufferRoot = OutputBuffer = (char*)malloc(Size);

1298 OutputBufferSize = Size;

1299 OutputBufferOwned = true;

1300 }

1301

1302 char *Relooper::GetOutputBuffer() {

1303 return OutputBufferRoot;

1304 }

1305

1306 void Relooper::SetAsmJSMode(int On) {

1307 AsmJS = On;

1308 }

1309

1310 #if DEBUG

1311 // Debugging

1312

1313 void Debugging::Dump(BlockSet &Blocks, const char *prefix) {

1314 if (prefix) printf("%s ", prefix);

1315 for (BlockSet::iterator iter = Blocks.begin(); iter != Blocks.end(); iter++) {

1316 Block Curr = iter;

1317 printf("%d:\n", Curr->Id);

1318 for (BlockBranchMap::iterator iter2 = Curr->BranchesOut.begin(); iter2 != Cu rr->BranchesOut.end(); iter2++) {

1319 Block *Other = iter2->first;

1320 printf(" -> %d\n", Other->Id);

1321 assert(contains(Other->BranchesIn, Curr));

1322 }

1323 }

1324 }

1325

1326 void Debugging::Dump(Shape S, const char prefix) {

1327 if (prefix) printf("%s ", prefix);

1328 if (!S) {

1329 printf(" (null)\n");

1330 return;

1331 }

1332 printf(" %d ", S->Id);

1333 SHAPE_SWITCH(S, {

1334 printf("<< Simple with block %d\n", Simple->Inner->Id);

1335 }, {

1336 printf("<< Multiple\n");

1337 for (IdShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multipl e->InnerMap.end(); iter++) {

1338 printf(" with entry %d\n", iter->first);

1339 }

1340 }, {

1341 printf("<< Loop\n");

1342 });

1343 }

1344

1345 static void PrintDebug(const char *Format, ...) {

1346 printf("// ");

1347 va_list Args;

1348 va_start(Args, Format);

1349 vprintf(Format, Args);

1350 va_end(Args);

1351 }

1352 #endif

1353

1354 // C API - useful for binding to other languages

1355

1356 typedef std::map<void*, int> VoidIntMap;

1357 VoidIntMap __blockDebugMap__; // maps block pointers in currently running code t o block ids, for generated debug output

1358

1359 extern "C" {

1360

1361 RELOOPERDLL_API void rl_set_output_buffer(char *buffer, int size) {

1362 #if DEBUG

1363 printf("#include \"Relooper.h\"\n");

1364 printf("int main() {\n");

1365 printf(" char buffer[100000];\n");

1366 printf(" rl_set_output_buffer(buffer);\n");

1367 #endif

1368 Relooper::SetOutputBuffer(buffer, size);

1369 }

1370

1371 RELOOPERDLL_API void rl_make_output_buffer(int size) {

1372 Relooper::SetOutputBuffer((char*)malloc(size), size);

1373 }

1374

1375 RELOOPERDLL_API void rl_set_asm_js_mode(int on) {

1376 Relooper::SetAsmJSMode(on);

1377 }

1378

1379 RELOOPERDLL_API void rl_new_block(const char text, const char *branch_var) {

1380 Block *ret = new Block(text, branch_var);

1381 #if DEBUG

1382 printf(" void *b%d = rl_new_block(\"// code %d\");\n", ret->Id, ret->Id);

1383 __blockDebugMap__[ret] = ret->Id;

1384 printf(" block_map[%d] = b%d;\n", ret->Id, ret->Id);

1385 #endif

1386 return ret;

1387 }

1388

1389 RELOOPERDLL_API void rl_delete_block(void *block) {

1390 #if DEBUG

1391 printf(" rl_delete_block(block_map[%d]);\n", ((Block*)block)->Id);

1392 #endif

1393 delete (Block*)block;

1394 }

1395

1396 RELOOPERDLL_API void rl_block_add_branch_to(void from, void to, const char co ndition, const char code) {

1397 #if DEBUG

1398 printf(" rl_block_add_branch_to(block_map[%d], block_map[%d], %s%s%s, %s%s%s) ;\n", ((Block)from)->Id, ((Block)to)->Id, condition ? "\"" : "", condition ? c ondition : "NULL", condition ? "\"" : "", code ? "\"" : "", code ? code : "NULL" , code ? "\"" : "");

1399 #endif

1400 ((Block)from)->AddBranchTo((Block)to, condition, code);

1401 }

1402

1403 RELOOPERDLL_API void *rl_new_relooper() {

1404 #if DEBUG

1405 printf(" void *block_map[10000];\n");

1406 printf(" void *rl = rl_new_relooper();\n");

1407 #endif

1408 return new Relooper;

1409 }

1410

1411 RELOOPERDLL_API void rl_delete_relooper(void *relooper) {

1412 delete (Relooper*)relooper;

1413 }

1414

1415 RELOOPERDLL_API void rl_relooper_add_block(void relooper, void block) {

1416 #if DEBUG

1417 printf(" rl_relooper_add_block(rl, block_map[%d]);\n", ((Block*)block)->Id);

1418 #endif

1419 ((Relooper)relooper)->AddBlock((Block)block);

1420 }

1421

1422 RELOOPERDLL_API void rl_relooper_calculate(void relooper, void entry) {

1423 #if DEBUG

1424 printf(" rl_relooper_calculate(rl, block_map[%d]);\n", ((Block*)entry)->Id);

1425 printf(" rl_relooper_render(rl);\n");

1426 printf(" rl_delete_relooper(rl);\n");

1427 printf(" puts(buffer);\n");

1428 printf(" return 0;\n");

1429 printf("}\n");

1430 #endif

1431 ((Relooper)relooper)->Calculate((Block)entry);

1432 }

1433

1434 RELOOPERDLL_API void rl_relooper_render(void *relooper) {

1435 ((Relooper*)relooper)->Render();

1436 }

1437

1438 }

OLD	NEW

« no previous file with comments | « lib/Target/JSBackend/Relooper.h ('k') | lib/Target/JSBackend/SimplifyAllocas.cpp » ('j') | no next file with comments »