Index: flang/include/flang/Optimizer/HLFIR/HLFIROps.td
===================================================================
--- flang/include/flang/Optimizer/HLFIR/HLFIROps.td
+++ flang/include/flang/Optimizer/HLFIR/HLFIROps.td
@@ -731,10 +731,9 @@
     The shape and typeparams operands represent the extents and type
     parameters of the resulting array value.
 
-    Currently there is no way to control the iteration order of a hlfir
-    elemental operation and so operations in the body of the elemental must
-    not have side effects. If this is changed, an attribute must be added so
-    that the elemental inlining pass can skip these impure elementals.
+    The unordered attribute can be set to allow out of order processing
+    of the indices. This is safe only if the operations in the body
+    of the elemental do not have side effects.
 
 
     Example: Y + X,  with Integer :: X(10, 20), Y(10,20)
@@ -754,14 +753,15 @@
 
   let arguments = (ins
     AnyShapeType:$shape,
-    Variadic<AnyIntegerType>:$typeparams
+    Variadic<AnyIntegerType>:$typeparams,
+    OptionalAttr<UnitAttr>:$unordered
   );
 
   let results = (outs hlfir_ExprType);
   let regions = (region SizedRegion<1>:$region);
 
   let assemblyFormat = [{
-    $shape (`typeparams` $typeparams^)?
+    $shape (`typeparams` $typeparams^)? (`unordered` $unordered^)?
     attr-dict `:` functional-type(operands, results)
     $region
     }];
@@ -775,13 +775,12 @@
       }
       /// ElementalOpInterface implementation.
 
-      mlir::Region& getElementalRegion() {return getRegion();}
+      mlir::Region& getElementalRegion() { return getRegion(); }
       mlir::Value getElementEntity();
-      mlir::Region* getElementCleanup() {return nullptr;}
+      mlir::Region* getElementCleanup() { return nullptr; }
 
       /// Must this elemental be evaluated in order?
-      /// TODO: add attribute and set it in lowering.
-      bool isOrdered() {return true;}
+      bool isOrdered() { return !getUnordered(); }
   }];
 
   let skipDefaultBuilders = 1;
@@ -1209,7 +1208,9 @@
 
   let arguments = (ins
     fir_ShapeType:$shape,
-    Variadic<AnyIntegerType>:$typeparams);
+    Variadic<AnyIntegerType>:$typeparams,
+    OptionalAttr<UnitAttr>:$unordered
+  );
 
   let regions = (region  SizedRegion<1>:$body,
                          MaxSizedRegion<1>:$cleanup);
@@ -1219,7 +1220,7 @@
   ];
 
   let assemblyFormat = [{
-    $shape (`typeparams` $typeparams^)?
+    $shape (`typeparams` $typeparams^)? (`unordered` $unordered^)?
     attr-dict `:` type(operands) $body
     custom<YieldOpCleanup>($cleanup)}];
 
@@ -1235,13 +1236,13 @@
 
     /// ElementalOpInterface implementation.
 
-    mlir::Region& getElementalRegion() {return getBody();}
+    mlir::Region& getElementalRegion() { return getBody(); }
     mlir::Value getElementEntity();
     mlir::Region* getElementCleanup();
 
     /// Must this elemental be evaluated in order?
-    /// TODO: add attribute and set it in lowering.
-    bool isOrdered() {return true;}
+    /// TODO: since the body has no side effects, can it always be unordered?
+    bool isOrdered() { return !getUnordered(); }
   }];
 
   let hasVerifier = 1;
Index: flang/test/HLFIR/element-addr.fir
===================================================================
--- flang/test/HLFIR/element-addr.fir
+++ flang/test/HLFIR/element-addr.fir
@@ -81,3 +81,36 @@
 // CHECK:               fir.freemem %[[VAL_11]] : !fir.heap<!fir.array<?xi32>>
 // CHECK:             }
 // CHECK:           }
