[IRSim] Treat Branch OperVals different from regular operands

[AndrewLitteken]

Summary

Branch operands are different from regular instructions. They can have a mix of boolean values and branch instructions. This makes sure that branches are treated as more of a special case and makes sure that the successor blocks are always in the same order, and that they do not include the conditional argument.

[paquette]

Testcase?

[paquette]

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

102

This can use cast<>. Then you get an assertion on the wrong type for free.

https://llvm.org/docs/ProgrammersManual.html#the-isa-cast-and-dyn-cast-templates

114

I think this needs brackets around the isas otherwise the && will be evaluated first.

724–725

I think you can use cast<> for both of these.

855

could use a comment?

858

Why are these asserts after the if?

[AndrewLitteken]

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

858

If the sizes of the block information between the two branch instructions do not match, then we don't need to worry about whether the information contained in them is correct. This checks consistency between the two data structures concerning the same branch. I think this could go before the if statements, but I also don't know if it matters the order.

[AndrewLitteken]

Updating based on comments, forgot to upload this diff several months ago

[paquette]

LGTM

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h

struct IRInstructionData
   /// taking the difference of the number assigned to the current basic block
   /// and the incoming basic block of the branch.
   ///
   /// \param BasicBlockToInteger - The mapping of basic blocks to their location
   /// in the module.
   void
   setPHIPredecessors(DenseMap<BasicBlock *, unsigned> &BasicBlockToInteger);
 
+  /// Get the BasicBlock based operands for PHINodes and BranchInsts.
+  ///
+  /// \returns A list of relevant BasicBlocks.
+  ArrayRef<Value *> getBlockOperVals();
+
   /// Hashes \p Value based on its opcode, types, and operand types.
   /// Two IRInstructionData instances produce the same hash when they perform
   /// the same operation.
   ///
   /// As a simple example, consider the following instructions.
   ///
   /// \code
   /// %add1 = add i32 %x1, %y1

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

 //===- IRSimilarityIdentifier.cpp - Find similarity in a module -----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // \file
 // Implementation file for the IRSimilarityIdentifier for identifying
 // similarities in IR including the IRInstructionMapper.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/IRSimilarityIdentifier.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SetOperations.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/User.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/SuffixTree.h"
 
 using namespace llvm;
 using namespace IRSimilarity;
