[ADCE] Modify data structures to support removing control flow

[david2050]

Summary

This is part of a serious of patches to evolve ADCE.cpp to support
removing of unnecessary control flow.

This patch changes the data structures to hold liveness information to
support the additional information we will eventually need. In
particular we now have a notion of basic blocks being live because
they contain a live operations. This will eventually feed into control
dependence analysis of which branches are live. We cater to getting
from instructions to associated block information and from blocks to
information about their terminators.

This patch also changes the structure of the main loop of the
algorithm so that it alternates propagating liveness between
instructions and usign control dependence information to mark branches
live.

We force all terminators live for now until we add code to handlinge
removing control flow in a later patch.

No changes to effective behavior with this patch

Previous patches:

D23065 [ADCE] Refactor anticipating new functionality (NFC)
D23102 [ADCE] Refactoring for new functionality (NFC)

[nadav]

lib/Transforms/Scalar/ADCE.cpp

45

"Instruction's" -> "Instructions. "

48

Doxygen comment above the line.

54

Period at the end of the sentence.

62

What's "== & InstInfo[Terminator]" ? Can you write in english that this pointer points to "InstInfo[Terminator]".

Also, it could be a good idea to say something about the invalidation of InstInfo.

69

Comment above the line.

77

Are you using std::vector instead of SmallVector because you are expecting that most function will have a large number of basic blocks?

146

Can you please add a comment that explains why BlockInfo is twice as big as BlockInfoVec?

160

initialize -> Initialize.
Period.

[mehdi_amini]

No tests?

lib/Transforms/Scalar/ADCE.cpp

40

"optimization"

70

Is this struct supposed to evolve in the future?
I feel it is close to the point where it may become a proper class.
(It seems to have invariants like Terminator == BB->getTerminator)

77

Why do you need this?
Is it because the iteration ordering over the BlockInfo DenseMap isn't deterministic?
Why can't you always iterate over the function? Will you mutate the ordering in the vector or remove elements?

147

Use reserve() instead, unless you have a good reason to use grow() here?

150

One line comment for this loop.

161

(Same as above)

204

auto *BB to mark explicitly that it is a pointer.

230

No trivial braces for the two previous if

264

Right now I don't make sense of this two-levels loop structure, because the checkControlDependences() operates only on BlocksWithDeadTerminators, which is only inserted to during initialize(). I assume it will change in a future patch? (Or I missed something)

291

"unconditional"

294

Fuse the two if with an &&

329

auto *BB

[david2050]

lib/Transforms/Scalar/ADCE.cpp

77

No, will change.

[david2050]

address review comments

[david2050]

Thanks!

lib/Transforms/Scalar/ADCE.cpp

70

We will had a little more state to support but it really will have no private data or sophisticated function.

77

Mehdi, yes, there are places where we iterate over the blocks in order so the DenseMap itself is not suitable. The order of the vector never changes. We could iterative of the basic blocks and index into the map if you feel strongly that it should be eliminated.

147

Is this comment about the resize above or the grow below?

264

In future, checkControlDependences will mark some branches as live as it determines they are needed. We then restart the data flow loop to make the data dependences of those branches as live.

[david2050]

Address comments

[majnemer]

lib/Transforms/Scalar/ADCE.cpp

139

Prefer auto * for pointer types.

331

Ditto.

[mehdi_amini]

lib/Transforms/Scalar/ADCE.cpp

77

For the three current loop over BlockInfoVec the iteration order does not seem to matter you could iterate over the DenseMap, the question is more about future patches that may benefit from this vector.

147

It is about grow below.

(Note there is an arrow on the top left of the comment next to my name with every comment that was made on a previous revision that can bring the context where the comment was made)

[david2050]

lib/Transforms/Scalar/ADCE.cpp

150

Missed this the first pass, in next diff

264

Will rename function to make this more explicit

[david2050]

Address comments

[david2050]

lib/Transforms/Scalar/ADCE.cpp

147

I would have sworn I tried to use reserve() on a DenseMap and it did not have it. Must have misunderstood the error message. I will change to use reserve()

[david2050]

Address comments

[david2050]

Remove BlockInfoVec and move data structure into BlockInfo map.

[david2050]

All comments have been addressed

lib/Transforms/Scalar/ADCE.cpp

77

I was made some simplifications in code-to-be added and eliminated BlockInfoVec to just store the information directly in BlockInfo.

[mehdi_amini]

Patch looks good overall, but it seems to me that you missed D.Majnemer's comments.
I added a few nits.
LGTM with these fixed.

lib/Transforms/Scalar/ADCE.cpp

39

"tempoary"

93

"blocks with not know to" does not seem correct (but English is not my native language)