+
+func.func @unordered() {
+  %c10 = arith.constant 10 : index
+  %c20 = arith.constant 20 : index
+  %0 = fir.shape %c10, %c20 : (index, index) -> !fir.shape<2>
+  hlfir.region_assign {
+    %addr = fir.undefined !fir.ref<!fir.array<10x20xf32>>
+    hlfir.yield %addr : !fir.ref<!fir.array<10x20xf32>>
+  } to {
+    hlfir.elemental_addr %0 unordered : !fir.shape<2> {
+    ^bb0(%i: index, %j: index):
+      %addr = fir.undefined !fir.ref<f32>
+      hlfir.yield %addr : !fir.ref<f32>
+    }
+  }
+  return
+}
+// CHECK-LABEL:   func.func @unordered() {
+// CHECK:           %[[VAL_0:.*]] = arith.constant 10 : index
+// CHECK:           %[[VAL_1:.*]] = arith.constant 20 : index
+// CHECK:           %[[VAL_2:.*]] = fir.shape %[[VAL_0]], %[[VAL_1]] : (index, index) -> !fir.shape<2>
+// CHECK:           hlfir.region_assign {
+// CHECK:             %[[VAL_3:.*]] = fir.undefined !fir.ref<!fir.array<10x20xf32>>
+// CHECK:             hlfir.yield %[[VAL_3]] : !fir.ref<!fir.array<10x20xf32>>
+// CHECK:           } to {
+// CHECK:             hlfir.elemental_addr %[[VAL_2]] unordered : !fir.shape<2> {
+// CHECK:             ^bb0(%[[VAL_4:.*]]: index, %[[VAL_5:.*]]: index):
+// CHECK:               %[[VAL_6:.*]] = fir.undefined !fir.ref<f32>
+// CHECK:               hlfir.yield %[[VAL_6]] : !fir.ref<f32>
+// CHECK:             }
+// CHECK:           }
+// CHECK:           return
+// CHECK:         }
Index: flang/test/HLFIR/elemental.fir
===================================================================
--- flang/test/HLFIR/elemental.fir
+++ flang/test/HLFIR/elemental.fir
@@ -76,3 +76,26 @@
 // CHECK:    %[[VAL_9:.*]] = hlfir.as_expr %[[VAL_8]] : (!fir.box<!fir.type<pdt(param:i32){field:f32}>>) -> !hlfir.expr<!fir.type<pdt(param:i32){field:f32}>>
 // CHECK:    hlfir.yield_element %[[VAL_9]] : !hlfir.expr<!fir.type<pdt(param:i32){field:f32}>>
 // CHECK:  }
+
+func.func @unordered() {
+  %c10 = arith.constant 10 : index
+  %c20 = arith.constant 20 : index
+  %0 = fir.shape %c10, %c20 : (index, index) -> !fir.shape<2>
+  %3 = hlfir.elemental %0 unordered : (!fir.shape<2>) -> !hlfir.expr<10x20xi32> {
+  ^bb0(%i: index, %j: index):
+    %c0 = arith.constant 0 : i32
+    hlfir.yield_element %c0 : i32
+  }
+  return
+}
+// CHECK-LABEL:   func.func @unordered() {
+// CHECK:           %[[VAL_0:.*]] = arith.constant 10 : index
+// CHECK:           %[[VAL_1:.*]] = arith.constant 20 : index
+// CHECK:           %[[VAL_2:.*]] = fir.shape %[[VAL_0]], %[[VAL_1]] : (index, index) -> !fir.shape<2>
+// CHECK:           %[[VAL_3:.*]] = hlfir.elemental %[[VAL_2]] unordered : (!fir.shape<2>) -> !hlfir.expr<10x20xi32> {
+// CHECK:           ^bb0(%[[VAL_4:.*]]: index, %[[VAL_5:.*]]: index):
+// CHECK:             %[[VAL_6:.*]] = arith.constant 0 : i32
+// CHECK:             hlfir.yield_element %[[VAL_6]] : i32
+// CHECK:           }
+// CHECK:           return
+// CHECK:         }