void IRInstructionData::setBranchSuccessors(
   DenseMap<BasicBlock *, unsigned>::iterator BBNumIt;
 
   BBNumIt = BasicBlockToInteger.find(BI->getParent());
   assert(BBNumIt != BasicBlockToInteger.end() &&
          "Could not find location for BasicBlock!");
 
   int CurrentBlockNumber = static_cast<int>(BBNumIt->second);
 
-  for (BasicBlock *Successor : BI->successors()) {
+  for (Value *V : getBlockOperVals()) {
+    BasicBlock *Successor = cast<BasicBlock>(V);
     BBNumIt = BasicBlockToInteger.find(Successor);
     assert(BBNumIt != BasicBlockToInteger.end() &&
            "Could not find number for BasicBlock!");
     int OtherBlockNumber = static_cast<int>(BBNumIt->second);
 
     int Relative = OtherBlockNumber - CurrentBlockNumber;
     RelativeBlockLocations.push_back(Relative);
   }
 }
 
+ArrayRef<Value *> IRInstructionData::getBlockOperVals() {
+  assert((isa<BranchInst>(Inst) ||
+         isa<PHINode>(Inst)) && "Instruction must be branch or PHINode");
+  
+  if (BranchInst *BI = dyn_cast<BranchInst>(Inst))
+    return ArrayRef<Value *>(
+      std::next(OperVals.begin(), BI->isConditional() ? 1 : 0),
+      OperVals.end()
+    );
+
+  if (PHINode *PN = dyn_cast<PHINode>(Inst))
+    return ArrayRef<Value *>(
+      std::next(OperVals.begin(), PN->getNumIncomingValues()),
+      OperVals.end()
+    );
+
+  return ArrayRef<Value *>();
+}
+
 void IRInstructionData::setCalleeName(bool MatchByName) {
   CallInst *CI = dyn_cast<CallInst>(Inst);
   assert(CI && "Instruction must be call");
 
   CalleeName = "";
   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
     // To hash intrinsics, we use the opcode, and types like the other
     // instructions, but also, the Intrinsic ID, and the Name of the
for (unsigned Idx = 0; Idx < PN->getNumIncomingValues(); Idx++) {
     BasicBlock *Incoming = PN->getIncomingBlock(Idx);
     BBNumIt = BasicBlockToInteger.find(Incoming);
     assert(BBNumIt != BasicBlockToInteger.end() &&
            "Could not find number for BasicBlock!");
     int OtherBlockNumber = static_cast<int>(BBNumIt->second);
 
     int Relative = OtherBlockNumber - CurrentBlockNumber;
     RelativeBlockLocations.push_back(Relative);
-    RelativeBlockLocations.push_back(Relative);
   }
 }
 
 CmpInst::Predicate IRInstructionData::predicateForConsistency(CmpInst *CI) {
   switch (CI->getPredicate()) {
   case CmpInst::FCMP_OGT:
   case CmpInst::FCMP_UGT:
   case CmpInst::FCMP_OGE:
if (!checkNumberingAndReplaceCommutative(B.IRSC.ValueToNumber,
     return false;
 
   return true;
 }
 
 bool IRSimilarityCandidate::checkRelativeLocations(RelativeLocMapping A,
                                                    RelativeLocMapping B) {
   // Get the basic blocks the label refers to.
-  BasicBlock *ABB = static_cast<BasicBlock *>(A.OperVal);
-  BasicBlock *BBB = static_cast<BasicBlock *>(B.OperVal);
+  BasicBlock *ABB = cast<BasicBlock>(A.OperVal);
+  BasicBlock *BBB = cast<BasicBlock>(B.OperVal);
 
   // Get the basic blocks contained in each region.
   DenseSet<BasicBlock *> BasicBlockA;
   DenseSet<BasicBlock *> BasicBlockB;
   A.IRSC.getBasicBlocks(BasicBlockA);
   B.IRSC.getBasicBlocks(BasicBlockB);
   
   // Determine if the block is contained in the region.
   bool AContained = BasicBlockA.contains(ABB);
   bool BContained = BasicBlockB.contains(BBB);
 
   // Both blocks need to be contained in the region, or both need to be outside
-  // the reigon.
+  // the region.
   if (AContained != BContained)
     return false;
   
   // If both are contained, then we need to make sure that the relative
   // distance to the target blocks are the same.
   if (AContained)
     return A.RelativeLocation == B.RelativeLocation;
   return true;
for (unsigned Loc = A.getStartIdx(); Loc < SectionLength;
     // outside the region, we are targeting a corresponding block in each
     // analagous location in the region we are comparing to.
     if (!(isa<BranchInst>(IA) && isa<BranchInst>(IB)) &&
         !(isa<PHINode>(IA) && isa<PHINode>(IB)))
       continue;
 
     SmallVector<int, 4> &RelBlockLocsA = ItA->RelativeBlockLocations;
     SmallVector<int, 4> &RelBlockLocsB = ItB->RelativeBlockLocations;
+    ArrayRef<Value *> ABL = ItA->getBlockOperVals();
+    ArrayRef<Value *> BBL = ItB->getBlockOperVals();
+
+    // Check to make sure that the number of operands, and branching locations
+    // between BranchInsts is the same.
     if (RelBlockLocsA.size() != RelBlockLocsB.size() &&
-        OperValsA.size() != OperValsB.size())
+        ABL.size() != BBL.size())
       return false;
 
+    assert(RelBlockLocsA.size() == ABL.size() &&
+           "Block information vectors not the same size.");
+    assert(RelBlockLocsB.size() == BBL.size() &&
+           "Block information vectors not the same size.");
+
     ZippedRelativeLocationsT ZippedRelativeLocations =
-        zip(RelBlockLocsA, RelBlockLocsB, OperValsA, OperValsB);
+        zip(RelBlockLocsA, RelBlockLocsB, ABL, BBL);
     if (any_of(ZippedRelativeLocations,
                [&A, &B](std::tuple<int, int, Value *, Value *> R) {
                  return !checkRelativeLocations(
                      {A, std::get<0>(R), std::get<2>(R)},
                      {B, std::get<1>(R), std::get<3>(R)});
                }))
       return false;
   }