diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -4750,8 +4750,6 @@
   // be undef or poison.
   if (isa<FreezeInst>(V))
     return true;
-  // TODO: Some instructions are guaranteed to return neither undef
-  // nor poison if their arguments are not poison/undef.
 
   if (auto *A = dyn_cast<Argument>(V)) {
     // NoUndef does not guarantee that paddings are not undef.
@@ -4760,9 +4758,7 @@
   }
 
   if (auto *C = dyn_cast<Constant>(V)) {
-    // TODO: We can analyze ConstExpr by opcode to determine if there is any
-    //       possibility of poison.
-    if (isa<UndefValue>(C) || isa<ConstantExpr>(C))
+    if (isa<UndefValue>(C))
       return false;
 
     if (isa<ConstantInt>(C) || isa<GlobalVariable>(C) || isa<ConstantFP>(V) ||
@@ -4771,9 +4767,6 @@
 
     if (C->getType()->isVectorTy())
       return !C->containsUndefElement() && !C->containsConstantExpression();
-
-    // TODO: Recursively analyze aggregates or other constants.
-    return false;
   }
 
   // Strip cast operations from a pointer value.
@@ -4793,31 +4786,57 @@
     return isGuaranteedNotToBeUndefOrPoison(V, CtxI, DT, Depth + 1);
   };
 
