[CGP] Allow cycles during Phi traversal in OptimizaMemoryInst

[skatkov]

Summary

Allowing cycles in Phi traversal increases the scope of optimize memory instruction
in case we are in loop.

The added test shows an example of enabling optimization inside a loop.

[efriedma]

lib/CodeGen/CodeGenPrepare.cpp

4285 ↗

(On Diff #106153)

When you're looking through a PHI node, equality can be deceptive; induction variables are the "same", but can have a different value. (We got into trouble with BasicAA doing that recently.) I'd like to see a comment explaining why this particular version of the algorithm is correct.

[skatkov]

Hmmm, it is strange but it appeared not to be sent :( Re-sending.

lib/CodeGen/CodeGenPrepare.cpp

4285 ↗

(On Diff #106153)

Hi Eli, thank you for the good question. My current understanding as is follows. We are traversing through all paths from address up by use->def chain and finally found that ptr is computed as arithmetic expression of the form BaseGv + Base + Scale * Index + Offset, where Offset and Scale are constants while BaseGV, Base and Index are exact the same instructions.

As soon as all these are the same and we traversed by all paths these instruction dominates our ptr and our memory instruction. Instruction cannot change its value on the paths its dominates and our found expression will produce the same value on the path from definition of these instruction till our load and actually further. So we can safely add the computation of ptr right before our load.

Please correct me if I'm wrong or missed anything.

[efriedma]

lib/CodeGen/CodeGenPrepare.cpp

4285 ↗

(On Diff #106153)

That looks right.

Please add that explanation as a comment in the code.

[skatkov]

Please take a look.

[efriedma]

LGTM.

lib/CodeGen/CodeGenPrepare.cpp

4281 ↗

(On Diff #107023)

"the" is unnecessary.

llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp

bool CodeGenPrepare::optimizeMemoryInst(Instruction *MemoryInst, Value *Addr,
   ExtAddrMode AddrMode;
   TypePromotionTransaction TPT(RemovedInsts);
   TypePromotionTransaction::ConstRestorationPt LastKnownGood =
       TPT.getRestorationPoint();
   while (!worklist.empty()) {
     Value *V = worklist.back();
     worklist.pop_back();
 
-    // Break use-def graph loops.
-    if (!Visited.insert(V).second) {
-      AddrModeFound = false;
-      break;
-    }
+    // We allow traversing cyclic Phi nodes.
+    // In case of success after this loop we ensure that traversing through
+    // Phi nodes ends up with all cases to compute address of the form
+    //    BaseGV + Base + Scale * Index + Offset
+    // where Scale and Offset are constans and BaseGV, Base and Index
+    // are exactly the same Values in all cases.
+    // It means that BaseGV, Scale and Offset dominate our memory instruction
+    // and have the same value as they had in address computation represented
+    // as Phi. So we can safely sink address computation to memory instruction.
+    if (!Visited.insert(V).second)
+      continue;
 
     // For a PHI node, push all of its incoming values.
     if (PHINode *P = dyn_cast<PHINode>(V)) {
       for (Value *IncValue : P->incoming_values())
         worklist.push_back(IncValue);
       PhiSeen = true;
       continue;
     }

llvm/trunk/test/Transforms/CodeGenPrepare/X86/sink-addrmode.ll

 
 rare.2:
 ; CHECK-LABEL: rare.2:
 ; CHECK: getelementptr i8, {{.+}} 40
   call void @slowpath(i32 %v2, i32* %casted) cold
   br label %fallthrough
 }
 
-
 declare void @slowpath(i32, i32*)
 
 ; Make sure we don't end up in an infinite loop after we fail to sink.
 ; CHECK-LABEL: define void @test8
 ; CHECK: %ptr = getelementptr i8, i8* %aFOO_load_ptr2int_2void, i32 undef
 define void @test8() {
 allocas:
   %aFOO_load = load float*, float** undef
   %aFOO_load_ptr2int = ptrtoint float* %aFOO_load to i64
   %aFOO_load_ptr2int_broadcast_init = insertelement <4 x i64> undef, i64 %aFOO_load_ptr2int, i32 0
   %aFOO_load_ptr2int_2void = inttoptr i64 %aFOO_load_ptr2int to i8*
   %ptr = getelementptr i8, i8* %aFOO_load_ptr2int_2void, i32 undef
   br label %load.i145
 
 load.i145:
   %ptr.i143 = bitcast i8* %ptr to <4 x float>*
   %valall.i144 = load <4 x float>, <4 x float>* %ptr.i143, align 4
   %x_offset = getelementptr [1 x [2 x <4 x float>]], [1 x [2 x <4 x float>]]* @x, i32 0, i64 0
   br label %pl_loop.i.i122
 
 pl_loop.i.i122:
   br label %pl_loop.i.i122
 }
+
+; Make sure we can sink address computation even
+; if there is a cycle in phi nodes.
+define void @test9(i1 %cond, i64* %base) {
+; CHECK-LABEL: @test9
+entry:
+  %addr = getelementptr inbounds i64, i64* %base, i64 5
+  %casted = bitcast i64* %addr to i32*
+  br label %header
+
+header:
+  %iv = phi i32 [0, %entry], [%iv.inc, %backedge]
+  %casted.loop = phi i32* [%casted, %entry], [%casted.merged, %backedge]
+  br i1 %cond, label %if.then, label %backedge
+
+if.then:
+  call void @foo(i32 %iv)
+  %addr.1 = getelementptr inbounds i64, i64* %base, i64 5
+  %casted.1 = bitcast i64* %addr.1 to i32*
+  br label %backedge
+
+backedge:
+; CHECK-LABEL: backedge:
+; CHECK: getelementptr i8, {{.+}} 40
+  %casted.merged = phi i32* [%casted.loop, %header], [%casted.1, %if.then]
+  %v = load i32, i32* %casted.merged, align 4
+  call void @foo(i32 %v)
+  %iv.inc = add i32 %iv, 1
+  %cmp = icmp slt i32 %iv.inc, 1000
+  br i1 %cmp, label %header, label %exit
+
+exit:
+  ret void
+}