From f2038b1d9325b23e73a20b57fcb3508f4dda1817 Mon Sep 17 00:00:00 2001
From: Devang Patel <dpatel@apple.com>
Date: Wed, 19 Sep 2007 20:18:51 +0000
Subject: [PATCH] Avoid unsafe promotion.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42149 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Scalar/LICM.cpp                | 50 +++++++++++++++----
 .../LICM/2007-09-17-PromoteValue.ll           | 35 +++++++++++++
 2 files changed, 76 insertions(+), 9 deletions(-)

diff --git a/lib/Transforms/Scalar/LICM.cpp b/lib/Transforms/Scalar/LICM.cpp
index 6c5976ad3a9..3058f74aab9 100644
--- a/lib/Transforms/Scalar/LICM.cpp
+++ b/lib/Transforms/Scalar/LICM.cpp
@@ -759,15 +759,24 @@ void LICM::PromoteValuesInLoop() {
 }
 
 /// FindPromotableValuesInLoop - Check the current loop for stores to definite
-/// pointers, which are not loaded and stored through may aliases.  If these are
-/// found, create an alloca for the value, add it to the PromotedValues list,
-/// and keep track of the mapping from value to alloca.
-///
+/// pointers, which are not loaded and stored through may aliases and are safe
+/// for promotion.  If these are found, create an alloca for the value, add it 
+/// to the PromotedValues list, and keep track of the mapping from value to 
+/// alloca. 
 void LICM::FindPromotableValuesInLoop(
                    std::vector<std::pair<AllocaInst*, Value*> > &PromotedValues,
                              std::map<Value*, AllocaInst*> &ValueToAllocaMap) {
   Instruction *FnStart = CurLoop->getHeader()->getParent()->begin()->begin();
 
+  SmallVector<Instruction *, 4> LoopExits;
+  SmallVector<BasicBlock *, 4> Blocks;
+  CurLoop->getExitingBlocks(Blocks);
+  for (SmallVector<BasicBlock *, 4>::iterator BI = Blocks.begin(),
+         BE = Blocks.end(); BI != BE; ++BI) {
+    BasicBlock *BB = *BI;
+    LoopExits.push_back(BB->getTerminator());
+  }
+
   // Loop over all of the alias sets in the tracker object.
   for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end();
        I != E; ++I) {
@@ -791,14 +800,37 @@ void LICM::FindPromotableValuesInLoop(
           break;
         }
 
-      // If GEP base is NULL then the calculated address  used by Store or
-      // Load instruction is invalid. Do not promote this value because
-      // it may expose load and store instruction that are covered by
-      // condition which may not yet folded.
-      if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V))
+      if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V)) {
+        // If GEP base is NULL then the calculated address used by Store or
+        // Load instruction is invalid. Do not promote this value because
+        // it may expose load and store instruction that are covered by
+        // condition which may not yet folded.
         if (isa<ConstantPointerNull>(GEP->getOperand(0)))
           PointerOk = false;
 
+        // If GEP is use is not dominating loop exit then promoting
+        // GEP may expose unsafe load and store instructions unconditinally.
+        if (PointerOk)
+          for(Value::use_iterator UI = V->use_begin(), UE = V->use_end();
+              UI != UE && PointerOk; ++UI) {
+            Instruction *Use = dyn_cast<Instruction>(*UI);
+            if (!Use)
+              continue;
+            for (SmallVector<Instruction *, 4>::iterator 
+                   ExitI = LoopExits.begin(), ExitE = LoopExits.end();
+                 ExitI != ExitE; ++ExitI) {
+              Instruction *Ex = *ExitI;
+              if (!DT->dominates(Use, Ex)){
+                PointerOk = false;
+                break;
+              }
+            }
+
+            if (!PointerOk)
+              break;
+          }
+      }
+
       if (PointerOk) {
         const Type *Ty = cast<PointerType>(V->getType())->getElementType();
         AllocaInst *AI = new AllocaInst(Ty, 0, V->getName()+".tmp", FnStart);
diff --git a/test/Transforms/LICM/2007-09-17-PromoteValue.ll b/test/Transforms/LICM/2007-09-17-PromoteValue.ll
index acbbabf40a1..e9ba9e16318 100644
--- a/test/Transforms/LICM/2007-09-17-PromoteValue.ll
+++ b/test/Transforms/LICM/2007-09-17-PromoteValue.ll
@@ -23,4 +23,39 @@ clear_modes.exit:		; preds = %blah.i
 	unreachable
 }
 
+define i32 @f(i8* %ptr) {
+entry:
+        br label %loop.head
+
+loop.head:              ; preds = %cond.true, %entry
+        %x = phi i8* [ %ptr, %entry ], [ %ptr.i, %cond.true ]           ; <i8*> [#uses=1]
+        %tmp3.i = icmp ne i8* %ptr, %x          ; <i1> [#uses=1]
+        br i1 %tmp3.i, label %cond.true, label %exit
+
+cond.true:              ; preds = %loop.head
+        %ptr.i = getelementptr i8* %ptr, i32 0          ; <i8*> [#uses=2]
+        store i8 0, i8* %ptr.i
+        br label %loop.head
+
+exit:           ; preds = %loop.head
+        ret i32 0
+}
+
+define i32 @f2(i8* %p, i8* %q) {
+entry:
+        br label %loop.head
+
+loop.head:              ; preds = %cond.true, %entry
+        %tmp3.i = icmp eq i8* null, %q            ; <i1> [#uses=1]
+        br i1 %tmp3.i, label %exit, label %cond.true
+
+cond.true:              ; preds = %loop.head
+        %ptr.i = getelementptr i8* %p, i32 0          ; <i8*> [#uses=2]
+        store i8 0, i8* %ptr.i
+        br label %loop.head
+
+exit:           ; preds = %loop.head
+        ret i32 0
+}
+
 declare void @exit(i32)
-- 
2.34.1