-  if (auto *I = dyn_cast<Instruction>(V)) {
-    switch (I->getOpcode()) {
-    case Instruction::GetElementPtr: {
-      auto *GEPI = dyn_cast<GetElementPtrInst>(I);
-      if (!GEPI->isInBounds() && llvm::all_of(GEPI->operands(), OpCheck))
+  if (auto *Opr = dyn_cast<Operator>(V)) {
+    if (auto *OverflowOp = dyn_cast<OverflowingBinaryOperator>(V)) {
+      if (!OverflowOp->hasNoSignedWrap() && !OverflowOp->hasNoUnsignedWrap() &&
+          OpCheck(OverflowOp->getOperand(0)) &&
+          OpCheck(OverflowOp->getOperand(1)))
         return true;
-      break;
     }
+
+    if (auto *GEPOp = dyn_cast<GEPOperator>(V)) {
+      if (!GEPOp->isInBounds() && llvm::all_of(GEPOp->operands(), OpCheck))
+        return true;
+    }
+
+    switch (Opr->getOpcode()) {
+    case Instruction::FNeg:
+    case Instruction::FAdd:
+    case Instruction::FSub:
+    case Instruction::FMul:
+    case Instruction::FDiv:
+    case Instruction::FRem:
     case Instruction::FCmp: {
-      auto *FI = dyn_cast<FCmpInst>(I);
-      if (FI->getFastMathFlags().none() &&
-          llvm::all_of(FI->operands(), OpCheck))
+      auto *FPOp = dyn_cast<FPMathOperator>(Opr);
+      if (FPOp->getFastMathFlags().none() &&
+          llvm::all_of(FPOp->operands(), OpCheck))
         return true;
       break;
     }
+    case Instruction::ExtractValue:
+      if (isGuaranteedNotToBeUndefOrPoison(Opr->getOperand(0), CtxI, DT,
+                                           Depth + 1))
+        return true;
+      break;
+    case Instruction::And:
+    case Instruction::Or:
+    case Instruction::Xor:
     case Instruction::BitCast:
     case Instruction::PHI:
     case Instruction::ICmp:
-      if (llvm::all_of(I->operands(), OpCheck))
+      if (llvm::all_of(Opr->operands(), OpCheck))
         return true;
       break;
     default:
       break;
     }
+  }
 
+  // Conservatively return false
+  if (isa<ConstantExpr>(V))
+    return false;
+
+  if (auto *I = dyn_cast<Instruction>(V)) {
     if (programUndefinedIfPoison(I) && I->getType()->isIntegerTy(1))
       // Note: once we have an agreement that poison is a value-wise concept,
       // we can remove the isIntegerTy(1) constraint.
diff --git a/llvm/test/Transforms/InstSimplify/freeze-noundef.ll b/llvm/test/Transforms/InstSimplify/freeze-noundef.ll
--- a/llvm/test/Transforms/InstSimplify/freeze-noundef.ll
+++ b/llvm/test/Transforms/InstSimplify/freeze-noundef.ll
@@ -19,12 +19,10 @@
   ret i1 %f
 }
 
-; TODO: should look into binary operations
 define i1 @or(i1 noundef %x, i1 noundef %x2) {
 ; CHECK-LABEL: @or(
 ; CHECK-NEXT:    [[Y:%.*]] = or i1 [[X:%.*]], [[X2:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = freeze i1 [[Y]]
-; CHECK-NEXT:    ret i1 [[Z]]
+; CHECK-NEXT:    ret i1 [[Y]]
 ;
   %y = or i1 %x, %x2
   %z = freeze i1 %y
@@ -42,12 +40,10 @@
   ret i1 %z
 }
 
-; TODO: should look into binary operations
 define i8 @add(i8 noundef %x) {
 ; CHECK-LABEL: @add(
 ; CHECK-NEXT:    [[Y:%.*]] = add i8 [[X:%.*]], 1
-; CHECK-NEXT:    [[Z:%.*]] = freeze i8 [[Y]]
-; CHECK-NEXT:    ret i8 [[Z]]
+; CHECK-NEXT:    ret i8 [[Y]]
 ;
   %y = add i8 %x, 1
   %z = freeze i8 %y
@@ -77,21 +73,18 @@
 define i32 @extract({i8, i32} noundef %x) {
 ; CHECK-LABEL: @extract(
 ; CHECK-NEXT:    [[Y:%.*]] = extractvalue { i8, i32 } [[X:%.*]], 1
-; CHECK-NEXT:    [[Z:%.*]] = freeze i32 [[Y]]
-; CHECK-NEXT:    ret i32 [[Z]]
+; CHECK-NEXT:    ret i32 [[Y]]
 ;
   %y = extractvalue {i8, i32} %x, 1
   %z = freeze i32 %y
   ret i32 %z
 }
 
-; TODO: should look into extract operations
 define i32 @extract2({i8, {i8, i32}} noundef %x) {
 ; CHECK-LABEL: @extract2(
 ; CHECK-NEXT:    [[Y:%.*]] = extractvalue { i8, { i8, i32 } } [[X:%.*]], 1
 ; CHECK-NEXT:    [[Z:%.*]] = extractvalue { i8, i32 } [[Y]], 1
-; CHECK-NEXT:    [[W:%.*]] = freeze i32 [[Z]]
-; CHECK-NEXT:    ret i32 [[W]]
+; CHECK-NEXT:    ret i32 [[Z]]
 ;
   %y = extractvalue {i8, {i8, i32}} %x, 1
   %z = extractvalue {i8, i32} %y, 1
diff --git a/llvm/test/Transforms/InstSimplify/freeze.ll b/llvm/test/Transforms/InstSimplify/freeze.ll
--- a/llvm/test/Transforms/InstSimplify/freeze.ll
+++ b/llvm/test/Transforms/InstSimplify/freeze.ll
@@ -123,6 +123,22 @@
   ret float %r
 }
 
+define i8* @constant_expr2() {
+; CHECK-LABEL: @constant_expr2(
+; CHECK-NEXT:    ret i8* bitcast (i16* @g to i8*)
+;
+  %r = freeze i8* bitcast (i16* @g to i8*)
+  ret i8* %r
+}
+
+define i32* @constant_expr3() {
+; CHECK-LABEL: @constant_expr3(
+; CHECK-NEXT:    ret i32* getelementptr (i32, i32* @glb, i64 3)
+;
+  %r = freeze i32* getelementptr (i32, i32* @glb, i64 3)
+  ret i32* %r
+}
+
 ; Negative test
 
 define <2 x i31> @vector_element_constant_expr() {