[AggressiveInstCombine] fixed PR36134

[aaboud]

Summary

Make TruncCombine class ignore unreachable basic blocks.

This should solve PR36134.

[uabelho]

I don't know this code but the fix makes sense to me and it makes the crash I saw go away.

[spatel]

LGTM.

Nit: when proposing patches and writing the commit message, make the title be more descriptive than 'Fixed Bug ###'. Ie, the title should be something like the summary text shown here:
"Make TruncCombine class ignore unreachable basic blocks"

...and then add some motivation in the summary:
"because dead code may contain non-standard IR that causes infinite looping or crashes in underlying analysis. See PR### for more details."

That lets people who are scanning the mailing list or doing bisection archaeology know quickly what this commit is doing and why.

llvm/trunk/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

 
 #include "llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h"
 #include "AggressiveInstCombineInternal.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/Pass.h"
 #include "llvm/Transforms/Scalar.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "aggressive-instcombine"
 
 namespace {
 /// Contains expression pattern combiner logic.
public:
   /// \returns true if the IR is changed.
   bool runOnFunction(Function &F) override;
 };
 } // namespace
 
 void AggressiveInstCombinerLegacyPass::getAnalysisUsage(
     AnalysisUsage &AU) const {
   AU.setPreservesCFG();
+  AU.addRequired<DominatorTreeWrapperPass>();
   AU.addRequired<TargetLibraryInfoWrapperPass>();
   AU.addPreserved<AAResultsWrapperPass>();
   AU.addPreserved<BasicAAWrapperPass>();
+  AU.addPreserved<DominatorTreeWrapperPass>();
   AU.addPreserved<GlobalsAAWrapperPass>();
 }
 
 bool AggressiveInstCombinerLegacyPass::runOnFunction(Function &F) {
+  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
   auto &DL = F.getParent()->getDataLayout();
 
   bool MadeIRChange = false;
 
   // Handle TruncInst patterns
-  TruncInstCombine TIC(TLI, DL);
+  TruncInstCombine TIC(TLI, DL, DT);
   MadeIRChange |= TIC.run(F);
 
   // TODO: add more patterns to handle...
 
   return MadeIRChange;
 }
 
 PreservedAnalyses AggressiveInstCombinePass::run(Function &F,
                                                  FunctionAnalysisManager &AM) {
+  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto &DL = F.getParent()->getDataLayout();
   bool MadeIRChange = false;
 
   // Handle TruncInst patterns
-  TruncInstCombine TIC(TLI, DL);
+  TruncInstCombine TIC(TLI, DL, DT);
   MadeIRChange |= TIC.run(F);
   if (!MadeIRChange)
     // No changes, all analyses are preserved.
     return PreservedAnalyses::all();
 
   // Mark all the analyses that instcombine updates as preserved.
   PreservedAnalyses PA;
   PA.preserveSet<CFGAnalyses>();
   PA.preserve<AAManager>();
   PA.preserve<GlobalsAA>();
   return PA;
 }
 
 char AggressiveInstCombinerLegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(AggressiveInstCombinerLegacyPass,
                       "aggressive-instcombine",
                       "Combine pattern based expressions", false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_END(AggressiveInstCombinerLegacyPass, "aggressive-instcombine",
                     "Combine pattern based expressions", false, false)
 
 FunctionPass *llvm::createAggressiveInstCombinerPass() {
   return new AggressiveInstCombinerLegacyPass();
 }

llvm/trunk/lib/Transforms/AggressiveInstCombine/AggressiveInstCombineInternal.h

 // The motivation for this optimization is that evaluating and expression using
 // smaller bit-width is preferable, especially for vectorization where we can
 // fit more values in one vectorized instruction. In addition, this optimization
 // may decrease the number of cast instructions, but will not increase it.
 //===----------------------------------------------------------------------===//
 
 namespace llvm {
   class DataLayout;
+  class DominatorTree;
   class TargetLibraryInfo;
 
 class TruncInstCombine {
   TargetLibraryInfo &TLI;
   const DataLayout &DL;
+  const DominatorTree &DT;
 
   /// List of all TruncInst instructions to be processed.
   SmallVector<TruncInst *, 4> Worklist;
 
   /// Current processed TruncInst instruction.
   TruncInst *CurrentTruncInst;
 
   /// Information per each instruction in the expression dag.
   struct Info {
     /// Number of LSBs that are needed to generate a valid expression.
     unsigned ValidBitWidth = 0;
     /// Minimum number of LSBs needed to generate the ValidBitWidth.
     unsigned MinBitWidth = 0;
     /// The reduced value generated to replace the old instruction.
     Value *NewValue = nullptr;
   };
   /// An ordered map representing expression dag post-dominated by current
   /// processed TruncInst. It maps each instruction in the dag to its Info
   /// structure. The map is ordered such that each instruction appears before
   /// all other instructions in the dag that uses it.
   MapVector<Instruction *, Info> InstInfoMap;
 
 public:
-  TruncInstCombine(TargetLibraryInfo &TLI, const DataLayout &DL)
-      : TLI(TLI), DL(DL), CurrentTruncInst(nullptr) {}
+  TruncInstCombine(TargetLibraryInfo &TLI, const DataLayout &DL,
+                   const DominatorTree &DT)
+      : TLI(TLI), DL(DL), DT(DT), CurrentTruncInst(nullptr) {}
 
   /// Perform TruncInst pattern optimization on given function.
   bool run(Function &F);
 
 private:
   /// Build expression dag dominated by the /p CurrentTruncInst and append it to
   /// the InstInfoMap container.
   ///

llvm/trunk/lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp

 //===----------------------------------------------------------------------===//
 
 #include "AggressiveInstCombineInternal.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRBuilder.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "aggressive-instcombine"
 
 /// Given an instruction and a container, it fills all the relevant operands of
 /// that instruction, with respect to the Trunc expression dag optimizaton.
 static void getRelevantOperands(Instruction *I, SmallVectorImpl<Value *> &Ops) {
if (!I->first->getNumUses())
       I->first->eraseFromParent();
   }
 }
 
 bool TruncInstCombine::run(Function &F) {
   bool MadeIRChange = false;
 
   // Collect all TruncInst in the function into the Worklist for evaluating.
-  for (auto &BB : F)
+  for (auto &BB : F) {
+    // Ignore unreachable basic block.
+    if (!DT.isReachableFromEntry(&BB))
+      continue;
     for (auto &I : BB)
       if (auto *CI = dyn_cast<TruncInst>(&I))
         Worklist.push_back(CI);
+  }
 
   // Process all TruncInst in the Worklist, for each instruction:
   //   1. Check if it dominates an eligible expression dag to be reduced.
   //   2. Create a reduced expression dag and replace the old one with it.
   while (!Worklist.empty()) {
     CurrentTruncInst = Worklist.pop_back_val();
 
     if (Type *NewDstSclTy = getBestTruncatedType()) {

llvm/trunk/test/Transforms/AggressiveInstCombine/trunc_unreachable_bb.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -aggressive-instcombine -S | FileCheck %s
+; RUN: opt < %s -passes=aggressive-instcombine -S | FileCheck %s
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+
+; Aggressive Instcombine should be able ignore unreachable basic block.
+
+define void @func_20() {
+; CHECK-LABEL: @func_20(
+; CHECK-NEXT:  for.body94:
+; CHECK-NEXT:    unreachable
+; CHECK:       for.cond641:
+; CHECK-NEXT:    [[OR722:%.*]] = or i32 [[OR722]], undef
+; CHECK-NEXT:    [[OR723:%.*]] = or i32 [[OR722]], 1
+; CHECK-NEXT:    [[CONV724:%.*]] = trunc i32 [[OR723]] to i16
+; CHECK-NEXT:    br label [[FOR_COND641:%.*]]
+;
+for.body94:
+  unreachable
+
+for.cond641:
+  %or722 = or i32 %or722, undef
+  %or723 = or i32 %or722, 1
+  %conv724 = trunc i32 %or723 to i16
+  br label %for.cond641
+}
+
+define void @func_21() {
+; CHECK-LABEL: @func_21(
+; CHECK-NEXT:  for.body94:
+; CHECK-NEXT:    unreachable
+; CHECK:       for.cond641:
+; CHECK-NEXT:    [[OR722:%.*]] = or i32 [[A:%.*]], undef
+; CHECK-NEXT:    [[A]] = or i32 [[OR722]], undef
+; CHECK-NEXT:    [[OR723:%.*]] = or i32 [[OR722]], 1
+; CHECK-NEXT:    [[CONV724:%.*]] = trunc i32 [[OR723]] to i16
+; CHECK-NEXT:    br label [[FOR_COND641:%.*]]
+;
+for.body94:
+  unreachable
+
+for.cond641:
+  %or722 = or i32 %a, undef
+  %a = or i32 %or722, undef
+  %or723 = or i32 %or722, 1
+  %conv724 = trunc i32 %or723 to i16
+  br label %for.cond641
+}