[DFAJumpThreading] Determinator BB should precede switch-defining BB

[alexey.zhikhar]

Summary

Otherwise, it is possible that the state defined in the determinator
block defines the state for the next iteration of the loop, rather than
for the current one.

Fixes llvm-test-suite's
SingleSource/Regression/C/gcc-c-torture/execute/pr80421.c
on X86.

[alexey.zhikhar]

I attach a picture of the CFG illustrating the problem in one of the llvm-test-suite tests that was failing on X86.

The DFA jump threader attempted to jump-thread the switch inside the if.else basic block. One of the threading paths is

< if.else sw.default.i if.end while.body sw.bb1 sw.epilog >

where basic block sw.epilog is marked as the determinator.

Determinator BB is the BB that that contains the phi-node that "determines" the value of the switch condition. Does sw.epilog determine the next state in the switch statement inside if.else? Not immediately: %next.state first is propagated through %state.1 and %state and only then this new state is used.

To catch and discard this case, this patch verifies the sequence of types of basic blocks: determinator BB should be followed by the basic block that defines the switch condition, followed by the basic block that uses the switch condition (the BB with the candidate switch).

[amehsan]

Alex and I have discussed this in detail. This testcase can also be investigated for potentially extending the algorithm. While we are confident that with the existing information (the paths that we gather during analysis phase) it is not possible to jump thread the switch statement, it may be possible to jump thread it if we gather more information (gathering a set of longer paths in the analysis phase). But at this point it does not seem worthwhile to explore this path, and the most reasonable solution is to add this new condition to make the case illegal. Alex have also compared with gcc, and they do not jump thread this switch statement.

llvm/lib/Transforms/Scalar/DFAJumpThreading.cpp

for (PathType Path : LoopPaths) {
 
         // Switch block is the determinator, this is the final exit value.
         if (TPath.isExitValueSet() && BB == Path.front())
           break;
 
         PrevBB = BB;
       }
 
-      if (TPath.isExitValueSet())
+      if (TPath.isExitValueSet() && isSupported(TPath))
         TPaths.push_back(TPath);
     }
   }
 
 private:
   // Value: an instruction that defines a switch state;
   // Key: the parent basic block of that instruction.
   typedef DenseMap<const BasicBlock *, const PHINode *> StateDefMap;
while (!Stack.empty()) {
 
         Stack.push_back(cast<PHINode>(Incoming));
       }
     }
 
     return Res;
   }
 
+  /// The determinator BB should precede the switch-defining BB.
+  ///
+  /// Otherwise, it is possible that the state defined in the determinator block
+  /// defines the state for the next iteration of the loop, rather than for the
+  /// current one.
+  ///
+  /// Currently supported paths:
+  /// \code
+  /// < switch bb1 determ def > [ 42, determ ]
+  /// < switch_and_def bb1 determ > [ 42, determ ]
+  /// < switch_and_def_and_determ bb1 > [ 42, switch_and_def_and_determ ]
+  /// \endcode
+  ///
+  /// Unsupported paths:
+  /// \code
+  /// < switch bb1 def determ > [ 43, determ ]
+  /// < switch_and_determ bb1 def > [ 43, switch_and_determ ]
+  /// \endcode
+  bool isSupported(const ThreadingPath &TPath) {
+    Instruction *SwitchCondI = dyn_cast<Instruction>(Switch->getCondition());
+    assert(SwitchCondI);
+    if (!SwitchCondI)
+      return false;
+
+    const BasicBlock *SwitchCondDefBB = SwitchCondI->getParent();
+    const BasicBlock *SwitchCondUseBB = Switch->getParent();
+    const BasicBlock *DeterminatorBB = TPath.getDeterminatorBB();
+
+    assert(
+        SwitchCondUseBB == TPath.getPath().front() &&
+        "The first BB in a threading path should have the switch instruction");
+    if (SwitchCondUseBB != TPath.getPath().front())
+      return false;
+
+    // Make DeterminatorBB the first element in Path.
+    PathType Path = TPath.getPath();
+    auto ItDet = std::find(Path.begin(), Path.end(), DeterminatorBB);
+    std::rotate(Path.begin(), ItDet, Path.end());
+
+    bool IsDetBBSeen = false;
+    bool IsDefBBSeen = false;
+    bool IsUseBBSeen = false;
+    for (BasicBlock *BB : Path) {
+      if (BB == DeterminatorBB)
+        IsDetBBSeen = true;
+      if (BB == SwitchCondDefBB)
+        IsDefBBSeen = true;
+      if (BB == SwitchCondUseBB)
+        IsUseBBSeen = true;
+      if (IsDetBBSeen && IsUseBBSeen && !IsDefBBSeen)
+        return false;
+    }
+
+    return true;
+  }
+
   SwitchInst *Switch;
   BasicBlock *SwitchBlock;
   OptimizationRemarkEmitter *ORE;
   std::vector<ThreadingPath> TPaths;
 };
 
 struct TransformDFA {
   TransformDFA(AllSwitchPaths *SwitchPaths, DominatorTree *DT,

llvm/test/Transforms/DFAJumpThreading/dfa-jump-threading-analysis.ll

infloop.i:
   br label %infloop.i
 
 exit:
   ret i32 0
 }
 
 declare void @baz()
 
-; Verify that having the switch block as a determinator is handled correctly.
-define i32 @main() {
-; CHECK: < bb43 bb59 bb3 bb31 bb41 > [ 77, bb43 ]
-; CHECK-NEXT: < bb43 bb49 bb59 bb3 bb31 bb41 > [ 77, bb43 ]
+; Do not jump-thread those paths where the determinator basic block does not
+; precede the basic block that defines the switch condition.
+;
+; Otherwise, it is possible that the state defined in the determinator block
+; defines the state for the next iteration of the loop, rather than for the
+; current one.
+define i32 @wrong_bb_order() {
+; CHECK-LABEL: DFA Jump threading: wrong_bb_order
+; CHECK-NOT: < bb43 bb59 bb3 bb31 bb41 > [ 77, bb43 ]
+; CHECK-NOT: < bb43 bb49 bb59 bb3 bb31 bb41 > [ 77, bb43 ]
 bb:
   %i = alloca [420 x i8], align 1
   %i2 = getelementptr inbounds [420 x i8], [420 x i8]* %i, i64 0, i64 390
   br label %bb3
 
 bb3:                                              ; preds = %bb59, %bb
   %i4 = phi i8* [ %i2, %bb ], [ %i60, %bb59 ]
   %i5 = phi i8 [ 77, %bb ], [ %i64, %bb59 ]