in lib/Optimizer/Scalar/StackPromotion.cpp [226:408]
bool promoteVariables(Function *F) {
bool changed = false;
llvh::DenseMap<BasicBlock *, llvh::DenseSet<Variable *>>
capturedVariableUsage;
determineCapturedVariableUsage(F, capturedVariableUsage);
// Find variables that are currently not optimal.
llvh::DenseSet<Variable *> needsOptimizing;
for (auto *var : F->getFunctionScope()->getVariables()) {
if (!hasExternalUses(var)) {
// This variable isn't needed at all, it should be purely on the stack.
needsOptimizing.insert(var);
continue;
}
// Look for loads/stores in the current function that are not needed.
for (auto *use : var->getUsers()) {
if (use->getParent()->getParent() != F)
continue;
if (capturedVariableUsage[use->getParent()].count(var))
continue;
// This use is not needed yet. We can optimize it.
needsOptimizing.insert(var);
break;
}
}
// Replace all variables with stack alloc operations in blocks that don't
// need real variables. For uncaptured variables, this replaces all uses.
IRBuilder builder(F);
llvh::DenseMap<Variable *, AllocStackInst *> stackMap;
for (auto *var : F->getFunctionScope()->getVariables()) {
if (!needsOptimizing.count(var))
continue;
if (!var->getNumUsers())
continue;
builder.setInsertionPoint(&*F->begin()->begin());
auto *stackVar = builder.createAllocStackInst(var->getName());
builder.createStoreStackInst(builder.getLiteralUndefined(), stackVar);
stackMap[var] = stackVar;
changed = true;
{
IRBuilder::InstructionDestroyer destroyer;
for (auto *U : var->getUsers()) {
// This instruction is not part of this function.
if (U->getParent()->getParent() != F)
continue;
// This block needs the variable in the frame.
if (capturedVariableUsage[U->getParent()].count(var))
continue;
NumOpsPostponed++;
if (auto *LF = llvh::dyn_cast<LoadFrameInst>(U)) {
builder.setInsertionPoint(LF);
auto *LS = builder.createLoadStackInst(stackVar);
LS->moveBefore(LF);
LF->replaceAllUsesWith(LS);
destroyer.add(LF);
continue;
}
if (auto *SF = llvh::dyn_cast<StoreFrameInst>(U)) {
builder.setInsertionPoint(SF);
auto *SS = builder.createStoreStackInst(SF->getValue(), stackVar);
SS->moveBefore(SF);
destroyer.add(SF);
continue;
}
llvm_unreachable("Invalid user");
}
}
// We were able to remove all uses.
if (!var->getNumUsers()) {
++NumSP;
}
}
// For any block where all incoming arrows require the same stores,
// insert them into the block itself.
llvh::DenseSet<std::pair<BasicBlock *, Variable *>> alreadyProcessed;
for (auto &BB : *F) {
// No incoming arrows
if (!pred_count(&BB))
continue;
llvh::DenseSet<Variable *> commons = capturedVariableUsage[&BB];
for (auto *predecessor : predecessors(&BB)) {
llvh::SmallVector<Variable *, 4> toErase;
for (auto *var : commons) {
if (needsOptimizing.count(var) &&
!capturedVariableUsage[predecessor].count(var))
continue;
toErase.push_back(var);
}
for (auto *var : toErase) {
commons.erase(var);
}
}
if (!commons.size())
continue;
auto insertionPoint = BB.begin();
while (llvh::isa<TryEndInst>(*insertionPoint) ||
llvh::isa<CatchInst>(*insertionPoint) ||
llvh::isa<PhiInst>(*insertionPoint)) {
insertionPoint++;
}
builder.setInsertionPoint(&*insertionPoint);
// Loop over the set of common variables, but in a deterministic order.
for (auto *var : F->getFunctionScope()->getVariables()) {
if (!commons.count(var))
continue;
// It could have been the case that this block both initializes and
// requires the variable. This load would then read an uninitialized
// value, which is illegal.
// To avoid this case, the variable is always initialized to undefined so
// that it's merely unnecessary, and will get optimized away.
auto *value = builder.createLoadStackInst(stackMap[var]);
builder.createStoreFrameInst(value, var);
alreadyProcessed.insert(std::pair<BasicBlock *, Variable *>(&BB, var));
changed = true;
}
}
// Find each block transition where one or more variable captures
// go from inactive to active.
llvh::SmallVector<StorePoint, 4> storePoints;
for (auto &BB : *F) {
TerminatorInst *terminator = BB.getTerminator();
auto &usedHere = capturedVariableUsage[&BB];
// Need to store each successor of the block, in order to ensure we don't
// accidentally consider the same arrow twice:
// A corner case that occurs under certain conditions in
// empty cases in switch statements
llvh::SmallPtrSet<BasicBlock *, 16> storeSuccessors;
for (int i = 0, e = terminator->getNumSuccessors(); i < e; i++) {
auto *next = terminator->getSuccessor(i);
// Only proceed if successor not seen before
if (!storeSuccessors.insert(next).second) {
continue;
}
auto &usedNext = capturedVariableUsage[next];
StorePoint *point = nullptr;
for (auto *var : F->getFunctionScope()->getVariables()) {
if (!needsOptimizing.count(var))
continue;
// We only care about transitions, i.e. variables
// that are usedNext but not usedHere.
if (usedHere.count(var) || !usedNext.count(var))
continue;
// We already incorporated this into the block itself
if (alreadyProcessed.count(
std::pair<BasicBlock *, Variable *>(next, var)))
continue;
if (!point) {
storePoints.push_back(StorePoint(&BB, next));
point = &storePoints.back();
}
point->variables.push_back(var);
}
}
}
// Copy from the stack to the frame at those points.
for (auto &point : storePoints) {
splitCriticalEdge(&builder, point.from, point.to);
for (auto *var : point.variables) {
auto *value = builder.createLoadStackInst(stackMap[var]);
builder.createStoreFrameInst(value, var);
changed = true;
}
}
return changed;
}