101

"Instruscions"

139

ping.

148

Stalled comment (probably don't need a comment here, reserve is fairly explicit)

331

Ping

lib/Transforms/Scalar/ADCE.cpp

 #include "llvm/ProfileData/InstrProf.h"
 #include "llvm/Transforms/Scalar.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "adce"
 
 STATISTIC(NumRemoved, "Number of instructions removed");
 
+// This is a tempoary option until we change the interface
+// to this pass based on optimization level.
+static cl::opt<bool> RemoveControlFlowFlag("adce-remove-control-flow",
+                                           cl::init(false), cl::Hidden);
+
 namespace {
+/// Information about Instructions
+struct InstInfoType {
+  /// True if the associated instruction is live.
+  bool Live = false;
+  /// Quick access to information for block containing associated Instruction.
+  struct BlockInfoType *Block = nullptr;
+};
+
+/// Information about basic blocks relevant to dead code elimination.
+struct BlockInfoType {
+  /// True when this block contains a live instructions.
+  bool Live = false;
+  /// True when this block ends in an unconditional branch.
+  bool UnconditionalBranch = false;
+
+  /// Quick access to the LiveInfo for the terminator,
+  /// holds the value &InstInfo[Terminator]
+  InstInfoType *TerminatorLiveInfo = nullptr;
+
+  bool terminatorIsLive() const { return TerminatorLiveInfo->Live; }
+
+  /// Corresponding BasicBlock.
+  BasicBlock *BB = nullptr;
+
+  /// Cache of BB->getTerminator()
+  TerminatorInst *Terminator = nullptr;
+};
+
 class AggressiveDeadCodeElimination {
   Function &F;
-  /// Instructions known to be live.
-  SmallPtrSet<Instruction *, 32> Alive;
+
+  /// Per basic block information.
+  SmallVector<BlockInfoType, 32> BlockInfoVec;
+
+  /// Mapping of blocks to associated information, an element in BlockInfoVec.
+  DenseMap<BasicBlock *, BlockInfoType *> BlockInfo;
+  bool isLive(BasicBlock *BB) { return BlockInfo[BB]->Live; }
+
+  /// Mapping of instructions to associated information.
+  DenseMap<Instruction *, InstInfoType> InstInfo;
+  bool isLive(Instruction *I) { return InstInfo[I].Live; }
+
   /// Instructions known to be live where we need to mark
   /// reaching definitions as live.
   SmallVector<Instruction *, 128> Worklist;
   /// Debug info scopes around a live instruction.
   SmallPtrSet<const Metadata *, 32> AliveScopes;
 
+  /// Set of blocks with not known to have live terminators.
+  SmallPtrSet<BasicBlock *, 16> BlocksWithDeadTerminators;
+
+  /// The set of blocks which we have determined are live in the
+  /// most recent iteration of propagating liveness.
+  SmallPtrSet<BasicBlock *, 16> NewLiveBlocks;
+
+  /// Set up auxiliary data structures for Instructions and BasicBlocks and
+  /// initialize the Worklist to the set of must-be-live Instruscions.
   void initialize();
-  /// True for operations which are always treated as live.
+  /// Return true for operations which are always treated as live.
   bool isAlwaysLive(Instruction &I);
-  /// True for instrumentation instructions for value profiling.
+  /// Return true for instrumentation instructions for value profiling.
   bool isInstrumentsConstant(Instruction &I);
-  
-
   /// Propagate liveness to reaching definitions.
   void markLiveInstructions();
   /// Mark an instruction as live.
-  void markLive(Instruction &I);
-  
+  void markLive(Instruction *I);
+  /// Record the Debug Scopes which surround live debug information.
   void collectLiveScopes(const DILocalScope &LS);
   void collectLiveScopes(const DILocation &DL);
-  
+  /// Analyze dead branches to find those whose branches are the sources
+  /// of control dependences impacting a live block. Those branches are
+  /// marked live.
+  void markLiveBranchesFromControlDependences();
 
   /// Remove instructions not marked live, return if any any instruction
   /// was removed.
   bool removeDeadInstructions();
 
 public:
   AggressiveDeadCodeElimination(Function &F) : F(F) {}
   bool performDeadCodeElimination();
 };
 }
 
 bool AggressiveDeadCodeElimination::performDeadCodeElimination() {
   initialize();
   markLiveInstructions();
   return removeDeadInstructions();
 }
 
+static bool isUnconditionalBranch(TerminatorInst *Term) {
+  auto BR = dyn_cast<BranchInst>(Term);
+  return BR && BR->isUnconditional();
+}
+
 void AggressiveDeadCodeElimination::initialize() {
+
+  auto NumBlocks = F.size();
+  BlockInfoVec.resize(NumBlocks);
+
+  // We will have an entry in the map for each block so we grow the
+  // structure to twice that size to keep the load factor low in the hash table.
+  BlockInfo.reserve(NumBlocks);
+  auto InfoP = BlockInfoVec.begin();
+  size_t NumInsts = 0;
+  
+  // Iterate over blocks and initialize BlockInfoVec entries, count
+  // instructions to size the InstInfo hash table.
+  for (auto &BB : F) {
+    NumInsts += BB.size();
+    auto &Info = *InfoP;
+    BlockInfo[&BB] = &Info;
+    Info.BB = &BB;
+    Info.Terminator = BB.getTerminator();
+    Info.UnconditionalBranch = isUnconditionalBranch(Info.Terminator);
+    ++InfoP;
+  }
+
+  // Initialize instruction map and set pointers to block info.
+  InstInfo.reserve(NumInsts);
+  for (auto &BBInfo : BlockInfoVec)
+    for (Instruction &I : *BBInfo.BB)
+      InstInfo[&I].Block = &BBInfo;
+
+  // Since BlockInfoVec holds pointers into InstInfo and vice-versa, we may not
+  // add any more elements to either after this point.
+  for (auto &BBInfo : BlockInfoVec)
+    BBInfo.TerminatorLiveInfo = &InstInfo[BBInfo.Terminator];
+
   // Collect the set of "root" instructions that are known live.
   for (Instruction &I : instructions(F))
     if (isAlwaysLive(I))
-      markLive(I);
+      markLive(&I);
+
+  if (!RemoveControlFlowFlag)
+    return;
+
+  // This is temporary: will update with post order traveral to
+  // find loop bottoms
+  SmallPtrSet<BasicBlock *, 16> Seen;
+  for (auto &BB : F) {
+    Seen.insert(&BB);
+    TerminatorInst *Term = BB.getTerminator();
+    if (isLive(Term))
+      continue;
+
+    for (auto Succ : successors(&BB))
+      if (Seen.count(Succ)) {
+        // back edge....
+        markLive(Term);
+        break;
+      }
+  }
+  // end temporary handling of loops
+
+  // Treat the entry block as always live
+  auto *BB = &F.getEntryBlock();
+  auto &EntryInfo = *BlockInfo[BB];
+  EntryInfo.Live = true;
+  if (EntryInfo.UnconditionalBranch)
+    markLive(EntryInfo.Terminator);
+
+  // Build initial collection of blocks with dead terminators
+  for (auto &BBInfo : BlockInfoVec)
+    if (!BBInfo.terminatorIsLive())
+      BlocksWithDeadTerminators.insert(BBInfo.BB);
 }
 
 bool AggressiveDeadCodeElimination::isAlwaysLive(Instruction &I) {
-
   // TODO -- use llvm::isInstructionTriviallyDead
-  if (isa<TerminatorInst>(I) || I.isEHPad() || I.mayHaveSideEffects()) {
+  if (I.isEHPad() || I.mayHaveSideEffects()) {
     // Skip any value profile instrumentation calls if they are
     // instrumenting constants.
-    if (!isInstrumentsConstant(I))
-      return true;
+    if (isInstrumentsConstant(I))
+      return false;
   }
+  if (!isa<TerminatorInst>(I))
+    return false;
+  if (RemoveControlFlowFlag && (isa<BranchInst>(I) || isa<SwitchInst>(I)))
     return false;
+  return true;
 }
 
 // Check if this instruction is a runtime call for value profiling and
 // if it's instrumenting a constant.
 bool AggressiveDeadCodeElimination::isInstrumentsConstant(Instruction &I) {
   // TODO -- move this test into llvm::isInstructionTriviallyDead
   if (CallInst *CI = dyn_cast<CallInst>(&I))
     if (Function *Callee = CI->getCalledFunction())
       if (Callee->getName().equals(getInstrProfValueProfFuncName()))
         if (isa<Constant>(CI->getArgOperand(0)))
           return true;
   return false;
 }
 
 void AggressiveDeadCodeElimination::markLiveInstructions() {
 
-  // Propagate liveness backwards to operands.  Keep track of live debug info
-  // scopes.
+  // Propagate liveness backwards to operands.
+  do {
+    // Worklist holds newly discovered live instructions
+    // where we need to mark the inputs as live.
     while (!Worklist.empty()) {
-    Instruction *Curr = Worklist.pop_back_val();
+      Instruction *LiveInst = Worklist.pop_back_val();
 
       // Collect the live debug info scopes attached to this instruction.
-    if (const DILocation *DL = Curr->getDebugLoc())
+      if (const DILocation *DL = LiveInst->getDebugLoc())
         collectLiveScopes(*DL);
 
-    for (Use &OI : Curr->operands()) {
+      DEBUG(dbgs() << "work live: "; LiveInst->dump(););
+      for (Use &OI : LiveInst->operands())
         if (Instruction *Inst = dyn_cast<Instruction>(OI))
-        markLive(*Inst);
+          markLive(Inst);
     }
-  }
+    markLiveBranchesFromControlDependences();
+    // TODO -- handle PhiNodes
+  } while (!Worklist.empty());
+
+  // temporary until control dependences are implemented
+  assert(BlocksWithDeadTerminators.empty());
+
+void AggressiveDeadCodeElimination::markLive(Instruction *I) {
+
+  auto &Info = InstInfo[I];
+  if (Info.Live)
+    return;
+
+  DEBUG(dbgs() << "mark live: "; I->dump());
+  Info.Live = true;
+  Worklist.push_back(I);
+
+  // Mark the containing block live
+  auto &BBInfo = *Info.Block;
+  if (BBInfo.Terminator == I)
+    BlocksWithDeadTerminators.erase(BBInfo.BB);
+  if (BBInfo.Live)
+    return;
+
+  DEBUG(dbgs() << "mark block live: " << BBInfo.BB->getName() << '\n');
+  BBInfo.Live = true;
+  NewLiveBlocks.insert(BBInfo.BB);
+
+  // Mark unconditional branches at the end of live
+  // blocks as live since there is no work to do for them later
+  if (BBInfo.UnconditionalBranch && I != BBInfo.Terminator)
+      markLive(BBInfo.Terminator);
 }
 
 void AggressiveDeadCodeElimination::collectLiveScopes(const DILocalScope &LS) {
   if (!AliveScopes.insert(&LS).second)
     return;
-  
   if (isa<DISubprogram>(LS))
     return;
-  
   // Tail-recurse through the scope chain.
   collectLiveScopes(cast<DILocalScope>(*LS.getScope()));
 }
 
 void AggressiveDeadCodeElimination::collectLiveScopes(const DILocation &DL) {
   // Even though DILocations are not scopes, shove them into AliveScopes so we
   // don't revisit them.
   if (!AliveScopes.insert(&DL).second)
     return;
-  
   // Collect live scopes from the scope chain.
   collectLiveScopes(*DL.getScope());
-  
   // Tail-recurse through the inlined-at chain.
   if (const DILocation *IA = DL.getInlinedAt())
     collectLiveScopes(*IA);
 }
 
-void AggressiveDeadCodeElimination::markLive(Instruction &I) {
-  if (!Alive.insert(&I).second)
-    return;
-  Worklist.push_back(&I);
+void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() {
+
+  // This is  a place holder, mark all read operations live
+  // The next patch will replace this with using iterated dominance
+  // frontier to compute branches that need to be live because they
+  // control live blocks with live operations
+  SmallVector<TerminatorInst *, 16> DeadTerminators;
+  for (auto *BB : BlocksWithDeadTerminators)
+    DeadTerminators.push_back(BB->getTerminator());
+  for (auto I : DeadTerminators)
+    markLive(I);
+  NewLiveBlocks.clear();
 }
 
 bool AggressiveDeadCodeElimination::removeDeadInstructions() {
 
   // The inverse of the live set is the dead set.  These are those instructions
   // which have no side effects and do not influence the control flow or return
   // value of the function, and may therefore be deleted safely.
   // NOTE: We reuse the Worklist vector here for memory efficiency.
   for (Instruction &I : instructions(F)) {
     // Check if the instruction is alive.
-    if (Alive.count(&I))
+    if (isLive(&I))
       continue;
 
+    assert(!I.isTerminator() && "NYI: Removing Control Flow");
+
     if (auto *DII = dyn_cast<DbgInfoIntrinsic>(&I)) {
       // Check if the scope of this variable location is alive.
       if (AliveScopes.count(DII->getDebugLoc()->getScope()))
         continue;
 
       // Fallthrough and drop the intrinsic.
       DEBUG({
         // If intrinsic is pointing at a live SSA value, there may be an
         // earlier optimization bug: if we know the location of the variable,
         // why isn't the scope of the location alive?
         if (Value *V = DII->getVariableLocation())
           if (Instruction *II = dyn_cast<Instruction>(V))
-            if (Alive.count(II))
+            if (isLive(II))
               dbgs() << "Dropping debug info for " << *DII << "\n";
       });
     }
 
     // Prepare to delete.
     Worklist.push_back(&I);
     I.dropAllReferences();
   }