--- a/browser/extensions/formautofill/FormAutofillHeuristics.jsm
+++ b/browser/extensions/formautofill/FormAutofillHeuristics.jsm
@@ -182,16 +182,27 @@ class FieldScanner {
   }
 }
 
 this.LabelUtils = {
   // The tag name list is from Chromium except for "STYLE":
   // eslint-disable-next-line max-len
   // https://cs.chromium.org/chromium/src/components/autofill/content/renderer/form_autofill_util.cc?l=216&rcl=d33a171b7c308a64dc3372fac3da2179c63b419e
   EXCLUDED_TAGS: ["SCRIPT", "NOSCRIPT", "OPTION", "STYLE"],
+
+  // A map object, whose keys are the id's of form fields and each value is an
+  // array consisting of label elements correponding to the id.
+  // @type {Map<string, array>}
+  _mappedLabels: null,
+
+  // An array consisting of label elements whose correponding form field doesn't
+  // have an id attribute.
+  // @type {Array.<HTMLLabelElement>}
+  _unmappedLabels: null,
+
   /**
    * Extract all strings of an element's children to an array.
    * "element.textContent" is a string which is merged of all children nodes,
    * and this function provides an array of the strings contains in an element.
    *
    * @param  {Object} element
    *         A DOM element to be extracted.
    * @returns {Array}
@@ -199,69 +210,80 @@ this.LabelUtils = {
    */
   extractLabelStrings(element) {
     let strings = [];
     let _extractLabelStrings = (el) => {
       if (this.EXCLUDED_TAGS.includes(el.tagName)) {
         return;
       }
 
-      if (el.nodeType == Ci.nsIDOMNode.TEXT_NODE ||
-          el.childNodes.length == 0) {
+      if (el.nodeType == Ci.nsIDOMNode.TEXT_NODE || el.childNodes.length == 0) {
         let trimmedText = el.textContent.trim();
         if (trimmedText) {
           strings.push(trimmedText);
         }
         return;
       }
 
       for (let node of el.childNodes) {
-        if (node.nodeType != Ci.nsIDOMNode.ELEMENT_NODE &&
-            node.nodeType != Ci.nsIDOMNode.TEXT_NODE) {
+        let nodeType = node.nodeType;
+        if (nodeType != Ci.nsIDOMNode.ELEMENT_NODE && nodeType != Ci.nsIDOMNode.TEXT_NODE) {
           continue;
         }
         _extractLabelStrings(node);
       }
     };
     _extractLabelStrings(element);
     return strings;
   },
 
-  findLabelElements(element) {
-    let document = element.ownerDocument;
-    let labels = [];
-    // TODO: querySelectorAll is inefficient here. However, bug 1339726 is for
-    // a more efficient implementation from DOM API perspective. This function
-    // should be refined after input.labels API landed.
-    for (let label of document.querySelectorAll("label[for]")) {
-      if (element.id == label.htmlFor) {
-        labels.push(label);
+  generateLabelMap(doc) {
+    let mappedLabels = new Map();
+    let unmappedLabels = [];
+
+    for (let label of doc.getElementsByTagName("label")) {
+      let id = label.htmlFor;
+      if (!id) {
+        let control = label.control;
+        if (!control) {
+          continue;
+        }
+        id = control.id;
+      }
+      if (id) {
+        let labels = mappedLabels.get(id);
+        if (labels) {
+          labels.push(label);
+        } else {
+          mappedLabels.set(id, [label]);
+        }
+      } else {
+        unmappedLabels.push(label);
       }
     }
 
-    if (labels.length > 0) {
-      log.debug("Label found by ID", element.id);
-      return labels;
+    this._mappedLabels = mappedLabels;
+    this._unmappedLabels = unmappedLabels;
+  },
+
+  clearLabelMap() {
+    this._mappedLabels = null;
+    this._unmappedLabels = null;
+  },
+
+  findLabelElements(element) {
+    if (!this._mappedLabels) {
+      this.generateLabelMap(element.ownerDocument);
     }
 
-    let parent = element.parentNode;
-    if (!parent) {
-      return [];
+    let id = element.id;
+    if (!id) {
+      return this._unmappedLabels.filter(label => label.control == element);
     }
-    do {
-      if (parent.tagName == "LABEL" &&
-          parent.control == element &&
-          !parent.hasAttribute("for")) {
-        log.debug("Label found in input's parent or ancestor.");
-        return [parent];
-      }
-      parent = parent.parentNode;
-    } while (parent);
-
-    return [];
+    return this._mappedLabels.get(id) || [];
   },
 };
 
 /**
  * Returns the autocomplete information of fields according to heuristics.
  */
 this.FormAutofillHeuristics = {
   RULES: null,
@@ -397,16 +419,19 @@ this.FormAutofillHeuristics = {
       let parsedAddressFields = this._parseAddressFields(fieldScanner);
 
       // If there is no any field parsed, the parsing cursor can be moved
       // forward to the next one.
       if (!parsedPhoneFields && !parsedAddressFields) {
         fieldScanner.parsingIndex++;
       }
     }
+
+    LabelUtils.clearLabelMap();
+
     if (allowDuplicates) {
       return fieldScanner.fieldDetails;
     }
 
     return fieldScanner.trimmedFieldDetail;
   },
 
   getInfo(element) {

--- a/browser/extensions/formautofill/test/unit/test_findLabelElements.js
+++ b/browser/extensions/formautofill/test/unit/test_findLabelElements.js
@@ -81,10 +81,11 @@ TESTCASES.forEach(testcase => {
 
     let doc = MockDocument.createTestDocument(
       "http://localhost:8080/test/", testcase.document);
 
     let input = doc.getElementById(testcase.inputId);
     let labels = LabelUtils.findLabelElements(input);
 
     Assert.deepEqual(labels.map(l => l.id), testcase.expectedLabelIds);
+    LabelUtils.clearLabelMap();
   });
 });

--- a/browser/extensions/formautofill/test/unit/test_getInfo.js
+++ b/browser/extensions/formautofill/test/unit/test_getInfo.js
@@ -233,10 +233,11 @@ TESTCASES.forEach(testcase => {
 
     let doc = MockDocument.createTestDocument(
       "http://localhost:8080/test/", testcase.document);
 
     let element = doc.getElementById(testcase.elementId);
     let value = FormAutofillHeuristics.getInfo(element);
 
     Assert.deepEqual(value, testcase.expectedReturnValue);
+    LabelUtils.clearLabelMap();
   });
 });